Assignments are boring
Statement
Goal
Story:Jasmine is on her desk, looking at the pile of papers that has been assigned to her for the week. But her mind has been wandering outside, thinking "How many days it would take to finish writing any given number of papers given she writes the minimum number for each paper?" You must help her track this for each day until the last day where the number of papers left is 0.
Rules:
To understand how she completes writing the papers in this hypothetical world, let's assume she has n papers where each paper has a page count from a range of 0 to 2 ^ p
i) Find the lowest page count from the n papers
ii) Subtract up to that page count for all of the n papers.
iii) Ignore the ones who have 0 pages left for the next turn
Repeats these steps until finally, all papers have 0 pages left to be completed.
To obtain the page count for the papers, we use a linear congruential generator expression (random number generator) :
Z(n+1) = (1664525 * Z(n) + 1013904223) MOD 2 ^ Power
Here, the initial value of Z(0) is passed as seed [but not kept in the list of papers] and power as power from the IDE. Then the expression is executed for N number of times to find the number of pages in sequential order.
For testcase 1: seed = 7, paper = 5, power = 3
--> For the number of pages of the first paper, we use the expression (1664525 * 7 + 1013904223) MOD 2 ^ 3 and obtain the first value as 2
--> For the number of pages of the second paper, we use the expression (1664525 * 2 + 1013904223) MOD 2 ^ 3 and obtain the second value as 1 …..
We repeat this until all of the pages counts for the starting list are obtained as [ 2, 1, 4, 3, 6 ]
Table representation:
2 1 4 3 6 # The starting list is always ignored
-------------------------------
1 0 3 2 5 [4 papers left]
0 0 2 1 4 [3 papers left]
0 0 1 0 3 [2 papers left]
0 0 0 0 2 [1 papers left]
0 0 0 0 0 [0 papers left]
Output: 4 3 2 1 0
Note: If the initial list of page counts has 0 present, it is considered only for the starting list as the lowest page count, and not later on.
Input
Line 1: a single integer seed that is the seed of the LCG generator.
Line 2: an integer paper representing the number of elements to be obtained by using the seed.
Line 3: an integer power representing the power of the modulo constant.
Line 2: an integer paper representing the number of elements to be obtained by using the seed.
Line 3: an integer power representing the power of the modulo constant.
Output
A sequence of numbers separated by a space where each number represents the number of assignments left after each day.
Constraints
0 < papers < 10^8
1< power < 8
1< power < 8
Example
Input
7 5 3
Output
4 3 2 1 0
Tags
Counting sort, Logical problem
Difficulty
Medium
Test cases
Simple Test
Input
7
5
3
Output
4 3 2 1 0
Simple Validator
Input
2
5
3
Output
4 3 2 1 0
Zero Page Test
Input
3
6
3
Output
5 4 3 2 1 0
Zero Page Validator
Input
6
8
3
Output
7 6 5 4 3 2 1 0
Same page count Test
Input
2
12
3
Output
11 9 8 6 4 3 1 0
Same page count Validator
Input
3
14
3
Output
12 10 8 7 6 4 2 0
A little big Test
Input
27
305
4
Output
286 267 248 229 210 191 172 153 134 115 96 77 58 39 19 0
A little big Validator
Input
105
425
4
Output
399 372 346 319 292 266 239 212 185 159 132 106 79 52 26 0
Slightly big Test
Input
792123
1500
6
Output
1476 1453 1429 1405 1381 1358 1334 1311 1288 1265 1242 1218 1195 1172 1149 1126 1102 1079 1056 1032 1009 986 962 939 916 893 869 846 822 799 775 751 728 705 682 659 636 612 589 565 541 517 494 471 448 424 400 376 353 329 305 282 258 234 211 187 163 139 116 93 70 46 23 0
Slightly big Validator
Input
12341123
2222
6
Output
2188 2153 2118 2084 2049 2014 1979 1944 1909 1874 1840 1805 1771 1736 1701 1666 1631 1596 1561 1526 1491 1456 1421 1387 1353 1318 1283 1248 1213 1179 1145 1111 1076 1042 1007 972 938 904 869 834 799 765 730 695 660 625 590 555 520 485 451 417 383 348 314 279 244 209 174 140 105 70 35 0
Isn't it too much? Test
Input
23401523
4500
7
Output
4465 4430 4395 4360 4325 4290 4255 4220 4185 4150 4114 4079 4044 4009 3974 3939 3904 3869 3834 3799 3764 3729 3694 3658 3622 3587 3552 3517 3482 3447 3412 3376 3341 3306 3271 3236 3201 3165 3130 3094 3059 3023 2988 2953 2918 2883 2848 2813 2778 2743 2708 2673 2638 2603 2568 2533 2498 2463 2428 2392 2357 2322 2287 2252 2216 2181 2146 2110 2075 2040 2004 1969 1934 1899 1864 1829 1793 1758 1723 1688 1653 1618 1583 1548 1513 1478 1443 1408 1373 1338 1303 1268 1233 1197 1161 1126 1091 1055 1020 985 950 915 880 845 809 774 739 704 669 633 598 563 528 493 457 422 386 351 315 280 245 210 175 140 105 70 35 0
Isn't it too much? Validator
Input
8361904
5250
7
Output
5209 5168 5127 5086 5045 5004 4963 4922 4881 4840 4799 4758 4717 4676 4635 4594 4553 4512 4471 4430 4389 4348 4307 4266 4225 4184 4143 4102 4061 4020 3979 3938 3897 3856 3815 3774 3733 3692 3651 3610 3569 3528 3487 3446 3405 3364 3323 3282 3241 3200 3159 3118 3077 3036 2995 2954 2913 2872 2831 2790 2749 2708 2667 2626 2585 2544 2503 2462 2421 2380 2339 2298 2257 2216 2175 2134 2093 2052 2011 1969 1928 1887 1846 1805 1764 1723 1682 1641 1600 1559 1518 1477 1436 1395 1354 1313 1272 1231 1189 1148 1107 1066 1025 984 943 902 861 820 779 738 697 656 615 574 533 492 451 410 369 328 287 246 205 164 123 82 41 0
This is against the law Test
Input
92374512
100000
7
Output
99219 98438 97657 96876 96095 95314 94533 93752 92971 92190 91408 90627 89846 89065 88284 87502 86720 85939 85158 84377 83596 82815 82034 81252 80470 79688 78907 78126 77344 76563 75782 75000 74219 73438 72656 71875 71093 70311 69530 68748 67967 67185 66404 65623 64842 64061 63279 62498 61717 60936 60155 59373 58592 57810 57029 56248 55467 54686 53905 53123 52342 51561 50780 49999 49217 48436 47655 46873 46092 45311 44529 43748 42967 42186 41405 40623 39841 39060 38279 37498 36717 35936 35155 34374 33593 32812 32031 31250 30469 29688 28906 28125 27344 26562 25780 24999 24218 23436 22655 21874 21093 20312 19531 18750 17968 17187 16406 15625 14844 14062 13281 12500 11719 10937 10155 9374 8592 7811 7029 6248 5467 4686 3905 3124 2343 1562 781 0
This is against the law Validator
Input
922
100000
7
Output
99219 98438 97656 96875 96093 95311 94530 93748 92967 92185 91404 90622 89841 89060 88279 87498 86717 85936 85155 84373 83592 82811 82030 81249 80468 79687 78906 78124 77343 76562 75781 75000 74218 73437 72656 71874 71093 70312 69530 68749 67968 67187 66406 65625 64843 64062 63281 62500 61719 60937 60156 59375 58594 57813 57032 56251 55470 54689 53907 53126 52345 51563 50781 50000 49219 48437 47656 46875 46094 45313 44532 43751 42969 42188 41407 40626 39845 39063 38282 37501 36719 35938 35156 34375 33593 32812 32030 31249 30468 29687 28906 28125 27343 26562 25781 25000 24219 23438 22657 21876 21095 20314 19533 18752 17971 17190 16408 15627 14846 14065 13283 12501 11720 10939 10158 9377 8596 7814 7033 6251 5469 4687 3906 3125 2344 1563 782 0
Are there even this many subjects? Test
Input
5739
1000000
7
Output
992187 984375 976562 968749 960936 953123 945310 937497 929685 921872 914060 906247 898434 890622 882810 874998 867186 859374 851562 843749 835937 828125 820313 812501 804689 796877 789064 781251 773439 765626 757813 750001 742188 734375 726563 718750 710938 703126 695313 687501 679688 671876 664064 656251 648438 640625 632813 625001 617188 609375 601562 593750 585937 578125 570312 562500 554688 546876 539063 531251 523439 515626 507813 500001 492189 484376 476564 468752 460940 453128 445316 437504 429691 421879 414066 406254 398442 390629 382816 375003 367190 359377 351564 343752 335939 328126 320313 312500 304687 296874 289062 281250 273437 265625 257813 250000 242188 234376 226563 218751 210938 203125 195313 187500 179688 171875 164062 156250 148438 140626 132813 125000 117188 109376 101564 93751 85939 78126 70314 62501 54688 46875 39063 31250 23437 15625 7813 0
Are there even this many subjects? Validator
Input
93280
1000000
7
Output
992187 984375 976562 968749 960936 953123 945310 937498 929685 921873 914061 906248 898435 890622 882810 874998 867186 859373 851560 843747 835934 828122 820310 812498 804686 796874 789061 781248 773436 765623 757810 749998 742185 734372 726560 718748 710936 703124 695312 687500 679687 671875 664063 656251 648438 640625 632813 625001 617188 609375 601562 593750 585937 578125 570312 562500 554688 546876 539064 531252 523439 515626 507813 500000 492188 484375 476563 468751 460939 453127 445315 437502 429690 421877 414064 406252 398440 390628 382815 375002 367189 359377 351565 343753 335941 328128 320315 312502 304689 296876 289064 281252 273439 265627 257815 250002 242190 234378 226565 218752 210939 203126 195313 187500 179688 171875 164062 156249 148437 140625 132812 124999 117187 109375 101563 93750 85938 78125 70313 62500 54687 46874 39061 31248 23436 15624 7812 0
Speed is everything Test
Input
3458
10000005
6
Output
9843755 9687505 9531255 9375005 9218754 9062504 8906254 8750004 8593754 8437504 8281254 8125004 7968754 7812504 7656254 7500004 7343754 7187504 7031254 6875003 6718753 6562503 6406252 6250002 6093752 5937502 5781252 5625002 5468752 5312502 5156252 5000002 4843752 4687502 4531252 4375002 4218752 4062502 3906252 3750002 3593752 3437502 3281252 3125002 2968752 2812502 2656252 2500002 2343752 2187502 2031252 1875002 1718752 1562502 1406252 1250002 1093752 937501 781251 625001 468751 312500 156250 0
Speed is everything Validator
Input
6344480
10000000
6
Output
9843750 9687500 9531250 9375000 9218750 9062500 8906250 8750000 8593750 8437500 8281250 8125000 7968750 7812500 7656250 7500000 7343750 7187500 7031250 6875000 6718750 6562500 6406250 6250000 6093750 5937500 5781250 5625000 5468750 5312500 5156250 5000000 4843750 4687500 4531250 4375000 4218750 4062500 3906250 3750000 3593750 3437500 3281250 3125000 2968750 2812500 2656250 2500000 2343750 2187500 2031250 1875000 1718750 1562500 1406250 1250000 1093750 937500 781250 625000 468750 312500 156250 0
Solution language
Solution
Stub generator input