Матрица: выбор элемента

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

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

 

В квадратную матрицу A порядка n записали n^2 чисел. В ячейку Aij записали число равное произведению ij для всех i, j, изменяющихся от 1 до n. Например, для n=3 матрица A после заполнения имеет вид:

1 2 3

A = 2 4 6

3 6 9.

 

После этого все элементы матрицы выписали на доску в порядке неубывания. Ваша задача найти K-е число в этом списке.

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

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

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

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

Пример

Ввод

3 4

Вывод

3

Задача коммивояжера?

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

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

 

На координатной прямой расположено N городов в точках с координатами X1, X2,..., XN. Вы находитесь в точке с координатой X0. Ваша задача посетить все города в произвольном порядке (можно даже посещать один город дважды). За какое наименьшее количество минут Вы справитесь с поставленной задачей, если ваша скорость равна 1 ед. в минуту?

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

В первой строке входного файла записана пара натуральных чисел N, X0 (1<=N<=200; 1<=X0<=10^5). Далее во второй строке записана последовательность из N натуральных чисел X1, X2,..., XN (1<=Xi<=10^5, для любого i от 1 до N). Числа во всех строках входного файла разделены пробелами. Возможно, что в последовательности X1, X2,..., XN есть совпадающие числа.

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

Выведите единственное число - наименьшее время в минутах, необходимое для посещения всех городов.

Пример

Ввод

2 3
4 5

Вывод

2

Почти палиндромы

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

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

 

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

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

Во входном файле записана строка S, состоящая из заглавных латинских букв и пробелов. Длина строки не менее 2-х символов и не более 200. Гарантируется, что в строке S найдется хотя бы одно слово. Длина каждого слова в S не менее 2-х символов.

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

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

Пример

Ввод

ABCA AAAA XAA

Вывод

3
3 4 1

Лыжи: сколько пар?

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

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

 

На лыжной базе осталось только 4 лыжи размерами L1, L2, L3 и L4. Хозяин лыжной базы утверждает, что лыжи не делятся на правые и левые, и, следовательно, пара лыж может быть выдана клиенту, если выполнется условие равенства размеров двух лыж в паре. Сколько всего пар лыж можно получить на этой лыжной базе?

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

Во входном файле записаны четыре натуральных числа L1, L2, L3 и L4 (1<=L1,L2,L3,L4<=1000), разделенные пробелом.

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

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

Пример

Ввод

1 2 2 1

Вывод

2

Прямоугольники: объединение

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

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

 

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

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

Входной файл состоит из двух строк. Каждая строка содержит описания прямоугольников. Каждое описание состоит из четырех чисел X1, Y1, X2, Y2, где (X1, Y1), (X2, Y2) - координаты двух противоположных углов прямоугольников. Все координаты - целые числа, по абсолютной величине не превосходящие 10^4.

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

Выведите площадь объединения двух прямоугольников.

Пример

Ввод

0 0 3 2
0 0 2 3

Вывод

8

Железная дорога (г. Тарасов)

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

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

 

Студентам Железнодорожного Университета дали задание подвести некоторую статистику движения поездов. Самый сообразительный студент Андрей вооружился расписанием поездов, в котором указаны все поезда, проходящие мимо станции Тарасов-1 (к сожалению, ни один поезд на этой станции не останавливается). Для каждого поезда указано два числа - время начала его движения мимо станции и общее время движения мимо станции Тарасов-1 (поезда бывают очень длинными). Так как весь день Андрей занят учебой, то у него есть только M минут свободного времени, чтобы провести их на станции. Помогите Андрею выбрать такой момент времени, придя в который на станцию он сможет увидеть наибольшее число поездов. Заметим, что если Андрей приходит ровно в тот момент, когда поезд покидает станцию или уходит в тот момент, когда поезд прибывает на станцию, он успевает увидеть поезд.

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

В первой строке входного файла записано два целых числа N и M (0<=N<=1000; 0<=M<=100000), где N- количество поездов в расписании, а M- количество свободных минут Андрея. Далее в N строках даны описания поездов. Каждое описание - это пара чисел, где первое число в паре - это минута, когда поезд приходит на станцию, а второе - время движения поезда мимо станции в минутах. Каждое из чисел натуральное, не превосходящее 100000.

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

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

Пример

Ввод

3 1
1 3
3 1
2 1

Вывод

2

Переворот блинов

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

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

 

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

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

В первой строке входного файла содержится натуральное число N (1<=N<=1000), где N - количество блинов в стопке. Далее в N строках описана сама стопка сверху вниз. Символ D в строке обозначает, что соответствующий блин лежит поджаренной стороной вниз, а U - вверх.

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

В первой строке выведите Q - наименьшее число действий. Далее выведите последовательность из Q натуральных чисел: A1, A2,..., AQ, где Ai - это номер блина (блины нумеруются сверху вниз от 1 до Q) под который помещается лопатка при i-ом действии. Если решений несколько, то выведите любое.

Пример

Ввод

4
D
U
D
U

Вывод

3
1 2 3

294. Выражение (`+` и `-`)

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

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

 

Дано выражение, которое может состоять из цифр '0'-'9', знаков '+', '-' и символов '(', ')'. Ваша задача найти значение выражения. Известно, что никакие два знака не идут подряд, и выражение составлено корректно в том смысле, что оно допустимо компилятором Borland Pascal 7.0 (что совпадает с общепринятыми математическими правилами). Например, выражение '2+(3-(4+5)-1)-3' корректно, а '2+(4-)2-1' - нет. Все целые константы в выражении состоят из одной цифры.

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

Во входном файле содержится выражение. Длина выражения не менее 1 символа и не более 100.

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

Выведите значение выражения.

Пример

Ввод

2+(3-(4+5)-1)-3

Вывод

-8

295. Репортаж `Восхождение и спуск`

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

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

 

Группа альпинистов покорила много вершин и возвратилась в родной город. Одна из местных газет решила написать статью об их походе. Как выяснилось, в процессе похода альпинисты N раз останавливались на ночлег на той или иной высоте hi.
Поскольку главный редактор газеты настаивает, чтобы название статьи было "Восхождение и спуск", решено было не упоминать о некоторых днях похода, рассказав лишь о 2k+1 дне, причем если статья будет рассказывать о x_1-ом, x_2-ом,..., x_(2k+1)-ом (x1<x2<...<x_(2k+1)) дне, то должно выполняться условие h_{x_1} < h_{x_2} <...< h_{x_k} < h_{x_(k+1)} > h_{x_(k+2)} >...> h_{x_2k} > h_{x_(2k+1)}.
Найдите максимальное k, для которого можно соответствующим образом выбрать 2k+1 день.

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

Первая строка входного файла содержит число N - количество дней в походе (1<=N<=100). Следующая строка содержит N целых чисел - h1, h2,..., hN (0<=hi<=10000).

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

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

Пример

Ввод

7
0 3 1 10 7 2 1

Вывод

2
1 2 5 6 7

Ненокку

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

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

 

Очень известный автор не менее известной книги решил написать продолжение своего произведения. Он писал все свои книги на компьютере, подключенном к интернету. Из-за такой не осторожности мальчику Ненокку удалось получить доступ к еще ненаписанной книге. Каждый вечер мальчик залазил на компьютер писателя и записывал на свой компьютер новые записи. Ненокку, записав на свой компьютер очередную главу, заинтересовался, а использовал ли хоть раз писатель слово "книга". Но он не любит читать книги (он лучше полазает в интернете), и поэтому он просит вас узнать есть ли то или иное слово в тексте произведения. Но естественно его интересует не только одно слово, а достаточно много.

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

В каждой строчке входного файла записано одна из двух записей.
1 -? <слово> (<слово> - это набор не более 50 латинских символов)
2 - A <текст> (<текст> - это набор не более 10^5 латинских символов)
1 означает просьбу проверить существование подстроки <слово> в произведение.
2 означает добавление в произведение <текст>.
Писатель только начал работать над произведением, поэтому он не мог написать более 10^5 символов. А входной файл содержит не более 15 мегабайт информации.

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

Выведите на каждую строчку типа 1 "YES", если существует подстрока <слово>, и "NO" в противном случае. Не следует различать регистр букв.

Пример

Ввод

? love
? is
A Loveis
? love
? WHO
A Whoareyou
? is

Вывод

NO
NO
YES
NO
YES

M-склад

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

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

 

У известного в M-ляндии предпринимателя Васечкина на M-складе хранится N бочек с бензином. Они стоят в ряд и пронумерованы от 1 до N. Год назад Васечкин проводил инспекцию, поэтому он знает, сколько литров бензина было в каждой бочки в то время. Когда приходил новый заказ на Q литров бензина, рабочие действовали по очень простому алгоритму. Они наливали его из бочки с наименьшим номером, в которой было достаточное количество бензина. Если такой бочки не находилось, то заказ игнорировался. Теперь Васечкин хочет знать, сколько у него осталось бензина, а очередную инспекцию проводить не хочется. Помогите ему.

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

В первой строке записано N (1 <= N <= 10000). Во второй строке записано N чисел не больших 1000 - количество бензина в бочках год назад. Бочки перечислены в порядке возрастания номера. В третей строке записано K (1 <= K <= 30000) - количество заказов. В четвертой строке записано K чисел не больших 1000 - количество литров в заказах. Заказы перечислены в порядке их поступления.

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

Выведите S - сколько литров бензина осталось у Васечкина.

Пример

Ввод

3
10 5 10
4
7 8 4 4

Вывод

6

Радистка Кэт

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

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

 

Радистка Кэт получила сверхважное сообщение из Москвы для полковника Исаева. Ей необходимо передать его адресату. Она может передать его либо лично (если такой канал возможен), либо через других людей. Для любой пары людей либо существует канал связи между ними, либо нет. Если для пары канал связи возможен, то на передачу сообщения через него требуется какое-то время. Необходимо найти так путь для передачи сообщения от радистки Кэт к полковнику Исаеву, что бы минимизировать суммарное время передачи сообщения. Между парой людей передача сообщения возможна если и только если между ними существует канал. Канал - двунаправленный и существует не более одного канала между каждой парой людей.

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

В первой строке записаны через пробел два числа N и M, где N - общее число человек, а M - число каналов связи. Далее следует M строк, содержащих тройки a, b, T; означающих, что существует канал связи от человека номер a к человеку номер b (a b) и передача информации через него занимает T секунд (2 <= N <= 10^4, 1 <= a,b,M <= 10^4, 1 <= T <= 300). Все числа во входном файле натуральные.

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

Выведите "No solution" передача если информации невозможна или искомую последовательность людей в противном случае. Числа разделяйте пробелами. Радистка Кэт имеет номер 1, а полковник Исаев номер N.

Пример

Ввод

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

Вывод

1 4 3 5

Квадраты

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

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

 

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

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

В первой строке входного файла записано целое число N (1 <= N <= 10) количество исходных фигур у Васи. Далее в N строках содержатся описания пар прямоугольников, на которые Вася разрезал каждую фигуру. Описание представляет собой последовательность 4 натуральных чисел, записанных через пробел (каждое не превосходит 100), где первые два соответствуют ширине и высоте (в любом порядке) первого прямоугольника, а третье и четвертое число соответствуют ширине и высоте (в любом порядке) второго прямоугольника.

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

Выведите N строк. Строка i должна содержать "YES" (без кавычек), если i-ая фигура могла быть квадратом и "NO" (без кавычек), если можно утверждать, что i-ая фигура точно не могла быть квадратом.

Пример

Ввод

3
2 3 3 1
3 2 1 3
3 3 1 3

Вывод

YES
YES

Числа

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

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

 

Даны два натуральных числа A и B. Вам необходимо переставить цифры числа A таким образом, чтобы получилось наибольшее возможное число, не превосходящее B. Никакое из входных или выходных чисел не может начинаться с нуля.

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

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

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

Выведите наибольшее число, не превосходящее B, полученное перестановкой цифр числа A. Гарантируется, что такое число существует.

Пример

Ввод

123
222

Вывод

213

Умножение

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

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

 

Числа в берляндской системе счисления представляют собой последовательность берляндских цифр, каждая из которых либо цифра в обычном понимании слова, либо символ "X". Цифры "0" - "9" имеют свое обычное значение, а цифра "X" обозначает "десять". Не все последовательности берляндских цифр являются числами, а только если
- Самая левая цифра не является "0", и
- Правее цифры "X" не может стоять цифра отличная от "0".
Например, числа "987", "13X", "X000" являются берляндскими числами, а "0056", "XX00" и "19X01" - нет.
Известно, что берляндское число "1" соответствует десятичному числу 1. Известно правило прибавления 1 к берляндскому числу N:
- Если число N содержит цифру "X", этот "X" заменяется на "0", а предыдущая цифра (слева от "X") увеличивается на 1 ("0" переходит в "1", "1" в "2":, "9" переходит в "X"). Если цифра "X" стояла на первом месте, то она заменяется на "0" и спереди к числу дописывают 1. Например, "89X" плюс "1" равно "8X0" и "X00" плюс "1" равно "1000".
- Если число N не содержит цифру "X", то его самая правая цифра увеличивается на 1 ("0" переходит в "1", "1" в "2",:, "9" переходит в "X").
Математики Берляндии доказали, что любое берляндское число может быть получено с помощью последовательности прибавлений единицы к "1" единственным образом. Таким образом, каждому натуральному числу соответствует одно и только одно берляндское число.
Ваша задача перемножить два числа N и M, записанные в берляндской системе счисления и вывести результат в той же системе счисления.

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

В первой строке записано число N в берляндской системе счисления, во второй - M. Длина каждого числа не превосходит 7 цифр.

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

Выведите произведение чисел N и M в берляндской системе счисления.

Пример

Ввод

X
2

Вывод

19

Плюсы-минусы

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

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

 

Магический треугольник строится следующим образом. Сначала заполняется его верхняя строка знаками "+" или "-". Остальные клетки заполняются так, что знак "-" ставят тогда и только тогда, когда ровно один его верхний сосед - это "-". В остальных случаях ставится "+".
Например, магическим треугольником является следующий:

+ + - + -

 + - - -

- + +

- +

-

 

Ваша задача найти количество магических треугольников с P знаками "+" и Q знаками "-" и размером верхней стороны N, где P1 <= P <= P2, Q1 <= Q <= Q2, 1 <= N <= N1.

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

В первой строке входного файла записано натуральное число 1 (1 <= N1 <= 17). Во второй строке записано четыре неотрицательных целых числа P1, P2, Q1, Q2 (P1 <= P2 <= 1000, Q1 <= Q2 <= 1000).

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

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

Пример

Ввод

2
0 1 0 2

Вывод

5

Разделяй и властвуй

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

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

 

Требуется разделить множество клеток Q, целиком лежащее в квадрате N x N клеток (1 <= N <= 20), на два подмножества так, чтобы из одного из них можно было получить другое путем вертикальных и/или горизонтальных сдвигов и поворотов на 90 градусов.

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

В первой строке входного файла находится N. Далее идет описание квадрата: N строк по N символов - "1", если клетка содержится в Q, или "0", если не содержится (без пробелов).

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

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

Пример

Ввод

3
100
011
010

Вывод

YES
100
010
000

Искусство - в массы

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

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

 

Малоизвестный саратовский художник-абстракционист Мадзинский-Калевич решил порадовать нас своим очередным шедевром. Для этого он нарисовал на прямоугольном листе бумаги N дуг окружностей. Радиусы дуг не превосходят 10^9. Чтобы картина произвела должный эффект, в названии картины должно фигурировать количество точек пересечения нарисованных дуг. Вы просто обязаны помочь мастеру.

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

Первая строка входного файла содержит натуральное число N (N<101). Каждая из следующих N строк содержит описание одной дуги. Описание каждой дуги представляет собой координаты трех точек: первые две точки - концы дуги, а третья - некоторая точка на самой дуге, не совпадающая ни с одним из концов. Координаты всех точек - действительные числа, не превосходящие по модулю 10^4 и заданные не более чем с 5 знаками после запятой. Числа в строке разделены пробелом.

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

Первая строка выходного файла должна содержать целое число M - количество различных точек пересечения дуг. Следующие M строк должны содержать сами координаты точек пересечения, выведенные в лексикографическом порядке с 5 знаками после запятой. Числа в строке разделяются пробелом. Под лексикографическим порядком здесь подразумевается упорядочивание точек по возрастанию первой координаты, а при одинаковой первой - по возрастанию второй. Если точек пересечения бесконечное количество, то выходной файл должен содержать единственное слово "Infinity" (без кавычек).

Пример

Ввод

3
0 -1 0 1 1 0
2 -1 2 1 1 0
1 2 -1 2 0 1

Вывод

2
0.00000 1.00000
1.00000 0.00000