Новая задача для олимпиады по программированию

В своё время, когда я еще был маленький (8 класс) и занимался математикой, я был на олимпиаде по математике и получил диплом второй степени. И на разборе задач Жук (это фамилия преподавателя) сказал, что очень часто задачу для олимпиады можно составить взглянув на самые простые вещи, например, на игры.

Поэтому, глядя на игру «Block Drop«, я сразу понял: вот она, одимпиадная задача.

Вот какой текст получился у меня.

Имеется игровое клетчатое поле размером N на M. Оно полностью залито водой. В каждой клетке над водой находиться определенное количество кубиков. У нас есть человечек, который может прыгать со столбика на соседний столбик или через одну клетку. Если человечек прыгнет в клетку в которой нет кубиков, то он утонет. После того, как человечек прыгнул с одного столбика на другой, тот столбик, на котором он находился до прыжка погружается на один кубик в воду, т.е. в этом столбике становиться на один кубик меньше. Необходимо пропрыгать со столбика А до столбика B таким образом, чтобы на поле не осталось ни одного кубика, кроме кубика на финишной клетке, на котором и должен стоять человечек после окончания серии прыжков. Необходимо вывести последовательность прыжков, выполня которую человечик решит поставленную задачу Варианты прыжков на соседнюю клетку — L,R,U,D, через одну — L2,R2,U2, D2.

Надеюсь объянять, что такое L,R,U,D не надо :) Как её решать я пока не знаю, но мне кажется будет интересно.

Реклама

Метки: , ,

комментария 3 to “Новая задача для олимпиады по программированию”

  1. Siarhei Kuryla Says:

    по-моему эта задача попахивает перебором :)

  2. krolser Says:

    Чтож, сегодня расскажу эту задачу Веронике. Посмотрим, что она скажет :)
    На самом деле эта задача сводиться к поиску гамильтонова пути, который является в свою очередь NP полной задачей.
    Поправь Сергей, если я не прав.

  3. Siarhei Kuryla Says:

    т.е. перебор…

Добавить комментарий

Заполните поля или щелкните по значку, чтобы оставить свой комментарий:

Логотип WordPress.com

Для комментария используется ваша учётная запись WordPress.com. Выход / Изменить )

Фотография Twitter

Для комментария используется ваша учётная запись Twitter. Выход / Изменить )

Фотография Facebook

Для комментария используется ваша учётная запись Facebook. Выход / Изменить )

Google+ photo

Для комментария используется ваша учётная запись Google+. Выход / Изменить )

Connecting to %s


%d такие блоггеры, как: