--->
232 задач
<---
Источники
В Тридевятом царстве царь был любителем разных заморских традиций. Как прознает, что в другом царстве есть какой-то обычай, сразу думает, как бы его к тридевятым реалиям приспособить.
Вот неделю назад вернулось посольство из Тридесятого царства. И главный посол доложил царю: дескать, придумал Тридесятый царь следующую вещь. Чтобы как-то зарегулировать гуляния народные, повелел он указать определенные дни, и в эти дни устраивать широкие гуляния, а в остальные дни массовые сборища запретить. И с тех пор жизнь в Тридесятом царстве стала прекрасной: гулять так гулять, работать так работать, и все строго по цареву указу.
Понравилась мысль такая царю Тридевятого царства. Подумал он ввести и у себя такие порядки. Собрал царь советников своих, и говорит: подготовьте мне список дней, в которые гулять можно. Только не на год, а на \(N\) дней вперед — посмотрим, дескать, что получится; понравится — сделаем круглогодичным.
И вот вчера принесли советники царю список. Но вот незадача: каждый советник свой список приготовил, да еще и обоснование предложил, какой праздник в какой из этих дней надо отмечать. И у всех советников праздники важные, но у всех — разные! Царь думал-думал и решил: а возьмем их все — объединим предложения советников! Если какой-то день есть в списке хотя бы одного советника, то объявим этот день праздничным, и пускай народ гуляет! Глядишь, и не будет недовольных.
Только одна проблема осталась: некоторые дни оказались в списках сразу у нескольких советников. Но царь и тут нашел выход: перенесем некоторые праздники на более поздние дни, так, чтобы в каждый день получался только один праздник, и переносы были бы как можно короче.
Пусть, например, четыре советника сразу предложили сделать некоторый день (пускай день 5) праздничным. Тогда перенесем три из этих четырех праздников на дни 6, 7 и 8 — так, что праздничными будут дни с 5 по 8 включительно. А если оказывается, что, например, день 7 тоже предложен в качестве праздничного кем-нибудь из советников, то перенесем этот праздник еще дальше — на день 9.
Напишите программу, которая, зная предложения советников, определит, какие дни будут праздничными, а какие нет. Не забывайте, что праздники можно переносить только на более поздние дни; на более ранние переносить нельзя.
На первой строке входного файла находится одно число \(N\) — количество дней, на которые царь хочет произвести планировку праздников.
На второй строке входного файла находятся \(N\) неотрицательных целых чисел — для каждого дня указано, сколько советников предложили считать его праздничным.
Гарантируется, что \(1\leq N\leq 100\,000\), и что сумма всех чисел во второй строке входного файла не превосходит \(100\,000\).
В выходной файл выведите одну строку, состоящую из символов “+” или “-”. “+” обозначайте праздничный день, “-” — непраздничный. Выведите как минимум \(N\) символов — по одному для каждого
из дней, на которые проводится планирование. Но если праздники приходится переносить на дни после \(N\)-го (что допустимо), то выведите больше символов — до последнего праздничного дня.
Символы разделяйте пробелами.
5 0 3 0 0 0
- + + + -
10 0 4 0 2 0 0 0 0 1 0
- + + + + + + - + -
3 0 3 0
- + + +
Даны два массива X и Y одинаковой длины. Записать алгоритм, меняющий последовательно местами значения элементов X[k] и Y[k] для этих таблиц, для k = 1, 2, ..., n, не используя промежуточных переменных.
В первой строке содержится одно число n — количество элементов в каждом из массивов. (1 ≤ n ≤ 100{, }000) Во второй строке через пробел записаны натуральные числа первого массива. В третьей строке через пробел записаны натуральные числа второго массива (Гарантируется, что числа не превышают 106)
В первой строке выведите через пробел все элементы второго массива, а во второй строке — первого.
3
1 2 3
4 5 6
4 5 6
1 2 3
Король Квадратландии прекрасно знает, сколько солдат патрулирует каждый квадрат своей квадратной страны. Теперь он желает оценить обороноспособность Квадратландии. Хорошо известно, что она зависит от количества солдат, которые патрулируют границу. Он поручает эту непростую задачу вам — своему придворному счетоводу.
Посчитайте общее количество солдат, патрулирующих пограничные квадраты.
На первой строке дано одно натуральное число n —величина Квадратландии (число квадратов по одной стороне) (1 ≤ n ≤ 100) . Дальше идут n строк по n неотрицательных чисел в каждой - количество солдат, которые охраняют каждый квадрат. Эти числа не превышают 10 6 .
Выведите одно число — обороноспособность
3 1 2 3 3 4 7 0 2 3
21
Дан массив целых чисел. Найти отрезок этого массива с максимальной суммой.
В первой строке дано натуральное число n ( 1 ≤ n ≤ 10 5 ) — размер массива. Во второй строке через пробел перечислены элемента массива. Числа не превышают 10 4 .
Выведите три числа — индекс начала отрезка, индекс конца и саму максимальную сумму. Массив индексируется с единицы. Если ответов несколько — выведите любой.
5 -1 2 3 -2 5
2 5 8
Известный художник решил написать новый шедевр. После многих дней усердной работы он захотел исследовать свое творение. Художник вспомнил, что картина писалась следующим образом. Сначала был взят белый холст, имеющий форму прямоугольника шириной w и высотой h. Затем художник нарисовал на этом холсте n прямоугольников с координатами углов (x1i;y1i), (x1i;y2i), (x2i;y2i), (x2i;y1i).
Помогите художнику определить площадь незакрашенной части холста.
Первая строка содержит два целых числа w и h (1 ≤ w;h ≤ 100) — ширину и высоту холста соответственно. Вторая строка входного файла содержит целое число n (0 ≤ n ≤ 5000) — количество прямоугольников. Следующие n строк содержат информацию о прямоугольниках. (i + 2)-ая строка содержит четыре целых числа x1i; y1i, x2i; y2i (0 ≤ x1i ≤ x2i ≤ w, 0 ≤ y1i ≤ y2i ≤ h).
Выведите ответ на задачу.
5 5 2 1 1 3 3 2 2 4 4
18
6 7 3 0 0 5 5 1 1 4 4 2 2 3 3
17