Turkmen National OI - Codeforces

№	Пользователь	Рейтинг
1	Benq	3792
2	VivaciousAubergine	3647
3	Kevin114514	3603
4	jiangly	3583
5	turmax	3559
6	tourist	3541
7	strapple	3515
8	ksun48	3461
9	dXqwq	3436
10	Otomachi_Una	3413

№	Пользователь	Вклад
1	Qingyu	157
2	adamant	153
3	Um_nik	147
4	Proof_by_QED	146
5	Dominater069	145
6	errorgorn	141
7	cry	139
8	YuukiS	135
9	TheScrasse	134
10	chromate00	133

Day1 Tasks

A. Bet you can't solve it

You need to build a stairway, which has 1.5 unit height and 4.5 unit width. Each step has to have 0.3 unit height and multiple of 0.5 unit width. How many different ways are there to build such a stairway?

Строится лестница из точки А в точку В. Растояние АС = 4.5м; ВС = 1.5м. Высота ступеньки 0.3м, ширина 0.5м или кратное 0.5м. Сколькими способами можно построить лестницу?

$\text{[math]}$ Sample stairway. $\text{[math]}$ Original images for description.

B. Piece of cake

Given matrix A[1...n][1...m], each element of which is 0, 1, 2 or 3. Find number of 4-ples A[i][j], A[i][j + 1], A[i + 1][j], A[i + 1][j + 1] where these numbers differ from each other.

Данна целочисленная матрица А[1...n][1...m],каждый элемент которой равен 0, 1, 2 или 3.Определить количество четвёрок A[i][j], A[i][j + 1], A[i + 1][j], A[i + 1][j + 1] в котором все элементы различны.

C. Strange Problem

Continue the sequence of 3-digit numbers: 215, 717, 316, 512 ...

Продолжить последовательность трёхзначных чисел: 215, 717, 316, 512 ...

D. Knights' Invasion

Find a way to place 12 knights so that every cell is either attacked or is owned by a knight.

Найти такую расстановку двенадцати коней на шахматной доске, при котором каждое поле будет находиться под ударом одного из них.

Day2 tasks are available here.

Constraints

Participant: What is the limit for N?
Jury Member: N can be anything... The limit for it is infinity...
Participant: But no computer can handle infinity? :D
Jury Member: That is your problem! You should try to solve it for infinity.

But actual tests are the ones that can be calculated by hand.

Time limit

Depends on the patience of the juries. Usually around 10 minutes.

Memory limit

Free memory available in the PC given to you.

Note1 Original blog title was «Turkmenistan National Olympiad in Informatics sucks». And it really does.
Note2 Actually tasks had no names. I gave the names.
Note3 Feel free to give your answers for A,C,D.

Комментарии (25)

Показать архивные | Написать комментарий?

artemohanjanyan

12 лет назад, скрыть # |

In A we can assume that width of each rectangle is 0.5 and do DP[width][height].

→ Ответить

accidentallygivenfuck

12 лет назад, скрыть # ^ |

Yes. Now write your solution and tell me your answer. I'll tell you if it matches the official answer.

Can you explain in more detail? Your solution seems to be incorrect. On the other hand, you can simply run 5 nested loops LOL:

for a: 0.5 ... 4.5
for b: 0.5 ... 4.5
for c: 0.5 ... 4.5
for d: 0.5 ... 4.5
for e: 0.5 ... 4.5
if a+b+c+d+e == 4.5
  res = res+1

d[0][0] = 1;
for (int i = 1; i < 9; ++i)
{
	d[i][0] = d[i-1][0];
	for (int j = 1; j < 5; ++j)
		d[i][j] = d[i-1][j] + d[i-1][j-1];
}
cout << d[8][4]; // 70 here

It's OK, but BIEmp's solution is better.

vlfom

← Rev. 15 →

In A: $\text{[math]}$ ?

← Rev. 5 →

Your solution (70) doesn't match with official one (252). 0/5 points.

But actually, yes answer is 70. But official answer was 252. When we asked juries that answer was incorrect, they defended themselves by saying that width of the stairway doesn't need to be 4.5 unit. But problem statement that was given to us is exactly same as russian version above. Let me number this as nonsense#1.

garakchy

+17

N->∞ & "Time limit depends on the patience of the juries" lmfao

Hint for D
Following is what one jury member told, when one of my friends wrote program for checking every possibility:
— This is not solved using recursion. Recursion is slow. This is solved using DP.

And don't think that he was joking. He seriously said that. Now tell me how this problem can be solved using DP. nonsense#2.

_Vadim_

dp[i][k][mask1][mask2] — true, if we can place k knights on first i rows, such that mask1 is positions of knights in (i-1)th row and mask2 is positions of knights in ith row.

Right. I didn't think about it (ДП по профилю, if I'm not mistaken). But as you can see, A is 5-loop problem, B is brute-force, C is non-IOI-like-at-all. I don't think, that jury had "ДП по профилю" in his mind when he told "... is solved with DP". He may at most mean knapsack when he says DP.

P.S. What is "ДП по профилю" in English?

← Rev. 3 →

Dynamic programming over subsets, I suppose.

P.S.: Or bitmasks.

RomaWhite

← Rev. 2 →

What is the correct answer for problem C?

+25

Let's define a sequence S.
S_i = 2ⁱ + 2 * (i mod 2) - 1
2⁰ + 1, 2¹ - 1, 2² + 1, 2³ - 1, 2⁴ + 1, ...
2, 1, 5, 7, 17, 31, 65, 127, ...
Now put all elements of S side by side. Divide the resulting string into 3-digit parts. There is your sequence:
215, 717, 316, 512 ...
Isn't this problem more suitable for April Fools' Day contest?