Description
A Trip to the Supermarket, v2017 (Subtask A)
Sometimes Ketfah will need to go buy some grocery from the supermarket near his house. However since the
supermarket is big and sometimes the things that need to be bought are quite numerous, he will have to wheel
himself around a lot. This can cause bleeding if he overexerts himself, and thus he needs to plan how to buy all the
items required while having to wheel himself over the least distance.
The Actual Problem Description
Today, Ketfah has to visit a supermarket at West Coast area to buy groceries (name omitted to avoid indirect
advertising). ket fah has visited this place numerous times and therefore he knows the location of various N items in
that supermarket. He has estimated the direct wheeling time from one point to every other points in that supermarket
(in seconds) and store that information in a 2D table T of size (N+1) * (N+1). Given a list of K items to be bought
today, he wants to know what is the minimum amount of time to complete the shopping duty of that day. We have to
make some simplifying assumptions in order for this problem to be solvable… :
Ketfah always starts at vertex 0, the entrance (+ cashier section) of that supermarket.
There are V = N+1 vertices due to the presence of this special vertex 0.
The other N vertices corresponds to the N items.
The vertices are numbered from [0..N].
The direct wheeling time graph that is stored in a 2D table T is a complete graph.
T is a symmetric square adjacency matrix with T[i][i] = 0 for all i in [0..N].
The values inside T is guaranteed to be between [1..1000].
Ketfah has to grab all K items (numbered from [1..K]) that he has to buy that day, or he will have to come
again another day which takes even more effort. Here 1 ≤ K ≤ N.
Ketfah is very efficient, once he arrives at the point that stores item i, he can grab item i into his shopping bag
in 0 seconds (e.g. for item ‘banana’, he does not have to compare the price of ‘banana A’ versus ‘banana B’
and he does not have to select which banana looks nicer, etc…). So, Ketfah’s shopping time is only
determined by the total time taken to wheel himself inside that supermarket to grab all the K items.
Search search for… in NUS Websites
NUS WebMail IVLE LIBRARY MAPS
CS2010 CodeCrunch
https://codecrunch.comp.nus.edu.sg/task_view.php?tid=2957 2/3
In this problem, Ketfah ends his shopping when he arrives at the cashier (also at vertex 0) after grabbing all
the required K items.
Ketfah can grab the K items in any order, but the total wheeling time (i.e. time to wheel himself from vertex 0
→ to various points in the supermarket in order to grab all the K items → back to vertex 0) must be
minimized. Ketfah can choose to bypass a certain point that is not in his shopping list or even revisit a point
that contains item that he already grab (he does not need to regrab it again) if this leads to faster overall
shopping time.
See below for an example supermarket:
A sample supermarket layout, N = 3, V = 3+1 = 4
Example Queries:
1. If today, Ketfah has to buy all item 1, item 2, and item 3, then one of the best possible shopping route is like
this: 0 → 1 → 2 → 3 → 0 with a total wheeling time of: 20+30+12+35 = 97 seconds.
2. If tomorrow, Ketfah has to buy only item 1 and item 2, then one of the best possible shopping route is still: 0 →
1 → 2 (→ 3) → 0 with a total wheeling time of: 20+30+(12+35) = 97 seconds. Notice that although Ketfah
does not have to buy item 3, taking sub path 2 → 3 → 0 (where Ketfah will just bypass item 3) is faster than
taking sub path 2 → 0.
3. If two days later, Ketfah has to buy only item 2, then one of the best possible shopping route is like this: 0 (→
3) → 2 (→ 3) → 0 with a total wheeling time of: (35+12)+(12+35) = 94 seconds. That is, Ketfah bypass
through item 3 twice.
4. If three days later, Ketfah has to buy only item 2 and item 3, then one of the best possible shopping route is
like this: 0 → 3 → 2 (→ 3) → 0 with a total wheeling time of: 35+12+(12+35) = 94 seconds. See that Ketfah
can revisit point 3 although he does not have to grab item 3 twice.
Hopefully these four examples should be clear enough to describe this problem.
The skeleton program Supermarket.java (click to view) that can handle all input/output details is already written for
you.
You just need to implement one (or more
1 CS2010
) method(s)/function(s):
int Query()
You are given a 2D matrix T of size (N+1) * (N+1) and an array shoppingList of size K. Query these two data
structures and answer the query as defined above.
Subtask A Constraints (70 points)
Time Limit: 1s.
The supermarket is a very small convenience store and everything there have to be grabbed/bought. 1 ≤ K = N ≤ 10.
Special for this Subtask A: T[i][j] ≤ T[i][k]+T[k][j] for all combinations of i, j, and k.
Note that the example above is for Subtask B :).
There are a few (not more than 30) test cases in the test data for Subtask AB.
Sample Input
2
3 3
1 2 3
0 20 47 35
3/31/2017 CodeCrunch
https://codecrunch.comp.nus.edu.sg/task_view.php?tid=2957 3/3
© Copyright 20092017 National University of Singapore. All Rights
Reserved.
Terms of Use | Privacy | Nondiscrimination
MySoC | Computing Facilities | Search | Campus Map
School of Computing, National University of Singapore
20 0 30 34
47 30 0 12
35 34 12 0
1 1
1
0 10
10 0
Sample Output
97
20
Generating Test Data
The given sample input/output are for illustration purpose and are not enough to verify the correctness of your
solution.
You are encouraged to generate and post additional test data in CS2010 Facebook group.
Please use SupermarketVerifier.java (click to view) to verify whether your custommade test data conform with the
required specifications.
Problem Author
Dr Steven Halim/Dr Chong Ket Fah
For CS2010/R.
Footnotes
1
If needed, you can write additional helper methods/functions to simplify your code.
Submission (Course)
Select course: CS2010 (2016/2017 Sem 2) Data Structures and Algorithms II
Your Files:
SUBMIT (only .java, .c, .cpp and .h extensions allowed)
To submit multiple files, click on the Browse button, then select one or more files. The selected file(s) will be
added to the upload queue. You can repeat this step to add more files. Check that you have all the files
needed for your submission. Then click on the Submit button to upload your submission.
3/31/2017 CodeCrunch
https://codecrunch.comp.nus.edu.sg/task_view.php?tid=2958 1/5
Logged in as: e0009011
CodeCrunch
Home My Courses Browse Tutorials Browse Tasks Search My Submissions Logout
CS2010 2016/2017 Sem 2: PS6 B
Tags & Categories
Tags:
Categories:
Related Tutorials
Task Content
A Trip to the Supermarket, v2017 (Subtask B)
The Actual Problem Description
Please refer to Subtask A for the full problem description.
Subtask B Constraints (additional 30 points)
Time Limit: 1s.
The supermarket is a minimart that sells ~hundreds of grocery items. However, Ketfah only needs to buy some items.
1 ≤ N ≤ 200, 1 ≤ K ≤ 10, K ≤ N.
For Subtask B, it is no longer guaranteed that: T[i][j] ≤ T[i][k] + T[k][j] for all combination of i, j, and k.
Sample Input
5
3 3
1 2 3
0 20 51 35
20 0 30 34
51 30 0 12
35 34 12 0
3 2
1 2
0 20 51 35
20 0 30 34
51 30 0 12
35 34 12 0
3 1
2
0 20 51 35
20 0 30 34
51 30 0 12
35 34 12 0
3 2
2 3
0 20 51 35
Search search for… in NUS Websites
NUS WebMail IVLE LIBRARY MAPS
3/31/2017 CodeCrunch
https://codecrunch.comp.nus.edu.sg/task_view.php?tid=2958 2/5
20 0 30 34
51 30 0 12
35 34 12 0
200 5
11 22 33 44 55
0 543 721 835 40 215 207 6 237 487 419 823 909 600 564 248 88 188 374 376 856 971 77 316 223 716 898 504 8543 0 932 872 548 328 555 886 199 77 989 465 796 751 547 866 74 77 94 821 641 38 145 261 655 981 882 404 8721 932 0 221 882 914 196 164 309 791 651 112 109 295 395 185 189 791 426 170 724 854 699 186 925 555 601835 872 221 0 769 417 718 541 572 442 416 768 630 192 948 886 443 281 494 879 200 377 569 151 885 473 3 4540 548 882 769 0 886 34 433 822 790 823 120 298 390 256 729 912 4 604 912 853 284 51 540 508 107 903 121 1215 328 914 417 886 0 661 791 303 403 568 684 525 736 22 199 556 323 595 748 942 797 443 305 252 131 142 6207 555 196 718 34 661 0 76 944 963 745 805 778 530 988 859 94 743 944 101 812 184 239 248 336 360 588 7016 886 164 541 433 791 76 0 515 954 448 418 38 105 428 748 734 379 84 372 10 797 350 483 197 590 305 884 58237 199 309 572 822 303 944 515 0 540 893 872 130 43 835 258 754 668 211 973 46 577 832 35 493 535 458 474487 77 791 442 790 403 963 954 540 0 570 762 369 826 481 769 982 675 149 725 607 492 853 356 212 577 306 5419 989 651 416 823 568 745 448 893 570 0 62 21 951 651 576 64 731 752 409 339 438 220 373 199 96 331 593823 465 112 768 120 684 805 418 872 762 62 0 975 486 999 20 917 384 513 771 276 592 335 906 666 108 628 68909 796 109 630 298 525 778 38 130 369 21 975 0 995 750 150 864 92 775 123 234 605 68 25 331 890 861 422 9600 751 295 192 390 736 530 105 43 826 951 486 995 0 736 843 326 416 621 730 308 729 520 692 636 48 49 299564 547 395 948 256 22 988 428 835 481 651 999 750 736 0 941 893 162 7 53 27 209 529 561 385 50 354 398 49248 866 185 886 729 199 859 748 258 769 576 20 150 843 941 0 439 121 765 793 906 650 906 971 443 863 270 388 74 189 443 912 556 94 734 754 982 64 917 864 326 893 439 0 104 277 225 403 352 343 819 2 44 380 172 900188 77 791 281 4 323 743 379 668 675 731 384 92 416 162 121 104 0 896 721 474 169 641 739 611 127 465 832374 94 426 494 604 595 944 84 211 149 752 513 775 621 7 765 277 896 0 418 882 426 615 17 835 514 94 932 32376 821 170 879 912 748 101 372 973 725 409 771 123 730 53 793 225 721 418 0 889 434 248 438 434 228 719 6856 641 724 200 853 942 812 10 46 607 339 276 234 308 27 906 403 474 882 889 0 841 484 86 755 693 738 503971 38 854 377 284 797 184 797 577 492 438 592 605 729 209 650 352 169 426 434 841 0 771 345 324 368 501 577 145 699 569 51 443 239 350 832 853 220 335 68 520 529 906 343 641 615 248 484 771 0 642 368 52 666 368316 261 186 151 540 305 248 483 35 356 373 906 25 692 561 971 819 739 17 438 86 345 642 0 31 813 780 343 9223 655 925 885 508 252 336 197 493 212 199 666 331 636 385 443 2 611 835 434 755 324 368 31 0 749 448 763716 981 555 473 107 131 360 590 535 577 96 108 890 48 50 863 44 127 514 228 693 368 52 813 749 0 414 196 2898 882 601 3 903 142 588 305 458 306 331 628 861 49 354 270 380 465 94 719 738 501 666 780 448 414 0 760504 404 294 452 121 680 701 884 474 534 593 687 422 299 398 348 172 832 932 649 503 517 368 343 763 196 76806 84 887 941 191 258 33 580 406 992 73 780 900 662 490 36 900 433 322 63 66 353 988 932 866 245 105 794239 13 288 8 810 682 141 278 70 415 492 140 226 927 12 991 213 545 74 506 594 895 860 223 66 309 636 877 4339 303 31 617 959 721 629 649 101 603 13 533 58 178 249 250 341 963 646 531 174 558 997 498 115 271 474 4983 114 462 882 852 62 131 156 398 640 278 214 204 491 149 704 743 485 573 120 400 855 564 865 267 514 663432 276 387 876 865 353 123 168 587 635 118 72 578 998 840 596 995 14 714 867 440 225 594 676 857 234 718994 577 115 362 720 882 426 592 670 217 921 158 780 707 152 319 961 602 492 636 186 683 691 812 365 505 91970 649 191 794 275 455 28 613 149 685 650 578 793 373 119 303 122 967 869 408 843 68 870 810 54 752 701 3563 719 413 486 320 709 181 686 150 156 714 473 473 483 719 668 995 638 781 932 48 906 996 210 787 237 366394 849 710 188 420 370 667 707 244 896 756 183 482 419 802 506 996 279 888 591 221 921 95 468 538 634 81359 552 299 890 5 315 420 612 475 371 386 820 970 782 898 278 144 329 908 386 190 483 88 374 165 453 31 33264 89 4 619 581 894 447 28 381 851 916 7 121 76 938 666 342 216 676 448 714 253 958 835 779 480 807 563 7391 290 863 711 707 299 962 612 745 985 22 171 453 406 314 578 843 758 349 620 846 453 747 7 418 305 376 5885 440 439 501 456 291 95 460 589 351 452 310 613 236 268 708 571 76 813 697 574 210 805 391 950 18 125 410 693 717 349 779 71 295 120 316 610 738 456 819 360 49 924 525 386 95 316 440 726 889 593 155 655 542 64585 651 85 941 626 643 862 781 258 379 514 822 333 666 490 511 137 88 749 628 609 737 585 842 824 113 91 7516 537 829 24 715 563 727 939 445 215 677 396 195 175 491 788 76 274 772 651 140 422 672 578 466 418 408632 832 354 393 601 547 709 277 231 544 958 992 34 258 545 205 891 765 54 959 596 345 555 164 729 355 352415 974 490 760 922 344 66 841 230 8 413 564 607 946 554 37 104 533 432 810 384 689 155 950 595 703 291 35674 849 744 41 614 870 142 77 35 955 937 330 96 419 57 430 618 790 247 827 288 326 475 225 527 95 375 368244 759 874 140 661 785 664 998 540 996 818 905 54 749 823 969 514 835 253 471 617 433 165 101 512 830 650129 753 125 322 371 650 897 424 52 237 848 206 879 776 231 752 644 696 530 694 977 441 149 734 276 713 405531 992 81 282 260 705 26 448 621 100 73 95 195 709 611 231 83 315 456 659 97 612 375 705 48 56 709 20 476561 744 66 606 922 327 554 154 336 133 981 487 999 742 726 493 852 764 147 695 583 372 732 979 443 934 297674 434 36 381 791 823 628 248 470 420 92 668 558 599 193 890 439 288 465 268 862 381 75 882 529 990 754 8302 516 606 9 988 943 269 631 13 444 618 625 573 916 854 128 813 781 679 414 515 397 163 454 254 84 863 97509 380 240 690 418 543 500 192 48 863 790 813 964 914 527 407 872 548 640 303 701 6 692 197 425 361 333 9462 357 268 487 573 110 110 600 512 595 242 296 950 845 119 941 791 611 894 955 413 683 980 123 815 116 62513 929 947 679 46 813 218 674 865 22 343 814 629 489 683 941 590 657 491 875 834 951 446 762 215 130 17 9305 612 574 942 89 916 521 183 459 462 609 230 472 733 53 882 103 182 742 618 616 206 642 387 738 620 18 5869 310 21 454 251 697 858 260 535 350 895 322 85 658 581 474 583 318 530 17 94 259 996 256 406 440 34 251974 289 722 755 994 458 371 710 77 109 856 965 265 442 649 561 32 929 298 728 204 686 846 847 92 405 254 2809 518 799 312 541 333 922 292 792 770 56 889 438 75 358 803 123 57 594 169 914 849 642 68 682 962 757 80608 616 335 524 304 66 974 697 872 960 428 115 702 670 178 866 194 827 634 912 469 512 464 829 530 93 716764 149 631 802 424 558 450 102 849 219 365 198 113 535 407 748 318 794 285 560 377 298 531 556 54 220 73395 236 779 244 848 687 289 502 88 999 117 476 613 509 806 85 275 884 107 776 97 883 166 177 850 355 156 7571 907 535 830 880 473 200 341 476 571 423 164 133 198 438 504 950 868 63 558 277 118 146 155 898 930 535876 993 501 459 598 349 988 63 695 96 765 795 399 660 439 469 823 924 703 389 356 745 371 358 985 391 92667 77 63 598 301 740 370 612 451 306 946 776 639 941 386 877 195 845 725 660 283 230 793 993 444 674 823 7744 555 678 405 90 173 886 563 608 154 842 710 875 576 149 625 704 871 753 635 125 12 786 253 177 970 100683 66 255 219 412 450 688 917 111 877 959 644 564 30 560 688 303 889 671 22 763 433 750 624 644 79 433 3727 266 249 851 936 296 704 389 362 562 555 436 944 461 96 39 932 372 715 882 299 729 850 44 357 434 356 78
3/31/2017 CodeCrunch
https://codecrunch.comp.nus.edu.sg/task_view.php?tid=2958 3/5
27 266 249 851 936 296 704 389 362 562 555 436 944 461 96 39 932 372 715 882 299 729 850 44 357 434 356 78856 54 62 4 46 658 779 184 308 98 931 708 511 931 930 911 881 189 151 815 432 148 732 592 99 872 326 49 54119 475 911 539 733 71 254 117 557 976 775 537 371 742 186 901 204 586 766 96 238 318 644 392 449 92 830 4949 462 850 535 428 307 827 121 660 150 143 178 280 285 589 556 108 419 492 363 646 817 519 760 912 338 88174 250 910 973 13 929 923 35 327 496 608 71 364 936 741 837 130 348 326 3 437 985 575 168 130 509 16 951923 431 571 876 626 436 726 723 16 508 607 556 760 389 319 61 195 995 645 398 251 756 877 193 832 944 795368 620 345 577 952 627 82 715 560 983 942 891 377 695 805 839 284 431 238 435 255 202 366 715 436 556 516119 328 732 44 933 736 559 733 844 344 919 340 305 306 806 433 644 158 427 107 519 850 662 272 397 297 497472 756 167 729 597 804 631 258 802 364 115 680 749 356 174 850 257 49 651 446 581 450 376 909 866 458 104568 443 37 843 894 177 158 760 179 491 931 158 29 331 648 499 783 519 950 897 552 489 637 54 537 86 175 37426 251 641 41 366 508 62 859 169 253 414 686 670 597 202 24 799 978 817 555 797 15 402 806 324 481 801 54470 356 223 510 340 11 695 123 753 303 324 870 694 420 342 499 942 597 598 414 662 871 314 662 610 662 630392 331 195 385 937 62 506 645 998 894 998 611 638 71 264 671 999 700 362 126 723 659 900 68 250 928 173 8349 390 280 719 835 963 308 440 114 954 513 902 606 166 668 643 818 39 754 654 572 276 618 986 604 449 957780 50 546 770 116 123 533 512 598 964 90 99 521 475 100 266 141 868 923 823 204 278 530 882 836 614 893 5582 36 909 44 708 930 900 579 526 917 393 226 927 357 328 631 537 699 977 387 541 245 481 318 91 436 707 3302 530 902 19 192 872 265 852 250 244 620 985 48 434 431 862 367 520 521 563 65 380 257 184 248 723 977 5925 615 135 598 858 767 486 796 305 341 176 53 955 237 368 179 893 883 787 533 711 521 556 23 837 490 281279 947 103 550 400 339 323 417 181 273 543 431 136 933 763 630 697 69 517 920 819 392 415 871 273 58 649240 10 323 858 636 409 587 809 223 483 564 322 621 905 604 534 158 897 419 147 367 834 181 889 754 77 424440 720 413 471 214 894 575 745 200 744 785 48 682 737 717 764 222 332 903 83 823 700 571 505 908 950 894639 101 714 858 891 955 840 728 98 37 483 421 83 420 795 973 737 57 951 416 778 943 66 427 885 825 865 602317 196 225 867 673 139 356 122 672 860 855 590 822 65 459 110 508 233 861 786 147 80 456 489 599 800 289903 310 799 859 179 960 88 192 85 287 160 159 759 141 279 779 646 786 93 872 76 2 141 297 106 752 804 569279 324 822 775 769 779 838 38 824 544 687 137 842 983 780 319 445 63 899 658 221 459 613 389 45 237 165 7980 144 523 923 734 449 323 33 312 747 85 481 169 466 655 437 339 156 361 461 368 749 545 385 166 671 997955 49 677 344 864 989 53 919 236 567 775 372 255 387 284 817 971 636 575 61 688 520 535 425 697 696 329 7332 4 641 605 914 300 663 457 156 202 48 82 683 552 610 31 476 889 117 578 516 132 160 305 885 172 97 91 1261 362 634 220 291 610 516 867 736 311 444 61 957 831 714 244 869 936 211 433 905 267 297 673 120 415 592311 543 362 844 891 816 280 730 334 541 184 390 38 766 852 870 784 105 649 375 142 808 549 587 410 321 35950 347 559 874 58 234 971 58 321 350 392 562 213 242 70 777 669 953 111 600 564 664 967 245 978 934 464 3847 223 768 357 430 902 410 953 761 102 25 96 262 251 588 834 33 409 951 843 892 690 100 159 847 643 948 2543 112 823 834 260 933 807 362 976 270 503 499 867 804 138 868 558 523 963 107 305 604 630 414 683 372 17656 307 599 798 622 92 125 112 655 590 984 46 952 749 868 723 103 55 938 456 906 428 668 834 485 768 81 1688 598 312 584 80 724 949 538 538 994 861 135 734 965 689 827 293 884 390 230 470 836 127 536 198 425 418321 549 87 150 295 731 829 143 816 851 90 119 441 986 225 614 729 744 177 115 183 729 582 154 888 421 147511 135 539 205 172 395 804 360 881 711 898 260 208 794 41 262 837 181 363 883 860 273 863 147 728 434 183552 402 261 717 550 799 627 448 5 896 391 51 502 481 823 497 504 390 399 182 700 404 847 464 146 401 509 2597 324 194 115 328 354 414 1 488 98 284 401 176 819 252 887 599 771 569 967 338 468 977 742 166 421 701 5988 528 632 617 191 383 846 433 598 118 592 417 161 821 878 311 915 971 266 845 819 628 195 5 240 166 688413 650 944 489 365 648 708 982 60 478 689 887 106 465 731 234 39 501 761 502 711 50 348 260 579 239 736 9923 293 869 33 698 753 40 880 26 942 209 443 440 205 122 130 181 429 409 705 930 825 774 296 806 137 683 8316 336 166 763 381 901 983 947 866 911 882 344 584 311 114 134 584 851 537 992 213 471 238 426 200 207 40330 881 337 489 999 900 224 533 334 334 23 291 107 688 182 396 526 834 801 112 387 490 606 873 826 172 147715 591 467 882 77 92 273 267 37 537 941 106 138 348 515 822 901 316 992 481 722 402 481 916 156 574 625 8502 63 70 41 286 266 279 697 524 872 558 910 12 373 957 274 648 393 63 1 349 629 346 386 976 494 742 850 85 184 592 712 919 634 384 549 898 229 839 579 3 740 717 86 638 512 330 680 35 626 998 259 873 437 183 338792 71 537 440 238 110 343 985 396 289 210 732 762 562 658 559 380 836 295 879 556 632 742 665 780 177 520952 463 115 940 491 31 90 30 12 339 898 317 356 569 104 242 882 63 633 662 729 30 580 499 276 221 937 688743 126 904 351 193 271 561 552 460 641 575 737 933 475 675 84 874 608 783 845 508 462 814 842 318 16 37 9317 299 724 92 483 895 680 680 636 526 788 755 956 276 396 304 889 192 192 310 454 715 407 990 881 697 624393 459 92 706 15 589 285 837 565 896 544 547 604 113 409 48 420 409 895 573 42 479 579 81 28 660 886 591231 884 336 433 39 365 363 866 586 767 330 234 972 434 364 725 919 731 571 153 671 157 889 584 56 220 162854 344 404 613 87 880 923 305 848 856 219 301 62 335 977 531 278 299 506 796 449 899 869 627 337 513 476668 542 764 215 207 793 755 326 264 96 73 455 110 27 188 21 87 637 391 435 354 342 462 652 12 748 203 479218 143 470 561 746 224 899 909 496 997 397 12 674 213 66 3 923 266 945 847 900 978 961 29 364 915 311 114905 531 581 74 818 984 174 686 520 988 919 15 786 208 937 441 42 208 221 750 910 82 956 923 238 864 744 85215 69 186 177 161 198 123 993 46 645 212 558 128 386 837 52 997 815 676 306 113 657 743 417 714 335 972 1906 128 557 634 964 357 364 324 809 542 884 280 666 856 699 765 292 730 547 790 278 308 300 512 171 832 40624 208 340 5 105 590 115 681 534 524 436 442 844 378 748 654 337 608 728 821 42 321 303 206 407 583 637 3221 470 68 17 912 709 370 377 897 869 536 777 679 699 121 131 8 945 20 772 240 246 834 868 201 770 705 985608 76 707 79 950 722 938 164 558 153 525 184 759 980 662 625 597 418 584 523 320 97 320 464 347 900 271 519 921 156 906 531 567 769 896 735 388 149 638 713 915 536 588 979 706 780 46 210 493 506 858 14 689 240 8444 310 567 118 420 248 4 267 826 41 82 771 787 885 885 863 436 338 158 545 39 554 236 139 247 996 482 646826 76 510 978 864 892 904 833 757 818 1 494 296 858 278 948 423 231 303 538 616 460 669 86 236 16 48 628935 758 629 790 15 923 175 341 35 559 309 436 341 712 867 774 419 437 82 480 354 88 711 765 819 805 646 95310 346 485 145 59 420 390 132 616 400 982 683 894 924 568 778 408 812 971 485 552 892 886 426 816 398 224538 547 194 217 488 458 533 293 350 489 551 938 624 965 418 384 709 650 428 109 923 485 220 347 359 661 69363 309 239 347 205 181 864 942 127 453 560 350 142 804 746 880 504 364 229 540 771 914 701 753 235 354 69541 372 608 232 697 63 280 288 893 115 528 471 652 522 166 751 728 639 857 480 178 328 298 632 938 156 774762 355 240 423 788 342 244 256 734 734 272 681 466 971 340 947 475 392 711 44 389 261 596 229 693 273 46439 486 768 787 947 141 496 901 350 807 722 449 692 684 283 400 581 678 986 854 641 211 118 321 409 497 64999 80 61 421 913 46 194 762 138 597 257 472 393 993 536 929 138 617 163 215 662 230 636 934 882 618 24 95620 833 942 599 796 582 298 665 543 148 778 583 235 651 344 423 344 266 556 4 151 853 339 471 325 614 823858 939 895 654 269 660 86 639 834 489 372 238 581 580 868 372 505 68 793 198 895 781 337 257 782 970 165
3/31/2017 CodeCrunch
https://codecrunch.comp.nus.edu.sg/task_view.php?tid=2958 4/5
858 939 895 654 269 660 86 639 834 489 372 238 581 580 868 372 505 68 793 198 895 781 337 257 782 970 165661 287 972 816 231 340 835 643 910 186 407 464 22 556 305 195 458 322 921 656 811 385 722 203 510 558 612540 351 144 502 103 703 735 935 305 109 11 124 777 625 165 963 603 815 790 958 787 709 292 512 992 196 64417 465 820 890 829 27 125 600 781 660 987 389 158 909 897 244 834 186 521 567 986 509 37 934 650 927 832967 533 339 631 788 265 809 753 627 576 474 636 28 577 733 273 365 698 352 31 849 591 708 377 590 263 321668 69 266 979 279 713 300 365 242 507 850 646 960 149 880 765 59 640 26 866 708 296 68 241 284 937 26 351179 917 193 200 64 309 843 860 794 433 966 510 429 927 755 764 991 51 669 568 751 663 156 705 886 838 441225 209 900 221 393 339 97 415 659 48 747 709 299 387 689 709 127 55 866 871 458 694 404 235 776 439 332 1164 504 468 351 566 999 964 542 526 943 299 495 474 127 86 897 780 552 283 959 215 11 699 361 249 446 4 59845 744 548 410 37 864 315 110 536 591 503 892 145 82 362 671 848 534 295 237 211 75 534 451 948 221 461 1208 728 484 556 352 909 828 89 933 799 730 336 802 196 22 5 590 601 564 407 925 473 261 938 889 577 842 24571 590 508 959 730 790 833 963 123 437 653 971 797 344 795 617 180 659 515 876 376 156 590 914 298 776 28218 56 595 753 228 957 398 678 621 191 487 379 342 832 358 411 917 90 756 800 545 600 709 558 518 86 921 534 319 456 541 394 864 145 366 719 732 743 328 614 454 414 555 515 324 36 932 386 92 925 160 860 617 242 3702 708 990 786 987 766 380 774 293 263 193 746 232 650 78 648 814 706 356 677 136 559 442 589 208 279 489619 691 548 997 921 471 414 135 901 4 921 241 558 98 172 692 703 754 242 411 150 285 642 806 585 479 719 7205 984 428 778 931 809 548 779 917 272 149 431 94 410 615 258 255 860 390 155 675 535 292 437 182 343 116789 893 787 691 755 91 436 817 40 566 467 965 343 538 718 534 888 419 540 998 813 95 477 607 780 4 573 97045 644 810 341 535 477 800 765 297 219 167 117 709 866 71 420 714 610 442 507 533 221 378 61 715 579 952 6424 112 730 725 615 153 202 206 612 648 540 297 613 314 615 950 846 345 96 536 983 753 798 547 509 265 27456 78 205 759 273 373 646 67 621 65 286 552 303 845 549 824 584 185 441 71 578 937 594 648 79 539 488 36172 359 780 276 471 663 167 805 894 860 335 57 287 514 374 214 882 334 381 217 683 662 510 194 614 687 615819 279 254 52 404 5 22 273 594 245 826 6 842 977 113 721 614 355 244 136 827 768 217 593 470 780 396 77 8776 910 867 292 211 10 61 458 775 192 155 655 937 64 348 260 926 669 897 758 310 411 40 513 529 555 301 66623 81 668 350 120 145 924 295 671 690 671 325 882 872 737 226 946 901 897 901 902 352 823 65 565 994 6884 236 535 42 860 754 280 865 186 141 51 945 908 262 485 953 163 22 896 199 829 491 584 182 989 172 628 499179 481 504 121 182 819 831 597 90 527 887 726 552 749 6 678 829 534 5 761 54 390 645 468 971 123 354 596987 637 437 906 659 907 440 156 670 807 13 160 935 291 609 422 2 625 255 882 949 230 357 33 421 193 7 997178 634 551 904 176 521 95 701 502 426 732 861 440 562 655 963 201 68 721 56 608 51 256 3 903 557 682 905440 842 951 703 21 30 398 457 911 865 690 945 97 813 223 696 810 313 10 562 711 439 614 331 497 124 182 84822 100 759 58 63 481 461 518 67 530 985 809 981 322 216 779 168 303 788 309 984 648 4 588 961 810 404 166713 477 119 862 619 921 310 296 218 6 313 595 815 368 586 870 533 683 246 759 254 830 908 512 275 946 115380 402 481 804 916 483 893 452 265 784 996 563 84 32 526 254 553 96 207 585 822 441 538 307 865 445 597 1539 579 636 306 884 247 55 3 988 161 768 128 75 500 979 671 353 908 213 342 847 220 826 406 94 582 197 969236 454 94 155 692 217 367 270 479 552 683 169 478 814 791 28 178 335 833 198 966 197 276 772 206 688 371204 483 701 612 115 299 251 296 658 424 776 593 594 784 802 834 688 661 154 98 321 66 132 728 160 281 69268 955 961 85 375 693 170 467 934 971 732 954 807 530 541 850 229 976 549 320 558 329 567 578 613 814 124208 732 319 100 599 248 806 834 558 114 810 974 888 907 792 368 987 941 958 249 219 176 614 939 500 608 83958 63 171 957 171 316 160 936 156 655 984 244 862 531 747 36 386 859 704 542 695 325 247 616 492 386 521681 628 73 320 586 524 83 839 116 16 286 903 114 792 210 481 143 505 318 242 750 943 676 153 698 447 428 5897 585 95 844 709 731 66 21 214 889 85 867 94 939 695 740 796 749 807 663 522 113 886 26 681 385 862 724866 200 311 947 530 908 630 940 567 436 833 675 276 240 716 847 434 660 574 147 792 581 426 516 68 911 82961 640 141 541 718 812 231 803 901 334 377 896 595 514 416 309 866 491 251 20 611 670 674 116 433 153 712149 907 285 829 880 386 821 138 452 643 447 219 550 912 521 368 865 275 33 73 725 624 647 712 193 258 197706 610 838 862 749 115 197 217 449 614 197 585 376 974 845 450 149 638 416 340 936 661 703 263 218 330 14503 25 780 164 279 283 701 856 539 730 953 641 895 387 514 555 566 929 607 186 207 760 94 191 588 217 834573 680 176 439 402 230 586 351 212 71 209 232 374 495 537 819 898 452 115 142 547 143 94 314 925 247 241367 377 236 842 180 853 233 251 478 82 693 382 603 213 21 678 571 375 354 574 936 616 838 860 728 624 241921 407 348 895 767 386 257 788 148 461 553 82 718 548 706 300 773 499 38 575 772 924 791 532 453 25 955 8235 346 607 556 316 170 59 602 456 44 964 700 166 102 710 708 215 746 283 866 682 868 53 150 834 494 254 2447 762 207 111 77 35 827 558 766 833 923 141 507 485 639 152 681 245 979 617 251 441 113 799 184 451 408262 225 933 853 921 190 711 45 528 12 371 634 668 956 760 994 123 725 361 743 313 271 598 335 924 26 369 7724 976 327 960 27 932 885 405 518 905 907 109 505 337 933 999 410 853 223 786 496 798 10 517 216 597 9 51517 676 514 208 960 358 24 903 733 869 422 722 578 686 54 963 845 421 375 506 740 989 16 151 890 881 834 272 905 567 727 866 339 887 525 55 411 528 683 22 117 582 892 523 670 965 427 874 717 372 340 935 986 382 2163 876 392 88 318 640 2 86 572 318 879 440 569 466 591 935 201 890 951 372 804 253 445 338 448 633 952 46641 288 904 17 219 485 314 623 172 791 505 725 812 446 152 463 459 447 48 661 715 920 171 974 748 226 77 9982 35 377 714 357 672 854 495 116 484 15 767 594 805 37 808 835 86 484 857 519 133 137 779 383 888 769 20363 933 101 545 661 812 449 560 425 444 119 183 211 46 229 30 688 599 276 933 399 378 136 793 888 154 800Sample Output
97
97
94
94
139
Problem Author
Dr Steven Halim
For CS2010/R.
3/31/2017 CodeCrunch
https://codecrunch.comp.nus.edu.sg/task_view.php?tid=2958 5/5
© Copyright 20092017 All Rights
Reserved.
Terms of Use | Privacy | Nondiscrimination
MySoC | Computing Facilities | Search | Campus Map
School of Computing,
Submission (Course)
Select course: CS2010 (2016/2017 Sem 2) Data Structures and Algorithms II
Your Files:
SUBMIT (only .java, .c, .cpp and .h extensions allowed)
To submit multiple files, click on the Browse button, then select one or more files. The selected file(s) will be
added to the upload queue. You can repeat this step to add more files. Check that you have all the files
needed for your submission. Then click on the Submit button to upload your submission.
