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

Don't Be Last!#90391

У Фермера Джона есть 7 молочных коров: Bessie, Elsie, Daisy, Gertie, Annabelle, Maggie, Henrietta. Он доит их каждый день и хранит детальный протокол количества молока, которая дала каждая корова во время каждой дойки. Не удивительно, что ФД поощряет коров, которые дают больше молока.

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

ФОРМАТ ВВОДА (файл notlast.in):

Ввод начинается со строки, содержащей целое число \(N\) (\(1 \leq N \leq 100\)), определяющее количество записей в протоколе дойки.

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

Любая корова, которая не появилась протоколе - не произвела молока вообще.

ФОРМАТ ВЫВОДА (файл notlast.out):

В единственной строке вывода выведите имя коровы, которая произвела второе по минимальности количество молока. Более точно, если \(M\) минимальное количество молока из всех произведённых коровами, выведите имя коровы, которая произвела минимальное колчиество млока, большее чем \(M\). Если несколько коров произвели такое количество молока или нет аких коров (т.е. все произвели по \(M\) молока), выведите слово "Tie". Не забудьте добавить символ перевода строки в своему выводу. Заметим, что \(M=0\) если одна из коров полностью отсутствует в протоколе дойки.

Алгоритмы обработки

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

Block Game#90356

Фермер Джон пытается научить своих коров читать, дав им множество из N дощечек, обычно используемых дошкольниками (\(1 \leq N \leq 100\)). Каждая дощечка имеет слово и рисунок на каждой стороне. Например, одна сторона может иметь слово 'cat' и картинку кота на одной стороне и слово 'dog' и картинку собаки на другой стороне.

Когда дощечки лежат на земле, видно \(N\) слов. Переворачивая таблички можно получать различные множества из \(N\) слов. Чтобы помочь коровам запомнить буквы, ФД хочет подготовить некоторое количество деревянных блоков, на каждом из которых выписана одна буква алфавита. Он хочет подготовить достаточное количество блоков с каждой буквой, для того чтобы вне зависимости от того, какое множество из \(N\) слов показывается, коровы могли составить все слова используя эти блоки. Например, если \(N=3\) и на табличках представлены слова 'box', 'cat', 'car', коровам нужно как минимум 1 'b', 1 'o', 1 'x', 2 'c', 2 'a', 1 't', 1 'r'.

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

ФОРМАТ ВВОДА (файл blocks.in):

Строка 1 содержит целое число \(N\).

Каждая из следующих \(N\) строк содержит 2 слова, разделённых одиночным пробелом, задавая два слова на противоположных сторонах дощечки. Каждое слово – строка не более чем из 10 маленьких английских букв.

ФОРМАТ ВЫВОДА (файл blocks.out):

Выведите 26 строк. Первая выходная строка должна содержать требуемое количество букв ‘a’. Следующая строка должна содержать требуемое количество букв ‘b’. И т.д.

Алгоритмы обработки

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

Herdle#90163

Коровы создали новый вид пазлов, который назвали Herdle.

Каждый день они выпускают новый пазл. Пазл представляет собой решётку 3*3, гже каждая клетка занята коровой определённой породы. Всего имеется 26 различных видов пород, которые представляются большими латинским буквами от A до Z. Играющий должен узнать тип породы в каждой клетке через серию запросов. В каждом запросе от представляет 3*3 латинских букв. Ответ формируется следующим образом: если буквы угаданы, они подсвечиваются зелёным, Буквы верной породы, но не на своём месте подсвечиваются жёлтым.

Количество подсвеченных указывает, сколько их должно быть. Например, предположим, что гипотеза содержит 4 символа A, а правильный ответ содержит только 2 символа A, причём ни одна позиция не угадана. Тогда в ответе на этот запрос только 2 символа A будут подсвечены жёлтым. В общем случае, если \(x\) коров определённой породы в запросе и только \(y\) - в правильном ответе (не считая коров, которые уже стоят на своём месте и будут подсвечены зелёным), только \(y\) из этих \(x\) коров будут подсвечены жёлтым.

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

ФОРМАТ ВВОДА (с клавиатуры / stdin):

Первые 3 строки ввода содержат решётку, представляющую правильный ответ. Слеующие 3 строки представляют запрос.

ФОРМАТ ВЫВОДА(на экран / stdout):

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

Алгоритмы обработки

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

Empty Stalls#89900

Новый амбар Фермера Джона представляет собой большой круг из N стойл (2 <= N <=3,000,000), пронумерованных от 0 до N-1, стойло N-1 соседствует со стойлом 0.
В конце каждого дня коровы ФД возвращаются в амбар, одна за одной, У каждой имеется предпочтительный номер стойла, который она хочет занять. Однако если это место уже занято другой коровой, она идёт вперёд последовательно от этого стойла, пока не найдёт первое не занятое стойло, которое она и займёт. Если она пройдёт стойло N-1, она продолжит поиск со стойла 0.
По заданному предпочтительному номеру для каждой коровы определите минимальный номер стойла, который останется незанятым после того как все коровы вернутся в амбар. Заметим, что ответ на этот вопрос не зависит от того, в каком порядке возвращаются коровы
Для того, чтобы избежать проблем с огромным вводом, данные вводятся в специальном формате, использующем K строк (1 <= K <=10,000) вида
X Y A B
Здесь описываются предпочтительные стойла X Y коров: X коров предпочитают каждое из стойл f(1) .. f(Y), где f(i)= (Ai + B) mod N. Значения A и B лежат в диапазоне 0...1,000,000,000.
Не забудьте про стандартное для всех задач ограничение на память – 64 Мбт.
PROBLEM NAME: empty
Формат входных данных
* Строка 1: Два разделённых пробелом целых числа: N и K.
* Строки 2..1+K: каждая строка содержит целые числа X Y A B, смысл которых описан выше. Общее количество коров описываемых этими числами не превысит N-1. Коровы могут добавляться в одно и тоже стойло разными из этих строк.
Формат выходных данных
* Строка 1: Минимальный индекс не занятого стойла.
Примечание
Все стойла будут заняты кроме стойла с номером 5.

Алгоритмы обработки

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

Cows in a Row#89851

У Фермера Джона N коров (1 <= N <= 1000) выстроены в ряд. У каждой коровы имеется ID породы. У коровы с номером i, ID породы B(i).
ФД думает, что его ряд коров выглядел бы более впечатляюще, если бы он имел как можно более длинный непрерывный блок коров с одинаковым ID коровы. Для того, чтобы создать такой блок, ФД решил удалить из своего ряда всех коров, имеющих конкретный ID породы, который он выберет.
Помогите ФД определить длину наибольшего непрерывного блока коров с одинаковым ID, который он может получить, удалив всех коров с некоторым ID, который выберет ФД.

PROBLEM NAME: cowrow
Формат входных данных
* Строка 1: Целое число N.
* Строки 2..1+N: Строка i+1 содержит B(i), целое число в диапазоне 0...1,000,000.
Формат выходных данных
* Строка 1: Наибольший размер непрерывного блока коров, с одинаковым ID коровы, который он может создать.

Примечание
При удалении всех коров с ID=3, ФД может получить ряд 2, 7, 7, 7, 7, 5, 7. В этому ряду максимальный непрерывный блок состоит из 4 коров с ID 7.

Алгоритмы обработки

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

Haybale Stacking#89826

Беси согласилась помочь ФД уложить пакеты с сеном. Она начинает с N (1 <= N <= 1,000,000, N нечетное) пустых стеков, пронумерованных от 1 до N. Затем ФД дает ей последовательность из K инструкций (1 <= K <= 25,000), каждая вида A B, означающая, что Беси должна добавить по одному пакету с сеном в каждый из стеков в диапазоне от A до B. Например, инструкция 10 13 означает, что Беси должна положить по пакету сеном в стеки 10, 11, 12, 13.
После того как вся работа закончена, ФД хочет узнать медианную высоту всех N своих стеков - то есть высоту среднего стека, если все стеки упорядочить по высоте. По условию N нечетно, поэтому этот стек уникален. Пожалуйста, помогите Беси ответить на этот вопрос.
PROBLEM NAME: stacking
Формат входных данных
* Строка 1: Два разделенных пробелом целых числа, N K.
* Строки 2..1+K: Каждая строка содержит одну инструкцию ФД в виде двух целых (разделенных пробелом) чисел A B (1 <= A <= B <= N).

Формат выходных данных
* Строка 1: Медианная высота после того как Беси выполнит все инструкции

Примечание
После того, как Беси закончит, стеки будут иметь высоты 0,1,2,3,3,1,0. Если их упорядочить, получим: 0,0,1,1,2,3,3. Средний элемент равен 1.

Алгоритмы обработки Использование сортировки Префиксные суммы(минимумы, ...)

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

Hay Bales#89789

Коровы вернулись! Фермер Джон аккуратно выстроил N (1 <= N <= 10,000) столбиков одинаковой высоты из пакетов сена. Однако пока он отошел ненадолго, коровы поперетаскивали некоторые пакеты между столбиками, так что теперь они необязательно имеют одинаковую высоту. По заданным новым высотам столбиков определите минимальное количество пакетов сена, которые нужно перенести, чтобы вернуть столбики к их исходным, одинаковым высотам.
PROBLEM NAME: haybales
Формат входных данных
* Строка 1: Количество столбиков, N (1 <= N <= 10,000). * Строки 2..1+N: Каждая строка содержит количество пакетов сена в одном столбике (целое число, от 1 до 10 000)
Формат выходных данных
* Строка 1: Одно целое число - минимальное количество пакетов сена, которое необходимо перенести, чтобы столбики стали одинаковой высоты.
Примечание
Переместив 7 пакетов сена, мы можем выровнять к 5 все высоты. 3 из столбика 2 в столбик 1, 2 из столбика 2 в столбик 4, 2 из столбика 3 в столбик 4.

Алгоритмы обработки

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

Победитель выборов#89748

На выборах мэра баллотируются три кандидата (номера 1, 2, 3). Побеждает кандидат, набравший строго больше голосов, чем каждый из остальных. Если два или три кандидата набрали одинаковое максимальное число голосов, выведите REPEAT (необходим второй тур).

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

Первая строка — целое число N (1 <= N <= 10000) - количество проголосовавших.
Каждая из следующих N строк содержит одно число (1, 2 или 3) - результат голосания каждого избирателя.

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

Номер победителя или REPEAT.

Алгоритмы обработки

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

Подсчёт голосов#89746

В школе проходят выборы президента ученического совета. Баллотируются три кандидата (номера 1, 2, 3). Каждый ученик голосует за одного из них.
Определите, сколько голосов набрал каждый кандидат.

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

Первая строка — целое число N (1 <= N <= 1000) — количество проголосовавших.
Каждая из следующих N строк содержит одно целое число (1, 2 или 3) — голос ученика.

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

Три числа через пробел — количество голосов за кандидата 1, 2 и 3 соответственно.

Алгоритмы обработки

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

Набор в космическую академию#84267

Космическая Академия «Звёздный Путь» проводит ежегодный набор курсантов. Отбор кандидатов происходит по сумме баллов трёх вступительных испытаний (физическая подготовка, математика, астронавигация) и собеседования с приёмной комиссией.

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

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

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

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

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

В первой строке находятся два числа:

- N — количество кандидатов (натуральное число, не превышающее 10000)

- S — количество имеющихся мест (натуральное число, S ≤ N)

Каждая из следующих N строк содержит пять чисел:

- ID кандидата (натуральное число, не превышающее 10 000 000)

- три оценки по испытаниям (целые неотрицательные числа, не превышающие 100)

- балл за собеседование (целое неотрицательное число, не превышающее 10)

Гарантируется, что в исходных данных существует полупроходной балл.

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

Два целых числа через пробел: полупроходной балл и ID кандидата с полупроходным баллом, занявшего последнее место.

Примечание

В первом тестовом примере

- ID=1001: сумма экзаменов = 270, собеседование = 10 → проходит (проходной балл)

- ID=1002: сумма = 240, собеседование = 8 → полупроходной балл, проходит

- ID=1003: сумма = 240, собеседование = 5 → не проходит (собеседование меньше)

- ID=1004: сумма = 210, собеседование = 10

Мест: 2. Кандидат с ID=1001 проходит автоматически. Осталось 1 место, но с суммой 240 — два кандидата. Это полупроходной балл. Между ними выбираем по собеседованию: ID=1002 (собес 8) > ID=1003 (собес 5).

Во втором тестовом примере
Все кандидаты имеют одинаковую сумму баллов (240) и одинаковый балл за собеседование (5). Мест: 2. Выбираем по ID в порядке убывания: сначала 503, затем 502. Последний зачисленный — кандидат с ID=502.

ЕГЭ - вычислительные задачи Задача на реализацию Массивы реализация

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

Подводная станция#82123

На подводной исследовательской станции «Нептун-7» требуется установить новый научный модуль. Станция состоит из M уровней (пронумерованных от 1 до M сверху вниз, где уровень 1 ближе всего к поверхности) и K отсеков на каждом уровне.

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

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

Гарантируется, что хотя бы один свободный отсек на станции существует.

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

В первой строке находятся три числа:

N — количество занятых отсеков (1 ≤ N ≤ 10 000)
M — количество уровней (1 ≤ M ≤ 100 000)
K — количество отсеков на каждом уровне (1 ≤ K ≤ 100 000)

В следующих N строках находятся пары натуральных чисел: номер уровня и номер отсека занятого места соответственно.

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

Два целых числа через пробел:

Номер уровня выбранного отсека
Количество свободных отсеков над ним (подряд, с тем же номером)

ЕГЭ - вычислительные задачи Задача на реализацию Массивы реализация

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

Космический техосмотр#82122

На орбитальной станции «Галактика-7» завершился ежегодный технический осмотр космических кораблей. По его результатам каждый корабль получил:

Оценки трёх бортовых систем: двигательной, навигационной и системы жизнеобеспечения (по шкале от 2 до 5, где 2 — критическая неисправность, 5 — отличное состояние)
Статус лицензии пилота: действующая или просроченная

Корабль допускается к полётам, если выполнены оба условия:

Все три бортовые системы имеют оценку 3 или выше
Лицензия пилота действующая

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

Руководство станции решило предоставить возможность экстренного ремонта одной системы одному из кораблей. Корабль может претендовать на ремонт, если:

Лицензия пилота действующая
Ровно одна система имеет критическую неисправность (оценка 2), а две другие системы исправны (оценка 3 или выше)

Если таких кораблей несколько, выбирается тот, у которого наибольшая сумма оценок всех трёх систем (такой корабль ближе всего к допуску).

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

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

В первой строке находится число N — количество кораблей (1 ≤ N ≤ 1000).

Каждая из следующих N строк содержит пять целых чисел через пробел:

ID — бортовой номер корабля (натуральное число, не превышающее 10⁸)
S₁, S₂, S₃ — оценки трёх бортовых систем (каждая от 2 до 5)
L — статус лицензии пилота (1 — действующая, 0 — просроченная)

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

Выведите два числа через пробел:

Количество кораблей, не допущенных к полётам
Бортовой номер корабля, который получит возможность экстренного ремонта

ЕГЭ - вычислительные задачи Задача на реализацию Массивы реализация

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

КОЛИЧЕСТВО ЛОКАЛЬНЫХ МАКСИМУМОВ#81918

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

Двумерные массивы

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

СУММА ЭЛЕМЕНТОВ НА КРАЯХ МАТРИЦЫ#81917

Программа получает на вход размеры матрицы n и m (количество строк и столбцов), затем элементы матрицы (n строк по m чисел в каждой). Все числа целые, не превышают по модулю 1000. Программа должна вывести сумму элементов первой строки, последней строки, первого столбца и последнего столбца. Угловые элементы учитываются один раз.

Двумерные массивы

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

КОЛИЧЕСТВО ЭЛЕМЕНТОВ БОЛЬШЕ СРЕДНЕГО#81916

Программа получает на вход размеры матрицы n и m (количество строк и столбцов), затем элементы матрицы (n строк по m чисел в каждой). Все числа целые, не превышают по модулю 1000. Программа должна вывести количество элементов матрицы, которые больше среднего арифметического всех элементов.

Двумерные массивы

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

НОМЕР СТОЛБЦА С МИНИМАЛЬНОЙ СУММОЙ#81915

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

Двумерные массивы

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

СУММА ЭЛЕМЕНТОВ ВЫШЕ ГЛАВНОЙ ДИАГОНАЛИ#81914

Программа получает на вход размер квадратной матрицы n, затем элементы матрицы (n строк по n чисел в каждой). Все числа целые, не превышают по модулю 1000. Программа должна вывести сумму элементов, расположенных выше главной диагонали (элементы, где номер столбца больше номера строки при нумерации с 0).

Двумерные массивы

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

КОЛИЧЕСТВО ПОЛОЖИТЕЛЬНЫХ В КАЖДОЙ СТРОКЕ#81913

Программа получает на вход размеры матрицы n и m (количество строк и столбцов), затем элементы матрицы (n строк по m чисел в каждой). Все числа целые, не превышают по модулю 1000. Программа должна вывести n чисел: количество положительных элементов в каждой строке (каждое число на отдельной строке).

Двумерные массивы

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

НОМЕР СТРОКИ С МАКСИМАЛЬНОЙ СУММОЙ#81912

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

Двумерные массивы

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

СУММА ПОБОЧНОЙ ДИАГОНАЛИ#81911

Программа получает на вход размер квадратной матрицы n, затем элементы матрицы (n строк по n чисел в каждой). Все числа целые, не превышают по модулю 1000. Программа должна вывести сумму элементов побочной диагонали (элементы, где сумма номера строки и номера столбца равна n+1 при нумерации с 1).

Двумерные массивы

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