Last Chime of the Clock Tower
National Olympiad — National round (2016 season)
Submission name: peal.cpp
Problem summary
A tower rings hourly and once at each half-hour from 06:00 to midnight. Hourly strikes follow a 12-hour clock. Given k consecutive ringing occasions totalling m strikes, find the latest possible final time.
Input
k and m.
Output
The latest final time in HH:MM, writing midnight as 00:00.
Constraints
1 ≤ k ≤ 37; 1 ≤ m ≤ 159. A matching interval exists.
Worked example
Input and output for the worked example discussed below.
Input
2 13
Output
00:00
Solution analysis
- Build the 37 ringing occasions at half-hour steps from 06:00 through 24:00. An integer hour contributes hour modulo 12, using 12 instead of 0; every half-hour contributes 1.
- Enumerate each consecutive window of k occasions and sum its strikes. Record its end whenever the total equals m. Processing ends chronologically means later matches replace earlier ones.
- For k=2,m=13, matches end at noon, 12:30 and midnight. Midnight is the latest even though its printed hour is 00. Keep chronological minutes until the final formatting step.
Why it works
Every possible observed interval is one consecutive k-element window of the constructed schedule, so examining every such window finds all matches.
Watch out. Count ringing occasions, not individual strikes. Midnight is after 23:30; do not order it as the beginning of the day.
Commented C++17 solution
An independently written complete program with standard headers.
// Every possible observed interval is one consecutive k-element window of the constructed schedule, so
// examining every such window finds all matches..
#include<iomanip>
#include<iostream>
#include<vector>
using namespace std;
int main(){
int count,total;
cin>>count>>total;
vector<int>strikes;
for(int minute=360;minute<=1440;minute+=30){
int hour=minute/60%12;
strikes.push_back(minute%60==30?1:(hour==0?12:hour));
}
int answer=0;
for(int end=count-1;end<int(strikes.size());end++){
int sum=0;
for(int index=end-count+1;index<=end;index++){
sum+=strikes[index];
}
if(sum==total){
answer=360+end*30;
}
}
cout<<setfill('0')<<setw(2)<<answer/60%24<<':'<<setw(2)<<answer%60<<'\n';
}