В этом году третий раз одна известная компания проводит соревнование по программированию искусственного интеллекта для игровых стратегий. В этот раз участникам предложили написать искусственный интеллект для управления командой хоккеистов.
После того, как стратегия была запрограммирована, Вася отправил ее в систему. Проведя ряд тестовых боев, она попала в песочницу и начала сражаться со стратегиями других участников. У каждого участника песочницы есть свой рейтинг, который показывает успешность отправленного решения. После каждого системного сражения он может измениться. Все колебания рейтинга можно увидеть на персональной странице участника в виде графика.
Анализировать данные — скучное и утомительное занятие, к тому же Вася занят написанием очередной версии своей стратегии. Но ему очень хочется узнать наиболее удачный и наиболее провальный период выступления своего искусственного интеллекта. Удачным периодом Вася считает такой период, когда рейтинг не понижался, а провальным, соответственно, когда рейтинг не рос. Наиболее удачным периодом Вася считает такой удачный период, на котором произошел наибольший рост рейтинга, а наиболее неудачным считает такой период, на котором произошло наибольшее падение. Помогите Васе по исходным данным найти изменения рейтинга за эти периоды.
Формат входных данных
В первой строке входного файла записано целое число N (1 ≤ N ≤ 105) — количество данных. Во второй строке через пробел записаны N целых неотрицательных чисел, не превосходящих 109 — величина рейтинга после каждой игры в хронологическом порядке.
Формат выходных данных
В выходной файл выведите два числа — на сколько вырос рейтинг за наиболее удачный период и на сколько упал за наиболее провальный.
Пример
input.txt output.txt
3
1 2 4 3 0
5
0 3 5 2 3 5 3
Как это решать? может у коговонибудь хоть идеи есть?
Удачным периодом Вася считает такой период, когда рейтинг не понижался, а провальным, соответственно, когда рейтинг не рос. Наиболее удачным периодом Вася считает такой удачный период, на котором произошел наибольший рост рейтинга, а наиболее неудачным считает такой период, на котором произошло наибольшее падение. Помогите Васе по исходным данным найти изменения рейтинга за эти периоды.
Из этого следует, что нужно проходить входной массив чисел от начала до конца. Если каждое последующее число больше предыдущего - значит это один из удачных периодов. Запоминаем первое число, с которого начался рост показателей, и последнее, на котором он стал снижаться. Разница между ними и будет показателем роста рейтинга.
Задания не олимпиадного класса, решаются простым перебором массива в одном цикле , алгоритм на уровне первого года информатики.
ну прочитайте за 10 минут статью про массивы в любой книге по паскалю, если вы не знаете ни одного языка программирования то зачем вас отправили на олимпиаду?
var
n, a, oldA, nu, np, u, p, i: integer;
begin
readln(n); read(oldA);
nu:= 0; np:= 0; u:= 0; p:= 0;
for i:= 2 to n do
begin
read(a);
if a > oldA then
begin
u:= u+a-oldA; p:= 0;
if nu < u then nu:= u;
end;
if a < oldA then
begin
p:= p+oldA-a; u:= 0;
if np < p then np:= p;
end;
oldA:= a;
end;
writeln(nu, ' ', np);
end.
u, p - показатель текущего удачного и провального периода
nu, np - показатель лучшего удачного и провального периода
a, oldA - текущее и предыдущее число
Суть алгоритма таков.
При каждом новом числе сразу вычисляем u, p, nu, np следующим образом.
Если новое число больше предыдущего или равно значит удачный период начинается или продолжается. Вычисляем u. Проверяем лучший ли он. Обнуляем p. Если текущее меньше то поступаем по аналогии. Получается мы таким образои после каждого числа вычислили сразу u, p, nu, np. В конце выводим nu и np.
Простой
