PROBLEM LINK: Champak and Clocks
Author: Yashodhan Agnihotri
Tester: Darshan Lokhande
DIFFICULTY:
CAKEWALK
PREREQUISITES:
Math
PROBLEM:
Find the number of times a right angle occurs between the hour hand and the minute hand in the given time range [L,R] , both inclusive, where L and R are hours in the 24-hour format.
EXPLANATION:
We can easily see that a right angle occurs twice per hour, except the cases of 3 and 9 when it occurs thrice per two hours.
We can iteratively count twice for every hour from L to R and subtract 1 from count for every occurence of 3,9,15,21.
This can also be done by maintaining a prefix array as done in the Tester’s solution below.
Another big corner case is [3,3] , [9,9] , [15,15] , [21,21] for which the answer will be 1 and not 0 as the right angle occurs at that very moment.
SOLUTIONS:
Setter's Solution
#include<bits/stdc++.h>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int q;
cin >> q;
while (q--)
{
int l, r, i;
cin >> l >> r;
int cnt = 0;
for (int i = l + 1; i < r; i++)
{
if (i == 3 || i == 9 || i == 15 || i == 21)
cnt++;
}
int ans = 2 * (r - l) - cnt;
if (l == r and (r == 3 || r == 9 || r == 15 || r == 21))
ans++;
cout << ans << "\n";
}
return 0;
}
Tester's Solution
#include<bits/stdc++.h>
#define boost ios::sync_with_stdio(false); cin.tie(0)
#define ll long long int
#define ld long double
#define mk make_pair
#define pb push_back
#define f first
#define s second
#define fo(i,a,b) for(i=a;i<b;i++)
#define foe(i,a,b) for(i=a;i<=b;i++)
#define all(x) x.begin(),x.end()
// #define vi vector<int>
#define vl vector <long long int>
// #define pii pair <int,int>
#define pll pair <long long int, long long int>
// #define vpii vector< pair<int,int> >
#define vpll vector < pair <long long int,long long int> >
#define MOD 1000000007
using namespace std;
const int inf = INT_MAX;
const ll inf64 = LLONG_MAX;
int main()
{
boost;
ll pre[25];
memset(pre, 0, sizeof pre);
pre[4] = pre[10] = pre[16] = pre[22] = -1;
for (int i = 1; i < 25; i++)pre[i] += pre[i - 1] + 2;
ll t;
cin >> t;
while (t--)
{
ll l, r;
cin >> l >> r;
ll ans;
ans = pre[r] - pre[l];
if (l == 3 or l == 9 or l == 15 or l == 21)ans++;
cout << ans << '\n';
}
return 0;
}
For doubts, please leave them in the comment section, I’ll address them.