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

Автор:mesenev   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:512 Мб
Выходной файл:Стандартный выход  

Условие

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

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

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

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

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

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

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

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

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

Ограничения

0 ≤ n ≤ 16777215

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

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

Стандартный вход Стандартный выход
1
6579300 g
25600

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

Автор:Г. Гренкин   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

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

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

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

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

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

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

Ограничения

1 ≤ N ≤ 100

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

Входной файл (input.txt) Выходной файл (output.txt)
1
2
1 2
2 1
2 1
1 2

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

Автор:Г. Гренкин   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

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

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

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

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

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

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

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

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

Ограничения

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

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

Входной файл (input.txt) Выходной файл (output.txt)
1
12 0
12 0
2
23 59
0 1
3
22 25
1 35

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

Автор:Г. Гренкин   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:4 Мб
Выходной файл:output.txt  

Условие

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

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

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

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

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

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

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

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

Ограничения

1 ≤ N ≤ 1000000

 − 1000 ≤ ai ≤ 1000

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

Входной файл (input.txt) Выходной файл (output.txt)
1
4
1 2 1 0
0 1
1 2
2 1
2
7
9 1 3 2 3 -2 7
-2 1
1 1
2 1
3 2
7 1
9 1

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

Автор:Жюри ВКОШП 2010   Ограничение времени:2 сек
Входной файл:arithm.in   Ограничение памяти:256 Мб
Выходной файл:arithm.out  

Условие

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

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

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

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

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

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

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

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

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

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

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

Входной файл (arithm.in) Выходной файл (arithm.out)
1
3
8 7 1 5 4 3
1 3

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

Автор:Г. Гренкин   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

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

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

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

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

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

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

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

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

Ограничения

1 ≤ N ≤ 15

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

Входной файл (input.txt) Выходной файл (output.txt)
1
2
00
01
10
11

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

Автор:stdalg   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

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

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

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

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

Выходной файл должен содержать N строк вида hi — коды Хаффмана для символов в порядке, соответствующем входному файлу. Каждый код должен представлять собой строку из цифр 0 и 1. Если существует несколько решений, вывести любое из них.

Ограничения

2 ≤ N ≤ 100, 0 ≤ fi ≤ 100000.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
6
45
13
12
16
9
5
0
101
100
111
1101
1100

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

Входной файл:input.txt   Ограничение времени:1 сек
Выходной файл:output.txt   Ограничение памяти:256 Мб

Условие

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

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

    
      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

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

Входной файл (input.txt) Выходной файл (output.txt)
1
1
2 4
90A314CE
Phad1d2Ref
A1AFD4059395B509F5C5E10B

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

Автор:И. Олейников, А. Кленин   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:2 Мб
Выходной файл:output.txt  

Условие

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

Открытый текстwords
Секретный ключkeyke
Зашифрованный текстgspnw

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

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

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

Входной файл содержит 2 строки: открытый текст и ключ шифрования.

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

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

Ограничения

Длина каждой строки не превосходит 255 символов.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
aab
aac
aad
2
aab
b
bbc

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

Автор:Н. Малявин   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

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

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

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

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

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

Ограничения

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

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

Входной файл (input.txt) Выходной файл (output.txt)
1
AAAAAAAAAAAAAAAAAAAAAAAAAAAA
BCDEFGHIJKLMNOPQRSTUVWXYZABC
2
QWERTY
RYHVYE

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

Автор:unknown   Ограничение времени:5 сек
Входной файл:input.txt   Ограничение памяти:200 Мб
Выходной файл:output.txt  

Условие

Шифрование строки подстановочным шифром производится путём замены каждого символа алфавита на другой символ. Разумеется, для однозначного шифрования и дешифрования необходимо, чтобы каждому символу исходного алфавита соответствовал ровно один символ зашифрованного, и наоборот. Например, при помощи шифра M->A, A->R, Y->K слово MAYA будет зашифровано в ARKR.
Даны две строки одинаковой длины, состоящие из заглавных латинских букв. Требуется найти подстановочный шифр, при помощи которого первая строка шифруется во вторую, или определить, что такого не существует. Например, для слов "GOOD" и "WELL" шифра не существует, потому что с одной стороны, буква "O" преобразуется одновременно в "E" и "L", а с другой стороны, буквы "O" и "D" обе превращаются в "L".

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

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

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

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

Ограничения

Длина каждой строки должна не более 50 символов.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
MAYAS
ARKRS
AR
MA
SS
YK
2
TRAINING
TAADFTFK
--

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

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб

Условие

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

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

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

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

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

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

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

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

Стандартный вход Стандартный выход
1
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. Марфа Геннадьевна ест яйца

Автор:Г. Гренкин   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

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

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

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

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

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

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

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

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

Ограничения

1 ≤ N ≤ 100

1 ≤ a1 < a2 < … aN ≤ 1000

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3
1 7 8
GOOD
2
5
1 7 9 12 17
BAD

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

Входной файл:input.txt   Ограничение времени:1 сек
Выходной файл:output.txt   Ограничение памяти:64 Мб

Условие

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

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

Во первой строке входного файла содержатся числа N, x0, y0, x1, y1. Далее следуют N строк по N символов в каждой — описание лабиринта.

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

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

Ограничения

0 ≤ N ≤ 100

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

Входной файл (input.txt) Выходной файл (output.txt)
1
4 1 1 4 1
..#.
..#.
..#.
....
9

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

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб

Условие

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

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

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

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

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

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

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

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

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

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

Ограничения

1 < n < 104

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

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

Стандартный вход Стандартный выход
1
5 8
1 2
1 5
2 3
2 5
3 4
3 5
4 1
4 5
3

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

Входной файл:input.txt   Ограничение времени:1 сек
Выходной файл:output.txt   Ограничение памяти:256 Мб

Условие

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

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

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

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

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

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

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

Ограничения

1 ≤ n ≤ 105

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3
1
1
1
2
2 3
2
3
1
2
2
1
3

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

Автор:И. Олейников   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

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

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

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

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

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

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

Ограничения

1 ≤ N ≤ 100000, 0 ≤ M ≤ 106

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3 1
2 3
2

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

Автор:Центральная предметно-методическая комиссия по информатике   Ограничение времени:2 сек
Входной файл:details.in   Ограничение памяти:256 Мб
Выходной файл:details.out  

Условие

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

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

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

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

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

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

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

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

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

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

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

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

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

Ограничения

1 ≤ n ≤ 100000, 1 ≤ pi ≤ 109

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

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

Входной файл (details.in) Выходной файл (details.out)
1
3
100 200 300
1 2
0
2 2 1
300 2
2 1
2
2
2 3
1 2
0
5 2
2 1
3
4
2 3 4 5
2 3 2
1 3
0
2 1 3
9 3
3 2 1

Problem G5. Eulerian cycle

Author:StdAlg   Time limit:1 sec
Input file:input.txt   Memory limit:64 Mb
Output file:output.txt  

Statement

You are to write a program that receives an undirected connected graph and finds its Eulerian cycle.

Input file format

Input file contains two integers N, M. Vertices are numbered with integer numbers from 1 to N. M is the number of edges. Each of following M lines contains a pair of vertex numbers, connected by some edge. There is at most one edge connecting two vertices.

Output file format

Output file must contain a sequence of vertex numbers in order of traversal in an Eiler cycle. If there does not exist any Eiler cycle, output file must contain  − 1.

Constraints

1 ≤ N, M ≤ 100000

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
3 3
1 2
2 3
3 1
1 2 3 1

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

Автор:Виртуальная реальность   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

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

Чем больше число, тем выше уровень мастерства персонажа в соответствующей области.

Считается, что, i-й персонаж является кандидатом на должность председателя в том и только том случае, когда для него не найдётся такого j-того персонажа, что одновременно mj > mi, pj > pi, tj > ti.

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

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

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

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

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

Ограничения

1 ≤ n ≤ 105

1 ≤ mi, pi, ti ≤ 109

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

Входной файл (input.txt) Выходной файл (output.txt)
1
4
2 3 4
1 1 3
2 1 8
3 2 10
1 4

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

Автор:mesenev   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

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

Чем больше число, тем выше уровень мастерства персонажа в соответствующей области.

Считается, что, i-й персонаж является кандидатом на должность председателя в том и только том случае, когда для него не найдётся такого j-того персонажа, что одновременно mj > mi, pj > pi.

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

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

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

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

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

Ограничения

1 ≤ n ≤ 105

1 ≤ mi, pi ≤ 109

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

Входной файл (input.txt) Выходной файл (output.txt)
1
4
2 3 
1 1 
2 1 
3 2
1 4

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

Автор:Г. Гренкин   Ограничение времени:5 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

Дан массив целых чисел a1, a2, ..., aN и дано M команд типа "найти сумму чисел ai для i от l до r".

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

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

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

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

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

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

Ограничения

1 ≤ N ≤ 1000000

1 ≤ M ≤ 1000000

 − 1000 ≤ ai ≤ 1000

1 ≤ lj ≤ rj ≤ N

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

Входной файл (input.txt) Выходной файл (output.txt)
1
5
1 2 3 4 5
3
1 3
2 5
3 5
6 14 12

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

Автор:Г. Гренкин   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

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

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

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

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

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

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

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

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

Ограничения

0.1 ≤ m ≤ 10

0.1 ≤ v0 ≤ 20

1 ≤ α ≤ 90

0 ≤ k ≤ 10

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

Входной файл (input.txt) Выходной файл (output.txt)
1
1 10 45 0
1.443 10.204
2
1 10 45 1
1.206 4.955

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

Автор:Г. Гренкин   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

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

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

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

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

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

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

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

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

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

Ограничения

1 ≤ N ≤ 105, 1 ≤ ai ≤ N. Все числа ai различны.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3
1 3 2
4
-3 2
-2 3
3 3
2 2
2
4
1 4 2 3
6
-4 2
-3 4
4 4
-2 3
3 3
2 2
3
3
1 2 3
0

Problem Z0. Square sort

Author:StdAlg   Time limit:1 sec
Input file:input.txt   Memory limit:8 Mb
Output file:output.txt  

Statement

You are to write a program that receives a sequence of integer numbers and sorts it, i. e. writes out all elements in ascending order.

Input file format

Input file contains integer N — length of the sequnece, followed by N integer numbers — elements of the sequence.

Output file format

Output file must contain N integer numbers, which must be elements of the source sequence printed in ascending order.

Constraints

0 ≤ N ≤ 3000. Sequence elements are less than 109 by absolute value.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
5 4 3 10 3 1
1 3 3 4 10

3.208s 0.024s 69