# 1122 程式設計實習IV (資訊一乙) Week04 作業 ## 1. Maximum Sum --- ### 題目敘述 A problem that is simple to solve in one dimension is often much more difficult to solve in more than one dimension. Consider satisfying a boolean expression in conjunctive normal form in which each conjunct consists of exactly 3 disjuncts. This problem (3-SAT) is NP-complete. The problem 2-SAT is solved quite efficiently, however. In contrast, some problems belong to the same complexity class regardless of the dimensionality of the problem. Given a 2-dimensional array of positive and negative integers, find the sub-rectangle with the largest sum. The sum of a rectangle is the sum of all the elements in that rectangle. In this problem the sub- rectangle with the largest sum is referred to as the maximal sub-rectangle. A sub-rectangle is any contiguous sub-array of size 1 × 1 or greater located within the whole array. As an example, the maximal sub-rectangle of the array: ![image](https://hackmd.io/_uploads/H1aD1_zQA.png) is in the lower-left-hand corner: ![image](https://hackmd.io/_uploads/S1BOyuzXR.png) and has the sum of 15. --- ### 題目輸入 The input consists of an $N \times N$ array of integers. The input begins with a single positive integer $N$ on a line by itself indicating the size of the square two dimensional array. This is followed by $N^2$ integers separated by white-space (newlines and spaces). These $N^2$ integers make up the array in row-major order (i.e., all numbers on the first row, left-to-right, then all numbers on the second row, left-to-right, etc.). $N$ may be as large as $100$. The numbers in the array will be in the range [$−127, 127$]. --- ### 題目輸出 The output is the sum of the maximal sub-rectangle. --- ### 範例輸入 ``` 4 0 -2 -7 0 9 2 -6 2 -4 1 -4 1 -1 8 0 -2 ``` --- ### 範例輸出 ``` 15 ``` --- ### Hint 答案如果為負要輸出 0，輸入直到 EOF --- ## 2. Steps --- ### 題目敘述 One steps through integer points of the straight line. The length of a step must be nonnegative and can be by one bigger than, equal to, or by one smaller than the length of the previous step. What is the minimum number of steps in order to get from $x$ to $y$? The length of the first and the last step must be $1$. --- ### 題目輸入 Input consists of a line containing $n$, the number of test cases. For each test case, a line follows with two integers: $0 \le x \le y < 2^{31}$. --- ### 題目輸出 For each test case, print a line giving the minimum number of steps to get from $x$ to $y$. --- ### 範例輸入 ``` 3 45 48 45 49 45 50 ``` --- ### 範例輸出 ``` 3 3 4 ``` --- ## 作業繳交方式 - 交至ilearn作業繳交區 - 原始碼檔名以 學號_題號.c 或 學號_題號.cpp 命名 (example. D1109070_01.c 或是 D1109070_01.cpp) - 兩題分兩個檔案上傳 - 在OJ上面有可以讓你檢視是否正確的作答區 - 名稱: [112 (資訊一乙) 程式設計IV Week04 作業] - 密碼: Copilot