Темы --> Информатика
    Язык программирования(952 задач)
    Алгоритмы(1657 задач)
    Структуры данных(279 задач)
    Интерактивные задачи(17 задач)
    Другое(54 задач)
---> 2656 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 252 253 254 255 256 257 258 >> Отображать по:
#1943
Электронное табло
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

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

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

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

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

Первая строка содержит текущую последовательность цифр, вторая строка — последовательность, которую требуется получить. Гарантируется, что обе последовательности не пустые, имеют одинаковую длину, не превосходящую 100 000, и состоят только из нулей и единиц. Цифры в строках записаны подряд (без пробелов).

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

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

Примеры
Входные данные
1101
1011
Выходные данные
2
Входные данные
0000
1111
Выходные данные
4
#1944
Заливка
  

Максимальное время работы на одном тесте:

2 секунды

Максимальный объем используемой памяти:

64 мегабайта

 

 

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

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

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

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

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

Вводятся два натуральных числа N, M (1 ≤ N ≤ 100, 1 ≤ M ≤ 100) — количество строк и столбцов у таблицы, соответствующей данному изображению. В следующих N строках содержатся по M символов. В i‑й строке и j-м столбце стоит 0, если соответствующая клетка белая, и 1, если чёрная.

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

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

Пример

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

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

3 5

10101

01010

10101

3
#1949
Старая стена
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

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

 Инспекция составила отчет, в котором для каждого вертикального ряда блоков указана его нынешняя высота. Военное министерство сразу же заинтересовалось вопросом: где находится самый уязвимый участок стены? Участок  стены является уязвимым, если он целиком состоит из подряд идущих рядов, высота которых меньше 5 и ограничен с обеих сторон либо границами стены, либо рядами блоков максимальной высоты.

 
Например, у стены на рисунке два уязвимых участка (второй и третий ряд; пятый и шестой ряды, считая слева). Длина стены на рисунке равна 6.

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

Для стены на рисунке второй участок более уязвимый чем первый.

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

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

Cначала вводится число N – длина стены (натуральное, не превышает 1000), затем следует N целых чисел в диапазоне от 0 до 5 – высота соответствующего вертикального ряда. Гарантируется, что на стене есть хотя бы один уязвимый участок.

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

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

Примеры
Входные данные
6
5 3 2 5 2 2
Выходные данные
5 6 6
Входные данные
10
5 1 5 2 5 3 5 5 0 2
Выходные данные
9 10 8
#1950
Накопительная скидка
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

В некотором интернет - магазине действует N накопительных скидок. Когда сумма, уплаченная каким-то клиентом за его предыдущие заказы превысит x1, начинает действовать скидка a1 (это означает что за последующие покупки клиент платит на a1 процентов меньше). Затем, когда суммарная стоимость покупок превысит x2 начинает действовать скидка a2. И так далее. Когда суммарная стоимость покупок превысит xn, то начинает действовать скидка an. Известно, что a1<a2<…<an.

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

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

Сначала вводится число N (натуральное, не превышает 10) – общее количество скидок. Затем вводится N пар чисел: величина скидки ai (натуральное, не превышает 100) и сумма, которую надо превысить чтобы получить такую скидку xi (натуральное, не превышает 100000). Далее вводится число K – количество товаров, которые хочет приобрести покупатель (натуральное, не более 100). Затем следует K чисел – цена каждого товара (натуральное, не более 1000). Гарантируется, что каждая следующая скидка дается после большей суммы, чем предыдущая, также гарантируется что величина каждой следующей скидки больше предыдущей. Гарантируется, что все цены в интернет-магазине кратны 100.

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

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

Пример:

Исходные данные

Результат

2

2 10

4 100

2

100

100

198

(обратите внимание, что скидка начисляется только после превышения суммы, поэтому после первой покупки скидка равна не 4, а 2%)

3

2 10

4 20

8 30

1

1000

1000

(скидка начисляется только после совершения покупки)

 

#1951
Долговые расписки
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

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

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

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

Cначала вводится число N – количество джентльменов (натуральное, не превышает 100, не менее 2), затем вводится число K – количество долговых расписок (натуральное, не превышает 10000), после этого следует K троек чисел: номер джентльмена взявшего в долг, номер джентльмена давшего деньги и сумма. Номера джентльменов в расписках – натуральные числа, не превышающие N. Сумма - натуральное число, не превышает 100. Гарантируется, что ни один джентльмен не брал в долг сам у себя.

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

Выведите N чисел – суммы, которые должны получить соответствующие джентльмены. Выведите положительное число, если этот джентльмен должен получить деньги от других, отрицательное – если он должен отдать деньги другим.

Примеры
Входные данные
2 3
1 2 10
1 2 20
1 2 20
Выходные данные
-50 50
Входные данные
3 1
3 1 100
Выходные данные
100 0 -100
Страница: << 252 253 254 255 256 257 258 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест