Posts Tagged ‘olymp’

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

Февраль 19, 2009

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

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

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

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

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

Реклама