Информатика

7 731 задачавместе с подтемами

Число у задачи — рейтинг сложности, слово рядом — насколько она трудна по сравнению с другими задачами такого же типа. Шкалы задач с ответом и задач с кодом между собой не сравниваются. Рядом — счётчики попыток: ✓ успешные, ✗ неуспешные.

РейтингЛюбой до 800 800–1199 1200–1599 1600+Без рейтинга

СначалаПодходящие Новые Популярные Простые Сложные

Системы счисления: сложение и вычитание (1)#95202

Чему равно значение выражения в системе счисления с основанием 16?

$1010{,}1_2 + 1\mathrm{A}{,}8_{16} - 3{,}4_8$

В ответе укажите только число (целую и дробную часть через запятую), основание указывать не нужно.

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

Анаграммы: города#92180

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

На вход подаётся число $N$, затем $N$ слов (каждое с новой строки, все строчные).

Программа должна:

Разбить слова на группы анаграмм
Вывести каждую группу, в которой больше одного слова
Группы отсортировать по убыванию размера. При равном размере — по алфавиту первого слова
Слова внутри группы — в алфавитном порядке, через пробел

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

Первая строка — целое число $N$ ($1 \le N \le 30$).

Следующие $N$ строк — по одному слову (строчные русские буквы).

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

Группы анаграмм (только те, где больше одного слова). Слова в группе через пробел в алфавитном порядке. Каждая группа на отдельной строке.

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

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

Анаграммы: природа#92179

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

На вход подаётся число $N$, затем $N$ слов (каждое с новой строки, все строчные).

Программа должна:

Разбить слова на группы анаграмм
Вывести каждую группу, в которой больше одного слова
Группы отсортировать по убыванию размера. При равном размере — по алфавиту первого слова
Слова внутри группы — в алфавитном порядке, через пробел

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

Первая строка — целое число $N$ ($1 \le N \le 30$).

Следующие $N$ строк — по одному слову (строчные русские буквы).

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

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

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

Анаграммы: еда#92178

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

На вход подаётся число $N$, затем $N$ слов (каждое с новой строки, все строчные).

Программа должна:

Разбить слова на группы анаграмм
Вывести каждую группу, в которой больше одного слова
Группы отсортировать по убыванию размера. При равном размере — по алфавиту первого слова
Слова внутри группы — в алфавитном порядке, через пробел

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

Первая строка — целое число $N$ ($1 \le N \le 30$).

Следующие $N$ строк — по одному слову (строчные русские буквы).

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

Примечание

Подсказка: два слова — анаграммы, если при сортировке их букв получается одинаковый результат. Например, sorted("кот") и sorted("ток") оба дают ['к', 'о', 'т'].

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

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

Журнал домашних заданий#92177

Учитель ведёт журнал сдачи домашних заданий. На вход подаётся число $N$ — количество записей. Затем $N$ строк в формате:

имя предмет балл

Один ученик может сдавать задания по разным предметам.

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

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

Первая строка — целое число $N$ ($1 \le N \le 30$).

Следующие $N$ строк — имя, предмет и балл через пробел.

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

Для каждого ученика строка в формате: Имя — X заданий, Y баллов

Алгоритмы обработки Использование сортировки Словари

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

Больше среднего#92165

Пользователь вводит количество чисел, а затем сами числа — каждое на отдельной строке. Сохраните все числа в список.

Вычислите среднее арифметическое. Выведите три строки:

Исходный список — числа через пробел.
Среднее арифметическое, округлённое до 1 знака после запятой.
Числа, которые строго больше среднего, через пробел (в порядке ввода). Если таких нет — пустая строка.

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

Первая строка — целое число $N$ ($1 \le N \le 20$).

Следующие $N$ строк — по одному целому числу (от $-1000$ до $1000$).

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

Первая строка — исходный список через пробел.

Вторая строка — среднее с одним знаком после запятой.

Третья строка — числа больше среднего через пробел.

Алгоритмы обработки Вычисление по заданной формуле Одномерные массивы

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

Среднее арифметическое#92161

Выведите две строки:

Исходный список — числа через пробел.
Среднее арифметическое, округлённое до 1 знака после запятой.

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

Первая строка — целое число $N$ ($1 \le N \le 20$).

Следующие $N$ строк — по одному целому числу (от $-1000$ до $1000$).

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

Первая строка — исходный список через пробел.

Вторая строка — среднее арифметическое с одним знаком после запятой.

Примечание

Подсказка: среднее = сумма / количество. Для вывода используйте round(x, 1).

Вычисление по заданной формуле Одномерные массивы Строки

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

Слова по алфавиту#92155

Пользователь вводит количество слов, а затем сами слова — каждое на отдельной строке. Сохраните все слова в список.

Выведите две строки:

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

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

Первая строка — целое число $N$ ($1 \le N \le 15$).

Следующие $N$ строк — по одному слову (строчные русские буквы, без пробелов).

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

Две строки: исходный список и отсортированный по алфавиту, слова через пробел.

Использование сортировки Одномерные массивы Строки

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

Числа по возрастанию#92153

Выведите две строки:

Исходный список — числа через пробел в порядке ввода.
Отсортированный список — числа через пробел по возрастанию.

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

Первая строка — целое число $N$ ($1 \le N \le 20$).

Следующие $N$ строк — по одному целому числу (от $-1000$ до $1000$).

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

Две строки: исходный список и отсортированный по возрастанию, числа через пробел.

Алгоритмы обработки Использование сортировки Одномерные массивы

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

Сортировка словаря по ключам#92136

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

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

Первая строка — целое число $N$ ($1 \le N \le 10$).

Следующие $N$ строк — имя и оценка через пробел. Имена уникальны, состоят из русских букв, начинаются с заглавной.

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

$N$ строк в формате Имя — оценка, отсортированные по имени (алфавитный порядок).

Алгоритмы обработки Использование сортировки Словари

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

Why Did the Cow Cross the Road III#90425

Фермер Джон на старости лет стал параноиком. Он построил огромную изгородь вокруг фермы для защиты своих коров. Коровам такая идея не понравилась.

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

Для каждой из $N$ коров, посещающих ферму, вам сообщается время, когда она прибывает к воротам и количество времени, которое её требуется для ответов на вопросы. В каждый момент времени только одна корова опрашивается, поэтому, если много коров прибывает примерно в одно и то же время, они должны ждать своей очереди отвечать на вопросы. Например, если корова прибыла во время 5 и отвечает на вопросы 7 единиц времени, то другая корова, прибывшая во время 8 должна подождать до времени 12, что начать отвечать на вопросы.

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

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

Первая строка ввода содержит $N$, положительное целое число, не более 100. Каждая из последующих $N$ строк описывает одну корову, задавая время прибытия и время, которое требуется ей для ответов на вопросы. Каждое из этих чисел - положительное целое число не более 1,000,000.

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

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

Жадный алгоритм Задачи на моделирование Использование сортировки

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

Cow Dance Show#90399

После нескольких месяцев репетиций, коровы готовы дать ежегодное танцевальное представление - балет "Cowpelia".

Остался непрояснённым только размер сцены. Сцена размера $K$ может выдержать $K$ коров, танцующих одновременно. $N$ коров в стаде ($1 \leq N \leq 10,000$) пронумерованы последовательно $1 \ldots N$ в порядке, в котором они должны появиться на сцене во время танца. Каждая корова $i$ планирует танцевать определённое время $d(i)$. Изначально коровы $1 \ldots K$ появляются на сцене и начинают танцевать. Когда первая из этих коров завершит свой танец, она покидает сцену и корова $K+1$ немедленно начинает танцевать и т.д. Поэтому всегда $K$ коров танцуют, за исключением последнего отрезка шоу, когда коровы уходят, но не добавляются. Шоу завершается, когда последняя корова завершит свой танец в момент времени $T$.

Понятно, что чем больше значение $K$, тем меньше время $T$. Поскольку шоу не может длится очень долго, вам на вводе даётся верхняя граница $T_{max}$, указывающая максимально возможное значение величины $T$. Ваша задача - определить минимально возможное подходящее значение $K$.

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

Первая строка ввода содержит $N$ и $T_{max}$, где $T_{max}$ - целое число, не более 1 000 000.

Следующие $N$ строк задают длительности танцев $d(1) \ldots d(N)$ для коров $1 \ldots N$. Каждое из $d(i)$ - целое число в интервале $1 \ldots 100,000$.

Гарантируется, что если $K=N$, шоу закончится вовремя.

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

Выведите наименьшее возможное значение $K$ такое, что танцевальное шоу закончится не более чем через $T_{max}$ единиц времени.

Бинарный поиск по ответу Жадный алгоритм Очередь

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

Angry Cows#90387

Беси создала новую игру. Игрок стреляет коровами на одномерную сцену, состоящую из множества стогов сена расположенных в различных точках на числовой прямой. Каждая корова приземляется с силой достаточной, чтобы разрушить ближайшие к точке приземления стоги. Цель - использовать множество коров так, чтобы разрушить все стоги сена.

Имеется $N$ стогов сена расположенных в целочисленных позициях $x_1, x_2, \ldots, x_N$ на числовой прямой. Если корова приземляется с энергией $R$ в позиции $x$, это вызывает взрыв "радиуса $R$", разрушающий все стоги сена в диапазоне $x-R \ldots x+R$.

Всего имеется $K$ коров для выстрелов, каждая с одной и той же энергией $R$. Определите минимальную целую величину $R$ такую, что возможно используя эти $K$ коров разрушить все стоги сена на сцене.

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

Первая строка ввода содержит $N$ ($1 \leq N \leq 50,000$) и $K$ ($1 \leq K \leq 10$). Каждая из оставшихся $N$ строк содержит целые числа $x_1 \ldots x_N$ (каждое в интервале $0 \ldots 1,000,000,000$).

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

Выведите минимальную энергию $R$, с которой должна приземлиться каждая корова, для того чтобы разрушить все стоги сена.

Бинарный поиск по ответу Жадный алгоритм Задачи на моделирование

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

High Card Wins#90349

Корова Беси - фанат карточных игр. Однако у неё нет достойных противников. Все они играют в полностью предсказуемой манере. Однако надо ещё придумать, как выиграть у них.

Беси и Эльза играют в простую карточную игру, в которой имеется колода из $2N$ карт, последовательно пронумерованных $1 \ldots 2N$. Они делят её поровну - $N$ карт Беси и $N$ карт Эльзе. Затем они играют $N$ раундов, в каждом из которых Беси и Эльза выкладывают по одной карте, и тот, у кого карта больше, зарабатывает очко.

Беси может предсказать порядок, в котором будет выкладывать карты Эльза. Определите максимальное количество очков, которое может выиграть Беси.

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

Первая строка ввода содержит значение N ($1 \leq N \leq 50,000$).

Следующие N строк содержат карты, которыми будет играть в каждом из последующих раундов игры. Заметим, что из этой информации легко определить карты, которые на руках у Беси.

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

Выведите в одной строке максимальное количество очков, которое может заработать Беси.

Жадный алгоритм Задачи на моделирование Использование сортировки

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

Grass Segments#90276

Беси посадила траву на положительной вещественной прямой. У неё есть $N$ ($2\le N\le 2\cdot 10^5$) различных сортов травы. И она посадит траву $i$-го сорта на интервале $[\ell_i, r_i]$ ($0 < \ell_i < r_i \leq 10^9$).

Известно, что сорт $i$ растёт лучше, если есть некоторый сорт $j$ ($j\neq i$) такой, что сорт $j$ и сорт $i$ перекрываются на длину не менее $k_i$ ($0 < k_i \leq r_i - \ell_i$). Беси хочет для каждого сорта $i$ вычислить количество таких of $j\neq i$, что сорты $j$ и $i$ перекрываются на длину не менее $k_i$.

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

Первая строка содержит число $N$.

Каждая из последующих $N$ строк содержит три разделённых одиночными пробелами целых числа $\ell_i$, $r_i$, $k_i$.

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

Ответы для всех сортов на отдельных строках.

SCORING:

Тесты 4-5: $N \leq 5000$
Тесты 6-11: $k$ одинаковое для всех интервалов
Тесты 12-20: Нет дополнительных ограничений..

В дополнение, в тестах 5, 7, ..., 19, $r_i \leq 2N$ for all $i$.

Автор: Benjamin Qi

Отрезки Префиксные суммы(минимумы, ...)Сортировка событий

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

Cowmpetency#90270

Фермер Джон нанимает нового вожака стада для своих коров. Для этого он интервьюирует $N$ ($2 \leq N \leq 10^5$) коров на эту позицию. После интервью $i$-го кандидата он назначает целое число "уровень компетенции" $c_i$ от $1$ дo $C$ включительно ($1 \leq C \leq 10^9$).

Поскольку ФД интервьюировал много коров, он не помнит все $c_i$. Однако он помнит $Q$ ($1 \leq Q < N$) пар чисел $(a_j, h_j)$ где корова $h_j$ компетенция которой была строго больше, чем уровень компетенции коров от $1$ до $a_j$ ($1 \leq a_j < h_j \leq N$).

ФД говорит Вам последовательность $c_1, \dots, c_N$ (где $c_i = 0$ означает, что он забыл уровень компетенции коровы $i$, и $Q$ пар $(a_j, h_j)$. Помогите ему определить лексикографически минимальную последовательность уровней компетенции, соответствующую этой информации или указать, что такой последовательности не существует. Последовательность чисел называется лексикографически меньше другой последовательности если в ней меньшее число не первой позиции, где эти последовательности различаются.

Каждый ввод содержит $T$ $(1 \leq T \leq 20)$ независимых подтестов. Гарантируется, что сумма $N$ по всем подтестам не превысит $3 \cdot 10^5$.

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

Первая строка содержит $T$, количество независимых подтестов. Каждый подтест описывается так:

Первая строка содержит $N$, $Q$, $C$.
Следующая строка содержит c₁, \dots, c_N(0 \leq c_i \leq C)$.
Каждая из последующих $Q$ строк содержит пару $(a_j, h_j)$. Гарантируется что все $a_j$ в текущем подтесте различны.

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

Для каждого подтеста выведите одну строку содержащую лексикографически минимальную последовательность уровней компетенции, соответствующую информации, которую помнит ФД, или $-1$, если такой последовательности не существует.

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

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

Stamp Grid#90200

Штамп-живопись это раскрашивание чёрным и белым цветом холста размером $N \times N$ ячеек, где определённые ячейки закрашиваются, а другие - нет. Этот холст может быть представлен массивом символов $N\times N$ ($1\le N\le 20$). The $i$-ый вход $j$-ой колонки массива равен символу '*', если холст содержит чернила в этой ячейке и символ '.' в противном случае.

У Беси есть план рисунка, а Фермер Джон дал ей штамп размером $K\times K$ ($1\le K\le N$) который она может использовать для закраски холста размером $N \times N$. Беси может поворачивать штамп на $90^{\circ}$ по часовой стрелке и применять его для закраски холста в любом месте, если штамп помещается целиком на холсте. Формально, Беси выбирает такие целые числа $i,j$, что $i \in [1,N-K+1]$ и $j \in [1, N-K+1]$; и затем для каждого $(i',j')$ такого, что $1 \le i', j' \le K$, ячейка холста $(i+i'-1, j+j'-1)$ закрашивается в чёрный цвет, если в штампе было чернило в позиции $(i', j')$. Беси может поворачивать свой штамп в любой момент между закрашиваниями. Если ячейку закрасили она остаётся закрашенной навсегда.

ФД интересно может ли Беси создать свой рисунок, используя его штамп. Для каждого из $T$ ($1 \le T \le 100$) подтестов помогите ФД получить ответ.

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

Первая строка ввода содержит $T$ - количество подтестов.

Каждый подтест начинается с целого числа $N$, за которым следуют $N$ строк, состоящих их символов '*' и '.', представляющих рисунок, который Беси хочет нарисовать. Следующая строка содержит число $K$, за которым следует $K$ строк, каждая из которых содержит символы '*' и '.', представляющих штамп ФД.

Последовательные подтесты разделены пустыми строками.

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

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

Задача на реализацию Задачи на моделирование Перебор

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

Train Scheduling#90195

**Замечание: Ограничение по памяти для этой задачи 512MB, в два раза больше значения по умолчанию.**

Беси приняли на новую работу - диспетчером поездов. Имеется две железнодорожные станции $A$ и $B$. В связи с ограничением бюджета, эти станции соединены только одной дорогой. Если поезд отправляется от одной станции в момент времени $t$, тогда он прибудет на другую станцию в момент времени $t+T$ ($1\le T\le 10^{12}$).

Имеется $N$ ($1\le N\le 5000$) поездов для которых нужно установить время отправки. $i$-ый поезд должен покинуть станцию $s_i$ в момент времени $t_i или позже ($s_i\in \{A, B\}, 0\le t_i\le 10^{12}$). Запрещено иметь поезда, которые движутся в противоположных направлениях в один и тот же момент времени (поскольку они столкнутся). Однако разрешено иметь множество поездов, которые еду в одном направлении в одно и то же время (предполагаем, что поезда имеют пренебрежимо малые размеры)

Помогите Беси спланрировать времена отправления так, чтобы не было столкновений, а общая задержка была минимальной. Если поезд спланирован на убытие в момент времени $a_i\ge t_i$, общая задержка определяется как $\sum_{i=1}^N(a_i-t_i)$.

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

Первая строка содержит $N$ и $T$.

Затем следуют $N$ строк, где i-ая строка содержит станции $s_i$ и время $t_i$, соответствующие $i$-ому поезду.

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

Минимально возможная общая задержка всех корректных планирований.

Жадный алгоритм Задачи на моделирование Теория расписаний

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

Farmer John Actually Farms#90189

Фермер Джон вырастил $N$ ($1 \leq N \leq 2\cdot 10^5$) аспарагусов на своей ферме. Однако некоторые из этих растений имеют генетические отличия, поэтому некоторые растения растут быстрее чем другие. Изначальная высота $i$-го растения равна $h_i$ дюймов и после каждого дня $i$-ое растение вырастает на $a_i$ дюймов.

ФД любит некоторые растения больше чем другие, и он хочет, чтобы некоторые растения были выше чем другие. Он дал Вам массив различных целых чисел $t_1,\dots,t_N$, содержащих все целые числа от $0$ до $N-1$ и хочет, чтобы $i$-ое растение имело ровно $t_i$ растений, которые выше этого. Определите минимальное количество дней, чтобы требование ФД было удовлетворено или укажите, что это невозможно.

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

Первая строка состоит из целого числа $T$, обозначающего количество независимых тестов $(1 \leq T \leq 10)$.

Первая строка каждого теста состоит из целого числа $N$.

Вторая строка состоит из $N$ целых чисел $h_i$ $(1 \leq h_i \leq 10^9)$, обозначающих изначальную высоту $i$-го растения в дюймах.

Третья строка состоит из $N$ целых чисел $a_i$ $(1 \leq a_i \leq 10^9)$, обозначающих количество дюймов, на которые $i$-ое растение вырастает каждый день.

Четвёртая строка содержит $N$ различных целых чисел $t_i$, обозначающих массив, который ФД даст Вам.

Гарантируется, что сумма всех $N$ по всем тестам не превысит $2\cdot 10^5$.

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

Выведите $T$ строк, ответ на каждый тест на отдельной строке. Если невозможно, выведите -1.

Заметим, что тесты этой задачи могут потребовать использования 64-битного целого типа (например, "long long" в C/C++).

Вывод формулы Жадный алгоритм Задачи на моделирование

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

Counting Liars#90175

Корова Беси прячется где-то на числовой прямой. Каждая из $N$ ($1\le N\le 1000$) других коров Фермера Джона имеет информацию, которой она делится с ФД: $i$-ая корова говорит, что Беси прячется в некоторой точке меньше либо равной to $p_i$, или больше либо равной $p_i$, ($0\le p_i\le 10^9$).

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

ФОРМАТ ВВОДА (С КЛАВИАТУРЫ / stdin):

Первая строка содержит $N$.

Каждая из следующих $N$ строк содержит символ L или G, за которым следует целое число $p_i$. L означает, что $i$-ая корова говорит, что Беси скрывается в позиции меньше либо равной $p_i$, а G означает, что $i$-ая корова говорит, что Беси скрывается в позиции больше либо равной $p_i$

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

Минимальное количество коров, которые солгали.

Жадный алгоритм Задачи на моделирование Префиксные суммы(минимумы, ...)

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