Файлы

Для работы с файлами из своей программы необходимо:

1. Подключить заголовочный файл fstream, содержащий описание функций, позволяющих работать с файловыми потоками.
2. Для чтения данных необходимо создать переменную (объект) типа ifstream, связав его с файлом на диске. Чтение данных из файла осуществляется также, как из стандартного ввода при помощи оператора “>>”
3. Для вывода данных необходимо создать переменную (объект) типа ofstream, связав его с файлом на диске. Запись данных в файл осуществляется также, как на стандартный вывод при помощи оператора “<<”

Если при связывании объектов с файлами указывается только имя файла (а не полный путь), то файл должен располагаться в текущем каталоге (там же, где и запускаемая программа).

Пример работы с файлами:

#include <fstream>
using namespace std;

ifstream fin("input.txt");
ofstream fout("output.txt");

int main()
{
    int a, b;
    fin >> a >> b ; // Считать числа a и b из файлового потока fin
    fout << a + b << endl;
    return 0;
}

Напоминаем, что строки можно считывать из файла двумя способами - до пробельного символа при помощи оператора fin >> S и до конца строки при помощи функции getline(fin, S).

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

Упражнения

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

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

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

3A: A + B

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

2
2

4

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

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

1
2
3

6

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

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

Фамилия и имя — текстовые строки, не содержащие пробелов. Класс - одно из трех чисел 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

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

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

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

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

91.5 91.0 92.0

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

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

Выведите три числа: количество победителей олимпиады по 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

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

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

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

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

Сергеев Петр

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

2

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

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

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

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

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

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

80 81 82

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

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

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

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

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

92 2

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

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

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

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

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

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

2

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

В олимпиаде по информатике принимало участие 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

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

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

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

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

23 27

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

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

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

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

13 35

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

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

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

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

20

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

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

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

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

20

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

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

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

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

20

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

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

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

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

13 70 14 20

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

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

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

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

20 70 13

5C: Числа

Саша и Катя учатся в начальной школе. Для изучения арифметики при этом используются карточки, на которых написаны цифры (на каждой карточке написана ровно одна цифра). Однажды они пришли на урок математики, и Саша, используя все свои карточки, показал число A, а Катя показала число B. Учитель тогда захотел дать им такую задачу, чтобы ответ на нее смогли показать и Саша, и Катя, каждый используя только свои карточки. При этом учитель хочет, чтобы искомое число было максимально возможным.

Во входном файле записано два целых неотрицательных числа A и B (каждое число в одной строке). Длина каждого из чисел не превосходит 100000 цифр.

Выведите одно число — максимальное целое число, которое можно составить используя как цифры первого числа, так и цифры второго числа. Если же ни одного такого числа составить нельзя, выведите -1.

280138
798081

8810

123
456

-1

5D: Палиндром

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

PARALLELOGRAM

ALRARLA

ONE

E

5E: Проходной балл

Для поступления в вуз абитуриент должен предъявить результаты трех экзаменов в виде ЕГЭ, каждый из них оценивается целым числом от 0 до 100 баллов. При этом абитуриенты, набравшие менее 40 баллов (неудовлетворительную оценку) по любому экзамену из конкурса выбывают. Остальные абитуриенты участвуют в конкурсе по сумме баллов за три экзамена.

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

Программа получает на вход количество мест K. Далее идут строки с информацией об абитуриентах, каждая из которых состоит из имени (текстовая строка содержащая произвольное число пробелов) и трех чисел от 0 до 100, разделенных пробелами.

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

Также возможны две ситуации, когда проходной балл не определен.

Если будут зачислены все абитуриенты, не имеющие неудовлетворительных оценок, программа должна вывести число 0.

Если количество абитуриентов, имеющих равный максимальный балл больше чем K, программа должна вывести число 1.

Решение должно использовать O(1) памяти, то есть нельзя использовать списки, длина которых зависит от длины входных данных

5
Иванов Сергей 70 70 70
Сергеев Петр 100 100 0
Петров Василий 70 60 70
Васильев Андрей 70 60 70
Андреев Денис 100 30 100
Денисов Роман 50 50 50
Романов Григорий 60 70 70
Григорьев Николай 50 50 50
Николаев Иван 40 40 40

200

1
Иванов Сергей 40 40 40
Сергеев Петр 100 100 39

0

1
Иванов Сергей 60 60 60
Сергеев Петр 100 40 40

1