Construction

Constructive Algorithms

1. Let’s call a permutation p of length n anti-Fibonacci if the condition

pi−2 + pi−1 ̸= pi holds for all i (3 ≤ i ≤ n). Recall that the permutation
is the array of length n which contains each integer from 1 to n exactly
once. Your task is for a given number n print n distinct anti-Fibonacci
permutations of length n.

2. Stanley defines the beauty of an array a of length n, which contains non-

negative integers, as follows:
n j k
X ai
i=1
k

which means that we divide each element by k, round it down, and sum
up the resulting values. Stanley told Sam the integer k and asked him to
find an array a of n non-negative integers, such that the beauty is equal
to b and the sum of elements is equal to s. Help Sam — find any of the
arrays satisfying the conditions above.

3. A sequence of n numbers is called a permutation if it contains all num-

bers from 1 to n exactly once. For example, the sequences [3,1,4,2], [1]
and [2,1] are permutations, but [1,2,1], [0,1] and [1,3,4] are not.

For a given number n, you need to make a permutation p such that two
requirements are satisfied at the same time:
• For each element pi , at least one of its neighbors has a value that
differs from the value of pi by one. That is, for each element pi
(1 ≤ i ≤ n), at least one of its neighboring elements (standing to the
left or right of pi ) must be pi+1 or pi−1 .
• The permutation must have no fixed points. That is, for every i
(1 ≤ i ≤ n), pi ̸= i must be satisfied.

1
 Construction

Let’s call the permutation that satisfies these requirements funny.

For example, let n = 4. Then [4,3,1,2] is a funny permutation, since:

• To the right of p1 = 4 is p2 = p1 − 1 = 4 − 1 = 3.
• To the left of p2 = 3 is p1 = p2 + 1 = 3 + 1 = 4.
• To the right of p3 = 1 is p4 = p3 + 1 = 1 + 1 = 2.
• To the left of p4 = 2 is p3 = p4 − 1 = 2 − 1 = 1.
• For all i, pi ̸= i.
For a given positive integer n, output any funny permutation of length
n, or output −1 if funny permutation of length n does not exist.

4. Little C loves number 3 very much. He loves all things about it. Now he
has a positive integer n. He wants to split n into 3 positive integers a, b,
c, such that a + b + c = n and none of the 3 integers is a multiple of 3.
Help him to find a solution.

5. Madoka finally found the administrator password for her computer. Her
father is a well-known popularizer of mathematics, so the password is the
answer to the following problem.

Find the maximum decimal number without zeroes and with no equal
digits in a row, such that the sum of its digits is n.

Madoka is too tired of math to solve it herself, so help her to solve this
problem!

6. You are given a positive integer n, it is guaranteed that n is even (i.e.

divisible by 2).

You want to construct the array a of length n such that:

• The first n
2 elements of a are even (divisible by 2);
• The second n
2 elements of a are odd (not divisible by 2);

2
 Construction

• all elements of a are distinct and positive;

n
2
X
• the sum of the first half equals to the sum of the second half ( ai =
i=1
n
X
ai ).
i= n2 +1

If there are multiple answers, you can print any. It is not guaranteed
that the answer exists.

7. Nastia has 2 positive integers A and B. She defines that:

• The integer is good if it is divisible by A · B;
• Otherwise, the integer is nearly good, if it is divisible by A.
For example, if A = 6 and B = 4, the integers 24 and 72 are good, the
integers 6, 660 and 12 are nearly good, the integers 16, 7 are neither good
nor nearly good.

Find 3 different positive integers x, y, and z such that exactly one of

them is good and the other 2 are nearly good, and x + y = z.

8. There are n cats in a line, labeled from 1 to n, with the i-th cat at po-
sition i. They are bored of gyrating in the same spot all day, so they
want to reorder themselves such that no cat is in the same place as be-
fore. They are also lazy, so they want to minimize the total distance they
move. Help them decide what cat should be at each location after the
reordering.

For example, if there are 3 cats, this is a valid reordering: [3,1,2]. No cat
is in its original position. The total distance the cats move is 1+1+2 = 4
as cat 1 moves one place to the right, cat 2 moves one place to the right,
and cat 3 moves two places to the left.

3
 Construction

9. Pari has a friend who loves palindrome numbers. A palindrome num-

ber is a number that reads the same forward or backward. For example
12321, 100001 and 1 are palindrome numbers, while 112 and 1021 are not.

Pari is trying to love them too, but only very special and gifted peo-
ple can understand the beauty behind palindrome numbers. Pari loves
integers with even length (i.e. the numbers with even number of digits),
so she tries to see a lot of big palindrome numbers with even length (like
a 2-digit 11 or 6-digit 122221), so maybe she could see something in them.

Now Pari asks you to write a program that gets a huge integer n from the
input and tells what is the n-th even-length positive palindrome number?

10. You are given a positive integer n. You have to find 4 positive integers
a, b, c, d such that
• a + b + c + d = n and
• gcd(a, b) = lcm(c, d).
If there are several possible answers you can output any of them. It is
possible to show that the answer always exists.

11. Given n, find any array a1 , a2 , . . . , an of integers such that all of the
following conditions hold:
• 1 ≤ ai ≤ 109 for every i from 1 to n.
• a1 < a2 < . . . < an
• For every i from 2 to n, ai isn’t divisible by ai−1 .
It can be shown that such an array always exists under the constraints
of the problem.

4
 Construction

12. In the beginning of the new year Keivan decided to reverse his name. He
doesn’t like palindromes, so he changed Naviek to Navick.

He is too selfish, so for a given n he wants to obtain a string of n charac-

ters, each of which is either ’a’, ’b’ or ’c’, with no palindromes of length
3 appearing in the string as a substring. For example, the strings ”abc”
and ”abca” suit him, while the string ”aba” doesn’t. He also want the
number of letters ’c’ in his string to be as little as possible.

13. There are n students standing in line in positions 1 to n. While the

teacher looks away, some students change their positions. When the
teacher looks back, they are standing in line again. If a student who was
initially in position i is now in position j, we say the student moved for
|i − j| steps. Determine a possible way to achieve maximal sum of steps.

14. Apart from having lots of holidays throughout the year, residents of
Berland also have whole lucky years. Year is considered lucky if it has
no more than 1 non-zero digit in its number. So years 100, 40000, 5 are
lucky and 12, 3001 and 12345 are not.

You are given current year in Berland. Your task is to find how long
will residents of Berland wait till the next lucky year.

15. At the store, the salespeople want to make all prices round.

In this problem, a number that is a power of 10 is called a round num-

ber. For example, the numbers 100 = 1, 101 = 10, 102 = 100 are round
numbers, but 20, 110 and 256 are not round numbers.

So, if an item is worth m bourles (the value of the item is not greater than
109 ), the sellers want to change its value to the nearest round number
that is not greater than m. They ask you: by how many bourles should

5
 Construction

you decrease the value of the item to make it worth exactly 10k bourles,
where the value of k — is the maximum possible (k — any non-negative
integer).

For example, let the item have a value of 178-bourles. Then the new
price of the item will be 100, and the answer will be 178 − 100 = 78.

16. A permutation of length n is an array consisting of n distinct integers

from 1 to n in arbitrary order. For example, [2,3,1,5,4] is a permutation,
but [1,2,2] is not a permutation (2 appears twice in the array) and [1,3,4]
is also not a permutation (n = 3 but there is 4 in the array).

For a positive integer n, we call a permutation p of length n good if

the following condition holds for every pair i and j (1 ≤ i ≤ j ≤ n) —
• (pi OR pi+1 OR . . . OR pj−1 OR pj ) ≥ j − i + 1,
where OR denotes the bitwise OR operation.

In other words, a permutation p is good if for every subarray of p, the

OR of all elements in it is not less than the number of elements in that
subarray.

Given a positive integer n, output any good permutation of length n.

We can show that for the given constraints such a permutation always
exists.

17. You are given a positive integer n.

The weight of a permutation p1 , p2 , . . . , pn is the number of indices 1 ≤

i ≤ n such that i divides pi . Find a permutation p1 , p2 , . . . , pn with the
minimum possible weight (among all permutations of length n).

A permutation is an array consisting of n distinct integers from 1 to n in

arbitrary order. For example, [2,3,1,5,4] is a permutation, but [1,2,2] is

6
 not a permutation (2 appears twice in the array) and [1,3,4] is also not a
permutation (n = 3 but there is 4 in the array).

18. You are given an integer n. You have to construct a permutation of size n.

A permutation is an array where each integer from 1 to s (where s is

the size of permutation) occurs exactly once. For example, [2,1,4,3] is a
permutation of size 4; [1,2,4,5,3] is a permutation of size 5; [1,4,3] is not a
permutation (the integer 2 is absent), [2,1,3,1] is not a permutation (the
integer 1 appears twice).

A subsegment of a permutation is a contiguous subsequence of that per-

mutation. For example, the permutation [2,1,4,3] has 10 subsegments:
[2], [2,1], [2,1,4], [2,1,4,3], [1], [1,4], [1,4,3], [4], [4,3] and [3].

The value of the permutation is the number of its subsegments which

are also permutations. For example, the value of [2,1,4,3] is 3 since the
subsegments [2,1], [1] and [2,1,4,3] are permutations.

You have to construct a permutation of size n with minimum possible

value among all permutations of size n.

19. You are given an integer n.

Find any pair of integers (x, y) (1 ≤ x, y ≤ n) such that xy · y + y x · x = n.

20. Pak Chanek has a prime number n. Find a prime number m such that
n + m is not prime.