Блог пользователя accidentallygivenfuck

Turkmen National OI — Day 2
Автор accidentallygivenfuck, 11 лет назад, По-английски

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 kth 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 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.

  • Проголосовать: нравится
  • +14
  • Проголосовать: не нравится

»
11 лет назад, # |
← Rev. 6   Проголосовать: нравится +3 Проголосовать: не нравится

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

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

→ Ответить
»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
»
11 лет назад, # |
  Проголосовать: нравится -11 Проголосовать: не нравится

Dowletdaki berlen mysallarmy...?

→ Ответить
»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    http://oeis.org/A000255

    → Ответить
    • »
      »
      »
      11 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      (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.

      → Ответить
»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится 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. :)

    → Ответить
  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    ... 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.

    → Ответить
»
11 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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..

→ Ответить
»
3 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

How did you solve problem A?

→ Ответить