Чемпионат по стрельбе
(Время: 1 сек. Память: 16 Мб Сложность: 32%)
Для решения задачи сначала следует найти минимальный номер победителя mi, сделать это можно простым линейным поиском одновременно с чтением результатов в некоторый массив a[1..n]. Тогда само значение a[mi] будет представлять собой количество очков, которые набрал победитель. Алгоритмическую схему данных действий можно представить так:
read(n)
mi=1
for i=1..n{
read(a[i])
if(a[mi] < a[i]) mi=i
}
Поскольку победитель стрелял раньше папы и папа стрелял не последним (после папы стрелял его друг), то номер результата папы в массиве a[1..n] будет располагаться в диапазоне от mi+1 до n-1. Для вычисления максимально возможного количества очков fi, которые мог набрать папа, можно перебрать все возможные значения вышеописанного диапазона и определить максимальное из них. При рассмотрении элемента a[i] нужно проверять его делимость на 5 и тот факт, что следующий элемент массива a[i+1] строго меньше текущего. В случае, если текущее значение fi меньше a[i] и a[i] удовлетворяет перечисленным ранее требованиям, то его следует занести в fi. Данный поиск осуществим следующим линейным алгоритмом:
fi=0
for i=mi+1..n-1
if(fi < a[i] and a[i] mod 10=5 and a[i] > a[i+1]) fi=a[i]
После нахождения fi мы можем определить возможное место, которое мог занять папа. Для этого достаточно подсчитать количество участников, набравших строго больше очков, и прибавить к данному результату 1. При этом следует учесть частный случай, когда может оказаться так, что среди рассматриваемых участников нет ни одного, удовлетворяющего условиям задачи, в этом случае следует вывести 0. Данная часть алгоритма представляется следующим кодом:
if(fi=0) write(0)
else{
c=1
for i=1..n
if(a[i] > fi) c=c+1
write(c)
}
|