Клавиатура

Региональный этап Всероссийской олимпиады школьников по информатике 2008/2009 учебного года
Второй тур

[к списку задач]

Задача 5. Клавиатура

Всем известно, что со временем клавиатура изнашивается, и клавиши на ней начинают залипать. Конечно, некоторое время такую клавиатуру еще можно использовать, но для нажатий клавиш приходиться использовать большую силу.

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

Требуется написать программу, определяющую, какие клавиши сломаются в процессе заданного варианта эксплуатации клавиатуры.

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

Первая строка входного файла содержит целое число n (1 ≤ n ≤ 100) – количество клавиш на клавиатуре. Вторая строка содержит n целых чисел – с1, с2, … , сn, где сi (1 ≤ сi ≤ 100000) – количество нажатий, выдерживаемых i-ой клавишей. Третья строка содержит целое число k (1 ≤ k ≤ 100000) – общее количество нажатий клавиш, и последняя строка содержит k целых чисел pj (1 ≤ pj ≤ n) – последовательность нажатых клавиш.

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

В выходной файл необходимо вывести n строк, содержащих информацию об исправности клавиш. Если i-ая клавиша сломалась, то i-ая строка должна содержать слово “yes” (без кавычек), если же клавиша работоспособна – слово “no”.

Пример входных и выходных данных

Краткие методические рекомендации по решению задачи

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

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

Таким образом, чтобы набрать полный балл, требуется реализовать простейшее линейное решение, в котором используются лишь базовые операции с массивами.

Возможные ошибки

Можно применить "лобовое" решение, т.е. создать два или  три массива, но на самом деле нужен только один размером 100 элементов. При лобовом решении необходим массив в 100000 элементов, а создать его в Turbo Pascal не удастся. Самое интересное, что лобовое решение проходит если использовать компилятор Free Pascal. При решении задачи надо обратить внимание, что в выходной файл данные надо выводит в нижнем регистре.

Текст программы на Паскале одного из участников олимпиады:

Var 
  c : array [1..100] of longint;
  n, i, k, t : longint;
  f : text;
Begin
  Assign(f,'keyboard.in');
  Reset(f);
  ReadLn(f,n);
  For i:=1 to N do 
    Read(f,c[i]);
  Readln(f,k);
  For i:=1 to k do
    begin  
      Read(f,t); 
      Dec(c[t]); 
    end;
  Close(f);
  Assign(f,'keyboard.out');
  Rewrite(f);
  For i:=1 to N do
    If c[i]>=0 Then 
      Writeln(f,'no') 
    Else Writeln(f,'yes');
  Close(f);
End.

[к списку задач]