Информатика

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

Входные данные
Сначала задано число N — количество элементов в массиве (1 ≤ N ≤ 10000). Далее через пробел записаны N ненулевых чисел - элементы массива. Массив состоит из целых чисел.

Выходные данные
Необходимо вывести слово YES, если существует пара соседних элементов с одинаковыми знаками. В противном случае следует вывести слово NO.

Примеры

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

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

push_front
Добавить (положить) в начало дека новый элемент. Программа должна вывести ok.

push_back
Добавить (положить) в конец дека новый элемент. Программа должна вывести ok.

pop_front
Извлечь из дека первый элемент. Программа должна вывести его значение.

pop_back
Извлечь из дека последний элемент. Программа должна вывести его значение.

front
Узнать значение первого элемента (не удаляя его). Программа должна вывести его значение.

back
Узнать значение последнего элемента (не удаляя его). Программа должна вывести его значение.

size
Вывести количество элементов в деке.

clear
Очистить дек (удалить из него все элементы) и вывести ok.

exit
Программа должна вывести bye и завершить работу.
Гарантируется, что количество элементов в деке в любой момент не превосходит 100. Перед исполнением операций pop_front, pop_back, front, back программа должна проверять, содержится ли в деке хотя бы один элемент. Если во входных данных встречается операция pop_front, pop_back, front, back, и при этом дек пуст, то программа должна вместо числового значения вывести строку error.

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

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

Примеры

№	Входные данные	Выходные данные
1	push_back 1 back exit	ok 1 bye
2	size push_back 1 size push_back 2 size push_front 3 size exit	0 ok 1 ok 2 ok 3 bye

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

push_front
Добавить (положить) в начало дека новый элемент. Программа должна вывести ok.

push_back
Добавить (положить) в конец дека новый элемент. Программа должна вывести ok.

pop_front
Извлечь из дека первый элемент. Программа должна вывести его значение.

pop_back
Извлечь из дека последний элемент. Программа должна вывести его значение.

front
Узнать значение первого элемента (не удаляя его). Программа должна вывести его значение.

back
Узнать значение последнего элемента (не удаляя его). Программа должна вывести его значение.

size
Вывести количество элементов в деке.

clear
Очистить дек (удалить из него все элементы) и вывести ok.

exit
Программа должна вывести bye и завершить работу.
Гарантируется, что количество элементов в деке в любой момент не превосходит 100. Все операции pop_front, pop_back, front, back всегда корректны.

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

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

Примеры

№	Входные данные	Выходные данные
1	push_back 1 back exit	ok 1 bye
2	size push_back 1 size push_back 2 size push_front 3 size exit	0 ok 1 ok 2 ok 3 bye

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

push n
Добавить в очередь число n (значение n задается после команды). Программа должна вывести ok.
pop
Удалить из очереди первый элемент. Программа должна вывести его значение.
front
Программа должна вывести значение первого элемента, не удаляя его из очереди.
size
Программа должна вывести количество элементов в очереди.
clear
Программа должна очистить очередь и вывести ok.
exit
Программа должна вывести bye и завершить работу.
Перед исполнением операций front и pop программа должна проверять, содержится ли в очереди хотя бы один элемент. Если во входных данных встречается операция front или pop, и при этом очередь пуста, то программа должна вместо числового значения вывести строку error.

Входные данные
Вводятся команды управления очередью, по одной на строке

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

Примеры

№	Входные данные	Выходные данные
1	push 1 front exit	ok 1 bye
2	size push 1 size push 2 size push 3 size exit	0 ok 1 ok 2 ok 3 bye

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

push n
Добавить в очередь число n (значение n задается после команды). Программа должна вывести ok.
pop
Удалить из очереди первый элемент. Программа должна вывести его значение.
front
Программа должна вывести значение первого элемента, не удаляя его из очереди.
size
Программа должна вывести количество элементов в очереди.
clear
Программа должна очистить очередь и вывести ok.
exit
Программа должна вывести bye и завершить работу.
Гарантируется, что набор входных команд удовлетворяет следующим требованиям: максимальное количество элементов в очереди в любой момент не превосходит 100, все команды pop и front корректны, то есть при их исполнении в очереди содержится хотя бы один элемент.

 
Входные данные
Вводятся команды управления очередью, по одной на строке

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

Примеры

№	Входные данные	Выходные данные
1	size push 1 size push 2 size push 3 size exit	0 ok 1 ok 2 ok 3 bye

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

push n
Добавить в стек число n (значение n задается после команды). Программа должна вывести ok.
pop
Удалить из стека последний элемент. Программа должна вывести его значение.
back
Программа должна вывести значение последнего элемента, не удаляя его из стека.
size
Программа должна вывести количество элементов в стеке.
clear
Программа должна очистить стек и вывести ok.
exit
Программа должна вывести bye и завершить работу.
Перед исполнением операций back и pop программа должна проверять, содержится ли в стеке хотя бы один элемент. Если во входных данных встречается операция back или pop, и при этом стек пуст, то программа должна вместо числового значения вывести строку error.
Входные данные
Вводятся команды управления стеком, по одной на строке

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

Примеры

№	Входные данные	Выходные данные
1	size push 1 size push 2 size push 3 size exit	0 ok 1 ok 2 ok 3 bye

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

push n
Добавить в стек число n (значение n задается после команды). Программа должна вывести ok.
pop
Удалить из стека последний элемент. Программа должна вывести его значение.
back
Программа должна вывести значение последнего элемента, не удаляя его из стека.
size
Программа должна вывести количество элементов в стеке.
clear
Программа должна очистить стек и вывести ok.
exit
Программа должна вывести bye и завершить работу.
Входные данные
Команды управления стеком вводятся в описанном ранее формате по 1 на строке.

Гарантируется, что набор входных команд удовлетворяет следующим требованиям: максимальное количество элементов в стеке в любой момент не превосходит 100, все команды pop и back корректны, то есть при их исполнении в стеке содержится хотя бы один элемент.

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

Примеры

№	Входные данные	Выходные данные
1	push 3 push 14 size clear push 1 back push 2 back pop size pop size exit	ok ok 2 ok ok 1 ok 2 2 1 1 0 bye

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

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

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

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

В первой строке входных данных записано одно натуральное число N, не превосходящее 500. В следующих N строках описаны стопки контейнеров: сначала записано число k_i – количество контейнеров в стопке, а затем k_i чисел – виды товара в контейнерах в данной стопке, снизу вверх. В каждой стопке вначале не более 500 контейнеров (в процессе переноса контейнеров это ограничение может быть нарушено).

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

Программа должна вывести описание действий автопогрузчика: для каждого действия напечатать два числа – из какой стопки брать контейнер и в какую стопку класть. (Обратите внимание, что минимизировать количество операций автопогрузчика не требуется.) Если задача не имеет решения, необходимо вывести одно число 0. Если контейнеры изначально правильно размещены по стопкам, то  выводить ничего не нужно.

Примеры

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

В постфиксной записи (или обратной польской записи) операция записывается после двух операндов. Например, сумма двух чисел A и B записывается как A B +. Запись B C + D * обозначает привычное нам (B + C) * D, а запись A B C + D * + означает A + (B + C) * D. Достоинство постфиксной записи в том, что она не требует скобок и дополнительных соглашений о приоритете операторов для своего чтения.

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

Выходные данные
Необходимо вывести значение записанного выражения.

Примеры

№	Входные данные	Выходные данные
1	8 9 + 1 7 - *	-102

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

Пустая последовательность явлется правильной, если A – правильная, то последовательности (A), [A], {A} – правильные. Если A и B – правильные последовательности, то последовательность AB – правильная.

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

Выходные данные
Если данная последовательность правильная, то программа должна вывести строку yes, иначе строку no.

Примеры

№	Входные данные	Выходные данные
1	()[]	yes

Чтобы затруднить снятие денег, банк на планете Крокрыс разрешает своим клиентам снимать только одну из следующих сумм за одну операцию:
- 1 крокрыскоин (действующая монета на планете Крокрыс);
- 6 крокрыскоинов, 36 (=6²) крокрыскоинов, 216(=6³) крокрыскоинов , ...;
- 9 крокрыскоинов, 81 (=9²) крокрыскоинов, 729(=9³) крокрыскоинов , ...
Сколько минимум операций требуется, чтобы вывести ровно N крокрыскоинов?
Невозможно повторно внести снятые вами деньги.

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

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

 

Примеры

№	Входные данные	Выходные данные	Пояснения
1	127	4	При снятии 1 + 9 + 36 + 81 получится снять 127 крокрыскоина за 4 операции.
2	3	3	1+1+1 = 3, всего 3 операции
3	44852	16

 

Все конкурсы SilverTests Beginner Coder (STBCoder) помечаются как STBC001, STBC002, ... с первого раунда до 999-го раунда. После раунда STBC999 возникает проблема: как должны быть помечены следующие раунды? В конце концов, было решено для раундов с 1000-го по 1999-й отмечать как STBD000, STBD001, ..., STBD999. Раунды с 2000 по 2999 отмеаются как STBE000, STBE001, ..., STBE999 и т.д., Каждый раз меняется последняя буква (STBC, STBD, STBE, ..., STBL). Таким образом помечаны раунды с 1 по 9999. 
Вам дано целое число N от 1 до 9999 (включительно). Выведите первые четыре символа ярлыка N-го тура конкурса SilverTests Begginer Coder.

Входные данные
На вход целое число N (\(1<=N<=9999\)).

Выходные данные
Выведите первые три символа ярлыка N-го тура конкурса SilverTests Beginner Coder.

 

Примеры

№	Входные данные	Выходные данные
1	999	STBC
2	1000	STBD
3	6345	STBI

 

Напишите программу, переводящую число из двоичной системы счисления в шестнадцатеричную

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

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

Примеры

№	Входные данные	Выходные данные
1	10100	14

Есть N человек. Имя i-го человека - Si . Мы хотим выбрать трех человек, чтобы выполнялись следующие условия:
- имя каждого выбранного человека начинается с M, А, R, С или Н; 
- среди выбранных людей нет людей, имена которых начинаются с одной буквы.
Сколько существует таких способов выбрать трех человек, не обращая внимания на порядок?

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

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

 

Примеры

№	Входные данные	Выходные данные	Пояснение
1	5 MASHIKE RUMOI OBIRA HABORO HOROKANAI	2	Трех людей можно выбрать такими способами: - MASHIKE, RUMOI, HABORO - MASHIKE, RUMOI, HOROKANAI Ответ: 2
2	4 ZZ ZZZ Z ZZZZZZZZZZ	0
3	5 CHOKUDAI RNG MAKOTO AOKI RINGO	7

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

Входные данные
На вход подается целое число N (\(1<=N<=1000\)) - количество всех студентов.

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

 

Примеры

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

 

У Громозеки есть N часов. Стрелка i-х часов (\(1<=i<=N\)) поворачивается на 360 ° ровно за Ti секунд. Изначально стрелка всех часов стоит на месте и направлена прямо вверх. Громозека запускает все часы одновременно. Через сколько секунд стрелка всех часов снова укажет прямо вверх?

Входные данные
В первой строке записано целое число N (\(1<=N<=100\)). В следующих N строках записаны целые числа Ti (\(1<=T_i<=10^{18}\)), по одному числу в строке. 

Выходные данные
Выведите на экран ответ. Гарантируется, что ответ не превышает \(10^{18}\).
 

 

Примеры

№	Входные данные	Выходные данные	Пояснение
1	2 2 3	6	У нас есть двое часов. Время, когда стрелка каждых часов указывает вверх, выглядит следующим образом: Часы 1: 2, 4, 6, ... секунд после начала. Часы 2: 3, 6, 9, ... секунд после начала. Таким образом, требуется 6 секунд, пока стрелки обоих часов снова не укажут прямо вверх.
2	5 2 5 10 1000000000000000000 1000000000000000000	1000000000000000000

 

Дан набор из N элементов. Значение i-го элемента (\(1<=i<=N\)) равно vi. Из данного набора выбирается не менее A и не более B элементов. Найти максимально возможное среднее арифметическое значений выбранных элементов. Кроме того, найти количество способов выбора элементов, чтобы среднее значение выбранных элементов было максимальным.

Входные данные
В первой строке задается три целых числа через пробел: N (\(1<=N<=50\)), A и B (\(1<=A,B<=N\)). В следующих N строках записаны целые числа vi (\(1<=v_i<=10^{15}\)), по одному числу в строке.

Выходные данные
Выведите две строки.
Первая строка должна содержать максимально возможное среднее арифметическое значений выбранных элементов. Вывод следует считать правильным, если абсолютная или относительная погрешность не превышает \(10^{-6}\). 
Вторая строка должна содержать количество способов выбора элементов, чтобы среднее значение выбранных элементов было максимальным.
 

 

Примеры

№	Входные данные	Выходные данные	Пояснения
1	5 2 2 1 2 3 4 5	4.500000 1	Среднее значение выбранных элементов будет максимальным при выборе четвертого и пятого элементов. Следовательно, первая строка вывода должна содержать 4.5. Нет другого способа выбрать элементы, чтобы среднее значение было 4,5, и поэтому вторая строка вывода должна содержать 1.
2	4 2 3 10 20 10 10	15.000000 3	Может быть несколько способов выбора элементов, чтобы среднее значение было максимальным.
3	5 1 5 1000000000000000 999999999999999 999999999999998 999999999999997 999999999999996	1000000000000000.000000 1

 

План эвакуации из здания нарисован в виде плоскости xy. В здании N кабинетов и M лестниц, ведущих к выходу. Координаты i-го кабинета (\( 1<=i<=N\)) - \((a_i, b_i)\), а координаты лестниц с номером j (\( 1<=j<=M\)) - \((c_j, d_j)\). Во время пожарной тревоги, все люди, находящиеся в конкретном кабинете должны эвакуироваться по ближайшей лестнице. Ближайшая лестница определяется по Манхэттенскому расстоянию между двумя точками \((x_1, y_1)\) и \((x_2, y_2)\) по формуле \(|x_1-x_2| + |y_1-y_2|\). Здесь \(|x|\) обозначает абсолютное значение x. Если для кабинета есть несколько ближайших лестниц, то эвакуироваться необходимо по лестнице с наименьшим индексом. 
Определите по какой лестнице должны эвакуироваться люди, находящиеся в каждом кабинете.

Входные данные
В первой строке задаются два целых числа N и M (\(1<=N,M<=50\)).   Далее идет N строк по два целых числа в кажой строке - координаты \((a_i, b_i)\), затем M строк по два целых  числа в кажой строке - координаты \((c_i, d_i)\). \(-10^8<=a_i ,b_i,c_j,d_j<=10^8\). 

Выходные данные
Выведите N строк. В i-й строке (\( 1<=i<=N\)) должен быть указан индекс лестницы, по которой эвакуируются из i-го кабинета.
 

 

Примеры

№	Входные данные	Выходные данные
1	2 2 2 0 0 0 -1 0 1 0	2 1
2	3 4 10 10 -10 -10 3 3 1 2 2 3 3 5 3 5	3 1 2
3	5 5 -100000000 -100000000 -100000000 100000000 100000000 -100000000 100000000 100000000 0 0 0 0 100000000 100000000 100000000 -100000000 -100000000 100000000 -100000000 -100000000	5 4 3 2 1

 

Пусть a₁ = 2, a₂ = 3, a_n = a_1·a₂·...·a_n-1 – 1 при n ≥ 3. Назовем числа ai псевдопростыми. Для заданного натурального числа X нужно ответить на вопрос: можно ли X однозначно представить в виде произведения псевдопростых чисел (представления, отличающиеся только порядком множителей, считаются одинаковыми), и, если можно — выдать разложение.<

Входные данные
Вводится одно натуральное число X, 1 < X ≤ 10⁹.

Выходные данные
Выведите псевдопростые числа, произведение которых равно X, в произвольном порядке. Если разложения не существует или оно не единственно, выдать 0.
 

Примеры

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

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



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

Входные данные
Вводится одно число N — количество уровней в фигуре (1 ≤ N ≤ 100000).

Выходные данные
Выведите  количество треугольников в такой фигуре.

Примеры

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