Портал обучения информатике. Подготовка к ЕГЭ, ОГЭ, олимпиадам

Cow Lineup#89804

Problem 2: Cow Lineup [Brian Dean]
Фермер Джон нанял профессионального фотографа, чтобы сфотографировать некоторых из своих коров. Поскольку у него есть коровы разных пород, он хочет иметь фото как минимум одной коровы каждой породы.
N коров ФД выстроены в ряд (позиция каждой указывается x-координатой) и целочисленным номером породы. ФД планирует сделать фотографию непрерывного участка коров. Стоимость фотографии равна ее размеру – то есть разностью между максимальной и минимальной x-координатами коров, представленных на фотографии.
Помогите ФД вычислить минимальную стоимость фотографии, в которой находится по крайней мере одна корова каждой породы.
PROBLEM NAME: lineup
Формат входных данных
* Строка 1: количество коров, N (1 <= N <= 50,000).
* Строки 2..1+N: Каждая строка содержит два числа, разделенных одиночным пробелом, указывающих x-координату и номер породы одной коровы. Оба числа не превосходят миллиард.
Формат выходных данных
* Строка 1: Минимальную стоимость фотографии, содержащей не менее одной коровы каждой породы.
Примечание
Диапазон от x=22 до x=26 (длиной 4) содержит коровы всех пород (1,3,7).

"Два указателя"

—Войти и решать

Cow Beauty Pageant (Silver Level)#89803

Problem 1: Cow Beauty Pageant (Silver Level) [Brian Dean]
Прослышав, что модно иметь коров с тремя пятнами, Фермер Джон купил целое стадо таких коров. К несчастью, мода меняется очень быстро, и сейчас в моде коровы с одним пятном.
ФД теперь хочет подкрасить своих коров так, чтобы они стали с одним пятном. Раскраска коровы задается двумерным массивом символов (N*M), например, так:
................ ..XXXX....XXX... ...XXXX....XX... .XXXX......XXX.. ........XXXXX... ..XXX....XXX....
Здесь 'X' обозначает часть пятна. Два символа 'X' принадлежат одному и тому же пятну, если они соседние вертикально или горизонтально (диагональные соседними не являются). Все коровы ФДЖ имеют ровно 3 пятна.
ФД хочет потратить как можно меньше краски, чтобы объединить три пятна в одно. На примере выше, он может сделать это, покрасив только 4 позиции, они обозначены символом ‘*’ на рис. ниже.
................ ..XXXX....XXX... ...XXXX*...XX... .XXXX..**..XXX.. ...*....XXXXX... ..XXX....XXX....
Помогите ФД определить минимальное количество клеток(символов), которые нужно закрасить, чтобы объединить три пятна в одно.
PROBLEM NAME: pageant
Формат входных данных
* Строка 1: Два разделенных пробелом целых числа, N и M (1 <= N,M <= 50).
* Строки 2..1+N: Каждая содержит строку из M символов 'X' и '.', указывающих соответствующую линию раскраски коровы.
Формат выходных данных
* Line 1: Минимальное количество сиволов 'X', которые нужно добавить ко введенным данным, чтобы получить единое пятно.
Примечание
4 символа ‘X’ нужно добавить, чтобы получить одно пятно.

Обход в ширину

—Войти и решать

Awkward Digits#89796

Problem 2: Awkward Digits [Brian Dean]
Бесси учиться конвертировать числа между системами счисления, с различными основаниями, но она делает ошибки, поскольку тяжело держать ручку между копытами.
Когда Бесси записывает результат конвертирования, она всегда записывает одну цифру с ошибкой. Например, если она конвертирует число 14 в двоичную систему, корректный результат будет 1110, но она может написать вместо него «0110» или «1111». Бесси никогда не добавляет и не удаляет цифры, но у нее может получится число с ведущим нулем в результате ее ошибки.
Вам дается ответ, записанный Бесси при конвертировании числа N К основаниям 2 и 3. Определите исходное значение числа N в десятичной системе счисления. Вы можете полагать, что N не превосходит 1 миллиард, и что всегда существует уникальное значение N.
PROBLEM NAME: digits
Формат входных данных
* Строка 1: представление числа N в двоичной системе счисления, одна цифра записана некорректно. (основание=2)
* Строка 2: представление числа N в троичной системе счисления, одна цифра записана некорректно (основание=3).
Формат выходных данных
* Строка 1: корректное значение числа N.
Примечание
Корректное значение числа 14 ("1110" в двоичной системе, "112" в троичной).

Системы счисления

✓ 10✗ 4—Войти и решать

Cow Photography#89793

Фермер Джон хочет сделать фотографию коров, которые стоят в ряд. А они все время перемещаются.
У ФД есть N (1 <= N <= 20,000) коров, каждая из которых имеет уникальный идентификатор - целое число. ФД хочет сфотографировать своих коров в особом порядке, который определяется содержимым массива A[1...N], где A[j] содержит ID j-ой коровы в правильном порядке.
ФД выстраивает своих коров, но прежде чем он успеет нажать кнопку "зафиксировать фотографию", группа коров (необязательно непрерывная) переходит на множество новых позиций (также необязательно непрерывных). ФД опять их выстраивает в желанном порядке, а часть коров снова перед самы нажатием меняет свои позиции. Так продолжается 5 раз.
Вам дается содержание каждой из этих 5 фотографий. Вы должны, если сможете, восстановить правильный порядок, заданныq массивом A.
Каждая фотография задает порядок, который в нескольких позициях отличается от правильного порядка. На каждой фотографии некоторые коровы перешли на другие позиции. Однако каждая корова перешла на новую позицию не более чем в одной фотографии. Более того, могут быть фотографии, на которых ни одна корова не меняла свою позицию.
PROBLEM NAME: photo
Формат входных данных
* Строка 1: Количество коров, N (1 <= N <= 20,000).
* Строки 2..5N+1: Следующие 5N строк описывают пять упорядочиваний, каждое одним блоком из N строк. Каждая строка содержит ID коровы целое число в диапазоне от 0 до 1,000,000,000.
Формат выходных данных
* Строки 1..N: Запланированный порядок A, по одному ID в строке.
Примечание
Запланированный порядок A[1..5]: 10, 20, 30, 40, 50.

Использование сортировки

—Войти и решать

Simplifying the Farm#89792

Фермер Джон изучает программирование на вечерних курсах при местном университете и сейчас проходит тему "минимальное остовное дерево". Он осознал, что проект его фермы не оптимален, и хочет его улучшить.
Ферма сейчас организована в виде графа, вершины которого представляют поля, а ребра представляют дорожки между этим полями, с каждой ассоциирована ее длина.
ФД заметил, что для каждой длины имеется не более трех дорожек, имеющих такую длину. ФД хочет удалить некоторые из дорожек на своей ферме так, чтобы получилось дерево - то есть, чтобы существовал единственный путь между любыми двумя полями. Более того, Фд хочет, чтобы это было минимальное остовное дерево, то есть дерево, которое имеет минимально возможную сумму длин всех дорожек.
Помогите ФД вычислить не только сумму длин всех дорожек в минимальном остовном дереве, но также количество различных возможных минимальных остовных деревьев, которые он может создать.
PROBLEM NAME: simplify
Формат входных данных
* Строка 1: Два целых числа N и M (1 <= N <= 40,000; 1 <= M <= 100,000), представляющих количество вершин и ребер соответственно. Вершины пронумерованы от 1 до N.
* Строки 2..M+1: Три целых числа a_i, b_i n_i (1 <= a_i, b_i <= N; 1 <= n_i <= 1,000,000) представляющих ребро от вершины a_i до b_i длиной n_i. Никакое ребро с длиной n_i не встретиться более трех раз.
Формат выходных данных
* Строка 1: Два целых числа, представляющих длину минимального остовного дерева и количество минимальных остовных деревьев (по модулю 1,000,000,007)
Примечание
Выбрав оба ребра с длиной 1 и любое ребро с длиной 2 мы получим минимальное остовное дерево с длиной 4.

Минимальный каркас

—Войти и решать

Grass Planting#89791

У Фермера Джона есть N пастбищ (2 <= N <= 100,000), соединенных N-1 двунаправленными дорогами так, что ровно один путь существует между любыми двумя пастбищами.
Бесси, любимая корова ФД пожаловалась, что на дорогах нет травы, и ФД решил посадить траву на дорогах.
Он делает это, используя процедуру, которая состоит из M шагов. (1 <= M <=100,000).
На каждом шаге происходит одна из двух вещей:
- ФД выбирает два пастбища и высаживает траву на каждой дороге пути между ними - Бесси спрашивает, сколько дорог засажено травой на конкретном пути, и ФД должен ей ответить.
Помогите ФД отвечать на вопросы.
PROBLEM NAME: grassplant
Формат входных данных
* Строка 1: Два разделенных пробелом целых числа N и M
* Строки 2..N: Два разделенных пробелом целых числа, описывающих конечные точки дороги.
* Строки N+1..N+M: Строка i+1 описывает шаг i. Первый символ этой строки либо P либо Q, которые описывают ФД садит траву или отвечает на вопрос. Затем следуют два разделенных пробелом целых числа A_i B_i (1 <= A_i, B_i <= N), которые описывают путь (для действия или вопроса)
Формат выходных данных
* Строки 1..???: Каждая строка содержит ответ на вопрос, в порядке поступления вопросов

Деревья

—Войти и решать

Cow Photography#89790

Использование сортировки

—Войти и решать

Escaping the Farm#89788

Коровы планируют сбежать от Фермера Джона на плоту, через реку. Проблема заключается в том, что плот может не выдержать всех желающих. N коров (1 <= N <= 20) имеют веса w₁ ... w_N. У коров плохо со сложением, они не умеют выполнять перенос. Вам требуется определить размер наибольшей группы коров, веса которых можно сложить без переноса при сложении.
PROBLEM NAME: escape
Формат входных данных
* Строка 1: Количество коров, N (1 <= N <= 20).
* Строки 2..N+1: Каждая строка содержит вес одной коровы, целое число от 1...100,000,000.
Формат выходных данных
* Строка 1: максимальное количество коров, чьи веса могут быть сложены без переноса.

Примечание
Три веса 522, 6, 7311, могут быть сложены без переноса.
522 6 + 7311 ------ 7839

битмаски Перебор

✓ 2✗ 12—Войти и решать

Cow Photography (Bronze Level)#89787

Problem XX: Cow Photography (Bronze) [Brian Dean, 2011]
Фермер Джон хочет сделать фотографию всех коров, выстроенных в ряд, а они не стоят на месте. N (1 <= N <= 20,000) коров помечены номерами от 1 до N. ФД хочет сфотографировать их, стоящими в ряд в конкретном порядке, заданном массивом A[1..N], где a[j] содержит номер j-той коровы в этом порядке. ФД выстроил коров в этом порядке, но прежде чем он нажал на клавишу фотоаппарата "Сделать снимок", одна корова переместилась на новую позицию. Он снова поставил их в нужном порядке (указанном массивом A), Но снова перед нажатием кнопки уже другая корова переместилась на новую позицию. Так происходило 5 раз. Вам дано содержание каждой фотографии, Вы должны реконструировать содержимое массива A. На каждой из фотографий не более чем одна корова переместилась на новую позицию. Возможно, что ни одна корова не перемещалась.
PROBLEM NAME: photo
Формат входных данных
* Строка 1: Количество коров, N (1 <= N <= 20,000).
* Строки 2..5N+1: Следующие 5N строк описывают 5 порядков, каждый состоит из N последовательных строк. Каждая строка содержит номер коровы, целое число.
Формат выходных данных
* Строки 1..N: Исходный порядок коров в массиве A, по одному ID в строке.
Примечание
Правильный исходный порядок в массиве A[1..5]: 1, 2, 3, 4, 5.

Использование сортировки

✓ 0✗ 2—Войти и решать

Выбор участка - 1 (24-25)#89300

Маша хочет построить дачу на одной приглянувшейся ей улице. Эта улица имеет длину n, то есть состоит из n одинаковых идущих подряд участков. На каждом участке указан уровень шума от 1 до 9 (где 1 — тишина, 9 — очень шумно).

Маша хочет найти участок с уровнем шума ровно 1 (тихий участок), который находится максимально далеко от шумных участков. Шумным считается участок с уровнем шума 7 или больше.

Необходимо написать программу, которая найдёт номер такого тихого участка и расстояние до ближайшего шумного участка.

Если таких участков несколько, выбрать участок с наименьшим номером.

Гарантируется, что есть хотя бы один тихий участок (уровень шума 1) и хотя бы один шумный участок (уровень шума ≥ 7).

Формат входных данных

В первой строке натуральное число n (1 ≤ n ≤ 6 000 000)
Во второй строке n чисел от 1 до 9 через пробел

Формат выходных данных

Номер участка и расстояние до ближайшего шумного (через пробел)

Линейный поиск

✓ 1✗ 4—Войти и решать

Длина НВП - 1 (24-25)#89299

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

Пример: в последовательности 5 8 13 9 17 12 21 25 можно выбрать:

5 9 17 21 25 или 5 13 17 21 25 (остаток 1 при делении на 4, длина 5)
8 12 (остаток 0 при делении на 4, длина 2)

Максимальная длина = 5.

Напишите программу, которая находит эту максимальную длину.

Формат входных данных

В первой строке число n (1 ≤ n ≤ 20000)
Во второй строке n чисел через пробел

Формат выходных данных

Длина самой большой такой подпоследовательности

Динамическое программирование: один параметр

✓ 0✗ 4—Войти и решать

Размещения без крутых спусков#89082

Размещением из \(n\) по \(k\) называется массив \(a[1..k]\), содержащий \(k\) различных натуральных чисел, каждое из которых находится в диапазоне от \(1\) до \(n\).

Пара подряд идущих элементов размещения \(a[i], a[i + 1]\) называется спуском, если \(a[i] > a[i+1]\). Спуск называется крутым, если \(a[i] > a[i + 1] + 1\).

По заданным \(n\) и \(k\) требуется вывести все размещения из \(n\) по \(k\) без крутых спусков. Размещения необходимо упорядочить по первому числу, при равенстве первого — по второму, затем по третьему и так далее.

Первая строка ввода содержит натуральное число \(n\), вторая строка ввода содержит натуральное число \(k\) (\(1 \le k \le n \le 13\)).

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

Простые задачи на перебор

✓ 4✗ 20—Войти и решать

Бинарный поиск в подмножестве#84682

У Васи есть набор чисел. Для каждого запроса нужно найти минимальное число из набора, которое больше или равно заданному X. Если такого числа нет, вывести -1.

Формат входных данных

В первой строке — число N (1 ≤ N ≤ 100000) — размер набора.

Во второй строке — N целых чисел (1 ≤ число ≤ 1000000).

В третьей строке — число Q (1 ≤ Q ≤ 100000) — количество запросов.

В следующих Q строках — по одному числу X (1 ≤ X ≤ 1000001).

Формат выходных данных

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

Бинарный поиск в массиве

✓ 2✗ 10—Войти и решать

Пицца для программиста#82078

Программист Вася заказывает пиццу. В меню есть N топпингов, пронумерованных от 1 до N. Вася хочет попробовать ВСЕ возможные комбинации топпингов (включая пиццу без топпингов).

Помогите Васе составить список всех возможных пицц. Каждая пицца описывается набором номеров топпингов на ней.

ВАЖНО: Пиццы в списке должны быть отсортированы в лексикографическом порядке. Топпинги внутри каждой пиццы должны быть в порядке возрастания номеров.

ВХОДНЫЕ ДАННЫЕ:
Одно число N (1 ≤ N ≤ 10) - количество топпингов в меню.

ВЫХОДНЫЕ ДАННЫЕ:
Выведите 2^N строк - все возможные пиццы.
Пустая пицца (без топпингов) обозначается как "-".
Для непустых пицц выведите номера топпингов через пробел.

Комбинаторные структуры

—Войти и решать

Кролик и морковки#82076

Кролик Роджер находится в начале числовой прямой (позиция 0) и хочет добраться до позиции N, где лежит гигантская морковка.

Кролик умеет делать только два вида прыжков:
- Короткий прыжок: +1 позиция (тратит 1 единицу энергии)
- Длинный прыжок: +2 позиции (тратит 1 единицу энергии)

Сколько РАЗЛИЧНЫХ способов есть у Роджера добраться до морковки?

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

ВХОДНЫЕ ДАННЫЕ:
Одно число N (0 ≤ N ≤ 45) - позиция морковки.

ВЫХОДНЫЕ ДАННЫЕ:
Одно число - количество различных способов добраться до морковки.

Динамическое программирование: один параметр

✓ 2✗ 4—Войти и решать

Все пути до листьев#81755

Выведите все пути от корня до каждого листа дерева.

Формат входных данных
JSON с деревом решений.

Формат выходных данных
Каждый путь на отдельной строке: id узлов через пробел от корня до листа. Пути отсортированы по id конечного листа (по возрастанию).

Деревья

✓ 4✗ 0—Войти и решать

Путь к узлу#81749

Дано дерево решений и id целевого узла. Найдите путь от корня (id=0) до этого узла.

Формат входных данных
Первая строка: JSON с деревом. Вторая строка: целевой id узла.

Формат выходных данных
ID узлов от корня до целевого, через пробел.

Деревья

✓ 6✗ 0—Войти и решать

Глубина дерева#81748

Найдите максимальную глубину дерева решений. Глубина корня равна 0.

Формат входных данных
JSON с деревом решений.

Формат выходных данных
Одно целое число — глубина дерева.

Деревья

✓ 5✗ 0—Войти и решать

Ремонт забора#67666

Забор состоит из N одинаковых вертикальных досок. Некоторые из досок сгнили и нуждаются в замене, для каждой доски известно, нужно ли её заменить. Для ремонта забора можно использовать продающиеся в магазине щиты, которые бывают L разных видов: шириной в 1 доску, в 2 доски, ..., в L досок. Щит нельзя разрезать на части, то есть одним щитом можно заменить не более любых L подряд идущих досок. При этом можно менять не только сгнившие доски, но и хорошие.

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

Входные данные

Первая строка входных данных содержит целое число L (L > 0) – максимальный размер щита. Во второй строке входных данных записано целое число N (N > 0) – количество досок в заборе. Следующие N строк содержат по одному числу, равному 0 или 1. Число 1 обозначает, что соответствующая доска в заборе нуждается в замене, число 0 – что доска может быть сохранена.

Выходные данные

Программа должна вывести одно целое число – минимальное число щитов, которое необходимо приобрести для ремонта всего забора.

Жадный алгоритм Задача на реализацию

✓ 1✗ 0—Войти и решать

Проверка на валидность#67515

re.fullmatch(pattern, string) - проверяет совпадение ВСЕЙ строки с шаблоном.

Возвращает: объект Match или None

Использование: match = re.fullmatch(r'\d+', text)

Проверить, что строка является корректным ID товара:

Формат: [Категория][Номер][Версия]
Категория: 1 буква (A-Z)
Номер: 1-3 цифры
Версия: необязательная, начинается с '-v' и 1-2 цифры

Программа на вход получает строку и должна вывести True, если ID товара корректен и False в противном случае.

Конечные автоматы

✓ 2✗ 2—Войти и решать