Темы --> Информатика
    Язык программирования(952 задач)
    Алгоритмы(1657 задач)
    Структуры данных(279 задач)
    Интерактивные задачи(17 задач)
    Другое(54 задач)
---> 544 задач <---
Источники --> Личные олимпиады
    Олимпиады сайта(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 задач)
Страница: << 103 104 105 106 107 108 109 >> Отображать по:
#113580
Маленький Матеж и большие проблемы
  
Темы: [Хеш]
Источники: [ Личные олимпиады, COCI, COCI 2015-2016, Раунд 5, Маленький Матеж и большие проблемы ]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
512 megabytes

У маленького Матежа возникла проблема с решением следующей задачи.

У него есть множество слов, содержащее N слов. Ему пришло Q запросов, являющихся шаблонами. Шаблон состоит из строчных латинских букв и символа '*'.

Требуется узнать, сколько слов из множества могут совпасть с шаблоном, если вместо '*' подставить любое (возможно, пустое) множество букв.

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

В первой строке содержатся N и Q ( 1 ≤ N , Q ≤ 10 5 ). В последующих N строках содержатся строки из множества. В последующих Q строках содержатся шаблоны. Входной файл содержит не более трех миллионов символов.

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

Выведите Q строк: в каждой ответ для соответствующего шаблона.

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

40 баллов: 1 ≤ N , Q ≤ 1000

Примеры
Входные данные
3 3
aaa
abc
aba
a*a
aaa*
*aaa
Выходные данные
2
1
1
Входные данные
5 3
eedecc
ebdecb
eaba
ebcddc
eb
e*
*dca
e*c
Выходные данные
5
0
2
#113581
Массивы, числа, три хеша
  
Источники: [ Личные олимпиады, COCI, COCI 2015-2016, Раунд 5, Массивы, числа, три хеша ]
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
256 megabytes

Вам дан массив целых чисел длины N . Пусть s 1 , s 2 , ... , s q - массив его непустых подпоследовательностей, отсортированный в лексикографическом порядке.

Подпоследовательностью массива называется массив, полученным путем вычеркивания нескольких (возможно, 0) элементов из изначального массива. Заметьте, что некоторые подпоследовательности могут быть одинаковыми, поэтому q = 2 N - 1 .

Массив A лексикографически меньше массива B , если A i < B i , где i - первая позиция, в которой массивы различаются, или если A - строгий префикс B .

Определим хеш массива s , состоящего из элементов v 1 , v 2 , ... , v p , как: h ( s )  =  ( v 1 · B p - 1 + v 2 · B p - 2 + ... + v p - 1 · B + v p ) mod M , где B и M - данные числа.

Посчитайте h ( s 1 ) , h ( s 2 ) , ... , h ( s K ) для данного K .

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

В первой строке содержатся числа N , K , B , M ( 1 ≤ N ≤ 100000 , 1 ≤ K ≤ 100000 , 1 ≤ B , M ≤ 1000000 ).

Во второй строке содержится N чисел a 1 , a 2 , a 3 , ... , a N ( 1 ≤ a i ≤ 100000 ).

Гарантируется, что во всех тестах K ≤ 2 N - 1 .

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

Выведите K строк, j -я строка должна содержать h ( s j ) и длину s j .

Примечание

Решения, работающие при 1 ≤ a 1 , a 2 , ..., a N ≤ 30 , будут оцениваться в 60 баллов.

Примеры
Входные данные
2 3 1 5
1 2
Выходные данные
1 1
3 2
2 1
Входные данные
3 4 2 3
1 3 1
Выходные данные
1 1
1 1
0 2
2 2
Входные данные
5 6 23 1000
1 2 4 2 3
Выходные данные
1 1
25 2
25 2
577 3
274 4
578 3
#113582
Водянистая гистограмма Мирко
  
Источники: [ Личные олимпиады, COCI, COCI 2015-2016, Раунд 5, Водянистая гистограмма Мирко ]
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Ночью Мирко приснилась гистограмма из N столбиков. Каждый из них имел ширину в 1 метр, а высоты столбиков в метрах равны h 1 , h 2 , ... , h N .

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

Формально, пусть количество воды над столбиками равно v 1 , v 2 , ... , v N соответственно. Тогда конфигурация воды стабильна, если выполняются следующие условия:

1. h i + v i ≤ h i - 1 + v i - 1 для каждого i ≥ 2 , такого что v i > 0 .

2. h i + v i ≤ h i + 1 + v i + 1 для каждого i ≤ N - 1 , такого что v i > 0 .

3. v 1 = 0 и v N = 0 .

Проснувшись, Мирко захотел нарисовать такую гистограмму, чтобы высоты ее столбиков были перестановкой множества {1, 2, ... , N} и ее вместимость была в точности равна его счастливому числу X . Помогите Мирко и найдите такую гистограмму.

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

Единственная строка содержит два целых числа N и X ( 1 ≤ N ≤ 1000000 , 1 ≤ X ≤ 10 15 ).

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

Если гистограмма вместимости X не существует, выведите -1.

Иначе, выведите числа h 1 , h 2 , ... , h N (являющиеся перестановкой множества {1, 2, ... , N}), удовлетворяющие условию задачи. Если существует несколько решений, выведите любое.

Группы тестов

25 баллов — (1 ≤ n ≤ 10) .

25 баллов — (0 ≤ x ≤ n - 2 ) .

50 баллов — полные ограничения.

Примеры
Входные данные
3 1
Выходные данные
3 1 2
Входные данные
4 1
Выходные данные
4 3 1 2
Входные данные
8 17
Выходные данные
6 2 3 1 8 4 5 7
#113583
Мирко и азартные игры
  
Источники: [ Личные олимпиады, COCI, COCI 2015-2016, Раунд 6, Мирко и азартные игры ]
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Юный Мирко - умный, но озорной мальчик, который часто бродит по паркам в поисках новых идей и друзей. В этот раз он встретился с пенсионерами, которые играли в карточную игру Белот. Они пригласили его помочь им подсчитать количество очков, выигранных в одной игре.

Каждая карта определяется мастью и символом. Набор из 4 карт называется рукой. В каждой игре одна из масть "бьет" все остальные и называется козырной. Количество очков в одной игре равно сумме победных очков всех карт из всех выигравших рук в игре. Мирко заметил, что пенсионерами было выиграно N рук, а козырная масть в игре была B .

Выигрышные очки карт (если масть козырная / если масть не козырная):

А : 11 / 11

K : 4 / 4

Q : 3 / 3

J : 20 / 2

T : 10 / 10

9 : 14 / 0

8 : 0 / 0

7 : 0 / 0

По данным выигравшим рукам и козырной масти определите количество очков, выигранных в этой игре.

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

Первая строка содержит одно целое число N ( 1 ≤ N ≤ 100 ) и один символ B ( S , H , D или C ) - козырная масть в игре.

Каждая из следующих 4 N строк содержит описание карты K i , состоящее из двух символов: первый - символ карты ( A , K , Q , J , T , 9 , 8 , 7 ), второй - масть карты ( S , H , D или C ).

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

Выведите одно целое число - количество выигранных очков.

Примеры
Входные данные
2 S
TH
9C
KS
QS
JS
TD
AD
JH
Выходные данные
60
Входные данные
4 H
AH
KH
QH
JH
TH
9H
8H
7H
AS
KS
QS
JS
TS
9S
8S
7S
Выходные данные
92
#113584
Опасность ожирения
  
Темы: [Массивы]
Источники: [ Личные олимпиады, COCI, COCI 2015-2016, Раунд 6, Опасность ожирения ]
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

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

У него есть возможность есть грибы, которые он находит во время прогулки. Все грибы, которые ему встречаются, различны, и он собирается съесть как можно больше различных грибов, но не превысить свою норму. Мислав действует так: он идет по лесу и в любой момент может начать действовать по следующему алгоритму. Если он может съесть гриб и не переесть, то он ест его, иначе – проходит мимо.

Вам дан массив из N весов грибов в том порядке, в котором Мислав находит их. Определите, сколько грибов он может съесть.

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

Первая строка содержит два целых числа N и C ( 1 ≤ N ≤ 1000 , 1 ≤ C ≤ 10 6 ).

Вторая строка содержит N целых чисел w i ( 1 ≤ w i ≤ 1000 ), обозначающих веса грибов.

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

Выведите одно число – максимальное количество грибов, которое может съесть Мислав, чтобы не ожиреть.

Примечание

В первом примере если он начнет есть с первого гриба, то он съест 3 гриба (3, 1, 1). Если он начнет со второго, то он сможет съесть 4 гриба (1, 2, 1, 1).

Примеры
Входные данные
5 5
3 1 2 1 1
Выходные данные
4
Входные данные
7 5
1 5 4 3 2 1 1
Выходные данные
3
Страница: << 103 104 105 106 107 108 109 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест