Результаты заочного тура

Победители заочного тура

            Информатика
     ФИО участника     Класс   № ОУ      Территория  
Филимонов Владислав      9      205     Екатеринбург 
Лихоманов Константин     9       5      Екатеринбург 
Дементьев Дмитрий        10    СУНЦ     Екатеринбург 
Зайникаев Алексей        10     68      Екатеринбург 
Иванков Дмитрий          10    СУНЦ     Екатеринбург 
Скробов Артем            11    СУНЦ     Екатеринбург 
Коромыслов Андрей        11     35      Екатеринбург 
Правдин Сергей           11     110     Екатеринбург 
Елькин Кирилл            11     135     Екатеринбург 
Титаренко Иван           11     110     Екатеринбург 
Плющенко Андрей          11     22      Екатеринбург 
Орлов Вячеслав           11     18      Н.Тагил    
Блейхер Александр        11     18      Н.Тагил   
Рыжков Сергей            9      32      Первоуральск 
Шведов Сергей            10      7      Первоуральск 

Правила выставления оценок за задачи

Оценки выставлялись по следующей шкале:
20 баллов - задача решена правильно и оптимально.
15 - то же, но некоторые огрехи в исполнении. Эта оценка ставилась крайне редко.
10 - задача решена правильно, но не оптимально. Т.е. использовался не лучший алгоритм, а решенние "в лоб". Подробнее - в комментариях к задачам.
5 - Решен частный случай, т.е. выдается правильный ответ только в части случаев.
1 - решен совсем уж частный случай.

Подробнее о задачах

1. Слово.

Правильное решение. Ищем последнюю пару букв, стоящих в алфавитном порядке. Заменяем первую из этих букв на ближайшую из следующих после нее и сортируем следующие после нее буквы по алфавиту.

Те, кто решал задачу так, получили по 20 баллов. Остальные решения как правило валились на элементарном тесте abdc, отвечая не acbd, а adbс или что-либо еще. Они получали по 5 баллов.

2. Минералка.

Правильный ответ - k*k*k*k + k - 1. Нужно было просто посчитать ответ по формуле. Те, кто отвечал k*k*k*k*k, получали 0 баллов.

Те, кто перебирал ответ, проверяя каждое целое число, начиная с какого-то, получал 10 баллов.

Представьте, сколько будет работать такое решение, если k=1000;

3. Родословная.

Надо было проверить не только то, что теленок не является своим родителем или является одновременно и коровой, и быком, но и то, не является ли он своим дальним предком. Более того, это надо было сделать эффективно. Например, для каждого теленка создать список, состоящий только из него. Потом добавлять в список родителей тех, кто в нем уже есть, но для которых эта операция еще не была проделана. Очевидно, в конце концов этот процесс прекратится за недостатком информации (для всех тех, кто в списке уже есть, родители либо уже добавлены, либо неизвестны). Очевидно, так мы очень быстро получим список предков теленка. Если у кого-то в этом списке родитель - этот самый теленок, то значит, мы нашли противоречие.

Многие решали рекурсивно, т.е. не оптимально. Они получили по 10 баллов.

Большинство вообще этот случай не рассматривали и получили по 5 баллов.

И еще. Не надо генерировать паспорта случайным образом. Данные должны вводится пользоватем.

4. Точки в круге.

Разумеется, число точек в круге не равно целой части его площади. Такие решения получали 0 баллов. И не надо фиксировать центр в начале координат и потом удивлятся, что задача решается только для ввода вида 4k+1. Надо просто подобрать точку так, что расстояния от нее до всех точек сетки различно. Хотя бы просто взять точку с псевдослучайными координатами и менять ее, если она вдруг не подойдет.

После этого можно, например, взять все точки в заведомо большом квадрате (т.е. все точки, которые лежат в искомой окружности, лежат и в этом квадрате). Отсортировать расстояния от них до центра. И взять (n-1)-е из них. Это и будет наш радиус.

Почти все, кто решал эту задачу, получили 20 баллов. Кроме того решения, в котором перебирались радиусы с маленьким шагом и которое работало очень долго - оно получило 10 баллов.

5. Лабиринт.

Решение.

а) Восстановить известную чать лабиринта по маршруиу путника.

б) Найти в ней кратчайший путь от финиша к старту методом волны.

Что такое метод волны - читайте в первой главе любого учебника по алгоритмам.

Большинство решающих искало решение методом срезания петель. Это частное решение, т.к. срезав где-то короткую петлю можно потерять возможность срезать более длинную. Они получили 5.

Также многие исходили из ошибочного предположения, что стен в лабиринте нет и можно идти напрямик, т.е. подсчитать, сколько до старта клеток на север и на восток и потом просто пройти соответствующее расстояние сначала на север, а потом на восток. Такие решения получали 1 балл.

Остальные (неофициальные) результаты заочного тура

            Информатика
           ФИО участника     Класс Прошли!!      Оценки
Ин-45 Мусихин Александр                     35
Ин-12 Куделевский Евгений      7            23
Ин-21 Барабошкин Николай       7            не та ол.
Ин-11 Пермяков Александр       8            30
Ин-13 Куколев Владимир         8            0
Ин-22 Запрудин Михаил          8            25
Ин-42 Грегер Ольга             8            не та ол.
Ин-1  Филимонов Владислав      9       *    70
Ин-28 Лихоманов Константин     9       *    45
Ин-35 Рыжков Сергей            9       *    65
Ин-36 Юркин Евгений            9            25
Ин-2  Дементьев Дмитрий        10      *    80
Ин-3  Закоптелков Владимир     10           0
Ин-5  Шведов Сергей            10      *    85
Ин-15 Зарипов П.               10           30
Ин-16 Переверзев Андрей        10           50
Ин-17 Зайникаев Алексей        10      *    65
Ин-19 Шигайкин Алексей         10           30
Ин-20 Зыкин Сергей             10           25
Ин-24 Константинов Андрей      10           дискета не зап.,
Ин-26 Лапшин Андрей            10           10
Ин-27 Иванков Дмитрий          10      *    85
Ин-34 Киселев Дмитрий          10           26
Ин-38 Скорынин Дмитрий         10           не та ол.
Ин-53 Жуков Сергей             10           15
Ин-4  Кушкин Сергей            11           50
Ин-6  Скробов Артем            11
Ин-7  Майорский Константин     11           50
Ин-8  Коромыслов Андрей        11      *    70
Ин-9  Правдин Сергей           11      *    65
Ин-10 Елькин Кирилл            11      *    80
Ин-14 Титаренко Иван           11      *    55
Ин-23 Шумков Евгений           11           15
Ин-25 Матвеев Андрей           11           40
Ин-29 Плющенко Андрей          11      *    100
Ин-30 Крестьянников Павел      11           30
Ин-31 Головнин Александр       11           30
Ин-32 Орлов Вячеслав           11      *    75
Ин-33 Тронин Роман             11           35
Ин-39 Засорин Андрей           11           16
Ин-40 Вахрушев Игорь           11           не та ол.
Ин-41 Москвин Иван             11           не та ол.
Ин-43 Шамшурин Павел           11           46
Ин-46 Гунько Сергей            11           25
Ин-48 Суслов Александр         11           36
Ин-54 Суслов Александр         11            --//--
Ин-55 Букланов Александр       11           50
Ин-18 Зайков Максим                         15
Ин-37 Анатолий                              не та ол.
Ин-44 Сергеев Андрей                        31
Ин-47 Зыкин Сергей                          25
Ин-49 Исенбаев Владислав                    0
Ин-50 Белецкий Иван                         10
Ин-51 Шамшурин Павел                        46
Ин-52 Тронин Роман                          40
      Лялин Александр          11           6
      Блейхер Александр                *    65

      48 оценок
      14 рекомендованы
      6 - не та олимпиада
      1 - дискета не читается, алгоритма нет