Темы --> Информатика --> Алгоритмы --> Динамическое программирование
    Рекуррентные последовательности(10 задач)
    Динамическое программирование: один параметр(49 задач)
    Динамическое программирование: два параметра(183 задач)
    Динамическое программирование в играх(9 задач)
    Динамическое программирование на графах(25 задач)
    Динамическое программирование по профилю(20 задач)
    Динамика по подмножествам(13 задач)
---> 85 задач <---
Источники --> Личные олимпиады
    Олимпиады сайта(17 задач)
    Школьная личная олимпиада ФМШ №2007 г. Москвы(7 задач)
    Золотая середина (Новосибирск)(10 задач)
    Нижегородская олимпиада школьников(42 задач)
    Московская олимпиада школьников(168 задач)
    Индивидуальная олимпиада по информатике и программированию (ИОИП)(22 задач)
    Открытая олимпиада школьников(173 задач)
    Украинские олимпиады(61 задач)
    Республиканская олимпиада школьников (Беларусь)(6 задач)
    Жаутыковские олимпиады(8 задач)
    Всероссийская олимпиада школьников(304 задач)
    Международные олимпиады(32 задач)
    Central European Olympiad in Informatics (4 задач)
    Интернет-олимпиады(2 задач)
    COCI(36 задач)
    Турнир Архимеда(36 задач)
    Baltic Olympiad in Informatics(10 задач)
Страница: << 5 6 7 8 9 10 11 >> Отображать по:
#1226
Игра с шашками
  

Поле для игры с шашками – длинная горизонтальная полоска, размеченная на клетки. Клетки пронумерованы от 1 до N (2 < N < 10000). На поле стоят две шашки. Позиция каждой из шашек определяется номером клетки, в которой она стоит.

Играют двое. Каждый игрок при своем ходе должен переместить любую шашку на одну, две или три клетки в сторону клетки 1 (сделать 1, 2 или 3 шага). Перепрыгивать через стоящую впереди шашку нельзя, но можно сдваивать шашки. На сдваивание шашек   тратится два шага из трех доступных игроку (то есть сдваивать можно либо шашки, стоящие  вплотную друг к другу, либо шашки, между которыми есть только одна пустая клетка). Если произошло сдваивание – ход передается другому игроку, который делает ход  одной шашкой , оставив другую на месте.

Выигрывает тот, кто сдвоит шашку на клетке с номером 1.

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

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

В первой строке содержится число K (0 < K < 10) – количество начальных позиций. В последующих K строках содержится по два целых числа от 3 до 10000, разделенных пробелом – номера начальных позиций шашек на игровом поле.

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

Выводится K строчек – ответ на каждую начальную позицию.

Если при заданной начальной позиции шашек в игре не достигается выигрыш (при правильной игре противника) выводится слово NO.

Если выигрыш достижим, то выводится первый ход начинающего игру, который приводит к его выигрышу независимо от того, как играет соперник. Ход описывается парой чисел  i, j через пробел, означающих, что выигрышный ход игрока – это перемещение шашки из клетки с номером i в клетку с номером  j. Например, «4 3» означает, что игрок двигает шашку, стоящую в клетке 4, на одну клетку в сторону клетки 1.

Примечание
Ответ на тест из примера:
NO
11 10
12 11
NO
15 12
12 10
Примеры
Входные данные
6
3 10
3 11
4 12
5 8
9 15
3 12
Выходные данные
YES
NO
#1254
Монотонная последовательность
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

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

Петя пытается добиться того, чтобы последовательность чисел, написанных на карточках стала строго монотонной (возрастающей или убывающей). Для этого ему разрешается совершать следующие действия: выбрать два числа l и r, такие что 1 ≤ l≤ r ≤ n и перевернуть каждую из карточек от карточки номер l до карточки номер r.

Напомним, что последовательность c1, . . . , cn называется строго возрастающей, если выполняются неравенства c1 < c2 < … < cn, и строго убывающей, если выполняются неравенства c1 > c2 > … > cn.

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

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

Первая строка входного файла содержит целое число n (1 ≤ n ≤ 100000). Каждая из последующих n строк описывает одну карточку и содержит два числа — ai написано на ее лицевой стороне, а bi — на оборотной. Все числа ai и bi находятся в диапазоне от 1 до 109.

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

В первой строке выходного файла выведите минимальное число действий, которое должен совершить Петя. Если Петина цель недостижима, то выведите в выходной файл число -1.

Комментарий к примеру тестов

В первом примере для достижения цели Петя может перевернуть карточки со второй по третью.

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

Примеры
Входные данные
3
3 4
1 2
4 1
Выходные данные
1
Входные данные
3
1 2
4 1
3 4
Выходные данные
-1
Входные данные
6
1 2
3 2
2 3
4 5
6 5
5 6
Выходные данные
2
#1277
Несчастливые номера
  

Обычно автобусный билет с номером, состоящим из 6 цифр, считается счастливым, если сумма первых трех цифр его номера была равна сумме трех последних. Школьник Вася очень любил получать счастливые билеты, однако это случалось не так часто. Поэтому для себя он изменил определение счастливого билета. Счастливым он считал тот номер, сумма некоторых цифр которого равнялась сумме оставшихся цифр. В его представлении билет с номером 561743 счастливый, так как 5 + 1 + 4 + 3 = 6 + 7.

Вася вырос, но по привычке в номерах различных документов пытается найти признаки счастливого номера ☺. Для этого он расширил свое определение счастливого номера на n-значные номера лицевых счетов и других документов, состоящих из цифр от 0 до k (1 ≤ k ≤ 9). Номер документа он называет счастливым, если сумма некоторых цифр этого номера равняется сумме оставшихся. Остальные номера для него несчастливые. К сожалению, несмотря на расширенное понимание “счастья”, несчастливых номеров остается еще много...

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

Входной файл unlucky.in содержит описание нескольких видов номеров. Каждый вид номеров определяется значениями n и k. Для данного входного файла вы должны создать соответствующий ему выходной файл и отправить его на проверку жюри.

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

Входной файл содержит несколько пар значений n и k, каждая пара записана в отдельной строке.

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

Для каждой пары значений n и k входного файла выведите в соответствующей строке выходного файла искомое количество несчастливых билетов или 0, если такое число вам получить не удалось. Количество строк во входном и выходном файлах должно совпадать.

Примечание

За правильное решение задачи для каждого вида номеров вы получите 5 баллов. Так, представленный в примере выходной файл соответствует 15 баллам.

При сдаче на проверку выходного файла во время тура вы будете получать одно из двух сообщений:

  • Presentation Error — если файл не соответствует формату вывода. В этом случае файл не принимается на проверку.
  • Accepted — если файл формату вывода соответствует. В этом случае файл принимается на проверку. Проверка правильности ответов в выходном файле осуществляется только после окончания тура.
Содержание файла unlucky.in:
4 1
7 1
3 2
6 2
22 2
7 9
8 7
9 6
8 8
12 9
20 9
20 3
17 5
16 7
15 9
19 5
26 9
100 3
99 4
50 5
#1342
Стековый калькулятор
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

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

Над стеком может выполняться операция проталкивания. Применение этой операции приводит к записи числа на вершину стека. Перед этим, если в стеке уже были числа, то каждое из них перемещается в ячейку с номером на единицу больше. Если в стеке уже находится K чисел, то выполнение операции проталкивания невозможно.

Калькулятор позволяет выполнять арифметические операции. Они применяются к числам, хранящимся во второй и первой ячейках стека. Результат операции записывается в первую ячейку стека, а число из второй ячейки удаляется. После этого, если третья ячейка непуста, то число из неё переписывается во вторую, если есть число в четвертой ячейке — оно переписывается в третью и так далее до последней занятой ячейки, которая становится пустой. Для выполнения арифметической операции в стеке должно быть хотя бы два числа. Например, при выполнении операций сложения или умножения, значения соответственно суммы или произведения чисел из первой и второй ячеек помещаются на вершину стека. Операция вычитания выполняется так: из содержимого второй ячейки стека вычитается содержимое первой ячейки.

Известно, что калькулятор неисправен. Из цифровых клавиш работает только клавиша «1». Нажатие этой клавиши приводит к проталкиванию в стек числа 1. Например, попытка набрать число 11, два раза нажав клавишу «1», приводит к тому, что в стек два раза проталкивается число 1. Из операций работают только сложение (клавиша «+»), умножение (клавиша «*») и вычитание (клавиша «-»). Если в результате вычитания получено отрицательное число, то калькулятор зависает.

Легко заметить, что на индикаторе возможно получить произвольное натуральное число. Например, чтобы получить число 3, необходимо дважды нажать клавишу «1», затем клавишу «+» (на индикаторе после этого появится число 2), затем один раз нажать клавишу «1» и один раз — клавишу «+». При K > 2 того же результата можно достичь иначе, трижды нажав клавишу «1», а затем два раза клавишу «+». Дополнительно используя операции умножения и вычитания, в некоторых случаях число N можно получить быстрее, чем сложив N единиц.

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

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

В единственной строке входного файла записаны два натуральных числа — N и K (1 ≤ N ≤ 109, 2 ≤ K ≤ 100).

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

В первой строке выходного файла выведите минимальное количество нажатий клавиш, необходимых для получения числа N. Если число нажатий не превосходит 200, то дополнительно выведите во второй строке оптимальную последовательность нажатий, приводящих к появлению данного числа на индикаторе.

Последовательность необходимо выводить без пробелов. Клавиши обозначаются символами «1» — протолкнуть число 1 в стек, «+» — выполнить операцию сложения, «*» — выполнить операцию умножения, «-» — вычесть из значения второй ячейки стека значение первой ячейки.

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

Примечания

Решения, корректно работающие при N ≤ 100 и K ≤ 10, будут оцениваться из 40 баллов.

Решения, корректно работающие при N ≤ 106 и K ≤ 100, будут оцениваться из 80 баллов.

Примеры
Входные данные
1 2
Выходные данные
1
1
Входные данные
9 3
Выходные данные
11
11+1+11+1+*
#1374
Снова ка-штаны
  
Требуется найти набор, остаток от деления которого на размер рюкзака минимален.

В этой задаче, как и в задаче B, Петя снова собирает своего M-лапого Зверя на прогулку (однако количество лап у Зверя в этой задаче может быть до 1000). Снова ему мама оставила N штанов, имеющих соответственно K1, K2, …, KN штанин. Однако тетерь Петя хочет надеть на Зверя штаны так, чтобы выполнялись следующие условия:

  • на каждой лапе была надета хотя бы одна штанина (гарантируется, что это всегда возможно),
  • количество штанин, надетых на самую «утепленную» лапу, должно как можно меньше отличаться от количества штанин, надетых на самую легко одетую лапу (когда количество штанов, одетых на разные лапы, сильно отличается, Зверь испытывает дискомфорт),
  • в отличие от задачи B Петя не обязан надеть на Зверя все имеющиеся штаны — какие-то из них можно оставить дома.

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

Помогите Пете – напишите программу, которая для каждой лапы укажет, сколько штанин должно быть на нее надето.

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

Вводится сначала число M, а затем число N (1 ≤ M ≤ 1000, 1 ≤ N ≤ 100). Далее вводятся N чисел Ki, обозначающих число штанин у оставленных мамой штанов (1 ≤ Ki ≤ M). Сумма всех Ki не меньше, чем M.

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

Выведите M строк, в i-ой строке должно быть выведено количество штанин, надетых на i-ю лапу. Если искомых ответов несколько, то выведите любой из них.

Комментарии к примерам тестов

1. Первые штаны надеты на лапу 1;
вторые штаны не используем;
третьи штаны надеты на лапы 2, 3 и 4.
Таким образом, на всех лапах по 1 штанине.

2. Первые штаны надеты на лапы 1, 2 и 3;
вторые штаны надеты на лапы 1 и 4.
Таким образом, количество штанов на самой «утепленной» лапе (это лапа номер 1) – 2, а на остальных лапах по одной штанине, т.е. количество штанин на разных лапах отличается на один. Нетрудно заметить, что в этом примере нельзя одеть зверя так, чтобы на всех лапах было поровну штанин, поэтому этот ответ является оптимальным.

Примеры
Входные данные
4 3
1 2 3
Выходные данные
1
1
1
1
Входные данные
4 2
3 2
Выходные данные
2
1
1
1
Страница: << 5 6 7 8 9 10 11 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест