Задача “Робот-сапер”

Программа робота-сапера состоит из последовательности команд вида (a, b), где a – символ, принимающий значения W, N, O или S, что означает, соответственно, запад, север, восток или юг, а b – натуральное число, bЈ 20. Исполняя команду (a, b), робот делает шаг длины b в направлении a. Робот программируют и запускают из некоторой исходной точки на минное поле. Выполняя друг за другом команды программы, робот обезвреживает встречающиеся ему мины и после каждого шага сообщает, что соответствующая команда выполнена. Проторенная им тропа считается безопасной. Не поступление от робота очередного сообщения означает, что он все же подорвался. В этом случае на его замену из той же исходной точки запускают аналогичный робот. При программировании второго робота возникает следующая задача: найти такую последовательность команд, выполняя которую робот

  • дойдет от исходной точки до места, из которого было получено последнее сообщение предыдущего робота;

  • будет двигаться при этом только по участкам безопасной тропы;

  • пройдет при этом путь минимальной длины.

Требуется написать программу, которая решает эту задачу.

Ввод данных организовать из файла input.txt или с клавиатуры, а вывод – в файл output.txt или на экран.

Формат входных данных:

1-я строка: K (KЈ 20) – количество команд, которые успел выполнить первый робот;

2-я строка: <a> <пробел> <b> – значения параметров 1-ой из этих команд;

3-я строка: <a> <пробел> <b> – значения параметров 2-ой из этих команд;

K+1-я строка: <a> <пробел> <b> – значения параметров K-ой из этих команд.

Формат выходных данных:

1-я строка: M – количество команд искомой последовательности;

2-я строка: <a> <пробел> <b> – значения параметров 1-ой из этих команд;

3-я строка: <a> <пробел> <b> – значения параметров 2-ой из этих команд;

M+1-я строка: <a><пробел><b> – значения параметров M-ой из этих команд.

Ограничение времени: 20 секунд.

Пример входных данных (соответствуют приведенному рисунку):

4

W 4

N 2

O 2

S 3

Пример выходных данных (соответствуют приведенным входным):

2

W 2

S 1

Задача “Локатор”

На плоскости расположены N неподвижных источников звука. Задана система координат xOy, при этом все источники расположены в верхней полуплоскости y>0. Звуковое давление pi, создаваемое в произвольной точке отдельно взятым i-м источником, зависит только от расстояния r от источника до этой точки и определяется формулой [image], где p0i – “стандартное звуковое давление” (константа, зависящая от источника). При одновременной работе нескольких источников создаваемые ими звуковые давления суммируются. По некоторым причинам в каждый момент времени работают все источники за исключением какого-то одного. В точках с координатами
(-a, 0) и (a, 0) находятся измерительные микрофоны A и B соответственно, регистрирующие звуковые давления в этих точках. Имеются измерения звукового давления [image] и [image], i=1,2,…,N, где [image] и [image] – измерения микрофонов в момент, когда работали все источники звука за исключением i-го.

Требуется написать программу, которая по значениям p0i, [image] и [image], i=1,2,…,N определяет координаты (xi, yi), каждого из источников звука.

Ввод данных организовать из файла input.txt или с клавиатуры, а вывод – в файл output.txt или на экран.

Формат входных данных:

1-я строка: N <пробел> a – натуральное число (2Ј NЈ 100) и действительное число;

2-я строка: p01 – положительное действительное число;

3-я строка: p02 – положительное действительное число;

N+1-я строка: p0N – положительное действительное число;

N+2-я строка: <пробел> [image] – пара положительных действительных чисел;

N+3-я строка: <пробел> [image] – пара положительных действительных чисел;

2N+1-я строка: <пробел> [image] – пара положительных действительных чисел;

Формат выходных данных:

1-я строка: x1 <пробел> y1 – координаты 1-го источника звука;

2-я строка: x2 <пробел> y2 – координаты 2-го источника звука;

N-я строка: xN <пробел> yN – координаты N-го источника звука;

Ограничение времени: 20 секунд.

Пример входных данных:

2 1.0

2.0

1.0

0.5 0.5

1.0 1.0

Пример выходных данных (соответствуют приведенным входным):

0 1

0 1

Задача “Обыграй букмекера”

Букмекерская контора – это заведение, принимающее у граждан денежные ставки на исходы различных событий (спортивных, политических и т.д.). Если исход события угадан, то ставка считается выигранной, при этом игрок, поставив x рублей, получает ax рублей, где число a>1 называется коэффициентом исхода и определяется букмекерами до начала события. Известно, что в городе Екатеринбурге встречаются неквалифицированные букмекеры, они часто назначают такие коэффициенты, что умный игрок может гарантировать себе определенный выигрыш при любом исходе события.

Рассмотрим президентские выборы 2000 года. Предположим, что зарегистрировано N кандидатов, и один из них обязательно победит. Ставки принимаются с коэффициентом a1 на победу в выборах 1-го кандидата, с коэффициентом a2 – на победу 2-го, …, с aN – N-го. Игрок располагает капиталом, равным X рублей. Задача заключается в том, чтобы определить, возможен ли гарантированный выигрыш этого игрока, и, в случае положительного ответа, найти оптимальную стратегию его игры, т.е. указать, сколько денег игроку следует поставить на каждого из кандидатов для того, чтобы получить максимальное гарантированное увеличение своего капитала.

Требуется написать программу, которая решает эту задачу в следующих случаях:

  1. принимаются любые ставки, даже выраженные иррациональным числом рублей, при этом выигрыш на ставку “выплачивается” точно и, вообще говоря, может тоже выражаться иррациональным числом;

  2. ставки принимаются только в виде целого числа рублей. При этом выигрыш на ставку выплачивается тоже только в виде целого числа рублей, а “копейки” отбрасываются в пользу букмекерской конторы (так, например, если игрок поставил 2 рубля на исход с коэффициентом a=1.32 и эта ставка выиграла, то ему будет выплачено 2 рубля).

Ввод данных организовать из файла input.txt или с клавиатуры, а вывод – в файлы output1.txt и output2.txt (соответственно случаям 1 и 2) или на экран (сначала для случая 1, затем, после нажатия на клавишу <Enter>, – для случая 2)

Формат входных данных:

1-я строка: N – натуральное число (NЈ 20);

2-я строка: a1 – действительное число, записанное по формату ***.**;

3-я строка: a2 – действительное число, записанное по формату ***.**;

N+1-я строка: aN – действительное число, записанное по формату ***.**;

N+2-я строка: X – натуральное число (XЈ 100000).

Формат выходных данных (для обоих случаев):

1-я строка: ‘Yes’, если гарантированный выигрыш возможен, ‘No’ – если нет.

В случае ‘Yes’:

2-я строка: x1 – количество денег, которое следует поставить на 1-го кандидата;

3-я строка: x2 – количество денег, которое следует поставить на 2-го кандидата;

N+1-я строка: xN – количество денег, которое следует поставить на N-го кандидата;

N+2-я строка: S – количество денег, которым гарантированно будет располагать игрок после выборов, если последует данной стратегии.

Ограничение времени: 20 секунд.

Пример входных данных:

2

2.00

3.00

10

Пример выходных данных (соответствуют приведенным входным)

Для случая 1:

Yes

6

4

12

Для случая 2:

Yes

6

4

12