e-olymp 6388. Муха Фон-Неймана

Задача

Следующая задача была предложена Джону Фон-Нейману:

Два велосипедиста [latex]a[/latex] и [latex]b[/latex] начинают поездку навстречу друг другу в одно и то же время с мест, находящихся на расстоянии [latex]250[/latex] друг от друга, [latex]a[/latex] движется со скоростью [latex]10[/latex] миль в час, [latex]b[/latex] движется со скоростью [latex]15[/latex] миль в час. В это же время муха взлетает с колеса велосипедиста [latex]a[/latex] и движется навстречу к [latex]b[/latex], затем разворачивается и летит обратно. Пока велосипедисты приближаются друг к другу, муха продолжает летать между ними, касаясь каждый раз переднего колеса велосипедистов, пока, наконец, не будет раздавлена колесами встретившихся велосипедов. Так как муха летает быстрее каждого из велосипедистов, она совершает бесконечное количество полетов, при этом пройдя конечное расстояние (бесконечный ряд сходится). Какое расстояние пролетела муха?

Фон-Нейман немедленно вычислил бесконечный ряд (в уме!), и получил верный ответ: [latex]200[/latex] миль.

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

Входные данные

Первая строка содержит количество тестов [latex]p (1 \leqslant p \leqslant 1000)[/latex].

Каждый тест состоит из одной строки, содержащей пять чисел: номер теста [latex]n[/latex] и четыре действительных числа: начальное расстояние между велосипедистами [latex]d (10 \leqslant d \leqslant 1000)[/latex], скорость первого велосипедиста [latex]a (1 \leqslant a \leqslant 30)[/latex] в милях в час, скорость второго велосипедиста [latex]b (1 \leqslant b \leqslant 30)[/latex] в милях в час и скорость мухи [latex]f (a \leqslant b < f \leqslant 50)[/latex] в милях в час.

Выходные данные

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

Тесты

# ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
1 5
1 250 10 15 20
2 10.7 3.5 4.7 5.5
3 523.7 15.3 20.7 33.3
4 1000 30 30 50
5 500 15 15 25
1 200.00
2 7.18
3 484.42
4 833.33
5 416.67

Код программы

Решение задачи

Безусловно, многие ознакомленные с курсом математического анализа люди (или же юные подражатели Фон-Неймана) после ознакомления с условием задачи мгновенно подумали о сумме сходящегося бесконечного ряда. Однако, если абстрагироваться от пестрых намеков содержания и попробовать мыслить менее глобально, можно прийти к куда более простому варианту решения. На самом деле под витиеватой формулировкой таится обыкновенная задача на движение с некоторым дополнительным фактором!

Согласно условию, велосипедисты [latex]a[/latex] и [latex]b[/latex] двигаются навстречу друг другу, а следовательно их скорость сближения (общая скорость) будет равна сумме скоростей каждого из велосипедистов: [latex]a + b[/latex]. По знакомой из школьного курса математики формуле [latex]S = V \times t[/latex] (тогда [latex]t = \frac { S }{ V }[/latex]), разделив расстояние между велосипедистами [latex]d[/latex] на их скорость сближения, найдем время [latex]t[/latex], спустя которое велосипедисты встретятся: [latex]t = d / (a + b)[/latex]. Муха, перелетающая с одного колеса на другое со скоростью [latex]f[/latex] достигнет момента своей погибели ровно тогда же, когда встретятся велосипедисты, то есть спустя то же время [latex]t[/latex]. Тогда, умножив скорость мухи на это время, то есть [latex]f\times t[/latex], получим расстояние [latex]flyDist[/latex], преодолённое мухой.
Для корректной реализации кода задачи сначала считываем количество тестов [latex]p[/latex], затем создаём цикл, внутри которого считываем все необходимые для вышеописанных действий переменные, производим нужные вычисления и, с помощью функции cout.precision и замечания fixed, выводим номер теста и его результат с точностью до двух десятичных знаков.

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

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

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

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

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

Немного подумав вспоминаем, что нам даны начальные координаты как источника так и энергии. Сразу же приходит в голову мысль, что их надо сравнивать.

Если равны координаты Тора и источника энергии по X, то тут мы находим разность координат источника и Тора по Y, если LY — TY > 0 (Источник находится выше Тора по оси Y), то идем на юг (вверх), в противном случае на север (вниз). Аналогично и с движением по Y,  что дает нам силы пройти первые два теста.

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

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

Конечно, мы могли бы высчитывать конечное число выводов команд на экран или подбивать все это проваливая тесты раз за разом. Но Тор нам подсказывает, что этого делать не надо, ведь он вспомнил могучее заклинание под названием цикл, которое спасает в очень многих ситуациях и эта не исключение.

Код на C++:

Код на Java:

 

Получается вот такой вот симпатичный код, описывающий все возможные ситуации по передвижению Тора (переносит Тора к источнику из любой точки карты). Разбивая на два возможных случая, движение в правой половине карты и в левой половине карты, получается, что программа охватывает любую ее точку. В самом цикле возьмем модуль между разностью (т.к. источник может находиться и ниже Тора). Сравниваем LX и TX, для того, чтобы узнать в какой половине карты находится источник. Если LX — TX > 0, то в цикле будем отнимать от LX, в противном случае — от TX, дабы не получить отрицательные значения. В конечном счете переменная E (энергия) там так и не понадобилось, так как воин и так находил кратчайшее расстояние.

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