қазақша
русскийРеспубликанская олимпиада по информатике, 2015 год, 10-11 сынып
Вы главный разработчик в компании грузоперевозок Нурлаш и КО inc. Компании требуется, чтобы вы написали новый функционал для сортирующего робота. Робот контролирует $N$ отсеков, последовательно пронумерованных от 1 до $N$, и может выполнять два типа операций:
Добавить контейнер с номером $C$ в каждый отсек с $L$-го по $R$-ый
Убрать последний контейнер из каждого отсека с $L$-го по $R$-ый
комментарий/решение(1)
Сегодня в кафе Нового Университета (НУ) пришли $N$ студентов. Каждый из них хочет выпить чашку кофе и съесть одно пирожное (никто из них не согласен только на кофе либо только на пирожное --- в этом случае студент уходит). В кафе подают $M$ видов кофе и $K$ видов пирожных. Для каждого из видов кофе или пирожного известно, сколько чашек или порций этого вида имеется в наличии.
Кроме того, у каждого студента есть свои вкусовые предпочтения. Для каждого студента известно, какие виды кофе и пирожных он любит. Никто из студентов не согласен есть или пить то, что ему не нравится.
Хозяин кафе задумался: какое максимальное количество студентов он сможет обслужить? А вы можете посчитать это число?
Во второй строке записано $M$ целых чисел через пробел $C_1,C_2,\dots,C_M$ ($1 \le C_i \le 500$) --- количество чашек кофе каждого вида, имеющихся в наличии.
В третьей строке записано $K$ целых чисел через пробел $P_1,P_2,\dots,P_K$ ($1 \le P_i \le 500$) --- количество порций пирожных каждого вида, имеющихся в наличии.
В следующих $N$ строках дана информация о том, какие виды кофе любит каждый студент. $i$-я строка ($1 \le i \le N$) содержит число $X_i$, за которым следуют различные числа $A_1,A_2,\dots,A_{X_i}$ --- виды кофе, которые любит $i$-й студент.
Следующие $N$ строк задают информацию о том, какие виды пирожных любит каждый студент. $i$-я строка ($1 \le i \le N$) содержит число $Y_i$, за которым следуют различные числа $B_1,B_2,\dots,B_{Y_i}$ --- виды пирожных, которые любит $i$-й студент.
$1 \le N, M, K \le 5$. Сумма всех $X_i$ и $Y_i$ ($1 \le i \le N$) вместе не превосходит $10$. Оценивается в $21$ балл.
$1 \le N, M, K \le 20$. Сумма всех $X_i$ и $Y_i$ ($1 \le i \le N$) вместе не превосходит $15$. Оценивается в $33$ балла.
$1 \le N, M, K \le 500$. Сумма всех $X_i$ и $Y_i$ ($1 \le i \le N$) вместе не превосходит $2000$. Оценивается в $46$ баллов.
Каждая следующая подзадача оценивается только при прохождении всех предыдущих.
Кроме того, у каждого студента есть свои вкусовые предпочтения. Для каждого студента известно, какие виды кофе и пирожных он любит. Никто из студентов не согласен есть или пить то, что ему не нравится.
Хозяин кафе задумался: какое максимальное количество студентов он сможет обслужить? А вы можете посчитать это число?
Входные данные:
Первая строка входных данных содержит целые числа $N$, $M$, $K$ ($1 \le N, M, K \le 500$).Во второй строке записано $M$ целых чисел через пробел $C_1,C_2,\dots,C_M$ ($1 \le C_i \le 500$) --- количество чашек кофе каждого вида, имеющихся в наличии.
В третьей строке записано $K$ целых чисел через пробел $P_1,P_2,\dots,P_K$ ($1 \le P_i \le 500$) --- количество порций пирожных каждого вида, имеющихся в наличии.
В следующих $N$ строках дана информация о том, какие виды кофе любит каждый студент. $i$-я строка ($1 \le i \le N$) содержит число $X_i$, за которым следуют различные числа $A_1,A_2,\dots,A_{X_i}$ --- виды кофе, которые любит $i$-й студент.
Следующие $N$ строк задают информацию о том, какие виды пирожных любит каждый студент. $i$-я строка ($1 \le i \le N$) содержит число $Y_i$, за которым следуют различные числа $B_1,B_2,\dots,B_{Y_i}$ --- виды пирожных, которые любит $i$-й студент.
Выходные данные:
Выведите единственное число — ответ на задачу.Примеры:
1.Вход:2 3 1 5 1 3 2 3 1 2 3 1 2 1 1 1 1Ответ:
2
Оценивание:
Данная задача содержит 3 подзадачи:$1 \le N, M, K \le 5$. Сумма всех $X_i$ и $Y_i$ ($1 \le i \le N$) вместе не превосходит $10$. Оценивается в $21$ балл.
$1 \le N, M, K \le 20$. Сумма всех $X_i$ и $Y_i$ ($1 \le i \le N$) вместе не превосходит $15$. Оценивается в $33$ балла.
$1 \le N, M, K \le 500$. Сумма всех $X_i$ и $Y_i$ ($1 \le i \le N$) вместе не превосходит $2000$. Оценивается в $46$ баллов.
Каждая следующая подзадача оценивается только при прохождении всех предыдущих.
комментарий/решение
Темирулану и Пернехану подарили последовательность $A$ из $1 \le N \le 5000$ целых положительных чисел. Они договорились поделить эту последовательность. Каждый из них должен взять некоторую не пустую последовательную часть последовательности, причем часть Темирулана должна начинаться раньше части Пернехана. Они хотят выглядеть уникально, поэтому они хотят чтобы не существовало ни одного числа, встречающегося в участке Темирулана и Пернехана одновременно. Айдос, наблюдавший за ними, заинтересовался, сколько существует различных способов сделать это. Помогите ему, напишите программу для количества способов.
$1 \le N \le 50$. Оценивается в $11$ баллов.
$1 \le N \le 500$. Оценивается в $21$ балл.
$1 \le N \le 2000$. Оценивается в $31$ балл.
$1 \le N \le 5000$. Оценивается в $37$ баллов.
Входные данные:
Первая строка входных данных содержит целое число $N$. Следующая строка содержит $N$ целых чисел $1 \le A_i \le N$, $1 \le i \le N$, разделенных пробелами.Выходные данные:
Выведите единственное число — ответ на задачу.Примеры:
1.Вход:3 1 2 3Ответ:
52.Вход:
4 1 2 3 2Ответ:
93.Вход:
1 1Ответ:
0Во втором тестовом примере есть следующие способы разделения: \{ [1] [2] 3 2 \}, \{ [1] [2 3] 2 \}, \{ [1] [2 3 2] \}, \{ [1] 2 [3] 2 \}, \{ [1] 2 [3 2] \}, \{ [1] 2 3 [2] \}, \{ [1 2] [3] 2 \}, \{ 1 [2] [3] 2 \}, \{ 1 2 [3] [2] \}
Оценивание:
Данная задача содержит четыре подзадачи:$1 \le N \le 50$. Оценивается в $11$ баллов.
$1 \le N \le 500$. Оценивается в $21$ балл.
$1 \le N \le 2000$. Оценивается в $31$ балл.
$1 \le N \le 5000$. Оценивается в $37$ баллов.
комментарий/решение
У Артема была последовательность $x$ из $1 \le N \le 100$ чисел, для которой выполнялось следующее свойство $1 \le L \le x_1 \le x_2 \le \ldots \le x_N \le R \le 10^9$, а наименьшее общее кратное этих чисел делилось на $1 \le A \le 10^9$. Но пришел Мансур и украл последовательность $x$. Артем очень расстроился, ведь он не помнит значения чисел своей последовательности. Он помнит только числа $N$, $L$, $R$ и $A$. Он хочет восстановить последовательность. Для этого он решил сначала посчитать, а сколько вообще существует последовательностей, с такими же $N$, $L$, $R$ и $A$. Помогите ему, --- напишите программу для решения этой задачи.
${ 1, 6}$, ${ 2, 3}$, ${ 2, 6}$
${ 3, 4}$, ${ 3, 6}$, ${ 4, 6}$
${ 5, 6}$, ${ 6, 6}$, ${ 6, 7}$
$1 \le N \le 2$, $1 \le A,L,R \le 100$. Оценивается в $6$ баллов.
$1 \le N \le 2$, $1 \le A,L,R \le 1000$. Оценивается в $11$ баллов.
$1 \le N \le 10$, $1 \le A,L,R \le 1000$. Оценивается в $15$ баллов.
$1 \le N \le 10$, $1 \le A,L,R \le 10^6$. Оценивается в $21$ балл.
$1 \le N \le 100$, $1 \le A,L,R \le 10^9$. Оценивается в $47$ баллов.
Каждая следующая подзадача оценивается только при прохождении всех предыдущих.
Входные данные:
Единственная строка входных данных содержит четыре целых положительных числа, разделенных пробелами: $N$, $L$, $R$, $A$.Выходные данные:
Выведите единственное число, ответ на задачу. Так как ответ может быть очень большим, выведите его остаток от деления на $10^9 + 7$.Примеры:
1.Вход:2 1 7 6Ответ:
92.Вход:
1 1 50 7Ответ:
7В первом тестовом примере подходящими последовательностями будут следующие::
${ 1, 6}$, ${ 2, 3}$, ${ 2, 6}$
${ 3, 4}$, ${ 3, 6}$, ${ 4, 6}$
${ 5, 6}$, ${ 6, 6}$, ${ 6, 7}$
Оценивание:
Данная задача содержит 5 подзадачи:$1 \le N \le 2$, $1 \le A,L,R \le 100$. Оценивается в $6$ баллов.
$1 \le N \le 2$, $1 \le A,L,R \le 1000$. Оценивается в $11$ баллов.
$1 \le N \le 10$, $1 \le A,L,R \le 1000$. Оценивается в $15$ баллов.
$1 \le N \le 10$, $1 \le A,L,R \le 10^6$. Оценивается в $21$ балл.
$1 \le N \le 100$, $1 \le A,L,R \le 10^9$. Оценивается в $47$ баллов.
Каждая следующая подзадача оценивается только при прохождении всех предыдущих.
комментарий/решение
Скоро состоится командное соревнование <<Наурыз Cup 2015>>. Команда должна состоять ровно из двух участников. Аманчик сильно хочет в нем участвовать. Он достал список всех $2 \cdot N$ ($1 \le N \le 10^5$) участников включая себя . У каждого участника есть свой рейтинг. Рейтинг команды это средний рейтинг двух участников. Чем выше рейтинг команды тем выше его место. Команда занимает место под номером $K+1$, если есть ровно $K$ команд, рейтинг которых строго больше .
Из всевозможных разбиений, какое самое высокое и самое низкое место может занять команда Аманчика. Аманчик участник под номером 1.
$1 \le N \le 3$. Оценивается в $7$ баллов.
$1 \le N \le 6$. Оценивается в $19$ баллов.
$1 \le N \le 2500$. Оценивается в $31$ балл.
$1 \le N \le 10^5$. Оценивается в $43$ балла.
Каждая следующая подзадача оценивается только при прохождении всех предыдущих.
Из всевозможных разбиений, какое самое высокое и самое низкое место может занять команда Аманчика. Аманчик участник под номером 1.
Входные данные:
Первая строка входных данных содержит целое число $N$. Следующая строка содержит $2 \cdot N$ целых чисел $1 \le a_i \le 10^5$, $1 \le i \le 2 \cdot N$, разделенных пробелами.Выходные данные:
Выведите два числа самое высокое и самое низкое место.Примеры:
1.Вход:3 999 3 1 2 1000 1Ответ:
1 22.Вход:
1 1540 1433Ответ:
1 13.Вход:
3 100000 100000 100000 100000 100000 100000Ответ:
1 1В первом примере если мы разобьем участников следующим образом (999, 2) (3, 1) (1000, 1) то команда Аманчика (999, 2) и команда (1000, 1) возьмут первые места, а команда (3, 1) возьмет третье место. А если мы разобьем следующим образом (999, 1) (1000, 2) (3, 1) то команда Аманчика возьмет второе место. Из всевозможных разбиений, указанные выше будут соответствовать самым высоким и самым низким местам.
Оценивание:
Данная задача содержит четыре подзадачи:$1 \le N \le 3$. Оценивается в $7$ баллов.
$1 \le N \le 6$. Оценивается в $19$ баллов.
$1 \le N \le 2500$. Оценивается в $31$ балл.
$1 \le N \le 10^5$. Оценивается в $43$ балла.
Каждая следующая подзадача оценивается только при прохождении всех предыдущих.
комментарий/решение