Statistics

Problem Statement for "GameShowTotal"

Problem Statement

Your friend just took part in a game show.

During the game show your friend was asked a sequence of N questions. The questions were numbered from 0 to N-1 in the order in which they were asked. Each question had an assigned dollar amount: for question i this amount was A[i].

The rules of the game are as follows: The contestant starts the game with an empty bank. Whenever the contestant answers a question correctly, the amount assigned to that question goes to the contestant's bank. But whenever the contestant answers incorrectly, they lose everything that is currently in their bank. At the end of the game the contestant wins the amount that is in the bank at that moment.


You are given the int N and the int[] A with N elements. You are also given the int W.

Your friend claims that in the game show he won exactly W dollars.


You don't know what questions your friend was asked. More importantly, you don't know how he answered and which of his answers were correct.

Return "possible" if your friend can be speaking the truth, or "impossible" if you can be sure that it's not the case.

Definition

Class:
GameShowTotal
Method:
verify
Parameters:
int, int[], int
Returns:
String
Method signature:
String verify(int N, int[] A, int W)
(be sure your method is public)

Notes

  • The return value is case-sensitive: the string must be all lowercase.

Constraints

  • N will be between 1 and 50, inclusive.
  • A will have exactly N elements.
  • Each element of A will be between 1 and 1000, inclusive.
  • W will be between 0 and 50,000, inclusive.

Examples

  1. 4

    {10, 20, 30, 40}

    100

    Returns: "possible"

    This is clearly possible in exactly one way: your friend must've gotten all four questions right!

  2. 4

    {10, 20, 30, 40}

    0

    Returns: "possible"

    This is also possible, in multiple ways. Among them, a very natural way is that your friend could've gotten all four questions wrong.

  3. 5

    {10, 20, 30, 1000, 40}

    1000

    Returns: "impossible"

    Note that the order of questions is fixed. In this particular game it's not possible to win exactly 1000 dollars. Why? Clearly, your friend must have gotten the 1000-dollar question right, but after that question there was one more: the 40-dollar question. If your friend got it right, he would have won at least 1040 dollars, and if he got the last question wrong, he would get nothing at all.

  4. 6

    {10, 20, 30, 40, 1000, 50}

    1050

    Returns: "possible"

    One valid gameplay: Your friend got question 0 right. In the bank: 10 dollars. Your friend got question 1 wrong. In the bank: 0 dollars. Your friend got question 2 right. In the bank: 30 dollars. Your friend got question 3 wrong. In the bank: 0 dollars. Your friend got question 4 right. In the bank: 1000 dollars. Your friend got question 5 right. In the bank: 1050 dollars.

  5. 1

    {10}

    0

    Returns: "possible"

  6. 1

    {10}

    6

    Returns: "impossible"

  7. 1

    {10}

    10

    Returns: "possible"

  8. 1

    {10}

    20

    Returns: "impossible"

  9. 23

    {65, 441, 567, 465, 585, 352, 264, 525, 396, 402, 631, 42, 815, 429, 675, 25, 981, 105, 1, 271, 966, 989, 812}

    0

    Returns: "possible"

  10. 35

    {10, 940, 836, 921, 324, 582, 438, 236, 244, 536, 527, 368, 453, 981, 248, 35, 575, 384, 734, 705, 362, 616, 351, 572, 589, 781, 201, 245, 808, 861, 747, 937, 958, 37, 129}

    14658

    Returns: "possible"

  11. 24

    {593, 393, 521, 554, 833, 259, 100, 665, 893, 903, 233, 950, 716, 866, 343, 224, 483, 763, 113, 792, 427, 620, 362, 692}

    0

    Returns: "possible"

  12. 16

    {829, 569, 945, 268, 366, 546, 579, 42, 496, 320, 577, 799, 405, 267, 968, 748}

    41117

    Returns: "impossible"

  13. 14

    {389, 498, 260, 986, 619, 948, 572, 153, 455, 16, 175, 561, 643, 824}

    17416

    Returns: "impossible"

  14. 33

    {833, 638, 560, 488, 802, 822, 447, 375, 941, 778, 34, 623, 272, 921, 660, 624, 530, 967, 691, 932, 484, 937, 726, 654, 818, 975, 323, 850, 23, 591, 249, 217, 355}

    13422

    Returns: "possible"

  15. 12

    {482, 944, 204, 131, 101, 140, 748, 804, 584, 353, 541, 402}

    3636

    Returns: "impossible"

  16. 1

    {669}

    68

    Returns: "impossible"

  17. 24

    {22, 271, 43, 144, 186, 757, 524, 856, 503, 206, 802, 792, 832, 507, 541, 465, 578, 581, 11, 712, 76, 180, 856, 155}

    1267

    Returns: "possible"

  18. 3

    {899, 637, 241}

    252

    Returns: "impossible"

  19. 2

    {91, 310}

    122

    Returns: "impossible"

  20. 40

    {918, 752, 548, 155, 564, 594, 781, 280, 634, 879, 585, 83, 577, 504, 351, 570, 54, 977, 118, 424, 428, 363, 929, 311, 578, 865, 778, 501, 613, 144, 66, 995, 521, 120, 925, 473, 669, 806, 465, 844}

    18478

    Returns: "impossible"

  21. 34

    {782, 990, 68, 801, 809, 295, 803, 722, 502, 515, 117, 774, 252, 361, 816, 340, 171, 474, 24, 602, 101, 688, 471, 963, 472, 284, 654, 558, 703, 712, 706, 941, 25, 987}

    1339

    Returns: "impossible"

  22. 50

    {270, 556, 495, 393, 71, 740, 805, 112, 901, 534, 727, 605, 614, 489, 551, 763, 810, 371, 593, 320, 422, 789, 700, 918, 920, 210, 750, 648, 94, 962, 106, 525, 829, 313, 415, 977, 341, 552, 857, 369, 872, 112, 836, 956, 96, 876, 638, 762, 437, 370}

    19098

    Returns: "impossible"

  23. 4

    {948, 402, 650, 827}

    1477

    Returns: "possible"

  24. 14

    {297, 215, 477, 872, 678, 841, 838, 980, 307, 456, 958, 795, 452, 326}

    38029

    Returns: "impossible"

  25. 31

    {1, 29, 433, 887, 469, 533, 449, 629, 835, 881, 264, 302, 105, 311, 127, 956, 174, 434, 345, 510, 437, 979, 241, 516, 584, 526, 270, 321, 569, 24, 941}

    965

    Returns: "possible"

  26. 40

    {572, 184, 699, 719, 387, 835, 44, 186, 628, 952, 186, 639, 80, 497, 421, 62, 230, 473, 181, 953, 613, 408, 5, 640, 143, 762, 75, 574, 399, 1, 394, 512, 760, 467, 645, 383, 749, 126, 524, 411}

    27544

    Returns: "impossible"

  27. 27

    {964, 912, 564, 107, 873, 633, 180, 926, 682, 511, 488, 450, 611, 849, 96, 405, 538, 518, 336, 443, 767, 936, 202, 324, 407, 869, 77}

    5456

    Returns: "impossible"

  28. 42

    {665, 108, 259, 498, 810, 998, 95, 366, 994, 31, 405, 640, 84, 616, 230, 529, 660, 216, 520, 264, 731, 879, 783, 993, 314, 513, 621, 117, 936, 576, 64, 294, 737, 182, 500, 713, 248, 415, 626, 486, 8, 604}

    1724

    Returns: "possible"

  29. 16

    {641, 984, 568, 384, 821, 807, 110, 346, 66, 161, 605, 109, 245, 865, 887, 188}

    33749

    Returns: "impossible"

  30. 11

    {737, 170, 80, 95, 129, 604, 404, 883, 357, 125, 985}

    3487

    Returns: "possible"

  31. 36

    {656, 225, 696, 940, 356, 788, 93, 657, 322, 105, 37, 207, 831, 573, 139, 987, 339, 959, 996, 94, 854, 327, 788, 733, 680, 962, 968, 939, 440, 519, 560, 587, 771, 789, 697, 923}

    2409

    Returns: "possible"

  32. 34

    {436, 654, 450, 447, 693, 424, 746, 503, 24, 200, 992, 335, 51, 615, 961, 439, 923, 104, 450, 792, 597, 128, 99, 867, 343, 448, 757, 934, 61, 342, 999, 807, 773, 192}

    2771

    Returns: "possible"

  33. 48

    {937, 949, 531, 487, 710, 529, 123, 955, 945, 235, 204, 643, 28, 553, 506, 334, 943, 146, 692, 168, 793, 297, 75, 49, 765, 858, 927, 620, 306, 46, 658, 633, 874, 686, 7, 263, 353, 925, 197, 569, 221, 379, 924, 380, 137, 208, 988, 459}

    19747

    Returns: "impossible"

  34. 43

    {307, 432, 114, 433, 864, 429, 356, 775, 510, 987, 263, 47, 742, 579, 740, 706, 934, 503, 236, 278, 416, 60, 894, 25, 403, 196, 785, 428, 376, 533, 91, 354, 740, 992, 889, 640, 908, 643, 348, 452, 887, 857, 70}

    8742

    Returns: "impossible"

  35. 5

    {167, 210, 233, 952, 433}

    1828

    Returns: "possible"

  36. 19

    {7, 117, 620, 578, 835, 13, 258, 547, 219, 546, 382, 483, 939, 987, 220, 341, 411, 934, 40}

    4737

    Returns: "possible"

  37. 35

    {353, 917, 8, 112, 22, 319, 811, 50, 624, 224, 843, 841, 865, 537, 886, 627, 4, 36, 893, 568, 603, 51, 393, 915, 782, 476, 196, 92, 990, 284, 964, 692, 953, 652, 909}

    2514

    Returns: "possible"

  38. 23

    {39, 908, 67, 312, 616, 732, 319, 54, 625, 939, 453, 475, 417, 747, 738, 341, 737, 93, 260, 874, 914, 971, 431}

    11048

    Returns: "possible"

  39. 46

    {387, 181, 303, 31, 32, 589, 999, 693, 591, 832, 908, 1000, 196, 130, 575, 229, 89, 8, 434, 438, 427, 725, 434, 593, 752, 131, 158, 792, 739, 758, 974, 760, 873, 385, 552, 657, 929, 472, 269, 656, 845, 657, 152, 77, 41, 605}

    4620

    Returns: "impossible"

  40. 40

    {141, 126, 531, 799, 131, 627, 875, 954, 968, 300, 584, 618, 902, 429, 561, 764, 987, 500, 628, 875, 595, 892, 25, 172, 801, 825, 613, 555, 593, 844, 649, 742, 150, 953, 237, 869, 121, 156, 918, 930}

    930

    Returns: "possible"

  41. 47

    {920, 827, 667, 502, 472, 844, 875, 620, 317, 420, 772, 949, 981, 461, 621, 188, 14, 439, 828, 807, 957, 894, 500, 502, 750, 418, 352, 384, 570, 310, 819, 919, 315, 404, 853, 848, 386, 37, 639, 782, 539, 276, 146, 479, 402, 104, 856}

    24102

    Returns: "impossible"

  42. 50

    {841, 913, 349, 680, 694, 586, 770, 152, 2, 267, 360, 164, 636, 880, 41, 817, 825, 423, 493, 735, 332, 152, 273, 966, 263, 339, 419, 673, 115, 211, 925, 993, 982, 686, 958, 181, 637, 901, 237, 944, 289, 681, 252, 472, 713, 785, 541, 350, 947, 160}

    22172

    Returns: "possible"

  43. 42

    {944, 182, 579, 948, 233, 553, 866, 586, 803, 541, 852, 795, 329, 655, 811, 655, 555, 211, 810, 653, 256, 972, 42, 375, 961, 390, 919, 773, 177, 502, 624, 956, 751, 923, 744, 175, 948, 895, 198, 413, 824, 746}

    10708

    Returns: "impossible"

  44. 48

    {935, 553, 77, 266, 98, 142, 871, 686, 842, 528, 766, 594, 685, 968, 214, 281, 612, 399, 891, 114, 262, 567, 367, 123, 385, 382, 665, 546, 231, 298, 257, 991, 624, 694, 716, 667, 329, 584, 40, 778, 993, 634, 213, 304, 457, 792, 946, 894}

    0

    Returns: "possible"

  45. 41

    {150, 607, 188, 904, 896, 932, 267, 352, 281, 97, 302, 213, 39, 784, 911, 278, 628, 667, 223, 204, 700, 505, 508, 80, 391, 665, 24, 671, 786, 968, 608, 154, 109, 909, 430, 309, 947, 226, 874, 424, 770}

    14038

    Returns: "impossible"

  46. 50

    {650, 897, 681, 229, 562, 92, 569, 430, 317, 323, 383, 934, 122, 94, 709, 322, 466, 217, 788, 121, 669, 89, 549, 681, 349, 779, 581, 706, 496, 815, 225, 61, 327, 316, 811, 749, 755, 684, 810, 389, 272, 785, 607, 61, 78, 263, 469, 517, 226, 526}

    15554

    Returns: "possible"

  47. 45

    {447, 529, 255, 625, 697, 873, 720, 658, 901, 337, 585, 650, 215, 892, 586, 846, 182, 194, 246, 772, 43, 31, 712, 623, 872, 522, 881, 921, 833, 621, 267, 754, 624, 302, 919, 204, 352, 607, 886, 620, 646, 904, 573, 345, 517}

    12212

    Returns: "impossible"

  48. 42

    {161, 677, 745, 506, 78, 37, 401, 476, 953, 712, 461, 302, 637, 97, 810, 655, 713, 505, 830, 643, 880, 992, 277, 342, 290, 712, 223, 840, 846, 928, 717, 871, 830, 438, 78, 262, 627, 392, 332, 471, 299, 165}

    23767

    Returns: "impossible"

  49. 43

    {946, 317, 38, 222, 707, 589, 486, 26, 365, 10, 646, 292, 281, 567, 426, 776, 543, 945, 242, 466, 466, 55, 841, 935, 85, 739, 134, 752, 413, 454, 192, 254, 48, 412, 689, 464, 545, 537, 103, 572, 28, 558, 460}

    2258

    Returns: "possible"

  50. 42

    {163, 807, 776, 973, 245, 283, 688, 327, 199, 571, 988, 692, 873, 505, 521, 821, 761, 282, 471, 262, 346, 538, 120, 983, 227, 780, 998, 261, 804, 972, 232, 34, 801, 142, 251, 706, 755, 902, 948, 730, 958, 459}

    23866

    Returns: "impossible"

  51. 48

    {756, 662, 672, 987, 975, 222, 332, 981, 642, 97, 812, 267, 531, 161, 285, 370, 143, 767, 169, 81, 893, 189, 833, 58, 874, 792, 522, 184, 619, 938, 939, 663, 830, 569, 627, 629, 106, 293, 43, 822, 329, 190, 89, 461, 283, 102, 306, 201}

    2783

    Returns: "possible"

  52. 42

    {791, 978, 886, 140, 250, 729, 552, 870, 247, 624, 320, 264, 690, 758, 920, 990, 466, 830, 27, 317, 938, 194, 764, 936, 27, 442, 179, 276, 901, 716, 499, 194, 460, 14, 379, 652, 254, 412, 520, 184, 806, 983}

    39519

    Returns: "impossible"

  53. 40

    {221, 323, 625, 413, 672, 308, 751, 275, 641, 96, 311, 236, 45, 575, 483, 952, 922, 835, 314, 242, 303, 854, 468, 184, 182, 568, 311, 811, 472, 297, 299, 627, 760, 54, 856, 315, 931, 39, 676, 887}

    18590

    Returns: "possible"

  54. 48

    {436, 150, 388, 394, 674, 556, 230, 543, 574, 424, 709, 456, 553, 834, 908, 187, 259, 411, 329, 937, 344, 921, 128, 388, 446, 144, 92, 753, 445, 256, 242, 4, 264, 556, 838, 26, 821, 346, 407, 881, 545, 311, 731, 203, 260, 70, 695, 52}

    40002

    Returns: "impossible"

  55. 45

    {355, 86, 701, 512, 268, 288, 788, 612, 377, 210, 833, 50, 845, 267, 499, 239, 681, 112, 541, 859, 313, 190, 407, 288, 759, 606, 936, 730, 207, 541, 287, 779, 165, 166, 328, 157, 285, 494, 102, 293, 711, 268, 155, 401, 691}

    49352

    Returns: "impossible"

  56. 42

    {89, 942, 298, 530, 150, 997, 836, 477, 797, 303, 33, 968, 110, 909, 697, 569, 986, 227, 213, 109, 202, 512, 393, 310, 734, 262, 13, 878, 344, 370, 431, 100, 91, 986, 338, 950, 267, 547, 855, 238, 595, 965}

    44134

    Returns: "impossible"

  57. 47

    {565, 715, 648, 206, 791, 35, 759, 172, 25, 584, 891, 892, 322, 234, 703, 376, 865, 235, 251, 501, 380, 207, 845, 885, 435, 191, 475, 610, 630, 1000, 228, 37, 789, 417, 478, 955, 238, 434, 936, 785, 19, 433, 634, 525, 983, 68, 503}

    6144

    Returns: "impossible"

  58. 40

    {246, 505, 533, 13, 857, 564, 960, 303, 491, 322, 314, 626, 717, 681, 532, 727, 710, 764, 642, 517, 385, 640, 228, 691, 56, 223, 224, 781, 504, 603, 452, 511, 867, 410, 557, 412, 144, 429, 366, 14}

    1922

    Returns: "possible"

  59. 41

    {784, 625, 371, 858, 523, 889, 396, 269, 157, 995, 908, 55, 221, 55, 577, 269, 705, 265, 181, 384, 907, 629, 383, 237, 585, 593, 979, 568, 832, 887, 949, 137, 242, 109, 909, 138, 369, 881, 53, 149, 751}

    8866

    Returns: "impossible"

  60. 48

    {65, 639, 750, 546, 998, 158, 963, 921, 247, 1000, 330, 466, 877, 531, 756, 727, 269, 97, 360, 782, 263, 10, 647, 567, 286, 547, 275, 477, 538, 629, 479, 901, 155, 373, 139, 688, 879, 213, 21, 101, 56, 394, 506, 211, 673, 691, 542, 689}

    1902

    Returns: "impossible"

  61. 48

    {762, 187, 900, 564, 245, 494, 998, 794, 491, 438, 59, 720, 510, 711, 720, 893, 706, 794, 891, 240, 525, 590, 333, 523, 226, 398, 760, 468, 139, 656, 174, 176, 900, 203, 824, 341, 2, 607, 536, 754, 205, 562, 870, 459, 168, 299, 535, 658}

    3551

    Returns: "possible"

  62. 47

    {568, 447, 884, 704, 22, 171, 597, 439, 409, 976, 988, 34, 571, 51, 63, 621, 707, 105, 213, 494, 193, 818, 565, 915, 33, 809, 547, 919, 789, 124, 17, 340, 265, 492, 285, 101, 933, 776, 757, 676, 120, 368, 495, 10, 286, 586, 472}

    15550

    Returns: "possible"

  63. 41

    {979, 959, 265, 378, 478, 56, 504, 709, 34, 437, 657, 84, 706, 918, 779, 716, 216, 380, 201, 236, 742, 600, 147, 211, 508, 527, 763, 110, 298, 789, 621, 654, 757, 702, 554, 778, 882, 102, 813, 862, 502}

    9844

    Returns: "impossible"

  64. 48

    {775, 265, 152, 288, 382, 151, 870, 341, 936, 883, 815, 681, 855, 934, 545, 380, 921, 131, 927, 147, 980, 439, 417, 585, 829, 326, 695, 185, 620, 837, 796, 385, 20, 935, 108, 435, 764, 171, 699, 942, 879, 67, 104, 133, 106, 812, 79, 823}

    11856

    Returns: "impossible"

  65. 46

    {99, 66, 834, 572, 494, 767, 905, 18, 126, 177, 342, 686, 752, 135, 719, 135, 286, 230, 143, 53, 398, 163, 430, 827, 568, 30, 75, 938, 250, 693, 713, 516, 437, 521, 643, 614, 65, 797, 955, 363, 249, 366, 273, 938, 975, 193}

    1459

    Returns: "impossible"

  66. 42

    {931, 61, 537, 319, 316, 448, 735, 947, 349, 902, 941, 49, 377, 762, 804, 665, 616, 258, 653, 970, 188, 533, 801, 812, 643, 168, 196, 635, 25, 546, 770, 810, 477, 236, 808, 266, 428, 492, 6, 773, 672, 54}

    1499

    Returns: "possible"

  67. 46

    {96, 78, 637, 351, 214, 266, 351, 710, 124, 638, 156, 610, 462, 915, 962, 388, 596, 345, 208, 264, 946, 281, 689, 469, 256, 494, 182, 589, 420, 398, 204, 37, 332, 977, 999, 46, 873, 241, 70, 120, 281, 246, 980, 494, 452, 774}

    45948

    Returns: "impossible"

  68. 40

    {601, 342, 291, 986, 584, 42, 986, 272, 384, 833, 382, 374, 162, 932, 968, 91, 767, 264, 92, 996, 495, 550, 519, 479, 684, 349, 620, 397, 167, 944, 303, 124, 457, 434, 599, 693, 272, 256, 739, 247}

    2181

    Returns: "impossible"

  69. 1

    {1 }

    0

    Returns: "possible"

  70. 4

    {10, 20, 30, 40 }

    100

    Returns: "possible"

  71. 4

    {10, 20, 30, 40 }

    50

    Returns: "impossible"

  72. 50

    {100, 99, 98, 97, 96, 95, 94, 93, 92, 91, 90, 89, 88, 87, 86, 85, 84, 83, 82, 81, 80, 79, 78, 77, 76, 75, 74, 73, 72, 71, 70, 69, 68, 67, 66, 65, 64, 63, 62, 61, 60, 59, 58, 57, 56, 55, 54, 53, 52, 51 }

    1

    Returns: "impossible"

  73. 1

    {2 }

    50000

    Returns: "impossible"

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: