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

Защищенное соединение#30707

В свете недавних новостей о прослушке каналов связи, два непримиримых интернет-гиганта Урагании <<Laim.UR>> и <<Xenda>> решили подписать соглашение об установлении защищенного канала связи между дата-центрами друг друга. В Урагании \(n\) городов, но, к сожалению, ни в одном городе нет дата-центров обоих гигантов. Поэтому для формирования защищенного канала придется прокладывать междугородние линии связи.

Специалисты компаний определили \(m\) пар городов, которые можно соединить, проложив сегмент канала связи, и оценили стоимость создания такого сегмента для каждой из этих пар.

Результирующий канал может состоять из нескольких сегментов. Он должен начинаться в одном из городов, где находится дата-центр первой компании, может проходить через промежуточные города и должен заканчиваться в городе, где находится дата-центр второй компании.

Теперь необходимо определить минимальную стоимость защищенного канала, соединяющего два дата-центра компаний.

Формат входных данных
В первой строке находятся целые числа \(n\) и \(m\) (\(2 \le n \le 5\,000\), \(1 \le m \le 10^5\)) — количество городов и количество пар городов, которые можно соединить сегментом канала связи.

Во второй строке находятся \(n\) целых чисел \(a_i\) (\(0 \le a_i \le 2\)). Если \(a_i = 0\), то в \(i\)-м городе нет дата-центра ни одного из гигантов. Если \(a_i = 1\), то в \(i\)-м городе есть дата-центр <<Laim.UR>>, а если \(a_i = 2\), то в \(i\)-м городе находится дата-центр <<Xenda>>. Гарантируется, что среди этих чисел есть как минимум одна единица и одна двойка.

В каждой из следующих \(m\) строк находится по три целых числа — \(s_i\), \(t_i\) и \(c_i\), которые означают, что города \(s_i\) и \(t_i\) (\(1 \le s_i, t_i \le n\), \(s_i \ne t_i\)) можно соединить сегментом канала связи стоимостью \(c_i\) (\(1 \le c_i \le 10^5\)). Каждую пару городов можно соединить не более чем одним сегментом канала.

Формат выходных данных
Если соединить защищенным каналом связи два дата-центра разных интернет-гигантов возможно, то выведите в выходной файл три числа: \(x\), \(y\) и \(d\), означающие, что между городами \(x\) и \(y\) возможно провести канал связи суммарной стоимостью \(d\). В городе \(x\) должен находиться дата-центр <<Laim.UR>>, в городе \(y\) — дата-центр <<Xenda>>. Если существует несколько оптимальных ответов, выведите любой. Если провести искомый канал невозможно, выведите \(-1\).

В первом примере оптимально построить канал связи из двух сегментов: \(3-2\) и \(2-4\).

Алгоритм Дейкстры

✓ 68✗ 1621 000средняяВойти и решать

Очень легкая задача#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лёгкаяВойти и решать

Заправки-2#30702

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

В каждом городе бак бензина имеет разную стоимость. Вам требуется добраться из первого города в N-й, потратив как можно меньшее денег.

В каждом городе можно заправить бак, заправить бак и канистру или же перелить бензин из канистры в бак. Это позволяет экономить деньги, покупая бензин в тех городах, где он стоит дешевле, но канистры хватает только на одну заправку бака!

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

В первой строке вводится число N (1<=N<=100), в следующей строке идет N чисел, i-е из которых задает стоимость бензина в i-м городе (всё это целые числа из диапазона от 0 до 100). Затем идет число M – количество дорог в стране, далее идет описание самих дорог. Каждая дорога задается двумя числами – номерами городов, которые она соединяет. Все дороги двухсторонние (то есть по ним можно ездить как в одну, так и в другую сторону), между двумя городами всегда существует не более одной дороги, не существует дорог, ведущих из города в себя.

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

Требуется вывести одно число – суммарную стоимость маршрута или -1, если добраться невозможно.

Алгоритм Дейкстры

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

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

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

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

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

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

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

Примеры

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

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

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

Тихий дон №2#29640

Аксинья любит Григория, но она замужем за Степаном. Со своим мужем она несчастна, поэтому время, которое она проводит с ним можно характеризовать отрицательным показателем счастья Аксиньи (\(a_i < 0\)), а то время, которое она проводит с Григорием, - положительным показателем счастья (\(a_i > 0\)). Известно, что Аксинья проводит один день либо с мужем, либо с Григорием.

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

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

В первой строке подается 3 числа: N – кол-во дней, L и C (\(1 <= L, C <= N <= 1 000 000\)).

Во второй строке содержится N чисел a_i (\(1 <= |a_i| <= 1 000 000 000\)).

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

Требуется вывести ответ на задачу.

Примеры

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

"Два указателя"Префиксные суммы(минимумы, ...)

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

Списки: алфавитно-частотный словарь#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лёгкаяВойти и решать

Load Balancing#29545

Коровы Фермера Джона стоят в различных точках (x₁,y₁)…(x_n,y_n) его поля (1≤N≤100,000, все x_i и y_i - положительные нечётные целые числа, не превышающие 1,000,000. ФД хочет разделить своё поле изгородью бесконечной длины с севера на юг, описываемой уравнением x=a (a - чётное целое, так обеспечивается, что изгородь не пройдёт через позицию ни одной коровы). Также он хочет построить изгородь бесконечной длины с востока на запад, которая описывается уравнением y=b, где b - чётное целое. Эти две изгороди пересекаются в точке (a,b), и вместе делят поле на четыре региона.

ФД хочет выбрать a и b так, чтобы получить "сбалансированное" количество коров во всех регионах, т.е. чтобы не было региона, который содержит слишком много коров. Пусть M - максимальное количество коров в этих четырёх регионах, ФД хочет, чтобы M было как можно меньше. Помогите ФД определить это минимально возможное значение для M.

ФОРМАТ ВВОДА:

Первая строка ввода содержит одно целое число, N. Каждая из следующих n строк содержит местоположение одной коровы, указанное её координатами x и y.

ФОРМАТ ВЫВОДА:

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

Ввод	Вывод
7 7 3 5 5 7 13 3 1 11 7 5 3 9 1	2

Дерево отрезков, RSQ, RMQ Дерево Фенвика Структуры данных Тернарный поиск

✓ 3✗ 251 100средняяВойти и решать

Вложенный вложенный тернарный поиск: Космические спасатели#29495

В галактике находится n планет, на каждой из которых обитают множество различных живых существ. И каждое из них может оказаться в беде! Космические спасатели прекрасно знают об этом и всегда готовы помочь каждому, кому эта помощь действительно понадобится. Стоит только позвать.

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

Поскольку планеты достаточно удалены друг от друга, их можно считать точками в евклидовом трехмерном пространстве. Расстояние между точками (x_i, y_i, z_i) и (x_j, y_j, z_j) вычисляется по формуле:

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

Галактика в опасности! Спасите космических спасателей и укажите им искомую точку.

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

В первой строке входного файла содержится целое число n — количество планет (1 ≤ N ≤ 100). Каждая из последующих n строк содержит информация о планетах. i-я из этих строк содержит три целых числа xi, yi, zi — координаты i-й планеты ( - 10⁴ ≤ xi, yi, zi ≤ 10⁴, 1 ≤ i ≤ n). Никакие две планеты не совпадают.

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

В первой строке выходного файла следует вывести три вещественных числа через пробел x₀, y₀, z₀ — координаты будущей базы. Если существует несколько решений, то разрешается вывести любое. Ответ будет засчитан, если расстояние от данной точки до самой удаленной планеты будет отличаться от результата жюри не более чем на 10^-6 по абсолютному или относительному значению.

Ввод	Вывод
5 5 0 0 -5 0 0 0 3 4 4 -3 0 2 2 -2	0.000 0.000 0.000

Тернарный поиск

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

Вложенный тернарный поиск: футбольные ворота#29484

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

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

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

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

В единственной строке записаны целые числа a, b — длины палок (\(1 <= a, b <= 10 000\)). Известно, что суммарная длина палок строго меньше высоты берёзы.

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

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

Примеры

№	Входные данные	Выходные данные
1	2 2	4.828427125

Источник: Уральская региональная командная олимпиада по программированию 2011

Тернарный поиск

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

Дремучий лес#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средняяВойти и решать

Велогонка#29480

Велосипедисты, участвующие в шоссейной гонке, в некоторый момент времени, который называется начальным, оказались в точках, удалённых от места старта на x₁, x₂, ..., x_n метров (n – общее количество велосипедистов). Каждый велосипедист двигается со своей постоянной скоростью v₁, v₂, ..., vn метров в секунду. Все велосипедисты двигаются в одну и ту же сторону.

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

Требуется написать программу, которая по заданному количеству велосипедистов n, заданным начальным положениям велосипедистов x₁, x₂, ..., x_n и их скоростям v₁, v₂, ..., vn, вычислит момент времени t, в который расстояние l между лидирующим и замыкающим велосипедистом будет минимальным.

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

Первая строка входного файла содержит целое число n – количество велосипедистов.

В последующих n строках указаны по два целых числа: x_i – расстояние от старта до i-го велосипедиста в начальный момент времени (0 ≤ x_i ≤ 10⁷ ) и v_i – его скорость (0 ≤ v_i ≤ 10⁷ ).

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

В выходной файл необходимо вывести два вещественных числа: t – время в секундах, прошедшее от начального момента времени до момента, когда расстояние в метрах между лидером и замыкающим будет минимальным, l – искомое расстояние.

Числа t и l должны иметь абсолютную или относительную погрешность не более 10^–6, что означает следующее. Пусть выведенное число равно x, а в правильном ответе оно равно y. Ответ будет считаться правильным, если значение выражения |x – y| / max(1, |y| ) не превышает 10^–6.

Подзадачи и система оценки

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

Ввод	Вывод
3 0 40 30 10 40 30	1 30
5 90 100 100 70 100 70 110 60 120 35	0.5 5.000000000000

Личные олимпиады, Всероссийская олимпиада школьников, Заключительный этап, 2011, Задача F

Тернарный поиск

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

Про любовь...#29478

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

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

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

Входной файл содержит 12 чисел: x₁, y₁, x₂, y₂, x₃, y₃, x₄, y₄, v_1x, v_1y, v_2x, v_2y. Координаты вершин первого отрезка: (x₁, y₁) и (x₂, y₂), координаты вершин второго отрезка: (x₃, y₃) и (x₄, y₄), скорость первого отрезка (v1x, v1y), скорость второго отрезка (v2x, v2y). Все числа целые и не превосходят по модулю 104. В начальный момент времени веточки не соприкасаются. Гарантируется, что веточки имеют ненулевую длину.

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

Выведите в выходной файл время до ближайшего момента, когда веточки соприкоснутся, с ошибкой не более 10⁻⁴. Если веточки не соприкоснутся никогда, выведите число -1.

Ввод	Вывод
0 0 -1 3 4 4 7 7 3 0 0 -1	1.6
0 0 -1 3 4 4 7 7 1 0 0 -3	-1

Тернарный поиск

✓ 11✗ 1001 300средняяВойти и решать

Архимедова спираль#29477

Дима недавно поступил на работу в НИИ Плоских Кривых. Как следует из названия этого научно- исследовательского института, он занимается различными исследованиями в области плоских кривых. Недавно Димин начальник Георгий столкнулся с весьма интересной кривой, которая, как выяснилось после некоторого исследования, известна под названием Архимедовой спирали. Архимедова спираль плоская кривая, изображающая траекторию точки M, которая равномерно движется вдоль луча OK с началом в O, в то время как сам луч OK равномерно вращается вокруг точки O (см. рисунок). Другими словами, расстояние до начала координат ρ = OM линейно зависит от угла поворота φ луча OK. При этом повороту луча OK на один и тот же угол соответствует одно и то же приращение расстояния ρ.

Движение точки M можно задать с помощью ряда параметров:

• начального угла поворота α луча OK (измеряется в градусах против часовой стрелки относительно положительного направления оси OX);

• угловой скорости вращения ω луча OK (измеряется в градусах за единицу времени);

• начального расстояния R от точки M до начала координат (точки O);

• скорости движения V точки M по лучу OK.

Если, задав эти параметры, не ограничить время движения точки M, то получится бесконечная кривая, исследовать которую достаточно трудно. Поэтому Дима решил ограничиться исследованием некоторой части этой кривой той, которая получается при движении точки M от нулевого момента времени до момента времени T. Задача, которую решает Дима состоит в поиске прямоугольника минимальной площади со сторонами, параллельными осям координат, в который ее можно вписать.

Требуется написать программу, которая найдет искомый прямоугольник

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

Входной файл содержит четыре целых числа: ω (1 ≤ ω ≤ 100), V (1 ≤ V ≤ 100), R (0 ≤ R ≤ 100) и T (1 ≤ T ≤ 1000). В этой задаче считается, что начальный угол поворота α равен нулю.

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

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

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

Тернарный поиск

✓ 9✗ 261 200средняяВойти и решать

Миссия Серенити#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-ого груза. Все объемы – натуральные числа, не превышающие 10⁹.

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

Пример

№	Входные данные	Выходные данные
1	3 2 5 10 7 5 5 5 6 9 5 3 5 12 10	4

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

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

Пузырьковая сортировка: количество обменов#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лёгкаяВойти и решать