National High School Programming Contest 2020 - Practice Contest

National High School
Programming Contest 2020 -

Practice Contest
https://toph.co/c/nhspc2020-practice-contest
Schedule
The contest will run for 36h0m0s.
Rules
You can use Bash 5.0, Brainf*ck, C# Mono 6.0, C++11 GCC 7.4, C++14 GCC 8.3, C++17 GCC
9.2, C11 GCC 9.2, Common Lisp SBCL 2.0, Erlang 22.3, Free Pascal 3.0, Go 1.13, Haskell
8.6, Java 1.8, Kotlin 1.1, Node.js 10.16, Perl 5.30, PHP 7.2, PyPy 7.1 (2.7), PyPy 7.1 (3.6),
Python 2.7, Python 3.7, and Ruby 2.6 in this contest.
Be fair, be honest. Plagiarism will result in disqualification. Judges’ decisions will be

final.
Notes
There are 11 challenges in this contest.
Please make sure this booklet contains all of the pages.
If you find any discrepencies between the printed copy and the problem statements in
Toph Arena, please rely on the later.
National High School Programming Contest 2020 - Practice Contest | Toph 2 of 25

A. Tom Is a Good Mentor
Today is the first day of the little mouse Jerry at school. Famous mathematician Tom is
his teacher. Today, Tom taught Jerry about numbers, powers, etc. After the discussion
session, Tom wanted to take a test of Jerry to evaluate how much he learned.
The problem that Tom asked Jerry to solve is simple. Tom will give him two integers N
and M. Jerry has to answer how many integer numbers X in the range [1,M] are there so
that the condition below will hold for all 1 ≤ Y < X and 1 ≤ Z < N, where Y and Z are
positive integers.
Jerry is clever. So he hired you to write a program to solve the problem for him.
Subtask 1: (10 Points)

6
1 ≤ T ≤ 10
6
1 ≤ N ≤ 10
M=N
Subtask 2: (30 points)

5
1 ≤ T ≤ 5 × 10
6
1 ≤ N ≤ 10
18
1 ≤ M≤ 10 and M is divisible by N.
Subtask 3: (60 points)

5
1 ≤ T ≤ 10
6
1 ≤ N ≤ 10
18
1 ≤ M ≤ 10 and M may not be divisible by N.
Input
First line of the input will contain a single integer T. T denotes the number of test cases.
Each of the next T lines will contain two positive integers N and M.
Output
For each case print “Case t: v” without quotations where t is the case number and v is
the required answer.

Samples
Input Output
5 Case 1: 1
1 1 Case 2: 1
2 2 Case 3: 2
3 3 Case 4: 2
4 4 Case 5: 4
5 5

B. Konami Code
The Konami code is a sequence of key/button presses that is implemented in many video
games to unlock hidden features (and often act as a cheat code).
The Konami Code was created by Kazuhisa Hashimoto, who was developing
the home port of the 1985 arcade game Gradius, a scrolling shooter released
on the NES in 1986. Finding the game too difficult to play through during
testing, he created a cheat code to give the player a full set of power-ups
(normally attained gradually throughout the game). — Wikipedia
The key sequence goes something like this:
↑↑↓↓←→←→BA
You could represent it as:
UUDDLRLRBA
Here, U represents the up key, D represents the down key, L represents the left key, R
represents the right key, and A and B represents the two action buttons found on NES
controllers.
The Konami code is more popular than you may think. It has been found in many non-
Konami video games, popular culture, and even in websites to unlock cool hidden
features. In fact, you would be surprised to know that this is implemented in many of
your favorite websites.
In this problem, you will have to write a program that will take a stream of key presses
(each key press represented with one of the following characters: U, D, L, R, A, and B)
and print the number of time the Konami code appears.
A Konami code is valid only if the following key press sequence occurs exactly in the
stream:
UUDDLRLRBA
Input
The input will contain a single line of string composed of these characters only: U, D, L, R,
A, and B. No other characters will appear in the string. The string will be at most 10000
characters in length.

Output
Print a single integer representing the number of times the Konami code appears in the
string.
Samples
Input Output
UUDDLRLRBA 1
Input Output
UUUUDDLRLRBADDLUUDDLRLRBARLRUUDDLRLRBABA 3

C. Palindrome and Queries
You’ll be given an array A of N strings containing lowercase english letters only and Q
queries. In each query, you have to find the length of the longest palindromic substring
which appears in at least L strings and at most R strings. If there is no such palindromic
substring, print 0.
A palindrome is a word which reads the same backward and forward, such as madam,
abba etc.
A substring is a string of character(s) that is contained in another string. For example,
abc has 6 substrings: a, ab, abc, b, bc, c.
A palindromic substring is a substring which reads the same backward and forward. For
example, taka has 4 unique palindromic substrings: t, a, k, aka.
Input
There will be multiple testcases. The first line of the input will contain an integer T, the
number of testcases. The first line of each case will contain two integers N and Q. Then
th
each of the next N lines will contain a string, i line will contain the string A . Then the
i
folowing Q lines will contain two integers each L and R, as described in the statement.
1 ≤ T≤ 15
5
1 ≤ N ≤ 10
5
1 ≤ Q ≤ 10
1≤L≤R≤N
5
1 ≤ |A | ≤ 10
i
6
Sum of length over all N strings per case will be ≤ 10
Subtask 1 (10 points):

1 ≤ T≤ 15, 1 ≤ N ≤ 10, 1 ≤ Q ≤ 100, 1 ≤ L ≤ R ≤ N, 1 ≤ |A | ≤ 20
i

1 ≤ T≤ 15, 1 ≤ N ≤ 100, 1 ≤ Q ≤ 10000, 1 ≤ L ≤ R ≤ N, 1 ≤ |A | ≤ 4100
i
Subtask 3 (60 points): Original constraints.

Output
th th
For each query, print 1 line, i line is the answer to the i query.
Samples
Input Output
1 6
3 6 6
aaac 6
aaabbbbbb 2
abbaaa 3
1 1 3
1 2
1 3
2 2
2 3
3 3
Dataset is huge, use faster I/O methods.

D. Crypto-Number
Walt and Gus have a great rivalry. Recently Gus has developed a cryptographic system.
Walt is trying to crack it. While trying, he has found out that there is an array C of
integers lying under the cryptographic system. Walt needs some information about the
array C.
Walt has developed an algorithm to generate random integers. He calls the random
integers generated by this algorithm as “Crypto-Number”. The algorithm is as follows:
1. Initially, the “Crypto-Number” is = 1.

2. Walt chooses two integers r, p - both greater than 1 randomly. Then he multiplies the
p
“Crypto-Number” with r .
3. The result of the multiplication is the new value of “Crypto-Number”.
4. He repeats the steps 2 and 3 for a random amount of time.
It is guaranteed that the generated “Crypto-Number” follows this constraint: 4 ≤ Crypto-

12
Number ≤ 10 .
Lets simulate the algorithm:
Step 1: The “Crypto-Number” = 1.

3
Step 2:Let, Walt chooses 81, 3 as r, p respectively. Result of multiplication = 1×81 =
531441.
Step 3: The new value of “Crypto-Number” = 531441.
If Walt repeats the steps 2 and 3 again:
Step 2: Let, Walt chooses 6, 5 as r, p respectively this time. Result of multiplication =
5
531441×6 = 4132485216.
Step 3: The new value of “Crypto-Number” = 4132485216.
And so on.
Now Walt wants to know, for a Crypto-Number k, how many integers are in the array C
such that k is completely divisible by them.
Input
The first line of the input contains an integer N, the size of the array C. The next line will
contain N space-separated integers C - the elements of the array C.
i
The next line contains an integer Q, the number of the queries. In each of the next Q
lines, there will be an integer k - the “Crypto-Number”.

Constraints:
6
1 ≤ N ≤ 10
12
1 ≤ C ≤ 10
i
4
1 ≤ Q ≤ 10
12
4 ≤ k ≤ 10
6
Subtask 1, For 10 points: 1 ≤ Q ≤ 10, 4 ≤ k ≤ 10
4 6
Subtask 2, For 30 points: 1 ≤ Q ≤ 10 , 4 ≤ k ≤ 10
Subtask 3, For 60 points: The original constraints.
Output
For each query, print in this format in a single line (without quotes): “Query x: y”, where
x is the number of the query and y is the number of the integers in the array C, which
integers can completely divide k.
Samples
Input Output
6 Query 1: 4
1 8 4 18 13 8 Query 2: 3
4 Query 3: 4
16 Query 4: 2
36
8
169
Notes:
In the first query, the integers in index 0, index 1, index 2 and index 5 in array C completely
divide 16. That is to say, the 4 integers in array C: 1, 8, 4, 8 completely divide 16.

E. Easy
This problem is very easy. As my mood is not so good, I will not elaborate the statement
unnecessarily. In this problem you will be given N sets. Each of them will contain some
distinct integer numbers. You have to form a new set using some chosen sets from given
sets in a way such that there is no common element among the chosen sets and the
number of total elements in the newly formed set is the maximum possible.
Input
In first line there will be an integer T, denoting the number of testcases.
In the first line of each test case there will be an integer N, denoting the number of sets.
Then each of the next N lines will contain some integers. The first integer is M , the
i
th
number of elements in i set. And then there will be M space separated distinct
i
th
integers A , A , ….A , …, A denoting the elements of the i set.
1 2 j M
i
6
summation of M over all testcases will not exceed 3×10
i
Constraints:
1 ≤ T ≤ 10
1 ≤ N ≤ 10
1 ≤ Mi ≤ 100
1 ≤ A ≤ 1000
j
Subtask 2 (90 Points):

1 ≤ T ≤ 10
1 ≤ N ≤ 20
1 ≤ M ≤ 100000
i
18
1 ≤ A ≤ 10
j
Output
For each test case, print the size of the newly formed set.

Samples
Input Output
1 2
3
2 1 2
2 2 3
2 1 3

F. Hello Choto Bondhu!
Hello Choto Bondhu,
2
Let’s play a game. I will give you a number n. You will have to tell me n . Okay, it may
2
seem difficult for you to calculate this huge number. So tell me the last digit of n . In
2
other words: (n % 10).
Input
The first line will contain T, which indicates test cases.
Here, 1 ≤ T ≤ 100.
Next T line will contain a number n.
Constraints:
9
Subtask 1, for 20 points, 1 ≤ n ≤ 10 .
100
Subtask 2, for 25 points, 1 ≤ n ≤ 10 .
100000
Subtask 3, for 55 points, 1 ≤ n ≤ 10
Output
Print T lines.
2
For each cases, print n % 10
Samples
Input Output
6 1
1 4
2 9
3 6
4 5
5 6
6

Input Output
When n = 1, ans = (n * n) % 10 = 1 % 10 = 1.
When n = 2, ans = (n * n) % 10 = 4 % 10 = 4.
When n = 3, ans = (n * n) % 10 = 9 % 10 = 9
When n = 4, ans = (n * n) % 10 = 16 % 10 = 6.
When n = 5, ans = (n * n) % 10 = 25 % 10 = 5.
When n = 6, ans = (n * n) % 10 = 36 % 10 = 6.

G. The Depressed Guy
There is a guy named “Lucky” who is depressed now. His friend Jack knows why he is
depressed. He has an array A which contains n numbers. He wants to find the largest
sub-array where the first and the last element are same.
So Jack wants to help lucky. But he doesn’t know anything about programming. That’s
why he comes to you as you are a great programmer in the world.
Find the size of the desired largest sub-array.
Note: a sub-array of an array composed from a contiguous block of the original

array’s elements.
Input
The first line of the input will contain one integers n (the size of the array).
The second line contains n numbers. (A ,A ,A ,……..,A )

1 2 3 n
3
Subtask 1 (10 points): 1 ≤ n ≤ 10 and 1 ≤ A ≤ 10
i
5 6
Subtask 2: (30 points): 1 ≤ n ≤ 2 * 10 and 1 ≤ A ≤ 10
i
5 18
Subtask 3: (60 points): 1 ≤ n ≤ 2 * 10 and 1 ≤ A ≤ 10
i
Output
Print the size of the desired largest sub-array.
Samples
Input Output
6 5
1 2 3 4 1 5

H. Birthday Gifts
Today is Luke’s birthday. Mr. Phil Dunphy (Luke’s father) has thrown a birthday party for
him and decided to buy some gifts for Luke. So he searched on the internet and
collected the following information.
There are total M different types of gift items in the city shops. The item types are
numbered from 1 to M. There are total N shops where these items can be found. But a
single shop may not contain all type of items. He has the list of items each shop has.
Mr. Phil has managed N assistants to help him. He will send each of his assistant to
exactly one shop. Also no shop should be assigned to more than one assistant. The i’th
assistant can buy at most C items from their assigned shop. They can not buy item from
i
any other shop except their assigned one. Each assistant can buy one instance of each
type of item. Also no two assistant can buy the same type of item.
Mr. Phil wants to assign shops to his assistants in such a way that he can buy maximum
number of gifts.
Input
First line contains an integer T, denoting the number of testcases.
In each test case, the first line contains two integers N and M.
The second line contains N integers C (0 ≤ C ≤ M) - denoting the capacity of items the
i i
i’th assistant can buy.
Then a binary matrix A of size (N x M) follows. The rows correspond to shops, and
columns to items. If A is 1, then the j’th item is available in the i’th shop, otherwise
ij
unavailable.
Scoring

1 ≤ T ≤ 15
N=2
1 ≤ M ≤ 100000

1≤T≤5

3≤N≤5
1 ≤ M ≤ 1000

1≤T≤5
3≤N≤5
1 ≤ M ≤ 100000
Output
For each test case, print the maximum number of items Mr. Phil can buy.
Samples
Input Output
1 4
3 5
1 1 2
10010
00110
01010
Input Output
1 6
4 6
1 1 2 2
000101
100011
000111
111100

I. Chow, Mo
Mo, the jumper has found an extraordinary tree in the woods. He absolutely loves it. He
already has made quite a few jumps from one branch to another. After a while, being
bored, he wonders what would be the minimum time to reach a vertex from another.
Formally, a tree is a connected graph with bidirectional edges and there exists only one
path between two vertices. The tree Mo found is rooted at and has vertices
numbered from to . Every vertex has some color . It takes him seconds to go
from vertex to if are adjacent. Also, Mo can jump from a vertex to vertex if
the colors of those two vertices are same, i.e. . These jumps take him
seconds.
For two vertices and , find out the minimum time needed for Mo to reach from .
Input
First line contains an integer .
There are test cases. For each test case —
• First line contains two integers , giving the number of vertices in the tree and
the time needed to move between adjacent vertices. The vertices are numbered
from to .
• Next line follows with integers, the th of which denotes the parent of
vertex .
• The next line contains integers, the th integer denotes the color of vertex , .
• The following line contains another integers, the th integer denotes . It is
guaranteed that for any , if then .
• The last line contains two integers and , the source and the destination.
Scoring
• ,
• ,
• ,

• .
• ,
• ,
• ,
• ,
• for every .
• ,
• ,
• ,
• .
Output
For each test case, output the minimum time needed in seconds to reach from .
Samples
Input Output
1 44
8 10
1 2 2 4 4 1 6
3 2 4 4 3 2 1 4
12 20 14 14 12 20 5 14
7 8

Input Output
Mo walks 7-1 in d=10 seconds. 1-2 in another 10 seconds. Then he goes to 3 via 2-3 causing
another 10 seconds. Then he jumps from vertex-3 to vertex-8 since they are the same
color. This jump takes him 14 seconds. Total time: 44 seconds.
Large input file. Please use faster I/O. (e.g. scanf(), printf() in C/C++)

J. Circle of Death
Abir is a school going boy, who loves math. Also, he loves to play with stones. Recently
he invented a game.
Abir has infinite amount of stones. He takes N of them and arranges them in a circle. He
marks them using numbers 1, 2, 3,… N. Stone 2 is next to stone number 1. And so on. As
the stones are arranged in a circle, after the stone number N there is the first stone with
stone number 1. He calls this the Circle of Death.
Now he takes out every second stone from the circle of death until there is only one
stone left in the circle. For example, if he starts with 5 stones, he takes out the stones in
the following order: First he skips the 1st stone and throws out the 2nd stone. Then he
skips the 3rd stone and he throws out 4th stone. Then he skips the 5th stone and throws
out the 1st stone. After this process, the only stone that was not thrown out is the stone
number 3. Then he arranges another circle of death with 3 stones (as 3 was the number
of only stone that was left in the last circle). And he again identifies the stone as 1, 2 and
3. Then he again throws away every second stone from the circle of death. The throwing
process happens as this: 2 -> 1. And again 3 is the last stone that was not thrown out in
this game. As the id of the stone that was left is the same as the number of stones he
started with, he ends his game. Then he announces 3 as his favorite number.
To be precise, at first he takes N stones, and arranges them in a circle. Then he throws
out every second stone in the circle until there is only one stone in the circle. If x is the
1
id of last stone that is not thrown out, he first checks if x is the number of stones the
1
circle had before he began throwing out the stones (in this case, the number is N). So he
checks if x = N. If the both the numbers are equal, then he stops his game and decides
1
that x is his favorite number. If the numbers are not equal he arranges x stones in a
1 1
different new circle, and again, throws every second stone out. Then if the last stone
that was not thrown out is x , then he again checks if the number x is the number of
2 2
stones he had in this circle. He had x stones before this round started. So he checks if x
1
= x . If the numbers are equal, he stops his game, and decides that x is his favorite
1 2 2
number. Otherwise he continues the game with x stones. The game goes on like this
2
until the result of a game starting with x stones ends with a stone with id x left. Then
i i
Abir decides that x is his favorite number.
i
Initially, Abir started playing with N stones in a circle. After finishing his game, he found
that x is his favorite number. Seeing this, his best friend Nabil also wants x to be his

favorite number. He thought of the following question, How many different integers
K
with value L are there, between 1 and 2 - 1(inclusive) such that if I played the game with
L stones, I can also decide x as my favorite number just like Abir’s? Can you help him? As
9
the number can be very large, print it modulo (10 + 7)
Input
The first line will contain T. The number of test cases. Each of the next T lines will
contain 2 integers each. Each line will contain the value of N and K separated with a
space.
Constraints
1 ≤ T ≤ 10
18
1 ≤ N ≤ 10
1 ≤ K ≤ 100000
Subtask 1(10 Points)

1≤T≤5
1 ≤ N ≤ 50
1≤K≤5

1 ≤ T ≤ 10
1 ≤ N ≤ 1000000
1≤K≤5

1≤T≤5
1 ≤ N ≤ 10000000
1 ≤ K ≤ 20

Original Constraints
Output
For each of the test cases, you have to output the number of different integers with
K
value L that is between 1 and 2 - 1 inclusive such that if the game was played with L
stones, the favorite number will be same as the game is played with N stones. Print the
9
answer modulo (10 + 7).

Samples
Input Output
2 6
10 4 4
11 4

K. A Girl Has No Name
“Joffrey… Cersei… Ilyn Payne… the Houn..” - Arya Stark
Garden of Bones, Game of Thrones S02E04
Arya Stark was one of the crucial member of the Stark family in the HBO’s epic fantasy
television series Game of Thrones.
Arya had a kill list consisting of a few people who had contributed to making her life
stressful. But she is so young that she can not kill a man yet. She decided to go to
Braavos to adopt some magical skills.
Arya’s tutor gave him a huge task. She had to run a magic code in her computer.
func (L, R){

sum = 0
for (i = L; i <= R; i++){
sum += score (i)
}
return sum
}
Where,
score (N){
A = number of unique non zero digits of N
B = number of unique digits of N which evenly divides N
return power (B, A) //B to the power A
}
She ran the code on her computer smoothly by some magical power. Can you do the
same?
Input
Input starts with an integer T, denoting the number of test cases. Each case starts with a
line containing two integers L R.
Scoring

1 ≤ T ≤ 10
7
1 ≤ L ≤ R ≤ 10

1≤T≤5
14
1 ≤ L ≤ R ≤ 10

T=1
18
1 ≤ L ≤ R ≤ 10
Output
9
For each case, print func (L, R) modulo (10 + 7)
Samples
Input Output
3 10
1 10 10
12 15 2522331
20 100000

National High School Programming Contest 2020 - Practice Contest

Uploaded by

Copyright:

Available Formats

National High School Programming Contest 2020 - Practice Contest

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

National High School Programming Contest 2020 - Practice Contest

Uploaded by

Copyright:

Available Formats

National High School

Programming Contest 2020 -

Be fair, be honest. Plagiarism will result in disqualiﬁcation. Judges’ decisions will be

Please make sure this booklet contains all of the pages.

National High School Programming Contest 2020 - Practice Contest | Toph 2 of 25

Subtask 1: (10 Points)

Subtask 2: (30 points)

Subtask 3: (60 points)

National High School Programming Contest 2020 - Practice Contest | Toph 3 of 25

National High School Programming Contest 2020 - Practice Contest | Toph 4 of 25

The key sequence goes something like this:

You could represent it as:

National High School Programming Contest 2020 - Practice Contest | Toph 5 of 25

National High School Programming Contest 2020 - Practice Contest | Toph 6 of 25

Subtask 1 (10 points):

Subtask 2 (30 points):

Subtask 3 (60 points): Original constraints.

National High School Programming Contest 2020 - Practice Contest | Toph 7 of 25

Dataset is huge, use faster I/O methods.

National High School Programming Contest 2020 - Practice Contest | Toph 8 of 25

1. Initially, the “Crypto-Number” is = 1.

It is guaranteed that the generated “Crypto-Number” follows this constraint: 4 ≤ Crypto-

Lets simulate the algorithm:

Step 1: The “Crypto-Number” = 1.

National High School Programming Contest 2020 - Practice Contest | Toph 9 of 25

Subtask 3, For 60 points: The original constraints.

National High School Programming Contest 2020 - Practice Contest | Toph 10 of 25

Subtask 2 (90 Points):

National High School Programming Contest 2020 - Practice Contest | Toph 11 of 25

National High School Programming Contest 2020 - Practice Contest | Toph 12 of 25

Next T line will contain a number n.

National High School Programming Contest 2020 - Practice Contest | Toph 13 of 25

National High School Programming Contest 2020 - Practice Contest | Toph 14 of 25

Find the size of the desired largest sub-array.

Note: a sub-array of an array composed from a contiguous block of the original

The second line contains n numbers. (A ,A ,A ,……..,A )

National High School Programming Contest 2020 - Practice Contest | Toph 15 of 25

Subtask 1 (20 Points):

Subtask 2 (40 Points):

National High School Programming Contest 2020 - Practice Contest | Toph 16 of 25

Subtask 3 (40 Points):

National High School Programming Contest 2020 - Practice Contest | Toph 17 of 25

There are test cases. For each test case —

Subtask 1 (20 points):

National High School Programming Contest 2020 - Practice Contest | Toph 18 of 25

Subtask 2 (30 points):

Subtask 3 (50 points):

National High School Programming Contest 2020 - Practice Contest | Toph 19 of 25

National High School Programming Contest 2020 - Practice Contest | Toph 20 of 25

National High School Programming Contest 2020 - Practice Contest | Toph 21 of 25

Subtask 1(10 Points)

Subtask 2(20 Points)

Subtask 3(30 Points)

Subtask 4(40 Points)

National High School Programming Contest 2020 - Practice Contest | Toph 22 of 25

National High School Programming Contest 2020 - Practice Contest | Toph 23 of 25

Garden of Bones, Game of Thrones S02E04

func (L, R){