#562

Стозначные числа

Темы: [Условный оператор (if)] [Цикл for]

Источники: [ Командные олимпиады, Школьная командная олимпиада ФМШ № 2007 г.Москвы, 10-11 классы, 2007-2008, Задача D ]

Требуется сравнить два 100-значных числа.

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

На вход программы поступают два 100-значных натуральных числа \(A\) и \(B\). Каждое число вводится на отдельной строке.

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

Если \(A\)>\(B\), то выведите “>” (один символ без кавычек).
Если \(A\)<\(B\), то выдайте “<”.
Если \(A\)=\(B\), выдайте “=”.

Комментарий

В примерах числа 111…1 и 222…2 состоят из 100 знаков.

Примеры

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

1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
2222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222

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

#563

Парты

Темы: [Цикл for] [Условный оператор (if)]

Источники: [ Командные олимпиады, Школьная командная олимпиада ФМШ № 2007 г.Москвы, 10-11 классы, 2007-2008, Задача E ]

Сколько понадобится парт, чтобы рассадить \(A\) школьников, если за одну парту можно посадить одного или двух человек? За каждой партой должен сидеть хотя бы один человек. Укажите все варианты.

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

Вводится одно натуральное число — \(A\) ( 1 ≤ \(A\) ≤ 10000)

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

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

Примеры

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

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

3 4 5 6

#564

Кони

Темы: [Условный оператор (if)]

Источники: [ Командные олимпиады, Школьная командная олимпиада ФМШ № 2007 г.Москвы, 10-11 классы, 2007-2008, Задача F ]

Сколько существует клеток на доске размером \(K\)x\(K\) таких, что шахматный конь, стоящий на этой клетке, бьет ровно \(N\) полей?

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

Вводятся натуральные числа \(K\) и \(N\) (1 ≤ \(K\) ≤ 100, 2 ≤ \(N\) ≤ 8).

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

Выведите количество клеток, с которых конь бьет ровно \(N\) полей.

Комментарий

на доске 8x8 конь бьет ровно два поля только с угловых клеток, их 4.

Примеры

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

8 2

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

#565

Игра со спичками

Темы: [Простые игры]

Источники: [ Командные олимпиады, Школьная командная олимпиада ФМШ № 2007 г.Москвы, 10-11 классы, 2007-2008, Задача G ]

Двое играют в следующую игру. Из кучки спичек за один ход игрок вытягивает либо 1, либо 2, либо 1000 спичек. Выигрывает тот, кто забирает последнюю спичку. Кто выигрывает при правильной игре?

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

Вводится одно натуральное число — \(N\) ( 1≤ \(N\) ≤ 10000) начальное количество спичек в кучке.

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

Выведите 1, если выигрывает первый игрок (тот, кто ходит первым), или 2, если выигрывает второй игрок.

Примеры

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

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

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

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

#572

Пузырьки 1D

Темы: [Динамическое программирование на таблицах]

Источники: [ Командные олимпиады, ВКОШП, 2007, Задача A ]

Задан одномерный массив "пузырьков", каждый из которых может быть одного из четырех цветов. Можно уничтожить группу подряд идущих пузырьков одинакового цвета и получить за это \(K^2\) очков (K - количество пузырьков). Требуется уничтожить все пузырьки и подсчитать максимальную сумму очков.

Сережа - большой любитель игр на сотовом телефоне. Недавно он скачал из интернета новую игру "Пузырьки 1D". Опишем правила игры.

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

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

Например, ниже на рисунке показана позиция, содержащая 10 пузырьков. В ней четыре группы, содержащие 3, 2, 4 и 1 пузырек, соответственно. Если взорвать группу, содержащую четыре пузырька, то игрок получит 16 очков, и верхние 5 пузырьков опустятся вниз. В получившейся позиции 6 пузырьков, и две группы по 3 пузырька в каждой.

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

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

На вход программы поступает одна строка, состоящая из букв "R", "G", "B и "Y", описывающая начальную позицию. Буквы задают цвета пузырьков в порядке просмотра сверху вниз ("R" означает красный пузырек, "G" – зеленый, "B" – синий, а "Y" – желтый). В заданной позиции не менее двух и не более 100 пузырьков.

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

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

Пояснения

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

Примеры

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

RRRGGRRRRG

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

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

RB

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