Introductory Problems Jul 01, 2025
Problem A. Weird Algorithm
Time Limit 1000 ms
Mem Limit 524288 kB
Consider an algorithm that takes as input a positive integer n. If n is even, the algorithm
divides it by two, and if n is odd, the algorithm multiplies it by three and adds one. The
algorithm repeats this, until n is one. For example, the sequence for n = 3 is as follows:
3 → 10 → 5 → 16 → 8 → 4 → 2 → 1
Your task is to simulate the execution of the algorithm for a given value of n.
Input
The only input line contains an integer n.
Output
Print a line that contains all values of n during the algorithm.
Constraints
1 ≤ n ≤ 106
Example
Input Output
3 3 10 5 16 8 4 2 1
Page 1 of 24
-
Introductory Problems Jul 01, 2025
Problem B. Missing Number
Time Limit 1000 ms
Mem Limit 524288 kB
You are given all numbers between 1, 2, … , n except one. Your task is to find the missing
number.
Input
The first input line contains an integer n.
The second line contains n − 1 numbers. Each number is distinct and between 1 and n
(inclusive).
Output
Print the missing number.
Constraints
2 ≤ n ≤ 2 ⋅ 105
Example
Input Output
5 4
2 3 1 5
Page 2 of 24
-
Introductory Problems Jul 01, 2025
Problem C. Repetitions
Time Limit 1000 ms
Mem Limit 524288 kB
You are given a DNA sequence: a string consisting of characters A, C, G, and T. Your task is
to find the longest repetition in the sequence. This is a maximum-length substring
containing only one type of character.
Input
The only input line contains a string of n characters.
Output
Print one integer: the length of the longest repetition.
Constraints
1 ≤ n ≤ 106
Example
Input Output
ATTCGGGA 3
Page 3 of 24
-
Introductory Problems Jul 01, 2025
Problem D. Increasing Array
Time Limit 1000 ms
Mem Limit 524288 kB
You are given an array of n integers. You want to modify the array so that it is increasing,
i.e., every element is at least as large as the previous element.
On each move, you may increase the value of any element by one. What is the minimum
number of moves required?
Input
The first input line contains an integer n: the size of the array.
Then, the second line contains n integers x1 , x2 , … , xn : the contents of the array.
Output
Print the minimum number of moves.
Constraints
1 ≤ n ≤ 2 ⋅ 105
1 ≤ xi ≤ 109
Example
Input Output
5 5
3 2 5 1 7
Page 4 of 24
-
Introductory Problems Jul 01, 2025
Problem E. Permutations
Time Limit 1000 ms
Mem Limit 524288 kB
A permutation of integers 1, 2, … , n is called beautiful if there are no adjacent elements
whose difference is 1.
Given n, construct a beautiful permutation if such a permutation exists.
Input
The only input line contains an integer n.
Output
Print a beautiful permutation of integers 1, 2, … , n. If there are several solutions, you
may print any of them. If there are no solutions, print "NO SOLUTION".
Constraints
1 ≤ n ≤ 106
Example 1
Input Output
5 4 2 5 3 1
Example 2
Input Output
3 NO SOLUTION
Page 5 of 24
-
Introductory Problems Jul 01, 2025
Problem F. Number Spiral
Time Limit 1000 ms
Mem Limit 524288 kB
A number spiral is an infinite grid whose upper-left square has number 1. Here are the
first five layers of the spiral:
Your task is to find out the number in row y and column x.
Input
The first input line contains an integer t: the number of tests.
After this, there are t lines, each containing integers y and x.
Output
For each test, print the number in row y and column x.
Constraints
1 ≤ t ≤ 105
1 ≤ y, x ≤ 109
Example
Input Output
3 8
2 3 1
1 1 15
4 2
Page 6 of 24
-
Introductory Problems Jul 01, 2025
Problem G. Two Knights
Time Limit 1000 ms
Mem Limit 524288 kB
Your task is to count for k = 1, 2, … , n the number of ways two knights can be placed on
ak × k chessboard so that they do not attack each other.
Input
The only input line contains an integer n.
Output
Print n integers: the results.
Constraints
1 ≤ n ≤ 10000
Example
Input Output
8 0
6
28
96
252
550
1056
1848
Page 7 of 24
-
Introductory Problems Jul 01, 2025
Problem H. Two Sets
Time Limit 1000 ms
Mem Limit 524288 kB
Your task is to divide the numbers 1, 2, … , n into two sets of equal sum.
Input
The only input line contains an integer n.
Output
Print "YES", if the division is possible, and "NO" otherwise.
After this, if the division is possible, print an example of how to create the sets. First,
print the number of elements in the first set followed by the elements themselves in a
separate line, and then, print the second set in a similar way.
Constraints
1 ≤ n ≤ 106
Example 1
Input Output
7 YES
4
1 2 4 7
3
3 5 6
Example 2
Input Output
6 NO
Page 8 of 24
-
Introductory Problems Jul 01, 2025
Problem I. Bit Strings
Time Limit 1000 ms
Mem Limit 524288 kB
Your task is to calculate the number of bit strings of length n.
For example, if n = 3, the correct answer is 8, because the possible bit strings are 000,
001, 010, 011, 100, 101, 110, and 111.
Input
The only input line has an integer n.
Output
Print the result modulo 109 + 7.
Constraints
1 ≤ n ≤ 106
Example
Input Output
3 8
Page 9 of 24
-
Introductory Problems Jul 01, 2025
Problem J. Trailing Zeros
Time Limit 1000 ms
Mem Limit 524288 kB
Your task is to calculate the number of trailing zeros in the factorial n!.
For example, 20! = 2432902008176640000 and it has 4 trailing zeros.
Input
The only input line has an integer n.
Output
Print the number of trailing zeros in n!.
Constraints
1 ≤ n ≤ 109
Example
Input Output
20 4
Page 10 of 24
-
Introductory Problems Jul 01, 2025
Problem K. Coin Piles
Time Limit 1000 ms
Mem Limit 524288 kB
You have two coin piles containing a and b coins. On each move, you can either remove
one coin from the left pile and two coins from the right pile, or two coins from the left pile
and one coin from the right pile.
Your task is to efficiently find out if you can empty both the piles.
Input
The first input line has an integer t: the number of tests.
After this, there are t lines, each of which has two integers a and b: the numbers of coins
in the piles.
Output
For each test, print "YES" if you can empty the piles and "NO" otherwise.
Constraints
1 ≤ t ≤ 105
0 ≤ a, b ≤ 109
Example
Input Output
3 YES
2 1 NO
2 2 YES
3 3
Page 11 of 24
-
Introductory Problems Jul 01, 2025
Problem L. Palindrome Reorder
Time Limit 1000 ms
Mem Limit 524288 kB
Given a string, your task is to reorder its letters in such a way that it becomes a
palindrome (i.e., it reads the same forwards and backwards).
Input
The only input line has a string of length n consisting of characters A–Z.
Output
Print a palindrome consisting of the characters of the original string. You may print any
valid solution. If there are no solutions, print "NO SOLUTION".
Constraints
1 ≤ n ≤ 106
Example
Input Output
AAAACACBA AACABACAA
Page 12 of 24
-
Introductory Problems Jul 01, 2025
Problem M. Gray Code
Time Limit 1000 ms
Mem Limit 524288 kB
A Gray code is a list of all 2n bit strings of length n, where any two successive strings
differ in exactly one bit (i.e., their Hamming distance is one).
Your task is to create a Gray code for a given length n.
Input
The only input line has an integer n.
Output
Print 2n lines that describe the Gray code. You can print any valid solution.
Constraints
1 ≤ n ≤ 16
Example
Input Output
2 00
01
11
10
Page 13 of 24
-
Introductory Problems Jul 01, 2025
Problem N. Tower of Hanoi
Time Limit 1000 ms
Mem Limit 524288 kB
The Tower of Hanoi game consists of three stacks (left, middle and right) and n round
disks of different sizes. Initially, the left stack has all the disks, in increasing order of size
from top to bottom.
The goal is to move all the disks to the right stack using the middle stack. On each move
you can move the uppermost disk from a stack to another stack. In addition, it is not
allowed to place a larger disk on a smaller disk.
Your task is to find a solution that minimizes the number of moves.
Input
The only input line has an integer n: the number of disks.
Output
First print an integer k : the minimum number of moves.
After this, print k lines that describe the moves. Each line has two integers a and b: you
move a disk from stack a to stack b.
Constraints
1 ≤ n ≤ 16
Example
Input Output
2 3
1 2
1 3
2 3
Page 14 of 24
-
Introductory Problems Jul 01, 2025
Problem O. Creating Strings
Time Limit 1000 ms
Mem Limit 524288 kB
Given a string, your task is to generate all different strings that can be created using its
characters.
Input
The only input line has a string of length n. Each character is between a–z.
Output
First print an integer k : the number of strings. Then print k lines: the strings in
alphabetical order.
Constraints
1≤n≤8
Example
Input Output
aabac 20
aaabc
aaacb
aabac
aabca
aacab
aacba
abaac
abaca
abcaa
acaab
acaba
acbaa
baaac
baaca
bacaa
bcaaa
caaab
caaba
cabaa
cbaaa
Page 15 of 24
-
Introductory Problems Jul 01, 2025
Problem P. Apple Division
Time Limit 1000 ms
Mem Limit 524288 kB
There are n apples with known weights. Your task is to divide the apples into two groups
so that the difference between the weights of the groups is minimal.
Input
The first input line has an integer n: the number of apples.
The next line has n integers p1 , p2 , … , pn : the weight of each apple.
Output
Print one integer: the minimum difference between the weights of the groups.
Constraints
1 ≤ n ≤ 20
1 ≤ pi ≤ 109
Example
Input Output
5 1
3 2 7 4 1
Explanation: Group 1 has weights 2, 3 and 4 (total weight 9), and group 2 has weights 1
and 7 (total weight 8).
Page 16 of 24
-
Introductory Problems Jul 01, 2025
Problem Q. Chessboard and Queens
Time Limit 1000 ms
Mem Limit 524288 kB
Your task is to place eight queens on a chessboard so that no two queens are attacking
each other. As an additional challenge, each square is either free or reserved, and you can
only place queens on the free squares. However, the reserved squares do not prevent
queens from attacking each other.
How many possible ways are there to place the queens?
Input
The input has eight lines, and each of them has eight characters. Each square is either free
( . ) or reserved ( * ).
Output
Print one integer: the number of ways you can place the queens.
Example
Input Output
........ 65
........
..*.....
........
........
.....**.
...*....
........
Page 17 of 24
-
Introductory Problems Jul 01, 2025
Problem R. Raab Game I
Time Limit 1000 ms
Mem Limit 524288 kB
Consider a two player game where each player has n cards numbered 1, 2, … , n. On each
turn both players place one of their cards on the table. The player who placed the higher
card gets one point. If the cards are equal, neither player gets a point. The game continues
until all cards have been played.
You are given the number of cards n and the players' scores at the end of the game, a and
b. Your task is to give an example of how the game could have played out.
Input
The first line contains one integer t: the number of tests.
Then there are t lines, each with three integers n, a and b.
Output
For each test case print YES if there is a game with the given outcome and NO otherwise.
If the answer is YES , print an example of one possible game. Print two lines representing
the order in which the players place their cards. You can give any valid example.
Constraints
1 ≤ t ≤ 1000
1 ≤ n ≤ 100
0 ≤ a, b ≤ n
Example
Input Output
5 YES
4 1 2 1 4 3 2
2 0 1 2 1 3 4
3 0 0 NO
2 1 1 YES
4 4 1 1 2 3
1 2 3
YES
1 2
2 1
NO
Page 18 of 24
-
Introductory Problems Jul 01, 2025
Problem S. Mex Grid Construction
Time Limit 1000 ms
Mem Limit 524288 kB
Your task is to construct an n × n grid where each square has the smallest nonnegative
integer that does not appear to the left on the same row or above on the same column.
Input
The only line has an integer n.
Output
Print the grid according to the example.
Constraints
1 ≤ n ≤ 100
Example
Input Output
5 0 1 2 3 4
1 0 3 2 5
2 3 0 1 6
3 2 1 0 7
4 5 6 7 0
Page 19 of 24
-
Introductory Problems Jul 01, 2025
Problem T. Knight Moves Grid
Time Limit 1000 ms
Mem Limit 524288 kB
There is a knight on an n × n chessboard. For each square, print the minimum number of
moves the knight needs to do to reach the top-left corner.
Input
The only line has an integer n.
Output
Print the number of moves for each square.
Constraints
4 ≤ n ≤ 1000
Example
Input Output
8 0 3 2 3 2 3 4 5
3 4 1 2 3 4 3 4
2 1 4 3 2 3 4 5
3 2 3 2 3 4 3 4
2 3 2 3 4 3 4 5
3 4 3 4 3 4 5 4
4 3 4 3 4 5 4 5
5 4 5 4 5 4 5 6
Page 20 of 24
-
Introductory Problems Jul 01, 2025
Problem U. Grid Coloring I
Time Limit 1000 ms
Mem Limit 524288 kB
You are given an n × m grid where each cell contains one character A , B , C or D .
For each cell, you must change the character to A , B , C or D . The new character must
be different from the old one.
Your task is to change the characters in every cell such that no two adjacent cells have the
same character.
Input
The first line has two integers n and m: the number of rows and columns.
The next n lines each have m characters: the description of the grid.
Output
Print n lines each with m characters: the description of the final grid.
You may print any valid solution.
If no solution exists, just print IMPOSSIBLE .
Constraints
1 ≤ n, m ≤ 500
Example
Input Output
3 4 CDCD
AAAA DCDC
BBBB ABAB
CCDD
Page 21 of 24
-
Introductory Problems Jul 01, 2025
Problem V. Digit Queries
Time Limit 1000 ms
Mem Limit 524288 kB
Consider an infinite string that consists of all positive integers in increasing order:
12345678910111213141516171819202122232425...
Your task is to process q queries of the form: what is the digit at position k in the string?
Input
The first input line has an integer q : the number of queries.
After this, there are q lines that describe the queries. Each line has an integer k : a 1-
indexed position in the string.
Output
For each query, print the corresponding digit.
Constraints
1 ≤ q ≤ 1000
1 ≤ k ≤ 1018
Example
Input Output
3 7
7 4
19 1
12
Page 22 of 24
-
Introductory Problems Jul 01, 2025
Problem W. String Reorder
Time Limit 1000 ms
Mem Limit 524288 kB
Your task is to reorder the characters of a string so that no two adjacent characters are the
same. What is the lexicographically minimal such string?
Input
The only line has a string of length n consisting of characters A–Z.
Output
Print the lexicographically minimal reordered string where no two adjacent characters
are the same. If it is not possible to create such a string, print −1.
Constraints
1 ≤ n ≤ 106
Example
Input Output
HATTIVATTI AHATITITVT
Page 23 of 24
-
Introductory Problems Jul 01, 2025
Problem X. Grid Path Description
Time Limit 1000 ms
Mem Limit 524288 kB
There are 88418 paths in a 7 × 7 grid from the upper-left square to the lower-left square.
Each path corresponds to a 48-character description consisting of characters D (down),
U (up), L (left) and R (right).
For example, the path
corresponds to the description
DRURRRRRDDDLUULDDDLDRRURDDLLLLLURULURRUULDLLDDDD .
You are given a description of a path which may also contain characters ? (any direction).
Your task is to calculate the number of paths that match the description.
Input
The only input line has a 48-character string of characters ? , D , U , L and R .
Output
Print one integer: the total number of paths.
Example
Input Output
??????R??????U?????????????????????????? 201
LD????D?
Page 24 of 24
-
