Темы --> Информатика --> Алгоритмы
    Задачи на моделирование(78 задач)
    Арифметические алгоритмы(240 задач)
    Алгоритмы поиска(155 задач)
    Алгоритмы сортировки(194 задач)
    Динамическое программирование(355 задач)
    Алгоритмы на графах(319 задач)
    Перебор(154 задач)
    Игры и выигрышные стратегии(33 задач)
    Вычислительная геометрия(216 задач)
    Эвристические методы(30 задач)
    Алгоритмы на строках(45 задач)
    Пересечение множеств(10 задач)
    Жадный алгоритм(71 задач)
    Теория расписаний(5 задач)
    Обработка текста(31 задач)
    Дата и время(14 задач)
---> 1657 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 243 244 245 246 247 248 249 >> Отображать по:
#3783
Abcdefg (полные ограничения)
  
ограничение по времени на тест
0.4 second;
ограничение по памяти на тест
64 megabytes

(Задача отличается от предыдущей исключительно ограничениями на N и M.)

Есть сообщение, записанное в алфавите из N символов. Известно, что 1-й, 2-й, ..., N-й символы алфавита использованы в сообщении f1, f2, ..., fN раз. Его необходимо набрать на M-клавишной клавиатуре, используя способ набора, аналогичный используемому в мобильных телефонах.

На телефоне, клавише 2 сопоставлены буквы abc, клавише 3 — def, и т.д. Для набора текста телефон переводится в специальный режим, в котором одно нажатие на клавишу 2 порождает символ a, 2 подряд нажатия на 2 символ b, 3 подряд символ c; аналогично, одно нажатие 3 порождает d, 2 подряд e и т. д. Если же необходимо набрать 2 подряд буквы a, то нажимают клавишу 2, немного ждут и снова нажимают клавишу 2.

В нашем случае, символы с 1-ого по некоторый K1-ый должны соответствовать 1-ой клавише, с (K1 + 1)-ого по некоторый K2-ой — 2-ой клавише и т. д., до KM = N. Конкретные значения K1, K2, ..., KM - 1 не задаются — их, наоборот, нужно подобрать.

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

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

В первой строке содержатся два числа N и M, во второй — N чисел f1, f2, ..., fN — количества вхождений соответствующего символа. Числа внутри строк разделены одинарными пробелами. 2 ≤ M ≤ 500, 3 ≤ N ≤ 700, M < N, 1 ≤ fi ≤ 1000.

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

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

Примечание

Значение 21 достигается при K1 = 2, K2 = 3 (1-й и 2-й символы сопоставить 1-й клавише, 3-й символ 2-й клавише, 4-й и 5-й символы 3-й клавише). Тогда количество нажатий будет

(3 × 1 + 2 × 2) + (5 × 1) + (7 × 1 + 1 × 2) = 21.

Примеры
Входные данные
5 3
3 2 5 7 1
Выходные данные
21
#3787
Кривая дракона
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Сегодня мальчик Саша на уроке математики узнал про фракталы. Учитель показывал так называемую «кривую дракона». Она представляет собой геометрическую фигуру, которая строится следующим образом: на первом шаге проводится отрезок из начала координатной плоскости в точку (0; 1). Далее на каждом шаге из конца фрактала повторяется уже нарисованная часть фигуры, повернутая на 90 градусов против часовой стрелки (см. рисунок).

После уроков Саша попробовал сам изобразить «кривую дракона», и теперь он хочет знать, в какой точке координатной плоскости он закончил рисовать фрактал, проделав описанные выше N шагов. Требуется написать программу, которая по заданному числу N определяет координаты конца фрактала после выполнения N шагов.

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

Вводится одно целое число N (1 ≤ N ≤ 30).

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

Выведите два числа через пробел — координаты конца фрактала.

Примеры
Входные данные
2
Выходные данные
1 1
Входные данные
4
Выходные данные
2 -2
#3789
Сохранить энергию
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Одна Фруктовая Компания, производящая электронику, решила озаботиться длительностью работы своих смартфонов от аккумулятора.

Выяснилось, что процессор, который они закупают у азиатского поставщика, поддерживает m различных режимов работы, при этом каждая из k операций языка программирования (который Фруктовая Компания использует для написания всех своих программ) может быть выполнена в каждом из режимов. Одновременно процессор может работать только в одном режиме, но перед выполнением каждой из операций можно один раз переключиться в любой другой режим работы.

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

В начале выполнения программы процессор находится в первом режиме, завершиться выполнение программы может при любом режиме процессора.

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

Первая строка содержит три целых числа: число k (1 ≤ k ≤ 100) — количество операций в языке программирования, число m (1 ≤ m ≤ 100) — количество режимов работы, которое поддерживает процессор, и число n (1 ≤ n ≤ 10000) — количество операций в исследуемой программе.

Следующие k строчек содержат по m целых неотрицательных чисел, не превышающих 100. j-е число в i-ой строчке обозначает, сколько энергии тратится на выполнение i-ой операции в j-ом режиме команд.

Далее следует m строчек, содержащих по m целых неотрицательных чисел, не превышающих 100. j-ое число в i-ой строчке обозначает, сколько единиц энергии тратится на переключение процессора с режима i на режим j. Гарантируется, что в i-ой строке i-ое число равно 0.

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

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

Выведите одно число — минимальное количество единиц энергии, необходимое для выполнения программы.

Подзадачи и система оценки

Тесты к этой задаче состоят из трех групп.

  • Тесты из условия, оцениваются в ноль баллов.
  • В тестах этой группы \(n\), \(m\), \(k\) не превосходят 10. Эта группа оценивается в 50 баллов, баллы ставятся только при прохождении всех тестов группы.
  • В тестах этой группы \(m\) не превосходит 10. Эта группа оценивается в 30 баллов, баллы ставятся только при прохождении всех тестов группы и предыдущих групп.
  • В тестах этой группы дополнительные ограничения отсутствуют. Группа оценивается в 20 баллов, баллы ставятся только при прохождении всех тестов этой и предыдущих групп.

Примеры
Входные данные
2 1 4
60
93
0
1 2 1 1
Выходные данные
273
Входные данные
2 2 4
1 10
10 1
0 1
2 0
1 1 2 2
Выходные данные
5
#3798
Минимальный простой делитель числа
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Дано натуральное число \(n>1\). Выведите его наименьший простой делитель.

Решение оформите в виде функции MinDivisor(n). Алгоритм должен иметь сложность \(O(\sqrt{n})\).

Указание. Если у числа \(n\) нет делителя не превосходящего \(\sqrt{n}\), то число \(n\) — простое и ответом будет само число \(n\).

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

Вводится натуральное число.

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

Выведите ответ на задачу.

Примеры
Входные данные
4
Выходные данные
2
Входные данные
5
Выходные данные
5
#3807
Алгоритм Евклида
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Для быстрого вычисления наибольшего общего делителя двух чисел используют алгоритм Евклида. Он построен на следующем соотношении: \(НОД(a, b)=НОД(b, a\bmod b)\).

Реализуйте рекурсивный алгоритм Евклида в виде функции gcd(a, b).

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

Вводится два целых числа.

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

Выведите ответ на задачу.

Примеры
Входные данные
12
14
Выходные данные
2
Входные данные
256
48
Выходные данные
16
Страница: << 243 244 245 246 247 248 249 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест