Как правильно понимать условие? 141) на первый вопрос – как именно вводятся данные – находим ответ в самом начале условия: вроде бы «дежурная» фраза «на вход программе подаются » означает

141) на первый вопрос – как именно вводятся данные – находим ответ в самом начале условия: вроде бы «дежурная» фраза «на вход программе подаются…» означает, что данные нужно читать не из файла, а со стандартного входного потока; это, в свою очередь, значит, что можно использовать привычные операторы read (readln), предполагая, что кто-то вводит эти данные с клавиатуры вручную[26]

142) итак, сначала вводится количество записей в файле N, а затем N строк с информацией; заметим, что из всей этой информации нас интересует (в каждой строке) только номер школы, остальное можно просто отбрасывать

143) номер школы стоит после второго пробела в строке

144) «<номер школы> – не более чем двузначный номер» – крайне важная информация; собственно, только она и позволяет найти хорошее решение задачи; это значит, что школ не более 99!

145) что означает выражение «как можно более эффективная программа»?

o прежде всего, данные читаются только один раз, за один проход, нельзя «вернуться» и прочитать что-то вновь

o в программе не выполняются никакие лишние действия

o используемые алгоритмы имеют минимальную сложность (см. выше)

o расходуется минимальный возможный объем памяти; например, чтобы найти количество отрицательных элементов массива, не нужно вводить второй массив; если нам достаточно держать в памяти одну введенную строку, не нужно одновременно хранить все прочитанные строки

146) зачем нужно уточнение «N>=1000»? этим авторы задачи намекают на то, что не нужно считывать все данные в оперативную память, а потом уже их обрабатывать; основная обработка должна быть сделана сразу, в том же цикле, где читаются входные данные

147) мы будем считать, что в исходных данных нет ошибок (так принято на олимпиадах и экзаменах), иначе обработка разнообразных ошибок будет составлять основную часть программы

Решение:

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

2) так как номер школы состоит (по условию!) не более, чем из двух цифр, всего может быть не более 99 школ (с номерами от 1 до 99)

3) поэтому можно ввести массив C из 99 элементов; для всех k от 1 до 99 элемент C[k] будет ячейкой-счетчиком, в которой накапливается число участников от школы с номером k; сначала во все элементы этого массива записываются нуль (обнуление счетчиков):

for k:=1 to 99 do C[k]:=0;

во многих системах программирования на Паскале все глобальные переменные автоматически обнуляются, и таким образом, этот цикл ничего не дает; однако на всякий случай нужно продемонстрировать эксперту, который будет проверять часть С вашей работы, что вы понимаете суть дела («счетчик необходимо сначала обнулить»)

4) основной цикл обработки вводимых строк можно записать на псевдокоде так:

for i:=1 to N do begin

{ читаем очередную строку }

{ определяем номер школы k }

C[k]:= C[k] + 1; { увеличиваем счетчик k-ой школы }

end;

5) поскольку данные вводятся в виде символьной строки, нужно выделить в памяти переменную s типа string

6) для чтения очередной строки будем использовать оператор readln

7) остается понять, как выделить из строки номер школы; по условию он закодирован в последней части строки, после второго пробела; значит, нужно найти этот второй пробел, вырезать из строки весь «хвост» после этого пробела, и преобразовать его из символьного формата в числовой

8) чтобы найти первый пробел и «отрезать» первую часть строки с этим пробелом, можно использовать команды

p:= Pos(' ', s);

s:= Copy(s, p+1, Length(s)-p);

первая команда определяет номер первого пробела и записывает его в целую переменную p, в вторая – записывает в строку s весь «хвост», стоящий за этим пробелом, начиная с символа с номером p+1; длина хвоста равна Length(s)-p, где Length(s) – длина строки;

9) поскольку нас интересует часть после второго пробела, эти две строчки нужно повторить два раза, в результате в переменной s окажется символьная запись номера школы;

10) заметим, что можно избежать дублирования двух строк, «свернув» их во внутренний цикл, но это вряд ли сильно упростит запись:

for k:=1 to 2 do begin

p:= Pos(' ', s);

s:= Copy(s, p+1, Length(s)-p);

end;

11) в пп. 8-10 описан достаточно общий метод, при котором инициалы могут быть любой длины, (но без пробела); в данном случае в условии четко сказано, что инициалы представляют собой именно 4 символа (буква, точка, буква, точка), поэтому можно найти первый пробел, а затем взять «хвост», который идет через 6 символов от него:

12) для преобразования номера школы из символьного вида в числовой можно использовать функцию Val:

Val(s, k, r);

эта процедура (Turbo Pascal, Borland Pascal, PascalABC, среда АЛГО) преобразует символьную строку s в числовое значение k; с помощью переменной r обнаруживается ошибка: если раскодировать число не удалось (в строке не число), в r будет записан нуль (здесь мы не будем обрабатывать эту ошибку, полагая, что все данные правильные);

если вы работаете на ПаскалеABC (никто не может вам запретить написать, что этот так), вместо Val можно использовать более удобную и понятную функцию StrToInt:

k:= StrToInt(s);

13) таким образом, основной цикл выглядит так:

for i:=1 to N do begin

readln(s); { читаем очередную строку }

{ выделяем часть после второго пробела }

p:= Pos(' ', s);

Delete(s, 1, p+5);

{ определяем номер школы k }

Val(s, k, r);

C[k]:= C[k] + 1; { увеличиваем счетчик k-ой школы }

end;

14) дальше стандартным алгоритмом определяем в массиве C минимальный элемент Min, не учитывая нули (школы, из которых не было участников):

Min:= N;

for k:=1 to 99 do

if (C[k] <> 0) and (C[k]<Min) then Min:= C[k];

здесь интересна первая строчка, Min:=N: по условию всего было N участников, поэтому минимальное значение не может быть больше N; обратите внимание, что привычный вариант (который начинается с Min:=C[1]) работает неверно, если из первой школы не было ни одного участника

15) и выводим на экран номера всех школ (обратите внимание – номера!), для которых C[k]=Min:

for k:=1 to 99 do

if C[k] = Min then writeln(k);

16) остается «собрать» программу, чтобы получилось полное решение; максимальное количество школ мы задали в виде константы LIM:

const LIM = 99;

var C:array[1..LIM] of integer;

i, p, N, k, r, Min: integer;

s:string;

Begin

for k:=1 to 99 do C[k]:=0;

readln(N);

for i:=1 to N do begin

readln(s); { читаем очередную строку }

{ выделяем часть после второго пробела }

p:= Pos(' ', s);

Delete(s, 1, p+5);

{ определяем номер школы k }

Val(s, k, r);

C[k]:= C[k] + 1; { увеличиваем счетчик k-ой школы }

end;

Min:= N;

for k:=1 to LIM do

if (C[k] <> 0) and (C[k]<Min) then Min:= C[k];

for k:=1 to LIM do

if C[k] = Min then writeln(k);

End.

Еще пример задания:

На вход программе подаются сведения о сдаче экзаменов учениками 9-х классов некоторой средней школы. В первой строке сообщается количество учеников N, которое не меньше 10, но не превосходит 100, каждая из следующих N строк имеет следующий формат:

<Фамилия> <Имя> <оценки>,

где <Фамилия> – строка, состоящая не более чем из 20 символов, <Имя> – строка, состоящая не более чем из 15 символов, <оценки> – через пробел три целых числа, соответствующие оценкам по пятибалльной системе. <Фамилия> и <Имя>, а также <Имя> и <оценки> разделены одним пробелом. Пример входной строки:

Поиск по сайту: