-
Notifications
You must be signed in to change notification settings - Fork 7
/
broken_clock.py
53 lines (48 loc) · 1.56 KB
/
broken_clock.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
# Copyright (c) 2021 kamyu. All rights reserved.
#
# Google Code Jam 2021 Round 1B - Problem A. Broken Clock
# https://codingcompetitions.withgoogle.com/codejam/round/0000000000435baf/00000000007ae694
#
# Time: O(1)
# Space: O(1)
#
from itertools import permutations
def linear_congruence(a, m, b): # Time: O(logN), the same as gcd, Space: O(logN)
# gcd(a, m) = g and g|b, find x, s.t. ax % m = b % m
# => (a%m)x = my+(b%m)
# => gcd(m, a%m) = g and g|-(b%m), find y, s.t. my % (a%m) = -(b%m) % (a%m)
# => y = linear_congruence(m, a%m, -(b%m))
# => x = (my+(b%m))/(a%m)
ambs = []
while m:
a, m, b = m, a%m, -(b%m)
if m:
ambs.append((m, a, -b))
x = a # a is gcd
while ambs:
a, m, b = ambs.pop()
x = (m*x+b)//a
return x
def format_ticks(t):
s, n = divmod(t, TICKS_PER_SECOND)
m, s = divmod(s, 60)
h, m = divmod(m, 60)
return "%s %s %s %s" % (h, m, s, n)
def solution():
A, B, C = map(int, raw_input().strip().split())
# t%TOTAL = (h+x)%TOTAL
# 12*t%TOTAL = (m+x)%TOTAL
# 720*t%TOTAL = (s+x)%TOTAL
# => find t s.t.
# 11*t%TOTAL = (m-h)%TOTAL
# 708*t%TOTAL = (s-m)%TOTAL
for h, m, s in set(permutations([A, B, C])):
t = INV_11*(m-h)%TOTAL
if 708*t%TOTAL == (s-m)%TOTAL:
break
return format_ticks(t)
TICKS_PER_SECOND = 10**9
TOTAL = 12*60*60*TICKS_PER_SECOND
INV_11 = linear_congruence(11, TOTAL, 1)%TOTAL # Time: O(log(min(11, TOTAL))) = O(log11) = O(1)
for case in xrange(input()):
print 'Case #%d: %s' % (case+1, solution())