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

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

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

input.txt	output.txt
5 1 50 3 4 3 161 2 3 4 5 1 3 3 4 5 5 5 5 5 4 5	yes no no no yes

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

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

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

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

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

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

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

Var c: array [1..100] of longint; n, i, k, t: longint; f: text;input,output: text; Begin Assign(f,' input.txt '); 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, 'output.txt'); Rewrite(f); For i:=1 to N do If c[i]>=0 Then Writeln(f,'no') Else Writeln(f,'yes'); Close(f); End.

Задача 4. Вырубка деревьев

Имя входного файла: input.txt Имя выходного файла: output.txt Максимальное время работы на одном тесте: 1 секунда Максимальный объем используемой памяти: 64 мегабайта

Король Флатландии решил вырубить некоторые деревья, растущие перед его дворцом. Деревья перед дворцом короля посажены в ряд, всего там растет N деревьев, расстояния между соседними деревьями одинаковы.

После вырубки перед дворцом должно остаться M деревьев, и расстояния между соседними деревьями должны быть одинаковыми. Помогите королю выяснить, сколько существует способов вырубки деревьев.

Требуется написать программу, которая по заданным числам N и M определит, сколько существует способов вырубки некоторых из N деревьев так, чтобы после вырубки осталось M деревьев и соседние деревья находились на равном расстоянии друг от друга.

 

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

Входной файл INPUT.TXT содержит два целых числа M и N (0 <= M <= N <= 1000).

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

В выходном файле OUTPUT.TXT должно содержаться одно число - искомое количество способов.

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

input.txt	output.txt
5 3

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

Зафиксируем расстояние между деревьями после вырубки. Если оно равно d, то возможно
n – d(m – 1) – m + 1 способов вырубить деревья. Суммируя по всем d, получаем ответ.

Если у нас есть 0 деревьев и 0 деревьев должно остаться после вырубки, то существует один вариант вырубки - это надо учитывать при решении задачи.

Вариант 1 (с использованием цикла)

var n, m: longint; i, d, s: longint; input, output: text; begin Assign(input,'input.txt'); Reset(input); Assign(output,'output.txt'); Rewrite(output); Read(input,n,m); s:= 0; if m = 0 then s:= 1 else if m = 1 then s:= n else for d:= 1 to (n-1) div (m-1) do inc(s,n-(m-1)*d); Write(output,s); Close(input); Close(output); end.

 

Вариант 2 (без цикла)

var n, m,k: longint; i, d, s: longint; input, output: text; begin Assign(input,'input.txt'); Reset(input); Assign(output,'output.txt'); Rewrite(output); read(input,n,m); if m=0 then s:=1 else if m=1 then s:=n else begin k:=(n-1) div (m-1);{количество членов прогрессии} d:=m-1;{шаг прогрессии} s:=(2+(k-1)*d)*k div 2;{формула суммы первых членов арифметической прогрессии} end; write(output, s); Close(input); Close(output); end.