Главная
Блог разработчиков phpBB
 
+ 17 предустановленных модов
+ SEO-оптимизация форума
+ авторизация через соц. сети
+ защита от спама

Russian Code Cup 2013: разбираем задачи финала

Anna | 24.06.2014 | нет комментариев

23 сентября 2012 года состоялся финал чемпионата по программированию Russian Code Cup 2013.

Первое место занял Петр Митричев (кстати, чемпион RCC 2011). 2-й приз взял Геннадий Короткевич, третье — Дмитрий Джулгаков.

Сегодня мы публикуем подробнейший разбор шести задач, которые были предложены финалистам RCC (спойлер: одна из них так и осталась нерешенной). В программе — сортировка небывалой быстроты, единоборство с капибарным гриппом, путешествия роботов и многое другое.

Задача А. Терпение

Идея: Артем Васильев
Реализация: Артем Васильев
Разбор: Артем Васильев

Условие:
Лимитация по времени: 2 секунды
Лимитация по памяти: 256 мегабайт

Хулиганы Петя и Вася сидят на непереносимо тоскливом уроке. Для того Дабы как-то развлечься, они решили поиграть с терпением педагога. ?рус недовольства педагога ребятами выражается целым числом x. Петя и Вася по очереди делают разные мелкие и огромные шалости, Петя делает шалость первым. Позже мелкой шалости ярус недовольства педагога возрастает на 1, позже большой шалости — возрастает в 2 раза. Тот ученик, позже шалости которого негодование педагога становится огромнее чем n, получает выговор от педагога и приходит позже уроков с родителями к директору. Безусловно, ни Вася, ни Петя такому исходу не рады, и следственно всякий из них действует оптимально, Дабы избежать этого.

Ребята играют в эту игру всякий день. С всяким днем исходное негодование педагога растет: в 1-й день оно равнялось 1, во 2-й день — 2, и так дальше. В i-й день первоначальное негодование педагога учениками равно i. Каждого в году ровно n учебных дней, то есть в конечный день учебы негодование педагога равно n и любая шалость учеников мигом выводит его из себя.

Отличнику Коле тоже дюже уныло на уроке, чай он теснее знает все, что рассказывает педагог. Коля подметил необычную игру Пети и Васи и легко узнал, кто пойдет за родителями в всякий учебный день. Некогда Коля заметил, что Вася пошел за родителями ровно в k-й раз. Определите, в какой по счету учебный день это случилось?

Скажем, пускай n = 4. В 1-й день исходное негодование педагога равно 1. Какую бы шалость ни совершил Петя, негодование педагога станет равно 2. Позже этого Вася делает большую шалость, и негодование педагога становится равно 4. Сейчас, какую бы шалость ни совершил Петя, он получит выговор и пойдет за родителями. Во 2-й учебный день исходное негодование педагога равно 2. Сейчас Петя делает огромную шалость и вынуждает Васю получить выговор. В 3-й учебный день Петя добивается того же результата, совершив мелкую шалость. В конечный же — четвертый — учебный день Петя получит выговор, от того что он должен совершить шалость первым. Таким образом, если Коля видит, что Вася пошел за родителями в 1-й раз, дозволено сделать итог, что теперь 2-й учебный день, а если Вася пошел за родителями во 2-й раз, то теперь 3-й учебный день.

Формат входных данных
Первая строка содержит целое число T (1 > Будем строить это уйма рекурсивно. Пускай процедура F(n) возвращает уйма всех таких отрезков, и при этом выполняется инвариант: игрок, сделавший ход в число большее, чем n, проигрывает.

Разглядим два случая. Пускай n — нечетное. Тогда всякое четное число от 2 до n-1 — это выигрышная позиция, а всякое нечетное — проигрышная. Покажем, что 1-й игрок неизменно может сделать так, что он ходит из четной позиции, а его противник — из нечетной. Подлинно, если 1-й игрок переводит x в число x 1, то 2-й игрок может перевести x 1 только в четное число. Осталось лишь подметить, что число n нечетное, и следственно 1-й игрок неизменно имеет ход, тот, что не приводит к его поражению. Продолжая по индукции, получаем, что если 1-й игрок начинает с четного числа, то у него есть выигрышная тактика. В случае, когда 1-й игрок начинает с нечетного числа, 2-й игрок использует ту же тактику и выигрывает.

Сейчас пускай n четное. Все нечетные позиции, которые огромнее n/2, выигрышны, от того что удвоение такого числа сразу приводит к поражению; в таком случае выигрышность позиции определяется четностью числа оставшихся ходов. Подметим также, что позиция n/2 выигрышна, от того что из n/2 дозволено получить n, и иной игрок непременно превышает n своим дальнейшим ходом.

Разглядим такое число l, которое будет огромнее, чем n/2; при этом позиция l является проигрышной. В зависимости от четности числа n/2 l равно либо n/2 1, либо n/2 2. Сейчас разглядим все числа от l/2 до n/2 включительно. Все эти позиции будут выигрышными, от того что если удвоить всякое из этих чисел, получится число, большее n/2 и четное, а такая позиция проигрышна. Получили два отрезка, на первом из которых выигрышна всякая позиция, а на втором — всякая вторая.

Подметим, что остальные отрезки дозволено получить, вызвав F(l/2 — 1). Разбором случаев дозволено показать, что l/2 — 1 неизменно равно n/4, округленному вниз. Удостоверимся в том, что требуемое качество выполняется. Пускай x return A middle = pick(A) aLess = elements of A less then middle aGreater = elements of A greater then middle return qqsort(aLess) [middle] qqsort(aGreater)

Для сортировки массива делается следующее: вначале проверяется, является ли он теснее отсортированным. Если является, последующие действия не требуются. В другом случае выбирается определенный элемент массива, остальные разбиваются на те, которые поменьше его и те, которые огромнее, позже чего запускается сортировка для этих новых массивов. В новых массивах элементы оказываются в том же порядке, в котором они шли в начальном массиве.

Функция isSorted(a) проверяет, не отсортирован ли теснее переданный ей доводом массив. Функция pick возвращает определенный элемент из массива, тот, что ей передается в качестве довода. Она может воротить всякий из элементов массива.

Вестимо, что от того, насколько верно выбран разделяющий элемент, значительно зависит быстродействие сортировки. Соответственно, в зависимости от возвращаемых функцией pick значений может меняться число действий, которые выполняются во время работы алгорифма. В качестве критерия минимизации будем применять число вызовов функции pick.

Задан массив из n разных целых чисел от 1 до n. Определите, какого малейшего числа вызовов функции pick дозволено добиться при его сортировке, если при всяком вызове pick разрешается предпочесть возвращаемое значение.

Скажем, если требуется отсортировать массив A = [1, 2, 6, 7, 5, 3, 4, 8, 9], то, если 1-й вызов функции pick вернет число 5, массив aLess будет равен [1, 2, 3, 4], а массив aGreater — [6, 7, 8, 9]. Соответственно, рекурсивные вызовы qqsort сразу выйдут, от того что в них вызовы isSorted вернут true и массив будет отсортирован. Это оптимально, в этом случае функция pick вызывалась лишь 1 раз.

Формат входных данных
В первой строке задано число тестов t. Дальше в 2t строках заданы сами тесты. В первой строке изложения теста задано позитивное число n — размер массива. Во 2-й строке задан сам массив ai (1 годы их жизни.

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

Формат входных данных
Первая строка содержит целое число t — число тестов.

Источник: programmingmaster.ru

Оставить комментарий
Форум phpBB, русская поддержка форума phpBB
Рейтинг@Mail.ru 2008 - 2017 © BB3x.ru - русская поддержка форума phpBB