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

22/12/2019 by Кирилл Колесник

Задача

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

Два велосипедиста [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

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

#include <iostream>
using namespace std;
 
int main() {
    double p, d, a, b, f, t, flyDist;
    int n;
    cin >> p;
    for (int i = 0; i < p; i++){
        cin >> n >> d >> a >> b >> f;
        t = d / (a + b);
        flyDist = f * t;
        cout.precision(2);
        cout << fixed << n << " " << flyDist << endl;
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

double p, d, a, b, f, t, flyDist;

int n;

cin >> p;

for (int i = 0; i < p; i++){

cin >> n >> d >> a >> b >> f;

t = d / (a + b);

flyDist = f * t;

cout.precision(2);

cout << fixed << n << " " << flyDist << endl;

}

return 0;

}

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

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

Согласно условию, велосипедисты [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, выводим номер теста и его результат с точностью до двух десятичных знаков.

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

Related Images:

Ragnarök — Power of Thor

12/10/2014 by Байков Дмитро

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

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

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

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

Игровой цикл

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

Вход

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

Выход

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

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

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

Тест 1

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

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

/**
 * Auto-generated code below aims at helping you parse
 * the standard input according to the problem statement.
 **/
int main()
{
    int LX; // the X position of the light of power
    int LY; // the Y position of the light of power
    int TX; // Thor's starting X position
    int TY; // Thor's starting Y position
    cin >> LX >> LY >> TX >> TY; cin.ignore();

    // game loop
    while (1) {
        int E; // The level of Thor's remaining energy, representing the number of moves he can still make.
        cin >> E; cin.ignore();

        // Write an action using cout. DON'T FORGET THE "<< endl"
        // To debug: cerr << "Debug messages..." << endl;

        cout << "SE" << endl; // A single line providing the move to be made: N NE E SE S SW W or NW
    }
}

#include <iostream>

#include <string>

#include <vector>

#include <algorithm>

using namespace std;

/**

* Auto-generated code below aims at helping you parse

* the standard input according to the problem statement.

**/

int main()

{

int LX; // the X position of the light of power

int LY; // the Y position of the light of power

int TX; // Thor's starting X position

int TY; // Thor's starting Y position

cin >> LX >> LY >> TX >> TY; cin.ignore();

// game loop

while (1) {

int E; // The level of Thor's remaining energy, representing the number of moves he can still make.

cin >> E; cin.ignore();

// Write an action using cout. DON'T FORGET THE "<< endl"

// To debug: cerr << "Debug messages..." << endl;

cout << "SE" << endl; // A single line providing the move to be made: N NE E SE S SW W or NW

}

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

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

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

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <math.h>
using namespace std;

/**
 * Auto-generated code below aims at helping you parse
 * the standard input according to the problem statement.
 **/
int main()
{
    int LX; // the X position of the light of power
    int LY; // the Y position of the light of power
    int TX; // Thor's starting X position
    int TY; // Thor's starting Y position
    cin >> LX >> LY >> TX >> TY; cin.ignore();

    // game loop
    while (1) 
    {
        int E; // The level of Thor's remaining energy, representing the number of moves he can still make.
        cin >> E; cin.ignore();
        if (LX == TX) //Movement along the X axis.
        {
            if (( LY - TY ) < 0)
            {
            cout << "N" << endl;
            }
            else 
            {
            cout << "S" << endl;
            }
        }    
        if (TY == LY) //Movement along the Y axis.
        {
            if (( LX - TX ) < 0)
            {
            cout << "W" << endl;
            }
            else 
            {
                cout << "E" << endl;
            }
        }
    }
}

#include <iostream>

#include <string>

#include <vector>

#include <algorithm>

#include <math.h>

using namespace std;

/**

* Auto-generated code below aims at helping you parse

* the standard input according to the problem statement.

**/

int main()

{

int LX; // the X position of the light of power

int LY; // the Y position of the light of power

int TX; // Thor's starting X position

int TY; // Thor's starting Y position

cin >> LX >> LY >> TX >> TY; cin.ignore();

// game loop

while (1)

{

int E; // The level of Thor's remaining energy, representing the number of moves he can still make.

cin >> E; cin.ignore();

if (LX == TX) //Movement along the X axis.

{

if (( LY - TY ) < 0)

{

cout << "N" << endl;

}

else

{

cout << "S" << endl;

}

if (TY == LY) //Movement along the Y axis.

{

if (( LX - TX ) < 0)

{

cout << "W" << endl;

}

else

{

cout << "E" << endl;

}

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

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

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

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

Код на C++:

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <math.h>
using namespace std;

/**
 * Auto-generated code below aims at helping you parse
 * the standard input according to the problem statement.
 **/
int main()
{
    int LX; // the X position of the light of power
    int LY; // the Y position of the light of power
    int TX; // Thor's starting X position
    int TY; // Thor's starting Y position
    cin >> LX >> LY >> TX >> TY; cin.ignore();

    // game loop
    while (1) 
    {
        int E; // The level of Thor's remaining energy, representing the number of moves he can still make.
        cin >> E; cin.ignore();
        if (LX == TX) //Movement along the X axis.
        {
            if (( LY - TY ) < 0)
            {
            cout << "N" << endl;
            }
            else 
            {
            cout << "S" << endl;
            }
        }    
        if (TY == LY) //Movement along the Y axis.
        {
            if (( LX - TX ) < 0)
            {
            cout << "W" << endl;
            }
            else 
            {
                cout << "E" << endl;
            }
        }
        if (( LX - TX ) > 0) //Movement to the left half of the map
        {
            
            if (( LY - TY ) < 0)
            {
               for(int i = 0;i < abs ( LY - TY );i++)
               {
                    cout << "NE" << endl;
               }
                for (int i = 0;i < abs ( LX - abs ( LY - TY ));i++)
                {
                    cout << "E" << endl;
                }
            }
            else 
            {
                if (( LY - TY ) > 0)
                 {
                    for(int i = 0;i < abs ( LY - TY );i++)
                    {
                        cout << "SE" << endl;
                    }
                   for (int i = 0;i < abs ( LX - abs ( LY - TY ));i++)
                    {
                        cout << "E" << endl;
                    }
                }
            }
        }
        if (( LX - TX ) < 0) //Movement to the right half of the map
        {
            
            if (( LY - TY ) < 0)
            {
                for(int i = 0;i < abs ( LY - TY );i++)
                {
                    cout << "NW" << endl;
                }
                for (int i=0;i < abs ( TX - ( LY - TY ));i++)
                {
                    cout << "W" << endl;
                }
            }
            else 
            {
                if (( LY - TY ) > 0)
                {
                   for (int i = 0;i < abs ( LY - TY );i++)
                   {
                        cout << "SW" << endl;
                   }
                    for (int i = 0;i< abs ( TX - ( LY - TY ));i++)
                    {
                        cout << "W" << endl;
                    }
                }
            }
        }
    }
}

100

101

102

103

104

105

106

#include <iostream>

#include <string>

#include <vector>

#include <algorithm>

#include <math.h>

using namespace std;

/**

* Auto-generated code below aims at helping you parse

* the standard input according to the problem statement.

**/

int main()

{

int LX; // the X position of the light of power

int LY; // the Y position of the light of power

int TX; // Thor's starting X position

int TY; // Thor's starting Y position

cin >> LX >> LY >> TX >> TY; cin.ignore();

// game loop

while (1)

{

int E; // The level of Thor's remaining energy, representing the number of moves he can still make.

cin >> E; cin.ignore();

if (LX == TX) //Movement along the X axis.

{

if (( LY - TY ) < 0)

{

cout << "N" << endl;

}

else

{

cout << "S" << endl;

}

if (TY == LY) //Movement along the Y axis.

{

if (( LX - TX ) < 0)

{

cout << "W" << endl;

}

else

{

cout << "E" << endl;

}

if (( LX - TX ) > 0) //Movement to the left half of the map

{

if (( LY - TY ) < 0)

{

for(int i = 0;i < abs ( LY - TY );i++)

{

cout << "NE" << endl;

}

for (int i = 0;i < abs ( LX - abs ( LY - TY ));i++)

{

cout << "E" << endl;

}

else

{

if (( LY - TY ) > 0)

{

for(int i = 0;i < abs ( LY - TY );i++)

{

cout << "SE" << endl;

}

for (int i = 0;i < abs ( LX - abs ( LY - TY ));i++)

{

cout << "E" << endl;

}

if (( LX - TX ) < 0) //Movement to the right half of the map

{

if (( LY - TY ) < 0)

{

for(int i = 0;i < abs ( LY - TY );i++)

{

cout << "NW" << endl;

}

for (int i=0;i < abs ( TX - ( LY - TY ));i++)

{

cout << "W" << endl;

}

else

{

if (( LY - TY ) > 0)

{

for (int i = 0;i < abs ( LY - TY );i++)

{

cout << "SW" << endl;

}

for (int i = 0;i< abs ( TX - ( LY - TY ));i++)

{

cout << "W" << endl;

}

Код на Java:

import java.util.*;
import java.io.*;
import java.math.*;

class Player 
{
    public static void main(String args[]) 
    {
    	Scanner in = new Scanner(System.in);
	    int lightX = in.nextInt(); // the X position of the light of power
	    int lightY = in.nextInt(); // the Y position of the light of power
	    int initialTX = in.nextInt(); // Thor's starting X position
	    int initialTY = in.nextInt(); // Thor's starting Y position
	
	    // game loop
	    while (true) 
	    {
	        int remainingTurns = in.nextInt();// The remaining amount of turns Thor can move. Do not remove this line.
	        if (lightX == initialTX) //Movement along the X axis.
	        {
	            if ((lightY - initialTY) < 0)
	            	System.out.println("N");
	            else 
	            	System.out.println("S");
	        }    
	        if (initialTY == lightY) //Movement along the Y axis.
	        {
	            if ((lightX - initialTX) < 0)
	            	System.out.println("W");
	            else 
	                System.out.println("E");
	        }
	        if ((lightX - initialTX) > 0) //Movement to the left half of the map
	        {
	            if ((lightY - initialTY) < 0)
	            {
	               for(int i = 0;i < Math.abs(lightY - initialTY);i++)
	                    System.out.println("NE");
	               for (int i = 0;i < Math.abs(lightX - Math.abs(lightY - initialTY));i++)
	                   System.out.println("E");
	            }
	            else 
	            {
	                if ((lightY - initialTY) > 0)
	                 {
	                    for(int i = 0;i < Math.abs(lightY - initialTY);i++)
	                    	System.out.println("SE");
	               		for (int i = 0;i < Math.abs(lightX - Math.abs(lightY - initialTY));i++)
	                		System.out.println("E");
	                }
	            }
	        }
	        if ((lightX - initialTX) < 0) //Movement to the right half of the map
	        {
	            
	            if ((lightY - initialTY) < 0)
	            {
	                for(int i = 0;i < Math.abs(lightY - initialTY);i++)
	            		System.out.println("NW");
	                for (int i=0;i < Math.abs(initialTX - (lightY - initialTY));i++)
	                	System.out.println("W");
	            }
	            else 
	            {
	                if ((lightY - initialTY) > 0)
	                {
	                   for(int i = 0;i < Math.abs(lightY - initialTY);i++)
	            		System.out.println("SW");
	                for (int i=0;i < Math.abs(initialTX - (lightY - initialTY));i++)
	                	System.out.println("W");
	                }
	            }
	        }
	    }
	}
}

import java.util.*;

import java.io.*;

import java.math.*;

class Player

{

public static void main(String args[])

{

Scanner in = new Scanner(System.in);

int lightX = in.nextInt(); // the X position of the light of power

int lightY = in.nextInt(); // the Y position of the light of power

int initialTX = in.nextInt(); // Thor's starting X position

int initialTY = in.nextInt(); // Thor's starting Y position

// game loop

while (true)

{

int remainingTurns = in.nextInt();// The remaining amount of turns Thor can move. Do not remove this line.

if (lightX == initialTX) //Movement along the X axis.

{

if ((lightY - initialTY) < 0)

System.out.println("N");

else

System.out.println("S");

}

if (initialTY == lightY) //Movement along the Y axis.

{

if ((lightX - initialTX) < 0)

System.out.println("W");

else

System.out.println("E");

}

if ((lightX - initialTX) > 0) //Movement to the left half of the map

{

if ((lightY - initialTY) < 0)

{

for(int i = 0;i < Math.abs(lightY - initialTY);i++)

System.out.println("NE");

for (int i = 0;i < Math.abs(lightX - Math.abs(lightY - initialTY));i++)

System.out.println("E");

}

else

{

if ((lightY - initialTY) > 0)

{

for(int i = 0;i < Math.abs(lightY - initialTY);i++)

System.out.println("SE");

for (int i = 0;i < Math.abs(lightX - Math.abs(lightY - initialTY));i++)

System.out.println("E");

}

if ((lightX - initialTX) < 0) //Movement to the right half of the map

{

if ((lightY - initialTY) < 0)

{

for(int i = 0;i < Math.abs(lightY - initialTY);i++)

System.out.println("NW");

for (int i=0;i < Math.abs(initialTX - (lightY - initialTY));i++)

System.out.println("W");

}

else

{

if ((lightY - initialTY) > 0)

{

for(int i = 0;i < Math.abs(lightY - initialTY);i++)

System.out.println("SW");

for (int i=0;i < Math.abs(initialTX - (lightY - initialTY));i++)

System.out.println("W");

}

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

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