Информатика

15 732 задачивместе с подтемами
Число у задачи — рейтинг сложности, слово рядом — насколько она трудна по сравнению с другими задачами такого же типа. Шкалы задач с ответом и задач с кодом между собой не сравниваются. Рядом — счётчики попыток: ✓ успешные, ✗ неуспешные.
РейтингЛюбойдо 800800–11991200–15991600+Без рейтинга
СначалаПодходящиеНовыеПопулярныеПростыеСложные
Миссия Серенити#29476
Экипаж Серенити межпланетного корабля класса Светлячок занимается доставкой грузов на различные планеты звездной системы. На корабле имеется секретный грузовой отсек, состоящий из N × M ячеек. Каждая ячейка грузового отсека имеет предельный объем, который она может вместить. Невозможно в ячейку вместить груз объемом больше, чем предельный объем ячейки. В одну ячейку можно поместить только ровно один груз. 
 
 Капитан Серенити Малькольм Рейнольдс продумывает размещение грузов по ячейкам. Помогите ему определить, какое максимальное количество грузов удастся доставить капитану.
 
Входные данные
В первой строке даны числа N и M (\(1 \leq N, M \leq 40\)). В каждой из последующих N строк содержится по M чисел, обозначающих предельный объем соответствующей ячейки. В (N+2)-ой строке находится число K (\(1 \leq K \leq 2000\)) – количество грузов. В (N+3)-ей строке содержатся K чисел, i-ое из которых – объем i-ого груза. Все объемы – натуральные числа, не превышающие 109.

Выходные данные
Требуется вывести одно число – максимально возможное количество грузов, которое удастся доставить.
 
Пример
№ Входные данные Выходные данные
1
3 2
5 10
7 5
5 5
6
9 5 3 5 12 10
 4
Квадратичные сортировки
✓ 734✗ 2 054800средняяВойти и решать
Пузырьковая сортировка: количество обменов#29475
Определите, сколько обменов сделает алгоритм пузырьковой сортировки по возрастанию для данного массива.
 
Входные данные
На первой строке дано число N (\(1 <= N <= 1000\)) – количество элементов в массиве. На второй строке – сам массив. Гарантируется, что все элементы массива различны и не превышают по модулю 109.
 
Выходные данные
Выведите одно число – количество обменов пузырьковой сортировки.
 
Примеры
№ Входные данные Выходные данные
1
5
1 2 3 4 5 
 0
2
5
5 4 3 2 1
 10
Сортировка "пузырьком"
✓ 2 539✗ 2 085200лёгкаяВойти и решать
Пузырьковая сортировка#29474
Требуется отсортировать массив по неубыванию методом "пузырька".
 
Входные данные
В первой строке вводится одно натуральное число N, не превосходящее 1000 – размер массива. Во второй строке задаются N чисел – элементы массива (целые числа, не превосходящие по модулю 1000).
 
Выходные данные
Вывести получившийся массив.
 
Примеры
№ Входные данные Выходные данные
1
5
5 4 3 2 1
 1 2 3 4 5
Квадратичные сортировки
✓ 2 890✗ 5 442200лёгкаяВойти и решать
Клавиатура#29472
Всем известно, что со временем клавиатура изнашивается, и клавиши на ней начинают залипать. Конечно, некоторое время такую клавиатуру еще можно использовать, но для нажатий клавиш приходиться использовать большую силу.
 
При изготовлении клавиатуры изначально для каждой клавиши задается количество нажатий, которое она должна выдерживать. Если знать эти величины для используемой клавиатуры, то для определенной последовательности нажатых клавиш можно определить, какие клавиши в процессе их использования сломаются, а какие – нет.
 
Требуется написать программу, определяющую, какие клавиши сломаются в процессе заданного варианта эксплуатации клавиатуры.
 
Входные данные
Первая строка входного файла содержит целое число n (1 ≤ n ≤ 100) – количество клавиш на клавиатуре. Вторая строка содержит n целых чисел – с1, с2, … , сn, где сi (1 ≤ сi ≤ 100000) – количество нажатий, выдерживаемых i-ой клавишей. Третья строка содержит целое число k (1 ≤ k ≤ 100000) – общее количество нажатий клавиш, и последняя строка содержит k целых чисел pj (1 ≤ pj ≤ n) – последовательность нажатых клавиш.
 
Выходные данные
В выходной файл необходимо вывести n строк, содержащих информацию об исправности клавиш. Если i-ая клавиша сломалась, то i-ая строка должна содержать слово “yes” (без кавычек), если же клавиша работоспособна – слово “no”.
 
 
Ввод Вывод
5
1 50 3 4 3
16
1 2 3 4 5 1 3 3 4 5 5 5 5 5 4 5
yes
no
no
no
yes

Личные олимпиады, Всероссийская олимпиада школьников, Региональный этап, 2009, 2 день, Задача A
Сортировка подсчетом
✓ 580✗ 442500лёгкаяВойти и решать
Форум#29471
Клуб Юных Хакеров организовал на своем сайте форум. Форум имеет следующую структуру: каждое сообщение либо начинает новую тему, либо является ответом на какое-либо предыдущее сообщение и принадлежит той же теме. 
 
После нескольких месяцев использования своего форума юных хакеров заинтересовал вопрос - какая тема на их форуме наиболее популярна. Помогите им выяснить это.
 
Входные данные
В первой строке вводится целое число N - количество сообщений в форуме (1 <= N <= 1000). Следующие строки содержат описание сообщений в хронологическом порядке. 
 
Описание сообщения, которое представляет собой начало новой темы, состоит из трех строк. Первая строка содержит число 0. Вторая строка содержит название темы. Длина названия не превышает 30 символов. Третья строка содержит текст сообщения. 
 
Описание сообщения, которое является ответом на другое сообщение, состоит из двух строк. Первая строка содержит целое число - номер сообщения, ответом на которое оно является. Сообщения нумеруются, начиная с единицы. Ответ всегда появляется позже, чем сообщение, ответом на которое он является. Вторая строка содержит текст сообщения. 
 
Длина каждого из сообщений не превышает 100 символов.
 
Выходные данные
Выведите название темы, к которой относится наибольшее количество сообщений. Если таких тем несколько, то выведите первую в хронологическом порядке
 
Ввод Вывод
2
0
topic 1
body of message 1
0
topic 2
body of message 2
 topic 1

 
Использование сортировки
✓ 191✗ 573900средняяВойти и решать
Разброс#29470
Дано N целых чисел, которые требуется отсортировать в порядке неубывания. В связи с нормами СЭС среди чисел не будет двух, разница между которыми превышает 107.
 
Входные данные
Первая строка входного файла содержит целое число N. (1 <= N <= 100000), вторая строка – N целых чисел, не превышающих по модулю 2*109. Никакие два не различаются более, чем на 107.
 
Выходные данные
Выведите данные числа в порядке неубывания.
 
Ввод Вывод
1
863961129 
 863961129 
5
1866455200 1866455199 1866455198 1866455197 1866455196 
 1866455196 1866455197 1866455198 1866455199 1866455200 
Сортировка подсчетом
✓ 484✗ 1 021600лёгкаяВойти и решать
Носки#29468
Имеется стол длины L. На столе разложено N носков так, что никакой носок не вылезает за границы стола. Далее имеется умный мальчик Васёк, который хочет (сугубо в корыстных целях) замерить толщину покрытия стола носками в M точках.
 
Формат входных данных
Во входном файле даны сначала L, N, M (1 ≤ L ≤ 10000, 1 ≤ N ≤ 10000, 1 ≤ M ≤ 100000). Далее идут N пар чисел l ≤ r от 1 до L – левые и правые концы носков. Затем идут M чисел от 1 до L интересующие Васька точки.
 
Формат выходных данных
Выведите M чисел – толщину носкового покрытия в каждой точке.
Сортировка подсчетом
✓ 616✗ 858500лёгкаяВойти и решать
Сортировка подсчетом#29467
Реализуйте алгоритм сортировки подсчетом для произвольных чисел, по модулю не превосходящих 10000.
 
Входные данные
На вход программе сначала подается значение n <= 100000 – количество элементов массива. В следующей строке расположены сами элементы – целые числа, по модулю не превосходящие 10000.
 
Выходные данные
Выведите на экран отсортированный по неубыванию массив.
 
Примеры
№ Входные данные Выходные данные
1
5
1 3 4 2 5
 1 2 3 4 5
Сортировка подсчетом
✓ 1 265✗ 4 097500лёгкаяВойти и решать
Количество способов топологической сортировки#29453
Дан связный ациклический ориентированный граф. Каждая вершина данного графа кроме листьев имеет по 2 сына.
Найдите количество способов топологически отсортировать, зная только количество вершин.
 
Входные данные
Входная строка содержит одно натуральное число n - кол-во вершин (n <= 15).

Выходные данные  
Выведите ответ на задачу.
 
Примеры
№ Входные данные Выходные данные
1 7 48
Топологическая сортировка
✓ 77✗ 293800средняяВойти и решать
Лексикографически минимальная топологическая сортировка#29452
Дан связный ациклический ориентированный граф. Найдите его лексикографически минимальную топологическую сортировку.
 
Входные данные
В первой строке вводится количество вершин n (1 <= n <= 10000). Во второй строке водится n чисел ai (0 <= ai <= n, ai != i). Значение ai - предок вершины с номером i (вершины нумеруются с 1). Если ai = 0, то вершина i является корнем и не имеет предков, гарантируется, что таких вершин ровно 1.
 
Выходные данные
Решение должно вывести n чисел - лексикографически минимальную топологическую сортировку.
 
Примеры
№ Входные данные Выходные данные
1
4
2 0 1 2
 2 1 3 4
Топологическая сортировка
✓ 40✗ 136900средняяВойти и решать
Расписание для 9И#29451
В августе Владлена Александровна решила составить расписание для 9 «И» класса. Она считает, что уроков в один день должно быть N (2<=N<=8). От учителей она получила M (1<=N) запросов. Так как Владлена Александровна учитель географии, то с компьютером опыт работы у нее не такой как у вас, она просит вас о помощи, решите эту «невыполнимую» задачу, соблюдая запросы учителей.

Входные данные:  В первой строке входных данных содержится число N – кол-во уроков и число M – количество последовательных пар уроков наверное.
В следующих M строках задаются 2 слова, которые обозначают названия предметов.
Известно что, граф не может зациклиться и предметы не могут быть в расписании 2 раза
Слова, которые можно вводить: PE,Math, Russian, Biology,Geometry, Literature, Science, Geography
 
Выходные данные: Задача — выстроить предметы в подходящем для всех пар порядке.
 
Ввод Вывод
3 2
PE Math
Math Literature		 PE
Math
Literature

(c) Бганцова А., 2018 г.
Топологическая сортировка
✓ 14✗ 19700средняяВойти и решать
Спасти новобранцев#29450
Группа солдат-новобранцев прибыла в армейскую часть N777. После знакомства с прапорщиком стало очевидно, что от работ на кухне по очистке картофеля спасти солдат может только чудо. 
 
Прапорщик, будучи не в состоянии запомнить фамилии, пронумеровал новобранцев от 1 до N. После этого он велел им построиться по росту (начиная с самого высокого). С этой несложной задачей могут справиться даже совсем необученные новобранцы, да вот беда, прапорщик уверил себя, что знает про некоторых солдат, кто из них кого выше, и это далеко не всегда соответствует истине. 
 
После трех дней обучения новобранцам удалось выяснить, что знает (а точнее, думает, что знает) прапорщик. Помогите им, используя эти знания, построиться так, чтобы товарищ прапорщик остался доволен. 
 
Входные данные 
Сначала на вход программы поступают числа N и M (1 < N <= 100, 1 <= M <= 5000) – количество солдат в роте и количество пар солдат, про которых прапорщик знает, кто из них выше. Далее идут эти пары чисел A и B по одной на строке (1 <= A,B <= N), что означает, что, по мнению прапорщика, солдат A выше, чем B. Не гарантируется, что все пары чисел во входных данных различны. 
 
Выходные данные 
В первой строке выведите "Yes" (если можно построиться так, чтобы прапорщик остался доволен) или "No" (если нет). После ответа "Yes" на следующей строке выведите N чисел, разделенных пробелами, - одно из возможных построений. 
Примеры
№ Входные данные Выходные данные
1
4 5 
1 2 
2 3 
3 4 
1 4 
4 1
 No

(c) Пасынков С., 2018 г.
Топологическая сортировка
✓ 29✗ 25500лёгкаяВойти и решать
Дороги королевства#29449
В одном королевстве n городов и m дорог. У каждого города есть своё название, состоящее из строчных латинских букв. Но королю не нравится, что есть дороги, ведущие из города с названием, являющимся лексикографически меньшим названия конечного. Он захотел это исправить, поменяв города, к которым относятся те или иные названия. Сам он, конечно, не справится. Помогите ему в этом! 
 
Формат файла входных данных: 
Первая строка содержит два целых числа n и m (2 <= n <= 1000; 1 <= M <= 10000) - количество городов и дорог в королевстве соответственно. 
 
Вторая строка содержит n строк, описывающих города. Описание задаётся строкой из строчных латинских букв - названия города. 
 
Далее в m строках перечислены дороги. Каждая дорога задаётся парой чисел - номерами начального и конечного городов соответственно. Дороги односторонние. 
 
Формат файла выходных данных: 
Вывести n чисел, каждое из которых обозначает номер названия, соответствующего i-ому городу. Если решения не существует, вывести -1.
 
Ввод Вывод
4 4 
aaa bacc cqe de 
1 4 
4 2 
4 3 
3 2
 1 4 3 2
3 3 
fi bru a 
1 2 
2 3 
3 1
 -1
(с) Филимонов И.
Топологическая сортировка
✓ 19✗ 8600лёгкаяВойти и решать
OLD or YOUNG#29447
Известен возраст группы людей в списке. Какой человек указан в списке раньше: самый старый или самый молодой? Если самых старых (молодых) несколько, то учитывайте того, кто встретился раньше.

Входные данные
В первой строке вводится число N - количество людей в списке (1<N<=100). Во второй строке вводятся N чисел - возраст людей в списке (каждое число в диапазоне от 0 до 120).

Выходные данные
Вывести на экран слово OLD,  если самый старый человек встречается в списке раньше, иначе слово YOUNG, если раньше встречается самый молодой.
 
Примеры
№ Входные данные Выходные данные
1
10
67 99 43 95 32 107 65 104 1 31 
 OLD
2
10
1 99 43 95 32 107 65 104 1 31 
 YOUNG
Одномерные массивы
✓ 200✗ 342500лёгкаяВойти и решать
Первый самый младший#29445
В массиве хранится информация о годе рождения каждого из N человек. Определить порядковый номер первого самого младшего по возрасту человека. 

Входные данные
В первой строке задается число N - число человек (0<N<=50). Во второй строке задаются года рождения N человек (N чисел, каждое число положительное, не больше 105).

Выходные данные
Вывести номер первого самого младшего человека.
 
Примеры
№ Входные данные Выходные данные
1 5
1904 1903 1905 1905 1903		 3
Одномерные массивы
✓ 116✗ 427500лёгкаяВойти и решать
Последний самый старший#29444
В массиве хранится информация о годе рождения каждого из N человек. Определить порядковый номер последнего самого старшего по возрасту человека. 

Входные данные
В первой строке задается число N - число человек (0<N<=50). Во второй строке задаются года рождения N человек (N чисел, каждое число положительное, не больше 105).

Выходные данные
Вывести номер последнего самого старшего человека.
 
Примеры
№ Входные данные Выходные данные
1 5
1904 1903 1905 1905 1903		 5
Одномерные массивы
✓ 161✗ 345500лёгкаяВойти и решать
Первый самый старший#29443
В массиве хранится информация о годе рождения каждого из N человек. Определить порядковый номер первого самого старшего по возрасту человека. 

Входные данные
В первой строке задается число N - число человек (0<N<=50). Во второй строке задаются года рождения N человек (N чисел, каждое число положительное, не больше 105).

Выходные данные
Вывести номер первого самого старшего человека.
 
Примеры
№ Входные данные Выходные данные
1 5
1904 1903 1905 1905 1903		 2
Одномерные массивы
✓ 101✗ 351500лёгкаяВойти и решать
Последний с минимальной премией#29442
В массиве хранится информация о годовой премии у N сотрудников фирмы. Определить порядковый номер последнего сотрудника с самой низкой годовой премией.

Входные данные
В первой строке задается число N - количество сотрудников фирмы (0<N<=50). Во второй строке задаются значения премий N сотрудников фирмы (N чисел, каждое число положительное, не больше 105).

Выходные данные
Вывести номер последнего сотрудника с минимальной премией.
 
Примеры
№ Входные данные Выходные данные
1 5
4 3 5 3 5		 4
Одномерные массивы
✓ 197✗ 450400лёгкаяВойти и решать
Первый с минимальной премией#29441
В массиве хранится информация о годовой премии у N сотрудников фирмы. Определить порядковый номер первого сотрудника с самой низкой годовой премией.

Входные данные
В первой строке задается число N - количество сотрудников фирмы (0<N<=50). Во второй строке задаются значения премий N сотрудников фирмы (N чисел, каждое число положительное, не больше 105).

Выходные данные
Вывести номер первого сотрудника с минимальной премией.
 
Примеры
№ Входные данные Выходные данные
1 5
4 3 5 5 3		 2
Одномерные массивы
✓ 123✗ 316400лёгкаяВойти и решать
Последний самый быстрый#29440
В массиве хранится информацию о максимальной скорости каждой из N марок легковых автомобилей. Определить порядковый номер последнего встретившегося автомобиля с самой высокой скоростью.

Входные данные
В первой строке задается число N - количество авомобилей (0<N<=50). Во второй строке задаются значения скоростей N автомобилей (N чисел, каждое число положительное, не больше 105).

Выходные данные
Вывести номер последнего встретившегося автомобиля с самой высокой скоростью.
 
Примеры
№ Входные данные Выходные данные
1 5
4 3 5 5 3		 4
Одномерные массивы
✓ 84✗ 188500лёгкаяВойти и решать
Поделиться
Класснуть