Темы --> Информатика --> Алгоритмы
    Задачи на моделирование(78 задач)
    Арифметические алгоритмы(240 задач)
    Алгоритмы поиска(155 задач)
    Алгоритмы сортировки(194 задач)
    Динамическое программирование(355 задач)
    Алгоритмы на графах(319 задач)
    Перебор(154 задач)
    Игры и выигрышные стратегии(33 задач)
    Вычислительная геометрия(216 задач)
    Эвристические методы(30 задач)
    Алгоритмы на строках(45 задач)
    Пересечение множеств(10 задач)
    Жадный алгоритм(71 задач)
    Теория расписаний(5 задач)
    Обработка текста(31 задач)
    Дата и время(14 задач)
---> 95 задач <---
Источники --> Командные олимпиады --> Московская командная олимпиада --> 9-11 классы
    2003(8 задач)
    2004(9 задач)
    2005(10 задач)
    2006(10 задач)
    2007(19 задач)
    2008(19 задач)
    2009(18 задач)
    2010(18 задач)
    2011(18 задач)
    2012(19 задач)
    2013(19 задач)
    2014(20 задач)
    2015(21 задач)
    2016(20 задач)
Страница: << 13 14 15 16 17 18 19 >> Отображать по:
#3588
Башня
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Петя в очередной купил себе набор из кубиков. На этот раз он выстроил из них настоящую крепость — последовательность из N столбиков, высота каждого столбика составляет Ai кубиков.

Вскоре ему стало интересно, насколько его крепость защищена от жуликов и воров. Для этого он ввел понятия башни. Башней называется любая последовательность из K столбиков подряд (где K — любимое число Пети). Защищенность башни определяется как суммарная высота всех столбиков этой башни (чем она больше, тем громаднее и ужаснее она кажется), умноженная на минимум высоты столбиков башни (т.к. враги, очевидно, будут пытаться проникнуть через самое слабое место башни). Неприступность крепости определяется как сумма защищенностей каждой из башен.

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

Петя успешно справился со своей задачей, но теперь Правительство Флатландии решило защитить свой горный курорт. Правительство уже построило крепость из кубиков (просто кубики были побольше). Теперь вы должны помочь Правительству посчитать неприступность этой крепости. Единственная трудность состоит в том, что у Правительства было очень много денег, и поэтому крепость была построена очень длинная.

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

В первой строке входного файла содержатся число N — количество столбиков в крепости и число K — любимое число Пети (1 ≤ K ≤ N ≤ 1000). Далее на следующей строке содержатся N целых чисел, обозначающих Ai (1 ≤ Ai ≤ 103).

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

На первой строке выведите число Q — количество башен в оптимальном разбиении. Далее выведите Q чисел — номера первых столбиков каждой башни.

Гарантируется, что в оптимальном разбиении неприступность крепости не превосходит 2 × 109.

Примеры
Входные данные
1 1
1
Выходные данные
1
1
Входные данные
2 1
1 1000
Выходные данные
2
1 2
Входные данные
8 3
1 2 3 4 1 6 7 8
Выходные данные
2
2 6
#3589
Фибоначчиева система счисления
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Напомним, что числами Фибоначчи называется последовательность чисел, получаемая по следующему правилу: f0 = f1 = 1, fk = fk - 1 + fk - 2, где k > 1.

Фибоначчиева система счисления (ФСС) — это позиционная система счисления с алфавитом, состоящим из двух цифр: 0 и 1, а ее базисом является последовательность чисел Фибоначчи 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, … (f0 = 1 в базис не включается). В фибоначчиевой системе, как и во всех позиционных системах счисления, «вес» каждого разряда определяется соответствующим элементом базиса этой системы. Так, 10011fib = 1 × 8 + 0 × 5 + 0 × 3 + 1 × 2 + 1 × 1 = 11. Если не наложить дополнительных ограничений, то представление чисел в такой системе счисления оказывается неоднозначным.

Например, 1110 = 1111fib = 10011fib = 10100fib

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

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

Во входном файле записано единственное число N (1 ≤ N ≤ 2· 109).

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

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

Примеры
Входные данные
5
Выходные данные
1000
Входные данные
11
Выходные данные
10100
#3590
Палиндромика
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

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

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

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

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

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

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

Примеры
Входные данные
3
uho
Выходные данные
1
Входные данные
6
ababab
Выходные данные
2
#3592
Лучшие друзья девушек - это фуллерены
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Развитие химической науки привело к тому, что высшие фуллерены (сложные молекулы углерода в виде шарика или продолговатой трубки) стали недорогими в производстве. Благодаря своим уникальным оптическим свойствам они нашли свое место и в ювелирной промышленности. Ювелирный дом «Кёрл, Крото и Смолли» выпустил уникальную коллекцию украшений из фуллеренов. Украшение продается в виде набора трубок-фуллеренов различной длины, из которых можно составить украшение самостоятельно.

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

Помогите Норме Джин узнать, сколько вечеров она сможет посетить с имеющимся у нее набором фуллереновых трубок. Фуллереновые трубки одинаковой длины считаются различными. Треугольники считаются различными, если они отличаются хотя бы одной трубкой. Треугольники, состоящие из одних и тех же трубок, считаются одинаковыми независимо от порядка трубок.

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

Первая строка входного файла содержит одно число N (1 ≤ N ≤ 100) — количество фуллереновых трубок в наборе Нормы Джин.

Вторая строка содержит N упорядоченных по возрастанию целых чисел Li (1 ≤ Li ≤ 20 000) — длины трубок.

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

Выведите одно целое число — количество вечеров, на которые сможет сходить Норма Джин.

Примеры
Входные данные
4
2 2 3 4
Выходные данные
3
#111267
Сортировка
  
ограничение по времени на тест
0.5 second;
ограничение по памяти на тест
6 megabytes

Учительница по программированию задала Вовочке задачу — отсортировать массив из N чисел от 1 до N по возрастанию :). Вовочка поступает так: он просматривает массив слева направо, и, если замечает два элемента, стоящих рядом, таких, что правый меньше левого, он меняет их местами. Так он поступает, пока массив не будет отсортирован. Но Вовочка — очень ленивый ученик. В какой-то момент ему надоело сортировать числа, и он решил посчитать, сколько ещё описанных выше обменов нужно сделать. Помогите ему.

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

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

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

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

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

Входные данные
5
1 2 5 4 3
Выходные данные
1

Страница: << 13 14 15 16 17 18 19 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест