Темы --> Информатика --> Алгоритмы
    Задачи на моделирование(78 задач)
    Арифметические алгоритмы(240 задач)
    Алгоритмы поиска(155 задач)
    Алгоритмы сортировки(194 задач)
    Динамическое программирование(355 задач)
    Алгоритмы на графах(319 задач)
    Перебор(154 задач)
    Игры и выигрышные стратегии(33 задач)
    Вычислительная геометрия(216 задач)
    Эвристические методы(30 задач)
    Алгоритмы на строках(45 задач)
    Пересечение множеств(10 задач)
    Жадный алгоритм(71 задач)
    Теория расписаний(5 задач)
    Обработка текста(31 задач)
    Дата и время(14 задач)
---> 1657 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 258 259 260 261 262 263 264 >> Отображать по:
#111423
Поиск шаблона
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

Шаблоном называется любая непустая строка, состоящая из маленьких латинских букв и символов "*".

Будем говорить, что строка T подходит под шаблон P, если в P можно символы "*" так заменить на последовательности букв латинского алфавита (возможно, пустые), что в итоге получится строка T. К примеру, строка aadbc походит под шаблон a*b*c, т.к. можно первую звездочку заменить на последовательность букв ad, а вторую — на пустую последовательность, в результате чего получится искомая строка.

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

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

Первая строка входных данных содержит шаблон P, длиной не более 100 символов. Вторая строка содержит исходную строку T, длиной не более 100 000 символов. Все строки имеют длину не менее одного символа.

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

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

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

Входные данные
aaaa
aaaa
Выходные данные
4
Входные данные
a*a
aaaaaa
Выходные данные
6
Входные данные
*a*b*c*
abacabadabacaba
Выходные данные
15

#111426
Раздел имущества
  
Темы: [meet in the middle]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

В этой задаче входные данные записаны в файле exchange.in, вывод нужно записать в файл exchange.out.

Вася — профессиональный юрист, и сейчас он рассматривает очередное дело о разделе имущества. Всего имеется N наследников, каждый из них имеет значимость Ri. Богатый дедушка оставил им состояние в размере L иностранных тугриков. Логично раздать наследство пропорционально значимости, в этом случае i-ый наследник получит иностранных тугриков. Однако, наследники очень привередливы, поэтому наследник желает получить кругленькую сумму, т.е. ту, которая делится на Si.

Чтобы выполнить просьбу наследников, Вася может округлять числа Ai до ближайшего, делящегося на Si (в случае, если делимость не имеет места). При этом, Вася сам выбирает, округлить очередное число вниз или вверх. Пусть Bi означает, сколько в итоге получит очередной наследник. Так как Вася — честный человек, он хочет минимизировать . В случае нескольких вариантов, он выбирает тот, при котором будет наименьшей.

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

В первой строке входных данных содержится два целых числа N и L — количество наследников и размер состояния, соответственно (1 ≤ N ≤ 30, 1 ≤ L ≤ 109). В следующей строке содержатся значимости наследников Ri (). В следующей строк содержатся числа Si (1 ≤ Si ≤ 109).

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

Выведите единственное число — искомую оптимальную сумму .

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

Входные данные
2 250
1 2
100 150
Выходные данные
250
Входные данные
3 1000
25 25 50
34 77 52
Выходные данные
989
Входные данные
3 10
1 1 0
50 50 50
Выходные данные
0

#111427
Студенческие годы
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

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

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

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

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

Все работы пронумерованы числами от 1 до T, где T = K1 + ... + KN, первые K1 работ относятся к первому предмету, следующие K2 ко второму предмету и т.д.

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

В первой строке входных данных содержится одно число N — количество предметов (1 ≤ N ≤ 500). Далее содержатся числа Ki — число лабораторных работ по соответствующему предмету (1 ≤ Ki ≤ 100).

В следующей строке содержится T целых чисел pj — времена выполнения соответствующих работ (1 ≤ pj ≤ 10 000).

В последней строке содержится T целых чисел wj, обозначающих коэффициенты сложности соответствующих работ (1 ≤ wj ≤ 10 000).

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

(student.in, student.out) В первой строке выведите одно число — искомую минимальную величину взяток. В следующей строке выведите перестановку чисел от 1 до T, обозначающих порядок выполнения работ в оптимальном расписании. Помните, что Вася сначала должен изучить какой-то один предмет целиком, а только потом приступить к следующему и также изучать его целиком. В случае, если существует несколько решений, выведите любое из них.

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

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

#111473
Кубики
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Мальчик Вася очень любит строить башни из кубиков. К сожалению, во время последней игры он увлёкся и потерял все кубики, кроме двух. Однако Вася не стал унывать и придумал новое развлечение. Заметив, что на каждой грани кубиков написано по одной цифре, он научился выкладывать двузначные числа из оставшихся игрушек. Вскоре мальчику стало интересно, сколько идущих подряд чисел, начиная с единицы, он сможет выложить с помощью двух кубиков. Помогите Васе найти ответ — такое максимальное число K, что все числа от 1 до K включительно можно получить, используя два оставшихся кубика.

Поскольку в игре используются оба кубика, числа, меньшие 10, Вася выкладывает с ведущими нулями (так, единицу можно получить, выбрав грань первого кубика с цифрой 0 и второго — с цифрой 1). Помните, что Вася умный мальчик: он знает, что перевернутый кубик с цифрой 6 позволяет получить цифру 9, и наоборот.

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

На вход подаются две строки, каждая из которых содержит 6 цифр, написанных на гранях соответствующего кубика.

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

Выведите максимально возможное число K. В случае, если даже число 1 получить невозможно, требуется вывести 0.

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

Входные данные
0 1 2 3 4 5
0 6 7 8 9 2
Выходные данные
10
#111474
Числа и цифры
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Дано натуральное число N. Требуется написать программу, которая находит такое минимальное число M, произведение цифр которого равно N.

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

Вводится целое число N (1 ≤ N ≤ 2·106) .

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

Выведите на экран одно число M  ≥ 10 или фразу «No solution». Число M должно начинаться со значащей цифры (не с нуля).

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

Входные данные
20
Выходные данные 
45
Входные данные 
1
Выходные данные
11
Страница: << 258 259 260 261 262 263 264 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест