562 - Dividing coins

[connor]

I try your input and got right
but still get wa on oj
i don't know why==
plz help me
3ks

here is my codes:

#include<stdlib.h>
#include<stdio.h>
int min(int a,int b) {if(a>b)return b;return a;}
int abs(int a) {if(a>0)return a;return -a;}
int f(int sum,int a) {return abs(sum-a-a);}
int fmin(int a,int b,int sum)
{
int res=min(f(sum,a),f(sum,b));
if(res==f(sum,a))return a;
return b;
}
int main()
{
int k,z;
scanf("%d",&z);
for(k=1;k<=z;k++)
{
int m;
scanf("%d",&m);
int i,j,a[110],sum=0;
int dp[110][110];
for(i=1;i<=m;i++)
{
scanf("%d",&a);
sum+=a;
}
for(i=0;i<=m;i++)for(j=0;j<=m;j++)dp[j]=0;
for(j=1;j<=m;j++)
{
int mm=a[1];
for(i=2;i<=j;i++)mm=fmin(mm,a,sum);
dp[1][j]=mm;
}
for(i=2;i<=m;i++)
{
for(j=1;j<=i;j++)
{
dp[j]=fmin(dp[i-1][j-1]+a,dp[i-1][j],sum);
}
}
int res=dp[m][1];
for(i=2;i<=m;i++)res=fmin(res,dp[m],sum);
printf("%d\n",f(sum,res));
}
// return main();
return 0;}

[brianfry713]

Input:

Code: Select all

1
10
500 499 500 488 467 500 499 488 499 487

AC output 1

[alimbubt]

Input:

Code: Select all

5
5
1 2 3 4 5
6
12 45 34 67 99 121
7
1 90 110 145 222 290 500
4
2 8 10 17
5
2 5 11 13 19

Output:

Code: Select all

1
2
42
1
2

[shuvokr]

Thanks brianfry713...

Code: Select all

cut...

[brianfry713]

try m = 0

[vhua_no_name]

hi,
I am new to UVa. i am getting WA for 562-Dividing coins problem. it will be very helpful if someone help me.
thanks

Code: Select all

#include<iostream>
using namespace std;

int main()
{
    int n,i,j,cases,min;
	long long int s,w;
	int a[2005];
	int m[2005];
	cin>>cases;
    while(cases--)
    {
		cin>>n;
		s=0;
        for(i=0;i<n;i++){
			cin>>a[i];
			s+=a[i];
		}
		w=s/2;
		for(i=0;i<n;i++)
			m[i]=w;
		for(i=0;i<n;i++)
		{
			for(j=0;j<=i;j++)
			{
				if(a[i]<=m[j])
					m[j]=m[j]-a[i];
			}
		}
		
		min=m[0];
		for(i=1;i<n;i++){
			if(m[i]<min)
				min=m[i];
		}
		
		if(n==0)
			cout<<0<<endl;
		else
			cout<<((s-w)+min)-(w-min)<<endl;
        
    }
    return 0;
}

[brianfry713]

See http://acm.uva.es/board/viewtopic.php?t=6208

[jddantes]

Why is this not greedy? i.e.if A has fewer coins than B, then he should get the next biggest coin. What's the flaw in this logic? I'd like to know what you think. (I got around this by a test case: 2 2 2 2 2 | 5 5 is optimal but greedy would yield 5 2 2 2 | 5 2 2).

[brianfry713]

Input:

Code: Select all

100
7
311 338 459 166 362 187 366
94
382 470 462 379 316 436 381 358 307 74 373 476 174 401 356 424 103 331 462 355 164 424 448 474 261 406 491 122 445 357 144 326 178 457 56 493 244 437 202 50 362 427 378 387 327 233 162 429 415 124 136 430 47 83 403 159 340 393 280 284 101 275 110 278 232 17 122 475 305 324 377 166 250 254 52 76 338 214 357 104 189 492 33 87 74 287 245 413 31 376 49 132 150 10
75
381 26 31 208 331 206 84 496 455 337 400 382 26 465 238 129 153 81 13 239 154 299 335 419 329 210 467 312 211 328 73 92 353 455 299 183 160 234 31 466 70 282 347 447 246 85 427 398 165 439 488 171 89 322 441 417 383 259 81 93 86 153 36 290 107 186 473 118 419 355 83 340 488 429 286
54
365 212 482 382 2 321 404 90 494 344 359 376 454 439 320 391 443 356 180 401 393 152 18 312 358 452 3 345 380 141 429 97 352 410 478 354 230 233 295 75 428 153 450 381 91 122 271 385 477 450 285 221 454 154
85
163 105 387 360 337 27 288 433 230 50 262 435 131 494 230 206 273 382 7 153 325 128 275 209 456 76 346 177 29 499 60 44 104 298 403 440 176 42 224 406 91 485 340 74 330 421 279 102 303 285 106 479 265 232 187 220 307 384 396 188 383 308 231 338 457 485 277 133 26 352 390 469 188 229 42 369 150 172 470 304 456 427 282 220 158
95
292 464 204 39 3 86 346 85 423 303 69 51 287 447 254 176 415 441 256 308 309 257 479 130 60 286 408 193 358 65 13 149 380 216 187 235 153 385 319 427 39 388 329 325 334 434 352 100 374 107 407 34 364 237 15 275 22 422 468 231 338 480 379 69 47 418 303 51 154 122 329 192 361 157 368 46 90 219 145 315 177 403 200 40 491 214 315 364 487 282 95 324 113 325 392
60
94 47 61 247 168 389 438 380 397 305 425 486 375 69 152 52 323 351 443 313 416 109 28 402 242 122 225 354 447 468 364 40 366 276 139 33 164 76 264 60 233 188 397 459 108 400 10 430 102 305 94 17 413 122 270 155 95 494 360 393
57
76 285 179 351 423 64 367 350 179 278 82 367 175 41 474 426 402 256 28 206 201 396 119 174 166 125 269 11 484 161 324 411 297 355 262 219 270 480 69 448 257 2 314 283 42 140 209 296 395 236 1 447 131 471 121 296 95
51
307 431 401 482 341 50 188 454 268 309 433 188 257 190 42 422 472 435 413 32 230 159 267 231 106 250 53 226 397 148 466 55 78 218 37 270 267 76 224 387 385 156 426 493 197 467 414 21 402 179 52
12
337 171 213 442 420 266 19 168 265 336 223 194
90
111 463 24 186 38 410 422 194 188 414 242 6 180 262 407 358 314 390 194 484 454 488 255 71 358 422 187 194 496 380 99 106 195 122 144 232 384 65 277 423 479 19 428 158 280 187 15 445 76 60 280 381 47 386 452 405 308 138 450 303 370 400 261 64 21 404 295 256 468 424 30 298 442 458 455 73 496 321 370 423 233 149 303 279 35 106 35 194 96 484
84
465 383 460 380 256 363 26 363 183 449 393 480 242 202 287 167 197 459 36 119 191 36 273 322 422 231 356 467 326 192 167 142 426 126 373 181 341 398 396 23 199 140 354 292 341 492 458 389 451 345 359 493 381 131 314 154 361 22 473 38 213 139 179 138 264 51 171 104 301 66 478 351 57 184 142 397 175 100 137 477 444 495 470 176
91
135 182 190 156 154 227 368 292 258 358 407 160 380 363 312 297 192 162 353 375 304 101 402 403 237 230 198 83 51 226 59 186 407 100 341 412 179 61 55 436 270 461 447 149 175 259 445 219 420 297 445 223 249 346 477 485 428 27 67 478 252 477 163 158 77 356 421 255 268 475 42 37 287 488 37 462 98 481 180 18 129 476 92 229 322 421 213 249 447 131 226
6
107 241 207 35 96 127
23
363 453 34 251 239 22 287 200 119 119 231 488 99 207 432 327 380 352 39 480 298 169 57
97
127 297 405 14 244 383 154 458 335 188 208 73 61 494 125 31 112 207 371 210 413 302 388 144 153 426 475 302 446 32 500 425 180 404 438 424 138 443 381 472 482 89 396 394 434 20 425 46 227 147 107 491 448 495 135 452 272 461 105 70 492 104 494 172 359 283 447 496 77 179 467 59 119 214 452 53 234 228 450 312 374 408 302 173 402 288 124 26 249 228 95 92 183 440 115 41 222
74
36 150 240 354 208 358 68 12 262 153 91 211 464 317 119 117 489 372 257 465 397 5 192 343 448 375 282 63 267 355 123 303 5 214 8 64 424 427 427 185 79 370 248 394 186 218 11 26 89 267 490 338 123 34 32 70 260 314 132 26 20 107 180 376 172 188 440 95 114 218 132 45 87 231
98
124 448 448 2 36 66 491 225 188 376 257 110 135 422 93 13 441 51 192 317 223 231 108 169 345 177 300 241 116 30 178 91 477 126 92 365 43 435 441 83 310 197 192 297 470 136 309 263 187 352 431 409 83 390 429 279 66 229 19 33 110 196 124 439 173 215 155 216 1 95 150 311 144 341 107 465 476 267 227 14 118 157 274 52 46 203 330 464 283 200 496 244 248 119 182 272 186 188
29
186 135 488 348 130 328 306 94 156 72 321 21 42 329 295 93 375 349 275 338 131 326 333 374 73 304 408 345 341
50
183 26 81 171 226 210 350 31 304 5 103 476 378 496 304 172 88 30 372 214 367 2 40 52 227 464 207 486 308 47 433 343 424 13 13 149 75 362 180 230 219 134 205 96 481 360 119 68 390 490
9
108 343 25 11 421 488 217 259 296
38
191 138 39 55 2 39 129 215 70 358 433 55 414 380 35 126 350 455 367 191 88 326 385 112 337 306 99 405 64 246 372 106 235 410 12 236 300 493
58
370 202 87 424 116 467 459 93 168 413 459 359 352 284 243 463 120 400 413 377 315 11 248 272 245 9 284 333 308 276 135 29 329 221 453 444 39 263 36 207 27 346 417 378 130 11 192 101 411 456 477 77 466 76 349 63 436 484
37
96 111 381 124 439 101 428 235 140 42 122 198 68 468 466 297 97 476 488 49 238 296 378 167 261 453 15 323 389 350 69 484 460 449 459 250 50
95
336 41 428 458 90 348 277 55 144 225 382 484 273 472 279 150 138 39 103 4 214 343 353 282 178 164 83 136 413 484 374 249 376 302 58 465 149 334 371 144 58 104 127 330 75 405 332 212 444 286 215 9 128 419 142 157 82 224 292 347 207 166 95 82 319 4 398 319 337 120 462 246 224 89 75 150 493 258 214 288 43 428 148 22 199 290 178 280 13 470 126 72 487 72 153
27
75 403 475 263 22 288 8 97 228 435 247 221 192 312 360 235 239 8 256 289 149 286 69 161 107 46 84
72
118 89 101 44 491 427 307 364 214 166 313 442 100 411 14 144 222 225 230 312 84 337 101 232 122 169 245 228 66 328 172 35 416 272 79 258 50 237 122 116 402 434 57 354 344 422 349 417 498 78 228 82 414 328 165 36 348 409 115 414 89 139 448 4 262 26 262 312 114 235 427 368
13
335 221 363 108 69 279 105 498 6 38 411 186 203
73
33 463 265 446 51 403 394 407 164 271 20 475 385 254 253 252 273 87 324 487 194 244 117 151 241 122 188 3 159 242 301 192 205 65 489 107 467 382 365 482 5 384 457 241 137 209 344 261 148 167 247 341 262 363 343 2 337 31 4 495 124 156 38 328 72 27 287 390 260 3 372 116 387
19
356 375 240 199 488 387 217 234 80 330 97 422 331 285 304 187 131 428 194
46
107 266 47 245 155 306 248 378 422 134 57 129 360 297 180 347 35 248 433 114 78 381 388 260 165 191 298 295 118 492 315 225 109 361 469 115 167 68 493 440 53 401 68 413 197 247
73
84 495 43 197 424 275 84 183 439 127 481 86 96 472 400 320 80 261 141 194 279 60 38 218 113 439 137 377 487 236 487 70 230 382 119 5 156 54 187 447 180 167 32 276 490 283 447 421 43 439 467 321 499 4 390 111 294 27 339 281 262 325 350 343 58 320 347 66 374 385 12 53 404
76
180 245 177 127 166 72 417 484 244 415 487 134 377 281 12 215 413 125 392 114 319 301 434 17 366 307 401 229 211 156 123 391 401 152 369 66 75 285 49 318 52 387 303 428 19 166 495 431 142 386 397 460 186 330 476 404 136 229 132 346 236 107 88 136 110 456 53 184 241 453 353 292 192 156 71 210
26
65 493 315 302 389 274 340 218 102 243 205 182 226 402 417 332 342 53 441 297 457 124 389 410 329 32
94
484 103 310 8 19 154 322 173 394 448 12 463 49 106 167 82 331 421 498 15 262 402 455 410 359 431 299 268 111 182 220 94 284 381 453 155 35 275 179 428 222 42 391 122 147 409 203 329 181 52 195 294 306 2 204 164 284 354 283 394 35 354 339 171 234 291 177 120 65 355 400 138 248 290 111 394 50 313 74 83 217 269 376 22 122 431 37 405 136 171 298 23 24 136
27
257 426 221 377 343 427 276 480 174 417 91 419 318 255 344 400 323 464 128 196 85 58 232 489 46 402 138
75
425 273 112 34 51 184 410 393 462 37 224 135 453 166 405 122 421 100 22 95 64 149 291 500 58 22 341 103 276 478 170 200 103 133 233 153 316 494 45 277 30 120 263 334 286 19 308 206 119 329 300 34 329 442 33 386 464 225 341 239 203 362 290 305 495 375 457 310 368 353 439 250 472 53 435
0

99
242 314 42 422 466 75 250 407 459 488 222 36 328 460 238 189 102 394 35 476 202 345 195 54 135 444 377 187 231 486 110 472 151 151 246 116 77 495 375 388 334 96 423 13 408 12 54 9 405 88 336 106 284 30 11 418 326 239 457 56 76 66 379 227 69 124 194 145 471 68 384 304 16 306 169 275 169 222 135 73 309 470 30 93 499 392 362 324 131 318 231 206 236 462 284 304 85 478 300
80
397 184 63 412 341 231 186 10 452 320 434 112 141 464 204 140 207 66 315 189 235 46 395 470 7 30 273 443 7 73 202 404 108 264 167 448 494 353 309 297 24 95 408 165 58 464 156 116 381 470 305 115 367 51 85 225 80 209 20 87 133 221 342 240 336 8 40 329 212 200 477 88 294 236 252 203 199 259 319 79
46
475 46 299 25 130 23 456 190 394 394 323 114 235 414 301 95 305 481 306 5 457 393 150 45 496 205 243 106 23 174 186 349 219 484 373 200 358 180 389 104 74 211 69 160 477 370
22
281 350 60 137 307 304 139 351 152 343 445 109 217 118 294 65 188 129 289 387 339 468
39
442 41 338 10 201 166 379 306 447 229 365 435 387 21 425 89 24 267 385 132 483 355 278 47 42 406 187 281 96 155 408 37 47 245 47 99 411 277 405
43
357 121 495 95 141 420 183 16 38 68 148 21 274 277 419 315 34 106 95 130 260 2 166 306 99 64 405 361 193 161 421 49 281 267 144 274 38 178 289 76 97 288 96
22
64 14 37 98 119 483 79 230 485 244 388 435 160 144 147 352 304 67 252 84 185 395
65
223 425 498 298 21 285 393 243 201 258 279 150 229 261 228 310 97 323 197 383 482 192 29 333 495 447 437 431 132 183 139 354 107 136 151 480 273 395 74 325 152 352 474 232 464 201 42 413 23 238 295 357 430 176 41 276 122 477 58 253 160 49 458 118 184
67
97 308 354 170 132 358 373 457 89 189 157 130 101 32 368 247 240 149 422 280 276 396 109 186 148 268 234 458 385 269 417 334 77 271 355 60 128 228 17 68 416 25 198 368 408 417 114 147 417 388 279 44 283 387 229 282 6 462 239 242 231 8 75 307 130 430 218
31
157 234 176 424 259 373 143 166 141 256 165 57 495 443 101 277 329 329 411 186 143 1 427 373 8 2 31 137 283 248 245
22
334 273 214 92 145 356 109 138 463 125 46 310 67 146 438 247 327 348 432 469 349 359
14
208 212 223 345 494 322 441 284 155 213 349 98 210 56
15
347 370 183 392 179 250 390 117 496 68 316 280 36 164 490
76
224 201 302 68 194 123 360 477 278 73 177 227 134 232 285 332 101 468 75 280 217 464 248 64 383 63 195 418 79 184 497 302 384 150 221 77 273 80 405 402 4 433 128 137 164 265 320 265 232 395 396 300 210 495 363 93 409 410 362 487 93 211 140 477 360 212 405 484 292 162 385 147 94 365 136 258
47
455 374 212 349 121 11 411 115 225 3 23 134 364 362 227 74 1 55 434 213 311 269 356 472 154 2 418 370 489 27 350 444 400 61 144 20 71 54 486 147 56 8 281 272 369 7 197
53
413 482 286 223 251 141 195 256 494 464 125 483 490 326 278 241 238 421 112 160 475 97 306 382 456 86 5 325 444 202 398 356 183 183 431 433 175 477 40 168 440 16 2 429 341 279 21 78 200 132 237 26 228
10
259 183 480 116 359 276 317 256 483 351
19
413 136 464 389 175 484 328 191 485 108 383 116 128 313 167 111 401 44 338
42
302 373 127 417 83 402 85 191 384 436 480 149 71 296 37 97 279 217 287 115 176 22 230 156 334 396 266 86 291 456 381 93 180 7 361 262 260 446 304 495 233 284
27
155 431 180 251 209 248 390 175 423 411 257 78 96 4 196 181 295 151 413 387 330 271 99 443 30 396 247
98
128 382 19 134 312 50 385 372 297 126 398 72 388 154 1 483 158 196 15 452 198 428 190 379 50 288 174 432 36 420 308 163 153 326 297 316 376 33 187 24 158 84 95 45 90 448 379 247 143 393 198 193 172 239 71 74 378 244 5 413 15 312 428 19 137 76 334 364 108 372 240 117 456 186 161 45 133 391 143 128 135 192 320 159 430 242 232 307 338 236 220 204 399 147 223 35 222 56
21
181 428 490 297 235 27 309 131 160 199 273 287 185 464 458 343 393 51 74 51 388
86
270 444 59 268 166 446 341 221 196 21 500 37 169 86 63 477 216 74 27 340 212 212 303 169 54 47 72 480 450 459 140 219 402 199 339 419 144 179 492 191 200 491 227 368 77 141 197 144 67 223 484 278 286 138 447 192 37 370 171 486 328 162 204 82 360 394 352 355 73 343 45 272 186 123 491 114 116 187 257 182 262 92 459 399 230 257
23
266 126 112 251 306 274 306 239 485 200 90 340 272 285 236 395 470 359 385 435 474 424 191
56
185 283 465 83 364 74 25 129 199 136 231 356 261 388 446 246 439 36 437 62 172 172 456 493 382 193 427 207 468 469 213 4 103 178 438 466 103 462 446 153 450 28 9 210 416 454 307 206 341 95 268 12 267 75 356 500
3
282 207 86
100
419 89 353 448 27 171 50 340 116 203 289 144 63 351 411 368 9 468 209 104 235 72 222 162 428 221 280 61 427 218 163 346 306 368 145 184 38 195 376 5 249 164 148 311 366 410 178 375 378 238 330 464 310 51 125 89 123 257 1 50 474 164 247 131 31 391 167 68 437 42 72 185 57 72 347 423 333 377 149 62 114 330 26 275 232 2 215 354 110 216 255 83 379 1 66 261 244 232 180 180
52
251 217 181 174 63 455 7 291 455 68 405 284 445 31 367 299 98 221 408 313 475 343 43 328 408 155 71 491 334 102 115 436 318 147 110 233 454 468 23 260 387 279 44 332 162 410 482 259 482 389 423 309
34
317 136 490 471 206 332 304 307 298 239 477 297 200 209 250 167 83 9 54 214 404 237 375 166 218 485 499 458 407 307 41 223 442 382
27
499 214 200 158 363 290 134 159 490 194 260 156 128 269 61 341 24 297 67 189 366 51 40 324 309 346 216
74
288 97 427 138 162 126 295 25 416 280 183 257 325 443 412 453 63 473 145 438 269 212 127 487 114 166 310 423 363 25 305 2 473 232 140 135 209 286 159 476 66 193 232 242 487 496 46 401 468 191 339 88 254 317 74 367 334 235 289 196 259 446 198 84 177 337 218 237 122 228 65 39 272 296
39
111 291 178 11 110 220 349 198 473 17 123 192 350 358 480 398 468 425 95 51 453 283 120 42 256 347 106 147 119 401 279 229 44 456 91 153 176 292 202
88
308 325 191 158 34 171 407 1 447 1 404 252 135 23 293 390 222 250 36 192 2 166 272 45 122 362 50 149 153 251 148 313 427 339 322 460 361 228 313 307 228 216 410 214 90 54 103 311 303 491 354 305 156 125 349 277 487 250 277 491 353 425 155 279 263 476 91 123 203 255 281 282 322 43 495 411 96 450 74 399 440 427 203 447 404 403 76 242
30
352 232 357 276 239 487 38 214 77 12 269 183 145 50 4 187 397 267 282 346 340 32 137 118 86 83 21 489 158 114
42
10 198 201 137 436 187 27 149 116 38 417 298 34 319 154 220 215 420 354 412 111 385 400 228 471 482 101 311 492 214 155 353 411 207 489 346 245 15 347 360 405 115
43
438 433 15 10 499 434 363 262 44 247 161 123 69 495 75 379 338 141 385 190 403 91 30 101 336 45 447 47 301 61 408 238 346 422 247 196 207 461 458 102 60 470 225
68
316 151 359 153 143 243 194 46 334 224 146 21 120 444 67 420 356 327 9 53 248 256 249 455 68 58 408 127 379 132 255 195 135 113 199 277 207 245 174 392 468 319 412 87 114 331 358 470 9 366 22 108 473 122 414 41 31 322 167 410 305 273 456 439 237 6 68 444
8
241 187 69 60 451 7 25 133
81
494 141 230 368 248 202 341 162 94 372 483 261 281 287 385 88 78 122 445 145 417 195 385 455 263 296 405 270 173 37 485 166 29 214 385 277 268 226 290 361 449 124 473 81 262 210 168 339 183 112 335 99 158 72 405 273 219 310 394 391 198 378 409 227 92 293 355 211 370 144 71 318 119 396 398 380 105 417 71 287 381
37
237 38 476 141 310 195 302 203 437 500 433 345 226 24 490 80 86 359 75 8 29 193 403 278 424 359 195 494 145 75 399 233 464 226 226 126 272
25
180 209 26 112 53 103 487 42 34 72 253 108 80 281 152 334 58 76 193 104 69 189 178 319 422
30
45 147 119 316 25 298 24 51 262 429 5 248 470 39 172 222 498 103 354 2 436 412 77 128 15 497 317 45 168 90
11
64 88 8 379 112 157 255 14 418 183 19
78
4 409 189 78 406 143 431 407 78 342 335 58 209 184 226 253 203 315 142 266 254 149 496 365 305 250 231 75 284 101 92 140 9 132 217 266 274 147 25 203 341 211 260 49 246 485 153 448 151 294 213 404 442 209 269 98 310 351 172 446 451 115 437 311 98 153 428 371 151 452 426 343 15 185 243 260 170 395
46
320 40 272 76 333 480 196 431 142 46 454 87 348 69 375 158 166 27 85 389 29 389 314 372 403 350 466 162 371 361 221 43 252 493 118 85 324 313 367 465 358 172 403 205 92 277
28
110 155 150 498 184 38 163 407 292 12 372 454 235 84 26 277 336 18 394 420 342 58 138 158 267 309 61 323
1
189
99
10 344 185 359 379 75 21 285 366 384 156 171 470 92 197 246 427 66 491 198 259 48 335 417 314 143 329 488 395 17 23 404 212 60 262 90 134 134 374 351 370 382 22 339 325 218 437 251 135 427 448 394 327 134 310 492 276 138 480 23 6 2 426 218 413 40 307 398 173 33 249 394 266 122 233 90 191 169 192 325 447 139 218 273 272 379 265 399 368 244 421 374 97 199 91 362 238 249 259
45
133 359 156 250 480 240 339 170 260 382 495 58 20 64 331 143 443 447 394 310 190 166 183 138 216 125 499 453 226 258 67 358 116 74 460 448 165 150 117 276 32 463 333 403 27
42
398 469 461 291 130 2 308 313 140 24 289 138 328 14 247 394 224 215 319 183 162 483 184 130 258 215 93 443 118 119 457 15 439 418 157 68 419 316 380 410 191 21
74
19 386 146 264 109 212 435 143 373 417 179 355 27 393 447 321 362 65 277 228 3 46 236 70 317 52 302 226 242 174 125 112 59 123 228 20 334 162 14 59 430 192 413 308 85 359 128 298 275 257 26 129 302 261 50 118 164 203 344 406 376 468 369 435 442 448 306 276 109 319 334 391 11 98
76
447 308 178 244 82 434 269 62 235 30 111 353 193 314 48 450 189 367 171 475 309 118 280 84 79 99 269 469 461 218 166 407 25 343 2 458 276 271 19 363 152 129 67 196 294 114 498 335 332 168 309 140 137 441 75 215 39 195 183 351 412 201 257 288 395 110 245 23 380 115 385 383 244 303 79 389
36
76 223 99 95 32 239 83 472 165 298 362 360 332 212 123 384 320 263 131 429 7 153 161 122 389 43 217 43 473 105 310 400 328 408 494 211
68
429 34 311 78 395 22 261 458 496 145 129 258 127 409 117 131 69 90 19 464 158 413 436 114 222 336 441 129 181 3 275 109 36 437 186 430 310 447 239 157 443 367 415 69 276 383 199 344 472 69 307 129 481 95 242 202 430 35 330 110 389 456 71 425 244 256 206 53
47
445 210 496 163 476 416 438 358 114 134 181 34 292 161 14 386 254 67 167 140 249 129 29 204 199 453 300 306 10 204 360 306 413 207 469 240 123 258 449 88 391 129 474 35 289 339 272
97
406 291 34 154 419 62 209 117 366 8 422 376 212 133 181 476 340 149 68 314 259 16 253 149 497 226 35 285 65 159 179 322 449 213 327 367 126 35 335 492 395 256 367 106 241 399 433 432 400 500 97 158 368 349 158 364 427 193 500 343 203 31 164 151 95 490 369 220 24 203 211 270 310 429 227 50 180 160 481 79 11 77 236 230 278 393 93 204 437 445 46 139 475 61 141 69 50
19
140 425 63 203 195 373 131 421 274 162 432 107 240 295 35 475 24 164 220
58
367 8 413 264 499 387 324 139 307 225 500 446 150 414 500 344 138 131 116 264 144 48 370 384 342 256 210 217 420 281 185 138 289 97 254 287 335 429 277 141 154 128 439 303 394 438 498 31 420 465 294 64 364 15 299 57 271 8
35
42 289 458 179 429 55 432 215 389 361 343 382 366 323 320 20 216 109 369 246 381 333 392 444 197 258 242 253 380 101 378 421 389 336 452
97
390 383 383 130 95 78 11 312 400 182 331 115 291 199 212 171 384 455 466 80 213 59 184 92 159 62 13 400 249 316 68 138 198 451 119 145 380 130 456 279 311 139 245 453 337 308 123 220 263 440 151 327 498 187 270 157 100 134 56 348 449 123 337 499 425 455 143 304 84 450 434 247 88 30 199 277 338 174 496 452 113 499 278 463 185 47 119 136 181 26 483 129 500 171 127 425 125
24
80 61 423 14 307 10 43 357 138 232 382 134 183 347 484 312 309 20 211 279 155 243 304 489
55
303 159 202 227 135 322 159 195 96 172 1 458 66 210 95 298 91 80 332 437 63 144 97 82 354 375 88 448 178 76 170 333 86 371 411 221 193 69 415 140 240 268 97 158 329 192 307 419 271 138 208 186 133 304 267

AC output:

Code: Select all

27
1
0
0
0
0
1
0
0
0
1
1
0
7
0
0
0
1
0
0
0
0
1
1
1
1
1
0
1
1
1
1
0
1
1
0
0
0
1
1
0
0
1
0
0
0
1
0
1
0
0
0
0
0
0
0
1
1
1
0
0
1
0
11
1
1
0
1
0
0
1
0
1
1
0
1
1
0
0
0
1
1
1
1
189
0
1
1
0
1
0
1
1
0
1
0
0
1
1
1

[prashantharshi]

dp is usefull only when knapsack capacity is not too large
here in worst case W=100*500
how dp can be usefull here

[brianfry713]

Yes you can solve this using DP

[Zyaad Jaunnoo]

Why is this not greedy? i.e.if A has fewer coins than B, then he should get the next biggest coin. What's the flaw in this logic? I'd like to know what you think. (I got around this by a test case: 2 2 2 2 2 | 5 5 is optimal but greedy would yield 5 2 2 2 | 5 2 2).

Try this example:
2 2 3 6

Optimal is A = 2 2 3 and B = 6
With the logic you used, you will get A = 2 3 and B = 2 6

Hope it helps!

[ashdboss]

thanks... accepted

[lighted]

Your code fails one case from Brianfry's post above.

Input

Code: Select all

1
97
127 297 405 14 244 383 154 458 335 188 208 73 61 494 125 31 112 207 371 210 413 302 388 144 153 426 475 302 446 32 500 425 180 404 438 424 138 443 381 472 482 89 396 394 434 20 425 46 227 147 107 491 448 495 135 452 272 461 105 70 492 104 494 172 359 283 447 496 77 179 467 59 119 214 452 53 234 228 450 312 374 408 302 173 402 288 124 26 249 228 95 92 183 440 115 41 222

Acc Output

Code: Select all

0

Don't forget to remove your code after getting accepted.