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