Страница: << 1 2 3 4 5 6 7 >> Отображать по:
#1184
Найдите последовательность
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

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

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

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

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

В первой строке входного файла записано число N — длина исходной последовательности (1≤N≤1000). Во второй строке идет сама последовательность. Последовательность состоит только из заглавных латинских букв.

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

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

Примеры

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

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

Комментарии

4

MAMA

A

Рассматриваются строки MAMA, AMA, MA, A. Выигрышная строка A

4

ALLO

ALLO

Выигрышной является исходная строка

5

BBABB

ABB


#1187
Сложите конфетки
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

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

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

Если останется одна кучка, то Вася все конфеты съест сам, а если две — то конфеты из первой кучки он съест сам, а из второй кучки отдаст Пете.

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

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

Начальное расположение кучек конфет будет описываться K парами чисел Ai, Ni, которые обозначают, что на столе выложено подряд Ni кучек конфет, по Ai конфет в каждой.

Во входном файле задано сначала число K (1≤K≤105). Затем идет K пар чисел Ai, Ni (1≤Ai≤100, 1≤Ni≤108). Общее количество кучек так же не превысит 108.

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

В выходной файл выведите сначала 1 или 2 — количество кучек конфет, которые останутся в конце игры. Затем выведите соответственно одно или два числа — количества конфет в оставшихся кучках.

Комментарии к примерам тестов

1. Исходно конфеты расположены в следующих кучках: 2 кучки по 2 конфеты, две кучки из 3-х конфет и одна из 2-х:
2 2 3 3 2
Далее по 2 конфеты перекладывается из 1 и 5кучек во 2 и 4, при этом и 1 и 5 кучки становятся пустыми, т.е. на столе остается только 3 кучки:
4 3 5
Теперь по 4 конфеты перекладываются из 1 и 3 кучек во 2-ю и на столе остается две кучки, игра заканчивается с результатом 11 1

2. Изначальноу нас 7 кучек по 1 конфете в каждой. После первого перекладывания получится следующая конфигурация:
2 1 1 1 1 2
После второго:
3 1 3
После третьего останется одна кучка с 7 конфетами.

3. Изначально имеется 6 кучек:
1 2 3 4 5 5
После первого перекладывания получим:
3 3 4 6 4
После второго:
6 4 9 1
После третьего:
5 5 10
Наконец, получим:
15 5

Примеры
Входные данные
3
2 2
3 2
2 1
Выходные данные
2
11 1
Входные данные
1
1 7
Выходные данные
1
7
Входные данные
5
1 1
2 1
3 1
4 1
5 2
Выходные данные
2
15 5
#1620
Субботник
  

В классе учатся N человек. Классный руководитель получил указание направить на субботник R бригад по С человек в каждой.

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

Числом неудобства бригады будем называть разность между ростом самого высокого и ростом самого низкого членов этой бригады (если в бригаде только один человек, то эта разница равна 0). Классный руководитель решил сформировать бригады так, чтобы максимальное из чисел неудобства сформированных бригад было минимально. Помогите ему в этом!

Рассмотрим следующий пример. Пусть в классе 8 человек, рост которых в сантиметрах равен 170, 205, 225, 190, 260, 130, 225, 160, и необходимо сформировать две бригады по три человека в каждой. Тогда одним из вариантов является такой:

1 бригада: люди с ростом 225, 205, 225

2 бригада: люди с ростом 160, 190, 170

При этом число неудобства первой бригады будет равно 20, а число неудобства второй — 30. Максимальное из чисел неудобств будет 30, и это будет наилучший возможный результат.

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

Сначала вводятся натуральные числа N, R и C — количество человек в классе, количество бригад и количество человек в каждой бригаде (1 ≤ R∙C ≤ N ≤ 100 000). Далее вводятся N целых чисел — рост каждого из N учеников. Рост ученика — натуральное число, не превышающее 1 000 000 000.

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

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

Примеры
Входные данные
8 2 3
170
205
225
190
260
130
225
160
Выходные данные
30
#1756
Динокод
  

Строки формируются по правилу: S1 = a, Si = Si-1 + chr(i) + Si-1. Необходимо по данной строке найти максимальное i, такое что данная строка является подстрокой Si

Учёные любят присваивать идентификаторы всему живому. Поэтому они обозначают динозавров I эпохи кодом `a'. Динозавры II эпохи, как произошедшие от динозавров I эпохи, именуются кодом `aba'. Ящеры III эпохи – `abacaba', и вообще если \(C\)(\(n\)) – код динозавров эпохи \(n\), то \(C\)(\(n\)+1)=\(C\)(\(n\))+\(S\)(\(n\)+1)+\(C\)(\(n\)) , где \(S\)(\(n\)+1) – символ очередной (\(n\)+1-ой) эпохи. Символ первой эпохи – `a' , символ второй эпохи – `b', затем `c', `d', …, `x', `y', `z'. После букв учёные почему-то перешли на цифры, и обозначили эпохи с XXVII по XXXVI соответственно `0', `1', …, `9' .

После XXXVI эпохи динозавры вымерли, и уже утверждённое название XXXVII эпохи (`α') отдали астрономам для нового кратера на Марсе.

Астрономы (в знак благодарности) нашли какую-то отдалённую звезду с огромной статуей динозавра, похожего на земные аналоги. Экспедиция, посетившая указанную звезду, нашла под статуей надпись, очевидно, с кодом этого динозавра. Впрочем, часть надписи стёрлась. Теперь учёные хотят максимально завысить древность находки. Для этого нужно определить, в коде динозавров какой эпохи – самой древней из подходящих – встречается данный образец (как подстрока). Такую задачу не по силам решить даже астрономам.

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

На первой и единственной строке входного файла находится непустая строка, состоящая из символов `a', …, `z', `0', …, `9'. Длина строки не превосходит 100.

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

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

Примеры
Входные данные
a
Выходные данные
1 0
Входные данные
bae
Выходные данные
5 13
#1768
Два прямоугольника
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
На прямоугольном поле есть закрашенные и незакрашенные клетки. Требуется определить, можно ли разбить закрашенные клетки на два прямоугольника, со сторонами, параллельными осям координат.

Недавно один известный художник-абстракционист произвел на свет новый шедевр – картину «Два черных непересекающихся прямоугольника». Картина представляет собой прямоугольник \(m\)×\(n\), разбитый на квадраты 1×1, некоторые из которых закрашены любимым цветом автора – черным. Федя – не любитель абстрактных картин, однако ему стало интересно, действительно ли на картине изображены два непересекающихся прямоугольника. Помогите ему это узнать. Прямоугольники не пересекаются в том смысле, что они не имеют общих клеток.

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

Первая строка входного файла содержит числа \(m\) и \(n\) (1 ≤ \(m\), \(n\) ≤ 200). Следующие \(m\) строк содержат описание рисунка. Каждая строка содержит ровно \(n\) символов. Символ «.» обозначает пустой квадрат, а символ «#» – закрашенный.

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

Если рисунок можно представить как два непересекающихся прямоугольника, выведите в первой строке «YES», а в следующих m строках выведите рисунок в том же виде, в каком он задан во входном файле, заменив квадраты, соответствующие первому прямоугольнику на символ «a», а второму – на символ «b». Если решений несколько, выведите любое.

Если же этого сделать нельзя, выведите в выходной файл «NO».

Примеры
Входные данные
2 1
#
.
Выходные данные
NO
Входные данные
2 2
..
##
Выходные данные
YES
..
ab
Входные данные
1 3
###
Выходные данные
YES
abb
Входные данные
3 1
.
#
#
Выходные данные
YES
.
a
b
Страница: << 1 2 3 4 5 6 7 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест