e-olymp 472. Вероятность

Latest posts by Данила Савчак (see all)

Задача

Однорукий бандит

Однорукий бандит

Вася придумал новую игру. Для игры требуется полоска из трёх стоящих в ряд клеток, фишки [latex]n[/latex] различных видов и непрозрачный мешок.

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

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

Чтобы оценить среднюю частоту выигрышей, Вася решил найти такую величину: количество выигрышных вариантов заполнения полоски разделить на количество всех вариантов заполнения полоски. Количество всех вариантов заполнения полоски Вася нашёл самостоятельно (получилось [latex] n^3[/latex] ), а вот для нахождения количества выигрышных вариантов он обратился к своему знакомому, лучше разбирающемуся в математике и программировании, т.е. к Вам. Continue reading

Ragnarök — Power of Thor

Вустянюк Ігор Дмитрович
Вустянюк Ігор Дмитрович

Latest posts by Вустянюк Ігор Дмитрович (see all)

 Рагнарёк

Задача

Есть Тор. А у Тора был источник силы. Больше нет. Тор движется по прямоугольному полю и ему известны его координаты и координаты источника. Наша задача: за наименьшее количество ходов привести Тора к источнику. Допустимые варианты движения приведены на картинке ниже:

Рагнарёк-2

Инициализация

Одна строка, в которой даны четыре целых числа:  LX, LY, TX, TY — соответственно абсцисса и ордината источника, абсцисса и ордината начального положения Тора.

Инициализация

Одна строка, в которой даны четыре целых числа:  LX, LY, TX, TY — соответственно абсцисса и ордината источника, абсцисса и ордината начального положения Тора.

Входные данные для одного игрового хода

Уровень энергии Тора. Нам он не понадобится.

Выходные данные для одного игрового хода

Одна из следующих строк: «N», «NE», «E», «SE», «S», «SW», «W», «NW», указывающая в каком направлении Тору нужно переместиться.

Решение

Поскольку Тор движется по прямоугольному полю, на котором нет преград, кратчайший путь получится, если на каждом шаге сравнивать положение Тора с положением источника по каждой из осей и направлять Тора в соответствующую сторону (так, чтобы скомпенсировать различие в координатах). Подробно этот процесс ниже описан в комменатариях к коду. Здесь сделаем только две ремарки.

Во-первых, нужно учесть, что ордината растёт в южном, а не в северном направлении, как обычно:

 Рагнарёк-3

Во-вторых, если бы поле не было прямоугольным (или на нём были бы преграды, не позволяющие двигаться в том или ином направлении), то наш метод пришлось бы серьёзно модифицировать.

 

Код на С++

Код на Java

 

The Descent

Вустянюк Ігор Дмитрович
Вустянюк Ігор Дмитрович

Latest posts by Вустянюк Ігор Дмитрович (see all)

Задача

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

Гор имеется 8 штук. Корабль летает кругами над горами: сначала слева направо, потом справа налево, и так далее. Один полный «пролёт» состоит из восьми игровых ходов. За один пролёт мы можем выстрелить только один раз и только по горе, над которой находимся. При этом высота горы уменьшится на случайное число.

Чтобы благополучно приземлиться нам нужно уничтожить все горы. Создатели игры дали ценную подсказку: если стрелять на каждом пролёте по самой высокой горе, посадка будет безопасной.

Входные данные для одного игрового хода

В первой строке введены два числа (SX и SY) — соответственно горизонтальная и вертикальная координаты нашего корабля. Горизонтальная меняется слева направо от нуля до семи. Вертикальная, как показал опыт, нам не понадобится.

Следующие восемь строк содержат каждая по одному целому числу от нуля до девяти — высоту соответствующей горы. Высоты перечислены слева направо.

Выходные данные для одного игрового хода

Одна строка: «FIRE», чтобы выстрелить, и «HOLD», если на текущем ходе стрелять не нужно.

Решение

Считаем SX и SY. После этого в цикле for считаем высоты гор. Нам нужно стрелять на каждом пролёте по самой высокой горе. Для этого мы применим приём, уже опробованный нами на практических занятиях: введём новую переменную max_height, в которую поместим высоту первой горы (точнее, нулевой). А в цикле будем обновлять эту переменную, если наткнёмся на более высокую гору. Всё? Нет, не всё. Стрелять мы можем только по горе, которая находится под нами. Чтобы знать, когда стрелять, введём переменную max_position, которая будет хранить координату самой высокой горы. Вначале присвоим ей нулевое значение. А в цикле будем обновлять эту переменную, вместе с переменной max_height.

Когда цикл for завершится, останется только проверить находимся ли мы на текущем ходу над самой высокой горой: для этого будем каждый раз сравнивать текущую координату корабля (SX) с координатой самой высокой горы, которая после цикла for хранится в переменной max_position. В случае совпадения — стреляем, в противном случае — ждём.

Код на С++

Код на Java

 

Ragnarök — Power of Thor

Четвертая по счету игра на сайте называется Ragnarök — Power of Thor, где нам посчастливилось быть Великим Воином Тором. Тору необходимо самым кратчайшим путем добраться до источника энергии, которая придаст ему еще больше сил и уверенности в дальнейших сражениях.

Пока еще не всемогущий Тор ждет указаний

Пока еще не всемогущий Тор ждет указаний

Инициализация

В начале нам сообщают положение на карте источника и самого персонажа (их координаты по X и Y) (int LX, LY) (int TX, TY) соответственно.

Игровой цикл

Бесконечно (до конца игры) повторяемый игровой цикл состоит из любого количества кода, который читает входной поток и выводит команду в выходной поток.

Вход

В самом игровом цикле нам сообщают величину энергии Тора (int E), которая уменьшается на 1 с каждым последующим ходом.

Выход

В выходной поток необходимо вывести одну строку. Нам представлено всего 8 возможных вариантов дальнейшего передвижения Тора. Screenshot_2222

 

Движение возможно только как показано на картинке (т.е. по компасу). Например, если мы хотим, чтобы персонаж двигался вправо (на восток) мы выведем буквочку E и т.д.

Перевод строки на новую обязателен.

 

Тест 1

Запуская программу впервые, Тор будет сам не свой, двигаясь совсем не по направлению к источнику.

Пройти первый и второй тесты, кажется просто, якобы написать в какую сторону мальчику бежать и только наблюдать за процессом, но не тут то было. Третий тест показывает нам, что все-таки придется подумать об адекватном решении.

Адекватное решение

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

Цикл for идет на помощь

Пройдя все тесты, наш довольный рыцарь полон сил и энергии. Пожелаем удачи ему в дальнейших приключениях.

Skynet — The Chasm

Вторая по счету игра на сайте называется Skynet — The Chasm. В игре мы будем управлять мотоциклистом, который изо всех сил пытается попасть на другую сторону пропасти и остановиться на конечной платформе.

Ни о чем не подозревающий мотоциклист

Ни о чем не подозревающий мотоциклист

Инициализация

В начале нам сообщают всевозможные данные о будущем пути: расстояние от мотоциклиста до пропасти (int R), длину пропасти (int G), длину платформы для приземления (int L).

Игровой цикл

Бесконечно (до конца игры) повторяемый игровой цикл состоит из любого количества кода, который читает входной поток и выводит команду в выходной поток.

Вход

Каждый новый ход (т.е. после каждого следующего выполненного действия в самом цикле while) нам сообщают скорость мотоциклиста (int S) и его позицию на дороге (int X).

Выход

В выходной поток необходимо вывести одну строку. Тут разработчики представляют нам 4 варианта:

  • ускоряться (SPEED);
  • тормозить (SLOW);
  • ехать вперед без ускорения (WAIT);
  • прыгать (JUMP).

Перевод строки на новую обязателен.

Тест 1

В начале нам представлен базовый код программы.

 

Запуская первый тест наш несчастный мотогонщик, постоянно ускоряясь, уже в который раз падает в пропасть. Но мы, всячески пытаемся его выручить и, наконец, пишем спасательный код.

Спасательный код

Подходя к 4 тесту сталкиваемся с новой проблемой. Длинна платформы для приземления очень мала и наш бессмертный каскадер вылетает за окончание дороги. Что же делать?

Еще более спасательный код

Кажется, что мы предусмотрели все варианты развития событий, но не тут то было. Разработчики устанавливают новую, увлекательную задачу. Что будет, если начальная скорость будет не равна 0, спрашивают они? И мы пускаемся в глубокие размышления.

Код дающий, в прямом смысле, крылья

В конце-концов мы получаем рабочий «крылатый» вариант программы. Все довольны, в том числе и мотоциклист, которому больше не придется падать в пропасть и выбираться из нее.