Задача 4. Единственный канал у пикселя ≡

Условие

Витя, Петя и Олег — программисты. Они решили написать свой графический редактор на библиотеке Qt!

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

Петя и Олег знают, что цвет пикселя обычно кодируется тремя значениями — red, green, blue. Каждый в диапазоне от 0 до 255. Но модуль Вити возвращает цвет пикселя в виде единственного числа. В битах с 0 по 7 включительно отражена интенсивность синего канала. С 8 по 15 зелёного, а с 16 по 23 интенсивность красного.

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

На вход подаётся число, и буква r\g\b — канал, который нужно оставить. Ваша задача получить итоговый цвет в том же формате.

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

Входные данные содержат число n и символ m — значение цвета и необходимый канал.

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

Выходные данные должны содержать единственное число — цвет в числовом представлении.

Ограничения

0 ≤ n ≤ 16777215

m ∈ {′r′, ′g′, ′b′}

Примеры тестов

6579300 g

25600

Задача A1. Куб со спицами ≡

Условие

Возьмём N³ одинаковых кубиков. Раскрасим кубики в N цветов так, чтобы в каждый цвет было раскрашено ровно N² кубиков. Сложим из всех кубиков один большой куб. Начнём протыкать этот куб спицами параллельно его рёбрам. Любая спица пройдёт сквозь ровно N кубиков.

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

Формат входного файла

Во входном файле содержится единственное натуральное число N.

Формат выходного файла

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

Ограничения

Примеры тестов

2

1 2
2 1
2 1
1 2

Задача A2. В ожидании Нового года ≡

Условие

31 декабря. Марфа Геннадьевна и Глафира Сергеевна уже приготовили новогодний ужин, и теперь они с нетерпением ждут Нового года.

Каждые 5-10 минут они смотрят на часы и вычисляют, сколько часов и минут осталось до Нового года. При этом на вычисление у них уходит много времени.

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

Число секунд в текущем времени принять равным 0.

Формат входного файла

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

Формат выходного файла

Требуется вывести в выходной файл, сколько времени осталось до Нового года — часы и минуты.

Ограничения

Часы от 0 до 23. Минуты от 0 до 59.

Примеры тестов

12 0

12 0

23 59

0 1

22 25

1 35

Задача A3. Количество каждого числа ≡

Условие

Вася записал в файл input.txt N чисел. Когда Петя открыл этот файл, он решил посчитать, сколько раз в файле записано каждое число.

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

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

Формат входного файла

Входной файл содержит целое число N, за которым следуют N целых чисел a_i.

Формат выходного файла

Выходной файл должен содержать пары чисел: число из входного файла и количество раз, сколько оно встретилось в файле.

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

Ограничения

1 ≤ N ≤ 1000000

 − 1000 ≤ a_i ≤ 1000

Примеры тестов

4
1 2 1 0

0 1
1 2
2 1

7
9 1 3 2 3 -2 7

-2 1
1 1
2 1
3 2
7 1
9 1

Задача B. Арифметическая прогрессия ≡

Условие

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

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

Теперь Петя хочет восстановить исходную последовательность по этим карточкам. К сожалению возможно, что это можно сделать несколькими способами, но Петю устроят любые n чисел, образующие арифметическую прогрессию.

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

Напомним что последовательность a₁, a₂, …, a_n называется арифметической прогрессией, если a_i = a_i − 1 + d для всех i от 2 до n и некоторого d. Число d называется разностью арифметической прогрессии.

Формат входного файла

В первой строке входного файла находится целое число n (1 ≤ n ≤ 100 000). В следующей строке находится 2n целых чисел по модулю не превосходящих 10⁹ — числа, написанные на карточках, перечисленные в произвольном порядке. Гарантируется, что можно выбрать n из них так, чтобы они образовывали арифметическую прогрессию.

Формат выходного файла

В первой строке выходного файла выведите a₁ и d — первый элемент и разность найденной арифметической прогрессии. Если d = 0, число a₁ должно встречаться среди заданных чисел n раз.

Если существует несколько решений, выведите любое.

Примеры тестов

3
8 7 1 5 4 3

1 3

Задача C. Двоичные последовательности ≡

Условие

Здравствуй, юный падаван!

Прошу тебя вывести все двоичные последовательности длины N.

Реши задачу двумя способами:

• рекурсивным перебором
• прибавлением 1 к числу в двоичной системе счисления

Да пребудет с тобой произведение массы на ускорение!

Формат входного файла

Входной файл содержит единственное целое число N.

Формат выходного файла

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

Ограничения

1 ≤ N ≤ 15

Примеры тестов

2

00
01
10
11

Задача C2. Код Хаффмана ≡

Условие

Построить код Хаффмана для алфавита из N символов и соответствующих им частот встречаемости.

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов

6
45
13
12
16
9
5

0
101
100
111
1101
1100

Задача C3. Сеть Фейстеля ≡

Условие

Необходимо реализовать шифрование Сетью Фейстеля

Псевдокод шифрования:

    
      for i in range(blocks):
          for r in range(rounds):
              TEMP = L[i]
              L[i] = R[i]
              R[i] = TEMP XOR F(K[r], R[i])
      
  

L[i] - первая половина i-го блока

R[i] - вторая половина i-го блока

K[r] - ключ шифрования на r-ом раунде, в данной задаче размер ключа равен размеру половины блока

F - функция шифрования, в данной задаче используется XOR

В случае если длина строки не кратна размеру блока, строка дополняется символами '\0'

Половины блока имеют одинаковую длину

Длина блока всегда четная

Формат входного файла

Первая строка входного файла содержит количество тестов N

Первая строка теста: 2 целых числа - количество раундов, размер блока в байтах

Вторая строка теста: раундовые ключи шифрования одной HEX строкой

Третья строка теста: целевая ASCII строка, которую необходимо зашифровать

Формат выходного файла

Выходной файл должен содержать N строк - шифротекстов HEX-ом для каждой целевой строки

Ограничения

Длина строки <= 65536

Размер блока <= 64

Кол-во раундов <= 32

Кол-во тестов <= 335

Примеры тестов

1
2 4
90A314CE
Phad1d2Ref

A1AFD4059395B509F5C5E10B

Задача C5. Простое шифрование ≡

Условие

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

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

Требуется написать программу, реализующую простейший алгоритм шифрования.

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов

aab
aac

aad

aab
b

bbc

Задача C6. Усовершенствованный шифр Цезаря ≡

Условие

Требуется написать программу для преобразования строки S в строку H в соответствии с правилом: символ строки H с номером i равен соответствующему символу строки S, смещённому на i символов по алфавиту (символы в строке нумеруются с 1; символ 'Z', смещённый на 1 символ, равен символу 'A').

Формат входного файла

Входной файл содержит строку S, состоящую из заглавных букв английского языка.

Формат выходного файла

Выходной файл должен содержать строку H — закодированное сообщение.

Ограничения

Строка во входном файле содержит от 1 до 255 символов.

Примеры тестов

AAAAAAAAAAAAAAAAAAAAAAAAAAAA

BCDEFGHIJKLMNOPQRSTUVWXYZABC

QWERTY

RYHVYE

Задача C7. Подстановочный шифр ≡

Условие

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов

MAYAS
ARKRS

AR
MA
SS
YK

TRAINING
TAADFTFK

--

Задача C8. Расшифровка ≡

Условие

Дан текст, зашифрованный с помощью шифра простой замены, то есть каждая буква во всём тексте заменена на другую букву (заглавные буквы заменяются на заглавные), знаки препинания, цифры и пробелы остались прежними. Зашифрованный текст можно скачать ЗДЕСЬ.

Известно, что каждая строка текста начинается с одной из следующих фраз:

    Hello
    Welcome back
    Good afternoon
    Nice to meet you
    Excuse me
    Good evening
    I have to apologize
    Not quite

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

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

Выходные данные должны содержать расшифрованный текст.

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

Примеры тестов

8
Excuse je
Hello 
Welcoje back
Good afternoon
Nice to jeet you 
Good evening
I have to apologize 
Not quite

Excuse me
Hello 
Welcome back
Good afternoon
Nice to meet you 
Good evening
I have to apologize 
Not quite

Задача D. Марфа Геннадьевна ест яйца ≡

Условие

У Марфы Геннадьевны есть любимая курица, которую она назвала Марфой. В определённые дни Марфа давала по яйцу, и Марфа Геннадьевна в тот же день съедала его. Марфа Геннадьевна записывала, в какие дни Марфа давала яйцо.

Однажды Марфа Геннадьевна где-то прочитала, что рекомендуется съедать не более двух яиц в неделю. Марфа Геннадьевна заинтересовалась, нарушала ли она хоть раз это правило, то есть найдётся ли промежуток из семи подряд идущих дней, в который она съедала более двух яиц.

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

Формат входного файла

Входной файл содержит целое число N.

Далее следуют N целых чисел a_i — номера дней, в которые Марфа Геннадьевна съедала яйцо.

Формат выходного файла

Требуется вывести в выходной файл слово GOOD, если Марфа Геннадьевна съедала не более двух яиц в неделю, и слово BAD, если найдётся хотя бы один промежуток из семи подряд идущих дней, в который она съедала более двух яиц.

Ограничения

1 ≤ N ≤ 100

1 ≤ a₁ < a₂ < …  < a_N ≤ 1000

Примеры тестов

3
1 7 8

GOOD

5
1 7 9 12 17

BAD

Задача G0. Лабиринт ≡

Условие

Дан квадратный лабиринт, размером N × N, координаты точки входа и точки выхода. Определите минимальное расстояние от входа до выхода.

Формат входного файла

Формат выходного файла

В выходном файле должно содержаться единственное число — минимальное расстояние. Лабиринт проходим.

Ограничения

Примеры тестов

4 1 1 4 1
..#.
..#.
..#.
....

9

Задача G1. Степень графа ≡

Условие

Степень вершины — это количество вершин, с которыми она связана ребром.

Степень графа — это наименьшая из всех степеней вершин.

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

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

Входные данные содержат числа n и m — количество вершин в графе и общее число рёбер.

Далее следует m описаний ребра в виде пар u_i v_i — вершин, которые оно соединяет.

Вершины пронумерованы от 1 до n.

Все рёбра в графе ненаправленные. Мультирёбер граф не содержит.

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

Выходные данные должны содержать единственное число — степень графа.

Ограничения

1 < n < 10⁴

0 < m < n(n − 1) / 2

Примеры тестов

5 8
1 2
1 5
2 3
2 5
3 4
3 5
4 1
4 5

3

Задача G2. Расстояние от корня ≡

Условие

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

Формат входного файла

В первой строке задано n "--- количество вершин в дереве. В следующих n − 1 строках заданы вершины, являющиеся предками вершин 2, 3, …, n. Вершина 1 является корнем дерева.

Формат выходного файла

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

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

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

Ограничения

1 ≤ n ≤ 10⁵

Примеры тестов

3
1
1

1
2
2 3

3
1
2

2
1
3

Задача G3. Модули ≡

Условие

Отдел инновационных технологий фирмы "Division Computers" решил, что повысить производительность в написании программ можно, если использовать модульное программирование, т.е. когда когда каждый программист пишет свою часть отдельно.

Когда все программисты сдали в отдел свою работу, выяснилось, что некоторым модулям для правильного функционирования требуются другие модули, при этом если i-тому модулю нужен j-тый, то и наоборот j-тому модулю нужен i-тый. Вам, как одному из программистов отдела, поручено написать программу, которая по сведениям о связях между модулями определила бы, сколько минимальных программ можно из них собрать. Минимальной считается программа, которую нельзя разделить на более мелкие части.

Формат входного файла

Входной файл содержит числа N и M — соответственно число модулей и связей между ними, за которыми следуют M пар чисел a_i a_j, означающие, что i-тый и j-тый модули не могут функционировать друг без друга.

Формат выходного файла

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

Ограничения

Примеры тестов

3 1
2 3

2

Задача G4. Производство деталей ≡

Условие

Предприятие &laquo;Авто-2010&raquo; выпускает двигатели для известных во всем мире автомобилей. Двигатель состоит ровно из n деталей, пронумерованных от 1 до n, при этом деталь с номером i изготавливается за p_i секунд. Специфика предприятия &laquo;Авто-2010&raquo; заключается в том, что там одновременно может изготавливаться лишь одна деталь двигателя. Для производства некоторых деталей необходимо иметь предварительно изготовленный набор других деталей.

Генеральный директор &laquo;Авто-2010&raquo; поставил перед предприятием амбициозную задачу — за наименьшее время изготовить деталь с номером 1, чтобы представить ее на выставке.

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

Система оценивания

Решения, правильно работающие только для тестов, в которых n не превосходит 10, будут оцениваться из 40 баллов.

Решения, правильно работающие только для тестов, в которых n не превосходит 100, будут оцениваться из 60 баллов.

Решения, правильно работающие только для тестов, в которых n не превосходит 1000, будут оцениваться из 80 баллов.

Формат входного файла

Первая строка входного файла содержит число n — количество деталей двигателя. Вторая строка содержит n натуральных чисел p₁, p₂… p_n, определяющих время изготовления каждой детали в секундах.

Каждая из последующих n строк входного файла описывает характеристики производства деталей. Здесь i-ая строка содержит число деталей k_i, которые требуются для производства детали с номером i, а также их номера.

Известно, что не существует циклических зависимостей в производстве деталей.

Формат выходного файла

В первой строке выходного файла должны содержаться два числа: минимальное время (в секундах), необходимое для скорейшего производства детали с номером 1 и число k деталей, которые необходимо для этого произвести. Во второй строке требуется вывести через пробел k чисел — номера деталей в том порядке, в котором следует их производить для скорейшего производства детали с номером 1.

Ограничения

1 ≤ n ≤ 100000, 1 ≤ p_i ≤ 10⁹

Сумма всех чисел k_i не превосходит 200000.

Примеры тестов

3
100 200 300
1 2
0
2 2 1

300 2
2 1

2
2 3
1 2
0

5 2
2 1

4
2 3 4 5
2 3 2
1 3
0
2 1 3

9 3
3 2 1

Problem G5. Eulerian cycle ≡

Statement

Input file format

Output file format

Constraints

Sample tests

3 3
1 2
2 3
3 1

1 2 3 1

Задача J. Митинг ≡

Условие

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

• m_i  — уровень познаний в математике;
• p_i  — уровень познаний в программировании;
• t_i  — преподавательское мастерство;

Считается, что, i-й персонаж является кандидатом на должность председателя в том и только том случае, когда для него не найдётся такого j-того персонажа, что одновременно m_j > m_i, p_j > p_i, t_j > t_i.

Напишите программу, составляющую список кандидатов на роль председателя.

Формат входного файла

Входной файл содержит натуральное число n  — количество персонажей. Далее следует n троек натуральных чисел m_i p_i t_i.

Формат выходного файла

Требуется вывести в выходной файл номера отобранных персонажей в порядке возрастания.

Ограничения

1 ≤ n ≤ 10⁵

1 ≤ m_i, p_i, t_i ≤ 10⁹

Примеры тестов

4
2 3 4
1 1 3
2 1 8
3 2 10

1 4

Задача J0. Митинг (две характеристики) ≡

Условие

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

• m_i  — уровень познаний в математике;
• p_i  — уровень познаний в программировании;

Считается, что, i-й персонаж является кандидатом на должность председателя в том и только том случае, когда для него не найдётся такого j-того персонажа, что одновременно m_j > m_i, p_j > p_i.

Напишите программу, составляющую список кандидатов на роль председателя.

Формат входного файла

Входной файл содержит натуральное число n  — количество персонажей. Далее следует n двоек натуральных чисел m_i p_i.

Формат выходного файла

Требуется вывести в выходной файл номера отобранных персонажей в порядке возрастания.

Ограничения

1 ≤ n ≤ 10⁵

1 ≤ m_i, p_i ≤ 10⁹

Примеры тестов

4
2 3 
1 1 
2 1 
3 2

1 4

Задача K. Многократное суммирование ≡

Условие

Дан массив целых чисел a₁, a₂, ..., a_N и дано M команд типа "найти сумму чисел a_i для i от l до r".

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

Формат входного файла

Входной файл содержит целое число N, за которым следуют N целых чисел a_i.

Далее во входном файле содержится целое число M, за которым следуют M пар целых чисел l_j r_j.

Формат выходного файла

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

Ограничения

1 ≤ N ≤ 1000000

1 ≤ M ≤ 1000000

 − 1000 ≤ a_i ≤ 1000

1 ≤ l_j ≤ r_j ≤ N

Примеры тестов

5
1 2 3 4 5
3
1 3
2 5
3 5

6 14 12

Задача Y. Марфа Геннадьевна и angry birds ≡

Условие

Недавно Марфа Геннадьевна увидела у внука на компьютере игру Angry birds и тоже захотела сыграть в такую игру. Она взяла кур, свиней и решила стрелять курами в свиней из рогатки. Марфа Геннадьевна задумалась: может, не стоит мучить бедных животных и сделать то же самое не с животными, а с математической моделью?

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

Тело имеет массу m кг, начальная скорость равна v₀ м/с и направлена под углом α градусов к горизонту. Ускорение свободного падения принять равным g = 9.8 м/с². Сила сопротивления воздуха равна .

Требуется определить время и дальность полёта курицы.

Формат входного файла

Входной файл содержит вещественные числа m v₀α k.

Формат выходного файла

Требуется вывести в выходной файл вещественные числа T L — время и дальность полёта соответственно с как минимум 2-мя точными знаками после запятой.

Ограничения

0.1 ≤ m ≤ 10

0.1 ≤ v₀ ≤ 20

1 ≤ α  ≤ 90

0 ≤ k ≤ 10

Примеры тестов

1 10 45 0

1.443 10.204

1 10 45 1

1.206 4.955

Задача Y. Марфа Геннадьевна и документы ≡

Условие

У Марфы Геннадьевны есть папка с файлами (не компьютерная, а обычная), в которую она складывает свои документы. Марфа Геннадьевна пронумеровала свои документы от 1 до N и уже привыкла к тому, что у неё в первом файле лежит первый документ, во втором файле — второй и т.д.

Однажды к Марфе Геннадьевне пришёл в гости внук и стал рассматривать её документы. Разумеется, после этого документы оказались не на своих местах.

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

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

Формат входного файла

Входной файл содержит целое число N, за которым следуют N целых чисел a_i, где число a_i означает, что в i-м файле лежит документ с номером a_i.

Формат выходного файла

Выходной файл должен содержать целое число K — количество выкладываний и вкладываний документов.

Далее должны следовать K пар целых чисел. Пара  − j i означает выкладывание документа с номером j, находящегося в i-м файле. Пара j i означает вкладывание документа с номером j в i-й файл. Если решений несколько, выведите любое из них.

Ограничения

1 ≤ N ≤ 10⁵, 1 ≤ a_i ≤ N. Все числа a_i различны.

Примеры тестов

3
1 3 2

4
-3 2
-2 3
3 3
2 2

4
1 4 2 3

6
-4 2
-3 4
4 4
-2 3
3 3
2 2

3
1 2 3

0

Problem Z0. Square sort ≡

Statement

Input file format

Output file format

Constraints

Sample tests

5 4 3 10 3 1

1 3 3 4 10