Rocket Fuel一题# JobHunting - 待字闺中
A*t
1 楼
先抛砖。求2^i3^j数列的前k项和（从小到大排序）对q取模的值。
k很大，可以到10^15，q可以到10^9。
O(k)都不行啊。请大虾指教。
Rocket Fuel
Challenges / Roulette Predictor The contest has ended. Rank: N/A Score: 0
.00
After defeating the guard in pinball using your program, you are released
and try to make your escape. You find a ship captain who is willing to sell
you passage home, but unfortunately you have only a little money with you
since your earnings from the irrigation project are stashed in hiding and
you don't have time to retrieve them. Worried about being detained before
you are able to make your escape, you begin thinking of ways to make some
fast money on the space station.
You turn your attention to the space station's casino (run by the same mafia
that has abducted you) and soon realize that the casino's roulette wheel is
a now out-of-date brand that has been removed from operation elsewhere in
the galaxy since a customer noticed a pattern in the distance the ball
travels during each roll. Specifically, the number of units the ball travels
clockwise around the wheel is always of the form 2^i * 3^j where i and j
are non-negative integers, and the sequence is strictly increasing and
includes all such numbers exactly once, starting from 1 on the first spin
during the operation of the wheel. You decide that your best chance to make
some money and avoid suspicion is to quickly place one bet as soon as you
walk up to the table and then immediately leave with your winnings, so you
will need to write a program that will rapidly tell you where the ball will
land once you arrive at the wheel.
You note that to compute the position in which the ball will land on the
next spin, it suffices to know two pieces of information. First, you need to
know the number of slots in the wheel, which can easily be seen by
inspection when you walk up to the wheel (this particular brand of roulette
wheel was sold in many sizes). Second, you need to know the number of spins
that have been performed on the wheel since it began operation. Fortunately,
the operators of the roulette wheel have unwittingly placed a counter that
gives you exactly this information as a way of bragging about how long they
have been in business.
To give more details about the pattern of the roulette wheel:
On the first spin the ball starts at position 0 and ends in position 1.
On the second spin, the ball travels 2^1 * 3^0 additional units, starting at
position 1 and ending in position 3.
On the third spin, the ball travels 2^0 * 3^1 additional units and lands in
position 6.
On the fourth spin, the ball travels 2^2 * 3^0 additional units and lands in
position 10.
And so on.
To give more examples, the number of units traveled by the ball in each spin
forms the sequence:
1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 24, 27, 32, 36, 48, 54, 64, 72, 81,...
Thus, if the wheel has q slots, the outcomes of the first spins of the wheel
form the sequence:
1, 3, 6, 10, 16, 24, 33, 45, 61, 79, 103, 130, 162, 198, 246, 300, 364, 436,
517,...
where all members of the above sequence are taken modulo q (to account for
wrapparound when the ball makes a complete circle around the roulette wheel).
Thus, you should write a program that reads from standard input one line of
the form:
k q
and produces one line of output that contains the sum of the k smallest
numbers of the form 2^i 3^j where i, j >= 0 are integers, and the sum should
be taken modulo q. Since you can't see the counter or the wheel-size until
you approach the wheel, you want to support the largest inputs you can while
keeping the running time low in order to be prepared for as many
contingencies as possible. You may assume that q is between 2 and 10^9 (
inclusive), and should try to support the largest value of k that you can.
Test cases of increasing size will be given, with the vast majority of
points earned by supporting values of k that range from 10^9 up to a maximum
of 10^15 (the wheel could have been in operation a really, really long time
).
k很大，可以到10^15，q可以到10^9。
O(k)都不行啊。请大虾指教。
Rocket Fuel
Challenges / Roulette Predictor The contest has ended. Rank: N/A Score: 0
.00
After defeating the guard in pinball using your program, you are released
and try to make your escape. You find a ship captain who is willing to sell
you passage home, but unfortunately you have only a little money with you
since your earnings from the irrigation project are stashed in hiding and
you don't have time to retrieve them. Worried about being detained before
you are able to make your escape, you begin thinking of ways to make some
fast money on the space station.
You turn your attention to the space station's casino (run by the same mafia
that has abducted you) and soon realize that the casino's roulette wheel is
a now out-of-date brand that has been removed from operation elsewhere in
the galaxy since a customer noticed a pattern in the distance the ball
travels during each roll. Specifically, the number of units the ball travels
clockwise around the wheel is always of the form 2^i * 3^j where i and j
are non-negative integers, and the sequence is strictly increasing and
includes all such numbers exactly once, starting from 1 on the first spin
during the operation of the wheel. You decide that your best chance to make
some money and avoid suspicion is to quickly place one bet as soon as you
walk up to the table and then immediately leave with your winnings, so you
will need to write a program that will rapidly tell you where the ball will
land once you arrive at the wheel.
You note that to compute the position in which the ball will land on the
next spin, it suffices to know two pieces of information. First, you need to
know the number of slots in the wheel, which can easily be seen by
inspection when you walk up to the wheel (this particular brand of roulette
wheel was sold in many sizes). Second, you need to know the number of spins
that have been performed on the wheel since it began operation. Fortunately,
the operators of the roulette wheel have unwittingly placed a counter that
gives you exactly this information as a way of bragging about how long they
have been in business.
To give more details about the pattern of the roulette wheel:
On the first spin the ball starts at position 0 and ends in position 1.
On the second spin, the ball travels 2^1 * 3^0 additional units, starting at
position 1 and ending in position 3.
On the third spin, the ball travels 2^0 * 3^1 additional units and lands in
position 6.
On the fourth spin, the ball travels 2^2 * 3^0 additional units and lands in
position 10.
And so on.
To give more examples, the number of units traveled by the ball in each spin
forms the sequence:
1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 24, 27, 32, 36, 48, 54, 64, 72, 81,...
Thus, if the wheel has q slots, the outcomes of the first spins of the wheel
form the sequence:
1, 3, 6, 10, 16, 24, 33, 45, 61, 79, 103, 130, 162, 198, 246, 300, 364, 436,
517,...
where all members of the above sequence are taken modulo q (to account for
wrapparound when the ball makes a complete circle around the roulette wheel).
Thus, you should write a program that reads from standard input one line of
the form:
k q
and produces one line of output that contains the sum of the k smallest
numbers of the form 2^i 3^j where i, j >= 0 are integers, and the sum should
be taken modulo q. Since you can't see the counter or the wheel-size until
you approach the wheel, you want to support the largest inputs you can while
keeping the running time low in order to be prepared for as many
contingencies as possible. You may assume that q is between 2 and 10^9 (
inclusive), and should try to support the largest value of k that you can.
Test cases of increasing size will be given, with the vast majority of
points earned by supporting values of k that range from 10^9 up to a maximum
of 10^15 (the wheel could have been in operation a really, really long time
).
