PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4
Setter: utkarsh_adm
Tester: Harris Leung
Editorialist: hrishik85
DIFFICULTY:
717
PREREQUISITES:
None
PROBLEM:
Chef and Chefina are in a hotel where each of the 10 floors has 10 rooms. Chef’s room is X and Chefina’s room is Y. We have the output the difference in floors between Chef and Chefina
EXPLANATION:
Note that the rooms are numbered sequentially from 1 to 10 on the 1st floor, 11 to 20 on the 2nd floor and so on.
Hint 1
Given the room numbers X and Y, we need to be able to identify their floor numbers. What does the room number sequence from [10 * (i - 1) + 1] to [10 * i] tell us?
Hint 2
How do we identify the floors that Chef and Chefina are staying on?
Hint 2a
Given any room number - we know that it lies between [10 * (i - 1) + 1] to [10 * i] for some i. We now need to find what that ‘i’ is - that will give us the floor number.
Hint 2b
If we divide the room number by 10, what will that give us? A number between [(i - 1) + 1/10] and [ i ].
Hint 2c
If we round up the above division to the nearest integer, [ (i - 1) + 1/10] will round up to [(i - 1) + 1] = [ i ].
Hence we will get the floor number. Note that this is true for any of the rooms in that floor. For eg. take the 6th room - [10 * (i-1) + 6]. When you divide it by 10, we get [ (i-1) + 6/10 ], and rounding this up, we get [ (i-1) + 1 ] = [ i ] again.
Hint 3
What do we do after finding their floors?
Hint 3a
Now we just need to calculate the floor numbers for both Chef and Chefina and subtract them. However, is that sufficient or are we missing something?
Hint 3b
If we just output (Chef’s floor - Chefina’’s floor), we are making a mistake. What is the mistake?
Hint 3c
We don’t know whether Chef is on a higher floor or Chefina
Hint 3d
Consider the case when Chef is in room 45, and Chefina is in room 65. We would be outputting -2. But the answer should actually be 2. So we should take the absolute difference between their floors.
Hint 4
Full Solution:
Hint 4a
Chef’s floor number is math.ceil [X/10] and Chefina’s floor number is math.ceil [Y/10]
Hint 4b
We need to output the absolute value of the difference in their floors - i.e. abs (math.ceil [X/10] - math.ceil [Y/10])
TIME COMPLEXITY:
Time complexity is O(1).
SOLUTION:
Tester's Solution
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
const ll mod=998244353;
const int N=2e5+5;
int n;
ll a[N];
int main(){
ios::sync_with_stdio(false);cin.tie(0);
int t;cin >> t;
while(t--){
int a,b;cin >> a >> b;
int c=abs((a-1)/10-(b-1)/10);
cout << c << '\n';
}
}
Editorialist's Solution
t=int(input())
for _ in range(t):
X,Y = map(int,input().split())
X = ((X-1)//10)
Y = ((Y-1)//10)
print(abs(X-Y))