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

Помогите пожалуйста решить задачу Scales с IOI 2015.
Автор Barsic, история, 8 лет назад, По-русски

Здравствуйте уважаемые читатели. Скажите пожалуйста как решить задачу Scales ( ENG RUS ). ( с IOI 2015 день 1 ).

Прошлый вопрос : можете сказать где можно найти разборы задач прошедших IOI на русском? ( чем больше разборов прошедших лет, тем лучше ) Огромное Спасибо.

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

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

Auto comment: topic has been translated by Barsic (original revision, translated revision, compare)

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

Did you read Problems and Solutions section at official website?

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

    Thank you. I read analysis. And want to solve problem with such algorithm :

    1) make list of comparison ( first, second ) where we put pair ( first, second ) when we know that first < second.

    2) look all permutations of { 1, 2, 3, 4, 5, 6 } ( with next permutation() in C++ ).

    2.1) if current permutation does not satisfy to list of comparison then look next permutation.

    2.2) if current permutation are satisfy to list of comparison then in this permutation find pair P[i] and P[i + 1] which not situated in list of comparison, compare them and add the result to list of comparison.

    We continue this procedure untill permutations are not finished or we not compare more than 6 founded pairs ( P[i], P[i + 1]). At the end we found right permutation.

    In this problem T <= 18 and all permutation of { 1, 2, 3, 4, 5, 6 } = 6! = 720 then O(18 * 780) = O (12960).

    No more than 1 second. But I got TL. Here is my code. Can you say where my mistake or show another solution with realization?

    Thank you.

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

      Hi, it seems to me, that your code runs into an infinite loop, for example when the output would be {1,2,3,4,5,6}, since at the start of the "while(1==1)" loop k==0, and you only increase k 5 times (in the inner loop after if(t==1), for i=0..4), so k will remain 5 throughout the execution, therefore you don't execute the break; command (if(k>6) break;). On the other hand since t always remains 1, you don't execute the other break; command either (if((t==0) && ...) break;), so you never jump out of the while loop.

      I hope, I am not missing anything. :)

      → Ответить