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

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


Клавиатура - 2

(Время: 1 сек. Память: 16 Мб Сложность: 25%)

Для решения этой задачи следует завести целочисленный массив a[1..n], где в a[i] будет храниться максимальное число нажатий, которое выдерживает i-я клавиша. После чего достаточно будет один раз пройтись по последовательности нажатий клавиш. Рассматривая текущее нажатие клавиши x, будем соответственно уменьшать число оставшихся нажатий в a[x]. По завершению этого процесса в каждом a[i] будет храниться число нажатий, которые i-я клавиша еще способна выдержать, если это значение отрицательно, то следует вывести "yes", иначе - "no".

Описанный выше алгоритм представим следующим образом:

  int a[1..100];
  //чтение данных
  read(n);
  for i=1..n read(a[i]);
  read(k);
  for i=1..k{
    read(x);           //чтение номера нажатой клавиши
    a[x]=a[x]-1;       //уменьшаем на единицу остаток нажатий, которые еще может выдержать эта клавиша
  }
  //вывод результата
  for i=1..n
    if(a[i]<0) writeln('yes') 
          else writeln('no');

Рассмотренное выше решение имеет линейный порядок сложности O(N+K) и поэтому вполне приемлемо. Здесь могло бы пройти даже решение порядка O(N*K). Речь идет о следующем: если использовать дополнительный массив, в котором хранить всю последовательность из K нажатий и для определения устойчивости каждой клавиши в отдельности пробегать по этому массиву и считать число нажатий конкретной клавиши, то в принципе мы получим верный алгоритм, но весьма более затратный по времени.

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


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