TOPIC
PROBLEM 1798 - URI Fórum 1.0
This topic was solved and cannot recieve new replies.
-
Raphael Griffo Duarte replied 5 years ago
Estou com 80% de WA usando esta função aqui:
int CUT_ROD(int *p, int n){ int r[n+1]; r[0] = 0; for(int i = 1; i <= n; i++){ r[i] = 0; int q = -1; for(int j = 1; j <= i; j++){ if(p[j] > 0 && r[i-j] >= 0){ q = max(q, p[j]+r[i-j]); } } r[i] = q; } return r[n]; }Alguma dica?
-
Jairo S. replied 5 years ago
Para quem está recebendo WA(10%) ou WA(20%), segue alguns inputs interessantes:
Input 1:
586 4309 4604 425 2290 486 1184 545 3751 97 2052 435 138 476 4425 454 3232 81 3497 321 3094 387 334 405 3527 1 3853 148 2471 109 4063 312 4816 160 2709 74 1221 129 577 119 4990 104 4194 568 4434 108 3000 81 2147 415 2778 68 2020 502 81 303 389 277 2065 516 3994 311 1510 429 563 93 1114 336 2323 140 4163 146 1243 528 4594 95 875 11 680 83 2709 488 2793 308 4546 505 3633 211 869 232 4201 401 3659 146 3904 242 2037 558 209 185 1085 566 3270 136 479 361 3804 355 1985 143 1595 222 2092 217 3669 117 2778 286 1031 342 73 449 2908 93 3618 560 2141 287 3993 85 4215 211 3083 145 4305 29 305 416 3875 481 2782 502 1473 361 4793 300 4835 503 1805 415 3045 533 3107 189 3629 580 1243 363 3432 6 498 262 162 560 641 106 3923 317 3983 128 1949 476 1793 404 1063 69 2856 370 3881 225 1891 380 696 169 1015 81 51 296 4550 453 1804 22 331 487 2167 54 4220 150 2685 157 394 133 811 197 2483 318 4346 165 2292 492 2684 350 3124 107 4644 156 4235 233 2876 324 164 1 4443 14 851 266 1219 76 1639 296 2473 582 4411 537 1044 129 3290 345 3725 277 3638 301 2866 416 4630 512 2290 102 1010 302 2203 548 3962 95 2132 487 177 471 4305 242 4496 132 2850 141 4191 175 2954 148 2809 276 4667 240 4901 89 4836 565 2235 494 1747 524 2486 552 2198 96 2220 281 4070 456 2950 246 520 273 3393 257 4017 483 4394 228 1651 331 2919 229 532 232 1883 274 1469 196 3025 237 3351 422 4630 242 887 480 968 297 2636 223 3028 169 1250 249 615 477 727 574 3533 513 2321 221 161 413 1699 481 1452 558 3744 96 2973 197 1865 271 1580 327 2851 369 4536 583 4264 555 4175 8 39 420 4024 10 4693 8 1337 85 3755 398 4575 558 3019 498 1237 67 3531 499 81 165 3101 111 4485 252 1455 584 2294 496 1700 421 2854 78 1712 364 2466 519 3617 381 3310 554 3517 88 4690 350 2731 357 1677 168 4463 487 2195 289 3341 443 803 271 1095 284 157 506 2425 131 474 574 179 151 2283 218 4166 176 3939 361 801 539 844 533 2119 35 2415 32 3563 523 847 46 2779 319 731 304 2758 254 3537 89 4350 461 4873 299 3795 272 3553 37 3341 564 3412 127 2981 261 2178 528 96 50 3849 359 3534 70 4566 61 2208 376 1500 384 4656 143 2473 158 2145 400 2279 458 1623 174 318 403 4096 142 587 390 1264 575 3939 200 3441 325 3286 216 3114 564 345 446 4560 586 1382 243 1054 462 4212 131 3640 584 4928 515 1159 96 2373 305 1114 40 1179 499 1582 45 85 535 3466 70 2215 393 4980 50 3764 221 1528 328 1433 457 4749 560 4292 157 4165 215 4552 509 4554 478 3140 16 892 420 2894 437 3929 440 1688 223 2629 174 1403 183 3291 85 2182 173 3300 255 206 24 3039 163 315 474 3840 386 2632 64 4156 29 1872 116 4032 279 4826 159 779 114 4246 501 820 214 2557 280 4537 459 4909 367 2584 55 2475 443 4985 218 697 149 2960 346 419 261 1022 243 3100 340 366 400 3085 371 4376 531 2603 418 3824 224 4179 494 3656 258 1277 405 3682 566 360 92 3523 397 408 11 133 420 1825 13 4315 165 4041 439 4828 431 2177 169 1548 535 683 33 3578 483 2904 586 3225 268 3588 271 517 531 3901 533 3467 137 1621 524 5000 117 2801 338 2691 280 206 318 3886 556 4420 459 801 429 1534 131 4140 242 1809 254 1490 450 1146 471 647 14 4175 171 4254 487 2016 40 4729 454 3223 330 1104 79 3639 271 2530 484 1676 586 793 276 1532 405 4465 4 233 353 4297 498 38 109 222 458 539 433 3760 267 3093 224 3493 165 969 44 4886 253 4519 24 1172 466 55 81 870 2 3718 304 1955 90 2113 250 2773 19 662 569 73 349 4553 122 99 339 4272 569 4030 96 4071 213 1693 342 3944 220 4634 396 3302 505 3661 62 926 245 3868 406 4851 244 3417 394 3589 180 4337 348 2159 576 2662 360 1837 206 4153 334 3610 288 678 355 939 426 3321 463 422 356 481 10 1226 155 4192 150 2073 438 1060 2 968 394 4555 36 4422 118 4746 225 4934 255 2591 310 3757 62 3566 376 3380 515 2121 448 4777 544 1682 5 4634 324 4569 468 4116 136 4642 181 168 334 1640 503 4963 222 1704 406 854 504 1449 162 3128 387 2489 344 592 70 2512 557 2350 369 2840 525 1830 348 4450 221 1265 62 675 94 1764 51 3513 541 2517 310 1285 36 1527 334 4338 579 3638 290 488 429 3053 289 1261 483 2072 424 872 326 1513 496 1375 176 173 474 2983 449 943 9 2210 316 1237 288 4091 296 4229 584 1594 469 1065 111 3367 207 3294 249 2257 37 3877 126 2370 46 858 561 4657 448 4612 365 3302 496 1606 530 529 8 243 457 4954 581 2353 438 496 536 2109 178 1734 350 2096 1 2932 154 27 308 1993 156 1955 322 3027 63 3366 46 866 449 3478 120 653 559 2451 328 2212 102 3897 92 2526 537 1966 529 3416 245 2416 456 4245 475 2593 462 1745 245 4283 127 3022 332 959 532 782 350 101 291 4330 296 4296 292 3532 164 684 255 3658 285 4558 571 3725 478 3231 403 1543 160 2855 288 2506 180 1058 261 4968 173 3367 130 1633 554 2421 398 4297 360 765 415 2233 210 3493 228 2580 118 4796 445 2231 562 1275 437 4872 226 2344 438 4474 214 2947 471 3068 233 742 15 1655 221 633 95 3054 576 2778 428 2349 579 3701 456 997 549 3144 70 516 287 4558 477 97 387 2931 467 1165 234 3832 184 3768 373 3658 44 381 548 1482 466 155 247 4957 202 4037 443 4671 199 3495 577 4553 337 1032 177 614 145 4661 543 4288 446 3445 98 2089 66 4396 176 411 65 2171 461 4118 470 3393 110 3719 428 1500 71 3117 437 4929 322 4567 348 3725 320 528 539 2485 273 1957 64 3914 147 2622 125 3198 203 4473 342 3567 440 516 336Input 2:
278 581 681 163 3811 121 3833 25 581 218 1873 59 1528 196 2908 194 191 123 433 107 1625 70 1636 140 1291 68 4083 109 4276 265 4665 63 1650 119 2873 269 4115 91 2025 82 2503 34 2724 133 2276 75 722 189 580 252 4681 135 4697 231 2902 267 3877 207 366 196 3579 59 3342 264 1361 27 3264 55 2835 246 3636 21 2749 133 2567 269 1685 3 3859 188 4279 213 2457 59 2666 4 570 176 4707 78 1306 109 3498 42 4014 61 3873 192 2206 109 2867 278 3454 70 3499 173 2493 248 3803 68 3173 11 1680 51 812 38 3060 201 4337 235 2645 60 1047 211 2618 32 3954 66 3825 198 3102 79 4360 13 4363 224 435 30 3083 88 3817 108 3016 2 432 3 4620 192 337 121 1002 268 1475 36 1443 129 2321 92 3219 171 3547 93 629 271 941 262 2811 93 3572 126 4913 248 1168 220 3333 92 2345 241 2890 119 660 70 39 192 1300 132 2347 270 236 137 3490 38 2305 178 720 130 4602 211 381 248 1769 207 3383 160 4754 25 2391 143 264 63 1898 13 46 228 2452 274 4491 247 1209 67 3236 19 1489 128 573 60 3580 46 3395 71 2065 60 3433 48 4464 254 3936 132 3468 185 3138 141 3493 16 222 253 470 277 2771 107 3017 182 2209 110 4883 70 4258 238 4765 102 1728 80 1902 189 1939 199 4846 173 3769 265 155 72 3724 11 3600 104 3236 4 4375 179 3421 86 2641 131 1846 235 2885 226 283 256 594 57 2060 15 2794 233 2421 109 4389 8 4058 186 1779 148 4525 188 1369 83 4483 273 2208 59 2463 29 4719 65 510 176 736 250 415 138 1441 250 1441 229 1704 20 3424 71 3933 218 2918 198 1616 103 2531 34 1219 198 1466 219 1119 249 3681 73 1132 106 168 197 3003 174 4411 45 208 15 2517 35 3298 91 4572 53 1650 207 1086 29 3907 75 2090 265 2621 161 2520 15 4689 4 3399 244 273 18 779 103 4308 228 2512 203 2984 83 873 251 1058 267 573 150 4707 278 1702 216 3615 52 3041 248 2979 261 3257 29 3198 128 4077 80 3361 33 1153 63 1610 77 76 64 1008 112 318 90 948 204 3319 165 627 177 2863 126 1108 265 3876 117 1702 197 3112 141 4388 25 1752 81 429 99 3240 258 2686 256 2214 29 830 28 2369 247 4290 84 2593 225 174 244 2620 39 4684 248 2486 49 556 27 746 206 2827 277 3304 263 4051 199 4604 274 2609 161 4086 165 735 223 2191 15 4396 176 2662 86 3743 211 1373 234 1305 43 875 12 4244 143 2540 173 1330 74 3070 41 754 35 632 187 292 44 1545 39 4170 114 1934 183 287 208 1154 98 224 254 3814 170 4525 116 3637 249 2158 149 3618 257 4890 188 3106 40 1030 272 2222 53 3261 19 4245 210 4162 253 3417 252 4077 43 3256 40 1231 202 3443 60Saída 1:
49084Saída 2:
2868
