Разбор задачи С4 ЕГЭ по информатике

Пример задания:

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

<Фамилия> <Инициалы> <номер школы>

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

Иванов П.С. 57

Требуется написать как можно более эффективную программу (укажите используемую версию языка программирования, например, Borland Pascal 7.0), которая будет выводить на экран информацию, из какой школы было меньше всего участников (таких школ может быть несколько). При этом необходимо вывести информацию только по школам, пославшим хотя бы одного участника. Следует учитывать, что N>=1000.

Как правильно понимать условие?

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

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

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

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

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

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

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

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

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

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

Пример задачи с решением

C4 (высокий уровень,

время – 60 мин)

=1000. " width="640"

Пример задания:

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

где – строка, состоящая не более чем из 20 символов, – строка, состоящая из 4-х символов (буква, точка, буква, точка), – не более чем двузначный номер. и , а также и разделены одним пробелом. Пример входной строки:

Иванов П.С. 57

Требуется написать как можно более эффективную программу (укажите используемую версию языка программирования, например, Borland Pascal 7.0), которая будет выводить на экран информацию, из какой школы было меньше всего участников (таких школ может быть несколько). При этом необходимо вывести информацию только по школам, пославшим хотя бы одного участника. Следует учитывать, что N=1000.

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

Input.txt

Output.txt

4

Иванов Петя 57

1 1

Петров Вадим 23

57 1

Карпушов Ваня 23

Гоцуленко Марат 1

=1000 »? этим авторы задачи намекают на то, что не нужно считывать все данные в оперативную память, а потом уже их обрабатывать; основная обработка должна быть сделана сразу, в том же цикле, где читаются входные данные мы будем считать, что в исходных данных нет ошибок (так принято на олимпиадах и экзаменах), иначе обработка разнообразных ошибок будет составлять основную часть программы " width="640"

Как правильно понимать условие?

• итак, сначала вводится количество записей в файле N , а затем N строк с информацией; заметим, что из всей этой информации нас интересует (в каждой строке) только номер школы, остальное можно просто отбрасывать
• номер школы стоит после второго пробела в строке
• « – не более чем двузначный номер » – крайне важная информация; собственно, только она и позволяет найти хорошее решение задачи; это значит, что школ не более 99!
• что означает выражение «как можно более эффективная программа»?
• прежде всего, данные читаются только один раз, за один проход, нельзя «вернуться» и прочитать что-то вновь
• в программе не выполняются никакие лишние действия
• используемые алгоритмы имеют минимальную сложность (см. выше)
• расходуется минимальный возможный объем памяти; например, чтобы найти количество отрицательных элементов массива, не нужно вводить второй массив; если нам достаточно держать в памяти одну введенную строку, не нужно одновременно хранить все прочитанные строки
• зачем нужно уточнение « N=1000 »? этим авторы задачи намекают на то, что не нужно считывать все данные в оперативную память, а потом уже их обрабатывать; основная обработка должна быть сделана сразу, в том же цикле, где читаются входные данные
• мы будем считать, что в исходных данных нет ошибок (так принято на олимпиадах и экзаменах), иначе обработка разнообразных ошибок будет составлять основную часть программы

Объявление массива

Var nc:array[1..99] of integer;

p:1..99;

с:char;

i,N,k,min:integer;

Блок считывания данных (файлы input и output готовы заранее)

Begin

Assign(input, ‘input.txt’);

Reset(input);

Assign(output, ‘output.txt’);

Rewrite(output);

Read(N); {количество школьников пришедших на олимпиаду}

Задаем и обнуляем массив с количеством школ

For i:=1 to 99 do nc[i]:=0;

Продолжение блока считывания данных

For i:=1 to N do begin {общий список}

repeat read(c);

until c=‘ ‘; {фамилии}

repeat read(p);

until p=‘ ‘; {инициалов}

Продолжение блока считывания данных {номер школы}

read(p);

nc[p]:=nc:[p]+1;

End;

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

min := N;

For i:=1 to 99 do

if (nc[i] 0) and (nc[i]

then min := nc[i];

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

for k:=1 to 99 do

If nc[i] = min then writeln(i);

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