Страница: << 1 2 3 4 5 Отображать по:
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
Выписаны двоичные числа от 1 до N. В каждом из них красным выделяется каждый k-ый ноль (ведущие нули не учитываются). Необходимо подсчитать суммарное количество красных нулей.

Толик только что узнал, что на свете существует двоичная система счисления. Обрадованный этим, он записал в столбик двоичные формы чисел 1, 2, …, \(n\). Получились числа 1, 10, 11, 100, 101, 110, 111, …

После этого он стер все написанные единицы и стал изучать расположение нулей. Он выбрал число \(k\) и в каждой строке, идя слева направо, выделил красным цветом каждый \(k\)-ый ноль, начиная с первого. Таким образом, оказались выделенными нули с номерами 1, \(k\) + 1, 2\(k\) + 1, … Например если \(k\) = 2, \(n\) = 56 то получились бы такие строки:

(красные нули выделены жирным шрифтом и подчеркнуты)

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

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

Во входном файле содержатся числа \(n\) и \(k\) (1 ≤ \(n\) < \(2^{31}\), 1 ≤ \(k\) ≤ 30).

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

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

Примеры
Входные данные
5 1
Выходные данные
4
Входные данные
23 3
Выходные данные
20
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Антон - большой любитель компьютерных игр. Совсем недавно вышла новая игра Heroes of Keyboard and Mouse, и он, конечно же, сразу ее купил и установил на свой компьютер. Эта игра относится к жанру квестов, и поэтому ее прохождение сводится к последовательному выполнению ряда заданий (квестов).

Один из квестов, над которым Антон бьется уже не первый день состоит в том, что требуется открыть замок. Замок состоит из \(n\) шестеренок, стоящих в ряд - \(i\)-ая из шестеренок имеет \(s_i\) зубцов, на каждом из которых написано число от \(0\) до \(s_i - 1\). Первая шестеренка зацеплена только со второй, вторая зацеплена с первой и третьей, третья - со второй и четвертой, ..., \((n-1)\)-ая - с \((n-2)\)-ой и \(n\)-ой, \(n\)-ая только с \((n-1)\)-ой.

На замке имеется \(n\) окошечек и \(n\) ручек - в \(i\)-ое окошко можно видеть число, написанное на одном из зубцов \(i\)-ой шестеренки, а с помощью \(i\)-ой ручки можно поворачивать \(i\)-ую шестеренку. При этом числа на шестеренках расположены таким образом, что если до поворота \(i\)-ой из них по часовой стрелке на одно деление в \(i\)-ом окошке было видно число \(x\), то после поворота будет видно число \((x+1) \bmod s_i\). Аналогично, после поворота против часовой стрелки на одно деление вместо числа \(x\) будет видно число \((x-1+s_i) \bmod s_i\). Разумеется, если шестеренку повернуть по часовой стрелке, то непосредственно зацепленные с ней шестеренки повернутся против часовой стрелки, и наоборот, если шестеренку повернуть против часовой стрелки, то они повернутся по часовой стрелке. Слева на рис.1 показано положение шестеренок до поворота первой из них по часовой стрелке, справа на рис. 1 показано положение шестеренок после указанного поворота. Более толстыми линиями нарисован тот зубец шестеренки, число на котором видно в соответствующее окошко замка.

Изначально замок находится в состоянии, в котором в \(i\)-ое окошко видно число \(a_i\). Для того, чтобы его открыть, необходимо перевести его в состояние, в котором в \(i\)-ое окошко видно число \(b_i\).

С помощью \(i\)-ой ручки можно поворачивать \(i\)-ую шестеренку. Разумеется, если повернуть \(i\)-ую шестеренку, то придут в движение и все шестеренки, с которыми она соединена - напрямую или через другие шестеренки. Поворот любой шестеренки на одно деление занимает одну секунду. Кроме этого, если \(i\)-ая шестеренка находится в таком состоянии, что в \(i\)-ое окошко видно число \(b_i\) (то есть, она находится в положении, соответствующем требуемому состоянию замка), то ее можно вдавить, нажав на ее ручку. В результате этого \(i\)-ая шестеренка перестает быть соединенной с \((i-1)\)-ой и \((i+1)\)-ой (если, конечно, они существуют). Вдавленная шестеренка остается в таком состоянии навсегда. На то, чтобы нажать на ручку и вдавить шестеренку требуется \(k\) секунд. На рис. 2 слева показано положение шестеренок до вдавливания второй из них, а справа - после вдавливания и после поворота первой по часовой стрелке, а третьей - против. Отметим, что после вдавливания второй шестеренки первая и третья вращаются независимо друг от друга.

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

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

Первая строка входного файла содержит два целых числа: \(n\) и \(k\) (\(1 \le n \le 25\), \(1 \le k \le 100\)). Вторая строка входного файла содержит \(n\) чисел: \(s_1\), \(s_2\), ..., \(s_n\) - размеры шестеренок. Все \(s_i\) - целые числа от 3 до 10. Третья строка входного файла содержит \(n\) целых чисел \(a_1\), \(a_2\), ..., \(a_n\) - начальные положения шестеренок (для всех \(a_i\) выполняются неравенства \(0 \le a_i < s_i\)). Четвертая строка входного файла содержит \(n\) целых чисел \(b_1\), \(b_2\), ..., \(b_n\) - требуемые положения шестеренок (для всех \(b_i\) выполняются неравенства \(0 \le b_i < s_i\)).

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

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

Примеры
Входные данные
2 2
3 5
0 0
1 1
Выходные данные
4
Входные данные
3 2
3 3 3
0 0 0
1 1 1
Выходные данные
5
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

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

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

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

В единственной строке входного файла содержится строка, предложенная игрокам. Строка состоит из маленьких латинских букв. Длина строки не превышает 250 символов.

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

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

Примеры
Входные данные
3
uho
Выходные данные
1
Входные данные
6
ababab
Выходные данные
2
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
256 megabytes

Задана последовательность цифр. Определите, можно ли расставить между некоторыми из них знаки "+" и "-", так чтобы получилось заданное число \(M\), но никакие промежуточные вычисления не превосходили по модулю \(10000\).

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

Входные данные содержат две строки: в первой строке - натуральное число \(M\)≤\(20000\), во второй строке - последовательность цифр. Длина входной последовательности не превышает \(200\) символов.

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

Выведите одно слово YES или NO в зависимости от того, есть решение у задачи или нет.

Примеры
Входные данные
2009
20009
Выходные данные
YES
Входные данные
10
000000050049000
Выходные данные
YES
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
6 megabytes

Город N, в отличие от города M, расположен на склоне одного холма. Чистоту улиц этого города обеспечивает единственная поливальная машина. Бензин нынче дорог, поэтому движение муниципального транспорта «в гору» признано слишком расточительным.

Карта города представляет собой прямоугольник, разбитый на H × W клеток, где H и W — высота и ширина карты в клетках соответственно. Часть клеток заняты зданиями, остальные соответствуют улицам и площадям, которые и требуется помыть.

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

Помогите узнать экономному муниципалитету, какое максимальное количество свободных клеток поливальная машина сможет помыть, не поднимаясь при этом в гору? Определите также, какое минимально возможное расстояние ей при этом придётся преодолеть. Считается, что, перемещаясь в соседнюю по горизонтали или вертикали клетку, поливальная машина преодолевает одну единицу расстояния.

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

В первой строке входного файла находятся натуральные числа H и W — высота и ширина карты города (1 ≤ W ≤ 1 000, 1 ≤ H ≤ 1 000). В следующей строке расположено единственное натуральное число K — номер столбца клетки первой строки, в которой поливальная машина начинает движение (1 ≤ K ≤ W). Гарантируется, что эта клетка свободна от зданий.

Каждая из следующих H строк содержит W символов ‘|#|’ и ‘.’, означающих, соответственно, клетки со зданиями и без.

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

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

Примеры тестов

Входные данные
8 8
7
..#....#
##..#...
...#..#.
.##..#..
..#.#...
#.#.#...
#.#...##
##..####
Выходные данные
21 23


Страница: << 1 2 3 4 5 Отображать по:
Выбрано
:
Отменить
|
Добавить в контест