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

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—Войти и решать

Классификация точек#89229

На плоскости отмечены несколько красных, синих и черных точек. Требуется покрасить каждую черную точку в красный или синий цвет так, чтобы сумма расстояний между всеми парами красных точек и расстояний между всем парами синих точек было минимальным. На вход подается csv-файл, в первой строке которого записаны заголовки столбцов: id,x,y,color

Входные данные
В каждой из остальных строк записана информация об одной из точек: id, x и y — целые числа, color — 0 для черных точек, 1 для красных точек и 2 для синих.

Общее количество точек не превосходит 15.

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

Примеры

№	Входные данные	Выходные данные
1	id,x,y,color 1,1,0,1 2,2,0,2 3,3,0,0 4,4,0,0	4.0

Перебор

✓ 2✗ 761 400средняяВойти и решать

Путь в лабиринте#89120

Дан лабиринт в виде прямоугольной таблицы N×M. Символ '.' — проход, символ '#' — стена. Найдите количество различных путей из левого верхнего угла (0,0) в правый нижний угол (N-1, M-1).
Двигаться можно только вправо или вниз. Проходить через одну клетку дважды нельзя.

Формат входных данных
Первая строка: два числа N и M — размеры лабиринта (2 ≤ N, M ≤ 5)
Следующие N строк: лабиринт (символы '.' и '#')

Формат выходных данных
Одно число — количество различных путей.
Если путей нет, вывести 0.

Примечание

В тестовом примере существуют два пути
Путь 1: (0,0)→(1,0)→(2,0)→(2,1)→(2,2)
Путь 2: (0,0)→(0,1)→(0,2)→(1,2)→(2,2)

ПОДСКАЗКА:
1. Отмечай посещённые клетки, чтобы не ходить по кругу
2. При откате снимай отметку о посещении
3. Проверяй границы лабиринта и стены

Рекурсивный перебор

✓ 15✗ 12800средняяВойти и решать

Подмножества с заданной суммой#89119

Дан набор различных положительных чисел и целевая сумма S. Найдите все подмножества, сумма элементов которых равна S. Каждое число можно использовать не более одного раза.

Формат входных данных
Первая строка: числа через пробел (от 2 до 8 чисел)
Вторая строка: целевая сумма S

Формат выходных данных
Все подмножества с суммой S, каждое на отдельной строке. Числа в подмножестве выводить через пробел в порядке возрастания. Подмножества выводить в лексикографическом порядке. Если решений нет, вывести "NO"

Примечание

В тестовом примере возможны только две комбинации
2+3+5=10
3+7=10
Другие комбинации не дают сумму 10.

ПОДСКАЗКА:
Для каждого числа есть два варианта: взять его или не взять. Используй отсечение: если текущая сумма уже больше S, дальше искать не нужно.

Рекурсивный перебор

✓ 52✗ 77700средняяВойти и решать

Размен монет#89118

Даны номиналы монет и сумма S. Найдите количество способов разменять сумму S данными монетами. Каждую монету можно использовать неограниченное число раз.

Важно: наборы, отличающиеся только порядком монет, считаются одинаковыми! Например, 1+2 и 2+1 — это один способ.

Формат входных данных
Первая строка: номиналы монет через пробел (от 1 до 5 монет)
Вторая строка: сумма S (1 ≤ S ≤ 20)

Формат выходных данных
Одно число — количество способов размена.

Примечание

В тестовом примере способы разменять 4:

1+1+1+1
1+1+2
2+2

Всего 3 способа.

ПОДСКАЗКА:
Чтобы избежать повторений (1+2 и 2+1), перебирай монеты в определённом порядке: каждая следующая монета должна быть не меньше предыдущей.

Рекурсивный перебор

✓ 24✗ 11600лёгкаяВойти и решать

Перестановки#89117

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

Формат входных данных
Одна строка: цифры через пробел (от 2 до 5 различных цифр)

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

ПОДСКАЗКА:
Нужно отслеживать, какие цифры уже использованы. Используй множество (set) или список для отметки использованных цифр. При откате не забудь снять отметку!

Рекурсивный перебор

✓ 28✗ 21600лёгкаяВойти и решать

Числа без повторяющихся соседей#89116

Даны цифры и длина числа N. Выведите все числа длины N, составленные из данных цифр, в которых никакие две соседние цифры не совпадают.

Формат входных данных
Первая строка: цифры через пробел (от 2 до 5 цифр)
Вторая строка: длина числа N (2 ≤ N ≤ 5)

Формат выходных данных
Все подходящие числа, каждое на отдельной строке. Числа выводить в лексикографическом порядке.

ОБЪЯСНЕНИЕ:
Числа 11, 22, 33 не подходят, так как соседние цифры одинаковые.

ПОДСКАЗКА:
Перед добавлением цифры проверяй, не равна ли она последней добавленной. Если равна — это отсечение, пропускаем эту ветку.

Рекурсивный перебор

✓ 40✗ 218500лёгкаяВойти и решать

Числа с заданной суммой цифр#89115

Даны цифры и целевая сумма S. Выведите все числа (любой длины), составленные из данных цифр, сумма цифр которых равна S. Цифры могут повторяться.

Формат входных данных
Первая строка: цифры через пробел (от 1 до 5 цифр, все цифры > 0)
Вторая строка: целевая сумма S (1 ≤ S ≤ 15)

Формат выходных данных
Все возможные числа с суммой цифр = S, каждое на отдельной строке. Числа выводить в лексикографическом порядке. Если решений нет, вывести "NO"

ПОДСКАЗКА:
Используй отсечение! Если текущая сумма уже больше S, дальше искать не нужно — это экономит время.

Рекурсивный перебор

✓ 42✗ 71500лёгкаяВойти и решать

Все числа#89114

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

Формат входных данных
Первая строка: цифры через пробел (от 1 до 5 цифр)
Вторая строка: длина числа N (1 ≤ N ≤ 4)

Формат выходных данных
Все возможные числа, каждое на отдельной строке. Числа выводить в лексикографическом порядке (как в словаре).

ПОДСКАЗКА:
Это базовая задача на перебор. Откат здесь не нужен, достаточно рекурсивно перебрать все комбинации.

Рекурсивный перебор

✓ 74✗ 76300лёгкаяВойти и решать

Размещения без крутых спусков#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—Войти и решать

Задача 1. Подсчёт соседей#88717

Дан набор точек. Напишите программу, которая считает количество соседей у заданной точки в радиусе eps

Формат входных данных
Первая строка: n eps — количество точек и радиус (n - натуральное, не превышает 100 , eps - вещественное)
Следующие n строк: x y — координаты точек (целые числа, по модулю не превышают 100)
Последняя строка: qx qy — точка запроса (целые числа, по модулю не превышают 100).
Гарантируется, что заданная точка находится в заданном наборе точек.

Формат выходных данных
Одно число — количество соседей (не считая саму точку)

Элементарная геометрия

✓ 12✗ 13400лёгкаяВойти и решать