Клавиатура - 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 нажатий и для определения устойчивости каждой клавиши в отдельности пробегать по этому массиву и считать число нажатий конкретной клавиши, то в принципе мы получим верный алгоритм, но весьма более затратный по времени.
| 
