Пример задачи с решением C4 (высокий уровень, время – 60 мин) - презентация

1 Пример задачи с решением C4 (высокий уровень, время – 60 мин)

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

3 Input.txtOutput.txt 4 Иванов Петя 57 Петров Вадим 23 Карпушов Ваня 23 Гоцуленко Марат Пример входных данных:

4 Как правильно понимать условие? 1.итак, сначала вводится количество записей в файле N, а затем N строк с информацией; заметим, что из всей этой информации нас интересует (в каждой строке) только номер школы, остальное можно просто отбрасывать 2.номер школы стоит после второго пробела в строке 3.« – не более чем двузначный номер» – крайне важная информация; собственно, только она и позволяет найти хорошее решение задачи; это значит, что школ не более 99! 4.что означает выражение «как можно более эффективная программа»? 5.прежде всего, данные читаются только один раз, за один проход, нельзя «вернуться» и прочитать что-то вновь 6.в программе не выполняются никакие лишние действия 7.используемые алгоритмы имеют минимальную сложность (см. выше) 8.расходуется минимальный возможный объем памяти; например, чтобы найти количество отрицательных элементов массива, не нужно вводить второй массив; если нам достаточно держать в памяти одну введенную строку, не нужно одновременно хранить все прочитанные строки 9.зачем нужно уточнение «N>=1000»? этим авторы задачи намекают на то, что не нужно считывать все данные в оперативную память, а потом уже их обрабатывать; основная обработка должна быть сделана сразу, в том же цикле, где читаются входные данные 10.мы будем считать, что в исходных данных нет ошибок (так принято на олимпиадах и экзаменах), иначе обработка разнообразных ошибок будет составлять основную часть программы

5 Объявление массива Var nc:array[1..99] of integer; p:1..99; с:char; i,N,k,min:integer;

6 Блок считывания данных (файлы input и output готовы заранее) Begin Assign(input, input.txt); Reset(input); Assign(output, output.txt); Rewrite(output); Read(N); {количество школьников пришедших на олимпиаду}

7 Задаем и обнуляем массив с количеством школ For i:=1 to 99 do nc[i]:=0;

8 Продолжение блока считывания данных For i:=1 to N do begin {общий список} repeat read(c); until c= ; {фамилии} repeat read(p); until p= ; {инициалов}

9 Продолжение блока считывания данных {номер школы} read(p); nc[p]:=nc:[p]+1; End;

10 1.дальше стандартным алгоритмом определяем в массиве C минимальный элемент Min, не учитывая нули (школы, из которых не было участников): min := N; For i:=1 to 99 do if (nc[i] 0) and (nc[i]

11 Находим ответ и выводим на экран min := N; for i:=1 to 99 do if (nc[i] 0) and (nc[i]