maximum subarray tutorial

maximum_subarray_tutor.md

Maximum Subarray Problem

給定一序列，求此序列中哪一個區間的總和最大。請輸出其總和。

※ 這篇教學中所說的區間都是指連續區間。 ※ 區間的長度為 0 也可以，而長度為 0 的區間的總和為 0 ，所以最大的區間和一定大於等於 0 。

例如：

−2 1 −3 4 −1 2 1 −5 4

最大區間為 4 −1 2 1 其總合為 6 。

-1 -2 -3

最大區間為空區間，其總合為 0 。

---

以下皆假設序列的長度是 N ，

且序列儲存在 data 陣列裡。

---

第一種解法：暴力解

Time Complexity : O(N^3)

就最直覺的想法，沒什麼好說的： 直接窮舉所有區間，每窮舉出一個區間，計算此區間的總和，然後跟目前已知的最大區間和比較，若大於，則代替之。

int max_sum = 0;
for (int i=0; i<N; i++) { // i 是區間的頭
	for (int j=i; j<N; j++) { // j 是區間的尾
		// 計算 區間 data[i], data[i+1], ... , data[j] 的和
		int sum = 0;
		for (int k=i; k<=j; k++)
			sum += data[k];

		// printf("sum from %d to %d is %d\n", i, j, sum);
		
		if (sum > max_sum)
			max_sum = sum;
	}
}

printf("%d\n", max_sum);

這種解法實在是太沒效率了，竟然要用三層迴圈來解，以下提供兩種優化過的方法。

第二種解法

Time Complexity : O(N^2)

這應該是大部分人寫出來的方法，想法是： 同樣是窮舉區間，但利用以下這個性質：

(data[i] + data[i+1] + ... + data[j]) = (data[i] + data[i+1] + ... + data[j-1]) + data[j]

所以我們在枚舉區間的尾時，可以同時計算區間的和，將這個值保存下來，等區間的尾又在向右移一格，要再次計算區間和時就可以利用。

int max_sum = 0;
for (int i=0; i<N; i++) {
	int sum = 0;
	for (int j=i; j<N; j++) {
		sum += data[j];

		// printf("sum from %d to %d is %d\n", i, j, sum);
	
		if (sum > max_sum)
			max_sum = sum;
	}
}

printf("%d\n", max_sum);	

第三種解法

Time Complexity : O(N^2 + N) = O(N^2)

觀察第一種與第二種解法的差別，可以發現，同樣都是窮舉區間，第二種方法可以用更快的方法來計算區間的總和所以更好。這裡提供另一種計算區間和的方法。這個技巧在其它題目中並不少見。

先設一個新的陣列：

int S[N];

讓 S 的第 i 項等於 data[0] + data[1] + ... + data[i] 。

S[0] = data[0];
for (int i=1; i<N; i++)
	S[i] = S[i-1] + data[i];

此時，如果我們想知道

data[i] + data[i+1] + ... + data[j]

那我們就只要計算以下公式：

S[j] - S[i-1]

就可以知道了，因為

S[j] - S[i-1] 
= (data[0] + data[1] + ... + data[j]) - (data[0] + data[1] + ... + data[i-1])
= data[i] + data[i+1] + ... + data[j]

---

所以我們只需要預先計算出 S 陣列，之後每次窮舉出一個區間，我們就可以在一瞬間計算出這個區間的和。

另外，要注意的是，如果 i = 0 時，直接套用上面那個公式會 RE，因為會存取到 S[-1] 。所以此時公式應該變為：

data[0] + data[1] + ... + data[j] = S[j]

至於為什麼，因為這就是之前寫的定義。

---

int S[N];
S[0] = data[0];
for (int i=1; i<N; i++)
	S[i] = S[i-1] + data[i];

int max_sum = 0;
for (int i=0; i<N; i++) {
	for (int j=i; j<N; j++) {
		int sum = S[j];
		if (i != 0)
			sum = sum - S[i-1];
			
		// printf("sum from %d to %d is %d\n", i, j, sum);
		
		if (sum > max_sum)
			max_sum = sum;
	}
}

printf("%d\n", max_sum);

第四種解法：Kadane's algorithm

Time Complexity : O(N)

引入了一點 DP (Dynamic Programming) 的想法，這個題目可以在線性時間內（一個 for 迴圈掃過整個序列就可以了）解出，而且程式碼還很短，超好的方法，以後遇到這類型題目，幾乎都是用這個方法解。

簡單地講就是這樣：

在迴圈中， max_sum_so_far 這個變數一直加上 data[i] ，如果結果 <= 0 我們就捨棄它，重新開始計算。每當有一個新的結果我們就跟 max_sum 比對，若大於就取而代之。

詳細的想法是：

我們設一個變數：

int max_sum_so_far;

代表區間尾在 i-1 的最大區間和。（區間的起始點我們不知道，除非另行記錄）這個數會隨著迴圈一直更新。

當迴圈執行到序列的第 i 項，要計算新的 max_sum_so_far 時，我們可以發現：

如果 max_sum_so_far + data[i] < 0 ，那麼這次計算的區間都不可能是「擁有最大區間和的區間」的一部份。所以我們將 max_sum_so_far 歸零，重新開始累加。

因為最大區間和一定大於等於 0 。

如果 max_sum_so_far + data[i] > 0 ，那麼我們當然就繼續累加下去。

每次計算完 max_sum_so_far ，我們就將它與 max_sum 比較，若大於，取而代之。

---

int max_sum_ending_here = 0;
int max_sum = 0;
for (int i=0; i<N; i++) {
	// 現在 max_sum_so_far 是區間尾在 i-1 的最大區間和，我們現在要更新它。
	if (max_sum_so_far + data[i] < 0)
		max_sum_so_far = 0;
	else
		max_sum_so_far += data[i];

	if (max_sum_so_far > max_sum)
		sum = max_sum_so_far;
}

printf("%d\n", max_sum);

或者寫：

int max_sum_so_far = 0;
int max_sum = 0;
for (int i=0; i<N; i++) {
	max_sum_so_far = max(0, max_sum_so_far + data[i]);
	max_sum = max(max_sum, max_sum_so_far);
}

printf("%d\n", max_sum);

---

如果需要輸出區間頭尾的 index，可以這麼寫：

int max_sum_so_far = 0;
int max_sum = 0;
int max_sum_left = 0, max_sum_right = 0;
int left = 0, right = 0;
for (int i=0; i<N; i++) {
	max_sum_so_far += data[i];
	right = i;
	
	if (max_sum_so_far <= 0) {
		left = i+1;
		right = i+1;
		max_sum_so_far = 0;
	}
	
	if (max_sum_so_far > max_sum) {
		max_sum_left = left;
		max_sum_right = right;
		max_sum = max_sum_so_far;
	}
}

printf("%d from %d to %d\n", max_sum, max_sum_left, max_sum_right);

如果看不懂，嘗試拿紙筆模擬看看，應該就能理解了。還不行的話，網路上自己找教學。

題目練習：

似乎都要用最後一種方法才能 AC，其它方法會 TLE 。

uva: 507, 10684

參考資料：

Wikipedia Maximum Subarray problem

DJWS 演算法筆記

problem.md

以下提供簡單的測資，下載檔案請點選 Raw，然後右鍵另存新檔。請不要用複製貼上的方法，空白行等可能會漏掉。

要測試你的程式對不對請使用以下指令，假設你的執行檔是 test.exe ， 然後 input.txt, output.txt 都跟 test.exe 放在同一個資料夾裡（假設是 D:\temp）

D:\temp>test.exe < input.txt > myoutput.txt

D:\temp>Fc myoutput.txt output.txt

標準程式為用來產生正確解答的程式。底下那兩個程式只是我保留記念的。你要拿去玩玩也歡迎。

Input

第一行為一個正整數 T ( <= 100) 代表測資數。 每筆測資一行，每一行的第一個數為 N ( <= 100)。之後有 N 個整數，代表序列，皆保證 int 可存。

Output

針對每筆測資請輸出該序列的最大連續區間和並換行。

Sample Input

2
3 -1 -2 -3
4 1 -1 3 -4

Sample Output

0
3

產測資的程式

Written in Python 3.4

# -*- coding: utf-8 -*-
from random import randint

for t in range(100):
    print(100)

    N = randint(1, 100)
    print(N, end=' ')
    
    for i in range(N):
        if i is not 0:
            print(' ', end='')
        
        print(str(randint(-300, +300)), end='')

    if t is not 99:
        print('')

標準程式

#include <stdio.h>

int max(int a, int b)
{
	return ((a > b) ? a : b);
}

int main() {
	int T;
	scanf("%d", &T);
	
	while (T--) {
		int N;
		scanf("%d", &N);
		
		int max_sum_so_far = 0;
		int max_sum = 0;
		for (int i=0; i<N; i++) {
			int inp;
			scanf("%d", &inp);
			
			max_sum_so_far = max(0, max_sum_so_far + inp);
			max_sum = max(max_sum, max_sum_so_far);
		}
		
		printf("%d\n", max_sum);
	}

	return 0;
}

problem_input.txt

100
66 300 -190 -220 -143 70 -176 -228 -196 197 214 -214 -104 51 155 91 215 -218 164 71 -112 182 -170 -193 -57 -239 46 14 -203 233 17 -101 -215 8 -83 -8 -5 294 24 -206 257 -33 -213 -42 248 114 -217 94 -57 -266 121 248 -119 210 -296 -286 -281 -201 -206 -162 -30 -227 -18 232 9 143 57
85 218 -20 149 179 -60 7 -204 -118 -20 -152 106 -112 -62 -25 -129 260 -281 276 242 101 -87 -237 -98 -13 -103 -149 157 128 -216 -35 -86 -127 3 -243 -221 -46 -292 -195 47 260 275 12 -193 257 77 -145 236 -153 -134 -105 229 -229 -156 165 -223 -12 -254 154 -213 -266 -76 -55 114 -165 -170 53 -133 124 -264 198 145 -6 39 153 -214 33 -230 -104 -68 153 276 192 188 81 12
61 54 -258 -148 -154 131 -241 -135 -101 -231 216 -60 -115 81 -48 293 188 60 275 16 -68 242 -97 3 -93 33 -154 -161 260 174 10 186 -50 292 72 240 -95 -13 -44 -187 -163 200 -124 -196 52 -256 231 -192 -98 174 -7 -98 134 -289 108 -11 198 -256 64 174 71 273
67 -215 14 -140 -162 174 -267 -147 289 -271 81 42 -251 -201 -46 -1 -10 20 -235 22 -227 -194 -72 -215 -247 63 56 -70 -7 -22 -151 -68 -99 -210 55 -26 145 142 153 -238 143 -133 173 -294 -189 -185 -43 174 -120 101 -138 -182 -189 -84 91 47 -5 95 253 81 148 -271 49 66 -292 -58 -266 -102
66 -21 196 122 -207 -20 264 -253 -38 -178 49 51 102 46 -193 -192 39 259 -183 7 246 -101 -42 -165 -237 -2 52 -45 -213 -144 15 199 171 116 -62 -217 -208 -22 227 179 233 -138 -125 140 35 130 277 180 275 -258 66 -273 298 -293 -50 -275 -24 167 85 -173 266 -217 125 -52 -287 235 181
25 -175 180 -254 -142 72 58 -54 -30 -104 -207 257 -5 -200 -130 -156 -224 228 -265 199 225 114 276 -72 127 -175
71 121 12 -160 -228 -57 -100 222 230 297 -237 167 274 72 157 -260 -81 167 -273 -64 254 25 44 -165 -12 19 -32 -75 22 -39 -278 -133 -192 -222 -226 -214 -174 -164 -117 54 268 -52 65 -263 -201 -181 -255 121 283 265 -160 -213 -56 76 -184 75 -289 -235 -17 -197 148 -284 -190 -210 -66 -34 -295 176 244 73 -251 -72
67 -188 278 -125 82 -169 -66 -137 124 -122 104 12 -215 283 -133 -157 285 -145 -193 29 61 281 -31 2 -100 -108 240 142 148 -115 1 185 -210 -48 226 -26 199 43 121 -89 105 125 36 -59 299 289 163 203 -176 286 213 269 -288 197 -217 127 -177 61 -116 259 -5 44 121 -224 192 152 119 129
96 -99 160 -191 -100 -261 234 -217 169 53 -240 -155 203 -81 -216 -159 -133 264 -239 62 -52 -18 68 -133 269 87 -143 -44 -76 -296 -297 -81 17 214 43 175 18 230 -207 -10 -39 108 196 264 208 -290 267 -223 45 270 198 -41 -181 -76 257 -243 -190 -194 182 150 -249 59 -67 -284 42 133 -185 112 33 14 -98 -276 -210 -59 -87 -154 -186 -150 148 -7 130 -233 294 13 -156 -10 37 -15 -258 162 198 216 62 37 -180 146 -190
78 -81 10 -137 274 -224 -185 -261 -118 -110 -281 -42 -197 267 68 125 -184 -116 -15 -132 169 -77 -14 66 59 183 -116 -239 125 147 -281 -137 -186 245 228 -60 30 2 236 -150 210 285 132 247 107 -207 32 226 91 -205 204 -159 188 -207 -193 46 -51 -155 -189 152 -157 138 -90 288 19 81 224 -55 -116 -181 201 -64 -134 -87 -123 31 40 209 166
54 235 -102 -118 -133 -9 -157 -146 158 137 190 -118 -188 -108 -19 65 -295 121 -19 240 203 -123 248 53 -22 -248 46 19 -65 -82 258 -225 -249 142 -177 272 97 48 -167 -106 133 63 -74 214 181 74 -219 129 -86 -274 203 -100 -297 -243 6
85 38 -195 -224 270 247 -194 -143 -88 219 12 -44 239 300 -246 -73 -11 182 119 -189 -130 117 5 -110 271 -53 -240 -264 70 156 91 281 232 254 171 -254 -238 -101 211 22 -156 259 106 1 -170 -146 -25 -132 184 -188 -144 -36 43 -46 -67 -121 -117 -256 96 -202 59 -155 56 17 159 211 279 194 116 111 -125 -277 41 -298 241 -53 -128 -81 -256 -25 20 -173 -110 287 -235 227
54 208 -50 27 59 88 -194 -34 -170 -102 19 -247 -248 268 -133 -115 -50 137 90 -3 243 61 45 158 -297 12 -296 175 -27 267 67 70 151 276 -172 129 230 170 145 102 -229 77 -154 -47 199 82 -208 -204 21 -233 263 21 92 125 -40
35 141 205 -212 -24 253 -214 90 -189 -103 139 179 254 -119 -234 107 -248 242 -217 -23 216 23 -31 -207 -43 60 -141 223 101 -201 110 110 82 93 -60 -208
77 122 -194 -265 -92 241 299 -157 161 196 -280 -68 37 -188 -93 148 185 -129 -153 -56 -167 272 -94 -281 44 89 7 -292 -290 223 -153 -201 -142 -134 -282 -77 -84 -120 -3 -126 266 107 180 15 -233 -268 243 -200 227 272 187 -152 -6 270 -115 -251 -28 -113 -18 107 61 -111 278 -300 -294 284 163 290 -76 -175 114 160 -296 166 -251 107 270 87
78 64 189 -149 224 -149 186 194 -202 -61 220 -287 -272 215 31 29 77 -268 -139 -225 253 136 -4 97 128 -159 206 -121 -13 -34 281 -55 -194 257 242 45 -180 -91 -184 -282 -146 176 -199 -251 -243 116 -57 17 166 293 290 127 -288 175 17 -119 46 -290 -78 73 -296 -136 -12 -82 83 295 151 -208 -110 -256 129 264 239 -74 -299 1 -157 -260 99
80 41 -57 145 -254 -136 -124 256 172 47 15 -48 71 -10 50 -10 109 -2 -55 -275 240 4 156 -159 278 -205 229 198 -174 -100 -50 118 11 -248 -295 82 230 -236 -16 294 11 -166 -44 72 178 -195 -282 -94 -128 288 -206 273 223 -238 292 227 103 -23 20 269 10 204 44 280 -172 210 -206 -148 -266 -74 58 233 215 150 22 227 -103 -28 111 156 -137
28 -37 90 292 -87 -214 -83 266 235 -282 213 256 284 176 -226 168 23 25 264 -188 -280 -182 85 273 26 192 -295 190 -247
10 221 261 -87 74 -161 -285 -159 257 -45 -14
97 53 -265 -124 131 -255 -228 213 144 -239 -257 -189 -242 269 201 -170 -181 -100 157 213 288 139 -202 -83 -124 -63 61 -40 191 42 149 -254 70 -282 -39 244 293 46 -145 245 69 -31 -258 225 -118 -10 -144 -291 -55 -234 -151 269 268 145 -283 27 -84 10 -212 -77 141 122 262 147 -266 122 268 45 131 -135 75 -189 -143 24 149 -262 -138 -221 -169 -146 -246 -117 205 -246 -257 254 -227 -33 292 -116 -263 45 -230 11 78 -102 171 252
42 289 -26 156 299 295 177 -239 -105 133 253 259 -153 2 -197 192 275 205 -173 89 92 253 248 -117 204 1 -281 104 -113 -295 162 58 -175 281 -165 -286 198 249 -20 -37 -67 277 285
26 -222 28 73 -256 -92 267 100 -105 -270 52 235 -86 -259 30 -5 -138 38 16 -180 -270 8 -171 78 -189 -141 -217
13 -286 -220 -142 90 157 -41 -290 215 -84 240 -173 -14 187
31 -53 131 96 -213 -224 -242 240 -234 166 86 -30 116 -204 183 238 -150 -149 -204 -119 -267 -10 -176 -230 268 226 148 -51 294 179 202 -258
22 219 230 83 29 255 103 -125 -221 99 85 211 -22 239 22 94 -296 226 115 280 121 -81 -252
9 215 69 199 56 13 -158 273 175 -174
12 -274 -229 -57 -299 -15 -81 -56 264 -48 269 -21 -236
23 273 290 -53 213 140 107 165 13 147 212 139 -296 166 -138 -54 -193 85 22 122 -74 -107 -4 111
33 203 146 -58 140 127 185 113 -39 -110 -53 94 -255 -239 -101 -115 289 257 4 156 -121 227 -288 -260 292 71 -123 -242 183 272 296 -128 82 248
53 69 -52 -248 228 -25 279 155 -234 -286 91 -83 233 -197 43 151 52 186 186 118 -202 147 -158 -264 13 -231 -106 -84 76 -265 -49 -233 -220 -166 -202 177 -136 -44 -68 -149 95 122 17 -287 237 -250 -165 -273 4 -267 206 -44 -219 -223
96 192 100 286 -173 205 -268 7 88 -94 -37 -228 221 203 -5 118 -169 117 77 -140 276 -151 16 6 -65 151 -171 -28 -253 -7 203 155 111 204 237 184 -31 -45 -212 165 -247 107 272 -228 72 -24 239 140 -43 -173 22 -277 -136 -10 -189 248 -178 -186 -101 120 143 -48 240 -65 -227 271 -128 -16 -117 -73 272 243 -91 182 225 -298 205 293 161 85 6 -70 -148 -169 59 62 -109 218 -255 164 -35 -192 -76 103 194 -188 -4
39 136 253 -123 -219 -64 56 188 -124 143 -8 88 145 10 228 -47 278 -26 -100 -225 93 106 -189 -146 -132 192 -187 36 -79 -232 -231 86 247 145 -157 146 -143 -174 -188 -159
7 -61 145 -173 292 189 -50 37
46 -154 -272 -9 154 -270 -56 -114 141 133 -124 -195 -25 280 175 -291 186 -92 -289 -126 -156 219 182 -239 275 -9 37 38 230 140 -277 -283 4 98 -59 1 149 229 135 269 41 -228 -278 -98 -95 27 30
99 277 -193 11 111 63 294 3 164 -33 144 -60 213 115 -251 70 -165 -31 -3 -22 -292 203 130 -206 -261 187 133 42 -205 9 151 139 -13 127 224 219 -89 249 -152 237 231 -181 235 122 29 -109 248 -122 -45 -185 -124 -169 -74 -63 -274 -90 167 291 -25 258 -85 -162 127 293 -83 0 102 -54 -2 106 192 262 73 -262 42 201 -283 5 89 120 284 -247 -264 -6 274 -32 -151 -258 192 -148 -269 -23 51 136 40 -109 280 176 196 207
100 39 173 167 238 -198 -25 17 180 -226 -76 -226 134 -218 221 104 -81 -296 -232 207 -145 298 12 67 28 -76 50 -130 -104 -128 224 223 -160 -47 18 -120 -199 -229 59 54 150 284 18 -60 -82 -157 65 -81 -242 253 -271 283 -133 109 -256 39 -40 -231 -43 -114 -173 149 229 -58 -183 -15 -75 -250 13 -22 101 -57 31 -29 28 -146 26 102 -214 1 295 -55 8 -285 -231 -297 147 -68 -39 -84 189 172 -228 -246 -66 197 151 -170 268 -47 112
9 -202 191 -184 272 -206 193 50 -160 194
36 113 161 92 -198 -168 -32 -292 -130 -41 103 -212 140 265 -290 125 62 -106 298 279 24 223 -91 164 108 12 -143 225 90 -227 88 268 269 -283 -275 159 43
62 -69 -77 274 -267 -25 220 -25 124 -264 -177 114 77 231 283 28 147 247 -217 -75 -146 -247 138 216 -87 96 -172 -238 -295 -205 -110 -199 -146 -254 214 192 -119 -235 -57 -195 -208 88 -256 -213 -101 -40 298 7 216 -29 279 -217 -139 -64 143 290 278 190 129 231 257 -100 292
4 -130 -235 -196 0
68 -288 -70 -253 -58 -75 54 18 -291 -203 167 198 -209 -149 235 -234 137 233 134 -36 -112 -17 -113 -2 -58 -148 263 84 -163 297 102 -239 -63 -53 131 -289 -111 -118 191 43 -187 -213 -99 -200 1 10 -279 -90 89 -114 246 -71 -111 206 21 49 71 -235 -10 104 234 -40 -48 110 186 259 90 253 -188
96 -172 -273 178 9 31 33 -286 35 270 155 1 -208 139 48 53 62 123 243 -179 241 97 -280 -11 274 -41 -160 256 162 -282 279 188 96 238 290 -279 -42 98 -98 224 103 292 150 -72 184 118 -166 165 -87 -13 157 -67 276 249 -198 -294 -137 -165 -64 137 -241 -131 100 -201 181 229 -66 143 -24 21 183 -64 227 222 182 -137 -50 292 -78 24 60 -28 231 -206 -106 -266 -223 -41 -34 -154 274 108 117 284 276 -108 -264
76 -145 -44 -44 -124 10 -57 -194 -216 -45 189 77 -207 240 -166 178 -262 -189 -14 -83 -237 299 81 150 267 -120 -155 -78 -184 -178 -182 -55 228 -95 -15 -122 1 21 202 -119 43 121 67 206 -179 -189 -24 291 227 -256 -95 52 -251 -281 251 -128 -97 -31 83 -234 157 94 -66 -245 -171 197 -143 -265 292 -96 -232 -109 14 160 -203 -212 234
17 132 -245 -283 -198 -43 -20 -219 163 165 -61 -143 142 -283 -198 -196 181 -137
1 -130
71 -217 -209 -288 66 8 20 134 -75 98 -110 36 -270 -24 -204 274 -139 -141 82 -264 294 137 52 267 -239 -215 -205 192 -93 -106 157 65 -141 -113 243 251 -93 -176 147 226 94 -75 -126 139 -292 -154 27 233 211 258 -165 -168 179 -179 -142 300 74 181 -142 -7 -217 20 -279 -178 -86 37 130 34 -77 -156 -178 -146
72 -179 -76 227 228 -21 244 31 126 19 -31 87 42 -144 265 -209 -74 67 -79 178 128 -135 -285 88 -20 -136 174 38 223 60 291 176 -294 159 -140 -257 69 -88 4 108 73 288 -9 199 -45 -93 -128 16 221 -189 270 -260 -34 -243 -299 -135 297 219 -217 16 190 10 156 256 116 192 -283 44 245 48 -168 217 -85
78 -24 -99 -295 -134 -190 125 137 38 -198 213 70 -25 31 192 -13 224 254 -203 -155 249 -134 -106 259 203 236 48 -45 -99 54 279 163 -102 -190 151 281 -213 -143 -13 -117 1 102 164 -53 264 238 -126 198 -169 292 -3 206 -16 298 63 -168 55 -299 29 -209 -166 -259 -39 -90 287 -108 101 156 143 97 159 -204 -55 -58 -166 156 -188 154 -267
53 -173 116 -40 47 -109 161 -29 -1 -116 -272 25 -117 -81 -99 -79 277 5 213 -266 -176 -205 217 -63 7 120 46 203 228 165 -300 68 -120 173 -149 -123 67 78 -3 -125 -255 224 -76 157 -168 -171 -30 -204 127 -257 -144 -101 300 241
1 -270
35 231 -198 -237 222 21 283 -35 -2 -141 -124 42 97 -5 92 -239 184 237 121 -95 57 -68 -123 -229 92 195 244 -167 -60 -83 91 113 93 101 -205 249
60 217 -112 -16 -159 -123 122 231 -105 -108 197 4 197 -143 178 93 291 -251 133 172 94 62 -11 232 -220 86 -279 245 -83 -271 199 91 100 -34 149 -181 -296 51 -76 223 -133 211 279 -92 179 88 43 -93 57 -60 128 -200 -119 267 28 -143 58 163 -235 190 111
27 -220 -141 -205 10 240 220 -113 -276 -129 -136 260 9 295 -226 106 -265 -91 195 248 -23 52 29 165 218 141 50 -134
39 -199 174 297 286 296 230 -199 248 -147 -231 96 -45 -188 -90 -248 -212 -139 -146 54 -242 -273 -294 -181 225 164 -218 -34 96 -80 -226 228 -123 15 227 -166 -163 -87 -268 297
46 21 -151 -231 -39 103 -265 -278 -82 -7 -282 -95 -126 140 60 -282 235 -276 263 -212 -67 193 75 252 106 -60 -252 -215 -277 -12 129 297 -276 26 -176 -257 -215 -195 -69 -263 67 -298 -241 -149 143 -132 -269
32 -192 285 87 62 11 -150 -206 50 -265 223 -75 -193 -116 134 23 9 255 287 -90 -68 259 -112 -77 -49 277 202 29 165 -84 -3 264 299
48 -267 261 -30 -265 -97 -55 148 97 -181 -9 -104 204 239 107 -220 85 199 71 -233 234 104 -137 285 -298 285 -295 29 -89 -104 95 68 235 143 163 95 -8 -215 -245 125 -20 275 201 252 73 107 99 -215 -157
19 38 59 134 145 -156 -189 -289 -206 175 -202 -173 -80 147 228 -240 -210 80 -299 -77
71 299 23 -196 286 -234 -188 41 -298 65 -95 66 -28 147 -21 211 -69 41 -141 279 -83 245 262 210 -224 229 -20 171 -139 -162 -207 -17 157 300 280 76 225 1 100 -256 276 204 -268 -128 289 -284 56 126 55 79 140 -213 184 148 -4 -156 -115 90 41 98 -139 -110 -247 1 -255 41 -75 -3 -249 -241 297 -73
18 -262 21 208 -288 6 224 -229 33 231 193 59 293 -17 -123 -72 149 107 -191
81 160 135 244 -242 173 220 -150 -175 67 -38 -229 124 55 -152 141 -276 -186 -226 185 121 180 5 -278 -4 -54 -246 10 239 -14 100 -222 176 51 -199 72 151 109 129 49 -158 37 -3 111 -98 -207 220 -176 97 160 200 285 293 -29 169 -179 47 123 -180 185 273 -168 95 60 172 17 -140 -261 -281 -121 277 116 -25 -242 -41 203 -171 186 216 -183 252 20
43 230 292 -289 -209 -212 -81 -6 -60 159 159 -215 -46 -109 76 -106 -151 187 -270 -131 282 -145 -176 276 235 -265 98 185 -108 84 -216 -256 33 -174 -122 -116 -93 -209 12 -239 -182 -297 -56 199
63 83 181 79 77 -140 250 76 0 -222 166 195 75 -17 -256 9 -280 -140 -81 35 -140 -157 -126 30 254 -275 -136 -145 208 -234 -159 263 17 85 102 194 98 -149 -281 52 -32 -125 246 -276 -235 -196 256 -300 106 -25 -13 -298 -33 -13 -265 216 42 216 182 -185 -204 -33 168 -297
98 -253 -299 -145 -79 145 28 -264 270 78 -21 -30 33 -282 -33 205 44 -161 -98 -150 -163 -270 140 -110 34 209 13 -258 -271 -217 -8 -111 150 234 172 -159 -37 -86 178 230 16 79 -34 296 132 -43 212 56 292 40 -82 195 -110 132 -255 -263 277 120 33 157 -185 -230 -92 144 91 -228 64 106 235 149 -49 281 298 -121 60 -39 -122 -78 105 165 51 35 34 64 -226 -134 204 174 124 55 -299 -166 115 91 -137 -192 -95 53 -47
38 -18 0 130 -149 54 -261 -119 -211 202 -18 242 144 238 239 255 136 -93 269 -48 92 -153 260 196 -292 -23 167 190 -245 -249 -125 -214 33 103 85 158 -195 75 78
74 -259 -138 -107 225 71 132 -236 -98 -22 227 121 -176 -237 284 -187 -228 -187 182 -167 -64 241 -160 -280 210 110 -219 3 -175 258 1 10 -68 -17 -156 93 210 160 -54 185 -6 286 151 202 221 -29 -32 114 -43 117 243 -49 -95 -76 21 44 51 -2 77 -100 169 -50 295 4 1 110 154 161 203 182 -83 220 283 253 -81
18 242 92 260 215 127 116 196 261 123 225 61 216 8 153 229 198 203 61
50 230 101 280 43 275 148 -274 59 252 -63 237 -165 -272 20 117 29 173 192 -196 238 195 125 31 265 112 221 111 -233 -210 -215 -138 202 -279 -91 -122 -28 110 277 -135 264 60 -226 197 90 -241 -154 -261 102 -77 152
52 -124 263 119 144 284 -119 -239 194 272 32 -220 46 -195 258 -162 -148 -91 -36 47 137 -277 -278 -242 64 -58 186 81 -94 -141 172 258 -247 -126 184 -238 137 242 188 -289 59 240 -13 283 286 188 262 260 223 18 130 255 262
24 -280 71 234 -70 -131 -118 154 -9 -20 8 257 201 78 -108 128 -120 95 113 35 -164 -2 -54 -295 7
95 -30 -191 -69 -102 192 151 -72 -227 157 -179 36 18 -60 284 -212 -65 144 -29 -104 243 -204 44 297 201 254 -295 172 280 -93 50 -265 -177 52 89 -269 100 -285 -173 284 -245 2 -247 145 166 -294 -62 -199 155 -160 -293 229 -60 250 -108 -120 130 124 84 54 -11 105 52 61 -286 -139 10 -178 276 -221 27 67 -191 0 -109 113 56 126 -294 164 20 57 -280 -38 233 -4 136 -285 137 242 -120 -192 255 200 68 87
79 -249 -197 -143 200 -161 66 92 -109 186 20 -204 193 160 36 -71 -115 123 229 -226 135 -138 -296 225 45 -254 -10 136 -30 -130 -191 114 -80 -82 -197 -229 178 -154 219 -178 -186 276 220 15 -127 -284 -267 -73 -170 95 271 11 -35 39 -65 -247 117 235 -62 212 -277 -135 -251 -171 -220 141 -46 -167 217 17 -44 -245 -272 52 202 -247 -274 210 -101 -268
66 41 -250 300 15 127 70 206 194 75 -208 119 119 121 -282 135 286 159 -195 225 -132 -28 -116 -205 239 3 -291 -265 -175 -21 -102 -100 -246 -241 -162 90 299 286 159 258 97 75 -282 -195 -150 257 192 294 105 -73 -84 89 -106 154 112 -39 -31 205 -44 -96 -174 26 -65 -183 -148 88 -284
25 -146 -63 -27 232 -34 -236 14 124 116 -270 73 244 -16 83 -97 62 -237 101 53 -227 149 -5 -123 -18 240
9 287 72 83 -150 155 -2 167 195 99
21 -5 -166 -88 -94 193 -124 171 3 -98 143 -292 -220 66 -213 102 83 -133 -186 -176 -271 -23
77 -212 -162 42 147 -295 -275 242 246 78 -99 249 109 -130 -135 278 157 233 -147 189 -209 -95 -123 200 -166 -81 -286 262 -81 59 230 -30 201 177 -69 108 -190 -293 -173 23 152 62 149 -122 39 277 -94 -130 -284 -140 254 275 62 -152 -4 73 155 256 2 -79 208 39 223 233 -290 -219 167 -221 -135 -160 -14 299 175 285 96 -91 -115 22
20 -95 279 -265 233 86 248 -114 -232 -104 76 -58 -300 -256 -42 155 -60 -145 200 -257 -178
58 91 -129 116 -271 15 -79 -245 80 293 -22 -11 161 -64 93 163 -86 -181 238 -106 201 -156 -16 208 -242 201 183 -224 173 94 90 -266 -177 142 -261 124 278 90 -12 178 -159 175 -83 180 258 -162 172 299 -126 -124 201 -224 -22 60 166 123 -230 -118 28
5 267 -48 126 36 -249
69 -125 -230 292 -44 -228 -224 -270 292 274 291 -227 -256 -52 26 119 -147 -47 -41 162 -165 133 29 -239 -263 26 57 -102 266 -160 122 -117 -93 287 -18 -90 39 170 250 37 -221 -67 -281 -78 278 -139 197 287 -37 293 -130 224 242 -108 264 -259 121 -184 22 -235 276 -139 221 0 -113 -300 44 -176 72 -49
28 154 293 111 -109 223 289 -6 283 146 261 -178 -281 99 -178 127 284 107 -182 167 198 248 0 -297 -156 291 7 271 184
1 -150
48 5 -169 183 -185 73 -182 -196 -204 57 -210 -253 178 -109 -212 -24 79 -107 -248 59 289 -222 -216 27 -81 90 262 151 -215 -141 212 -72 39 -168 7 81 -129 42 -104 -25 -8 -273 -251 125 -218 -218 35 -253 -61
74 97 -273 -68 -156 16 -72 -10 186 -122 -182 271 137 -45 -104 -247 -146 197 18 -16 -84 155 156 191 -232 246 -52 36 133 -55 152 135 114 11 15 229 255 -172 200 -174 -112 -197 267 287 120 -181 -282 22 212 189 -288 267 79 -242 271 -154 115 36 -12 287 57 101 261 -53 -255 -106 178 -90 -196 234 165 39 264 257 -254
19 -79 -268 -233 171 -28 -173 66 -9 167 111 18 -217 63 -62 272 220 226 -209 237
23 -92 -236 -150 26 155 194 119 287 123 -97 -262 -76 145 270 200 -191 110 298 -94 138 197 -248 191
76 -31 21 5 -94 113 -208 167 -136 -99 -96 -13 -182 -189 117 -227 35 202 220 62 246 270 -150 158 254 195 105 168 79 -292 12 134 -270 -216 -183 -14 -26 192 -157 108 173 93 -100 176 91 203 153 -67 -246 -98 -132 289 194 -242 -104 -33 -44 158 -281 63 -1 104 130 -155 -138 -40 247 -152 140 26 -104 -28 100 -60 -126 198 49
54 -88 80 -170 49 227 18 -21 -200 -260 -230 -210 -141 -266 117 -19 150 -33 37 -256 212 156 -46 -86 268 249 168 101 -47 234 -165 278 -270 -107 5 -114 -24 -245 -227 291 228 104 -38 -47 -56 84 37 -167 -55 282 238 -182 -148 71 -221
25 147 -136 8 218 43 263 -281 241 -59 -214 199 -197 139 -53 -66 44 62 5 -246 -123 206 58 265 171 202
13 -78 -284 24 -173 -297 -252 -76 70 285 13 -80 -150 50
61 -148 -134 -145 -151 -202 -131 -154 -230 -69 15 -231 2 219 58 239 70 -89 -6 1 -66 30 292 -75 192 -192 35 44 -251 51 149 -160 101 -164 23 -150 136 -134 -192 279 25 -70 3 -292 -259 160 109 129 217 143 20 123 -225 187 261 51 226 -89 -250 35 101 277
98 213 268 47 92 73 120 -148 -132 -240 241 161 -72 -121 -242 158 141 166 -276 -47 0 -191 -137 120 144 179 -149 43 156 -35 161 32 129 151 -241 298 96 124 -212 -300 -256 -95 213 268 233 -134 208 201 -46 -224 -71 -56 -238 209 126 -100 7 -53 -85 23 117 -215 -73 -284 267 0 279 -65 -150 237 -241 215 57 196 -296 -163 175 40 128 -286 -286 150 -136 -278 49 -125 -218 18 -226 93 -262 -46 168 32 -101 232 -144 -49 -24
9 238 -95 -90 255 -114 35 -32 -239 274
92 134 104 85 -11 -286 122 -145 257 40 65 -20 -19 139 -122 113 111 252 224 271 -155 108 -235 -162 -87 -251 -167 -267 -141 -178 -112 264 -150 137 -157 177 -241 -137 79 -18 178 -80 163 73 -91 213 154 -156 -83 -15 -125 -31 -254 -79 -227 -190 7 -199 -157 -78 210 278 -178 -113 196 -242 -245 159 27 -141 271 -107 115 160 -13 -128 68 -264 17 -79 -191 164 56 186 109 152 -261 -158 153 -293 -157 112 -117
45 -284 -142 248 -158 88 28 12 -33 -213 163 -154 -272 -288 -185 -21 -68 123 79 -163 155 -175 80 173 250 24 -293 93 119 -144 -129 287 -32 -165 -282 124 198 141 -130 56 69 13 -261 -125 233 -206
93 -143 -50 -68 6 1 140 172 -7 -39 5 205 31 -37 -155 -292 -170 12 68 -163 -100 -35 -90 -260 -265 -228 178 -161 -288 142 -167 25 273 264 279 179 -10 -53 111 -31 -52 184 -149 -196 131 171 -71 -170 -36 25 245 19 -110 242 264 51 -200 -66 -206 -44 -32 51 -146 3 57 73 219 -230 154 -174 146 -97 -192 166 30 -15 184 117 300 266 1 62 -293 53 207 -210 -198 199 269 77 59 -115 117 29
49 -141 -166 -44 -35 -184 159 217 57 167 -80 -300 255 -101 -282 -299 -5 -267 -218 98 102 33 149 103 284 -78 67 -152 -209 -57 -93 188 -228 -11 59 289 -156 247 19 57 -143 238 -277 -152 242 212 141 -172 294 79
96 128 -66 -12 -166 -170 33 -102 7 42 139 178 -3 16 -190 17 -117 20 -200 185 55 139 260 -145 36 -184 -18 24 141 -180 199 -114 163 99 -5 29 -216 -231 -33 -153 99 -299 -176 -266 -180 147 -159 201 -274 -297 -267 -229 -277 -158 -267 -50 41 -154 96 -50 172 258 62 -297 283 -242 46 -251 182 170 -111 -122 70 -21 160 -223 147 178 -203 133 -156 242 198 -260 273 24 -1 225 -107 278 -95 -78 -79 -279 -272 94 -137
21 -223 66 -238 -286 -239 -42 65 123 -68 8 -158 135 146 121 -26 -136 142 36 -16 168 203

problem_output.txt

692
902
1795
710
1413
869
1182
3078
1484
1682
855
1451
1733
572
967
1065
2180
1402
482
1035
2587
367
371
1266
1747
842
485
1646
1253
897
1936
957
481
1180
2669
617
350
1783
2061
0
1314
3664
797
328
0
1045
2089
2910
923
0
958
1819
1163
1332
626
1720
1909
376
2297
854
1997
529
820
2867
2003
3619
2986
2484
2772
812
1026
645
1712
384
906
288
2188
581
1900
381
1417
2356
0
503
2998
883
1542
1921
1322
902
368
1475
1408
308
1314
546
2206
1173
1153
773