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

Очень легкая задача#30703

Сегодня утром жюри решило добавить в вариант олимпиады еще одну, Очень Легкую Задачу. Ответственный секретарь Оргкомитета напечатал ее условие в одном экземпляре, и теперь ему нужно до начала олимпиады успеть сделать еще N копий. В его распоряжении имеются два ксерокса, один из которых копирует лист за х секунд, а другой – за y.
Разрешается использовать как один ксерокс, так и оба одновременно. Можно копировать не только с оригинала, но и с копии. Помогите ему выяснить, какое минимальное время для этого потребуется.

Входные данные: на входе задается три натуральных числа N, x и y, разделенные пробелом (\(1 <= N <= 2 \cdot 10^8,\ 1 <= x, y <= 10\)).

Выходные данные: выведите одно число – минимальное время в секундах, необходимое для получения N копий.

Примеры

№	Входные данные	Выходные данные
1	4 1 1	3
2	5 1 2	4

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

✓ 1 167✗ 3 112500лёгкаяВойти и решать

Сложная сортировка массива структур#30690

Дан список людей состоящих из фамилии и имени. Напишите программу, которая отсортирует список по фамилиям в возрастающем лексикографическом порядке. Если фамилии совпадают, то отсортировать по имени.

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

Сначала задано число N - количество людей в списке (1<= N <= 100). Далее через пробел записаны N фамилий и мен.

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

Необходимо вывести массив отсортированный по фамильно в возрастающем лексикографическом порядке, при совпадении фамили, сортировать по имени.

Примеры

№	Входные данные	Выходные данные
1	3 Sidorov Petr Ivanov Ivan Ivanov Anton	Ivanov Anton Ivanov Ivan Sidorov Petr

Сортировка записей

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

Списки: алфавитно-частотный словарь#29633

Дан текст, состоящий из нескольких строк. Текст заканчивается строкой, содержащей единственное слово "END!". Слово "END!" не является содержимым текста, а служит только признаком окончания.

Постройте для данного текста алфавитно-частотный словарь отсортированный по частоте слов: список слов, справа от каждого слова должно быть указано, сколько раз оно встречается в исходном файле. Слова должны идти в порядке убывания. Если количество слов одинаково, сортировка идет по словам в лексикографическом порядке.

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

Пример

№	Входные данные	Выходные данные
1	Duis aute irure dolor in reprehenderit in voluptate. Velit esse cillum dolore eu fugiat nulla pariatur. END!	in 2 aute 1 cillum 1 dolor 1 dolore 1 duis 1 esse 1 eu 1 fugiat 1 irure 1 nulla 1 pariatur 1 reprehenderit 1 velit 1 voluptate 1

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

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

Разложение на простые - 1#29549

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

Входные данные
На вход падается число N (\(2 <= N <= 10^9\)).

Выходные данные
Выведите список простых множителей числа N в порядке неубывания, разделенных знаком «*».

Примеры

№	Входные данные	Выходные данные
1	5	5
2	30	235

Простые числа и разложение на множители

✓ 954✗ 1 847400лёгкаяВойти и решать

Разложение на простые - 2#29548

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

Входные данные
На входе дано число N (\(2 <= N <= 10^9\)).

Выходные данные
Вывести разложение N на простые множители.

Примеры

№	Входные данные	Выходные данные
1	2	2
2	1008	2^43^27

Простые числа и разложение на множители

✓ 627✗ 1 580500лёгкаяВойти и решать

Дремучий лес#29481

Чтобы помешать появлению СЭС в лагере, администрация ЛКШ перекопала единственную дорогу, соединяющую «Берендеевы поляны» с Судиславлем, теперь проехать по ней невозможно. Однако, трудности не остановили инспекцию, хотя для СЭС остается только одна возможность — дойти до лагеря пешком. Как известно, Судиславль находится в поле, а «Берендеевы поляны» — в лесу.

- Судиславль находится в точке с координатами (0, 1).

- «Берендеевы поляны» находятся в точке с координатами (1, 0).

- Граница между лесом и полем — горизонтальная прямая y=a, где a — некоторое число (0 ≤ a ≤ 1).

- Скорость передвижения СЭС по полю составляет V_p, скорость передвижения по лесу — V_f. Вдоль границы можно двигаться как по лесу, так и по полю.

Администрация ЛКШ хочет узнать, сколько времени у нее осталось для подготовки к визиту СЭС. Она попросила вас выяснить, в какой точке инспекция СЭС должна войти в лес, чтобы дойти до «Берендеевых полян» как можно быстрее.

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

В первой строке входного файла содержатся два положительных целых числа V_p и V_f (1≤ V_p, V_f ≤ 10⁵) . Во второй строке содержится единственное вещественное число — координата по оси Oy границы между лесом и полем a (0 ≤ a ≤ 1) .

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

В единственной строке выходного файла выведите вещественное число с точностью не менее 8 знаков после запятой — координата по оси Ox точки, в которой инспекция СЭС должна войти в лес.

Ввод	Вывод
5 3 0.4	0.783310604
5 5 0.5	0.500000000

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

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

Пузырьковая сортировка: количество обменов#29475

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

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

На первой строке дано число N (\(1 <= N <= 1000\)) – количество элементов в массиве. На второй строке – сам массив. Гарантируется, что все элементы массива различны и не превышают по модулю 10⁹.

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

Выведите одно число – количество обменов пузырьковой сортировки.

Примеры

№	Входные данные	Выходные данные
1	5 1 2 3 4 5	0
2	5 5 4 3 2 1	10

Сортировка "пузырьком"

✓ 2 540✗ 2 085200лёгкаяВойти и решать

Пузырьковая сортировка#29474

Требуется отсортировать массив по неубыванию методом "пузырька".

Входные данные
В первой строке вводится одно натуральное число N, не превосходящее 1000 – размер массива. Во второй строке задаются N чисел – элементы массива (целые числа, не превосходящие по модулю 1000).

Выходные данные
Вывести получившийся массив.

Примеры

№	Входные данные	Выходные данные
1	5 5 4 3 2 1	1 2 3 4 5

Квадратичные сортировки

✓ 2 891✗ 5 442200лёгкаяВойти и решать

Палиндром#29473

Палиндром - это строка, которая читается одинаково как справа налево, так и слева направо.

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

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

В первой строке входных данных содержится число N (1 <= N <= 100000). Во второй строке задается последовательность из N больших латинских букв (буквы записаны без пробелов).

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

В единственной строке выходных данных выдайте искомый палиндром.

Ввод	Вывод
3 AAB	ABA
6 QAZQAZ	AQZZQA
6 ABCDEF	A

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

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

Клавиатура#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лёгкаяВойти и решать

Разброс#29470

Дано N целых чисел, которые требуется отсортировать в порядке неубывания. В связи с нормами СЭС среди чисел не будет двух, разница между которыми превышает 10⁷.

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

Первая строка входного файла содержит целое число N. (1 <= N <= 100000), вторая строка – N целых чисел, не превышающих по модулю 2*10⁹. Никакие два не различаются более, чем на 10⁷.

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

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

Ввод	Вывод
1 863961129	863961129
5 1866455200 1866455199 1866455198 1866455197 1866455196	1866455196 1866455197 1866455198 1866455199 1866455200

Сортировка подсчетом

✓ 484✗ 1 021600лёгкаяВойти и решать

Анаграммы#29469

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

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

Даны два слова на отдельных строках. Слова состоят из строчных латинских букв и цифр. Длины слов не превышают 255.

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

Требуется вывести "YES" – если введенные слова являются анаграммами друг друга, "NO" – если нет.

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

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

Носки#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лёгкаяВойти и решать

Пересечение множеств#29466

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

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

В первой строке входного потока записано через пробел два целых числа N и М (1 ≤ N, М ≤ 300 000) — количество элементов первого и второго наборов, соответственно. В следующих двух строках записано сначала N чисел первого набора, а затем M чисел второго набора. Числа разделены пробелами. Каждое из этих чисел попадает в промежуток от 0 до 10⁵.

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

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

Входные данные	Выходные данные
11 6 2 4 6 8 10 12 10 8 6 4 2 3 6 9 12 15 18	6 12

Алгоритмы обработки Множества Пересечение множеств

✓ 736✗ 1 150500лёгкаяВойти и решать

Расписание для 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

Топологическая сортировка

✓ 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

Топологическая сортировка

✓ 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лёгкаяВойти и решать

Самый младший#29446

В некотором списке записана информация о годе рождения каждого из N человек. Определить наибольший порядковый номер самого младшего по возрасту человека (считая с 1).

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

Выходные данные
Выведите наибольший номер самого младшего человека.

Пример

№	Входные данные	Выходные данные
1	5 1904 1903 1905 1905 1903	4

Алгоритмы обработки Линейный поиск Одномерные массивы

✓ 5 316✗ 16 022300лёгкаяВойти и решать

Сокращение дроби#29423

Дана дробь \(a \over b\). Требуется ее сократить, то есть записать это же число в виде \(c \over d\), где c — целое число, d - натуральное число и d минимальное возможное.

Входные данные
Вводятся два целых числа a и b (\(-100<=a<=100,\ 0<b<=100\)).

Выходные данные
Выведите два числа c и d.

Примеры

№	Входные данные	Выходные данные
1	3 6	1 2
2	-2 5	-2 5

НОД и алгоритм Евклида

✓ 1 331✗ 3 701400лёгкаяВойти и решать