International Collegiate Programming Contest

The 2023 ACPCTeensOnline Collegiate Programming Contest

Online
July 2023

The International Collegiate Programming Contest

Sponsored by ICPC Foundation

The 2023 ACPCTeensOnline Collegiate

Programming Contest
(Contest Problems)

Online
July 2023
 SCPC / ECPC Teens Online Qualification Contest
Online, July 17th 2023

Problem A. SCPCTeens
Input file: standard input
Output file: standard output
Balloon Color: Red

“I hate common mistakes.“

— Grouchy Smurf

SCP CT eens is not the name of this contest, but it’s SCP C T eens.
This is a common mistake that every one falls into, there is a space between SCP C and T eens.
given a string of size excatly 9 characters, which represents the wrong name of some contest, correct it.
(by adding a space between the 4th and the 5th character).

Input
one line contains a string of excatly 9 characters,(the first five characters are Upper case English letters,
and the remaining four characters are lower case English letters). represents the wrong name of the contest.

Output
Output one line contains a string of the correct name of the contest name for the input.

Examples
standard input standard output
SCPCTeens SCPC Teens
ECPCTeens ECPC Teens
SMRFSecpc SMRF Secpc

Page 1 of 17
 SCPC / ECPC Teens Online Qualification Contest
Online, July 17th 2023

Problem B. SCPCteensQual2024
Input file: standard input
Output file: standard output
Balloon Color: Blue

“I hate strings.“
— Grouchy Smurf

Given a string of length 17, represent a wrong name, find the value of it’s wrongness. the value of the
wrongness of a string s.
let the string T = SCP CteensQual2024. The wrongness of a string S is the number of indices i from 1
to 17 such that S[i] 6= T [i].
for example the wrong name SCP CteensQual2023 has 2 as the wrongness value. (for i = 3 : S[i] = ‘t’,
while T [i] = ‘T’. and for i = 17 S[i] = ‘3’, while T [i] = ‘4’).

Input
You are given a string with length exactly 17 that may contains lowercase or uppercase or numbers.

Output
Print the wrongness value of the given string.

Examples
standard input standard output
SCPCTeensQual2024 0
SCpctEEnsqUAL2023 10

Page 2 of 17
 SCPC / ECPC Teens Online Qualification Contest
Online, July 17th 2023

Problem C. Qualifying Teams

Input file: standard input
Output file: standard output
Balloon Color: Yellow

“I hate qualifications.“
— Grouchy Smurf

There are N teams participate in this contest.

There are three types of teams for this contests, (Syrian Teens, Egyption Teens, Unofficial Teens).
The process of determining which teams will pass the contest: The judges start from the first team ending
with the last team on the scoreboard, and they follow these rules:

1. If the team is a Syrian Teens team, he will pass the contest if the number of teams who have already
passed is still lower than A+B.

2. If the team is an Egyptian Teens team, he will pass the contest only if the number of teams who
have already passed is currently lower than A+B and the number of Egyptian Teens teams who
have already passed is still lower than B.

3. An Unofficial team cannot pass at all.

A string S of length N is given, indicating the final scoreboard of this contest, if the i-th character is ‘S’,
this means that the team ranked i-th on the contest is a Syrian team, if the i-th character is ‘E’, this
means that the team ranked i-th on the contest is an Egyption team, if the i-th character is ‘U’, this
means that the team ranked i-th on the contest is an Unofficial team.
Print N lines each line is either ‘Yes’ or ‘No’, ‘Yes’ if the i-th team passes the Qualification contest, ‘No’
otherwise.

Input
The first line contain three integers N,A,B ( 2 ≤ N ≤ 105 , 1 ≤ A, B ≤ 105 ).
The second line contain a string of length N that may contains ‘E’, ‘S’ or ‘U’.
It is guaranteed that A + B ≤ N .

Output
Print N lines each line is either ‘Yes’ or ‘No’, ‘Yes’ if the i-th team passes the Qualification contest, ‘No’
otherwise.

Page 3 of 17
 SCPC / ECPC Teens Online Qualification Contest
Online, July 17th 2023

Examples
standard input standard output
5 1 2 Yes
ESUES Yes
No
Yes
No
7 3 2 No
UUSSEEE No
Yes
Yes
Yes
Yes
No

Page 4 of 17
 SCPC / ECPC Teens Online Qualification Contest
Online, July 17th 2023

Problem D. Smurfy teams

Input file: standard input
Output file: standard output
Balloon Color: White

“I hate contests.“
— Grouchy Smurf

There are N contestants who wants to participate in this contest, but as you may already know this
contest is for teams of two contestants.
So the contestants has to form teams in order to participate. the contestants matching process is really
hard, So we are going to automate it.
A team is considered smurf y if each one of its contestant wants to form a team with the other one.
Count the numebr of smurf y teams that can be formed.

Input
The fist line contain integer N (2<= N <= 1e5).
The second line contain an array of length N and each integer (1<=a[i]<=N, a[i] != i), means that the
contestant number i wants to form a team with contestant number a[i].

Output
Print the number of smurfy teams.

Examples
standard input standard output
4 2
2 1 4 3
3 0
3 1 2

Page 5 of 17
 SCPC / ECPC Teens Online Qualification Contest
Online, July 17th 2023

Problem E. A Damsel In Distress

Input file: standard input
Output file: standard output
Balloon Color: Black

“I hate passwords.”
— Grouchy Smurf

Enamored Smurf has been in love with Smurfette ever since her arrival. He dreams about her, carves her
name in trees, and pulls the petals off daisies, reciting “She loves me, she loves me not ...” When she loves
him not, he cries all night.
Papa Smurf is telling a story about him to the Smurfs: 00 Enamored Smurf recently found out that Gargamel
got hold of Smurfette (Again...) and is keeping her in his cage in order to turn her into gold.
Enamored Smurf then (together with the rest of the Smurfs) went on to her rescue. Their plan was to
lure Gargamel away from the cage and let Enamored Smurf, Hefty Smurf and Handy Smurf proceed to
open the cage and rescue Smurfette.
But, it turns out that the cage is locked with a mechanical 3-digit password. Handy Smurf deduced that
the password must be a sub-sequence of the string S that is near the cage.
The hhree smurfs are going to create the 3-digits password from it as following:
Enamored Smurf is going to choose index i ( 1 ≤ i ≤ N − 2 ), then Smurf Handy is going to choose index
j ( i + 1 ≤ j ≤ N − 1 ), then Smurf Hefty is going to choose index k ( j + 1 ≤ k ≤ N ).
Then the password is Si Sj Sk .
And they proceeded to find the correct password and save Smurfette.00
After the story is over Brainy Smurf wondered how they found the password so quickly. And decide to
count the number of possible distinct passwords that the three smurfs could’ve created using the string S
from Papa’s Story. And you decided to help him.

Input
You are given a String S ( 3 ≤ |S| ≤ 105 ), the string S from Papa’s Story.

Output
Output one integer: the number of possible distinct passwords.

Examples
standard input standard output
000 1
000111 4

Page 6 of 17
 SCPC / ECPC Teens Online Qualification Contest
Online, July 17th 2023

Problem F. A Battle Over Smurfette (Resli’s version)

Input file: standard input
Output file: standard output
Balloon Color: Green

“I hate romance.”
— Grouchy Smurf

Smurfette is the main protagonist and a female Smurf Before the smurflings created Sassette, Smurfette
was the only female smurf in the Smurf village. Most of the time Smurfette is portrayed as an object of
admiration of many other Smurfs, since she is the only female Smurf consistently in the village. She is
usually hopeless in times of danger and sometimes thinks she knows it all, yet has a caring side as well.
there are N Smurfs that are trying to win Smurfette’s heart. So they decided to play a game to decide who
is going to win her heart. They would stand in a line from 1 to n and let Papa Smurf choose two
random consecutive Smurfs that battle each other and the loser steps out of the line. this
process will repeat N − 1 times, until only one Smurf remains and be declared the winner.
Papa Smurf knows the winner of any two Smurfs battle. And he wonders: how many smurf
have a chance of winning?

Input
You are given an integer N (2 ≤ N ≤ 100) the number of Smurfs. Then a matrix A that
consists of N strings follow: each string Ai has length N and consist only of zeros and ones.
the i-th Smurf wins against j-th Smurf if and only if Ai,j = 1. it is guaranteed that Ai,j = Aj,i
and Ai,i = 0

Output
Output a single integer. the number of smurfs that have a chance of winning Smurfette
heart.

Examples
standard input standard output
4 1
0000
1010
1000
1110
4 2
0101
0010
1000
0110
3 2
010
001
100

Page 7 of 17
 SCPC / ECPC Teens Online Qualification Contest
Online, July 17th 2023

Problem G. Smurfs’ Village Trips

Input file: standard input
Output file: standard output
Balloon Color: Cyan

I hate trips.
— Grouchy Smurf

Papa Smurf is the leader and elder of the Smurfs. He decided to start a series of trips around the village
to raise moral of the smurf. All the smurfs were happy because of this announcement. Well..., except for
Lazy Smurf. Who then proceeded to measure the of sum distances of all possible trips inside the Smurfs’
Village. The Village has N sights and N − 1 bidirectional roads connecting them, the i-th of them has a
length of li . A trip plan is a permutation p of those sites. where the Smurfs go from site pi to site pi+1
(for i ≤ N − 1) using the shortest path between them. Lazy smurf couldn’t be bothered to calculate such
a huge number. so he asks you to do it. Since it is a very big number he asks you to calculate it modulo
109 + 7. (since he is too lazy to read the whole number)

Input
You are given a single integer N (1 ≤ N ≤ 105 ) the number of sites in the village. then N - 1 lines follow.
The i-th of which has three integers: ai , bi , li (1 ≤ ai , bi ≤ N , 1 ≤ li ≤ 109 ). which represent a road that
connects site ai with site bi and has a length li .

Output
Output a single integer X: the sum distances of all possible trips inside the Smurfs’ Village modulo 109 +7.

Examples
standard input standard output
2 4
1 2 2
4 276
1 2 3
2 3 2
3 4 2

Page 8 of 17
 SCPC / ECPC Teens Online Qualification Contest
Online, July 17th 2023

Problem H. Pigeon Rides

Input file: standard input
Output file: standard output
Balloon Color: Bronze

I hate pigeons.
— Grouchy Smurf

Handy Smurf is the handyman of the Smurfs. He helps fix things in the village and is known for his
amazing technological inventions. Today he has invented a way to fly around the world. It’s called a
Pigeon Ride! thanks to the light weight of the Smurfs. a Pigeon is able to fly one Smurf across the planet
and back. Not only that. But a pigeon can fly exactly two Smurfs to the sky (by installing another seat
which weighs exactly 1), if their combined wight does not exceed C (with the extra seat). there are N
Smurfs that want to travel to Smurfy Grove. each Smurf has a weight wi . Since pigeons are costly. Handy
Smurf asks you to find the minimum number of pigeons needed to transport all N Smurfs using his Pigeon
Rides.

Input
You are given a single integer T which represent the number of test cases. For each test case: You are given
two integers N and C (1 ≤ N ≤ 105 , 1 ≤ C ≤ 109 ). then the next line has N integers wi (1 ≤ wi ≤ 109 ).
the weight of the i-th Smurf.

Output
for each test case output a single integer. the minimum number of pigeons needed to transport all N
Smurfs to the Smurfy Grove.

Example
standard input standard output
2 2
3 5 2
1 2 4
4 12
1 2 3 2

Page 9 of 17
 SCPC / ECPC Teens Online Qualification Contest
Online, July 17th 2023

Problem I. A Battle Over Smurfette (Shadi’s version)

Input file: standard input
Output file: standard output
Balloon Color: Seliver

I hate romance.
— Grouchy Smurf

Smurfette is the main protagonist and a female Smurf Before the smurflings created Sassette, Smurfette
was the only female smurf in the Smurf village. Most of the time Smurfette is portrayed as an object of
admiration of many other Smurfs, since she is the only female Smurf consistently in the village. She is
usually hopeless in times of danger and sometimes thinks she knows it all, yet has a caring side as well.
there are N Smurfs that are trying to win Smurfette’s heart. So they decided to play a game to decide
who is going to win her heart. They would stand randomly in a line and let Papa Smurf choose two
random consecutive Smurfs that battle each other and the loser steps out of the line. this
process will repeat N − 1 times, until only one Smurf remains and be declared the winner.
Papa Smurf knows the winner of any two Smurfs battle. And he wonders: for all different
permutations of the line the smurfs could be standing, how many smurf have a chance of
winning?

Input
You are given an integer N (2 ≤ N ≤ 100) the number of Smurfs. Then a matrix A that
consists of N strings follow: each string Ai has length N and consist only of zeros and ones.
the i-th Smurf wins against j-th Smurf if and only if Ai,j = 1. it is guaranteed that Ai,j = Aj,i
and Ai,i = 0

Output
Output a single integer. the number of smurfs that have a chance of winning Smurfette
heart.

Examples
standard input standard output
4 1
0000
1010
1000
1110
4 4
0101
0010
1000
0110

Page 10 of 17
 SCPC / ECPC Teens Online Qualification Contest
Online, July 17th 2023

Problem J. Smurfy Voyage

Input file: standard input
Output file: standard output
Balloon Color: Gold

I hate bridges.
— Grouchy Smurf

Brainy Smurf considers himself the most intelligent Smurf in the village and an expert on everything,
although his actual knowledge is questionable at best; often, his attempts to help in a given situation
lead to even more problems. His vices aside, Brainy is a good, loyal Smurf who can be counted on when
the need arises, and more than once – without thinking about it – ends up doing the right thing. Brainy
Smurf is planning An trip to New York City. to do so, he must travel through the sea to get there. But, he
can’t go in one go since the trip will take a lot of time and he needs to rest. So, he decided to visit some
islands on his way first and connect them with bridges as he moves along them (to help other Smurfs do
the trip as well). the sea has N islands that he may want to visit. initially there is no bridges connecting
the islands.
he is going off a trip that consists of M islands to visit in order, and during the plan he is going to add
on-way bridges (if none exists). For example, let’s suppose that he is currently on island number x and
the next island to visit in his trip is city y. If there is no directed one-way road from x to y he will add
it to the graph. he will also connect the island 1 (which is the island of the Smurfs) with the first island
he visits using a one way bridge. (if they are not the same, and if there is no bridge going from the last
island to the first island).
He also wants for the Smurfs to visit all islands starting from any island (since there are some beautiful
islands along the way). So, after the trip ends. He will be satisfied if and only if he can travel from any
city on his trip to any other city on his trip by using one or more one-way bridges.
Brainy Smurf told Hefty Smurf of his plan. So Hefty Smurf asked him the number of possible travel plan
of M islands (order of islands there is so that you will be satisfied after the trip ends).
Note that the trip may contains the same island any number of times (it’s also possible to have the same
islands listed any number of times in a row in his trip).
Wanting to answer his question (and not wanting the Smurfs clobbering him with a club off screen). He
asks for your help.
Find the number possible of travel plan modulo 109 + 7.

Input
You are given a single integer T . The number of test cases. Then test cases follow: each test case consist
of two integer N, M (2 ≤ N ≤ 100, 1 ≤ M ≤ 100). the number of islands and the number of islands in
the trip.

Output
For each test case output a single integer: number of travel plan modulo 109 + 7.

Page 11 of 17
 SCPC / ECPC Teens Online Qualification Contest
Online, July 17th 2023

Example
standard input standard output
3 2
3 3 96
4 5 124616832
12 23

Page 12 of 17
 SCPC / ECPC Teens Online Qualification Contest
Online, July 17th 2023

Problem K. Fishing Day

Input file: standard input
Output file: standard output
Balloon Color: Purple

I hate fishing.
— Grouchy Smurf

Greedy is an exceptionally gluttonous Smurf. He has an exceptional interest in eating cakes and other
pastry. Greedy usually cannot seem to help himself and he is often chased by Chef Smurf for stealing snacks
and food. Chef Smurf is the Smurf village’s chef. He knows dozens of recipes and cooks many dishes. He
always wears his toque blanche (white chef’s hat). Today Chef Smurf and Greedy Smurf decided to settle
their differences. And cook a delicious meal for the villages, a meal so large that Greedy Smurf can’t finish
it on his own. So Chef Smurf asks Greedy Smurf to fetch him a large number of fish from the river. Jokey
Smurf is the village prankster. as a prank he decided to put all the fishes in his buckets and will return
them to the river later to surprise Greedy Smurf.
the river is of length N . Initially the river is empty. the river can be considered as a segment with integer
coordinates from [0, N − 1].
There is also a special type of fish called Smurfy Fish that can lives in the river.
Those Smurfy Fishs always swim along the river, and their speed is 1 unit per second, and it’s direction
is one of two options (left or right).
The movement of a fish is defined as follows: let the position of the fish be x ≤ N − 2 on time t and it’s
direction is right –> then at the time t + 1 it’s position will be x + 1, unless it’s position is N − 1 then
the fish will change direction.
let the position of the fish be x > 0 on time t and it’s direction is left <– then at the time t + 1 it’s
position will be x − 1, unless it’s position is 0 then the fish will change direction.
Greedy Smurf notices that something is wrong with the fishes and decided to find out what. To do so, he
must process Q queries.
You know of Jokey Smurf’s prank. But you decided to help Greedy get his fishes. So, you will answer the
queries for him.

Input
You are given two integers N, Q (2 ≤ N ≤ 105 , 1 ≤ Q ≤ 105 ). The length of the river, and the number of
queries.
The i-th query is one of the following three types:

1. ”L” ti Yi Zi (Jokey adds Zi fishes in the position from Yi and their direction is to the left at time
ti ). (0 ≤ Yi ≤ N − 1, 1 ≤ ti , Zi ≤ 108 ).

2. ”R” ti Yi Zi (Jokey adds Zi fishes in the position Yi and their direction is to the right at time ti ).
(0 ≤ Yi ≤ N − 1, 1 ≤ ti , Zi ≤ 108 ).

3. ”C” ti Li Ri (count the number of fishes in the range [Li , Ri ] at time ti ). (0 ≤ Li < Ri ≤ N − 1,
1 ≤ ti ≤ 108 ).

it is guaranteed For all queries such that i > 1 that ti−1 < ti .

Page 13 of 17
 SCPC / ECPC Teens Online Qualification Contest
Online, July 17th 2023

Output
For each query of type ”C” output one integer: The answer to the query.

Examples
standard input standard output
10 3 2
R 1 2 1
L 2 5 1
C 3 4 5
5 4 2
L 1 1 2 4
R 2 4 2
C 3 2 4
C 5 2 4
10 10 0
C 1 3 8 0
L 2 1 2 2
R 3 7 3 10
C 4 1 5
C 5 0 6
L 6 2 3
R 7 3 5
C 8 2 9
R 9 7 1
L 10 6 1
14 15 0
R 1 6 4 0
C 2 0 4 15
R 6 3 8 22
L 9 0 8 33
L 11 1 3 22
R 18 8 7 40
L 19 3 3
C 22 5 7
C 25 2 5
C 30 4 7
R 31 10 7
C 39 1 10
C 41 4 10
C 47 1 12
R 49 8 4

Page 14 of 17
 SCPC / ECPC Teens Online Qualification Contest
Online, July 17th 2023

Problem L. Hefty Smurf

Input file: standard input
Output file: standard output
Balloon Color: Pink

I hate lifting.
— Grouchy Smurf

Hefty Smurf has incredible strength and often is seen doing a lot of the heavy work in the village. He also
has a tattoo on his right arm (or sometimes both of his arms) of a red heart with an arrow through it. His
favorite activity is lifting weights and doing other forms of exercise, and is often the one to kick Brainy
out of the village whenever he is boasting. Hefty takes pride in being tough, sometimes doing it just for
attention.
he has challenged himself to lift N barbell plates numbered from 1 to N , and the weight of the i-th plate
is Wi .
Hefty Smurf noticed that he can lift any number of barbell plates if the following condition is held:

• For any digit from 0 to 9, the digit must not occur in the weights more than twice.

For example: Hefty Smurf can lift plates with weights [11, 23, 2], but he can’t lift [10, 999] or [99, 9, 10]
because the digit 9 repeated 3 times.
Interested to test his limits. Hefty Smurf is wondering what is the maximum weight that he can lift, you
want to know as well. So you decided to help him find it out.

Input
The first line contains the number of test cases T (1 ≤ T ≤ 100). A description of the test cases follows.
The first line of each test case contains one integer N (1 ≤ N ≤ 100) — the number of barbell plates in
the gym
The second line contains N integers W1 , W2 , .., WN (1 ≤ Wi ≤ 1016 ) — the wights of the barbell plates
It is guaranteed that the sum of N over all test cases does not exceed 100

Output
For each test case, output the maximum weight that Hefty Smurf can lift.

Example
standard input standard output
3 36
3 0
11 23 2 195
1
222
3
97 98 99

Page 15 of 17
 SCPC / ECPC Teens Online Qualification Contest
Online, July 17th 2023

Problem M. Fearsome Prankster

Input file: standard input
Output file: standard output
Balloon Color: Olive

I hate pranks.
— Grouchy Smurf

Scaredy Smurf easily gets scared by anything whether it is a small insect or the noise of a storm. He is
often teased by the other Smurfs because of this.
Today, Jokey Smurf is going to play at most M pranks on him. and he wants to scare him as much
as possible. To help him measure how much he scared Scaredy Smurf he created an imaginary scoring
system using a unit called “Jokey Points”. So that each time he pranks Scaredy Smurf he can measure
how effective his prank was by the number of Jokey Points he got from that prank. He has N kinds of
pranks that he can try any number he wants as long as he does not go over M pranks in total. However,
eventually, even Scaredy Smurf will grow tired of his pranks if he repeats them often. therefore, Jokey
Smurf will get Vi − Di ∗ (ti − 1) Jokey Points if he tries to do the i-th prank for the ti -th time.
Since you are interested in Jokey Smurf’s scoring sytem, you decided to help him get the maximum
amount of Jokey Points.

Input
You are given two integer N and M ( 1 ≤ N ≤ 105 , 0 ≤ M ≤ 109 ). the number different of prank Jokey
Smurf has. And the maximum number of Pranks he can do. and then you are given two arrays V and D.
Both of length N . which represent the Vi and Di of the i-th kind of prank ( 1 ≤ Vi , Di ≤ 108 ).

Output
Output a single integer the maximum amount of Jokey Points Jokey can have if he chooses his pranks
optimally.

Example
standard input standard output
3 5 27
5 7 9
2 4 6

Page 16 of 17
 SCPC / ECPC Teens Online Qualification Contest
Online, July 17th 2023

Problem N. Dopey Sumation

Input file: standard input
Output file: standard output
Balloon Color: Orange

“I hate sums.”
— Grouchy Smurf

Dopey Smurf is the least intelligent among the Smurfs. Other Smurfs asked him to sum two number A
and B. But, he couldn’t answer. You feel bad Dopey Smurf. So you’re going to calculate A + B for him.

Input
You are given two number A,B ( 1 ≤ A, B ≤ 105 ).

Output
Print one integer: The answer to A + B.

Example
standard input standard output
1 1 2

Page 17 of 17