Nordic Collegiate Programming Contest

NCPC 2020

November 7, 2020

Problems
A Array of Discord
B Big Brother
C Coin Stacks
D Dams in Distress
E Exhaustive Experiment
F Film Critics
G Gig Combinatorics
H Hiring and Firing
I Infection Estimation
J Joining Flows
K Keep Calm And Carry Off
L Language Survey
M Methodic Multiplication

Do not open before the contest has started.

Advice, hints, and general information
• The problems are not sorted by difficulty.
• Your solution programs must read input from standard input (e.g. System.in in Java or
cin in C++) and write output to standard output (e.g. System.out in Java or cout
in C++). For further details and examples, please refer to the documentation in the help
pages for your favorite language on Kattis.
• For information about which compiler flags and versions are used, please refer to the
documentation in the help pages for your favorite language on Kattis.
• Your submissions will be run multiple times, on several different inputs. If your submission
is incorrect, the error message you get will be the error exhibited on the first input on which
you failed. E.g., if your instance is prone to crash but also incorrect, your submission
may be judged as either “Wrong Answer” or “Run Time Error”, depending on which is
discovered first. The inputs for a problem will always be tested in the same order.
• If you think some problem is ambiguous or underspecified, you may ask the judges for a
clarification request through the Kattis system. The most likely response is “No comment,
read problem statement”, indicating that the answer can be deduced by carefully reading
the problem statement or by checking the sample test cases given in the problem, or that
the answer to the question is simply irrelevant to solving the problem.
• In general we are lenient with small formatting errors in the output, in particular whitespace
errors within reason, and upper/lower case errors are often (but not always) ignored. But
not printing any spaces at all (e.g. missing the space in the string “1 2” so that it becomes
“12”) is typically not accepted. The safest way to get accepted is to follow the output
format exactly.
• For problems with floating point output, we only require that your output is correct up to
some error tolerance. For example, if the problem requires the output to be within either
absolute or relative error of 10−4 , this means that
– If the correct answer is 0.05, any answer between 0.0499 and .0501 will be accepted.
– If the correct answer is 500, any answer between 499.95 and 500.05 will be accepted.
Any reasonable format for floating point numbers is acceptable. For instance, “17.000000”,
“0.17e2”, and “17” are all acceptable ways of formatting the number 17. For the definition
of reasonable, please use your common sense.
• An interactive problem is a problem where your program will be communicating back
and forth with a judge program, e.g. playing a game against an opponent.
In these problems, you still read from standard input and write to standard output just
as in other problems, but for these problems you need to also make sure to flush your
output after sending a message to the judge program (otherwise it may just be placed in
an internal buffer in your program and not sent). If you are using output streams in Java
or C++ this can be done by calling the .flush() method of your output stream.
For interactive problems we sometimes also provide a simple testing tool program that you
can use to test-run your solution. When available you will find this tool under “Download”
to the right of the problem statement on the page for the problem in Kattis. Note that
this tool is generally only meant to facilitate basic testing of your program, and that your
solution might not necessarily be tested in the same way when submitted.
 Problem A
Array of Discord
Time limit: 0 seconds
Once upon a time, high up on Mount Olympus, it came to pass that
the gods held a competition to see who among them was the best at
sorting lists of integers. Eris, the goddess of discord, finds this terribly
boring and plans to add some mischief to the mix to make things more
fun. She will sabotage the answers of Zeus so that his list of numbers
is no longer sorted, which will no doubt be so embarrassing that he
becomes furious and starts a minor war.
Eris must be careful not to be discovered while performing her
sabotage, so she decides to only change a single digit in one of the Eris clip art from freesvg, public domain
numbers in Zeus’ answer. The resulting number may not have any
leading zeros (unless it becomes equal to zero in which case a single zero digit is allowed). Eris
can only replace a digit with another digit – adding or removing digits is not allowed.

Input
The first line of input contains n (2 ≤ n ≤ 100), the length of Zeus’ answer. The second line
contains n integers a1 , a2 , . . . , an (0 ≤ a1 ≤ a2 ≤ . . . ≤ an ≤ 1015 ), Zeus’ answer.

Output
If Eris can make the list not be sorted by changing a single digit of one of the numbers, then
output n integers b1 , . . . , bn , the resulting list of numbers after making the change. Otherwise,
output “impossible”. If there are many valid solutions, any one will be accepted.

Sample Input 1 Sample Output 1

3 2021 2020 2020
2020 2020 2020

Sample Input 2 Sample Output 2

2 impossible
1 9999999

Sample Input 3 Sample Output 3

4 1 42 4711 3876
1 42 4711 9876

NCPC 2020 Problem A: Array of Discord 1

This page is intentionally left blank.
 Problem B
Big Brother
Time limit: 0 seconds
You have come up with a new brilliant idea of automatically
keeping track of how much (or little) your employees are working
in the office: face recognition! By installing some advanced
CCTV cameras in the office you will be able to automatically
detect when the staff arrives or leaves, are taking breaks etc, thus
reducing the need for manual administrative work. No more
stamping clocks.
A good CCTV camera is expensive, so ideally you would only
use one. It would obviously have to be placed somewhere where
the entire office floor can be overlooked, so there are no walls Picture by mi_brami, public domain
blocking some dark corner of the floor where your workforce
might hide.
While looking at the floor map, which can be modelled as a simple polygon, you are not sure
if this is possible. Since the task is way above the paygrade of everyone else in the company you
will have to write the program figuring this out yourself. If it is possible, you also want to know
the area of the surface where the camera could be placed. See Figure B.1 for an example.

Figure B.1: Illustration of Sample Input 3. The blue shaded area in the middle indicates the
region where the camera can be placed.

Input
The first line of input contains an integer n (3 ≤ n ≤ 500 000), the number of vertices describing
the polygon representing the office floor. Then follow n lines containing the integer coordinates
x, y of the polygon in clockwise order (0 ≤ x, y ≤ 107 ).

Output
Output the area of the region of the map where a CCTV camera could be placed so that the rest
of the office can be observed. (If it is not possible to put the camera anywhere, this area is 0.)
The answer must be correct with a relative of at most 10−6 , or an absolute error of at most
0.1.

NCPC 2020 Problem B: Big Brother 3

Sample Input 1 Sample Output 1
8 1.0
0 0
0 1
1 1
1 2
2 2
2 1
3 1
3 0

Sample Input 2 Sample Output 2

8 0.0
0 0
0 2
1 2
1 1
2 1
2 2
3 2
3 0

Sample Input 3 Sample Output 3

6 48.80349500
140 62
97 141
68 156
129 145
153 176
130 109

NCPC 2020 Problem B: Big Brother 4

 Problem C
Coin Stacks
Time limit: 0 seconds
A and B are playing a collaborative game that involves n
stacks of coins, numbered from 1 to n. Every round of the
game, they select a nonempty stack each, but they are not
allowed to choose the same stack. They then remove a coin
from both the two selected stacks and then the next round
begins.
The players win the game if they manage to remove all
the coins. Is it possible for them to win the game, and if it
Picture by KMR Photography via Wikimedia Commons, cc by
is, how should they play?

Input
The first line of input contains an integer n (2 ≤ n ≤ 50), the number of coin stacks. Then
follows a line containing n nonnegative integers a1 , a2 , . . . , an , where ai is the number of coins
in the i’th stack. The total number of coins is at most 1 000.

Output
If the players can win the game, output a line containing “yes”, followed by a description
of the moves. Otherwise output a line containing “no”. When describing the moves, output
one move per line, each move being described by two distinct integers a and b (between 1 and
n) indicating that the players remove a coin from stacks a and b. If there are several possible
solutions, output any one of them.

Sample Input 1 Sample Output 1

3 yes
1 4 3 1 2
2 3
2 3
2 3

Sample Input 2 Sample Output 2

3 no
1 1 1

NCPC 2020 Problem C: Coin Stacks 5

This page is intentionally left blank.
 Problem D
Dams in Distress
Time limit: 0 seconds
Freyr, the god of prosperity, rain and the harvest, is having
a lot of trouble these days. The giants are once again trying
to invade Midgard, and have built a war camp at the bottom
of the many valleys leading to Midgard. Now Freyr needs
to wash that camp away, so a great victory feast can be held.
Being at the bottom of the valley, any rain in the region can
make its way through rivers and streams to the bottom of the
valley and contribute to the glorious flooding of the giants.
However, beavers and industrious humans have built dams
throughout the river system, and these act as buffers that can
hold some amount of water. But, on the flip side, once a
dam is filled up to its capacity, it will break and all of the
water stored there (as well as any further water added) will
be released downstream.
Freyr, being the god of rain, knows exactly how much
water is needed to wash the war camp away, and for each dam Freyr by Johannes Gehrts (1901), Public Domain

knows its exact capacity and how much water is currently

stored there. Freyr, also being the god of prosperity and harvest, has better things to do than
making it rain everywhere all day, so Freyr decides to only make it rain at a single place (either
a dam, or the war camp), and to make it rain as little as possible in that place. What is the
minimum amount of rain that Freyr needs to make to wash away the giants war camp, provided
he carefully chooses the best location for the rain?
The network of dams and the war camp form a rooted tree, where the war camp is the root
and the parent of a dam is the location (either another dam, or the war camp) immediately
downstream of the dam. See Figure D.1 for an example.

48/50 10/49

0/50

50/100

Figure D.1: Illustration of Sample Input 1. In this case Freyr only has to make 2 units of rain
at the left-most dam in order to make it break and send 50 units of water downstream, which
then ultimately results in 100 units of rain reaching the war camp, well exceeding the 75 units of
water needed to flood the camp.

NCPC 2020 Problem D: Dams in Distress 7

Input
The first line of input consists of two integers n and w (1 ≤ n ≤ 2 · 105 , 1 ≤ w ≤ 109 ), the
number of dams and the amount of water needed to wash away the war camp, respectively. Then
follow n lines, describing the n dams. The dams are numbered from 1 to n.
The ith line contains three integers di , ci and ui (0 ≤ di < i, 1 ≤ ci ≤ 109 , 0 ≤ ui < ci ),
where di is the number of the dam immediately downstream of dam i (or 0 if the war camp is
immediately downstream of dam i), ci is the maximum capacity of dam i, and ui is the current
amount of water in dam i.

Output
Output the minimum amount of rain Freyr needs to make at one location, which will result in at
least w water reaching the war camp.

Sample Input 1 Sample Output 1

4 75 2
0 100 50
1 49 10
1 50 0
3 50 48

Sample Input 2 Sample Output 2

4 13 10
0 12 1
1 6 1
2 4 1
3 10 0

Sample Input 3 Sample Output 3

4 1 1
0 100 50
1 49 10
1 50 0
3 50 48

NCPC 2020 Problem D: Dams in Distress 8

 Problem E
Exhaustive Experiment
Time limit: 0 seconds
You have been assigned to a new top-secret program involving
a strange vacuum system. The physicists working on the system
have been trying to find out where it is leaking but now they are
confused by all the measurement results and want your help to
figure out what is going on.
The vacuum system contains a wall with possibly leaking
components. The physicists have performed vacuum leak tests
on some of these components by flushing them with helium gas
and then noting down whether their mass spectrometer detected
any spike in helium in the vacuum system directly following this
release of gas. If the component has even the tiniest leak they
will detect it this way but there are some complications as well.
The helium will rise up and spread out from where they released
it and if it passes by any other leaking component, that will also Picture by Alf van Beem, public domain

trigger a positive reading. For each unit distance the helium has
risen it will also have expanded by one unit. Thus the leak test will produce a positive result
if the tested component is leaking or if there is a leaking component above it for which the x
coordinates differs by at most half of the difference in the y coordinate. See Figure E.1 for an
example.
You start out with a positive mindset thinking that there are probably just a few leaking
components responsible for all the positive measurements. To determine if this is indeed possible
you set out to determine the minimum number of leaking components that could give rise to the
observed leak test results.
y

N
P

x
- P

Figure E.1: Illustration of Sample Input 1. Circles indicate components and the blue triangle
indicates where helium will spread when the first component is tested. This test being positive
means that at least one of the the three components covered by the triangle is leaking. The
correct answer in this case is 1 since the measurement results can all be explained with only the
rightmost component leaking.

NCPC 2020 Problem E: Exhaustive Experiment 9

Input
The first line of input contains an integer n (1 ≤ n ≤ 2·105 ), the number of components involved.
The following n lines each contain two integers x and y and a character c (−108 ≤ x, y ≤ 108 ,
c ∈ {-, P, N}), where (x, y) are the coordinates of a component and c describes a possible
leak test result, with the following meanings:

• ‘-’ – No leak test has been performed on this component

• ‘N’ – Leak test gave negative response on this component

• ‘P’ – Leak test gave positive response on this component

No two components have the same position.

Output
Output a single integer, the minimum number of leaking components that could give rise to the
observed leak test results. If no set of leaking components could give rise to the observed results,
instead output the single word impossible.

Sample Input 1 Sample Output 1

4 1
1 -1 P
2 2 P
-1 3 N
-2 -1 -

Sample Input 2 Sample Output 2

2 impossible
0 0 N
1 2 P

NCPC 2020 Problem E: Exhaustive Experiment 10

 Problem F
Film Critics
Time limit: 0 seconds
The premier of the anticipated action film
No Thyme to Fry is right around the corner,
and it is time to give early screenings to film
critics so that they can review it. A small
cinema has been selected to show these early
screenings.
There are n critics numbered from 1 to
n scheduled to watch the movie early, and
each of them will watch it separately. After
watching it, they will immediately give it a
score from 0 to m. Susan, the cinema owner,
has carefully looked at every critics social Picture by Mattias Ek, cc by

media and already knows that the ith critic

thinks the movie is worth a score of ai . However, the ith critic will not simply give the movie a
score of ai like you would expect, because they also take into account the scores that the other
critics gave. Here is how they behave:
1. The first critic to arrive will be so happy that they are the first to review the movie that
they will give it a score of m regardless of their initial opinion.
2. Every subsequent critic will look at the average score given by the previous critics. If this
number is smaller than or equal to the initial opinion ai then the critic will it a score of m,
otherwise they will give it a 0.
Susan thinks the critics behaviour is ridiculous. She has watched the movie, and it is clearly
worth a score of exactly k/n and nothing else! But Susan is the owner of the cinema, so she
gets to decide in what order to invite the critics. Your task is to find a permutation of 1, 2, . . . , n
so that if the critics arrive in this order the average score will be exactly k/n.

Input
The first line of input contains three integers n, m and k (1 ≤ n ≤ 2 · 105 , 1 ≤ m ≤ 104 ,
0 ≤ k ≤ n · m). The second line contains the n integers a1 , a2 , . . . , an (0 ≤ ai ≤ m for each i),
the n critic scores as described above.

Output
If the critics can be ordered in such a way that the resulting average score is exactly k/n, then
output n integers p1 , . . . , pn , where 1 ≤ pi ≤ n indicates that the ith critic to visit the cinema is
the critic numbered pi . This list of integers should be a permutation such that the average score
given by the critics is k/n. If there are multiple solutions any one will be accepted.
Otherwise, if there is no such way to order the critics, output “impossible”.

Sample Input 1 Sample Output 1

5 10 30 3 5 2 1 4
10 5 3 1 3

NCPC 2020 Problem F: Film Critics 11

Sample Input 2 Sample Output 2
5 5 20 impossible
5 3 3 3 3

NCPC 2020 Problem F: Film Critics 12

 Problem G
Gig Combinatorics
Time limit: 0 seconds
Your friend Tóti is an aspiring musician. He has written
n songs, each of which has hype-rating of either 1, 2,
or 3. A higher hype-rating means the song has more
energy. Tóti is planning his first live performance and
needs your help. He wants to know how many setlist
he can make. A setlist consist of at least three songs,
the first songs has to have a hype-rating 1, the last has
to have a hype-rating 3, and all others have to have a
hype-rating 2. Tóti also wants to play the songs in the
same order he wrote them. Picture by Veress Attila Esküvői, cc by-sa

Given the hype-rating of each of Tóti’s song in the

order he wrote them, how many setlist can he make?

Input
The first line of the input consists of a single integer n (1 ≤ n ≤ 106 ), the number of songs Tóti
has written. The second line consists of n integers, each in {1, 2, 3}, giving the hype-ratings of
the n songs in the order they were written.

Output
The output should consist of one integer, the number of setlists Tóti can make. Since this number
can be large, print it modulo 109 + 7.

Sample Input 1 Sample Output 1

9 63
1 1 1 2 2 2 3 3 3

Sample Input 2 Sample Output 2

8 15
1 2 1 2 3 1 2 3

NCPC 2020 Problem G: Gig Combinatorics 13

This page is intentionally left blank.
 Problem H
Hiring and Firing
Time limit: 0 seconds
Amazin’ Inc, an up-and-coming company in e-commerce,
has recently optimized its operations to make the most out
of its workers. Thanks to state-of-the-art prediction meth-
ods, Amazin’ now knows in advance how many workers
will be needed each day for the foreseeable future. Using
this information they can adjust the size of their work-
force on a day-to-day basis by firing and/or hiring workers
so that they always have exactly as many as are needed
each day. In order to prevent the workers from getting
too comfortable and organizing themselves, they will also Image by Gerd Altmann via Pixabay
regularly fire workers and replace them with new ones.
For instance, if on some day four more workers are needed than yesterday, Amazin’ might fire
10 people and then hire 14 new ones on that day.
Unfortunately, due to labor laws, the firing of workers must follow a last-in-first-out order:
the people who have been employed the shortest time must be fired first. Furthermore, a fired
person cannot be re-hired within the foreseeable future so it is not possible to circumvent the
law by firing some people and then immediately re-hiring some of them.
But this story is actually about HR, not workers! Every day, one employee from the HR
department is assigned to be responsible for giving the fired workers the bad news that they are
fired, and for then giving the newly hired workers the good news that they are hired. In order to
minimize work environment problems in the form of social awkwardness for the HR staff, a
policy has been established requiring that the HR person firing an employee must always be a
different HR person than the one welcoming them when they were hired.
Now the time has come for the HR department to also optimize itself, by making itself as
small as possible. Unlike workers, new HR staff cannot be hired with short notice, so the HR
personnel must be permanent employees. What is the smallest number of HR people needed in
order to manage all the planned hirings and firings?

Input
The first line of input contains an integer n (1 ≤ n ≤ 105 ), the length in days of the foreseeable
future. Then follow n lines, the ith of which contains two integers fi and hi (0 ≤ fi , hi ≤ 106 )
where fi is the number of workers fired on day i and hi the number of people hired.
The number of workers fired Pon a day is never larger than the number of currently employed
i−1
workers (in other words, fi ≤ j=0 hj − fj for all 1 ≤ i ≤ n).

Output
Output a line with an integer k, the smallest number of HR people needed. The HR people are
arbitrarily given IDs from 1 to k. Then output a line with n integers, the ith of which contains
the ID of the HR person in charge of the firing and hiring on day i. If there is more than one
solution, any one will be accepted.

NCPC 2020 Problem H: Hiring and Firing 15

Sample Input 1 Sample Output 1
4 3
0 3 1 2 3 2
1 1
2 1
2 0

Sample Input 2 Sample Output 2

6 2
0 10 1 2 1 2 1 2
0 5
2 0
0 0
0 100
50 100

NCPC 2020 Problem H: Hiring and Firing 16

 Problem I
Infection Estimation
Time limit: 0 seconds
A new virus has appeared in country X, with a
population of 10 million people. This time the
country is prepared, and wants to start tracking
its spread as quickly as possible. It is currently
only known that at least 100 and at most 5 000 000
people are infected, and your job is to provide a
more accurate estimate on the number of infected
people.
While it will take some time until tests get into
mass production, one of the research labs is able Picture by Luca Volpi, cc by-sa

to perform up to 50 tests per day. To improve test

efficiency, the researchers have decided to combine tests from multiple people. Each test takes
in tissue samples from any chosen number of people, and gets a positive result if there is virus
in at least one of them, otherwise a negative result. The tests are performed sequentially – the
result of each test becomes available before the next test can be performed.
Write a program which decides how to perform the tests and provides an estimate of the
number of infected people which is within a factor 2 of the actual number of infected people.

Interaction
Your program can run up to 50 tests, and must then produce an estimate of the number of
infected people. To issue a test, output “test k” for an integer 1 ≤ k ≤ 107 . The judge will
then provide a line which contains either “1” if the test for k randomly chosen people came
back positive, or “0” if it came back negative. The k people will be chosen without replacement,
i.e., the same person cannot be chosen twice. However, the tests are independent, so a person
may end up being chosen in more than one round.
To provide the estimate, output “estimate x”, where 0 ≤ x ≤ 107 is your estimate on the
number of infected people. The answer will be treated as correct if it is within a factor 2 of the
correct answer y, i.e., if y/2 ≤ x ≤ 2y.
There will be a total of 100 runs of your program. You may assume that each run is
deterministic: making the same sequence of tests on the ith run will always result in the same
sequence of test results. To facilitate testing of your solutions, we provide a simple tool that you
can download from the Kattis page for this problem. Remember to flush your standard output
buffer for every line you output!

NCPC 2020 Problem I: Infection Estimation 17

 (Note: the sample interaction below is shown only for the purpose of illustrating the
interaction protocol: there is no way the solution could reliably conclude the given estimate of
250 000 infected people based on the four tests performed.)

Read Sample Interaction 1 Write

test 10
1
test 10
0
test 17
0
test 16
1
estimate 250000

NCPC 2020 Problem I: Infection Estimation 18

 Problem J
Joining Flows
Time limit: 0 seconds
Having recently taken over the Wonka Factory, Charlie is
now in charge of the day-to-day production of the various
chocolate products made there. While this may seem
like a cushy job with an all-you-can-eat-chocolate perk, it
also comes with the difficult responsibility of keeping the
(somewhat convoluted and complicated) production lines
working.
The heart of the factory is the Chocolate River, where
raw molten chocolate flows from k chocolate-producing
faucets, to outlets where different types of pralines and
Picture by André Karwath, cc by-sa
choclate bars are made. The i’th of the k chocolate faucets
produces chocolate at some fixed temperature ti , and the amount of chocolate flowing from
the faucet can be adjusted to any value between ai and bi millilitres per second. Suppose the
k taps are adjusted to produce x1 , x2 , . . . , xk millilitres of chocolates per second respectively
(where ai ≤ xi ≤ bi ). Then the total flow in the Chocolate river is x1 + x2 + . . . + xk , and its
temperature is the weighted average
x1 t1 + x2 t2 + . . . + xk tk
x1 + x2 + . . . + xk
(each faucet produces grade A quality chocolate which instantly mixes with the chocolate from
the other faucets).
Each type of praline and chocolate bar produced at the factory requires the Chocolate River
to be adjusted to have a specific temperature and flow level. Charlie recently came across a long
list of new praline recipies, and would now like to figure out which of these are even possible to
make at the factory. Write a program to determine, for each of the new recipies, if its required
temperature and flow level is possible to achieve with some setting of the k faucets.

Input
The first line of input contains an integer k (1 ≤ k ≤ 10), the number of taps. Then follow
k lines, describing the taps. The i’th of these lines contains the three integers ti , ai , and bi
(0 ≤ ti ≤ 106 , 0 ≤ ai ≤ bi ≤ 106 ) describing the i’th faucet.
Next follows a line containing an integer r (1 ≤ r ≤ 105 ), the number of new recipies to
check. Then follows r lines, each describing a recipe. A recipe is described by two integers
τ and φ (0 ≤ τ ≤ 106 and 1 ≤ φ ≤ 106 ), where τ is the chocolate temperature and φ the
chocolate flow needed for this recipe.

Output
For each of the r recipies, print one line with the string “yes” if it is possible to achieve the
desired combination of chocolate temperature and flow, and “no” otherwise.

NCPC 2020 Problem J: Joining Flows 19

Sample Input 1 Sample Output 1
2 no
50 0 100 yes
100 50 100 no
3
20 75
75 150
75 90

NCPC 2020 Problem J: Joining Flows 20

 Problem K
Keep Calm And Carry Off
Time limit: 0 seconds
Petra is learning how to add two positive integers in school, but
thinks it is a bit too difficult. They are currently working with the
standard algorithm for addition, where you first compute the sum
of the two units digits, then the sum of the two tens digits, and
so on. Whenever the sum of the digits at the same position in the
two numbers exceeds 9, a carry digit is added onto the digit of
the next higher magnitude. Petra has trouble with the last step –
she often forgets to keep track of the carry digit.
A few weeks ago, she also learnt a simpler method of addition.
In this method, you repeatedly add 1 to one of the numbers and
subtract 1 from the other, until the second one reaches zero. This
can of course take a lot of time for large numbers.
Petra now wants to combine the two methods, for fast and
error-free addition. Her plan is to first perform the second method
one step at a time, until the two numbers would not produce a
Picture by Dennis Clarisse
carry digit when added using the standard algorithm (for positive
integers, this always happens eventually). To evaluate the performance of her new method,
she has asked you to help her compute the number of steps she must perform of the second
method when adding two given integers. Petra may perform the addition by 1 to either of the
two numbers (and subtraction by 1 from the other).

Input
The input consists of two lines, each containing a positive integer with at most 106 digits. These
are the two integers Petra wants to add.

Output
Output a single integer, the minimum number of times Petra must add 1 to one of her numbers
(while subtracting 1 from the other) until they can be added using the standard addition algorithm
without any carry digits.

Sample Input 1 Sample Output 1

10 1
99

Sample Input 2 Sample Output 2

90 10
10

Sample Input 3 Sample Output 3

23425 12085
487915

NCPC 2020 Problem K: Keep Calm And Carry Off 21

This page is intentionally left blank.
 Problem L
Language Survey
Time limit: 0 seconds
In Gridnavia, three languages are spoken:
Arwegian, Banish, and Cwedish. Gridnavia
consists of an n × m grid, where in each cell
some non-empty subset of languages is spo-
ken. It is known that each of the three lan-
guages is spoken in a non-empty connected
subset of grid cells. Connected means that it
is possible to get between any pair of cells by
moving through adjacent cells, where two
cells are said to be adjacent if they share a
side.
You have made a survey to find where
in Gridnavia each language is spoken. The
Picture by LA2, cc by-sa
following question was sent to every cell in
the region: “Please indicate if one or several of the languages is spoken in your cell”. But due to
a misprint, there were no choices after the question, so everyone just wrote “one” or “several”.
So the only thing you know is for each cell whether exactly one, or more than one language is
spoken in that cell.
To make the best out of the situation, you should find any division of the three languages
that corresponds to the information.

Input
The first line of input contains two integers n and m (1 ≤ n, m ≤ 200).
The following n lines each contain a string of length m, consisting of the characters 1 and 2.
The jth character on the ith line is 1 if exactly one language is spoken in that cell, and 2 if at
least two languages are spoken.

Output
If the languages can be divided according to the information, then output three copies of the grid.
The first copy should consist of characters “A” and “.”, where the “A” indicates that Arwegian is
spoken in that cell, and “.” indicates that it isn’t spoken. The following two grids should consist
of characters “B” and “.”, and “C” and “.”, respectively, with the corresponding information
about Banish and Cwedish.
Remember that the three regions have to be connected and non-empty, and every cell must be
part of some region. For readability, it is recommended to put empty lines in between the three
grids, but it is not necessary to do so. If there are multiple solutions any one will be accepted.
Otherwise, if there is no way to divide the languages, output “impossible”.

NCPC 2020 Problem L: Language Survey 23

Sample Input 1 Sample Output 1
3 4 AAAA
2211 ...A
1112 ....
1112
BB..
BBBB
...B

....
...C
CCCC

Sample Input 2 Sample Output 2

1 1 impossible
1

NCPC 2020 Problem L: Language Survey 24

 Problem M
Methodic Multiplication
Time limit: 0 seconds
After one computer crash too many, Alonso has had enough of all this
shoddy software and poorly written code! He decides that in order for
this situation to improve, the glass house that is modern programming
needs to be torn down and rebuilt from scratch using only completely
formal axiomatic reasoning. As one of the first steps, he decides to
implement arithmetic with natural numbers using the Peano axioms.
The Peano axioms (named after Italian mathematican Giuseppe
Peano) are an axiomatic formalization of the arithmetic properties of
the natural numbers. We have two symbols: the constant 0, and a unary
successor function S. The natural numbers, starting at 0, are then 0, S(0), Giuseppe Peano, public domain

S(S(0)), S(S(S(0))), and so on. With these two symbols, the operations
of addition and multiplication are defined inductively by the following axioms: for any natural
numbers x and y, we have

x+0=x x·0=0
x + S(y) = S(x + y) x · S(y) = x · y + x

The two axioms on the left define addition, and the two on the right define multiplication.
For instance, given x = S(S(0)) and y = S(0) we can repeatedly apply these axioms to
derive

x · y = S(S(0)) · S(0) = S(S(0)) · 0 + S(S(0))

= 0 + S(S(0)) = S(0 + S(0)) = S(S(0 + 0)) = S(S(0))

Write a program which given two natural numbers x and y, defined in Peano arithmetic, computes
the product x · y.

Input
The input consists of two lines. Each line contains a natural number defined in Peano arithmatic,
using at most 1 000 characters.

Output
Output the product of the two input numbers.

Sample Input 1 Sample Output 1

S(S(0)) S(S(S(S(S(S(0))))))
S(S(S(0)))

Sample Input 2 Sample Output 2

S(S(S(S(S(0))))) 0
0

NCPC 2020 Problem M: Methodic Multiplication 25

This page is intentionally left blank.