Created
April 25, 2015 18:25
-
-
Save joostrijneveld/c0907afaaf5ef8ab228f to your computer and use it in GitHub Desktop.
The partial solution as listed in the GCJ contest analysis for 2015-R1A-B-small seems to contain an infinite loop
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
from fractions import gcd | |
from itertools import count | |
def naive_get_barber_number(N): | |
customer = 1; | |
for T in count(1): | |
for barber in range(B): | |
if T % M[barber] == 0: | |
# at this point N = 0 and customer > 0.. | |
# and boom, infinite loop | |
if customer == N: | |
return barber | |
customer += 1 | |
def slow_get_barber_number(N): | |
period = M[0] | |
for i in range(1, B): | |
period = period // gcd(period, M[i]) * M[i] | |
customers_per_phase = 0 | |
for i in range(B): | |
customers_per_phase += period // M[i] | |
N_in_my_phase = N % customers_per_phase | |
return naive_get_barber_number(N_in_my_phase) | |
M = [7,7,7] | |
B = 3 | |
N = 12 | |
print(slow_get_barber_number(N)) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment