Turkmen National OI — Day 2

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

A. Camel Caravan

There is a caravan of n camels. You are fed up with seeing the same camel day after day. Now you wonder, how many ways are there to reorganize the camels, so that no camel sees the same camel as before?

По пустыне идет караван из n верблюдов. За много дней путешествия надоедает идеть впереди себя одного и того же верблюда. Сколькими способами можно переставить верблюдов так, чтобы впереди каждого шел другой верблюд, чем до этого?

I had an argument with juries about what this task asks. I would be glad if you read russian version (which is official), and tell answers for n = {1, 2, 3, 4, 5}.

B. Magic is Might

Given natural number k. Find k^th number in the sequence consisting of powers of 2: 2481632...
For example for k = 4 answer is 1.

Задано некоторое натуральное число k. В последовательности 2481632... составленная из степеней 2 найти цифру стояшей на k - ом месте.
Например для k = 4 ответ 1.

C. Tom Marvolo Riddle

Given n natural numbers. Find smallest natural number, which can not be represented as sum of given numbers, if in the representation one number can be used only once.

Даны n натуральных чисел. Найти минимальное натуральное число, непредставимое суммой никаких из этих чисел, если в сумму каждое исходное число может входить не более одного раза.

D. Fractions

Given natural number n. Find all irreducible regular fractions $\text{[math]}$ where i is in range [1, n - 1].

Дано натуральное число n. Найти все несокротимые правильные дроби, знаменатель которых равен n, а числитель принимaет значения, находящиеся в диапазоне [1...n - 1].

Time & Memory Limits

You can find details here.

Natural numbers

I hate problem statements where term "natural number" is used. You can't know if zero is included or not. And when I asked if zero is included or not in TKMNOI, I recieved "10th grade and you don't know that?!", when the whole world doesn't know that.

Note 1: As you may have noticed I couldn't come up with good task names, because these tasks don't deserve good names :D
Note 2: Feel free to leave comments about tasks and their solutions.

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

Написать комментарий?

JuanMata

11 лет назад, # |

← Rev. 6 →

for problem D, if u just want the number of such fractions then it's simply the Euler totient function of $\text{[math]}$ and can be solved in $\text{[math]}$ (using Euler's product formula).
if u want all such fractions to be printed, then it can be solved in $\text{[math]}$ by iterating over all integers in the range and checking if $\text{[math]}$ or not.

EDIT: can anyone help me with why the link i posted is not working? thanks!

→ Ответить

IlyaCk

Why 10 days between these posts? Really approximately 10 days between tours???

accidentallygivenfuck

11 лет назад, # ^ |

No =) There is not even a day between 2 tours. It's just because I'm a lazy guy =)

bnurgeldiyev514

-11

Dowletdaki berlen mysallarmy...?

← Rev. 3 →

Howa

EDIT: Translation: "Are these tasks national olympiad tasks?", "Yes".

Пожалуста помогите на задаче А...

mmaxio

http://oeis.org/A000255

← Rev. 2 →

(No Russian anymore :D I have used my all Russian skills and suffered enough to write the above message LOL).

Official answers were {0, 2, 2, 3, 4} instead of {1, 1, 3, 11, 53}. So I guess, I am the one who understood the problem correctly. Let's say n = 3. Now lets list permutations of {1, 2, 3}:

state 1 : 1-2-3 (original state of camels)
state 2 : 1 3 2 (OK)
state 3 : 2 1 3 (OK)
state 4 : 2-3 1 (BAD 2 is followed by 3)
state 5 : 3 1-2 (BAD 1 is followed by 2)
state 6 : 3 2 1 (OK)

As you see answer is 3.

But juries say: it should be 2 because in the 6th state "2 is followed by 1" and "2 is already followed by 1" in the 2nd state too.

But I told them that I am just listing all possibilities and checking if they are OK or not and there is no relationship between 2nd and 6th state. But they turned out to be dumber than I expected.

Yeah, they really drove me crazy this year. Thank god, IOI selections are seperate from National Olympiad.

Xellos

You can't know if zero is included or not.

You can in this case. n can't be 0, or you'd divide by 0.

Honestly, I don't remember when I asked that question. Maybe it was last year. But it was necessary to know that. Otherwise I wouldn't have asked that. :)

marat.snowbear

... you'd divide by 0.

Based on this entire post, I'd say that such a minor issue won't stop jury from treating zero as a natural number.

Yeah, well, the answer they expect can be literally anything.

osmanuss

guys to be frankly the programming is very low in Turkmenistan i mention teachers.. we have good programmers, but not good teachers.. so if u find any mistake on their solutions or questions they are getting mad. they are even not allowing to discuss on these things. as i mentioned before we need improvement.. their way of thinking is student can never reach teachers level on programming.. so so i hope u understand our situation. by the way sylap97 (who wrote this blog) could not get achievement on that TNOI. and eventually he got rabid. calm down bro as far as i know me too could not get any place .. try to put up with these useless stuffs..

Guwanch1

3 года назад, # |

How did you solve problem A?

exhausted

3 года назад, # ^ |

чел хорош