Олимпиадные задачи школьного этапа 2014-2015

Быстрый старт

Имя входного файла

input.txt

Имя выходного файла

output.txt

Максимальное время работы на одном тесте

2 секунды

Ограничение по памяти

64 МБ

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

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

Помогите Васе по известным значениям ловкости и подвижности определить этот коэффициент.

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

Во входном файле заданы два целых числа D и A (0 ≤ D, A ≤ 10⁹) - ловкость и подвижность хоккеиста соответственно.

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

В выходной файл выведите коэффициент.

Пример

input.txt

output.txt

1 2

2

2 3

3

В данной задаче требовалось найти максимум из двух чисел. Читаем из файла два числа в переменные a и d. При помощи полного ветвления оператора if находим максимум из двух чисел, при этом учитываем ситуацию, когда числа равны.

program start;

var

input, output : text;

a, d : int64;

begin

assign(input, 'input.txt');

assign(output, 'output.txt');

reset(input);

rewrite(output);

read(input, d, a);

if (a > d) then

write(output, a)

else

write(output, d);

close(input);

close(output);

end.

Кто быстрее?

Имя входного файла

input.txt

Имя выходного файла

output.txt

Максимальное время работы на одном тесте

2 секунды

Ограничение по памяти

64 МБ

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

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

На каждом ходу известно, что хоккеист повернут на А градусов, а для того, чтобы смотреть точно на шайбу, нужно быть повернутым на В градусов. Углы отсчитываются от положительного направления оси абсцисс против часовой стрелки. Расстояние от игрока до шайбы равно D. За один ход хоккеист может повернуться не более чем на Т градусов или переместиться на расстояние, не превосходящее S. За какое наименьшее количество ходов игрок сможет добраться до шайбы?

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

Во входном файле заданы пять целых чисел D, A, B, S и T (0 ≤ D ≤ 10⁹, 0 ≤ A, B < 360, 1 ≤ S ≤ 10⁹, 1 ≤ T < 360).

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

В выходной файл выведите, за какое наименьшее количество ходов хоккеист сможет добраться до шайбы.

Пример

input.txt

output.txt

15 0 12 5 3

7

20 12 0 4 4

8

Количество ходов, сделанных игроком, состоит из ходов, сделанных при повороте к шайбе, и ходов, сделанных при движении по направлению к шайбе. Для того чтобы повернуться к шайбе за наименьшее количество ходов, будем поворачиваться на максимальные t градусов, до тех пор, пока не окажемся повёрнутыми на b градусов. Для этого необходимо разность между углами a и b поделить нацело на t и в случае, если a и b не делится нацело на t, прибавить единицу. При этом следует учитывать, что если разница между a и b больше 180 градусов, то быстрее будет повернуться в противоположную сторону, т.е. на 360 - abs(a - b) градусов. Для того чтобы добраться до шайбы за наименьшее количество ходов, необходимо за один ход передвигаться на наибольшее расстояние, т.е. на s. Делим d нацело на s. Если есть остаток, то увеличиваем количество на единицу. Суммируем два полученных результата и получаем ответ.

program who;

var

input, output : text;

s, d, ans : int64;

a, b, t : integer;

begin

assign(input, 'input.txt');

assign(output, 'output.txt');

reset(input);

rewrite(output);

read(input, d, a, b, s, t);

if (abs(a - b) > 180) then

ans := 360 - abs(a - b)

else

ans := abs(a - b);

if (ans mod t > 0) then

ans := ans div t + 1

else

ans := ans div t;

ans := ans + d div s;

if (d mod s > 0) then

inc(ans);

write(output, ans);

close(input);

close(output);

end.

Анализ рейтинга

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

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

Анализировать данные - скучное и утомительное занятие, к тому же Вася занят написанием очередной версии своей стратегии. Но ему очень хочется узнать наиболее удачный и наиболее провальный период выступления своего искусственного интеллекта. Удачным периодом Вася считает такой период, когда рейтинг не понижался, а провальным, соответственно, когда рейтинг не рос. Наиболее удачным периодом Вася считает такой удачный период, на котором произошел наибольший рост рейтинга, а наиболее неудачным считает такой период, на котором произошло наибольшее падение. Помогите Васе по исходным данным найти изменения рейтинга за эти периоды.

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

В первой строке входного файла записано целое число N (1 ≤ N ≤ 10⁵) - количество данных. Во второй строке через пробел записаны N целых неотрицательных чисел, не превосходящих 10⁹ - величина рейтинга после каждой игры в хронологическом порядке.

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

В выходной файл выведите два числа - на сколько вырос рейтинг за наиболее удачный период и на сколько упал за наиболее провальный.

Пример

input.txt

output.txt

3
1 2 4

3 0

5
0 3 5 2 3

5 3

Анализ рейтинга

В задаче необходимо найти наибольшие спад и рост рейтинга. Для этого необходимы две переменные: start, prev и now, где start - первое значение того или иного периода, prev - предыдущее значение рейтинга и now - текущее значение рейтинга. Если now - prev < 0, значит это период роста. Проверяем, если до этого также был период роста, то проверяем, является ли данный рост максимумом среди всех предыдущих периодов роста. Если же нет, то помечаем, что начался новый период роста. Точно так же и для периодов спада.

program analis;

const

INF = 10000000000;

var

input, output : text;

prev, now, start, min, max : int64;

n, i : integer;

flag, flag2 : boolean;

begin

assign(input, 'input.txt');

assign(output, 'output.txt');

reset(input);

rewrite(output);

max := 0;

min := INF;

flag := false;

read(input, n);

read(input, prev);

start := prev;

for i := 2 to n do

begin

read(input, now);

flag2 := false;

if (flag = true) then

begin

if (now - prev < 0) then

begin

start := prev;

flag := false;

flag2 := true;

if (min > now - start) then

min := now - start;

end;

if (now - prev > 0) then

if (max < now - start) then

max := now - start;

end;

if (flag = false) and (flag2 = false) then

begin

if (now - prev < 0) then

if (min > now - start) then

min := now - start;

if (now - prev > 0) then

begin

start := prev;

flag := true;

if (max < now - start) then

max := now - start;

end;

end;

prev := now;

end;

write(output, max, ' ');

if (min = INF) then

write(output, 0)

else

write(output, abs(min));

close(input);

close(output);

end.