A. Again Twenty Five!

The problem of getting the last two digits is equivalent to the problem of getting the number modulo 100. So we need to calculate . According to the rules of modular arithmetic

So

Let's note that 5² = 25. Then

And so on. All are equal to 25 for all n ≥ 2.

So to solve the problem one need to just output 25. There is no need to read n.

B. Moore's Law

Every second the number is multiplied by 1.000000011. Multiplication several times to the same number is equivalent to exponentiation. So the formula is n·1.000000011^t (1.000000011 raised to the power of t and then multiplied to n). In a program one should not use a loop to calculate power as it is too slow for such big n, usually a programming language provides a function for exponentiation such as pow.

C. Lucky Numbers

There are 2 lucky numbers of the length 1. They are 7 and 8. There are 4 lucky numbers of the length 2. They are 77, 78, 87 and 88. There are 8 lucky numbers of the length 3. They are 777, 778, 787, 788, 877, 878, 887, 888. For each addition of 1 to the length the number of lucky numbers is increased times 2. It is easy to prove: to any number of the previous length one can append 7 or 8, so one number of the prevous length creates two numbers of the next length.

So for the length n the amount of lucky numbers of the length exactly n is 2ⁿ. But in the problem we need the amount of lucky numbers of length not greater than n. Let's sum up them. 2¹ = 2, 2¹ + 2² = 2 + 4 = 6, 2¹ + 2² + 2³ = 2 + 4 + 8 = 14, 2¹ + 2² + 2³ + 2⁴ = 2 + 4 + 8 + 16 = 30. One can notice that the sum of all previous powers of two is equal to the next power of two minus the first power of two. So the answer to the problem is 2^n + 1 - 2.

One of the possible implementations of 2^n + 1 in a programming language is to shift 1 bitwise to the left for n + 1 binary digits or to shift 2 bitwise to the left for n binary digits. For example, in Java the problem answer formula is (2L << n) - 2, in C++ is (2LL << n) - 2. Suffixes L and LL correspondingly are required so that result of the shift expression have 64-bit integer type (long in Java and long long in C++). Type of the second operand does not matter for the type of shift expression, only the type of the first operand. Also parenthesis are required because without them subtraction is performed first and only then bitwise shift.

D. Hexagons!

Let's count the number of cells having the distance of exactly n. For n = 0 it is 1, for n = 1 it is 6, for n = 2 it is 12, for n = 3 it is 18 and so on. One can notice that n = 0 is a special case, and then the amount increases by addition of 6. These numbers form an arithmetic progression. In the problem we need to sum these numbers. The formula of the sum of an arithmetic progression is (first + last)·amount / 2. The first is 6, the last is 6n, the amount is n. So the sum is (6 + 6n)n / 2 = 3(n + 1)n. And plus 1 that is not in the arithmetic progression. So the final formula is 1 + 3n(n + 1).

To avoid overflow, multiplication in the formula should be performed in 64-bit integer type. For this either 3 or 1 or n should have 64-bit integer type. The literals are 64-bit integer when they have suffix L in Java or LL in C++.

E. A rectangle

Let's see how the number of affected cells changes depending on the column. For example 3, 2, 3, 2, 3. That is it alternates between the size of the first column and the size of the first column minus one. The amount of "minus ones" is the amount of columns divided by 2 rounded down. Without "minus ones" all columns have equal size and the total amount of cells is equal to size of the first column multiplied by the number of the columns. The first column size is (y₂ - y₁) / 2 + 1. The columns amount is x₂ - x₁ + 1. So the final formula is ((y₂ - y₁) / 2 + 1)·(x₂ - x₁ + 1) - (x₂ - x₁) / 2.

To avoid overflow, multiplication should be computed in 64-bit integer type.

F. Selection of Personnel

The amount of ways to choose a group of 5 people from n candidates is equal to the number of combinations , the amount of ways to choose a group of 6 people from n candidates is , the amount of ways to choose a group of 7 people from n candidates is , the amount of ways to choose a group of 5, 6 or 7 people from n candidates is .

To avoid 64-bit integer overflow can be calculated in the following way: n / 1 * (n - 1) / 2 * (n - 2) / 3 * (n - 3) / 4 * (n - 4) / 5 * (n - 5) / 6 * (n - 6) / 7. Each division returns an integer because each prefix of this formula after division is also the number of combinations .

G. Challenge Pennants

First of all, ways to place both types of the pennants are independent. So each way to place "I fixed a critical bug" pennants on n tables is compatible to each way to place "I suggested a new feature" pennants on n tables. Therefore the answer of the problem is equal to the number of ways to place "I fixed a critical bug" pennants multiplied by the number of ways to place "I suggested a new feature" pennant.

The number of ways to place k identical items into n different places when any place can contain any amount of items is the definition of the number of k-combinations with repetitions or k-multicombinations. The formula for the number is .

So the whole formula for the problem is .

To avoid overflow of 64-bit integer type recommended formulas for computation are (n + 2) / 1 * (n + 1) / 2 * n / 3 and (n + 4) / 1 * (n + 3) / 2 * (n + 2) / 3 * (n + 1) / 4 * n / 5.

H. Benches

The number of ways to choose 5 east to west paths that will have benches from n is . There are n ways to place a bench on the first of these paths. Given the place of the first bench there are n - 1 ways to place a bench on the second of these paths because one of north to south paths is already taken. Given the places of the first and second benches there are n - 2 ways to place a bench on the third of these paths because two of north to south paths are already taken. And the same way n - 3 and n - 4 for the fourth and the fifth benches. Total number of ways to place benches on selected 5 east to west path is n(n - 1)(n - 2)(n - 3)(n - 4). So the formula for the problem is .

To avoid 64-bit integer overflow recommended order of computation is exactly as in the formula above, division should not be the last operation.

I. Parking Lot

There are the following ways to place n cars of the same make. They can be the first n, the last n, or they can be somewhere in the middle of the parking lot.

When n cars of the same make are the first or the last, there are 4 ways to choose the make of these n cars, then there are 3 ways to choose the make of one car adjacent to them (the make should be different from the make of n cars) and there are 4 ways to choose the make of each of the remaining n - 3 cars. So the formula for the case of n cars of the same make on either end of the parking lot is 4·3·4^n - 3.

When n cars of the same make are situated somewhere in the middle, there are 4 ways to choose the make of these n cars, then there are 3 ways to choose the make of each of two cars adjacent to them (the makes of these two cars should be different from the make of n cars) and there are 4 ways to choose the make of each of the remaining n - 4 cars. So the formula for the case of n cars of the same make on a given position somewhere in the middle of the parking lot is 4·3²·4^n - 4.

There are 2 positions of n cars of the same make in the end of the parking lot and there are n - 3 positions of n cars of the same make somewhere in the middle of the parking lot. So the final formula is 2·4·3·4^n - 3 + (n - 3)·4·3²·4^n - 4.

J. Divisibility

Let's factorize numbers from 2 to 10. 2 = 2, 3 = 3, 4 = 2², 5 = 5, 6 = 2·3, 7 = 7, 8 = 2³, 9 = 3², 10 = 2·5. If a number is divisible by all numbers from 2 to 10, its factorization should contain 2 at least in the power of 3, 3 at least in the power of 2, 5 and 7 at least in the power of 1. So it can be written as x·2³·3²·5·7 = x·2520. So any number divisible by 2520 is divisible by all numbers from 2 to 10.

There are numbers from 1 to n divisible by all numbers from 2 to 10. In a programming language it is usually implemented as simple integer division.

K. Indivisibility

The amount of numbers from 1 to n not divisible by any number from 2 to 10 is equal to the amount of all numbers from 1 to n (that is n) minus the amount of numbers from 1 to n divisible by some number from 2 to 10.

The set of numbers from 1 to n divisible by some number from 2 to 10 can be found as union of the set of numbers from 1 to n divisible by 2, the set of numbers from 1 to n divisible by 3 and so on till 10.

Note that sets of numbers divisible by 4 or 6 or 8 are subsets of the set of numbers divisible by 2, and sets of numbers divisible by 6 or 9 are subsets of the set of numbers divisible by 3. So there is no need to unite 9 sets, it is enough to unite sets for 2, 3, 5, 7 only.

The size of set of numbers from 1 to n divisible by some of 2, 3, 5, 7 can be calculated using inclusion-exclusion principle that says that size of each single set should be added, size of pairwise intersections should be subtracted, size of all intersections of three sets should be added and so on.

The size of set of numbers from 1 to n divisible by 2 is equal to , the size of set of numbers from 1 to n divisible by 2 and 3 is equal to and so on.

The final formula is

Division with rounding down in the formula in a programming language is usually just integer division.

L. Cracking the Code

In this problem just implementation of the actions described in the statement is required. However there are two catches in this problem.

The first catch is that the fifth power of five-digit number cannot be represented by a 64-bit integer. But we need not the fifth power, we need the fifth power modulo 10⁵. And mod operation can be applied after each multiplication (see problem A above).

The second catch is that you need to output five digits, not the fifth power modulo 10⁵. The difference is when fifth digit from the end is zero. To output a number with the leading zero one can either use corresponding formatting (%05d in printf) or extract digits and output them one by one.

M. Turn

First of all, let's reduce camera rotation angle to [0, 359] degrees range. It is accomplished by the following C++/Java code: angle = (angle % 360 + 360) % 360;

Then there are the following cases:

• [0, 44] degrees — no need to rotate,
• 45 degrees — 0 or 1 turn to minimum deviation, minimum is 0,
• [46, 134] degrees — one turn required,
• 135 degrees — 1 or 2 turns to minimum deviation, minimum is 1,
• [136, 224] degrees — two turns required,
• 225 degrees — 2 or 3 turns to minimum deviation, minimum is 2,
• [226, 314] degrees — three turns required,
• 315 degrees — 3 or 0 turns to minimum deviation, minimum is 0,
• [316, 359] degrees — no need to rotate.

Let's add 44 degrees to the angle from the range [0, 359]. C++/Java code is angle = (angle + 44) % 360; Then the ranges will be:

• [0, 89] degrees — 0 turns,
• [90, 179] degrees — 1 turn,
• [180, 269] degrees — 2 turns,
• [270, 358] degrees — 3 turns,
• 359 degrees — 0 turns.

One special case of 359 degrees can be eliminated by taking angle modulo 359. Then just integer division by 90 is required to get the answer. C++/Java code is answer = (angle % 359) / 90;

N. Forecast

There is nothing special in solving a quadratic equation but the problem has one catch. You should output the greater root first.

The simplest approach is to output max(x₁, x₂) first, then min(x₁, x₂).

Another approach is based upon the sign of a.

for a > 0 and for a < 0.

We can divide all coefficients by a, and then the first coefficient will be positive. But notice that division should be done in a floating point type and a should be divided last otherwise resulting a / a = 1 would not be able to divide b and c.

O. Arrow

To get a vector of the given length b in the direction of the given vector (vx, vy) it is just required to normalize the given vector (divide it by its length) and then multiply by b.

Let's denote , vnx = vx / len, vny = vy / len. Then (vnx, vny) is the normalized vector, and the first point of the arrow is (px + vnx·b, py + vny·b).

To get the second point of the arrow one needs to rotate the normalized vector 90 degrees counter-clockwise and then multiply by the half of the triangle base a / 2. Let's denote vlx =  - vny, vly = vnx. Then (vlx, vly) is the normalized vector 90 degrees counter-clockwise to (vnx, vny). So the second point of the arrow is (px + vlx·a / 2, py + vly·a / 2).

The third point can be found the same way as the second point but the length of the vector to it is c / 2. So the third point of the arrow is (px + vlx·c / 2, py + vly·c / 2).

The fourth point can be found by adding the vector of the length c / 2 to the left of the given and the vector of the length d reverse to the given. So the fourth point of the arrow is (px + vlx·c / 2 - vnx·d, py + vly·c / 2 - vny·d).

The remaining points are symmetrical to the points discussed above so they can be obtained the same way, just using minus for (vlx, vly) instead of plus. So the next points are (px - vlx·c / 2 - vnx·d, py - vly·c / 2 - vny·d), (px - vlx·c / 2, py - vly·c / 2), (px - vlx·a / 2, py - vly·a / 2).

Editorial of problems P and Q will appear here in a few hours.

R. Game

For the field of an even size there is a winning strategy for the second player. Namely, to paint a cell that is symmetrical with respect to the center of the field to the cell painted by the first player on the previous turn. After each turn of the second player the field is centrosymmetrical and so there is always a cell that can be painted that is symmetrical with respect to the center of the field to any cell that the first player can choose to paint.

....  1...  .1..  ....  ....
....  ....  ....  1...  .1..
....  ....  ....  ...2  ..2.
....  ...2  ..2.  ....  ....

For the field of an odd size there is a winning strategy for the first player. Namely, on the first turn to paint the central cell, then to paint a cell that is symmetrical with respect to the center of the field to the cell painted by the second player on the previous turn. After each turn of the first player the field is centrosymmetrical and so there is always a cell that can be painted that is symmetrical with respect to the center of the field to any cell that the second player can choose to paint.

.....  2....  .2...  ..2..  .....
.....  .....  .....  .....  .2...
..1..  ..1..  ..1..  ..1..  ..1..
.....  .....  .....  .....  ...1.
.....  ....1  ...1.  ..1..  .....

So for even n the answer is 2, for odd n the answer is 1. One of the possible formulas for the problem is .

n can be up to 10¹⁸ so at least 64-bit integer type should be used to input it.