accidentallygivenfuck's blog

Turkmen National OI — Day 2
By accidentallygivenfuck, 10 years ago, In English

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.

  • Vote: I like it
  • +14
  • Vote: I do not like it

»
10 years ago, # |
← Rev. 6   Vote: I like it +3 Vote: I do not like it

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!

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
10 years ago, # |
  Vote: I like it -11 Vote: I do not like it

Dowletdaki berlen mysallarmy...?

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

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

      → Reply
»
10 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

→ Reply
»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

How did you solve problem A?

→ Reply