Темы --> Информатика --> Язык программирования --> Типы данных
    Символы(9 задач)
    Строки(121 задач)
    Целые числа(112 задач)
    Битовые операции(28 задач)
    Логический тип(3 задач)
    Структуры(18 задач)
    Вещественные числа(33 задач)
    Множества(16 задач)
    Словари(21 задач)
---> 17 задач <---
Источники --> Личные олимпиады --> Всероссийская олимпиада школьников
    Муниципальный этап(80 задач)
    Окружная олимпиада(18 задач)
    Региональный этап(109 задач)
    Заключительный этап(97 задач)
Страница: << 1 2 3 4 >> Отображать по:
#3014
Поклейка обоев
  
Темы: [Целые числа]

Пете нужно оклеить обоями стену размером N метров в высоту и M метров в ширину. Для поклейки используются обои, которые продаются рулонами. Каждый рулон имеет ширину 1 метр и длину K метров. Обои клеятся на стену вертикальными полосами (сверху вниз). При этом Петя хочет так поклеить обои, чтобы горизонтальных стыков разных кусков не было (то есть один цельный кусок клеится от потолка до пола). От рулона можно отрезать куски нужного размера (иногда при этом может оставаться кусок, меньшего размера, который поэтому не может быть поклеен, этот кусок идет в отходы).

По данным числам N, M и K определите наименьшее количество рулонов, которое нужно купить Пете, чтобы оклеить всю стену.

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

Вводятся натуральные числа N, M и K (1 ≤ N ≤ 100, 1 ≤ M ≤ 100, N ≤K ≤100).

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

Выведите одно число - количество рулонов, которые должен купить Петя.

Примеры
Входные данные
10
5
25
Выходные данные
3
Входные данные
3
6
9
Выходные данные
2
#3139
Лицензионные ключи
  
Темы: [Строки]

Компания Macrohard выпустила в свет новую версию операционной системы «Frames» («Рамки») и теперь стремится внедрить ее на рынок информационных технологий. Каждая фирма, заказывающая новую версию «Рамок», получает лицензионные ключи от компании Macrohard по следующим правилам:

  • каждой копии присваивается уникальный 25-разрядный ключ, состоящий из цифр и заглавных букв латинского алфавита. Код разбивается на группы по 5 символов, которые разделяются между собой знаком «-»
  • по каждому ключу можно вычислить его контрольную сумму по следующему правилу: необходимо сложить веса значащих символов и взять остаток от деления этой суммы на некое число P, где вес символа есть
    • значение цифры, если символ является цифрой (то есть вес цифры 5 равен пяти)
    • порядковый номер буквы в латинском алфавите плюс 9 (то есть вес буквы F равен 15)
Например, для кода 12345-12345-12345-12345-12345 при P = 11 контрольная сумма равна (1+2+3+4+5)*5 mod 11 = 9
  • контрольная сумма является идентификатором фирмы, которая покупает операционные системы, следовательно, оно должно быть различным для разных юридических лиц.

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

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

В первой строке входного файла содержится два натуральных числа N и P (1 ≤ N ≤ 30000, 1 ≤ P ≤ 1000), где N – число уже использованных ключей, P – число, используемое для подсчета контрольной суммы. В следующих N строках следуют ключи, которые задаются в виде
XXXXX-XXXXX-XXXXX-XXXXX-XXXXX, где X – значащий символ (цифра или буква латинского алфавита).

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

В выходной файл требуется вывести новый уникальный ключ в соответствии с указанным форматом, обладающий уникальной контрольной суммой. В случае, если такой ключ сгенерировать невозможно, выведите слово «Impossible».

Ввод
Вывод
3 5
23545-14978-59345-87926-52496     
67955-58818-19438-55659-02068    
99185-57241-15114-39158-36125
01389-28172-62843-79648-28129
5 3
BGPOV-D618J-FTN7L-4QWZJ-E6P8S     
7K3J3-I8076-58COS-0066F-9UAT4     
7S17C-YI099-1UC85-5S9PB-772LT     
TN2I4-TC1Z6-1OLI6-LT43G-9JMD3     
73OQ3-A9NBJ-N7UT7-AI349-XYJDT
1APMP-RSO53-G743I-F5TK6-R6487
5 4
7911L-5D41U-0N09C-34T16-5D0KI     
FRLAX-RE1Y1-WFVU0-88R56-C5D4V     
RUG51-IR00T-8L812-R6056-7OM59     
804F2-L7292-I12PX-14NDO-02LEW     
J3QQ4-H7H2V-2HCH4-M3HK8-6M8VW
Impossible
#3864
Цапли
  
Темы: [Целые числа]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Петя и Маша пришли в зоопарк. Больше всего Пете понравились цапли. Он был поражен их способностью спать на одной ноге.

В вольере находятся несколько цапель. Некоторые из них стоят на двух ногах, некоторые — на одной. Когда цапля стоит на одной ноге, то другую ее ногу не видно. Петя пересчитал видимые ноги всех цапель, и у него получилось число a.

Через несколько минут к вольеру подошла Маша. За это время некоторые цапли могли поменять позу, поэтому Петя предложил ей заново пересчитать видимые ноги цапель. Когда Маша это сделала, у нее получилось число b.

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

Требуется написать программу, которая по заданным числам a и b выведет минимальное и максимальное количество цапель, которое могло быть в вольере.

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

Входной файл содержит два целых числа a и b, разделенных ровно одним пробелом (1 ≤ a ≤ 109, 1 ≤ b ≤ 109).

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

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

Примечание к примеру тестов

В приведенном примере возможны следующие варианты:

  1. В вольере две цапли. Когда Петя считал ноги, одна цапля стояла на двух ногах, а другая — на одной. Петя насчитал три ноги. Когда Маша считала ноги, обе цапли стояли на двух ногах, Маша насчитала четыре ноги.
  2. В вольере три цапли. Когда Петя считал ноги, все цапли стояли на одной ноге, Петя насчитал три ноги. Когда Маша считала ноги, одна цапля стояла на двух ногах, а еще две — на одной. Маша насчитала четыре ноги.
Примеры
Входные данные
3 4
Выходные данные
2 3
#3871
«Abracadabra»
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

Строка s называется супрефиксом для строки t, если t начинается с s и заканчивается на s. Например, «abra» является супрефиксом для строки «abracadabra». В частности, сама строка t является своим супрефиксом. Супрефиксы играют важную роль в различных алгоритмах на строках.

В этой задаче требуется решить обратную задачу о поиске супрефикса, которая заключается в следующем. Задан словарь, содержащий n слов t1, t2, …, tn и набор из m строк-образцов s1, s2, …, sm. Необходимо для каждой строки-образца из заданного набора найти количество слов в словаре, для которых эта строка-образец является супрефиксом.

Требуется написать программу, которая по заданному числу n, n словам словаря t1, t2, …, tn, заданному числу m и m строкам-образцам s1, s2, …, sm вычислит для каждой строки-образца количество слов из словаря, для которых эта строка-образец является супрефиксом.

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

Первая строка входного файла содержит целое число n (1 ≤ n ≤ 200 000).

Последующие n строк содержат слова t1, t2, …, tn, по одному слову в каждой строке. Каждое слово состоит из строчных букв латинского алфавита. Длина каждого слова не превышает 50. Суммарная длина всех слов не превышает 106. Словарь не содержит пустых слов.

Затем следует строка, содержащая целое число m (1 ≤ m ≤ 200 000).

Последующие m строк содержат строки-образцы s1, s2, …, sm, по одной на каждой строке. Каждая строка-образец состоит из строчных букв латинского алфавита: Длина каждой строки-образца не превышает 50. Суммарная длина всех строк-образцов не превышает 106. Никакая строка-образец не является пустой строкой.

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

Выходной файл должен содержать m чисел, по одному на строке.

Для каждой строки-образца в порядке, в котором они заданы во входном файле, следует вывести количество слов словаря, для которых она является супрефиксом.

Система оценки

Решения, работающие при \(n\), \(m\) не превосходящими 100 оцениваются из 30 баллов.

Примеры
Входные данные
4
abacaba
abracadabra
aa
abra
3
a
abra
abac
Выходные данные
4
2
0
#111634
Робот
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
256 megabytes

Студенты одного из вузов спроектировали робота для частичной автоматизации процесса сборки авиационного двигателя.

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

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

Память робота состоит из K ячеек, каждая из которых содержит одну операцию. Операции выполняются последовательно, начиная с первой, в том порядке, в котором они расположены в памяти. Выполнив последнюю из них, робот продолжает работу с первой. Робота можно остановить после любой операции. Использование робота экономически целесообразно, если он выполнит хотя бы K + 1 операцию.

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

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

В первой строке входного файла записано число K > 0 "— количество операций, которые можно записать в память робота.

Вторая строка состоит из N > K строчных латинских букв, обозначающих операции "— процесс сборки двигателя. Операции одного и того же типа обозначаются одной и той же буквой.

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

Выходной файл должен содержать единственное целое число "— количество экономически целесообразных способов использования робота.

Примечание

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

  1. Тесты из условия. Подзадача оценивается в 0 баллов.

  2. N ≤ 100. Подзадача оценивается в 30 баллов.

  3. N ≤ 2000. Подзадача оценивается в 30 баллов.

  4. N ≤ 200 000. Подзадача оценивается в 40 баллов.

Примеры
Входные данные
2
zabacabab
Выходные данные
5
Входные данные
2
abc
Выходные данные
0
Страница: << 1 2 3 4 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест