This repository contains programming tasks gathered from different programming language courses. Tasks are sorted by addition order.
Задача о рюкзаке (backpack.cpp)
Решить задачу о рюкзаке методом динамического программирования. Алгоритм должен быть инкапсулирован.
Данные подаются на стандартный поток ввода. Пустые строки игнорируются. Первая строка содержит натуральное число - максимальную массу предметов, которую выдержит рюкзак. Каждая последующая содержит два неотрицательных числа: массу предмета и его стоимость.
Первая строка содержит два числа: суммарную массу предметов и их суммарную стоимость. В последующих строках записаны номера предметов, которые были помещены в рюкзак, в порядке возрастания номера. Результат работы программы выводится в стандартный поток вывода. В любой непонятной ситуации результатом работы любой команды будет "error".
| Входные данные | Результат работы |
|
165 23 92 31 57 29 49 44 68 53 60 38 43 63 67 85 84 89 87 82 72 |
165 309 1 2 3 4 6 |
Сумасшедший богач (millionaire_dynamic.py, millionaire_fastest.py)
Один сумасшедший богач на старости лет впал в маразм и стал еще более сумасшедшим. Он решил отдать половину своих богатств тому, кто выиграет в математической игре. Правила игры: изначально каждый игрок начинает с нулевой суммой. Он может либо получить у богача 1 миллион сантиков, либо отдать ему 1 миллион сантиков, либо получить от богача ту же сумму, которая есть у него сейчас. Выигрывает тот, кто за минимальное количество действий наберет сумму, равную половине состояния богача. На беду других игроков, нашелся человек, который что-то слышал про жадные алгоритмы и двоичную систему счисления (возможно это вы).
В стандартном потоке записано единственное натуральное число - размер половины состояния богача (в миллионах).
Каждая строка выхода содержит ровно одну операцию (inc, dec или dbl) из кратчайшей последовательности действий для победы. Результат работы программы выводится в стандартный поток вывода.
| Входные данные | Результат работы |
| 23 |
inc dbl inc dbl dbl dbl dec |
Автокоррекция (word_correction.py)
Реализуйте программу, которая предлагает варианты замены слова, в котором допущена одна ошибка. Эту задачу можно решить достаточно многими способами - на это ограничений нет, но код должен быть хорошего качества и читаемым. Регистр букв для программы коррекции не имеет значения (слова в словаре хранятся в нижнем регистре). Варианты ошибок - как в алгоритме Дамерау-Левенштейна: вставка лишнего символа, удаление символа, замена символа или транспозиция соседних символов.
Данные подаются на стандартный поток ввода. Пустые строки игнорируются. Первая строка содержит число N - количество слов в словаре. Последующие N строк содержат слова из словаря, по одному в строке. Остальные строки - слова, которые надо проверять.
Каждая строка выхода содержит предложение для исправления слов, в порядке их появления. Если слово не содержит ошибок, то выводится "%слово% - ok". Если слово содержит одну ошибку, то выводится "%слово% -> %слово_в_словаре%". Если вариантов несколько, то они разделяются запятой с пробелом. Если слово содержит более одной ошибки, то выводится "%слово% -?" Результат работы программы выводится в стандартный поток вывода.
| Входные данные | Результат работы |
|
8 some random words for testing your solutions far some randoms wards seeking fro solution fur |
some - ok randoms -> random wards -> words seeking -? fro -> for solution -> solutions fur -> far, for |
Разложение на слагаемые (decompose.cpp, decompose2.cpp)
Дано натуральное число N. Рассмотрим его разбиение на различные натуральные слагаемые. Два разбиения, отличающихся только порядком слагаемых, будем считать за одно, поэтому можно считать, что слагаемые в разбиении упорядочены по невозрастанию.
Задано единственное число N. (N ≤ 40)
Необходимо вывести все разбиения числа N на различные натуральные слагаемые в обратном лексикографическом порядке.
| Входные данные | Результат работы |
| 5 |
5 4 1 3 2 3 1 1 2 2 1 2 1 1 1 1 1 1 1 1 |
Максимальный палиндром (maxpalindrome.py)
Палиндром - это строка, которая читается одинаково как справа налево, так и слева направо.
На вход программы поступает набор больших латинских букв (не обязательно различных). Разрешается переставлять буквы, а также удалять некоторые буквы. Требуется из данных букв по указанным правилам составить палиндром наибольшей длины, а если таких палиндромов несколько, то выбрать первый из них в алфавитном порядке.
В первой строке входных данных содержится число N (1 <= N <= 100000). Во второй строке задается последовательность из N больших латинских букв (буквы записаны без пробелов).
В единственной строке выходных данных выдайте искомый палиндром.
| Входные данные | Результат работы |
|
3 AAB |
ABA |
|
6 QAZQAZ |
AQZZQA |
|
6 ABCDEF |
A |
Сортировка матрицы (matrixSort.cpp)
Напишите алгоритм сортировки двумерного массива n на n такой, что A[i][j] ≤ A[k][m], если i+j < k+m. Внутри антидиагонали упорядоченность по возрастанию по строкам. Постарайтесь использовать O(1) памяти. Реализация алгоритма должна быть инкапсулирована.
Данные подаются на стандартный поток ввода. Первая строка содержит число N - размерность массива. Последующие N строк содержат N целых неотрицательных чисел, помещающихся в int32.
Вывод результирующей матрицы построчно через пробел.
| Входные данные | Результат работы |
|
3 1 3 2 7 8 9 6 8 9 |
1 2 6 3 7 8 8 9 9 |
Быстрая сортировка (quicksort.py)
Реализуйте эффективный алгоритм быстрой сортировки.
Ввод осуществляется со стандартного потока ввода. Первая и единственная строка всегда содержит входной массив. Все данные гарантированно валидны, проверять данные на корректность не нужно.
Результат работы - отсортированный массив. Результат работы программы выводится в стандартный поток вывода.
| Входные данные | Результат работы |
| 4 3 5 1 2 | 1 2 3 4 5 |
Бинарный поиск (binarysearch.py)
Реализуйте рекурсивно алгоритм бинарного поиска. Реализация алгоритма должна быть инкапуслирована, т.е. не зависеть от форматов входных/выходных данных и непосредственно ввода/вывода.
Ввод осуществляется со стандартного потока ввода. Первая строка всегда содержит отсортированный массив, в котором должен производится поиск. Остальные строки имеют формат search K, где K - некоторое число. Все данные гарантированно валидны, проверять данные на корректность не нужно.
Результат поиска - индекс числа в массиве. Если число в массиве отсутствует, то результатом будет -1. Результат работы программы выводится в стандартный поток вывода.
| Входные данные | Результат работы |
|
10 20 30 40 50 60 70 80 search 30 search 5 |
2 -1 |
Перестановки (permutations.py)
Реализуйте алгоритм генерации перестановок с началом в произвольной перестановке. Реализация алгоритма должна быть инкапсулирована и не зависеть от ввода/вывода.
На стандартном потоке ввода в первой и единственной строке задаётся перестановка — несколько чисел, разделенных пробелами.
На стандартный поток вывода выводятся построчно все последующие перестановки, включая входную, в лексикографическом порядке.
| Входные данные | Результат работы |
| 3 2 1 4 |
3 2 1 4 3 2 4 1 3 4 1 2 3 4 2 1 4 1 2 3 4 1 3 2 4 2 1 3 4 2 3 1 4 3 1 2 4 3 2 1 1 2 3 4 1 2 4 3 1 3 2 4 1 3 4 2 1 4 2 3 1 4 3 2 2 1 3 4 2 1 4 3 2 3 1 4 2 3 4 1 2 4 1 3 2 4 3 1 3 1 2 4 3 1 4 2 |
Самый частый элемент массива (mostcommon.py)
Реализуйте алгоритм поиска наиболее частого элемента массива, который работает за линейное время.
Ввод осуществляется со стандартного потока ввода. Первая и единственная строка всегда содержит входной массив. Все данные гарантированно валидны, проверять данные на корректность не нужно.
Результат поиска - самый частый элемент массива. Если таких чисел несколько, то наименьшее из них. Результат работы программы выводится в стандартный поток вывода.
| Входные данные | Результат работы |
| 2 5 1 3 5 4 2 3 5 4 3 4 5 4 5 | 5 |
Самый частый элемент массива 2 (mostcommon2.cpp)
Реализуйте алгоритм поиска наиболее частого элемента массива, который работает за линейное время.
На вход подается количество чисел n, после которого идет n чисел. Числа и их количество не превышают 1000000.
Результат поиска - самый частый элемент массива. Если таких чисел несколько, то наименьшее из них. Результат работы программы выводится в стандартный поток вывода. После числа с наибольшим количеством упоминаний вывести медианное число (в случае четного количества чисел, вывести минимальное).
| Входные данные | Результат работы |
|
2 4 5 |
4 4 |
|
4 8 8 8 8 |
8 8 |
|
8 9 7 8 3 1 9 7 7 |
7 7 |
|
7 4 8 5 7 8 4 9 |
4 7 |
|
3 6 9 1 |
1 6 |
Сферы в параллелепипедах (spheresinside.py)
В трёхмерном пространстве описан набор сфер и прямоугольных параллелепипедов. Требуется определить, находятся ли все сферы внутри параллелепипедов или нет.
В первой строке через пробел записаны 2 целых числа M и K - количество сфер и параллелепипедов соответственно. Оба числа не превышают 10. Далее идёт M строк по 4 числа в строке через пробел: целочисленные координаты X,Y,Z центров сфер (не превышают по модулю 1000) и целочисленный радиус (от 1 до 100). Далее - K строк, описывающих параллелепипеды, по 24 целых числа - координат вершин (не превышают по модулю 2000) в строке через пробел: X1 Y1 Z1 X2 Y2 Z2 X3 Y3 Z3 X4 Y4 Z4 X5 Y5 Z5 X6 Y6 Z6 X7 Y7 Z7 X8 Y8 Z8.
Номера сфер по порядку ввода (нумерация начинается с 1), которые не находятся полностью в параллелепипедах.
Параллелепипеды не могут быть вложены друг в друга, между собой не пересекаются и не соприкасаются.
| Входные данные | Результат работы |
|
2 1 1 1 1 1 10 10 10 2 0 0 0 10 0 0 0 10 0 10 10 0 0 0 10 10 0 10 0 10 10 10 10 10 |
2 |
Последняя цифра (lastdigit.py)
Для заданного в некоторой системе счисления числа N определить последнюю цифру числа N^k.
В строке через пробел записаны число C - основание системы счисления от 2 до 20, целое число N (не более 5 разрядов, в C-й системе счисления) и положительная целая степень k в десятичной системе счисления, не превышающая 100.
Последняя цифра N^k в C-й системе счисления.
| Входные данные | Результат работы |
| 2 111 3 | 1 |
| 16 AE 2 | 4 |
Минимальное число контейнеров (mincontainers.py)
Мама Малыша готовится к приёму гостей, ей срочно нужно приготовить очень много тефтелей. Готовые тефтели она решила раскладывать по кастрюлям и позвала Малыша помочь принести нужные кастрюли. Помогите Малышу определить минимальное количество кастрюль, которые потребуются.
В первой строке через пробел записаны целые числа N и M - минимальный общий объём кастрюль, который понадобится, и количество свободных кастрюль на кухне. Далее M строк, в каждой записано по одному вещественному числу - объём соответствующей кастрюли.
Номера кастрюль, которые надо принести Малышу, записанные по одному в строке, в порядке возрастания. Номера считать по порядку входных данных, начиная с единицы. Если подходит несколько возможных вариантов, то Малышу требуется принести самые большие кастрюли. В случае, если подходящих кастрюль нет, вывести слово NO.
| Входные данные | Результат работы |
|
5 4 1 3.5 2 4 |
2 4 |
|
3 5 1 0.8 1.2 2 1.5 |
4 5 |
Мороженое и холодильник (refrigerator.java)
Харитон любит мороженое. В своём любимом магазине мороженого Харитон каждому сорту мороженого присвоил рейтинг. Чем больше этот рейтинг, тем вкуснее мороженое с точки зрения Харитона. Каждый день в киоске некоторое мороженое назначаются мороженым дня и продают со скидкой. Харитон любит экономить, поэтому он покупает только мороженое дня или не покупает мороженого вообще. Если рейтинг мороженого дня не меньше, чем рейтинг самого вкусного мороженого, хранящегося в холодильнике Харитона, то он купит две порции этого мороженого. Одну съест сразу, а вторую положит в холодильник. Иначе Харитон не будет ничего покупать и съест самое вкусное мороженое из своего холодильника.
Требуется по заданной информации о мороженых дня за n дней определить, какое максимальное количество порций мороженого одновременно оказывалось в холодильнике Харитона на протяжении этих n дней. А также какое мороженое Харитон покупал чаще всего.
В первой строке содержится целое число (1<=n<=300000) - количество дней, для которых имеется информация о мороженом.
В каждой из следующих n строк содержится информация о мороженом дня в соответствующий день: наименование сорта мороженного s_j и через пробел его рейтинг r_j (0<=r_j<=1000000).
Наименование сорта мороженого s_j - непустая строка из строчных латинских букв, цифр и нижнего подчёркивания, начинающаяся с буквы и имеющая длину не более 30 символов.
Гарантируется, что для фиксированного наименования мороженого рейтинг сорта мороженого постоянный.
В первой строке выведите целое число m - максимальное число одновременно лежавших в холодильнике порций мороженого.
Во второй строке вывести целые числа v и k - максимальное количество раз, которое Харитон покупал мороженое одного и того же сорта, и количество сортов мороженого, которые Харитон покупал чаще всего.
Далее выведите k строк, в каждой строке укажите по одному наименованию сорта мороженого, которое Харитон покупал чаще всего. Наимеинования сортов выводите в лексикографическом (алфавитном) порядке.
| Входные данные | Результат работы |
|
14 strawberry 3 vanilla 5 blackberry 4 banana 3 strawberry 3 watermelon 2 lemon 6 vanilla 5 blackberry 4 vanilla2 4 strawberry 3 vanilla2 4 vanilla 5 strawberry 3 |
5 2 3 strawberry vanilla vanilla2 |
Мороженое и холодильник 2 (refrigerator2.java)
Харитон решил изменить стратегию. Он не станет покупать мороженое в двух случаях:
- Если в холодильнике имеется мороженое, которое лежит там уже d дней. В этом случае Харитон съест в этот день именно это мороженое.
- Если никакое мороженок не лежит в холодильнике d дней, но рейтинг мороженого дня меньше, чем рейтинг самого вкусного мороженого, которое есть у Харитона в холодильнике. В этом случае Харитон съест в этот день самое вкусное мороженое из своего холодильника. Если в холодильнике несколько порций мороженого с одинаковым рейтингом, то он съест то, которое купил последним.
Если рейтинг мороженого дня не меньше, чем рейтинг самого вкусного мороженого, хранящегося в холодильнике Харитона, и, кроме того, никакое мороженое в холодильнике не лежит уже d дней, Харитон купит две порции мороженого дня. Одну съест, а вторую положит в холодильник.
Требуется по заданной информации о мороженых дня за n дней определить:
- Сколько раз Харитон отказывался от покупки мороженого, рейтинг которого был выше, чем хотя бы у одного мороженого, имевшегося в тот момент в холодильнике.
- Максимальное количество дней, которое порция мороженого провела в холодильнике Харитона, и количество таких порций.
- Количество сортов мороженого, порции которого пробыли в холодильнике максимальное количество дней, и вывести список этих сортов в лексикографическом (алфавитном) порядке.
В первой строке содержатся целые числа n,d (1<=n<=300000, 1<=d<=100000) - количество дней, для которых имеется информация о мороженом дня, количество дней, в течение которого Харитон считает нахождение мороженого в холодильнике допустимым.
В каждой из следующих n строке содержится информация о мороженом дня в соответствующий день: наименование сорта мороженого s_j и через пробел его рейтинг r_j с точки зрения Харитона (j=1,2,...,n), (0<=r_j<=1000000)
Наименование сорта мороженого s_j - непустая строка из строчных латинских букв, цифр и нижнего подчёркивания, начинающаяся с буквы и имеющая длину не более 30 символов.
Гарантируется, что для фиксированного наименования мороженого рейтинг сорта мороженого постоянный.
В первой строке выведите целое число z - количество раз, которое Харитон отказывался от покупки мороженого, рейтинг которого был выше, чем хотя бы у одного мороженого, имевшегося в тот момент в холодильнике.
Во второй строке выведите целые числа p и q - максимальное количество дней, которое порция мороженого провела в холодильнике Харитона, и количество таких порций.
В третьей строке выведите целое число w - количество сортов, порции которых провели в холодильнике Харитона максимальное количество дней.
Далее выведите w строк - названия этих сортов в лексикографическом (алфавитном) порядке.
| Входные данные | Результат работы |
|
14 3 strawberry 3 vanilla 5 blackberry 4 banana 3 strawberry 3 watermelon 2 lemon 6 vanilla 5 blackberry 4 vanilla2 4 strawberry 3 vanilla2 4 vanilla 5 strawberry 3 |
1 3 2 2 blackberry strawberry |
|
8 4 blackberry 4 strawberry 3 vanilla 5 watermelon 2 banana 3 lemon 6 strawberry 3 vanilla 5 |
0 3 1 1 banana |
|
1 1 blackberry 4 |
0 0 1 1 blackberry |
Контрольная работа (controlwork.java)
Фалалель готовится к контрольной работе.
По просьбе Фалалеля его товарищ подобрал ему n задач, для каждой из которых указал уровень сложности d_j. По мнению товарища, Фалалей в начальный момент времени способен решать задачи с уровнем сложности, не превосходящим величину f. Для краткости будем говорить, что в начальный момент времени Фалалей обладает навыком f.
Фалалей решает задачи в порядке нумерации.
Возможны следующие исходы:
- Фалалей решает задачу и уровень сложности больше текущего навыка f. В этом случае Фалалель испытывает положительные эмоции, а его навык выростает до уровня сложности задачи.
- Фалалей решает задачу и уровень сложности не больше текущего навыка f. В этом случае Фалалелю становится скучно.
- Фалалей не решает задачу. В этом случае Фалалей испытывает отрицательные эмоции. Если при этом сложность задачи не больше навыка Фалалея, то его навык уменьшается на единицу.
Ваша задача - по представленным номерам задач определить:
- минимальный и максимальный уровни сложности задачи, которую Фалалей не решил к моменту, когда он завершил работу над задачей с представленным номером;
- каких эмоций Фалалей испытал больше к моменту, когда он завершил работу над задачей с заданным номером.
В первой строке содержатся целые числа n,m,f (1<= n,m <= 100000, 1 <= f<=1000000) - количество задач в наборе, количество заданных номеров задач и начальный навык Фалалея соответственно.
Во второй строке содержится n целых чисел d_1, d_2, ..., d_n (1<=d_j<=1000000, j=1,2,...,n) - уровни сложности задач.
В третьей строке содержится последовательность из n символов (без пробелов) A и R. Если на i-й позиции находится символ A, то Фалалей решил соответствующую задачу. Если R, то не решил.
В четвёртой строке содержится m целых чисел p_1, p_2, ..., p_m - номера задач, для которых нужно ответить на вопрос задачи.
Выведите m строк. Каждая строка должна содержать два целых числа и обозначение эмоции, которую Фалалей испытывал наиболее часто к этому моменту. Числа и обозначение эмоции должны быть разделены пробелами.
Первое и второе числа - это минимальный и максимальный уровень сложности задачи, которую Фалалей не решил к моменту завершения работы над задачей с номером p_i. Если к этому моменту Фалалель решил все предыдущие задачи, выведите -1.
Обозначение эмоции - это последовательность символов ":-)", ":-(" для положительных и отрицательных эмоций, ":-|" для скуки.
Если Фалалей к моменту завершения работы над задачей с номером p_i испытал одинаковое (максимальное) количество различных эмоций, следует выводить обозначение той эмоции, которую он испытал позже.
| Входные данные | Результат работы |
|
15 10 8 7 5 7 8 14 6 11 7 11 12 3 11 14 12 14 ARRAAARAAARRAAA 7 3 14 13 9 15 8 5 3 12 |
5 11 :-( 5 7 :-( 3 11 :-) 3 11 :-) 5 11 :-) 3 11 :-| 5 11 :-| 5 7 :-) 5 7 :-( 3 11 :-( |
|
3 4 5 7 3 8 AAA 3 2 1 3 |
-1 -1 :-) -1 -1 :-| -1 -1 :-) -1 -1 :-) |
Подготовка (preparations.java)
Харитон расспросил однокурсников, уже сдавших экзамен, какие дополнительные вопросы задавал им преподаватель.
Всего Харитон расспросил n однокурсников, и каждый из них перечислил Харитону заданные ему дополнительные вопросы. Для каждого дополнительного вопроса Харитон записывал тему, к которой этот вопрос относится.
Требуется выяснить, по каким темам было задано больше всего дополнительных вопросов.
В первой строке содержится целое число n (1<=n<=1000) - количество однокурсников, которых расспросил Харитон.
В каждой из следующих n строк содержится число m_i (0<=m_i<=1000) - количество дополнительных вопросов, на которые пришлось отвечать i-му однокурснику. Через пробел далее записаны m_i чисел t_1,t_2,...,t_m_i (1<=t_i<=1000000) - номера тем, к которым относились эти вопросы.
В первой строке выведите целые числа p и q - количество тем, по которым было задано максимальное количество дополнительных вопросов, и количество этих вопросов.
| Входные данные | Результат работы |
|
6 3 10 5 14 2 14 12 5 8 13 5 12 3 4 10 13 1 4 0 3 2 2 8 |
7 2 |
Регистрация (registration.py)
Предварительно создайте текстовый файл (accounts.txt), в котором структурирована информация вида: login -> password (не менее 5 пар). При этом на каждой строчке содержатся уникальные логины, а пароли могут повторяться. Создайте функцию регистрации нового пользователя, которая будет предлагать пользователю ввести логин и пароль до тех пор, пока не будет введён уникальный логин, и пароль не будет соответствовать требованиям:
- Наличие букв в разных регистрах
- Наличие цифры
- Наличие спецсимвола (@,!,$,#)
Корректная комбинация должна быть добавлена в текстовый файл accounts.txt.
Содержимое accounts.txt на начало работы:
login1 -> password
user -> friendly
summer -> qwerty
qbq812309 -> gdhjasdgj
nagibator228 -> systemCall1238sj
newUser -> Hey2201#
Две кучи (two_heaps.cpp)
Имеется 2<=N<=23 камня с целочисленными весами W1, W2, ... , WN. Требуется разложить их на две кучи таким образом, чтобы разница в весе куч была минимальной. Каждый камень должен принадлежать ровно одной куче.
N
W1 W2 ... WN
Минимальная неотрицательная разница в весе куч.
| Входные данные | Результат работы |
|
5 8 9 6 9 8 |
4 |
|
6 14 2 12 9 9 8 |
2 |
Польский калькулятор (calculator_polsk_prefix.cpp)
Для вычисления арифметических выражений на практике удобно использовать польскую запись. В ней операции записывают перед операндами, а не между как мы привыкли. Таким образом
- 2 1 = (2 - 1)
и
- * / 15 - 7 + 1 1 3 + 2 + 1 1 = 15 / (7 - (1 + 1)) * 3 - (2 + (1 + 1))
Вам необходимо написать калькулятор, который вычисляет значение арифметического выражения в префиксной записи. Размеры операндов и результаты операций не превосходят 1000.
| Входные данные | Результат работы |
| + 1 2 | 3 |
| - * / 15 - 7 + 1 1 3 + 2 + 1 1 | 5 |
Польский калькулятор (обратный) (calculator_polsk_reverse.py)
Задание связано с обратной польской нотацией. Она используется для парсинга арифметических выражений. Ещё её иногда называют постфиксной нотацией. В постфиксной нотации операнды расположены перед знаками операций.
В единственной строке дано выражение, записанное в обратной польской нотации. Числа и арифметические операции записаны через пробел. На вход могут подаваться операции: +, -, *, / и числа, по модулю не превосходящие 10000. Операция / является математическим целочисленным делением с округлением вниз. Гарантируется, что значение промежуточных выражений в тестовых данных по модулю не больше 50000.
Выведите единственное число - значение выражения.
| Входные данные | Результат работы |
| 3 4 + | 7 |
| 12 5 / | 2 |
| -1 3 / | -1 |
| 10 2 4 * - | 2 |
| 2 1 + 3 * | 9 |
| 7 2 + 4 * 2 + | 38 |
Торговый автомат (h11_authomata.cpp)
Одна фирма обслуживает автоматы по продаже чая и кофе. Стоимость стакана чая и кофе в автомате равна пяти рублям. Автомат принимает монеты по 5 и 10 рублей, а также купюры в 10, 50 и 100 рублей. Когда покупателю надо выдавать сдачу (т.е. когда пассажир бросил в автомат десятирублёвую монету или 10-, 50- или 100- рублёвую купюру), автомат выдаёт сдачу пятирублёвыми монетами; если же покупатель бросил в автомат пятирублёвую монету, то автомат её сохраняет и может использовать для сдачи следующим покупателям. Ясно, что, чтобы обеспечить возможность выдачи сдачи всем покупателям, может потребоваться изначально загрузить в автомат некоторое количество пятирублёвых монет.
Сейчас автоматы проходят испытания с целью определить минимальное количество монет, которые надо загрузить в автомат перед началом дня.Вам дан протокол одного из таких испытаний: известен порядок, в котором покупатели оплачивали свои покупки различными монетами и купюрами.Определите, какое минимальное количество пятирублёвых монет должно было изначально находиться в автомате, чтобы всем покупателям хватило сдачи.
В первой строке входных данных находится одно натуральное число N — количество покупок в автомате, которые были совершены в ходе испытания 1<=N<=50000. Во второй строке находятся N натуральных чисел, каждое из которых равно номиналу монеты или купюры, которую использовал очередной покупатель для оплаты; каждый номинал может принимать одно из четырёх значений: 5, 10, 50 или 100.
Выведите одно число — минимальное количество пятирублёвых монет, которые надо было загрузить в автомат изначально, чтобы всем покупателям хватило сдачи.
| Входные данные | Результат работы |
|
3 10 5 100 |
19 |
|
3 5 5 10 |
0 |
Обратное число по модулю (h12_reciprocal.cpp)
Известно, что команда деления целых чисел на современных компьютерах исполняется неприлично долго. Оптимизирующие компиляторы во многих случаях заменяют операцию деления на константу группой операций, в которых имеется умножение на другую константу.
Для этого компилятору, в числе других действий, требуется найти такое число q для заданного делителя p, что q * p = 1 по известному модулю m.
Ваша задача по заданным числам 2 <= p,m <= 4 294 967 295 найти любое число q такое, чтобы (p * q) (mod m) = 1.
Известно также, что m — простое число, и что для заданных p и m ответ существует.
p m
q
| Входные данные | Результат работы |
| 5 7 | 3 |
| 199212331 4010101141 | 525555399 |
Последовательность строк (h13_sequence.cpp)
Последовательность строк формируется следующим образом:
Первая строка состоит из цифры 1.
Каждая из последующих строк формируется из номера строки, записанного в виде последовательности десятичных цифр, за которым дописана предыдущая строка и затем перевёрнутая предыдущая строка.
Вот несколько первых строк:
1
211
3211112
432111122111123
5432111122111123321111221111234
Заметьте, что десятая строка начнётся с символов 10, одиннадцатая — с символов 11 и так далее.
Ваша задача заключается в том, чтобы по заданному номеру строки и номеру её элемента вывести символ, стоящий в ней на указанном месте.
N M
P1 P2 ... PM
Ограничения:
1<=N<=30
1<=M<=100000
1<=Pi<=length(string).
Нумерация строк и символов в строках начинается с единицы.
M символов, не разделённых пробелами, соответствующие позициям Pi.
| Входные данные | Результат работы |
|
5 5 2 4 6 8 10 |
42112 |
Перестановки (h14_permutation.cpp)
Как известно, из множества из N различных предметов можно сделать N! различных перестановок.
Если предметы можно сравнивать между собой, то перестановки можно перенумеровать в лексикографическом порядке. Например, перестановки множества {1,2,3} будут идти в следующем порядке: {1,2,3}, {1,3,2}, {2,1,3}, {2,3,1}, {3,1,2}, {3,2,1}.
Таким образом, все перестановки множества различных элементов можно пронумеровать от 1 до N!.
В нашей задаче мы будем переставлять элементы из множества натуральных чисел от 1 до N.
На вход программы подаётся два числа — количество предметов в перестановке 2<=N<=20 и номер перестановки 1<=M<=2*10e18.
Вывести через пробел элементы перестановки, имеющей номер M.
| Входные данные | Результат работы |
|
5 120 |
5 4 3 2 1 |
|
10 73238 |
1 3 9 6 8 4 7 2 10 5 |
Чуждые элементы (h15_alliens.cpp)
Последовательность из 2<=N<=1000000 элементов содержит натуральные числа от 1 до 10e18. Назовём пару соседних чисел, которая имеет общие множители, большие единицы, родственниками. В исходную последовательность вставляют натуральные числа (чуждые элементы) таким образом, что в итоговой последовательности не остаётся родственников. Требуется определить минимально возможную сумму чуждых элементов. Пример: в исходную последовательность
4 8 9 10
можно вставить чуждый элемент 5 после 4:
4 5 8 9 10
после чего последовательность не содержит родственников.
N
X1
X2
...
XN
Sum
| Входные данные | Результат работы |
|
10 4 8 1 2 4 2 1 7 62 3 |
3 |
Камера хранения (h21_storeroom.cpp)
На железнодорожном вокзале столицы Бурляндии решили установить новую автоматическую камеру хранения. Для этого потребовалось узнать, сколько ячеек одновременно занято хранящимся багажом. Было установлено несколько датчиков использования старой камеры хранения, фиксировавших момент прихода пассажира и занятия им ячейки, а так же момент ухода пассажира и момент освобождения им ячейки. Протокол прихода и ухода пассажиров за одни сутки приведён далее. Ячейка не освобождается мгновенно, поэтому если в какое-то время один пассажир ушёл и в это же время пришёл другой пассажир, требуется две ячейки. Определите максимальное количество одновременно занятых ячеек, наблюдаемое в течении суток.
Камера открыта круглосуточно. Времена прихода и ухода пассажиров находятся в пределах одних суток. В 00:00 камера хранения пуста.
N (количество пассажиров, 1<=N<=1000000).
HA1:MA1 HD1:MD1
...
HAN:MAN HDN:MDN
MaximumNumberOfBusyCells
| Входные данные | Результат работы |
|
5 02:18 11:54 03:18 04:16 00:26 20:41 17:19 20:48 08:42 23:45 |
3 |
|
10 17:59 22:58 12:25 16:06 09:05 18:39 08:34 23:23 15:59 22:53 15:55 21:20 18:05 22:08 03:48 22:23 12:50 14:41 05:46 10:41 |
7 |
Башня (h22_circus.cpp)
В Бурляндск приехал цирк. Одним из привлекающих внимание горожан номеров всегда было построение как можно более высокой башни из группы циркачей.
В построенной башне один циркач стоит на земле, второй - на его плечах, третий - на плечах второго, и так далее. У циркача под номером i вес равен wi, а сила — fi. Сила — способность удерживать на себе заданный вес. Точно известно, что более тяжёлый циркач является и более сильным. Впрочем, циркачи с одинаковым весом могут иметь различную силу.
Первая строка ввода содержит 4<=N<=3000 — количество человек в команде, которые хотят построить башню.
Каждая их последующих строк содержит по два числа — вес и силу участника команды. Все числа — положительные целые, меньшие 10000.
Максимальная высота башни, которую может построить эта команда.
| Входные данные | Результат работы |
|
4 1 9 5 13 13 15 16 20 |
4 |
Разрезание блинов (h23_cakes.cpp)
На очень большом столе разложено много абсолютно круглых блинов, некоторые из которых могут частично или полностью налегать друг на друга. Абсолютно прямым ножом проводится луч из первой точки по направлению ко второй. Требуется определить, какие из блинов будут задеты разрезом. Касания НЕ учитываются.
В первой строке — координаты двух точек на плоскости, которые определяют луч разреза. Во второй строке — количество блинов 1<=N<=100000. В следующих N строках по три числа — координаты центра блина и его радиус. Все координаты — целые числа от -10000 до 10000.
Радиус — строго положительное целое число.
Номера разрезанных блинов в порядке возрастания. Нумерация блинов начинается с 1.
| Входные данные | Результат работы |
|
0 0 0 1 5 -1 -1 1 -2 -2 1 -3 -3 4 1 2 4 3 1 1 |
4 |
|
0 0 0 1 2 3 0 3 3 0 1 |
Позитивизм (h24_positivism.cpp)
У Иеремии родители — философы. Он часто слышит их разговоры, но мало что в них понимает. Сам Иеремия учится в информатическом классе физматшколы, и философия его пока не интересует. Недавно он услышал новое для себя слово: позитивизм. Он постеснялся спросить своих родителей, что это слово обозначает, и узнал в Википедии, что-то про эмпирические и философские исследования. Так как слово ему понравилось, он загорелся идеей провести какие-то исследования, а так, как недавно в школе они проходили матрицы, вопрос, что же будет объектом исследования, оказался для него очевидным. Он называет позитивной матрицей такую двумерную матрицу, у которой сумма элементов каждой из строк неотрицательна и сумма элементов каждого из столбцов тоже неотрицательна.
Он поставил перед собой задачу установить, каждую ли из матриц можно сделать позитивной, имея ровно две операции: смену всех знаков на противоположные либо для всех элементов строки, либо для всех элементов столбца. Операции первого вида он записывал, как l y, где y — номер инвертируемой строки, а второго — как c x, где x — номер инвертируемого столбца. И столбцы и строки нумеруются с нуля. Он проделал серию экспериментов и убедился, что если решение существует, то оно может быть не единственным.
Ваша задача состоит в том, чтобы помочь Иеремии, написав программу, которая либо сообщит, что не существует такой последовательности операций, чтобы матрица стала позитивной, либо выдаст любую последовательность операций, приводящую в конечном итоге к позитивной матрице.
В первой строке — числа N и M — количество строк и столбцов соответственно. Эти числа не превосходят 100. В каждой из следующих N строк содержатся значения элементов каждой строки. Ни одно из этих чисел по абсолютной величине не превосходит 10e6.
Если матрицу можно сделать позитивной, то решение должно состоять из произвольного числа строк указанного выше вида. Если матрица позитивна с самого начала, программа ничего не должна выводить. Если её позитивной сделать нельзя, нужно вывести одно слово: Impossible.
| Входные данные | Результат работы |
|
3 3 1 -10 8 2 1 3 1 7 4 |
l 0 c 2 |
|
2 2 1 2 3 4 |
Количество подстрок (h25_strings.cpp)
Назовём подстрокой любой набор подряд идущих символов строки. Например, в строке aba можно найти три подстроки длины один: a, b, a, две подстроки длины два: ab и ba, а также одну подстроку длины 3: aba. Две подстроки здесь совпадают, поэтому различных подстрок здесь 5. Нужно для заданной строки, состоящей из строчных букв латинского алфавита, определить, сколько в ней можно найти различных подстрок.
Строка, длиной от 5 до 10000 символов.
Количество различных подстрок в данной строке.
| Входные данные | Результат работы |
| abracadabra | 54 |
Генератор Гауссовых слов (gausswordgenerator.py)
Гауссово слово – это слово, в котором все буквы встречаются ровно два раза. При этом вначале идет буква a, первая непарная ей – b, следующая непарная им – с, и так далее. Требуется написать программу, которая выведет все Гауссовы слова из букв от "a" вплоть до введённой латинской буквы.
Одна буква латинского алфавита.
Все возможные Гауссовы слова из заданного диапазона букв по одному слову на строчке.
| Входные данные | Результат работы |
| a | aa |
| c |
aabbcc aabcbc aabccb ababcc abbacc abbcac abbcca abacbc abcabc abcbac abcbca abaccb abcacb abccab abccba |
Накачка и сброс (pumpndump.py)
Pump'n'dump (накачка и сброс) - это схема относительно честного отъема денег. Она выглядит следуюшим образом. Несколько крупных игроков или много мелких договариваются вместе купить малоизвестную бумагу с низкой ценой и объёмом торгов. Это приводит к мгновенному взлету цены (pump), далее приходят неопытные игроки в надежде успеть заработать на таком росте. В этот момент организаторы схемы начнают все продавать (dump). Весь процесс занимает от нескольких минут до нескольких часов.
Ваша задача найти самый сильный pump'n'dump бумаги на заданном промежутке времени. Для этого для каждого дня определим число pnd, равное отношению максимальной цены бумаги в данный день к максимуму из цен открытия и закрытия в тот же день. Нужно найти день, когда pnd был максимален и его величину.
На вход подаётся много-много строк в формате дата цена. Самая первая цена за день - цена открытия. Самая последняя цена за день - цена закрытия. Гарантируется, что цены идут в хронологическом порядке.
Выведите самое большое число pnd
| Входные данные | Результат работы |
|
2020-07-19 18:00:00 20 2020-07-19 19:00:00 10 2020-07-19 20:00:00 30 2020-07-19 21:00:00 40 |
1 |
|
2020-07-19 21:00:00 20 2020-07-19 22:00:00 10 2020-07-19 23:00:00 40 2020-07-20 00:00:00 50 2020-07-20 01:00:00 10 2020-07-20 02:00:00 20 2020-07-20 03:00:00 15 2020-07-20 04:00:00 60 2020-07-20 05:00:00 10 |
1.2 |
|
2021-03-01 09:30:00 690 2021-03-01 10:30:00 703 2021-03-01 11:30:00 711 2021-03-01 12:30:00 714 2021-03-01 13:30:00 709 2021-03-01 14:30:00 710 2021-03-01 15:30:00 712 2021-03-02 09:30:00 719 2021-03-02 10:30:00 709 2021-03-02 11:30:00 705 2021-03-02 12:30:00 704 2021-03-02 13:30:00 699 2021-03-02 14:30:00 691 2021-03-02 15:30:00 686 2021-03-03 09:30:00 690 2021-03-03 10:30:00 679 2021-03-03 11:30:00 693 2021-03-03 12:30:00 680 2021-03-03 13:30:00 680 2021-03-03 14:30:00 666 2021-03-03 15:30:00 657 |
1.0043478260869565 |
Кубики (cubes.py)
Аня и Боря любят играть в разноцветные кубики, причем у каждого из них свой набор и в каждом наборе все кубики различны по цвету. Однажды дети заинтересовались, сколько существуют цветов таких, что кубики каждого цвета присутствуют в обоих наборах. Для этого они занумеровали все цвета случайными числами. На этом их энтузиазм иссяк, поэтому вам предлагается помочь им в оставшейся части. Номер любого цвета — это целое число в пределах от 0 до 109.
В первой строке входного файла записаны числа N и M — количество кубиков у Ани и Бори соответственно. В следующих N строках заданы номера цветов кубиков Ани. В последних M строках номера цветов кубиков Бори.
Выведите сначала количество, а затем отсортированные по возрастанию номера цветов таких, что кубики каждого цвета есть в обоих наборах, затем количество и отсортированные по возрастанию номера остальных цветов у Ани, потом количество и отсортированные по возрастанию номера остальных цветов у Бори.
| Входные данные | Результат работы |
|
4 3 0 1 10 9 1 3 0 |
2 0 1 2 9 10 1 3 |
|
2 2 1 2 2 3 |
1 2 1 1 1 3 |
| 0 0 |
0 0 0 |
Продажи (sales.py)
Дана база данных о продажах некоторого интернет-магазина. Каждая строка входного файла представляет собой запись вида Покупатель товар количество, где Покупатель — имя покупателя (строка без пробелов), товар — название товара (строка без пробелов), количество — количество приобретенных единиц товара. Создайте список всех покупателей, а для каждого покупателя подсчитайте количество приобретенных им единиц каждого вида товаров.
Вводятся сведения о покупках в указанном формате.
Выведите список всех покупателей в лексикографическом порядке, после имени каждого покупателя выведите двоеточие, затем выведите список названий всех приобретенных данным покупателем товаров в лексикографическом порядке, после названия каждого товара выведите количество единиц товара, приобретенных данным покупателем. Информация о каждом товаре выводится в отдельной строке.
| Входные данные | Результат работы |
|
Ivanov paper 10 Petrov pens 5 Ivanov marker 3 Ivanov paper 7 Petrov envelope 20 Ivanov envelope 5 |
Ivanov: envelope 5 marker 3 paper 17 Petrov: envelope 20 pens 5 |
|
Ivanov aaa 1 Petrov aaa 2 Sidorov aaa 3 Ivanov aaa 6 Petrov aaa 7 Sidorov aaa 8 Ivanov bbb 3 Petrov bbb 7 Sidorov aaa 345 Ivanov ccc 45 Petrov ddd 34 Ziborov eee 234 Ivanov aaa 45 |
Ivanov: aaa 52 bbb 3 ccc 45 Petrov: aaa 9 bbb 7 ddd 34 Sidorov: aaa 356 Ziborov: eee 234 |
Слишком серьёзная задача (tooserious.py)
Эконом прослушал курс по финансовым рынкам. Он показался ему слишком практическим. Теперь надо как-то применять знания на практике. Поэтому все скачали себе Пенькоф-Инвестиции и начали торговать. Это не является инвестиционной рекомендацией. Давайте немного помечтаем и представим, что нам стало так везти, что для любой ценной бумаги в любой день мы умудряемся купить её по минимальной цене и в тот же день продать по максимальной. Страшно подумать, как можно было бы приумножить свой капитал всего лишь за несколько дней...
Ваша задача - узнать во сколько раз вырастут ваши вложения при такой удаче. Все заработанные деньги вы реинвестируете. Короткие позиции запрещены. Продавать раньше, чем покупать запрещено. У вас нет премиум-аккаунта.
На вход подаётся много-много строк в формате дата цена. Гарантируетcя, что цена изменяется от 0 до 106.
Выведите свою максимальную доходность. В процентах. Сумма, которую вы изначально вкладываете в бумагу - неважна.
- Есть 100 рублей. Мы купили бумаги по 10 и продали по 40. В итоге у нас 400 рублей. Итоговая доходность 100*(40 - 10)/10 = 300%
- Есть 100 рублей. Мы купили бумаги по 20 и продали по 40. Ко второму дню у нас есть 200 рублей. Все полученные деньги мы реинвестировали. Купили за 20, продали за 60. В итоге у нас 600 рублей. Итоговая доходность 500%.
| Входные данные | Результат работы |
|
2020-07-19 18:00:00 20 2020-07-19 19:00:00 10 2020-07-19 20:00:00 30 2020-07-19 21:00:00 40 |
300 |
|
2020-07-19 21:00:00 20 2020-07-19 22:00:00 40 2020-07-19 23:00:00 10 2020-07-20 00:00:00 20 2020-07-20 01:00:00 60 2020-07-20 02:00:00 30 |
500 |
Очень быстрая сортировка (radix_sort.cpp)
Уметь сортировать быстро – полезный навык. Стандартные сортировки в языках Си и C++ достаточно быстры и универсальны. К сожалению, их универсальность имеет недостаток: сложность алоритмов этих сортировки составляет O(N log(N)). Между тем известно, что для некоторых типов данных имеются и сортировки со сложность по времени O(N). Вам и предстоит такую написать.
Файл, который вы должны послать в тестирующую систему, должен иметь реализацию ровно одной функции. Она должна ничего не вводить и ничего не выводить.
void fast_sort(unsigned *begin, unsigned *end) {
// Your code for implementation
}
Требуется, чтобы ваша функция отсортировала массив, заданный аргументами, по возрастанию. Ваша программа не должна содержать функции main.
Пример программы, которую можно использовать при тестировании:
int main() {
unsigned array[8] = {3,1,4,1,5,9,2,6};
fast_sort(array, array+8);
// Now array = {1,1,2,3,4,5,6,9}
}
Факториальная система счисления (r11_factradix.cpp)
Наряду с уже привычными позиционными системами счисления, к которым мы все уже привыкли, существует множество других, всё также позиционных, но с другими правилами вычисления весов позиций. Мы рассмотрим факториальную систему счисления, в которой вес каждой позиции — факториал от её номера. Для позиций после десятичной точки используются обратные к факториалам веса. Каждая правильная дробь (p < q) представляется в такой системе единственным конечным образом при условии, что в самом правом члене записи коэффициент отличен от нуля. Ваша задача — найти такие числа ai < i, чтобы сумма их произведений на факториалы их индексов i равнялась заданной дроби.
1 <= P < Q < 1000
В одной строке через пробел выведите коэффициенты разложения, начиная с a2.
Гарантируется, что число выводимых членов будет меньше 1000.
| Входные данные | Результат работы |
| 1 4 | 0 1 2 |
| 5 7 | 1 1 1 0 4 2 |
Танец точек (r12_dance.cpp)
На прямой располагается 1<=N<=10000 точек с целочисленными координатами −10e9<=Vi<=10e9. Каждой из точек разрешается сделать ровно одно движение (танцевальное па) в любом направлении на расстояние не больше 0<=L<=10e8 и остановиться на другой позиции. Какое минимальное количество точек может оказаться после окончания танца (все точки после танца, оказывающиеся на одной позиции сливаются в одну)?
L N
V1
V2
...
VN
MinimalNumberOfPoints
| Входные данные | Результат работы |
|
10 5 30 3 14 19 21 |
2 |
Офисное здание (r13_complaints.cpp)
Эта задача аналогична задаче h21_storeroom за исключением точности до секунд.
В одной очень большой стране в одном очень большом городе стояло очень-очень большое здание, в котором граждане этой страны подавали жалобы на других граждан. Так как жалобщиков было очень много, оно работало круглосуточно, но каждый из посетителей, пришедших в какое-то время после нуля часов, был обязан покинуть здание до 24 часов. Клерков, принимающих жалобы, было не очень много, из-за чего гражданам приходилось сидеть и ждать в очереди, пока нужный клерк освободится. На эту организацию, принимающую жалобы, в неё же поступила жалоба, что жалобы рассматриваются недостаточно быстро и вам было поручено определить, а сколько же жалобщиков одновременно находится в здании. К счастью для вас, во всех жителей этой страны были встроены чипы, точно определяющие положение в любой момент времени. Вам был дан доступ к данным за сутки. В 00:00:00 здание жалобщиков не ещё не содержало, а в 24:00:00 уже не содержало, так как все жалующиеся покинули здание. Дверей в здании много, поэтому вполне могли случаться такие ситуации, когда в одну и ту же секунду один жалобщик прибывал, а другой — покидал помещение. В таком случае оба считались находящимися в здании. Ваша задача — определить максимальное число жалобщиков, одновременно находящихся в здании.
На вход программы подаётся число 1<=N<=200000 — число записей в базе данных. Каждая запись имеет содержит два времени с точностью до секунд — время прибытия и время убытия в формате HH:MM:SS.
Одно число — максимальное количество жалобщиков, одновременно находящихся в здании.
| Входные данные | Результат работы |
|
5 02:03:42 20:44:18 02:01:25 13:54:01 13:04:48 23:39:34 02:08:16 19:30:44 01:02:34 08:00:07 |
4 |
Подмножества (r14_subsets.cpp)
Множество задано строкой, то есть каждая буква есть элемент множества. Но это множество — не совсем простое. Элементы в нём могут повторяться. Два подмножества считаются одинаковыми, если все элементы одного множества совпадают с элементами другого. Например, множества, представленные строками abc и cba совпадают. Совпадают также множества abra и raba. Ваша задача по заданной строке, представляющей исходное множество, вывести все различные его подмножества, каждое на отдельной строке вывода. Выводить можно в произвольном порядке. Выход не должен содержать совпадающие подмножества. Пустое множество тоже является подмножеством исходного.
Исходное множество в виде строки
Все уникальные подмножества исходного множества по одному на строку. Подмножества не требуется как-либо упорядочивать, будет принят любой верный ответ.
Не забудьте, что пустая строка — тоже верное подмножество. В приведённом примере она следует первой, перед строкой a.
| Входные данные | Результат работы |
| abra |
a b ba ar rb aa raab baa abr ara r |
|
|
|
| Q1aQQ |
QQa Qa 1 1a QQQa QQQ 1QQQ a 1Q 1QQ 1QQQa 1QQa Q 1Qa |
Игра в 2048 (game2048.cpp)
Петя решил поиграть в известную игру 2048. Но играть в классическую версию ему уже неинтересно и он разработал улучшенную версию. У игрока имеется набор из нескольких чисел, где каждое число - степень двойки с натуральным показателем, не превыщающим n. Каждый ход игрок может сделать одно из следующих действий:
Сгенерировать число 2^k, это действие занимает ak секунд.
Умножить все имеющиеся числа на 2. При этом, если вы умножаете на 2 число 2^n, оно превращается в число 2. Такое действие занимает x секунд.
Например, если вы собрали набор 2, 32, 128 и n=7, то после выполнения второго действия у вас будет набор 4, 64, 2. Игра заканчивается, когда вы собираете ровно n чисел, и все они различны. Изначально у игрока нет чисел. Все ходы выполняются последовательно, один за одним. Петя решил провести соревнования по новой игре, и вы принимаете в нём участие. Спланируйте свою тактику так, чтобы быстрее всего закончить игру.
В первой строке даны два натуральных числа n (2<=n<=2000) и x (1<=x<=10e9) - требуемое количество чисел и время работы умножителя. Во второй строке задано n целых чисел ai (1<=ai<=10e9) - время генерации числа 2^i.
Выведите одно число - минимальное количество времени, необходимое для прохождения игры.
| Входные данные | Результат работы |
|
3 5 1 2 3 |
6 |
|
4 5 1 100 3 4 |
13 |
В первом тесте невыгодно использовать второе действие, поэтому просто последовательно сгенерируем все степени двойки. Во втором тесте выгодно сгенерировать за первые два хода (2,8), после этого умножить их на два, получить набор (4,16), и за два хода сгенерировать 2 и 8. Ответ: 1+3+5+1+3=13.
Несколько классов (several_classes.cpp)
Разработать набор классов, объекты которых реализуют типы данных, указанные ниже. С помощью перегрузки операторов (operator) разработать стандартную арифметику объектов, включающую арифметические действия над объектами и стандартными типами (целыми, вещественными, строками – в зависимости от вида объектов), присваивание, ввод и вывод в стандартные потоки (используя операторы «<<» и «>>»), приведение к/от базового типа данных. Организовать операции в виде конвейера значений, с результатом (новым объектом) и сохранением значений входных операндов.
-
Дата и время, представленные целочисленными переменными: год, месяц, день, час, минута, секунда. Базовый тип: uint64_t формат представления unix time. Реализовать возможность преобразования в/из формата представления filetime (целое 64-х разрядное значение, представляющее число интервалов по 100 наносекунд, прошедших с первого января 1601 года).
-
Год «от Адама», имеющий внутреннее представление в виде целочисленных переменных: индикт, круг солнцу, круг луне. Диапазоны значений (циклические): индикт 1—15, круг солнцу 1—28, круг луне 1—19. Ежегодно каждая переменная увеличивается на 1. Итоговое значение вычисляется как произведение переменных (диапазона на некоторый множитель; переменные независимы), а хранимое значение является остатком от деления (на диапазон), при этом 0 соответствует максимум. Необходима возможность отображения/задания как в виде одного числа, так и виде трех. Реализовать возможность преобразования в/из формата представления «от рождества Христова» используя соответствие 1652 = 7160 «от Адама».
-
Разреженная матрица, представленная динамическим массивом структур, содержащих описания ненулевых коэффициентов: индексы местоположения коэффициента в матрице (целые) и значение коэффициента (вещественное).
Агата и Кристи (agata_kristie.cpp)
Кристи и Агата – лучшие подруги. Они любят проводить свободное время за разгадыванием головоломок. В этот раз загадку подготовила Кристи, помогите Агате справиться с задачей. Даны n чисел ai (1 <= ai <= 200000). Также имеются q запросов вида (lj , rj) – такой запрос означает, что надо сложить все числа на отрезке от lj до rj включительно и вернуть полученную сумму. Кристи дала Агате набор чисел и сами запросы. Задача Агаты – расставить числа ai на позициях от 1 до n (по одному на позицию) так, чтобы сумма ответов на все q запросов была как можно больше. Помогите Агате!
В первой строке через пробел даны количество чисел в наборе – n (1 <= n <= 200000) и количество запросов q (1 <= q <= 200000). Во второй строке даны числа ai (1 <= ai <= 200000), записанные через пробел. В следующих q строках даны запросы по одному в строке. Запрос j состоит из двух чисел lj и rj , записанных через пробел (1 <= lj <= rj <= n).
Выведите единственное число – максимальную сумму ответов на запросы, которую может получить Агата.
| Входные данные | Результат работы |
|
5 3 1 9 4 3 1 1 4 2 2 3 5 |
34 |
|
1 1 5 1 1 |
5 |
|
2 2 8 4 1 1 2 2 1 1 |
12 |
Физрук Арсений (gym_teacher.cpp)
В начале урока физкультуры ученики 13А класса выстроились в ряд. Физрук Арсений любит порядок, но школьники опять встали не по росту. Он решил проучить их и выбрать какой-то хороший отрезок детей, и отправить их играть в волейбол, а остальных оставить выполнять нормативы. Хорошим отрезком детей Арсений называет такой непрерывный отрезок детей в ряду, что их рост строго убывает. Ученики любят волейбол, поэтому хотят понять, есть ли у них шанс оказаться в числе счастливчиков. Для этого каждый школьник хочет выяснить, как много людей может пойти играть с ним в волейбол, то есть найти длину наибольшего хорошего отрезка, содержащего его самого.
Первая строка содержит одно целое число n (1 <= n <= 100000) — количество учеников 13А, пришедших на урок. Вторая строка содержит n целых чисел a1, a2, ..., an (1 <= ai <= 1000000000) — рост школьников в том порядке, в котором они встали изначально.
Выведите n целых чисел через пробел, где i-е число — максимальная длина хорошего отрезка, содержащего школьника номер i.
Примеры
| Входные данные | Результат работы |
|
5 7 4 2 2 10 |
3 3 3 1 1 |
|
5 2 4 6 4 2 |
1 1 3 3 3 |
Гурман (gourmet.cpp)
Нитуширг в жизни больше всего любит две вещи - вкусно поесть и отдыхать на море. Поэтому он решил совместить приятное с приятным и поехать на пятизвёздочный морской курорт Фокьнит. Но вот незадача: в Фокьните есть только одна столовая, меню в которой каждый день заранее фиксировано. Поскольку Нитуширг - гурман, он предпочитает разнообразие в еде, поэтому если за время отдыха какое-то меню попадётся более K раз - Нитуширг очень расстроится и весь отпуск пойдёт насмарку. При этом, разумеется, Нитуширг хочет отдохнуть на море как можно дольше. Ваша задача состоит в том, чтобы по известному заранее меню столовой на N дней выбрать как можно более длинный отрезок подряд идущих дней, в которые Нитуширг поедет в Фокьнит так, чтобы никакой набор блюд не повторялся более K раз за всё время поездки.
В первой строке вам даны целые числа 1 <= N <= 100000 и 1 <= K <= N - количество дней, когда Фокьнит открыт для гостей и K - максимальное количество раз, которое может повториться меню за время отпуска. В следующей строке входного файла вам дана строка, состоящая из N строчных латинских букв. Каждая буква означает свой вариант меню, разным меню соответствуют разные буквы.
На выход ваша программа должна вывести два целых числа: 1 <= L <= N - максимальное количество дней отпуска Нитуширга и 1 <= d0 <= N - номер дня заезда. Считайте, что в день заезда Нитуширг успевает съесть предлагаемое столовой меню.
| Входные данные | Результат работы |
|
1 1 a |
1 1 |
|
6 2 abbbaa |
4 3 |
Структура данных - Дек (data_structure_deck.py)
Гоша реализовал структуру данных Дек, максимальный размер которого определяется заданным числом. Методы push_back(x), push_front(x), pop_back(), pop_front() работали корректно. Но, если в деке было много элементов, программа работала очень долго. Дело в том, что не все операции выполнялись за О(1). Помогите Гоше! Напишите эффективную реализацию. При реализации нельзя использовать связный список.
В первой строке записано количество команд n - целое число, не превосходящее 5000. Во второй строке записано число m - максимальный размер дека. Он не превосходит 1000. В следующих n строках записана одна из команд:
- push_back(value) - добавить элемент в конец дека. Если в деке уже находится максимальное число элементов, вывести 'error'.
- push_front(value) - добавить элемент в начало дека. Если в деке уже находится максимальное число элементов, вывести 'error'.
- pop_back() - вывести последний элемент дека и удалить его. Если дек был пуст, то вывести 'error'.
- pop_front() - вывести первый элемент дека и удалить его. Если дек был пуст, то вывести 'error'. value - целое число, по модулю не превосходящее 1000.
Выведите результат выполнения кадой команды на отдельной строке. Для успешных запросов push_back(x) и push_front(x) ничего выводить не надо.
| Входные данные | Результат работы |
|
4 4 push_front 861 push_front -819 pop_back pop_back |
861 -819 |
|
7 10 push_front -855 push_front 720 pop_back pop_back push_back 844 pop_back push_back 823 |
-855 720 844 |
Сжиматель фоток (BMP_image_resizer/BMP_image_resizer.cpp)
В файле pic.bmp задано изображение в формате True Color 32 бита на пиксел. Написать программу на языке C++, которая загружает это изображение в программу, масштабирует изображение таким образом, чтобы его ширина и высота уменьшились бы втрое и выводит в файл pic2.bmp. В каждой точке создаваемого изображения каждая компонента цвета должна быть выбрана в виде среднего значения из девяти значений из квадрата 3х3 вокруг соответствующей точки на исходном изображении. В граничных точках размер области вокруг соответствующей точки на исходном изображении может быть меньше. Вся отведенная память в программе должна быть очищена. Все открытые файлы должны быть закрыты.
Скобочная последовательность (bracketssequence.py)
Дана скобочная последовательность. Нужно определить, правильная ли она. Будем придерживаться такого определения:
- пустая строка - правильная скобочная последовательность;
- правильная скобочная последовательность, взятая в скобки одного типа является правильной скобочной последовательностью;
- правильная скобочная последовательность с приписанной слева или справа правильной скобочной последовательностью - тоже правильная.
На вход подаётся последовательность из скобок трёх видов: [], (), {}. Напишите функцию is_correct_bracket_seq, которая принимает на вход скобочную последовательность и возвращает True, если последовательность правильная, а иначе False.
На вход подаётся одна строка, содержащая скобочную последовательность. Скобки записаны подряд, без пробелов.
Выведите True или False
| Входные данные | Результат работы |
| {[()]} | True |
| () | True |
| ({)} | False |
Списочная очередь (listqueue.py)
Любимый вариант очереди Тимофея - очередь, написанная с использованием связного списка. Помогите ему с реализацией. Очередь должна поддерживать выполнение трёх команд:
- get() - вывести элемент, находящийся в голове очереди, и удалить его. Если очередь пуста, то вывести "error";
- put(x) - добавить число x в очередь;
- size() - вывести текущий размер очереди.
В первой строке записано количество команд n - целое число, не превосходящее 1000. В каждой из следующих n строк записаны команды по одной строке.
Напечатайте результаты выполнения нужных команд, по одному на строке.
| Входные данные | Результат работы |
|
10 put -34 put -23 get size get size get get put 80 size |
-34 1 -23 0 error error 1 |
|
6 put -66 put 98 size size get get |
2 2 -66 98 |
|
9 get size put 74 get size put 90 size size size |
error 0 74 0 1 1 1 |
Ограниченная очередь (sizedqueue.py)
Нужно написать класс MyQueueSized, который принимает параметр max_size, означающий максимально допустимое количество элементов в очереди. Реализуйте программу, которая будет эмулировать работу такой очереди. Функции, которые надо реализовать, описаны в формате ввода.
В первой строке записано одно число - количество команд, оно не превосходит 5000. Во второй строке задан максимально допустимый размер очереди, он не превосходит 5000. Далее идут команды по одной на строке. Команды могут быть следующих видов:
- push(x) - добавить число x в очередь;
- pop() - удалить число из очереди и вывести на печать;
- peek() - напечатать первое число в очереди;
- size() - вернуть размер очереди.
При превышении допустимого размера очереди нужно вывести "error". При вызове операций pop() или peek() для пустой очереди нужно вывести "None".
Напечатайте результаты выполнения нужных команд, по одному на строке.
| Входные данные | Результат работы |
|
8 2 peek push 5 push 2 peek size size push 1 size |
None 5 2 2 error 2 |
|
10 1 push 1 size push 3 size push 1 pop push 1 pop push 3 push 3 |
1 error 1 error 1 1 error |
Стек (stack.py)
Нужно реализовать класс StackMax, который поддерживает операцию определения максимума среди всех элементов в стеке. Класс должен поддерживать операции push(x), где x - целое число, pop() и get_max().
В первой строке записано одно число n - количество команд, которое не превосходит 10000. В следующих n строках идут команды. Команды могут быть следующих видов:
- push(x) - обавить число x в стек;
- pop() - удалить число с вершины стека;
- get_max() - напечатать максимальное число в стеке
Если стек пуст, при вызове команды get_max() нужно напечатать "None", для команды pop() - "error".
Для каждой команды get_max() напечатайте результат её выполнения. Если стек пустой, для команды get_max() напечатайте "None". Если происходит удаление из пустого стека - напечатайте "error".
| Входные данные | Результат работы |
|
8 get_max push 7 pop push -2 push -1 pop get_max get_max |
None -2 -2 |
|
7 get_max pop pop pop push 10 get_max push -9 |
None error error error 10 |
Транспонирование матрицы (transposeMatrix.py)
Есть матрица размера m x n. Нужно написать функцию, которая её транспонирует. Транспонированная матрица получается из исходной заменой строк на столбцы.
В первой строке задано число m - количество строк матрицы. Во второй строке задано n - число столбцов. m,n<=1000
В следующих m строках задана матрица. Числа в ней не превосходят по модулю 1000.
Напечатайте транспонированную матрицу в том же формате, который задан во входных данных. Каждая строка матрицы выводится на отдельной строке, элементы разделяются пробелами.
| Входные данные | Результат работы |
|
4 3 1 2 3 0 2 6 7 4 1 2 7 0 |
1 0 7 2 2 2 4 7 3 6 1 0 |
|
9 5 -7 -1 0 -4 -9 5 -1 2 2 9 3 1 -8 -1 -7 9 0 8 -8 -1 2 4 5 2 8 -7 10 0 -4 -8 -3 10 -7 10 3 1 6 -7 -5 9 -1 9 9 1 9 |
-7 5 3 9 2 -7 -3 1 -1 -1 -1 1 0 4 10 10 6 9 0 2 -8 8 5 0 -7 -7 9 -4 2 -1 -8 2 -4 10 -5 1 -9 9 -7 -1 8 -8 3 9 9 |
Два велосипеда (binarysearch2.py)
Вася решил накопить на два одинаковых велосипеда - себе и сестре. У Васи есть копилка, в которую каждый день он может добавлять деньги. В процессе накопления Вася не вынимает деньги из копилки. У вас есть информация о росте Васиных накоплений - сколько у Васи в копелке было денег в каждый из дней.
Ваша задача - по заданной стоимости велосипеда определить первый день, в который Вася смог бы купить один велосипед, а также первый день, в который он бы мог купить два велосипеда. Решение должно работать за O(log n).
В первой строке дано число дней n, по которым велись наблюдения за Васиными накоплениями. 1<=n<=1000000. В следующей строке записаны n целых неотрицательных чисел. Числа идут в порядке неубывания. Каждое из чисел не превосходит 1000000. В третьей строке записано целое положительное число s - стоимость велосипеда. Это число не превосходит 1000000.
Нужно вывести два числа - номера дней по условию задачи. Если необходимой суммы в копилке не нашлось, нужно вернуть -1 вместо номера дня.
| Входные данные | Результат работы |
|
6 1 2 4 4 6 8 3 |
3 5 |
|
6 1 2 4 4 4 4 3 |
3 -1 |
|
6 1 2 4 4 4 4 10 |
-1 -1 |
|
4 1 10 10 10 2 |
2 2 |
Генератор скобок (bracketsgenerator.py)
Рита по поручению Тимофея наводит порядок в правильных скобочных последовательностях (ПСП), состоящих только из круглых скобок (). Для этого ей надо сгенерировать все ПСП длины 2n в алфавитном порядке - алфавит состоит из ( и ) и открывающаяся скобка идёт раньше закрывающей. Помогите Рите - напишите программу, которая по заданному n выведет все ПСП в нужном порядке.
Рассмотрим второй пример. Надо вывести ПСП из четырёх символов. Таких всего две:
- (())
- ()()
(()) идёт раньше ()(), так как первый символ у них одинаковый, а на второй позиции у первой ПСП стоит (, который идёт раньше ).
На вход функция принимает n - целое число от 0 до 10.
Функция должна напечатать все возможные скобочные последовательности заданной длины в алфавитном (лексикографическом) порядке.
| Входные данные | Результат работы |
| 3 |
((())) (()()) (())() ()(()) ()()() |
| 2 |
(()) ()() |
| 4 |
(((()))) ((()())) ((())()) ((()))() (()(())) (()()()) (()())() (())(()) (())()() ()((())) ()(()()) ()(())() ()()(()) ()()()() |
Комбинации (combinations_mobile.py)
На клавиатуре старых мобильных телефонов каждой цифре соответствовало несколько букв. Примерно так: 2: 'abc' 3: 'def' 4: 'ghi' 5: 'jkl' 6: 'mno' 7: 'pqrs' 8: 'tuv' 9: 'wxyz'
Вам известно в каком порядке были нажаты кнопки телефона, без учёта повторов. Напечатайте все комбинации букв, которые можно набрать такой последовательностью нажатий.
На вход подаётся строка, состоящая из цифр 2-9 включительно. Длина строки не превосходит 10 символов.
Выведите все возможные комбинации букв через пробел.
| Входные данные | Результат работы |
| 23 | ad ae af bd be bf cd ce cf |
| 92 | wa wb wc xa xb xc ya yb yc za zb zc |
| 228 | aat aau aav abt abu abv act acu acv bat bau bav bbt bbu bbv bct bcu bcv cat cau cav cbt cbu cbv cct ccu ccv |
Большое число (bignumber.py)
Вечером ребята решили поиграть в игру "Большое число". Даны числа. Нужно определить, какое самое большое число можно из них составить.
В первой строке записано n - количество чисел. Оно не превосходит 100. Во второй строке через пробел записаны n неотрицательных чисел, каждое из которых не превосходит 1000.
Нужно вывести самое большое число, которое можно составить из данных чисел.
| Входные данные | Результат работы |
|
3 15 56 2 |
56215 |
|
3 1 783 2 |
78321 |
|
5 2 4 5 2 10 |
542210 |
|
6 9 10 1 1 1 6 |
9611110 |
|
38 82 58 66 34 64 37 40 97 93 52 28 98 90 64 19 22 21 83 56 70 46 17 31 51 55 41 68 18 98 89 88 74 6 6 31 36 35 8 |
9898979390898888382747068666664645856555251464140373635343131282221191817 |
Клумбы (segmentsunion.py)
Алла захотела, чтобы у неё под окном были узкие клумбы с тюльпанами. На схеме земельного участка клумбы обозначаются просто горизонтальными отрезками, лежащими на одной прямой. Для ландшафтных работы было нанято n садовников. Каждый из них обрабатывал какой-то отрезок на схеме. Процесс был организован не очень хорошо, иногда один и тот же отрезок или его часть могли быть обработаны сразу несколькими садовниками. Таким образом, отрезки, обрабатываемые двумя разными садовниками, сливаются в один. Непрерывный обработанный отрезок затем станет клумбой. Нужно определить границы будущих клумб.
В первой строке записано n - количество отрезков. В следующих n строках через пробел записаны 2 неотрицательных числа.
Вывести границы будущих клумб.
| Входные данные | Результат работы |
|
4 7 8 7 8 2 3 6 10 |
2 3 6 10 |
|
4 2 3 5 6 3 4 3 4 |
2 4 5 6 |
|
6 1 3 3 5 4 6 5 6 2 4 7 10 |
1 6 7 10 |
Гардероб (wardrobe.py)
Рита решила оставить у себя одежду только трёх цветов: розового, жёлтого и малинового. После того как вещи других расцветок были убраны, Рита захотела отсортировать свой новый гардероб по цветам. Сначала должны идти вещи розового цвета, потом - жёлтого, и в конце - малинового. Помогите Рите справиться с этой задачей.
В первой строке задано количество предметов в гардеробе: n - оно не превосходит 1000000. Во второй строке даётся массив, в котором указан цвет для каждого предмета. Розовый цвет обозначен 0, жёлтый - 1, малиновый - 2.
Нужно вывести в строку через пробел цвета предметов в правильном порядке.
| Входные данные | Результат работы |
|
7 0 2 1 2 0 0 1 |
0 0 0 1 1 2 2 |
|
5 2 1 2 0 1 |
0 1 1 2 2 |
|
6 2 1 1 2 0 2 |
0 1 1 2 2 2 |
| 0 |
Подпоследовательность (issubsequence.py)
Даны 2 строки, нужно понять, является ли первая из них подпоследовательностью второй. Когда строки достаточно длинные, очень трудно получить ответ на этот вопрос, просто посмотрев на них. Помогите Гоше написать функцию, которая решает эту задачу.
В первой строке записана строка s. Во второй - строка t.
Обе строки состоят из маленьких латинских букв, длины строк не превосходят 150000. Строки могут быть пустыми.
Выведите True, если s является подпоследовательностью t, иначе - False.
| Входные данные | Результат работы |
|
abc ahbgdcu |
True |
|
abcp ahpc |
False |
|
abcd dkajsdlkbca |
False |
|
anystring |
True |
Пузырек (bubblesort.py)
Требуется реализовать алгоритм сортировки пузырьком (по неубыванию):
- На каждой итерации проходим по массиву, поочередно сравниваем пары соседних элементов. Если элемент на позиции i больше элемента на позиции i+1, то меняем их местами. После первой итерации самый большой элемент всплывёт в конце массива.
- Проходим по массиву, выполняя указанные действия до тех пор, пока на очередной итерации не окажется, что обмены больше не нужны, то есть массив уже отсортирован.
- После не более, чем n-1 итераций выполнение алгоритма заканчивается, так как на каждой итерации хотя бы один элемент оказывается на правильной позиции.
В первой строке на вход подаётся натуральное число n - длина массива, 2<=n<=1000. Во второй строке через пробел записано n целых чисел. Каждое из чисел по модулю не превосходит 1000.
После каждого прохода по массиву, на котором какие-то элементы меняются местами, выводите его промежуточное состояние. Таким образом, если сортировка завершена за k меняющих массив итераций, то надо вывести k строк по n чисел в каждой - элементы массива после каждой из итераций. Если массив был изначально отсортирован, то просто выведите его.
| Входные данные | Результат работы |
|
2 4 51 |
4 5 |
|
5 1 1 1 1 1 |
1 1 1 1 1 |
|
5 4 3 9 2 1 |
3 4 2 1 9 3 2 1 4 9 2 1 3 4 9 1 2 3 4 9 |
|
5 12 8 9 10 11 |
8 9 10 11 12 |
|
10 87 123 23 9 71 2 11 23 -99 0 |
87 23 9 71 2 11 23 -99 0 123 23 9 71 2 11 23 -99 0 87 123 9 23 2 11 23 -99 0 71 87 123 9 2 11 23 -99 0 23 71 87 123 2 9 11 -99 0 23 23 71 87 123 2 9 -99 0 11 23 23 71 87 123 2 -99 0 9 11 23 23 71 87 123 -99 0 2 9 11 23 23 71 87 123 |
Двумерные массивы (211012_matrices.pas)
Даны квадратные матрицы A, B, C размерности n. Вычислить матрицу D. E - единичная матрица. Для решения задачи применить процедуры: сложения, вычитания и умножения матриц. Исходные и получаемые матрицы должны отображаться на форме.
На первой строке вводится целое положительное число n. На последующих 3n строках вводятся строки матриц A, B, C по n целых чисел в строке, разделённых пробелами.
Вывести результирующую матрицу D = A * A - B * C + E.
| Входные данные | Результат работы |
|
3 1 2 3 -2 0 7 -8 -7 -6 8 17 22 -1 1 17 2 0 0 9 6 3 -1 -2 -3 4 2 0 |
-169 -77 26 -116 -78 -42 36 14 -42 |
Поиск в сломанном массиве (binarysearch_shifted_array.py)
Произошла ошибка при копировании из одной структуры данных в другую. Массив чисел хранился в кольцевом буфере и был отсортирован по возрастанию, в нём можно было найти элемент за логарифмическое время. Данные были скопированы из кольцевого буфера в обычный массив, в результате они стали циклически сдвинуты. Нужно обеспечить возможность находить элемент за логарифмическое время.
В первой строке вводится размер массива n. Во второй - искомое число. На третьей строке идут n целых чисел через пробел. Длина массива не превосходит 10000. Элементы массива и число k не превосходят по значению 10000.
Вернуть индекс элемента, равного k, если такой есть в массиве (нумерация с нуля). Если элемент не найден, вернуть -1. Изменять массив нельзя.
| Входные данные | Результат работы |
|
9 5 19 21 100 101 1 4 5 7 12 |
6 |
|
2 1 5 1 |
1 |
Матричные манипуляции (MatrixManipulation.cpp)
Реализовать программу для работы с квадратной матрицей. Программа должна содержать:
- Структуру, описывающую матрицу.
- Функцию для заполнения квадратной матрицы размерностью nn возрастающей последовательностью от 1 до nn целых чисел по заданной схеме.
На примере n=4:
4 3 2 1
5 10 11 12
6 9 14 13
7 8 15 16
n=5:
5 4 3 2 1
6 13 14 15 16
7 12 19 18 17
8 11 20 23 24
9 10 21 22 25
- Функцию для заполнения квадратной матрицы размерностью n*n целых чисел.
- Функция вывода матрицы в файл (в виде матрицы).
- Функция нахождения обратной матрицы.
- Функция умножения матриц.
Парсер арифметических операций (arithmetic_operations_parser.c)
Мир наш исполнен войны - целая вечность сражений во имя Императора. Он никогда не прекращает и не отступается от бесконечной вражды, а значит - не должны и мы.
Второй год Похода Мучений. В отдалённой системе войска Императора столкнулись с планетой полной ужасающих человекоподобных зверей, представляющих собой серьёзную угрозу. После ожесточённых боёв связь с ударным отрядом чёрных тамплиеров во главе с братом Герхартом была потеряна, в связи с чем было приятно единственно верное решение в таких ситуациях - ЭКСТЕРМИНАТУС, то есть полное уничтожение всего живого на поверхности. Для запуска орбитальной бомбардировки требуются специальные коды запуска. Обычно они приходят на отдельный канал и с ними не возникает никаких проблем, но в этот раз в связи с оплошностью подчинённого несколько передач принимались по одному каналу и результаты перемешались. Ваша задача состоит в том, чтобы извлечь из полученной информации коды запуска орудий.
Передача состоит из заглавных и строчных латинских букв, цифр, а также 4 основных арифметических действий '+', '-', '*', '/'. Её длина не превосходит 2000 символов. Известно, что кодом является некоторая команда вида A op B, где A и B - целые неотрицательные числа, а op - одно из арифметических действий, результат которой является корректно вычислимым выражением модуль которого не превосходит 120000. При этом выражение "A op B" является подстрокой исходного сообшения. Гарантируется, что числа A,B и результат операции над ними не переполняют 32-х битные целые знаковые числа.
Необходимо найти все такие команды и вывести их каждую с новой строки в виде A op B = res, где res - результат вычисления. Всё остальное считается мусором из других передач. Заметим, что для выражения A op1 B op2 C нужно вывести:
A op1 B = res1
B op2 C = res2
| Входные данные | Результат работы |
| 100+200/9 |
100 + 200 = 300 200 / 9 = 22 |
| rDU+9519+28006-+45350-80003-7034/14870/50385i-25266-39120*8557 |
9519 + 28006 = 37525 45350 - 80003 = -34653 80003 - 7034 = 72969 7034 / 14870 = 0 14870 / 50385 = 0 25266 - 39120 = -13854 |
Работа со списком (list_manipulation.c)
Во входном файле input.txt записаны две строки, каждая из которых содержит последовательность из не более чем 10000 целых чисел. Обе последовательности заканчиваются числом -1 (и оно не входит в последовательность), остальные числа неотрицательны и не превосходят 10^9.
Указание: при решении данной задачи запрещается использовать массивы. Для хранения последовательности чисел используйте однонаправленный или двунаправленный список.
Требуется в файл output.txt вывести без изменения порядка все члены второй последовательности, кроме тех которые встречаются в первой последовательности.
| Входные данные | Результат работы |
|
1 8 4 12 -1 2 4 1 3 5 8 -1 |
2 3 5 |
|
3 5 4 2 0 -1 5 3 2 1 0 4 3 -1 |
1 |
Вставка в двоичное дерево поиска (search_tree_insertion.c)
Структура struct tree (int x; struct tree *left, *right, *parent;); описывает двоичное дерево поиска. Напишите функцию void ins (struct tree *t, int x), вставляющую в дерево поиска t, заведомо содержащее ключ x, элемент с ключом, на единицу меньшим следующего по размеру за x ключа в дереве, либо с ключом x+1, если x - максимальный элемент дерева. Гарантируется, что ключ, который нужно вставлять, не содержится в дереве.
Dual linked list (dualLinkedListTemplate.cpp)
Develop a template of a container class, that represents an abstract data type of dual linked list. This class should contain random access iterator and have the following interface:
| Name | Description |
|---|---|
| constructor | |
| destructor | |
| operator= | |
| Iterators: | |
| begin | return iterator to beginning |
| end | return iterator to end |
| rbegin | return reverse iterator to reverse beginning |
| rend | return reverse iterator to reverse end |
| Capacity: | |
| empty | test whether container is empty |
| size | return size |
| Element access: | |
| front | access first element |
| back | access last element |
| Modifiers: | |
| assign | assign new content to container |
| push_front | insert element at beginning |
| pop_front | delete first element |
| push_back | add element at the end |
| pop_back | delete last element |
| insert | insert element x at index idx |
| erase | erase element |
| swap | swap content |
| resize | change size |
| clear | clear |
| Operations: | |
| reverse | reverse the order of elements |
It is forbidden to use std::iterator. Demonstrate work of the implemented methods in the main function.
Горнолыжный курорт (hills.cpp)
Сеть пунктов проката горнолыжного оборудования представляет собой корневое дерево, состоящее из n вершин, пронумерованных от 1 до n с корнем в вершине номер 1. В каждой вершине имеется пункт проката. Пункт, расположенный в i-й вершине, закупает оборудование по цене c_i рублей за комплект.
Пусть a_i - суммарное количество комплектов горнолыжного оборудования, которое будет закуплено во всех пунктах проката, находящихся в поддереве вершины номер i. Согласно маркетинговым исследованиям для каждого i эта величина должна находиться в диапазоне: l_i <= a_i <= r_i.
Необходимо определить, какое количество комплектов нужно закупить к началу сезона каждому из пунктов проката, чтобы для поддерева любой вершины сети общее количество комплектов находилось в указанном маркетологами диапазоне, а суммарная стоимость всех купленных комплектов была как можно меньше. Либо определить, что выполнить все условия маркетологов невозможно.
Напомним, что граф называется деревом, если он связный и не содержит циклов. Между любыми двумя вершинами в дереве существует ровно один простой путь. Корневым деревом называется дерево, в котором есть одна выделенная вершина - корень. Поддеревом вершины v называют множество всех вершин, для которых вершина v лежит на пути от соответствующей вершины до корня. Обратите внимание, что сама вершина v тоже входит в это множество. Родителем вершины v называется такая вершина p_v, что v и pv соединены ребром, и pv лежит на пути от v до корня.
Каждый тест состоит из нескольких наборов входных данных. В первой строке дано одно целое число t - количество наборов входных данных. Далее следует описание наборов входных данных.
В первой строке каждого набора входных данных дано одно целое число n (1 <= n <= 100000) - количество вершин в дереве.
Во второй строке даны n - 1 целых чисел p2, p3, ..., pn (1<= pi < i), обозначающих, что родителем вершины i является вершина pi.
В следующей строке даны n целых чисел c1, ..., cn (1 <= ci <= 10^9), где ci - цена закупки одного комплекта оборудования пунктом проката номер i.
В следующих n строках даны по два целых числа li и ri (0 <= li <= ri <= 10^9) - ограничения на общее количество комплектов горнолыжного оборудования в пунктах проката, находящихся в поддереве вершины номер i, к началу сезона.
Гарантируется, что сумма n по всем наборам входных данных не превышает 100000.
Для каждого набора данных выведите ответ в следующем формате.
Если невозможно выполнить все условия маркетологов, в единственной строке выведите -1.
Иначе, в первой строке выведите минимальное количество рублей, которое необходимо потратить на закупку горнолыжного оборудования всем пунктам сети суммарно. Во второй строке выведите n целых чисел bi, где bi равно количеству комплектов, которое необходимо закупить пункту проката номер i. Если существует несколько способов выполнить все условия маркетологов, потратив минимальное возможное количество рублей, вы можете вывести любой из них.
| Входные данные | Результат работы |
|
2 3 1 1 3 1 2 5 7 1 2 2 4 2 1 5 5 0 1 2 2 |
8 0 2 3 -1 |
|
1 10 1 2 1 1 4 2 1 2 5 229935705 252294888 574618756 226876866 225916692 249797075 133791770 102539705 760471176 956697279 125 237 48 102 13 27 20 42 29 58 11 22 21 41 13 26 7 15 20 40 |
45429982917 0 0 13 9 9 11 30 26 7 20 |
Сумма и определитель матрицы (matrixsum.java)
Реализовать консольное приложение, которое имеет примитивный текстовый интерфейс и меню, состоящее как минимум из четырех пунктов:
- Ввод исходных данных, как вручную, так и сгенерированных случайным образом
- Выполнение алгоритма по заданию
- Вывод результата
- Завершение работы программы
В работе можно использовать только массивы! Результат не может быть выведен без обработки введённых данных. Вывод результата не может быть осуществлен без выполнения алгоритма. При вводе новых данных результаты выполнения алгоритма "сбрасываются". Варианты заданий, где указан массив слов подразумевают, что разделителями для слов являются пробельные символы и знаки препинания.
Две квадратные матрицы одинакового размера, значение которого также вводит пользователь.
Сумма матриц и значение ее определителя.
Количество выходных в году (weekdays_a_year.c)
В некоторой стране действует Григорианский календарь. В добавление к выходным дням субботы и воскресенья выходными объявляются 1, 2, 4, 8, 16, 32, 64, 128 и 256 день в году (1 января считается днем 1). Если такой день уже приходится на выходной, он не переносится, то есть дополнительный выходной “сгорает”.
Целое число - год (от 1902 до 2037).
Целое число - количество выходных дней в этом году.
В десятичную систему счисления (anytodecimal.c)
В аргументах командной строки задаются 64-битные беззнаковые числа в 17-ричной системе счисления. На стандартный поток вывода напечатайте эти числа в десятичной системе счисления, упорядоченные по невозрастанию.
Пример запуска программы: ./solution 1 2 3
Результат работы программы:
3
2
1
Бинаризуй (BinarizeMe.cpp)
Дана строка. Требуется заменить все целые положительные числа в ней на двоичные аналоги (перевести из десятичной в двоичную систему счисления).
На вход подается строка из не более 255 символов, среди которых могут быть и пробельные. Гарантируется, что числа в строке не начинаются с 0.
Строка - результат преобразования.
| Входные данные | Результат работы |
| 192873a kjhfd129380 | 101111000101101001a kjhfd11111100101100100 |
| 6a8g923mx | 110a1000g1110011011mx |
Электронные часы (digitalwatch.cpp)
У вас есть сломанные электронные часы, у которых некоторые пиксели перестали работать или наоборот - работают всегда. Требуется по ним определить и вывести текущее время или вывести ошибку в случае, если этого сделать нельзя.
На вход подаются 6 строк по 20 символов. Каждый прямоугольник 6х5 задает цифру циферблата.
Выведите время в формате hh:mm. Если на изображении присутствуют лишние пиксели или неверный формат времени (больше 23:59), выведите ERROR. Если время нельзя определить однозначно, выведите AMBIGUITY.
| Входные данные | Результат работы |
|
..##..####.####..##. .#..#....#.#....#..# ....#...#..###..#..# ...#.....#....#..### ..#......#.#..#....# .####.###...##..###. |
23:59 |
|
....#.#..#.####..### ...##.#..#.#....#... ..#.#.#..#.###..###. ....#.####....#.#..# ....#....#.#..#.#..# ....#....#..##...##. |
14:56 |
|
..##..####.#..#..##. .#..#....#.#..#.#..# .#..#...#..#..#..##. .#..#..#...####.#..# .#..#..#......#.#..# ..##...#......#..##. |
07:48 |
|
....#..##..###...##. ...##.#..#....#.#..# ..#......#...#...... ........#.....#....# ....#..#......#....# ......####.#.....##. |
AMBIGUITY |
|
....#..##..###...##. ...##.#..#....#.#..# ..#......#...#....#. ........#.....#....# ....#..#......#....# .................##. |
12:38 |
|
#................... .................... .................... .................... .................... .................... |
ERROR |
|
...........#........ .................... ..#.....#.........#. ...........#........ .................#.. ......#............. |
13:47 |
Стабильная сортировка (stable_quicksort.cpp)
Требуется реализовать стабильную сортировку для следующей задачи. Выведите фамилии и имена абитуриентов, подавших документы на поступление в ВУЗ в порядке убывания их среднего балла по ЕГЭ.
Про каждого ученика известны их фамилии, имена и баллы ЕГЭ по следующим предметам: информатика, математика и русский язык.
В первой строке идет число N (1<=N<=10^5) - количество абитуриентов, подавших документы. Далее идет N строк - описания ученика в формате "surname name inf_points math_points rus_points", где "surname" - строки длины не более 40, "*_points" - баллы за экзамены (целые числа от нуля до ста включительно).
Необходимо вывести пары фамилия - имя по одной на строке, разделяя фамилию и имя одним пробелом. Выводить баллы не нужно. Если несколько учащихся имеют одинаковые средние баллы, то их нужно выводить в порядке, заданном во входных данных.
| Входные данные | Результат работы |
|
2 Markov Alexander 100 99 98 Ivanov Ivan 99 98 98 |
Markov Alexander Ivanov Ivan |
|
3 Markov Alexander 75 90 90 Sergey Petrov 100 50 100 Petrov Petr 99 94 71 |
Petrov Petr Markov Alexander Sergey Petrov |
|
6 A A 90 90 90 B B 90 90 90 C C 90 90 90 D D 90 90 90 E E 90 90 90 F F 90 90 90 |
A A B B C C D D E E F F |
Гипершашки (hypershashki.cpp)
Андрей работает судьей на чемпионате по гипершашкам. В каждой игре в гепершашки участвует три игрока. По ходу игры каждый из игроков набирает некоторое положительное целое число баллов. Если после окончания игры первый игрок набрал a баллов, второй - b, третий c, то говорят, что игра закончилась со счетом a : b : c. Андрей знает, что правила игры гипершашек устроены таким образом, что в результате игры баллы любых двух игроков различаются не более чем в k раз. После матча Андрей показывает его результат, размещая три карточки с очками игроков на специальном табло. Для этого у него есть набор из n карточек, на которых написаны числа x1, x2, ..., xn. Чтобы выяснить, насколько он готов к чемпионату, Андрей хочет понять, сколько различных вариантов счета он сможет показать на табло, используя имеющиеся карточки. Требуется написать программу, которая по числу k и значениям чисел на карточках, которые имеются у Андрея, определяет количество различных вариантов счета, которые Андрей может показать на табло.
Первая строка содержит два целых числа: n и k (3 <= n <= 100000, 1 <= k <= 10^9). Вторая строка содержит n целых чисел x1, x2, ..., xn (1 <= xi <= 10^9).
Одно целое число - искомое количество различных вариантов счета.
| Входные данные | Результат работы |
|
3 1 1 1 1 |
1 |
|
6 6 1 1 1 2 2 21 |
8 |
|
6 3 1 2 3 4 5 6 |
66 |
|
3 1 1 2 3 |
0 |
|
5 2 2 2 3 4 5 |
18 |
Карточная игра (cardgame.cpp)
В игре в зожника карточная колода раздается поровну двум игрокам. Далее они вскрывают по одной верхней карте, и тот, чья карта старше, забирает себе обе вскрытые карты, которые кладутся под низ его колоды. Тот, кто остается без карт - проигрывает. Для простоты будем считать, что все карты различны по номиналу, а также, что самая младшая карта побеждает самую старшую карту ("шестерка берет туза"). Игрок, который забирает себе карты, сначала кладет под низ своей колоды карту первого игрока, затем карту второго игрока (то есть карта второго игрока оказывается внизу колоды).
Напишите программу, которая моделирует игру в зожника и определяет, кто выигрывает. В игре участвует 10 карт, имеющих значения от 0 до 9, большая карта побеждает меньшую, карта со значением 0 побеждает карту 9.
Две строки: первая строка содержит 5 чисел, разделенных пробелами - номера карт первого игрока, вторая строка - номера карт второго игрока. Карты перечислены сверху вниз, то есть каждая строка начинается с той карты, которая будет открыта первой.
Программа должна определить, кто выигрывает при данной раздаче, и вывести слово "first" или "second", после чего вывести количество ходов, сделанных до выигрыша. Если на протяжении 10^6 ходов игра не заканчивается, программа должна вывести слово "botva".
| Входные данные | Результат работы |
|
1 3 5 7 9 2 4 6 8 0 |
second 5 |
|
7 8 3 0 4 6 2 9 1 5 |
botva |
|
9 8 7 1 2 0 3 4 5 6 |
second 15 |
Задачи на графы (TasksOnGraphs.ipynb)
22 небольшие задачи на ориентированные и неориентированные графы, написанные на python. В том числе задачи на подсчет числа компонент связности, определение транзитивности, полноты и регулярности графов.
Процессы: текущее время (fork_currentdate.c)
Родитель создает сына, тот — внука, а тот — правнука. Правнук передает в канал текущее время, полученное с помощью системного вызова time, в бинарном виде (тип time_t).
Отец, сын и внук считывают время из канала. Процесс-отец выводит на экран строку "Y:????", где ???? заменяются на текущий год, сын — "M:??", где ?? заменяются на текущий месяц в году (от 1 до 12), число всегда выводится с двумя знаками, внук — "D:??", где ?? заменяются на номер дня в месяце, всегда выводящееся с двумя знаками.
Внук должен вывести число первым, сын — вторым, а отец — третьим. Записывать в канал разрешается только правнуку.
Пример вывода:
D:11
M:09
Y:2001
Процессы: сумма чисел (fork_printsum.c)
Процесс-родитель создает процесса-сына, а тот в свою очеред процесса-внука. Процесс-родитель и процесс-внук должны быть соединены анонимным каналом в направлении от родителя к внуку. Процесс-родитель считывает 32-битные знаковые целые числа, подаваемые на стандартном потоке ввода в текстовом виде. Последовательность заканчивается признаком конца файла. Процесс-родитель передает считанные числа в канал в бинарном виде. Процесс-внук считывает числа из канала и вычисляет их сумму. После чтения всех чисел процесс-внук выводит на стандартный поток вывода их сумму и завершает работу. Процесс-родитель должен дождаться завершения всех порожденных им процессов и завершиться сам с кодом завершения 0.
Input 1 2 3 4 5 6 7 8 9 10 Output 55
Максимальная куча на бинарном дереве (maxheap.cpp)
Требуется реализовать приоритетную очередь с помощью бинарной пирамиды, поддерживающую три операции: добавить элемент, извлечь максимальный элемент и удалить заданный элемент. При просеивании нельзя совершать лишние перемещения (например, в случае равенства элементов). Если при просеивании вниз, рассматриваемый элемент можно перемещать как влево вниз, так и вправо вниз, то следует выбрать лево.
В первой строке вводятся два числа - максимальный размер приоритетной очереди N и количество запросов M, (1 <= M,N <= 10^5). Далее идут M строк, в каждой строке - по одному запросу. Первое число в запросе задает его тип, остальные числа (если есть) - параметры запроса. Тип 1 - извлечь максимальный (без параметров). Тип 2 - добавить данный элемент в очередь. Запрос имеет один параметр - число из отрезка [-10^9;10^9]. Тип 3 - удалить элемент по индексу (индексы нумеруются с единицы).
В ответ на запрос типа 1 следует вывести: Если извлекать было нечего (очередь пуста), то -1. Иначе - два числа, первое - индекс конечного положения элемента после его просеивания (если удален последний элемент и просеивать нечего, то вывести 0), второе - значение извлеченного элемента. В ответ на запрос типа 2 следует вывести: Если добавить нельзя (нет места, т.к. в очереди уже N элементов), то -1. Иначе - индекс добавленного элемента. В ответ на запрос типа 3 следует вывести: Если элемента с таким индексом нет и удаление невозможно, то -1. Иначе - значение удаленного элемента. После выполнения всех запросов требуется вывести пирамиду в её конечном состоянии.
| Входные данные | Результат работы |
|
4 10 1 2 9 2 4 2 9 2 9 2 7 1 3 4 2 1 3 3 |
-1 1 2 3 2 -1 2 9 -1 4 9 9 4 1 |
|
5 5 2 4 2 5 1 1 1 |
1 1 1 5 0 4 -1 |
|
10 30 1 2 -1 1 1 2 0 1 2 0 2 9 2 -6 1 1 1 1 2 6 2 4 2 -1 2 -5 2 3 1 2 -5 1 1 2 7 1 2 -3 2 6 1 1 2 4 2 0 |
-1 1 0 -1 -1 1 0 0 1 1 3 2 9 1 0 0 -6 -1 1 2 3 4 5 2 6 5 2 4 3 3 1 2 7 2 1 2 6 2 -1 1 2 4 0 -5 -5 -3 |
Количество способов из 1 в N (countWays1toN.py)
Имеется калькулятор, который выполняет следующие операции:
- умножить число X на 2
- умножить число X на 3
- прибавить к числу X единицу
Определите, какое наименьшее количество операций требуется, чтобы получить из числа 1 число N.
Во входном файле написано натуральное число N, не превосходящее 10^6.
В первой строке выходного файла выведите минимальное количество операций. Во второй строке выведите числа, последовательно получающиеся при выполнении операций. Первое из них должно быть равно 1, а последнее N. Если решений несколько, выведите любое.
| Входные данные | Результат работы |
| 1 |
0 1 |
| 5 |
3 1 3 4 5 |
Движение по полосам (dorogi.py)
При организации движения по сложным перекресткам, для того, чтобы траектории водителей, выполняющих различные маневры, не пересекались, вводят ограничения на возможные маневры водителей, в зависимости от того, по какой полосе движения водитель подъехал к перекрестку. Для этого используется знак "движение по полосам". Рассмотрим дорогу, подходящую к перекрестку, на котором сходится m дорог. Водитель, подъезжающий к перекрестку по этой дороге, потенциально может продолжить свое движение в m различных направлениях - обратно по дороге, по которой он приехал, а также по одной из оставшихся m - 1 дорог. Пронумеруем возможные направления числами от 1 до m слева направо с точки зрения подъезжающего водителя. Номер 1 получит разворот и возврат по дороге, по которой водитель подъезжал к перекрестку, номер 2 - поворот на самую левую из дорог, и т.д.
Пусть дорога содержит n полос для движения. Пронумеруем полосы от 1 до n слева направо, самая левая полоса получит номер 1, следующая номер 2, и т.д. Знак "движение по полосам" разрешает каждой из полос движение по некоторым из m возможных направлений. При этом должны выполняться следующие условия:
- Если с i-й полосы разрешено движение в a-м направлении, а с j-й полосы разрешено в b-м направлении, причём i < j, то a <= b.
- С каждой полосы разрешено движение хотя бы в одном направлении.
- В каждом направлении разрешено движение хотя бы с одной полосы.
Инспекция по безопасности дорожного движения заинтересовалась, а сколько различных знаков "движение по полосам" можно установить перед таким перекрестком. Помогите им найти ответ на этот вопрос.
Два целых числа: m и n (2<=m<=50, 1<=n<=15). m - число дорог, n - число полос
В выходной файл выведите одно число - количество возможных знаков "движение по полосам", которые можно установить перед перекрестком.
| Входные данные | Результат работы |
| 4 2 | 7 |
| 5 2 | 9 |
| 4 3 | 25 |
| 50 15 | 108206580836328381 |
В первом примере возможны следующие варианты знаков "движение по полосам":
| С левой полосы | С правой полосы |
| разворот | разворот, налево, прямо, направо |
| разворот | налево, прямо, направо |
| разворот, налево | налево, прямо, направо |
| разворот, налево | прямо, направо |
| разворот, налево, прямо | прямо, направо |
| разворот, налево, прямо | направо |
| разворот, налево, прямо, направо | направо |
Каждому по компьютеру (pcforeverybody.py)
В каждом новом учебном году на занятия в компьютерные классы Дворца Творчества Юных пришли учащиеся, которые были разбиты на N групп. В i-й группе оказалось Xi человек. Тут же перед директором встала серьезная проблема: как распределить группы по аудиториям. Во дворце имеется M >= N аудиторий, в j-й аудитории имеется Yj компьютеров. Для занятий необходимо, чтобы у каждого учащегося был компьютер и еще один компьютер был у преподавателя. Переносить компьютеры из одной аудитории в другую запрещается. В одной аудитории одновременно может находиться только одна группа. Напишите программу, которая найдет, какое максимальное количество групп удастся одновременно распределить по аудиториям, чтобы всем учащимся в каждой группе хватило компьютеров, и при этом остался бы ещё хотя бы один для учителя.
На первой строке входного файла расположены числа N и M (1<=N<=M<=1000). На второй строке расположено N чисел - X1, X2, …, XN (1<=Xi<=1000). На третьей строке расположено M чисел Y1, …, YM (1<=Yi<=1000).
Выведите на первой строке число P - количество групп, которые удастся распределить по аудиториям. На второй строке выведите распределение групп по аудиториям - N чисел, i-е число должно соответствовать номеру аудитории, в которой должна заниматься i-я группа. (Нумерация как групп, так и аудиторий, начинается с 1). Если i-я группа осталась без аудитории, i-е число должно быть равно 0. Если допустимых распределений несколько, выведите любое из них.
| Входные данные | Результат работы |
|
1 1 1 2 |
1 1 |
|
1 1 1 1 |
0 0 |
|
3 4 5 3 4 3 5 3 6 |
2 0 2 4 |
|
3 3 1 2 3 3 4 2 |
3 3 1 2 |
Турнир (tournament.py)
В турнире по хоккею участвовало K команд, каждая сыграла с каждой по одному матчу. За победу команда получала 2 очка, за ничью - 1, за поражение - 0 очков. Известно, сколько очков в итоге получила каждая команда, однако результаты конкретных матчей были утеряны. Требуется восстановить одну из возможных турнирных таблиц.
В первой строке входных данных содержится одно натуральное число K, не превосходящее 100 - количество команд. Во второй строке задаются через пробел K целых неотрицательных чисел, не превосходящих 2(K-1), количество очков, набранных командами, занявшими первое, второе, ..., K-е места соответственно (то есть каждое следующее число не больше предыдущего).
Выведите турнирную таблицу в следующем формате. Таблица должна состоять из K строк с результатами игр команд, занявших первое, второе, ..., последнее место (команды, набравшие одинаковое число очков, могут быть расположены в таблице в любом порядке). В каждой строке должно быть записано K чисел через пробел - количество очков, набранных в игре данной команды с первой, второй, ..., командами соответственно. Количество очков - это число 0, 1 или 2. В клетках на главной диагонали (соответствующих не существующей игре команды "самой с собой") нужно записать нули. Гарантируется, что входные данные соответствуют реальному турниру, то есть хотя бы одна таблица, соответствующая входным данным, может быть построена. Если таких таблиц несколько, выведите любую из них.
| Входные данные | Результат работы |
|
4 6 4 2 0 |
0 2 2 2 0 0 2 2 0 0 0 2 0 0 0 0 |
|
4 3 3 3 3 |
0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0 |
|
4 4 3 3 2 |
0 1 1 2 1 0 1 1 1 1 0 1 0 1 1 0 |
|
5 6 5 5 2 2 |
0 1 1 2 2 1 0 1 1 2 1 1 0 2 1 0 1 0 0 1 0 0 1 1 0 |
Транспортировка (transfer.cpp)
К очередной Летней компьютерной школе было решено подготовить кружки как для школьников, так и для всех преподавателей.
Имея привычку делать важные дела в самый последний момент, дизайнер закончил работу над макетом за два дня до начала школы. Ещё день уйдёт у завода-изготовителя на то, чтобы изготовить кружки и нанести на них изображение. На то, чтобы довезти кружки от завода-изготовителя до ЛКШ, остаётся всего 24 часа.
Заказ на 10000000 экземпляров кружек (а именно столько заказали организаторы), конечно же, за один рейс не увезти. Однако, за первый рейс хочется привезти максимальное количество кружек. Для перевозки был заказан один большегрузный автомобиль. Но есть один нюанс: на некоторых дорогах установлено ограничение на вес автомобиля. Поэтому если автомобиль нагрузить кружками под завязку, то, возможно, не удастся воспользоваться самым коротким маршрутом, а придётся ехать в объезд. Может случиться даже так, что из-за этого грузовик не успеет доехать до лагеря вовремя, а этого допустить никак нельзя. Итак, сколько же кружек можно погрузить в автомобиль, чтобы успеть привезти этот ценный груз вовремя, и не нарушая правил дорожного движения
В первой строке находятся числа n (1≤n≤500) и m - количество узловых пунктов дорожной схемы и количество дорог, соответственно. В следующих m строках находится информация о дорогах. Каждая дорога описывается в отдельной строке следующим образом. Сначала указаны номера узловых пунктов, которые соединяются данной дорогой, потом время, которое тратится на проезд по этой дороге, и, наконец, максимальный вес автомобиля, которому разрешено ехать по этой дороге. Известно, что все дороги соединяют различные пункты, причем для каждой пары пунктов есть не более одной дороги, непосредственно их соединяющей. Все числа разделены одним или несколькими пробелами.
Узловые пункты нумеруются числами от 1 до n. При этом завод по производству кружек имеет номер 1, а ЛКШ - номер n. Время проезда по дороге задано в минутах и не превосходит 1440 (24 часа). Ограничение на массу задано в граммах и не превосходит одного миллиарда. Кроме того, известно, что одна кружка весит 100 грамм, а пустой грузовик - 3 тонны.
Выведите одно число - максимальное количество кружек, которое можно привезти за первый рейс, потратив не более 24часов.
| Входные данные | Результат работы |
|
3 3 1 2 10 3000220 2 3 20 3000201 1 3 1 3000099 |
2 |
Нормализация UNIX пути (unixpath.cpp)
В этой задаче нужно написать функцию, которая приводит к нормализованному виду строку, представляющую собой путь к файлу или директории в UNIX-подобной операционной системе.
Нормализация пути заключается в приведении к абсолютному пути и избавлении от следующих элементов:
/в конце пути.- текущая директория..- родительская директория//- равносильно/
На вход подается текущая директория current_working_dir (абсолютный путь, т.е. начинающийся с /) и путь path, который может быть как абсолютным, так и относительным.
Надо вернуть нормализованный абсолютный путь, которому соответсвует path.
| Входные данные | Результат работы |
| NormalizePath("/", ".") | / |
| NormalizePath("/home/user1", "../user2") | /home/user2 |
| NormalizePath("/", "..") | / |
| NormalizePath("/home", "../../tmp") | /tmp |
| NormalizePath("/", "../../a/") | /a |
| NormalizePath("/", ".././/././/./../b/././././././") | /b |
Сапёр (minesweeper.cpp)
Реализуйте класс Minesweeper для игры "Сапёр".
- принимающий размеры поля и количество мин - расставляет мины на поле случайным образом
- принимающий размеры поля и список клеток - расставляет мины на указанных клетках
NewGame- инициализирует новую игру; имеет два варианта, аналогичных конструкторамOpenCell- аналог клика левой кнопкой мыши- если игра выиграна или проиграна, ничего не делает
- если клетка с флажком, ничего не делает
- если клетка без флажка, открывает клетку; алгоритм отрытия клеток описан ниже
MarkCell- аналог клика правой кнопкой мыши- если игра выиграна или проиграна, ничего не делает
- пустую клетку отмечает флажком
- с клетки с флажком снимает флажок
GetGameStatus- возвращает статус игрыRenderField- возвращает список строк, соответствующий отрисованному полю. Соответствие элементов символам:- закрытая клетка -
- - клетка с миной -
* - клетка с флагом -
? - открытая клетка без мин - число от
1до8(соответствует количеству мин в соседних клетках), вместо 0 рисуется.
- закрытая клетка -
- Если клетка содержит мину
- открываются все клетки
- игра заканчивается проигрышем
- Если клетка не содержит мину, но мина есть в соседней клетке, то открывается только эта клетка
- Если клетка и её соседи не содержат мин
- текущая клетка открывается
- алгоритм открытия клетки применяется ко всем соседям текущей клетки без флажка
Игра считается выигранной, когда открыты все клетки кроме тех, на которых стоят мины.
Внутреннее представление игры не должно быть завязано на отображение.
Преобразуйте внутреннее представление в строки только в методе RenderField.
Наивный алгоритм случайной расстановки мин может быть неэффективен при количестве мин, близком к общему количеству клеток. Поле может быть очень большим. Не используйте рекурсивный вызов функций/методов для открытия клеток.
Тесты для данной задачи находятся в функции main файла minesweeper.cpp.
К-я строка (kthstring.cpp)
Реализуйте структуру данных, которая поддерживает следующие операции:
- добавить в словарь строку S;
- найти в словаре k-ю строку в лексикографическом порядке. Изначально словарь пуст.
Формат входных данных
Первая строка входного файла содержит число N — количество команд (
- 1 S — добавить строку S в словарь;
- 2 k — вывести k-ю строку в лексикографическом порядке.
Гарантируется, что при запросе
k-й строки она существует. Также гарантируется, что сумма длин всех добавляемых строк не превышает
$3*10^5$ . Все строки состоят из строчных латинских букв.
Формат результата
Для каждого запроса второго типа выведите k-ю в лексикографическом порядке строчку из словаря на момент запроса. Гарантируется, что суммарная длина строк в выходном файле не превышает
Примеры
| Входные данные | Результат работы |
|
7 1 pushkin 1 lermontov 1 tolstoy 1 gogol 1 gorkiy 2 5 2 1 |
tolstoy gogol |
Повторы подстрок в кольцевом списке (circulardups.c)
Вам дан тип узла двунаправленного закольцованного списка, который хранит Си-строку. Каждый элемент списка содержит адрес своей отдельной области памят под Си-строку. struct list_item { char *str; struct list_item *prev, *next; } Напишите функцию void process(struct list_item **list, const char *s);
Она получает на вход указатель на начало двунаправленного закольцованного списка list и Си-строку s. Функция находит элементы списка, чья строка содержит строку s в качестве подстроки, и полностью дублирует этот элемент столько раз, какова длина этой строки. Остальные элементы надо переставить в конец списка с сохранением порядка. Функция должна один раз пройти по списку и не использовать функцию освобождения памяти.
Пример: если функция получит список ["a", "xabc", "ab"] и строку "abc", то список должен стать ["xabc", "xabc", "xabc", "xabc", "xabc", "a", "ab"].
| Входные данные | Результат работы |
|
a xabc ab abc |
xabc xabc xabc xabc xabc a ab |
Последовательное выполнение команд с обработкой ошибок (concurrent_error.c)
Программа получает на стандартный ввод последовательность строк, каждая строка - это последовательность команд, разделенных точкой с запятой. За последней строкой может не идти перенос строки. Нужно выполнить последовательно все эти команды. Внутри команды точка с запятой не встречается. Команда состоит из последовательности слов - имени программы и ее аргументов. "Пустых" команд не может быть (т.е. в строке не может быть в конце и в начале точки запятой и двух точек с запятой подряд). Программу запускать с использованием переменной PATH. Код завершения программы равен коду завершения последней запущенной команды, если она завершилась системным вызовом _exit, а иначе 128 + номер сигнала. Если функция exec завершилась ошибкой, процесс завершается с кодом 127. В случае других ошибок - код завершения 1. Использовать bash напрямую или косвенно запрещается. Все аргументы разделены не менее чем одним пробельным символом. Длина строки ограничена лишь размерами памяти.
| Входные данные | Результат работы |
|
echo 1 ; echo 2 echo 3 4a |
1 2 3 4a |
Выполнение команд сигналами и таймером (sigalarm_commands.c)
Аргументы командной строки вашей программы такие: p1 arg11 arg12 ... arg1N -- p2 arg21 arg22 ... arg2M. Отец создает дочерний процесс и соединяется с ним ровно одним каналом. Отец читает последовательность неотрицательных целых чисел со стандартного ввода. Если он читает 0, то отправляет сыну сигнал (выберите сами, какой), а если больше 0, он спит указанное количество микросекунд (функция usleep). Сын на каждый третий приход сигнала выполняет команду p1 arg11 arg12 ... arg1N | p2 arg21 arg22 ... arg2M, используя PATH. Первый пришедший сигнал имеет номер 1, т.е. первый раз сын должен запустить команду, получив сигнал в третий раз. Команды не должны пересекаться по времени. То есть их надо выполнять последовательно нужное количество раз. Активное ожидание недопустимо. Считать, что последовательность чисел не содержит двух нулей подряд и не оканчивается нулем. Отец завершает сына отправкой сигнала SIGTERM, сын должен довыполнить все требуемые команды и завершиться.
Параллельная запись и синхронизация процессов (concurrent_process_file.c)
Отец получает на стандартный ввод целые неотрицательные числа N и K. Отец создает временный файл и записывает туда число K. Затем он запускает параллельно N дочерних процессов. Дочерние процессы по очереди по кругу дописывают в конец файла число, на единицу меньшее, чем последнее число в файле. Как только они дошли до 0, дочерние процессы завершаются. Отец дожидается завершения дочерних процессов, распечатывает последовательно содержимое файла на стандартный вывод и удаляет файл. Глобальными переменными пользоваться нельзя. Синхронизацию процессов осуществить при помощи IPC. Число K детям иным образом, кроме как в файле, не передавать.
Рамка для рисунка (maximum_area.py)
У Алексея есть набор, который состоит из n палочек длины 1 и m палочек длины 2. Палочки можно соединять между собой, либо выстраивая их в линию, либо под прямым углом. Алексей хочет собрать из имеющихся палочек рамку прямоугольной формы, чтобы потом вставить в эту рамку лист бумаги и нарисовать красивый пейзаж для мамы на Новый год. При этом Алексей считает, что чем больше будет площадь прямоугольника, тем значимей будет его подарок. Поэтому ему важно определить максимальную площадь прямоугольника, границу которого можно собрать из имеющихся палочек.
Формат входных данных
Первая строка входных данных содержит целое число n — количество палочек длины 1,
Формат результата
В единственной строке выведите единственное целое число — максимальную площадь прямоугольника, который можно сложить из имеющихся палочек. Если из имеющихся палочек невозможно сложить никакой прямоугольник, то выведите число 0. Обратите внимание на то, что ответ в этой задаче может превышать возможное значение 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные целочисленные типы данных (тип long long в языке C++, тип int64 в Pascal, тип long в Java и C#).
Примеры
| Входные данные | Результат работы |
|
5 0 |
1 |
|
4 3 |
6 |
|
3 0 |
0 |
Замечание
В первом примере есть 5 палочек длины 1. Из них можно сложить квадрат со стороной 1, его площадь равна 1, при этом одна палочка останется. Во втором примере есть 4 палочки длины 1 и 3 палочки длины 2. Из них можно сложить прямоугольник размера 2 × 3. В третьем примере есть 3 палочки длины 1, из них невозможно сложить прямоугольник.
Strcat (pointers_d2.c)
Реализовать функцию my_strcat конкатенации двух строк (аналог функции strcat). Нельзя использовать операцию индексации (квадратные скобки) и ее эквивалентные выражения (т.е. требуется эффективная реализация). Эта функция не должна знать, как получены строки (все ненулевые символы считаются значимыми!).
Для тестирования этой функции напишите функцию main. Она считывает две строки (используйте функцию fgets). Длина каждой строки не превосходит 80 символов. Не забудьте заменить символ перевода строки на ноль! Затем вызывается целевая функция так, чтобы в конец первой строки добавилась вторая строка. В конце печатается строка-результат. Функция main завершается явным return 0.
| Входные данные | Результат работы |
|
abc def |
abcdef |
Проверка суффикса (pointers_d3.c)
Напишите функцию, которая получается два указателя - начало первой строки и начало второй строки - и возвращает единицу, если первая строка содержится в конце второй строки, и ноль в противном случае. Заголовок функции должен свидетельствовать, что функция не собирается менять содержимое обеих строк. Требуется эффективная реализация. Функция не должна знать, как созданы строки.
Напишите функцию main. Она считывает две строки (используйте функцию fgets). Длина каждой строки не превосходит 80 символов. Не забудьте "занулить" символ перевода строки в них! Затем вызывает целевую функцию и печатает строку YES, если результат истина, и NO иначе.
| Входные данные | Результат работы |
|
abc de |
NO |
|
abc defabc |
YES |
Обмен знаками (pointers_d4.c)
Требуется написать программу, которая считывает два массива вещественных чисел (сначала идет целое число - размер массива - затем нужное количество вещественных чисел). Размеры массивов не превосходят 10000 (но даже такие массивы не нужно размещать на стеке!). Затем она меняет местами первый отрицательный элемент первого массива и последний положительный элемент второго массива, если оба эти числа существуют. В конце печатаются подряд числа первого массива, затем числа второго массива. Печатать каждое вещественное число нужно при помощи спецификатора %.llf. Требуется эффективная реализация. Не используйте глобальные переменные.
| Входные данные | Результат работы |
|
2 -1.0 -2.0 2 1.0 2.0 |
2.0 -2.0 1.0 -1.0 |
Обмен знаками (pointers_d8.c)
Напишите функцию, которая получает на вход Си-строку и отыскивает в ней самое левое вхождение неотрицательного целого числа (непустой последовательности цифр). Функция возвращает успешность поиска, указатель на начало подстроки-числа и длину числа (подумайте, как составить заголовок этой функции!). Ведущих нулей в числе нет.
Для тестирования этой функции напишите функцию main. Она считывает одну строку (используйте функцию fgets). Длина строки не превосходит 80 символов. Затем при помощи написанной функции находит самое большое число и распечатывает его (подстрока с числом может быть очень длинная!).
| Входные данные | Результат работы |
| 123abc004 | 123 |
| 123abc124 | 124 |
| abc004 | 4 |
| abc00 | 0 |
| abc-32x | 32 |
| 1111111111111111111111111111c | 1111111111111111111111111111 |
Разворот (struct_heap_f3.c)
Напишите программу, которая читает последовательность целых чисел типа int до конца ввода (т.е. до первой ошибки в scanf). Записывает числа последовательно в динамически расширяющийся массив. Распечатывает последовательность в обратном порядке.
В динамически расширяющимся массиве количество операций реаллокации должно логарифмически зависеть от длины массива.
| Входные данные | Результат работы |
| -1 2 3 | 3 2 -1 |
Строковый switch (preproc_funcptrs_h3.c)
Реализуйте тип данных - строковый switch - отображение Си-строк в функции с одним формальным параметром - Си-строкой - и без возвращаемого значения. Оно указывает, какой код нужно выполнить для какой строки. Кроме этого, строковый switch должен иметь функцию с описанным выше заголовком для default-случая, т.е. если ни одна из строк не подошла. В имени типа данных не должно быть struct.
Напишите функцию выполнения строкового switch. Она получает его и Си-строку и выполняет соответствующий код. "Проваливания" нет. Указатель на функцию, равный NULL, означает пустой код.
Функция main для каждого аргумента командной строки (без имени программы) выполняет следующий строковый switch (используя функцию выше):
- на строку add печатается строка ADD
- на строку sub печатается строка SUB.
- Default-случай проверяет, является ли строка десятичной записью числа типа int (используя функцию strtol). В случае успеха печатает фразу NUMBER, иначе печатает строку UNKNOWN.
Эта задача без динамической памяти
Строковый switch 2 (preproc_funcptrs_h4.c)
Решите предыдущую задачу (preproc_funcptrs_h3.c) с другим строковым switch. В нем должно быть отображение для строк add и sub. default-случай ничего не делает. На каждое нечетное (1-е, 3-е, 5-е, ... - счет идет с единицы) вхождение add должен печататься номер вхождения (1, 3, 5, ...). После 2-го sub надо завершить программу.
Тип строкового switch и функция выполнения его не меняются по сравнению с предыдущей задачей. Глобальные переменные и динамическую память не использовать.
Файловая синхронизация (processes_j4.c)
Два процесса работают одновременно. Каждый получил свой номер (1 или 2); напечатал строку с переданным ему номером и завершился. Организовать процессы так, чтобы всегда сначала печаталось 2, а потом 1. Исходный код процессов одинаковый, поместите его в отдельную функцию, принимающую число - номер для печати.
Создать процессы как дочерние в вашей программе. Использовать лишь известные нам средства (процессы и файлы).
Если потребуется создать файл, его нужно создавать в текущей директории и обязательно удалить.
Везде здесь и далее! Требования к программам на программирование процессов по умолчанию:
- Обрабатывать ошибочные завершения системных вызовов не нужно;
- Процесс, запускаемый первым, должен завершиться последним;
- Процесс, запускаемый первым, должен завершиться с кодом 0;
- Все файлы, передаваемые в программу, успешно открываются;
- Все программы, которые надо запустить, успешно запускаются;
- При запуске программ необходимо использовать переменную окружения PATH;
- Активное ожидание недопустимо; переводите процессы в состояние сна до наступления некоторого события или на некоторое время (функция usleep).
Многозадачность: Отец и Сыновья (processes_j5.c)
Отец читает посимвольно стандартный ввод и для каждого символа, кроме первого, создает сына. Сын получает от отца текущий символ и, если он совпадает с первым символом, печатает текущий символ дважды, иначе ничего не печатает.
Сыновья должны работать параллельно. Размер ввода неограничен. Ввод непустой. Отец в конце печатает символ перевода строки, чтобы в итоге программа печатала ровно одну строку.
В начале программы отключите буферизацию ввода: setbuf(stdin, 0);
Изменение входного потока (input_change_k2.c)
Реализуйте команду шелла p < f, p (путь к программе) и f (путь к файлу) передаются в командной строке.
Функция main должна завершаться явным return.
Не использовать средства ввода-вывода стандартной библиотеки языки Си (stdio.h) для файлов. В качестве исключения можно использовать scanf и printf для чисел.
Изменение выходного потока (output_change_k3.c)
Реализуйте команду шелла p > f, p (путь к программе) и f (путь к файлу) передаются в командной строке.
Функция main должна завершаться явным return.
При реализации перенаправления вывода файл создавать с правами rw-rw-rw-.
Композитные команды (shell_composite_k4.c)
Реализуйте команду шелла (p1 || p2) >> f && p3; p1, p2 (пути к программам), f (путь к файлу) и p3 (путь к программе) передаются в командной строке.
Функция main должна завершаться явным return.
Не ошибитесь в том, у какого из процессов (одного!) надо перенаправить вывод (круглые скобки означают создание дочернего процесса, внутри которого выполняется то, что идет внутри скобок).
Удаление второй строки (remove2nd_k5.c)
В командной строке находится имя текстового файла. Удалить из файла вторую строку, если она существует.
Функция main должна завершиться явным return.
Минимизировать количество вызываемых системных вызовов, т.е. чтение и запись не должны быть побайтовыми.
Имя временного файла создавать при помощи функции mkstemp в рабочей директории. Временный файл не должен существовать после завершения программы. Проще всего этого добиться, удалив его имя сразу после получения файлового дескриптора на него! При этом сам файл будет удален после закрытия всех файловых дескрипторов на него.
Совет! Решение этой задачи может быть понятнее при правильном разделении задачи на подзадачи.
Обработка сигналов (signal_m2.c)
Процесс-сын пишет номер каждого пришедшего сигнала SIGINT (строка с номером, начиная с 1) и завершается по 5-му приходу сигнала SIGINT. Процесс-отец создает сына, отправляет ему 5 раз сигнал SIGINT с интервалом в 50 микросекунд и дожидается его завершения.
Здесь и везде далее! Написание программ с сигналами сильно усложняется, если сигналы поступают извне слишком часто. Поэтому в учебных целях мы будем предполагать, что сигналы не поступают слишком часто извне. Но это не означает, что одиночный сигнал не может поступить в произвольный момент времени.
Функция main должна завершаться явным return.
Обработка сигналов 2 (signal_m3.c)
Программа читает со стандартного ввода число типа unsigned long long. Программа отнимает от него по 1. Завершается, как только дойдёт до 0. Каждые 5 секунд печатает строку с текущим числом (в самом начале программы печатать не надо). По сигналу SIGINT печатает строку с количеством секунд до следующей печати числа.
Функция main должна завершаться явным return.
Анализатор кода (pipe_l3.c)
На стандартном вводе находится текст исходного модуля на языке Си, оформленный в соответствии со стилем кодирования. Распечатать список имен функций, определенных в этой программе, в лексикографическом порядке.
Для поиска строк файла использовать утилиту grep. Для выделения начала строки до открывающейся скобки - утилиту cut. Для сортировки - утилиту sort. Утилиты должны работать параллельно.
Вначале решите эту задачу в шелле, а потом реализуйте полученную команду в своей программе.
Раскраска в три цвета (graph3paint.cpp)
Петя нарисовал на бумаге n кружков и соединил некоторые пары кружков линиями. После этого он раскрасил каждый кружок в один из трех цветов - красный, синий или зеленый. Теперь Петя хочет изменить их раскраску. А именно - он хочет перекрасить каждый кружок в некоторый другой цвет так, чтобы никание два кружка одного цвета не были соединены линией. При этом он хочет обязательно перекрасить каждый кружок, а перекрашивать кружок в тот же цвет, в который он был раскрашен исходно, не разрешается.
Помогите Пете решить, в какие цвета следует перекрасить кружки, чтобы выполнялось указанное условие.
Формат входных данных
Первая строка содержит два целых числа n и m - количество кружков и количество линий, которые нарисовал Петя, соответственно (
Следующие m строк содержат по два целых числа - пары кружков, соединенных отрезками.
Формат результата
Выведите одну строку, состоящую из n символов из множества {'R', 'G', 'B'} - цвета кружков после перекраски. Если решений несколько, выведите любое. Если решения не существует, выведите слово "Impossible".
Примеры
| Входные данные | Результат работы |
|
4 5 RRRG 1 3 1 4 3 4 2 4 2 3 |
GGBR |
|
4 5 RGRR 1 3 1 4 3 4 2 4 2 3 |
Impossible |
Телефонные номера (phone_numbers.cpp)
И где здесь телефонные номера?
Дана строка s из строчных букв английского алфавита и число k. Найдите лексикографически минимальную строку t, имеющую длину k, множество букв которой является подмножеством множества букв s и s лексикографически меньше t.
Гарантируется, что ответ существует.
Обратите внимание, что под множеством букв строки подразумевается множество, а не мультимножество.
В частности, множество букв строки abadaba это
Строка p считается лексикографически меньше строки q, если p — префикс q, не равный q или существует i такое, что
Формат входных данных
В первой строке через пробел заданы два целых числа n и k
Во второй строке задана строка s, состоящая из n строчных букв английского алфавита.
Формат результата
Выведите строку t, удовлетворяющую условиям, описанным выше.
Гарантируется, что ответ существует.
Примеры
| Входные данные | Результат работы |
|
3 3 abc |
aca |
|
3 2 abc |
ac |
|
3 3 ayy |
yaa |
|
2 3 ba |
baa |
Примечание
В первом примере список строк t длины 3, подходящих под условие, что множество букв t — подмножество множества букв s, таков: aaa, aab, aac, aba, abb, abc, aca, acb, .... Из них лексикографически больше abc: aca, acb, .... Лексикографически минимальная из них — aca.
Точки на прямой (points_on_line.cpp)
Наши тесты не готовы. Впереди крупная олимпиада. Но ведь самая главная цель авторов контеста — сделать еще одну задачу.
Назовём диаметром мультимножества точек на прямой максимальное расстояние между двумя точками этого множества. Например, диаметр мультимножества
Диаметр мультимножества, состоящего из одной точки, равен 0.
Даны n точек на прямой. Какое минимальное число точек необходимо убрать, чтобы диаметр мультимножества оставшихся точек не превосходил d?
Формат входных данных
В первой строке заданы два целых числа n и d
Во второй строке через пробел заданы n целых чисел
Формат результата
Выведите одно целое число — минимальное количество удалённых точек.
Примеры
| Входные данные | Результат работы |
|
3 1 2 1 4 |
1 |
|
3 0 7 7 7 |
0 |
|
6 3 1 3 4 6 9 10 |
3 |
Примечание
В первом тестовом примере выгодно удалить точку с координатой 4. Оставшиеся точки будут иметь координаты 1 и 2, поэтому диаметр оставшегося мультимножества будет равен 2-1=1.
Во втором тестовом примере диаметр равен 0, поэтому удалять точки не потребуется.
В третьем тестовом примере выгодно удалить точки с координатами 1, 9 и 10. Оставшиеся точки будут иметь координаты 3, 4 и 6, поэтому диаметр будет равен 6-3=3.
Алена и обогреватель (alena_and_heater.cpp)
"Мы пробовали одиночное заключение, утопление и прослушивание группы Just In Beaver, но безрезультатно. Нам нужно что-то экстремальное."
"Маленькой Алене подарили массив на день рождения..."
Пусть есть массив a длиной n и два числа l и r (l≤r). Тогда массив b имеет размер n и получается следующим образом:
Для всех
-
$b_i = 0$ если$a_i, a_{i-1}, a_{i-2}, a_{i-3}, a_{i-4} > r$ и$b_{i-1} = b_{i-2} = b_{i-3} = b_{i-4} = 1$ -
$b_i = 1$ если$a_i, a_{i-1}, a_{i-2}, a_{i-3}, a_{i-4} < l$ и$b_{i-1} = b_{i-2} = b_{i-3} = b_{i-4} = 0$ -
$b_i = b_{i-1}$ иначе
Даны массивы
Гарантируется, что ответ существует.
Формат входных данных
В первой строке задано целое число
Во второй строке входных данных задаются n целых чисел
В третьей строке входных данных задается строка из n символов, состоящая из 0 и 1 — элементы массива
Формат результата
В единственной строке выведите два целых числа l и r
Если подходящих пар значений несколько, выведите любую из них.
Гарантируется, что ответ существует.
Примеры
| Входные данные | Результат работы |
|
5 1 2 3 4 5 00001 |
6 15 |
|
10 -10 -9 -8 -7 -6 6 7 8 9 10 0000111110 |
-5 5 |
Примечание
В первом тестовом примере подходит любая пара l и r, где