EPANLNK - Editorial


Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Authors: d_k_7386
Tester: tabr
Editorialist: iceknight1093






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?


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.


\mathcal{O}(|N|) per test case.


Editorialist's code (Python)
for _ in range(int(input())):
    n = int(input())
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';