Интеллект против QSort

ограничение времени на тест: 3 сек.
ограничение памяти на тест: 16384 KB.

ввод: input.txt
вывод: output.txt

 

Для сортировки последовательности чисел широко используется быстрая сортировка - QSort. Ниже приведена программа, которая сортирует массив a, используя данный алгоритм.

Хотя QSort является самой быстрой сортировкой в среднем, существуют тесты, на которых она работает очень долго.

Будем оценивать время работы алгоритма количеством сравнений, сделанных с элементами массива (т.е. суммарным количеством сравнений в первой и втором while). Требуется написать программу, генерирующую тест, на котором быстрая сортировка сделает наибольшее число таких сравнений.

 

var a: array [1..N] of integer;

 

procedure QSort(left, right: integer);

var m, i, j, t: integer;

begin

m:= a[(left+right) div 2];

i:= left; j:= right;

repeat

while a[i] < m do inc(i); {первый while}

while a[j] > m do dec(j); {второй while}

if i <= j then

begin

t:= a[i]; a[i]:= a[j]; a[j]:= t;

inc(i); dec(j);

end;

until i > j;

 

if j > left then QSort(left, j);

if i < right then QSort(i, right);

end;

 

begin

...

QSort(1, N);

end.

 

 

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

Во входном файле задано число N (1<=N<=700000).

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

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

Пример

Ввод

3

Вывод

1 3 2

Дешевле, еще дешевле

ограничение времени на тест: 1.5 сек.
ограничение памяти на тест: 16384 KB.

ввод: input.txt
вывод: output.txt

 

Алфавит A состоит из K букв латинского алфавита. У каждой буквы есть цена (своя). Цена слова - сумма цен всех вхождений всех букв в нем. Множество слов называется хорошим, если никакой слово не является началом другого слова. Ваша задача найти цену самого дешевого N-элементного хорошего множества слов.
Допустим K = 2 (даны буквы a и b). Цена буквы a равна 2, а b - 5. Цена слова ab равна 7, а цена слова aba равна 9. Множество слов {ab, aba, b} стоит 21, но оно не является хорошим, так как ab является началом слова aba. Наиболее дешевое хорошее множество слов мощности 3 это {b, aa, ab}. Его цена равна 16.

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

В первой строке записано число N (1 <= N <= 10000) и K (2 <= K <= 26) через пробел. Вторая строка содержит K чисел - цены букв (натуральные числа, не большие 10000).

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

Выведите цену наиболее дешевого хорошего N элементного множества над алфавитом A.

Пример

Ввод

3 2
2 5

Вывод

16

Мэры

ограничение времени на тест: 1 сек.
ограничение памяти на тест: 32768 KB.

ввод: input.txt
вывод: output.txt

 

Во Флатландии имеется N городов, расположенных на плоскости в точках с координатами (xi, yi). Недавно президент Флатландии решил назначить в каждом городе мэра. При этом, чтобы его нельзя было уличить в дискриминации, он решил назначить на эти посты как мужчин, так и женщин. Для каждой горизонтальной и вертикальной прямой назовем несправедливостью модуль разности между количеством городов на этой прямой, в которых на пост мэра назначены мужчины и количеством городов на этой прямой, в которых на этот пост назначены женщины.
Чтобы показать свою беспристрастность, президент хочет минимизировать суммарную несправедливость по всем вертикальным и горизонтальным прямым.
Напишите программу, которая определит для каждого города, следует ли в нем назначить на пост мэра женщину или мужчину, так, чтобы суммарная несправедливость была минимальна.

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

Первая строка входного файла содержит число N - количество городов (1 <= N <= 20000). Следующие N строк содержат по два целых числа - координаты городов. Все координаты не превышают 10^9 по абсолютной величине.

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

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

Пример

Ввод

5
0 0
0 1
1 0
1 1
1 2

Вывод

1
0
0
1
0

Складываем время

ограничение времени на тест: 0.5 сек.
ограничение памяти на тест: 4096 KB.

ввод: input.txt
вывод: output.txt

 

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

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

В двух строках входного файла содержится два времени в формате HH:MM:SS (где HH - часы, MM - минуты, SS - секунды, время изменяется в пределах от 00:00:00 до 23:59:59). Первое время - показания часов на момент началы работы, второе время - продолжительность рабочего дня.

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

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

Пример

Ввод

01:00:01
10:10:10

Вывод

11:10:11

Всеобщая факторизация

ограничение времени на тест: 0.75 сек.
ограничение памяти на тест: 4096 KB.

ввод: input.txt
вывод: output.txt

 

В рамках всеобщей ежегодной факторизации вам дали задание - написать программу, которая факторизует (раскладывает на простые множители) натуральное число N (1<N<=10^12).

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

Во входном файле записано единственное число N.

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

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

Пример

Ввод

4

Вывод

1
2 2

S and 1's

ограничение времени на тест: 0.5 сек.
ограничение памяти на тест: 4096 KB.

ввод: input.txt
вывод: output.txt

 

Вася изучает в школе системы счисления. Когда вечером он вернулся домой, Вася осознал, что две цифры есть в любой системе счисления - это '0' и '1'. И он начал составлять равенства в различных системах счисления используя только '0' и '1'. У него не возникло проблем со сложением. Зато умножение его очень заинтересовало. Вася заметил, что равенство 11*11=1001 верно только в двоичной системе счисления.
Теперь он хочет создать аналогичное равенство для других систем счисления. Напишите программу для Вася, которая для заданного основания системы счисления выводит равенство вида A*B=C (где A, B и C состоят только из '0' и '1') или выясняет, что его не существует.

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

Входной файл содержит только одно целое число Z - основание системы счисления (2<=Z<=36).

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

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

Пример

Ввод

2

Вывод

11*11=1001

Поиграем?

ограничение времени на тест: 1 сек.
ограничение памяти на тест: 640 KB.

ввод: input.txt
вывод: output.txt

 

...Они встали в шеренгу и начали расчет. Если на человека выпадало число кратное 3 или в котором встречалась цифра 3, тот выпрыгивал вверх и говорил слово "Гоп!". Было сделано N (0<N<100001) ходов. Ваша задача определить сколько прыжков было совершенно за игру.

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

Во входном файле записано число N.

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

Выведите единственное число - ответ на поставленную задачу.

Пример

Ввод

4

Вывод

1

Хитрые перестановки

ограничение времени на тест: 5 сек.
ограничение памяти на тест: 4096 KB.

ввод: input.txt
вывод: output.txt

 

Выведите все такие N-элементные перестановки P, что A <= P[1] * 1 + P[2] * 2 +... + P[N] * N <= B.

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

Во входном файле записаны целые N, A, B (1 <= N <= 10; 0 <= A <= B <= 1000).

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

Выведите все искомые перестановки в лексикографическом порядке.

Пример

Ввод

3 9 10

Вывод

3 2 1

Бер-сот Инк.

ограничение времени на тест: 2.5 сек.
ограничение памяти на тест: 4096 KB.

ввод: input.txt
вывод: output.txt

 

Правительство небольшой берляндской провинции решило открыть сотовую сеть. Для этого по все области было потавлено N базовых станций. Правительство открыло тендер для компаний, работающих в области телекоммуникаций, на прокладку кабеля между базовыми станциями. Чтобы принять участие в тендере компания должна предоставить ровно один план прокладки кабеля, который должен удовлетворять следующим условиям:
1. Все N станций должны быть соеденены кабелем по кругу (последняя станция соединяется с первой).
2. Кабель прокладывается по прямой между вышками.
3. Никакие два кабеля в плане не должны пересекаться.
4. К каждой базовой станции должно подходить ровно два кабеля.
5. Планы всех компаний должны быть различны.
Ваша задача определить максимальное количество компаний, которые смогут принять участие в тендере.

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

В первой строке входного файла содержится натуральное число N (3<=N<=11). В следующих N строках содержатся координаты базовых станций - по два целых числа, не превосходящих по абсолютному значению 1000. Никакие две базовые не находятся в одной точке. Известно, что существуют три базовые станции не лежащие на одной прямой.

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

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

Пример

Ввод

3
0 0
1 0
0 1

Вывод

1

Самое длинное слово

ограничение времени на тест: 0.75 сек.
ограничение памяти на тест: 65536 KB.

ввод: input.txt
вывод: output.txt

 

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

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

В файле записан текст, длиной не более 10^5 символов.

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

Выведите искомое самое длинное слово.

Пример

Ввод

It is impossible to solve this problem

Вывод

impossible

Сортировка

ограничение времени на тест: 0.5 сек.
ограничение памяти на тест: 65536 KB.

ввод: input.txt
вывод: output.txt

 

Дано N (1<=N<=1000) целых положительных чисел. Требуется отсортировать их так, что бы сначала шли нечетные числа в неубывающем порядке, а затем четные в невозрастающем.

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

В первой строке входного файла записано число N. Далее записано N чисел, разделенных пробелами иили переводами строки. Все числа не превосходят 1000.

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

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

Пример

Ввод

6 6 2
3 1 4 5

Вывод

1 3 5 6 4 2

Eratosthen 2.0

ограничение времени на тест: 0.5 сек.
ограничение памяти на тест: 4096 KB.

ввод: input.txt
вывод: output.txt

 

На доске написано N чисел: 1, 2,..., N. Сначала с доски стирают каждое второе число. Затем каждое третье, потом каждое четвертое и т.д. до бесконечности. Ваша задача узнать, что в конце концов останется на доске.

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

В первой строке записано число N (1<=N<=65000).

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

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

Пример

Ввод

8

Вывод

1 3 7

211. В этом городе ф***

ограничение времени на тест: 0.5 сек.
ограничение памяти на тест: 4096 KB.

ввод: input.txt
вывод: output.txt

 

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

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

В первой строке записано два натуральных числа N и M (1<=N<=15000, 1<=M<=15000). Далее следует N чисел - последовательность координат фонарей. Затем M чисел - последовательность координат голосующих. Все координаты целые, по модулю не превосходящие 10^6. Числа во входном файле разделяются пробелами и/или переводами строк.

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

Выведите M чисел - длины путей каждого автостопера. Числа разделяйте пробелами.

Пример

Ввод

2 2
5 10
4 8

Вывод

1 2

Король в бегах

ограничение времени на тест: 0.5 сек.
ограничение памяти на тест: 4096 KB.

ввод: input.txt
вывод: output.txt

 

Шахматный король пустился в бега! Имеется последовательность его ходов. Король умеет ходить на одну из восьми соседних клеток. Команды обозначаются как
L - влево;
R - вправо;
U - вверх;
D - вниз;
LU - влево и вверх (по диагонали);
LD - влево и вниз (по диагонали);
RU - вправо и вверх (по диагонали);
RD - вправо и вниз (по диагонали).
Ваша задача определить попадал ли король на одну клетку более одного раза. Клетка, с которой он начал свое путешествие - учитывается. Если да, то найдите номер хода, когда он это сделал впервые. Король путешествует по бесконечной во все стороны шахматной доске.

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

В первой строке записано число N (1<=N<=2000) - количество ходов короля. Во второй строке содержится последовательность описаний его ходов, записанных через пробел(ы). Строка может заканчиваться пробелами.

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

Выведите "NO", если король побывал на всех клетках пути ровно по разу. В противном случае выдайте "YES" на первой строке и номер искомого хода на второй.

Пример

Ввод

3
R R RU

Вывод

NO

Считаем биты

ограничение времени на тест: 0.5 сек.
ограничение памяти на тест: 4096 KB.

ввод: input.txt
вывод: output.txt

 

Дано натуральное число N. Ваша задача подсчитать количество единиц в двоичном представлении этого числа. Например, если N = 13, то в двоичном представлении N = (1101)₂, следовательно, ответ равен 3.

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

Во входном файле записано натуральное число N (1 <= N <= 10^9).

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

Выведите целое число, ответ на поставленную задачу.

Пример

Ввод

13

Вывод

3

Нулевая сумма

ограничение времени на тест: 0.5 сек.
ограничение памяти на тест: 4096 KB.

ввод: input.txt
вывод: output.txt

 

Дана последовательность из N целых чисел. Найти в этой последовательности непрерывную подпоследовательность максимальной длины, сумма элементов которой равна 0.

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

Во входном файле в первой строке целое число N (1<=N<=1000). Далее идет N строк с элементами последовательности, в каждой строке одно целое число от -100 до 100.

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

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

Пример

Ввод

4
1
-1
0
-1

Вывод

3 1

Антипростые числа

ограничение времени на тест: 0.5 сек.
ограничение памяти на тест: 4096 KB.

ввод: input.txt
вывод: output.txt

 

Число N называется антиростым, если оно имеет больше натуральных делителей, чем любое натуральное число меньшее N.
Например, антипростые числа это: 1, 2, 4, 6, 12, 24.
Ваша задача по данному N найти наибольшее антипростое число, не превосходящее N.

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

Дано натуральное N (1<=N<=2000000000).

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

Выведите ответ на поставленную задачу.

Пример

Ввод

1000

Вывод

840

Книги

ограничение времени на тест: 0.5 сек.
ограничение памяти на тест: 4096 KB.

ввод: input.txt
вывод: output.txt

 

В берляндской научной библиотеке всего три книги. В первой - A1 страниц, во второй - A2 и в третей - A3 страниц. В целях самообразования школьник Б. Берляев решил прочесть эти книги, но так как ему книги с одинаковым количеством страниц кажутся похожими, он читает только книги с разным количеством страниц. Помогите Б. Берляеву узнать количество книг, которое он сможет прочесть в библиотеке.

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

В первой строке входного файла записано три натуральных числа A1, A2, A3. Числа разделяются пробелами и не превосходят 100.

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

Выведите количество книг, которое Б. Берляев сможет прочесть в библиотеке.

Пример

Ввод

45 45 26

Вывод

2

Berland Pascal 7.0

ограничение времени на тест: 0.5 сек.
ограничение памяти на тест: 4096 KB.

ввод: input.txt
вывод: output.txt

 

Знаменитая компания по разработке сред программирования Berland выпустила обновление своего популярного продукта Berland Pascal 7.0.
Теперь написание шифровальных систем на Berland Pascal станет намного проще, так как появились две новых встроенных функции. Первая из них шифрует неотрицательное целое число, а вторая - дешифрует. Первая функция работает следующим образом: она оставляет первую (старшую) цифру числа без изменения, к i-ой цифре прибавляет (i - 1)-ую (для i > 1). Если результат окажется больше 9, то оставляется только остаток при делении на 10. Например, число 12345 после шифрования примет вид: 13579, а число 533976 примет вид: 586263.

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

В первой строке записано неотрицательное целое число N (0 <= N <= 10^9).

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

Выведите такое неотрицательное целое число M, которое после шифрования станет равно N.

Пример

Ввод

13579

Вывод

12345

Дом улыбок

ограничение времени на тест: 2.5 сек.
ограничение памяти на тест: 4096 KB.

ввод: input.txt
вывод: output.txt

 

Дом улыбок создан, чтобы повышать настроение. В нем есть N комнат. Некоторые из комнат соединены дверьми. Про каждые две комнаты соединенные дверью с номерами i и j Петя знает величину Cij - на сколько изменяется у него настроение при переходе из комнаты с номером i в комнату с номером j.
Петя задумался: может ли он поднять себе настроение до бесконечности, двигаясь по каком-нибудь циклу. А если может, то какое минимальное количество комнат ему надо будет проходить за один период цикла?

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

В первой строке записаны натуральные числа N и M (1 <= N <= 100, 0 <= M <= N*(N-1) / 2), где M - количество дверей в доме улыбок. Далее идет M строк по 4 целых числа i, j, Cij и Cji
(-10^4 <= Cij,Cji <= 10^4).

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

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

Пример

Ввод

4 4
1 2 -10 3
1 3 1 -10
2 4 -10 -1
3 4 0 -3

Вывод

4