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

Автор Salat, 15 лет назад, По-русски

Впечатления от TopCoder’а: Все так быстро происходит, что я успел только понять эти задачи.

1 ЗАДАЧА

Минут тридцать пытался понять чего тут хотят та, таки понял, написал решение, но кто-то очень умный решил меня challenge’нуть, от чего мне не удалось набрать больше нуля баллов.

Условие:

Про кроликов. Надо подсчитать кол-во прыжков которые кролики могут сделать при трех условиях:

-              Кролик не может перепрыгнуть сразу через двух кроликов

-              Кролик не может прыгнуть на место другого кролика

-              Кролик должен прыгать только на место 2*b-a

Кролики стоят в ряд например {5,8} это координаты двух кроликов на прямой.

 

2 ЗАДАЧА

Тут я сразу понял чего хотят, но времени на написание решения уже не было.

Условие:

Все кролики хотят быть пронумерованными, всего их n, i–ый кролик может быть пронумерован от 1 до max[i] включительно. Определить кол-во способов, которыми можно пронумеровать всех кроликов.

Например : 4 кролика {4,4,4,4}

Тогда у первого кроля 4 способа выбрать номер, у третьего осталось три способа, и.т.д.

Получается 24 = 4*3*2*1 способа всего.

 

3 ЗАДАЧА

Не понятно как решать, такую задачу.

Условие:

Есть колода карт, на каждой из них записано какое-то число, типа double. Теперь нужно удалить две карты из колоды, их числа либо сложить, либо умножить, результат записать на новую карту и вставить в колоду. Повторить эти действия до тех пор, пока в колоде не останется одна карта.

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

 

После кодинга наступает затишье, вроде три минуты. После чего участники пытаются, валить друг друга.  МОЖНО СМОТРЕТЬ ЧУЖИЕ РЕШЕНИЯ, и стрелять по ним.  Вот и все.


Итог: рейтинг 806.

Вывод: быстрее соображать надо.

Вердикт: accepted.

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

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

В подавляющем большинстве случаев неважно, челленджат тебя или нет -- если никто не свалил плохое решение, оно обычно падает на систесте. Исключение -- хэши, к которым обычно надо специально подбирать коллизии.

В третьей задаче (nisoku) все упрощается за счет нижнего огранения на число: полтора. Благодаря этому каждое число может участвовать в сложении только один раз, а производные от сложения потом складывать смысла не имеет. Это позволило бы свести задачу к получению паросочетания максимальной стоимости, но существует более простое жадное решение: нужно отсортировать все числа, потом 2*K минимальных из них попарно сложить (начиная с двух краев и двигаясь к середине), а дальше только умножения. Решения, в основном различались выбором K (среди них много неправильных). Времени хватало на то, чтобы попробовать все решения K, получив решение O(N^2).

  • 15 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    спасибо=) 
    попробую отсортировать сложить и умножить.