» » Приглашаем на MosCode Festival и разбираем задачи прошлых лет

 

Приглашаем на MosCode Festival и разбираем задачи прошлых лет

Автор: admin от 8-02-2018, 17:05, посмотрело: 180

Приглашаем на MosCode Festival и разбираем задачи прошлых лет



Привет, Хабр! Центр развития ИТ-образования МФТИ приглашает тебя на международный студенческий чемпионат по спортивному программированию MosCode Festival. Это хорошая возможность потренироваться на задачах уровня финала ACM ICPC вместе с участниками из других стран. Контест пройдёт 31 марта (личный тур) и 1 апреля (командный тур) в технопарке «Сколково». Онлайн-отбор пройдёт в ближайшее воскресенье, 11 февраля, в 11:00 по московскому времени. Пока вы думаете о регистрации, рассказываем подробности и делимся двумя задачами прошлого года с разбором.

Задача «Нечто с точками и прямоугольниками»

Задача «Игра на поле»



Код:

Пример выигрышной стратегии:

Код: Описание: Пусть z — количество камней в некой клетке. Рассмотрим несколько соображений:



1. Если z ? 4, то из этой клетки камни могут двигаться, только вправо и вниз, так-как в противном случае, при S = z, все S камней никогда не останутся лежать в нижней правой клетке.



2. Если z ? 4, то какая-то не нулевая часть камней обязательна должна идти вправо, и какая-то не нулевая часть должна идти вниз, так-как в противном случае, при S = z, мы проиграем в таблицах состоящих из 1-й строки, или 1-го столбца.



3. Если количество камней, лежащих изначально в левой верхней клетки ? 4, то можно считать значения 1, 2, 3 некоторыми базовыми частями, при помощи которых мы будем разбивать большие части.



На основании данных соображений и некоторых предположений можно прийти к стратегии следующего вида. Основная часть камней (назовем ее T) идет вниз, и на каждом ходу она отделяет от себя несколько базовых частей. 1 и 2 будут полностью передвигаться вправо, а 3-ка будет передвигаться полностью вниз, идея стратегии в том, что-бы выделять из T части 1 и 2, а 3-ки должны собираться только на правой границе, откуда они уже придут внижнюю клетку. ПустьT, состоящая из z камней делится таким образом:



• вниз идет основная часть без 3-х камней, то-есть z — 3 камня;

• вправо идет 2 камня;

• в данной клетке остается 1 камень.



Тогда единицы и двойки будут идти вправо, пока не соберутся в 3-ку н аправой границе. Однако в данной стратегии есть изъяны, а именно она не будет работать для маленького z. Например потому-что 6-ка по такой стратегии разделиться на 2, 1 и 3, и 3-ка пойдет вниз, хотя она и находиться пока на левой границе, поэтому еще нужно аккуратно рассмотреть количества камней от 4-х до 6-и, а остальные будут распадаться на базовые части и части ? 4.



В итоге получаем такую стратегию:














КоличествоВправоВниз
1

2

3

4

5

6

z ? 7

1

2

0

2

1

2

2

0

0

3

1

2

2

z–3



[/spoiler]

Источник: Хабрахабр

Категория: Программирование

Уважаемый посетитель, Вы зашли на сайт как незарегистрированный пользователь.
Мы рекомендуем Вам зарегистрироваться либо войти на сайт под своим именем.

Добавление комментария

Имя:*
E-Mail:
Комментарий:
Полужирный Наклонный текст Подчеркнутый текст Зачеркнутый текст | Выравнивание по левому краю По центру Выравнивание по правому краю | Вставка смайликов Выбор цвета | Скрытый текст Вставка цитаты Преобразовать выбранный текст из транслитерации в кириллицу Вставка спойлера
Введите два слова, показанных на изображении: *