Coincidences on an Alien Clock
Autumn Tournament (2018)
Submission name: clock.cpp
Problem summary
An alien half-day contains a hours, each hour b minutes, each minute c seconds. The three hands move continuously and all point up at both endpoints. Count interior moments when all three hands coincide.
Input
a b c.
Output
The coincidence count, excluding both endpoints.
Constraints
1 < a,b,c < 400.
Worked example
Original statement sample.
Input
3 11 60
Output
1
Solution analysis
- Measure time t as a fraction of the half-day. The hour, minute and second hands make respectively t, a·t and a·b·t turns. The factor c changes the unit called a second, but the second hand still makes one full turn per minute, so it has a·b turns per half-day.
- The hands coincide precisely when (a−1)t and (a·b−1)t are both integers. If g=gcd(a−1,a·b−1), these simultaneous conditions hold at t=j/g for integer j. The interior choices j=1,...,g−1 give g−1 coincidences.
- For a=3,b=11, g=gcd(2,32)=2, so only t=1/2 is interior and the answer is 1. For an ordinary clock a=12,b=60, gcd(11,719)=1, so no interior triple coincidence occurs.
Why it works
Let u=a−1 and v=ab−1. Bézout’s identity implies ut and vt integral only if gcd(u,v)t is integral. Conversely t=j/g makes both differences integral because g divides u and v. Excluding j=0 and j=g proves the formula.
Watch out. The count can be zero even though the output wording calls it positive. Do not simulate ticks: the hands move continuously. c is read but does not affect the coincidence count.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<numeric>
using namespace std;
int main(){
int hours;
int minutes;
int seconds;
cin>>hours>>minutes>>seconds;
// Relative turns against the hour hand must both be integral.
int common=gcd(hours-1,hours*minutes-1);
cout<<common-1<<'\n';
}