PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Authors: d_k_7386
Tester: tabr
Editorialist: iceknight1093
DIFFICULTY:
1044
PREREQUISITES:
None
PROBLEM:
An office of 20 workers received N queries. Each worker must solve the same number of queries, and the number of answered queries should be maximum.
How many queries will remain unsolved?
EXPLANATION:
If each person solves x queries, the total number of queries answered will be 20x, and the unanswered queries will be N - 20x.
We want to find the smallest possible value of N - 20x across all x such that 20x \leq N.
Notice that this is simply the remainder when N is divided by 20.
However, N can be an extremely large number, so we need to deal with it appropriately — in a language like C++, you cannot just print N\% 20 because N itself is too large to be stored in any inbuilt data type.
Instead, notice that it’s enough to keep the last 2 digits of N.
That is, the remainder when N is divided by 20 is the same as the remainder when the last two digits of N are divided by 20 (this is true because 100 is divisible by 20).
For example, 1256\% 20 = 16 = 56\%20.
So, read N as a string, then take only its last two digits and find the remainder when they are divided by 20; that’s the answer.
Alternately, you can use a language that does support such large numbers, such as Python or Java.
TIME COMPLEXITY
\mathcal{O}(|N|) per test case.
CODE:
Editorialist's code (Python)
for _ in range(int(input())):
n = int(input())
print(n%20)
Editorialist's code (C++)
#include <iostream>
using namespace std;
int main() {
int t; cin >> t;
while (t--) {
string s; cin >> s;
s = "0" + s; // To ensure len(s) >= 2
s = s.substr(s.size() - 2); // Take the last 2 characters of s
int n = stoi(s); // Convert to integer
cout << n%20 << '\n';
}
}