#1631

Язык Мумба-Юмба

Темы: [Строки] [Простые задачи на перебор]

Источники: [ Командные олимпиады, Московская командная олимпиада, 9-11 классы, 2009, Лига Б, Задача F ]

Слова в языке Мумба-Юмба могут состоять только из букв a, b, c, и при этом:

никогда не содержат двух букв b подряд,
ни в одном слове никогда не встречается три одинаковых подслова подряд. Например, по этому правилу в язык Мумба-Юмба не могут входить слова aaa (так как три раза подряд содержит подслово a), ababab (так как три раза подряд содержит подслово ab), aabcabcabca (три раза подряд содержит подслово abc).

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

Напишите программу, которая по данному слову определит, принадлежит ли оно этому языку.

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

Вводится одно слово, состоящее только из строчных букв a, b, c, длины не более 100.

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

Если слово входит в язык Мумба-Юмба, выведите YES, в противном случае выведите NO.

Примеры

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

abca

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

YES

#1632

Операционные системы

Темы: [Пересечение множеств]

Источники: [ Командные олимпиады, Московская командная олимпиада, 9-11 классы, 2009, Лига Б, Задача G ]

Васин жесткий диск состоит из M секторов. Вася последовательно устанавливал на него различные операционные системы следующим методом: он создавал новый раздел диска из последовательных секторов, начиная с сектора номер a_i и до сектора b_i включительно, и устанавливал на него очередную систему. При этом, если очередной раздел хотя бы по одному сектору пересекается с каким-то ранее созданным разделом, то ранее созданный раздел «затирается», и операционная система, которая на него была установлена, больше не может быть загружена.

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

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

Сначала вводятся натуральное число M — количество секторов на жестком диске (1 ≤ M ≤ 10⁹) и целое число N — количество разделов, которое последовательно создавал Вася (0 ≤ N ≤ 1000).

Далее идут N пар чисел a_i и b_i, задающих номера начального и конечного секторов раздела

(1 ≤ a_i ≤ b_i ≤ M).

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

Выведите одно число — количество работающих операционных систем на Васином компьютере.

Input:

10

3

1 3

4 7

3 4

Output:

1

#1633

Пицца

Темы: [Задача о рюкзаке]

Источники: [ Командные олимпиады, Московская командная олимпиада, 9-11 классы, 2009, Лига Б, Задача H ]

Вы решили заказать пиццу с доставкой на дом. Известно, что для клиентов, сделавших заказ на сумму более \(C\) рублей, доставка является бесплатной, при заказе на \(C\) рублей и меньше доставка стоит \(B\) рублей. Вы уже выбрали товара стоимостью \(A\) рублей. В наличии имеются еще \(N\) товаров стоимостью \(d_1, ..., d_N\) рублей, каждый в единственном экземпляре. Их также можно включить в заказ. Как потратить меньше всего денег и получить на дом уже выбранный товар стоимостью \(A\) рублей?

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

Вводятся сначала числа \(A, B, C, N,\) а затем \(N\) чисел \(d_1, ..., d_N\). Все числа целые, \(1 \le A \le 1000, 1 \le B ≤ 1000, 1 \le C \le 1000, 0 \le N \le 1000, 1 \le di \le 1 000 000\).

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

Выведите единственное число – суммарное количество денег, которое придется потратить.

Примечание

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

Примеры

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

10 17 25
5
2 7 5 3 7

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

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

100 1 50
5
5 2 4 3 1

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

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

10 14 25
5
2 7 5 3 7

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

#1634

Спички

Темы: [Арифметические алгоритмы]

Источники: [ Личные олимпиады, Украинские олимпиады, 2005, Задача A ]

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

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

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

Единственная строка входного файла содержит одно целое число \(N\) (1≤\(N\)≤\(10^9\)).

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

Единственная строка выходного файла должна содержать одно целое число – минимальное количество спичек требуемых для составления заданного количества квадратов.

Примеры

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

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

#1635

Альтернативные пути

Темы: [Динамическое программирование]

Источники: [ Личные олимпиады, Украинские олимпиады, 2005, Задача B ]

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

Будем снисходительными к Путнику, считая «хорошими» не только пути, на которых в точности достигается максимально возможная сумма, а еще и пути, сумма которых отличается от максимальной не более чем на \(K\).

Количество «хороших» путей гарантированно не превышает \(10^9\).

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

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

Первая строка входного файла содержит три целых числа \(M\) (2≤\(M\)≤200), N (2≤\(N\)≤200) и \(K\) (0≤\(K\)≤200). Каждая из последующих \(M\) строк содержит \(N\) чисел, записанных в соответствующих клеточках.

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

Первая строка выходного файла должна содержать максимальную возможную сумму; вторая строка – количество маршрутов, сумма чисел которых отличается от максимальной не более чем на \(K\).

Примеры

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

2 3 3
1 9 7
2 5 3

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

20
2

Страница: << 221 222 223 224 225 226 227 >> Отображать по: