Упражнения

Входные данные для всех задач записаны в файле input.txt, результат работы нужно вывести в файл output.txt.

В задачах C-K, N-S размер используемой памяти должен быть \(O(1)\), то есть нельзя создавать списки, размер которых может быть пропорционален количеству человек.

Слово balls на русский переводится так.

A: A + B

Во входном файле записано два целых числа, каждое в отдельной строке. Выведите в выходной файл их сумму.

2
2

4

B: Сумма нескольких чисел

Во входном файле записано любое количество чисел, каждое в отдельной строке. Выведите их сумму.

1
2
3

6

C: Максимальный балл по классам

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

Фамилия и имя — текстовые строки, не содержащие пробелов. Класс - одно из трех чисел 9, 10, 11. Балл - целое число от 0 до \(10^6\).

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

Определите количество баллов, которое набрал победитель в каждом классе. Гарантируется, что в каждом классе был хотя бы один участник.

Выведите три числа: баллы победителя олимпиады по 9 классу, по 10 классу, по 11 классу.

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

Решения, содержащие разбор трех случаев типа

if (form == 9)
    ....
else if (form == 10)
    ....
else

приниматься не будут.

Решение должно иметь сложность \(O(N)\), где \(N\) — общее количество участников олимпиады. Решение должно использовать \(O(1)\) памяти.

Иванов Сергей 9 90
Сергеев Петр 10 91
Петров Василий 11 92
Васильев Иван 9 93

93 91 92

D: Средний балл по классам

В условиях предыдущей задачи определите и выведите средние баллы участников олимпиады в 9 классе, в 10 классе, в 11 классе.

Решение должно иметь сложность \(O(N)\), где \(N\) — общее количество участников олимпиады. Решение должно использовать \(O(1)\) памяти.

Иванов Сергей 9 90
Сергеев Петр 10 91
Петров Василий 11 92
Васильев Иван 9 93

91.5 91.0 92.0

E: Количество победителей по классам

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

Выведите три числа: количество победителей олимпиады по 9 классу, по 10 классу, по 11 классу.

Решение должно иметь сложность \(O(N)\), где \(N\) — общее количество участников олимпиады. Решение должно использовать \(O(1)\) памяти.

Иванов Сергей 9 80
Сергеев Петр 10 80
Петров Василий 11 81
Васильев Андрей 9 81
Андреев Александр 10 80
Александров Роман 9 81
Романов Иван 11 80

2 2 1

F: Победитель олимпиады

Зачет в олимпиаде проводится без деления на классы. Выведите фамилию и имя победителя олимпиады. Если таких несколько - выведите только их количество.

Решение должно иметь сложность \(O(N)\), где \(N\) — общее количество участников олимпиады. Решение должно использовать \(O(1)\) памяти.

Иванов Сергей 9 90
Сергеев Петр 10 95
Петров Иван 11 85

Сергеев Петр

Иванов Сергей 9 90
Сергеев Петр 10 85
Петров Иван 11 90

2

G: Максимальный балл не-победителя

Зачет проводится отдельно в каждом классе. Победителями олимпиады становятся школьники, которые набрали наибольший балл среди всех участников в данном классе.

Для каждого класса определите максимальный балл, который набрал школьник, не ставший победителем в данном классе.

Выведите три целых числа.

Решение должно иметь сложность \(O(N)\), где \(N\) — общее количество участников олимпиады. Решение должно использовать \(O(1)\) памяти.

Иванов Сергей 9 80
Сергеев Петр 10 82
Петров Василий 11 82
Васильев Андрей 9 81
Андреев Александр 10 81
Александров Роман 9 81
Романов Иван 11 83

80 81 82

H: Максимальный балл призера и их количество

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

Определите наибольший балл, который набрали призеры олимпиады и количество участников олимпиады, набравших такой балл. Выведите два числа: наибольший балл призера и количество участников, имеющий такой балл.

Решение должно иметь сложность \(O(N)\), где \(N\) — общее количество участников олимпиады. Решение должно использовать \(O(1)\) памяти.

Иванов Сергей 9 92
Сергеев Петр 10 91
Петров Василий 11 92
Васильев Иван 9 93

92 2

I: Имя наилучшего не-победителя

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

Решение должно иметь сложность \(O(N)\), где \(N\) — общее количество участников олимпиады. Решение должно использовать \(O(1)\) памяти.

Иванов Сергей 9 93
Сергеев Петр 10 91
Петров Василий 11 92
Васильев Иван 9 93

Петров Василий

Иванов Сергей 9 92
Сергеев Петр 10 91
Петров Василий 11 92
Васильев Иван 9 93

2

J: Школы с наибольшим числом участников олимпиады

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

Фамилия и имя — текстовые строки, не содержащие пробелов. Школа — целое число от 1 до 999. Балл — целое число от 0 до 100.

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

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

Решение должно иметь сложность \(O(N + K)\), где \(N\) — общее количество участников олимпиады, \(K\) — количество школ. Решение должно использовать \(O(K)\) памяти.

Иванов Сергей 14 56
Сергеев Петр 23 74
Петров Василий 3 99
Васильев Андрей 3 56
Андреев Роман 14 75
Романов Иван 27 68

3 14

K: Школы с наименьшим числом участников олимпиады

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

Решение должно иметь сложность \(O(N + K)\), где \(N\) — общее количество участников олимпиады, \(K\) — количество школ. Решение должно использовать \(O(K)\) памяти.

Иванов Сергей 14 56
Сергеев Петр 23 74
Петров Василий 3 99
Васильев Андрей 3 56
Андреев Роман 14 75
Романов Иван 27 68

23 27

L: Отсортировать список участников по алфавиту

Известно, что фамилии всех участников — различны. Сохраните список всех участников и выведите его, отсортировав по фамилии в лексикографическом порядке. Используйте стандартную функцию сортировки языка.

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

Сложность решения должна быть \(O(N)\) без учета сложности сортировки, где \(N\) — количество участников олимпиады. Решение может использовать \(O(N)\) памяти.

Иванов Сергей 14 56
Сергеев Петр 23 74
Петров Василий 3 99
Васильев Андрей 3 56
Андреев Роман 14 75
Романов Иван 27 68

Андреев Роман 75
Васильев Андрей 56
Иванов Сергей 56
Петров Василий 99
Романов Иван 68
Сергеев Петр 74

M: Отсортировать список участников по баллам

Отсортируйте список участников олимпиады:

1. По убыванию набранного балла.
2. При равных значения балла - по фамилии в лексикографическом порядке.
3. При совпадающих баллах и фамилии - по имени в лексикографическом порядке.

Для сортировки используйте встроенную функцию сортировки.

Выведите список в таком же виде, как в предыдущей задаче.

Сложность решения должна быть \(O(N)\) без учета сложности сортировки, где \(N\) — количество участников олимпиады. Решение может использовать \(O(N)\) памяти.

Иванов Сергей 14 75
Сергеев Петр 23 74
Сергеев Андрей 3 99
Петров Василий 3 99
Иванов Роман 14 75
Иванов Иван 27 76

Петров Василий 99
Сергеев Андрей 99
Иванов Иван 76
Иванов Роман 75
Иванов Сергей 75
Сергеев Петр 74

N: Школы, в которых есть победители олимпиады

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

Решение должно иметь сложность \(O(N + K)\), где \(N\) — общее количество участников олимпиады, \(K\) — количество школ. Решение должно использовать \(O(K)\) памяти.

Иванов Сергей 13 80
Сергеев Петр 26 70
Сергеев Андрей 35 80
Петров Василий 13 80
Иванов Роман 35 70
Иванов Иван 26 70

13 35

O: Школы с высоким средним баллом

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

Решение должно иметь сложность \(O(N + K)\), где \(N\) — общее количество участников олимпиады, \(K\) — количество школ. Решение должно использовать \(O(K)\) памяти.

Иванов Сергей 13 45
Сергеев Петр 13 45
Сергеев Андрей 20 55
Петров Василий 20 55
Иванов Роман 70 40
Иванов Иван 70 60

20

P: Школы с наибольшим средним баллом

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

Решение должно иметь сложность \(O(N + K)\), где \(N\) — общее количество участников олимпиады, \(K\) — количество школ. Решение должно использовать \(O(K)\) памяти.

Иванов Сергей 13 45
Сергеев Петр 13 45
Сергеев Андрей 20 55
Петров Василий 20 55
Иванов Роман 70 40
Иванов Иван 70 60

20

Q: Список школ упорядоченный по числу участников

В условиях предыдущей задачи выведите номера школ, из которых был хотя бы один участник олимпиады, в порядке убывания количества участников олимпиады из этих школ. Если из двух школ было одинаковое число участников, то их номера выводятся в порядке возрастания номера школы.

Решение должно иметь сложность \(O(N + K)\) (без учета сложности сортировки списка), где \(N\) — общее количество участников олимпиады, \(K\) — количество школ. Решение должно использовать \(O(K)\) памяти.

Иванов Сергей 13 45
Сергеев Петр 70 45
Сергеев Андрей 20 55
Петров Василий 14 55
Иванов Роман 13 40
Иванов Иван 70 60

13 70 14 20

R: Список школ упорядоченный по среднему баллу участников

В условиях предыдущей задачи выведите номера школ, из которых был хотя бы один участник олимпиады, в порядке убывания среднего балла участников олимпиады из этих школ. Если для двух школ средний балл участников совпадает, то их номера выводятся в порядке возрастания номера школы.

Решение должно иметь сложность \(O(N + K)\) (без учета сложности сортировки списка), где \(N\) — общее количество участников олимпиады, \(K\) — количество школ. Решение должно использовать \(O(K)\) памяти.

Иванов Сергей 13 45
Сергеев Петр 13 45
Сергеев Андрей 20 55
Петров Василий 20 55
Иванов Роман 70 40
Иванов Иван 70 60

20 70 13

S: Школы с наибольшим числом победителей

В условиях предыдущей задачи выведите в порядке возрастания номера школ, из которых наибольшее количество участников стало победителями олимпиады. В этой задаче значение числа баллов одного участника может быть до \(10^6\).

Решение должно иметь сложность \(O(N + K)\), где \(N\) — общее количество участников олимпиады, \(K\) — количество школ. Решение должно использовать \(O(K)\) памяти.

Иванов Сергей 13 70
Сергеев Петр 13 60
Сергеев Андрей 20 70
Петров Василий 20 70
Иванов Роман 70 60
Иванов Иван 70 60

20