Информатика

Дана строка. Известно, что она содержит ровно две одинаковые буквы. Найдите эти буквы. Гарантируется, что повторяются буквы только одного вида.

Входные данные
На вход подается 1 строка.

Выходные данные
Необходимо вывести  букву, которая встречается в строке дважды.
 

Примеры

№	Входные данные	Выходные данные
1	fif	f

Измените регистр символа. Если он был строчной английской буквой сделайте его заглавной буквой; если он был заглавной английской буквой  - строчной.


Входные данные
Задан единственный символ c.

Выходные данные
Необходимо вывести  получившийся символ.
 

Примеры

№	Входные данные	Выходные данные
1	a	A
2	B	b

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

Входные данные
Задано единственное число N. (N ≤ 40)

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

Примеры

№	Входные данные	Выходные данные
1	5	1 1 1 1 1  2 1 1 1  2 2 1  3 1 1  3 2  4 1  5

Компания BrokenTiles планирует заняться выкладыванием во дворах у состоятельных клиентов узоров из черных и белых плиток, каждая из которых имеет размер 1 х 1 метр. Известно, что дворы всех состоятельных людей имеют наиболее модную на сегодня форму прямоугольника N х M метров. Однако при составлении финансового плана у директора этой организации появилось целых две серьезных проблемы: во-первых, каждый новый клиент, очевидно, захочет, чтобы узор, выложенный у него во дворе, отличался от узоров всех остальных клиентов этой фирмы, а во-вторых, этот узор должен быть симпатичным.

Как показало исследование, узор является симпатичным, если в нем нигде не встречается квадрата 2 х 2 метра, полностью покрытого плитками одного цвета. Для составления финансового плана директору Васе необходимо узнать, сколько клиентов он сможет обслужить, прежде чем симпатичные узоры данного размера закончатся. Помогите ему!

Входные данные
Вводятся два положительных целых числа N и M (1 ≤ N · M ≤ 30).

Выходные данные
Выведите единственное число –  количество различных симпатичных узоров, которые можно выложить во дворе размера N х M. Узоры, получающиеся друг из друга сдвигом, поворотом или отражением, считаются различными.
 

Примеры

№	Входные данные	Выходные данные
1	1 2	4
2	2 3	50

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

Для простоты будем считать, что все карты различны по номиналу, а также, что самая младшая карта побеждает самую старшую карту ("шестерка берет туза").

Игрок, который забирает себе карты, сначала кладет под низ своей колоды карту первого игрока, затем карту второго игрока (то есть карта второго игрока оказывается внизу колоды).

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

Входные данные
Программа получает на вход две строки: первая строка содержит 5 чисел, разделенных пробелами — номера карт первого игрока, вторая – аналогично 5 карт второго игрока. Карты перечислены сверху вниз, то есть каждая строка начинается с той карты, которая будет открыта первой.

Выходные данные
Программа должна определить, кто выигрывает при данной раздаче, и вывести слово first или second, после чего вывести количество ходов, сделанных до выигрыша. Если на протяжении 10⁶ ходов игра не заканчивается, программа должна вывести слово botva.

Примеры

№	Входные данные	Выходные данные
1	1 3 5 7 9 2 4 6 8 0	second 5

Имеется сетка из N строк и N столбцов квадратов. Пусть (i, j) индексы клетки, которая расположена в i-й строке сверху и j-м столбце слева. Эти клетки должны быть окрашены в один из цветов C от цвета 1 до цвета C. Первоначально (i, j) окрашен в цвет ci,j. Назовем сетку хорошей, когда выполняются следующие условия для всех i, j, x, y, удовлетворяющих \(1<=i,j,x,y<=N\):
- если \((i+j)\%3=(x+y)\%3\), цвет (i, j) и цвет (x, y) совпадают;
- если \((i+j)\%3\neq(x+y)\%3\), цвет (i, j) и цвет (x, y) различны.
Здесь \(X \% Y \) представляет X по модулю Y.
Мы перекрасим ноль или более клеток, чтобы сетка была хорошей сеткой.
Неправильной клеткой назовем клетку, которая имела цвет X до перерисовки и Y после перекраски (DX,Y).
Найдите минимально возможную сумму всех неправильных клеток.

Входные данные
В первой строке задаются два целых числа N и C. В следующих C строках задаются по C значений Di,j. В последних N строках записаны N чисел в каждой строке - ci,j.

Выходные данные
Выведите минимально возможную сумму всех неправильных клеток
 

 

Примеры

№	Входные данные	Выходные данные	Пояснения
1	2 3 0 1 1 1 0 1 1 4 0 1 2 3 3	3	Перекрасить (1,1) в цвет 2. Неправильный (1,1) становится D 1,2 = 1. Перекрасить (1,2) в цвет 3. Неправильность (1,2) становится D 2,3 = 1. Перекрасить (2,2) в цвет 1. Неправильность (2,2) становится D. 3,1 = 1. В этом случае сумма неправильности всех квадратов равна 3. Отметим, что возможно \(Di, j  \neq D j, i \).
2	4 3 0 12 71 81 0 53 14 92 0 1 1 2 1 2 1 1 2 2 2 1 3 1 1 2 2	428

 

В некоторой деревне есть 999 башен высотой 1, (1 + 2), (1 + 2 + 3), ..., (1 + 2 + 3 + ... + 999) метров с запада на восток. Расстояние между двумя соседними башнями 1 метр. Некоторое время шел снег, прежде чем он наконец прекратился. Для двух соседних башен, расположенных на расстоянии 1 метра друг от друга, мы измерили длины частей этих башен, которые не покрыты снегом, и получили a метров для западной башни и b метров для восточной башни. Предполагая, что толщина снежного покрова и высота над уровнем моря одинаковы во всем населенном пункте, найдите общую глубину снежного покрова. Предположим также, что глубина снежного покрова всегда составляет не менее 1 метра.

Входные данные
Во входной строке содержится два целых чисел a и b (\(1\leq a<b<499500=1+2+3+...+999\)). Все входные данные удовлетворяют условию задачи.

Выходные данные
Выведите глубину снежного покрова.
 

 

Примеры

№	Входные данные	Выходные данные	Пояснение
1	8 13	2	Высота двух башен - 10 метров и 15 метров соответственно. Таким образом, мы видим, что глубина снежного покрова составляет 2 метра.
2	54 65	1

 

Весельчак У любит дарить алмазных черепашек. У него в сумке лежат черепашки либо трех цветов: розовый, белый и зеленый, либо четырех цветов: розовый, белый, зеленый и желтый. Он по очереди дарил черепашек из сумки, цвет i-й черепашки был Si. Цвета представлены следующим образом: P - розовый, W - белый, G - зеленый, Y - желтый. Если количество цветов черепашек в сумке было три, выведите Three; если цветов было четыре, выведите Four. 

Входные данные
В первой строке записано число N (\(1<=N<=100\)) - количество Черепашек, которое вынимал Весельчак У. Во второй строке содержатся N символов Si - цвета, вынимаемых черепашек. Каждый символ Si равен P, W, G или Y. Всегда существуют такие i, j и k, что Si = 'P', Sj = 'W' и Sk = 'G'.

Выходные данные
Если количество цветов черепашек в сумке было три, выведите Three; если цветов было четыре, выведите Four. 

 

Примеры

№	Входные данные	Выходные данные
1	6 G W Y P Y W	Four
2	9 G W W G P W P G G	Three
3	8 P Y W G Y W Y Y	Four

Алиса и Боб управляют роботом. У каждого из них есть по одной кнопке, которая управляет роботом. Алиса начала удерживать кнопку через A секунд после запуска робота и отпустила кнопку  через B секунд после запуска. Боб начал удерживать кнопку через C секунд после запуска и отпустил кнопку через D секунд после запуска. Сколько секунд Алиса и Боб удерживали свои кнопки одновременно?

Входные данные
На вход 4 целых числа: A, B, C и D (\(1<=A<B<=100\), \(1<=C<D<=100\)).

Выходные данные
Выведите продолжительность времени (в секундах), в течение которого Алиса и Боб удерживали свои кнопки одновременно.
 

 

Примеры

№	Входные данные	Выходные данные	Пояснения
1	0 75 25 100	50	Алиса начала удерживать кнопку через 0 секунд после запуска робота и отпустила ее через 75 секунд после запуска. Боб начал удерживать кнопку через 25 секунд после запуска и отпустил ее через 100 секунд после запуска. Следовательно, время, когда они оба удерживали свои кнопки, составляет 50 секунд от 25 секунд после запуска до 75 секунд после запуска.
2	0 33 66 99	0	Алиса и Боб не удерживали кнопки одновременно, поэтому ответ - ноль секунд.
3	10 90 20 80	60

 

Дано целое число N (\(1<=N<=10^{10}\)).
Для двух положительных целых чисел A и B определим \(F (A, B)\) как большее из двух: 
- количество цифр в десятичной записи числа A;
- количество цифр в десятичной записи числа B.
Например, \(F (3,11) = 2\), поскольку 3 состоит из одной цифры, а 11 - из двух.
Найдите минимальное значение \(F (A, B)\) среди всех пар положительных целых чисел A и B, таких что \(N = A \cdot B\).

Входные данные
На вход подается целое число N (\(1<=N<=10^{10}\)).

Выходные данные
Выведите на экран ответ на задачу.
 

 

Примеры

№	Входные данные	Выходные данные	Пояснение
1	10000	3	\(F(A,B) \) имеет минимальное значение при \((A,B)=(100,100)\).
2	1000003	7	Есть две пары A и B, таких чтобы выполнялость условие задачи: \((1,1000003)\) и \((1000003,1)\). Для этих пар, \(F(1,1000003)=F(1000003,1)=7\).
3	9876543210	6

 

Громозека любит соревнования по программированию. Сегодня он примет участие в конкурсе в STCoder. На этой площадке используются 24-часовые часы. Например, 21:00. обозначается как «21 o'clock».
Текущее время - A часов, а соревнование начнется ровно через B часов. Определите время начала соревнования? Ответ дайте в 24-часовом формате.

Входные данные
Во входной строке содержится два целых числа A и B (\(0<=A,B<=23\)), записанных через один пробел.

Выходные данные
Выведите час начала конкурса в 24-часовом формате.
 

 

Примеры

№	Входные данные	Выходные данные
1	9 12	21
2	19 0	19
3	23 2	1

 

Дан массив из N различных натуральных чисел от 1 до N. Сортировка массива по возрастанию "пузырьком" работает следующим образом. Сначала сравниваются первый и второй элемент, и, если первый больше второго, то они меняются местами. Затем та же процедура производится со вторым и третьим элементом, …, с предпоследним и последним. Затем эта процедура снова повторяется с первым и вторым, со вторым и третьим, …, с предпоследним и последним элементами. И так (N – 1) раз.

Сортировка «с конфеткой» выполняется по тем же правилам, но дополнительно задан список пар чисел, которые не меняются друг с другом ни при каких условиях (в таком случае сортирующий получает конфетку за то, что пропускает соответствующий обмен). Например, наличие в списке пары (4,1) обозначает, что если в какой-то момент рядом окажутся числа 4 и 1 или 1 и 4, и по алгоритму сортировки их нужно будет поменять местами, то обмена не произойдет, а сортирующий получит конфетку.

Требуется провести сортировку «с конфеткой» данного массива и выдать результат сортировки.

Входные данные
Сначала вводится число N — количество чисел в массиве, затем N чисел — элементы массива. Далее задается число M — количество пар чисел, за которые дают конфетку, а затем M пар чисел. Если в списке есть пара (i,j), то и за пару (j,i) также дают конфетку.

1 ≤ N ≤ 5000, 0 ≤ M ≤ 10000.

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

Примеры

№	Входные данные	Выходные данные
1	4 1 4 2 3 2 4 3 1 2	1 2 4 3

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

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

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

Входные данные
Сначала на вход программы поступают числа N — количество залов (1≤N≤400) и K — количество туннелей (1≤K≤20000). Далее вводится K пар чисел, каждая пара описывает номера залов, соединяемых туннелем (по туннелю можно перемещаться в обе стороны). Между двумя залами может быть несколько туннелей. Туннель может соединять зал с самим собой. Далее следует число M (1≤M≤400) — количество роботов. Затем вводятся M чисел, задающих номера залов, где вначале расположены роботы. В одном зале может быть несколько роботов.

Выходные данные
Выведите минимальное время в минутах, через которое роботы могут собраться вместе. Если роботы никогда не смогут собраться вместе, выведите одно число –1 (минус один).

Примеры

№	Входные данные	Выходные данные
1	4 5 1 2 2 3 3 4 1 4 1 3 3 1 2 4	1
2	3 2 1 2 2 3 2 1 3	1

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

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

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

Входные данные
Сначала на вход программы поступают числа N и M (1 < N <= 100, 1 <= M <= 5000) – количество солдат в роте и количество пар солдат, про которых прапорщик знает, кто из них выше. Далее идут эти пары чисел A и B по одной на строке (1 <= A,B <= N), что означает, что, по мнению прапорщика, солдат A выше, чем B. Не гарантируется, что все пары чисел во входных данных различны.

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

Примеры

№	Входные данные	Выходные данные
1	4 5 1 2 2 3 3 4 1 4 4 1	No

Автомат обрабатывает десятичное натуральное число N по следующему алгоритму.
1. Строится двоичная запись числа.
2. К полученному числу справа дописывается 0, если в числе единиц больше, чем нулей, и 1 в обратном случае.
3. К полученному числу справа дописывается бит четности (0, если количество единиц четное, и 1 в обратном случае).
4. Полученное число переводится в десятичную систему счисления и является результатом работы автомата.
При каком наибольшем значении N результатом работы будет число, не превышающее 155?

Автомат обрабатывает десятичное натуральное число N по следующему алгоритму.
1. Строится двоичная запись числа,
2. К полученному числу справа дописывается 0, если в числе единиц больше, чем нулей, и 1 в обратном случае.
3. Действие 2 повторяется еще раз.
4. Из середины двоичного числа убирается 2 разряда, если количество разрядов получилось четным, и 3 разряда, если нечетным.
5. Полученное число переводится в десятичную систему счисления и является результатом работы автомата.
Сколько различных значений может получиться в результате работы, если автомат обработает все значения N, которые принадлежат отрезку [100; 200] ?

Черепашка ползет по полу, который уложен квадратной плиткой со стороной A см. Начало пути Черепахи в точке X. Черепашка успела проползти расстояние D см, прежде чем хозяин взял ее на руки. Определите сколько клеток (частично или целых) успела проползти Черепашка.

Входные данные
Первая строка содержит число A – длина стороны одной плитки. Вторая строка содержит число X - координата точки, с которой Черепашка начала свой путь. Третья строка - число D - расстояние, которое проползла Черепаха. Ось OX направлена вправо. Крайняя плитка в ряду, по которому ползет Черепашка находится в начале координат. Все числа целые, не превосходящие \(2\cdot10^9 \), числа A, D – положительные, число X – положительное или равно 0.

Выходные данные
Вывести одно число – количество плиток, которые Черепашка полностью или частично успела проползти.
Считается, что Черепашка проползла плитку, если условно проведенная линия пути Черепашки имеет ненулевую длину, то есть касание линии пути и края плитки не считается.

 

Примеры

№	Входные данные	Выходные данные	Пояснение
1	10 15 35	4	Сторона плитки (сторона клетки на рисунке) А = 10. Черепашка начала движение с координаты Х = 15, и прошла 35. Черепаха прошла полностью или частично 4 плитки.

 

Для хранения текста в памяти компьютера отводится целое число байт. Текст занимает N бит. Какое минимальное число байт потребуется для хранения данного текста? Напишите программу.

Входные данные
Вводится целое число N. 

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

Примеры

№	Входные данные	Выходные данные
1	8	1
2	9	2

 
 

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

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

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

Входные данные
В первой строке входного файла записано целое число N (1 ≤ N ≤ 10⁵) - количество папок. Во второй строке записаны N целых чисел a₁, a₂, ..., a_N (0 ≤ a_i ≤ 10⁵) - количество дипломов в каждой из папок.

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

Примечание
В первом примере Иван может открыть и просмотреть папку 2 за 2 секунды и, не найдя там диплома, понять, что диплом находится в папке 1.

Во втором примере Иван за 2 секунды просмотрит папку 1, потом за 2 секунды просмотрит папку 4, а если ни в одной из них диплома не встретилось, он поймет, что диплом в папке 3.

Примеры

№	Входные данные	Выходные данные
1	2 2 1	2
2	4 1 0 2 1	4

Магазины в рекламных целях часто устраивают распродажи. Так, например,одна из крупных сетей магазинов канцелярских товаров объявила два рекламных предложения: "купи N одинаковых товаров и получи еще один товар бесплатно"и "купи K товаров по цене K−1 товара".

Для проведения олимпиады организаторам требуется распечатать условия для участников, на что уходит очень много бумаги. Каждая пачка стоит B рублей. Какое максимальное количество пачек бумаги можно приобрести на A рублей, правильно используя рекламные предложения?

Входные данные
Во входном файле записаны целые числа N, K, A и B (1 ≤ N ≤ 100, 2 ≤ K ≤ 100, 1 ≤ A ≤ 10⁹, 1 ≤ B ≤ 10⁹), разделенные пробелами.

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

Примечание
В первом примере, дважды используя второе рекламное предложение, можно купить 8 пачек бумаги, заплатив за 6.

Во втором примере рекламными предложениями воспользоваться нельзя.

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

Примеры

№	Входные данные	Выходные данные
1	4 4 13 2	8
2	3 4 8 3	2
3	3 4 7 1	9