IPSC 2009 :: отчет
Результаты IPSC 2009, в личном зачете. Мой результат — эпик фейл (виноваты, конечно, жара и шум).
PDF с задачами
PDF с решениями
A
Реализовать симуляцию простого калькулятора (без скобок, без приоритетов) с весьма скромными ограничениями.
Сложно не суметь.
B
Шары катаются и сталкиваются в ящике, найти их положение, отсортированное по x и y, через некоторое время.
Т.к. шары не нужно нумеровать, любое столкновение можно рассматривать, как отсутствие столкновения. Поэтому используем стандартный трюк: всю плоскость представляем, как бесконечно размноженный ящик. Тогда шары двигаются по прямой, а для нахождения конечного положения нужна простая трансформация остатка от деления координат на размеры ящика.
C
Даны картинки с перфокартами, и надо понять, что от нас хотят.
Easy: первая, вторая и четвертая перфокарты задают строковое описание арифметической операции, но третья является т.н. lace card, забивающей картоприемник, заставляя тем самым игнорировать четвертую.
Hard: 9 перфокарт содержат программу на Фортране с тремя трюками: на перфокартах колонки 73-80 игнорируются; строка, начинающаяся с первой колонки на символ C, является комментарием; если в колонке 6 есть символ, строка, его содержащая, является продолжением предыдущей.
Позор на мою седую голову, изучавшую в детстве отцовские конспекты по перфокарточному Fortran IV на IBM 360!
D
В этой задаче за каждый WA дается −40 к штрафу. Проблема только в том, что WA получить очень тяжело — надо подобрать не повторяющиеся хитрые числа, и количество сабмитов, как и везде, ограничено 10. В easy надо найти число n, такое, что n, n+18, n+36, n+138, n+198, n+240, n+258 взаимно просты со всеми меньшими числами и не равны 1 по модулю 4. В hard надо найти число x такое, что x2 − 1 делится на 6550766734437075510991430716180516667142
Easy: решетом Эратосфена находим примерно 5кк простых чисел между требуемыми в программе 100000000 и 198765432, после чего перебором с помощью set находим за NlogN 14 удовлетворяющих чисел.
Hard: чтобы найти квадратные корни единицы над ZN, надо факторизовать (например, методом эллиптических кривых) N, и методом двухстраничных авторских выкладок под знаменем китайской теоремы прийти к расширенному алгоритму Евклида, который и выдаст из 3 делителей N 8 корней, 7 из которых подходят.
E
В этой задаче правильную скобочную последовательность рисуют и закрашивают примерно так:
(())(()(())) →
Нужно найти площадь, закрашенную черным.
Решением является конечный автомат, при открытии скобки запихивающий в стек запись об ее позиции и высоте 1, и увеличивающий высоты всех предыдущих открытий, если их не хватает; при закрытии к результату добавляется или вычитается, в зависимости от четности уровня, площадь прямоугольника соответствующей длины и высоты. Важно не забыть, что hard-тест достаточно большой, чтобы результат не помещался в int.
F
Надо сыграть в хитрую Flash-игру и выиграть.
См. авторское решение.
G
Дан вектор b, найти количество размещений a1..K K по N таких, что ai ≥ bi.
См. авторское решение.
H
На торе 30x30 есть несколько волков и овец. Надо сыграть с сервером и сожрать 10 (easy) или 60 (hard) овец.
См. авторское решение.
I
На 26-регистровой 64-битной машине с командами mov, &, |, ^, ~, <<, >> надо написать 2 программы. Easy (не длиннее 64 инструкций): a + 8. Hard (не длиннее 300): найти следующее число с тем же количеством единичных бит.
См. авторское решение.
J
Найти количество рассадок K пассажиров по сетке MxN, чтобы у каждого 4-окрестность была пустой.
Hard-тест имеет довольно большие размеры сетки, поэтому надо отдельно рассмотреть случаи с K ≤ 2, ДП по профилю по минимальной стороне, и оптимизацией на случай очень большой длинной стороны с помощью быстрой матричной степени.
K
За покупки можно расплатиться либо деньгами, либо ваучерами (ваучер описывается максимальной стоимостью и номерами товаров, которые можно на него купить). Минимизировать количество заплаченных денег.
Максимальный поток, из истока в вершины ваучеров идут ребра со стоимостью ваучеров, из тех в вершины товаров ребра неограниченной емкости, из товаров в сток — со стоимостью товаров.
L
В дереве (размером до 106) несколько (до 200к раз) красят путь из одной вершины в другую в один из 7 цветов. Надо вывести для каждого цвета, сколько им окрашено ребер.
Дерево отрезков.
M
Словесно описана строка. Найти, какая из данных строк соответствует описанию. Описание вида: THE LETTER A FOLLOWED BY (ONE OF THE LETTERS abc OR THE STRING gg) AT LEAST 3 TIMES
Регекспами можно превратить строку в регексп, не забыв про специальные символы, которым следует заматчить входные строки. Пожалуй, единственная хитрость — не забыть заключить полученный регексп в скобки (чтобы было ^(a|b)$, а не ^a|b$)
1. Ural Fanclub of Ksenia Sobchak 32 2665
2. R+T+J 31 1373
3. jiong+jiong+jiong 29 1686
4. SGJL 27 1624
5. Waterloo Black 26 2163
6. MSU Unpredictable 25 1135
7. Croatia IOI team Predator (leaders) 25 2142
8. Moscow SU x13 24 746
9. KMCoders 24 1094
10. Zodiac 24 1585
12. nika+rem+irancoldfusion 23 1004
13. Gennady Team 23 1568
14. ACRush 23 1607
16. bmerry 23 1634
Личный зачет:
1. Gennady Team 23 1568
2. ACRush 23 1607
3. bmerry 23 1634
4. RAVEman 22 1471
5. WiNGeR 22 1513
6. dzhulgakov 21 758
7. Cow 21 1000
8. Jonick 21 1485
9. bhzhan 21 1995
10. ivank 20 683
UPD: Спасибо
renatm за ссылку на авторский эдиториал.
PDF с задачами
PDF с решениями
A
Реализовать симуляцию простого калькулятора (без скобок, без приоритетов) с весьма скромными ограничениями.
Сложно не суметь.
B
Шары катаются и сталкиваются в ящике, найти их положение, отсортированное по x и y, через некоторое время.
Т.к. шары не нужно нумеровать, любое столкновение можно рассматривать, как отсутствие столкновения. Поэтому используем стандартный трюк: всю плоскость представляем, как бесконечно размноженный ящик. Тогда шары двигаются по прямой, а для нахождения конечного положения нужна простая трансформация остатка от деления координат на размеры ящика.
C
Даны картинки с перфокартами, и надо понять, что от нас хотят.
Easy: первая, вторая и четвертая перфокарты задают строковое описание арифметической операции, но третья является т.н. lace card, забивающей картоприемник, заставляя тем самым игнорировать четвертую.
Hard: 9 перфокарт содержат программу на Фортране с тремя трюками: на перфокартах колонки 73-80 игнорируются; строка, начинающаяся с первой колонки на символ C, является комментарием; если в колонке 6 есть символ, строка, его содержащая, является продолжением предыдущей.
Позор на мою седую голову, изучавшую в детстве отцовские конспекты по перфокарточному Fortran IV на IBM 360!
D
В этой задаче за каждый WA дается −40 к штрафу. Проблема только в том, что WA получить очень тяжело — надо подобрать не повторяющиеся хитрые числа, и количество сабмитов, как и везде, ограничено 10. В easy надо найти число n, такое, что n, n+18, n+36, n+138, n+198, n+240, n+258 взаимно просты со всеми меньшими числами и не равны 1 по модулю 4. В hard надо найти число x такое, что x2 − 1 делится на 6550766734437075510991430716180516667142
Easy: решетом Эратосфена находим примерно 5кк простых чисел между требуемыми в программе 100000000 и 198765432, после чего перебором с помощью set находим за NlogN 14 удовлетворяющих чисел.
Hard: чтобы найти квадратные корни единицы над ZN, надо факторизовать (например, методом эллиптических кривых) N, и методом двухстраничных авторских выкладок под знаменем китайской теоремы прийти к расширенному алгоритму Евклида, который и выдаст из 3 делителей N 8 корней, 7 из которых подходят.
E
В этой задаче правильную скобочную последовательность рисуют и закрашивают примерно так:
(())(()(())) →
Нужно найти площадь, закрашенную черным.
Решением является конечный автомат, при открытии скобки запихивающий в стек запись об ее позиции и высоте 1, и увеличивающий высоты всех предыдущих открытий, если их не хватает; при закрытии к результату добавляется или вычитается, в зависимости от четности уровня, площадь прямоугольника соответствующей длины и высоты. Важно не забыть, что hard-тест достаточно большой, чтобы результат не помещался в int.
F
Надо сыграть в хитрую Flash-игру и выиграть.
См. авторское решение.
G
Дан вектор b, найти количество размещений a1..K K по N таких, что ai ≥ bi.
См. авторское решение.
H
На торе 30x30 есть несколько волков и овец. Надо сыграть с сервером и сожрать 10 (easy) или 60 (hard) овец.
См. авторское решение.
I
На 26-регистровой 64-битной машине с командами mov, &, |, ^, ~, <<, >> надо написать 2 программы. Easy (не длиннее 64 инструкций): a + 8. Hard (не длиннее 300): найти следующее число с тем же количеством единичных бит.
См. авторское решение.
J
Найти количество рассадок K пассажиров по сетке MxN, чтобы у каждого 4-окрестность была пустой.
Hard-тест имеет довольно большие размеры сетки, поэтому надо отдельно рассмотреть случаи с K ≤ 2, ДП по профилю по минимальной стороне, и оптимизацией на случай очень большой длинной стороны с помощью быстрой матричной степени.
K
За покупки можно расплатиться либо деньгами, либо ваучерами (ваучер описывается максимальной стоимостью и номерами товаров, которые можно на него купить). Минимизировать количество заплаченных денег.
Максимальный поток, из истока в вершины ваучеров идут ребра со стоимостью ваучеров, из тех в вершины товаров ребра неограниченной емкости, из товаров в сток — со стоимостью товаров.
L
В дереве (размером до 106) несколько (до 200к раз) красят путь из одной вершины в другую в один из 7 цветов. Надо вывести для каждого цвета, сколько им окрашено ребер.
Дерево отрезков.
M
Словесно описана строка. Найти, какая из данных строк соответствует описанию. Описание вида: THE LETTER A FOLLOWED BY (ONE OF THE LETTERS abc OR THE STRING gg) AT LEAST 3 TIMES
Регекспами можно превратить строку в регексп, не забыв про специальные символы, которым следует заматчить входные строки. Пожалуй, единственная хитрость — не забыть заключить полученный регексп в скобки (чтобы было ^(a|b)$, а не ^a|b$)
1. Ural Fanclub of Ksenia Sobchak 32 2665
2. R+T+J 31 1373
3. jiong+jiong+jiong 29 1686
4. SGJL 27 1624
5. Waterloo Black 26 2163
6. MSU Unpredictable 25 1135
7. Croatia IOI team Predator (leaders) 25 2142
8. Moscow SU x13 24 746
9. KMCoders 24 1094
10. Zodiac 24 1585
12. nika+rem+irancoldfusion 23 1004
13. Gennady Team 23 1568
14. ACRush 23 1607
16. bmerry 23 1634
Личный зачет:
1. Gennady Team 23 1568
2. ACRush 23 1607
3. bmerry 23 1634
4. RAVEman 22 1471
5. WiNGeR 22 1513
6. dzhulgakov 21 758
7. Cow 21 1000
8. Jonick 21 1485
9. bhzhan 21 1995
10. ivank 20 683
UPD: Спасибо
renatm за ссылку на авторский эдиториал. 