Темы --> Информатика --> Алгоритмы
    Задачи на моделирование(78 задач)
    Арифметические алгоритмы(240 задач)
    Алгоритмы поиска(155 задач)
    Алгоритмы сортировки(194 задач)
    Динамическое программирование(355 задач)
    Алгоритмы на графах(319 задач)
    Перебор(154 задач)
    Игры и выигрышные стратегии(33 задач)
    Вычислительная геометрия(216 задач)
    Эвристические методы(30 задач)
    Алгоритмы на строках(45 задач)
    Пересечение множеств(10 задач)
    Жадный алгоритм(71 задач)
    Теория расписаний(5 задач)
    Обработка текста(31 задач)
    Дата и время(14 задач)
---> 1657 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 179 180 181 182 183 184 185 >> Отображать по:
#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
#1967
Транспортировка
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

К очередной Летней компьютерной школе было решено подготовить кружки как для школьников, так и для всех преподавателей.

Имея привычку делать важные дела в самый последний момент, дизайнер закончил работу над макетом за два дня до начала школы. Ещё день уйдёт у завода-изготовителя на то, чтобы изготовить кружки и нанести на них изображение. На то, чтобы довезти кружки от завода-изготовителя до ЛКШ, остаётся всего 24 часа.

Заказ на 10000000 экземпляров кружек (а именно столько заказали организаторы), конечно же, за один рейс не увезти. Однако, за первый рейс хочется привезти максимальное количество кружек. Для перевозки был заказан один большегрузный автомобиль. Но есть один нюанс: на некоторых дорогах установлено ограничение на вес автомобиля. Поэтому если автомобиль нагрузить кружками под завязку, то, возможно, не удастся воспользоваться самым коротким маршрутом, а придётся ехать в объезд. Может случиться даже так, что из-за этого грузовик не успеет доехать до лагеря вовремя, а этого допустить никак нельзя. Итак, сколько же кружек можно погрузить в автомобиль, чтобы успеть привезти этот ценный груз вовремя, и не нарушая правил дорожного движения?

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

В первой строке находятся числа n (1≤n≤500) и m - количество узловых пунктов дорожной схемы и количество дорог, соответственно. В следующих m строках находится информация о дорогах. Каждая дорога описывается в отдельной строке следующим образом. Сначала указаны номера узловых пунктов, которые соединяются данной дорогой, потом время, которое тратится на проезд по этой дороге, и, наконец, максимальный вес автомобиля, которому разрешено ехать по этой дороге. Известно, что все дороги соединяют различные пункты, причем для каждой пары пунктов есть не более одной дороги, непосредственно их соединяющей. Все числа разделены одним или несколькими пробелами. 

Узловые пункты нумеруются числами от 1 до n. При этом завод по производству кружек имеет номер 1, а ЛКШ - номер n. Время проезда по дороге задано в минутах и не превосходит 1440 (24 часа). Ограничение на массу задано в граммах и не превосходит одного миллиарда. Кроме того, известно, что одна кружка весит 100 грамм, а пустой грузовик -  3 тонны.

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

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

Примеры
Входные данные
3 3
1 2 10 3000220
2 3 20 3000201
1 3 1 3000099
Выходные данные
2
#1972
Первый ход
  

Дима и Катя играют в следующую игру: каждому игроку дается набор из N карточек, на которых написаны натуральные числа от 1 до N включительно. Ходы делаются одновременно. За один ход каждый игрок выбирает какую-то карточку, которую он будет использовать (естественно, не сообщая об этом сопернику). Выбранные игроками карточки открываются, и сумма выигрыша (или проигрыша) каждого определяется по специальной таблице, которая известна игрокам заранее. Карточки, которые были использованы в предыдущих ходах, в игру не возвращаются.

Пример таблицы для N=4 показан на рисунке: в первом столбце перечислены возможные ходы Димы, в первой строке – возможные ходы Кати. На пересечении строки и столба записана сумма выигрыша Димы (если число положительное) или сумма его проигрыша (если число отрицательное).

 

1

2

3

4

1

5

0

1

-9

2

-2

-4

8

-6

3

9

-10

6

3

4

5

1

-1

-3

Определите оптимальный первый ход для Димы (указание: используйте маскиминный критерий).

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

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

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

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

Примеры
Входные данные
2
4 -8
-1 2
Выходные данные
2
#1973
k-й ход
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Дима и Катя продолжают играть в игру, описанную в задаче A (задача №1972) . В данный момент каждый из них уже сделал (k-1) ходов. При этом Катя, с ее феноменальной памятью, прекрасно помнит, какие карточки использовал Дима (и, конечно же, Катя знает какие карточки использовала она сама).

Определите оптимальный k-й ход для Кати (указание: используйте маскиминный критерий).

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

Cначала вводится число N (натуральное, не менее 2 не превосходит 20), затем вводится N строк по N чисел в каждой – таблица сумм выигрышей для Кати. Числа в таблице целые, по модулю не превосходят 1000. Затем вводится число k – номер текущего хода (натуральное, не менее двух, не превосходит N). После этого следуют две строки по (k-1) числу в каждой: первая строка – карточки, которые уже использовал Дима, вторая строка – карточки, которые использовала Катя. Гарантируется, что описания использованных карточек корректны (натуральные числа, не превосходят N, никакое число в строке не повторяется).

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

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

Примеры
Входные данные
2
-1 8
9 -6
2
1
1
Выходные данные
2
Страница: << 179 180 181 182 183 184 185 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест