Олимпиады по информатике (ХМАО - Югра)

   
 
Югорский НИИ ИТ, Югорский ФМЛ
Логин:   Пароль:    
 
   
 
Новости
О проекте
Регистрация
Гостевая книга
Форум
Архив задач
Состояние системы
Олимпиады
Работа в системе
Рейтинг
Новичкам
Методическое пособие
Дистанционное обучение
Дистрибутивы
Ссылки

















Чемпионат по стрельбе

(Время: 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)
  }

[Все попытки] [Задача]


 
     
Югорский НИИ ИТ, Югорский ФМЛ