Алгоритмы

948 задачвместе с подтемами
Число у задачи — рейтинг сложности, слово рядом — насколько она трудна по сравнению с другими задачами такого же типа. Шкалы задач с ответом и задач с кодом между собой не сравниваются. Рядом — счётчики попыток: ✓ успешные, ✗ неуспешные.
РейтингЛюбойдо 800800–11991200–15991600+Без рейтинга
СначалаПодходящиеНовыеПопулярныеПростыеСложные
Снова ка-штаны#38366
В этой задаче, как и в задаче B, Петя снова собирает своего M-лапого Зверя на прогулку (однако количество лап у Зверя в этой задаче может быть до 1000). Снова ему мама оставила N штанов, имеющих соответственно K1, K2, …, KN штанин. Однако тетерь Петя хочет надеть на Зверя штаны так, чтобы выполнялись следующие условия:
  • на каждой лапе была надета хотя бы одна штанина (гарантируется, что это всегда возможно),
  • количество штанин, надетых на самую «утепленную» лапу, должно как можно меньше отличаться от количества штанин, надетых на самую легко одетую лапу (когда количество штанов, одетых на разные лапы, сильно отличается, Зверь испытывает дискомфорт),
  • в отличие от задачи B Петя не обязан надеть на Зверя все имеющиеся штаны — какие-то из них можно оставить дома.
Как и раньше, любые штаны можно надевать на любой набор лап. В частности, нельзя несколько штанин одних и тех же штанов надеть на одну и ту же лапу Зверя.

Помогите Пете – напишите программу, которая для каждой лапы укажет, сколько штанин должно быть на нее надето.

Входные данные
Вводится сначала число M, а затем число N (1 ≤ M ≤ 1000, 1 ≤ N ≤ 100). Далее вводятся N чисел Ki, обозначающих число штанин у оставленных мамой штанов (1 ≤ Ki ≤ M). Сумма всех Ki не меньше, чем M.

Выходные данные
Выведите M строк, в i-ой строке должно быть выведено количество штанин, надетых на i-ю лапу. Если искомых ответов несколько, то выведите любой из них.
 
Примеры
№ Входные данные Выходные данные Пояснение
1 4 3
1 2 3		 1
1
1
1		 Первые штаны надеты на лапу 1;
вторые штаны не используем;
третьи штаны надеты на лапы 2, 3 и 4.
Таким образом, на всех лапах по 1 штанине.
2 4 2
3 2		 2
1
1
1		 Первые штаны надеты на лапы 1, 2 и 3;
вторые штаны надеты на лапы 1 и 4.
Таким образом, количество штанов на самой «утепленной» лапе (это лапа номер 1) – 2, а на остальных лапах по одной штанине, т.е. количество штанин на разных лапах отличается на один. Нетрудно заметить, что в этом примере нельзя одеть зверя так, чтобы на всех лапах было поровну штанин, поэтому этот ответ является оптимальным.
Задача о рюкзаке
✓ 3✗ 10—Войти и решать
Изобретательный Петя#38365
Петя нашел на чердаке старый телеграфный аппарат и приделал к нему хитроумное устройство, которое может печатать на телеграфной ленте определенное слово (обозначим его X). Петино устройство может напечатать на ленте это слово сколько угодно раз. Петя может заставить аппарат напечатать на ленте и любое другое сообщение, но для этого ему нужно разобрать свое хитроумное устройство, и после этого он уже не сможет печатать сообщение X. А самое главное, что напечатать даже один символ другого сообщения потребует от Пети больше усилий, чем напечатать на ленте слово X с помощью хитроумного устройства.

Петя хочет сделать так, чтобы всем казалось, что ему по телеграфу пришло сообщение Z. Для этого он может (строго в этой последовательности):
  • сколько угодно раз напечатать сообщение X
  • разобрать хитроумное устройство и посимвольно напечатать еще что-нибудь (назовем это Y)
  • оторвать и выбросить начало ленты так, чтобы на оставшейся ленте было напечатано в точности сообщение Z
Поскольку набирать отдельные символы сообщения Y довольно сложно, Петя хочет, чтобы в сообщении Y было как можно меньше символов.

Для лучшего понимания задачи смотрите примеры и пояснения к ним.

Входные данные
В первой строке вводится слово X, которое Петя может печатать с помощью хитроумного устройства сколько угодно раз. Во второй строке вводится сообщение Z, которое хочет получить Петя. Каждое сообщение состоит только из маленьких латинских букв и имеет длину не более 100 символов.

Выходные данные
Выведите минимальное по длине сообщение Y, которое Пете придется допечатать вручную.
 
Примеры
№ Входные данные Выходные данные Пояснение
1 mama
amamam		 m Сначала Петя два раза напечатает слово mama, потом к нему припечатает букву m, а затем отрежет и выбросит три начальных символа (mam). Ответом является допечатываемая отдельно буква m.
2 ura
mura		 mura Казалось бы, Пете стоит сначала напечатать букву m, а затем слово ura, которое он умеет печатать. Однако для того, чтобы напечатать m, ему придется разобрать свое устройство, и печатать ura ему придется также посимвольно.
3 computer
comp		 comp Казалось бы, Петя может напечатать слово computer, а затем отрезать и выбросить его конец — однако он не может так поступить, потому что отрезать и выбросить он может только начало ленты.
4 ejudge
judge		   Пете достаточно один раз напечатать слово ejudge, а затем отрезать и выбросить букву e. Ничего посимвольно выводить ему не придется, поэтому ответом является пустая строка.
5 m
mmm		   Достаточно трижды напечатать исходное слово и нужный результат будет получен. Ничего добавлять не надо, поэтому ответ – пустая строка.
Алгоритмы на строках
✓ 3✗ 0—Войти и решать
Наберите текст#38353
В новой модели сотового телефона разработчики предусмотрели только 5 кнопок: «стрелка вверх», «стрелка вниз», «стрелка вправо», «стрелка влево» и «Ok». Чтобы набрать номер телефона, на экран выводится виртуальная клавиатура в виде такой таблицы:
 
1 2 3
4 5 6
7 8 9
выход 0 звонок

По ячейкам этой таблицы пользователь телефона может перемещать курсор вверх, вниз, вправо или влево. Для выбора цифры необходимо нажать кнопку «Ok». После набора всех цифр пользователь должен подвинуть курсор на ячейку «звонок» и нажать «Ok». Таблица не «зациклена» (это означает, что нажатие кнопки «вправо», например, из ячейки с цифрой 6 не приведет к перемещению курсора).

При вызове экранной клавиатуры курсор находится на кнопке с надписью «выход».

По заданному семизначному номеру телефона определите, сколько нажатий кнопок должен сделать пользователь, чтобы позвонить по этому номеру.

Входные данные
Во входном файле задан номер телефона, содержащий ровно 7 цифр.

Выходные данные
В выходной файл выведите одно число — минимальное количество нажатий суммарно на все кнопки, которое необходимо, чтобы совершить звонок по этому номеру.
 
Примеры
№ Входные данные Выходные данные
1 0800000 12
2 1234567 24
Задача на реализациюЗадачи на моделирование
✓ 3✗ 0—Войти и решать
Определите порядок действий#38344
Ученику второго класса рассказали правила, как нужно выполнять арифметические действия, чтобы вычислить значение арифметического выражения, состоящего из чисел, скобок и знаков арифметических операций + (сложение) и * (умножение). После этого ему дали упражнения — несколько задач, в которых требуется расставить порядок выполнения действий. Помогите ему.

Правила вычисления выражения, рассказанные ученику, звучат так. Если в выражении вообще нет скобок, то сначала выполняются все операции умножения слева направо, а затем — операции сложения также слева направо. Если же в выражении есть скобки, то находится самая левая пара скобок (открывающая и закрывающая), содержащая внутри себя бесскобочное выражение, которое может быть вычислено по вышеописанным правилам. Дальше это выражение (вместе со скобками) мысленно удаляется из выражения и заменяется числом – результатом. Если в выражении остались скобки, то процедура повторяется.

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

Входные данные
Во входном файле записана одна строка, состоящая из символов #, +, *, (, ). Длина строки не превышает 250 символов. Строка соответствует правильному арифметическому выражению.

Выходные данные
В выходной файл нужно вывести ту же строку, заменив знаки операций + и * в ней натуральными числами, задающими порядок выполнения действий в соответствии с описанными правилами.
Примеры
№ Входные данные Выходные данные
1 #+#*# #2#1#
2 #+#+(#+#) #2#3(#1#)
3 #+(#+#*#)*#+# #4(#2#1#)3#5#
4 #+#+#+#+#+#+#+#+#+#+# #1#2#3#4#5#6#7#8#9#10#
5 #+#+(#+(#+#))+(#+#) #4#5(#2(#1#))6(#3#)
Разбор выражений
✓ 3✗ 4—Войти и решать
Марсианские нолики#38280
На Марсе используют систему счисления с основанием k . В отличие от привычной нам десятичной системы счисления, в этой системе счисления k цифр со значениями от 0 до k - 1 , а вес цифры в i -м разряде равен ki .

Например, пусть k = 8 . Запись 3578 означает число 3·8 2 + 5·8 + 7 , в более привычной землянам десятичной системе счисления это число записывается как 23910 . А число 19210 , в системе счисления с основанием 8 записывается как 3008 .

Ильдар — юный марсианин, и он очень любит круглые числа. Ильдар называет число достаточно круглым , если его запись в системе счисления с основанием k заканчивается хотя бы на n нулей. Сегодня Ильдар хочет найти i -е по порядку достаточно круглое число.

Помогите Ильдару, найдите i -е достаточно круглое в системе счисления с основанием k натуральное число и выведите его в десятичной системе счисления. Ильдар очень дружелюбен и гарантирует, что ответ в десятичной системе счисления не превосходит 1018 .

Входные данные
Все ограничения на числа в этой задаче заданы в десятичной системе счисления. Все числа во вводе также записаны в десятичной системе счисления.

Первая строка входных данных содержит число k — основание системы счисления, которую использует Ильдар ( 2 ≤ k ≤ 109 ).

Вторая строка входных данных содержит число n — минимальное количество нулей на конце достаточно круглого числа ( 0 ≤ n ≤ 100 ).

Третья строка входных данных содержит число i — порядковый номер достаточно круглого числа, которое интересует Ильдара ( 1 ≤ i ≤ 109 ).

Выходные данные
Выведите одно число — запись в десятичной счистеме счисления i -го по порядку достаточно круглого в системе счисления с основанием k натурального числа. Гарантируется, что ответ не превышает 1018 .

Обратите внимание, что ответ может не поместиться в стандартный 32-битный тип данных. Надо использовать 64-битный тип, в паскале он называется « int64 », в C++ « long long », в Java « long ». Если вы пишете на языке Python, то волноваться не надо, в Python встроенный целочисленный тип не имеет ограничений на величину числа.
 
№ Входные данные Выходные данные
1 8
2
2		 192
Разные системы счисления
✓ 3✗ 0—Войти и решать
Том и Джерри#38275
В этой задаче мы снова возвращаемся в младшую группу детского сада «Телепузики». Чтобы окончательно успокоить детей, воспитательница решила включить им мультик про Тома и Джерри. Серия, которую сейчас смотрят дети, довольно-таки незамысловата — в ней Джерри развесил по потолку комнаты наковальни на веревках. Когда Том оказывается под очередной наковальней, Джерри перерезает веревку. Наковальня падает на Тома, Тому больно, всем остальным весело, дети смеются. В общем, вполне обычная серия.

А вам нужно по кадру из этой серии определить, упадет ли наковальня на Тома, если Джерри перережет веревку.

Входные данные
Вам дана ASCII-арт картинка, то есть картинка, нарисованная символами. На ней есть наковальня, привязанная веревкой к потолку, и кот Том. В первой строке даны числа N, M (4≤N≤100, 1≤M≤100 ). Следующие N строк состоят из M символов каждая, и представляют собой саму картинку. Картинка устроена следующим образом:
  • Первые K1 строк в одной и той же позиции X1 стоит символ «|», в остальных — пробел. Это веревка.
  • Следующие K2 строк в одних и тех же позициях с X2 по X3 стоит символ «#», в остальных — пробел. Это наковальня.
  • 2×X1=X2+X3, то есть наковальня подвешена за середину.
  • Следующие K3 строк содержат только пробелы. Это пустота между наковальней и котом.
  • Следующие N − K1 − K2 − K3 строк содержат произвольные символы. Любой символ, кроме пробела — часть кота. Существует хотя бы один непробельный символ.
Числа K1, K2, K3 и N − K1 − K2 − K3  ненулевые.
Выходные данные
Выведите «YES», если при падении наковальня заденет Тома, в противном случае выведите «NO».
 
Примеры
№ Входные данные Выходные данные
1 13 29 
          |                  
          |                  
          |                  
    #############            
    #############            
    #############            
                             
                             
            /\_/\            
            >^.^<.---.       
           _'-`-'     )\     
          (6--\ |--\ (`.`-.  
              --'  --'  ``-'
YES
2 16 30 
    |                         
 #######                      
 #######                      
 #######                      
 #######                      
                              
            ,                 
           \)\_               
          /    '. .---._      
        =P ^     `      '.    
         `--.       /     \   
         .-'(       \      |  
        (.-'   )-..__>   , ;  
        (_.--``    (__.-/ /   
                .-.__.-'.'    
                 '-...-'
NO
Задачи на моделированиереализация
—Войти и решать
Считаем графы#38146
У Маши есть связный ненаправленный граф G с N вершинами, помеченными 1…N и M ребрами (\(1 \leq N \leq10^2\), \(N-1 \leq M \leq \frac {N^2+N}{2}\)). G может содержать петли (ребра из вершины в неё же), но не имеет параллельных ребер (несколько ребер, соединяющих одни и те же конечные точки).
Пусть \(f_G(a,b)\) это булевская функция, которая отвечает истина, если существует путь от вершины 1 до вершины a, который проходит ровно b ребер, для \(1 \leq a \leq N\) и \(0 \leq b\), и ложь иначе. Если по ребру проходим множество раз, это число включается в ответ. 
Даша хочет повторить за Машей. В частности, она хочет сконструировать ненаправленный граф G′ такой, что \(f_{G'}(a,b)=f_G(a,b)\) для всех a и b.

Посчитайте количество различных графов G′, которые Даша может создать, по модулю \(10^9+7\). Как и G, G′ может содержать петли но не может иметь параллельные ребра (это означает, что имеется всего \(2^{ \frac {N^2+N} {2}}\) различных графов на N вершинах).
Каждый ввод содержит T (\(1 \leq T \leq \frac {10^5}{4}\)) тестов, которые должны решаться независимо. Гарантируется, что сумма \(N^2\) по всем тестам не превысит \(10^5\).

Входные данные
Первая строка ввода содержит T, количество тестов.
Первая строка каждого теста содержит два целых числа N и M.
Следующие M строк каждого теста содержат два целых числа x и y (\(1 \leq x \leq y \leq N\)), обозначающих ребро между x и y в G.

Тесты разделены пустой строкой для читабельности.

Выходные данные
Для каждого теста выведите количество различных G′ по модулю \(10^9+7\) на отдельной строке.
 
 
Примеры
№ Входные данные Выходные данные Примечание
1 1

5 4
1 2
2 3
1 4
3 5		 3 G′ может быть равен G′ или одному из двух следующих графов:
5 4
1 2
1 4
3 4
3 5

5 5
1 2
2 3
1 4
3 4
3 5
2 7

4 6
1 2
2 3
3 4
1 3
2 4
1 4

5 5
1 2
2 3
3 4
4 5
1 5

5 7
1 2
1 3
1 5
2 4
3 3
3 4
4 5

6 6
1 2
2 3
3 4
4 5
5 6
6 6

6 7
1 2
2 3
1 3
1 4
4 5
5 6
1 6

10 10
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10

22 28
1 2
2 3
3 4
4 5
5 6
6 7
1 7
1 8
3 9
8 10
10 11
10 12
10 13
10 14
11 15
12 16
13 17
14 18
9 15
9 16
9 17
9 18
15 19
19 20
15 20
16 21
21 22
16 22		 45
35
11
1
15
371842544
256838540		 Это пример более крупного теста.
Обязательно выводите ответ по модулю \(10^9+7\).
Обратите внимание, что ответ для предпоследнего теста - \(2^{45}\ \ (mod\ 10^9 + 7)\).

 
Вывод формулыграфыОбход в ширину
✓ 1✗ 3—Войти и решать
Игра в камушки#38145
Маша и Даша играют в игру с N (\(1<=N<=10^5\)) кучками камушков, где i-ая кучка содержит ai камешков (\(1<=i<=N\), \(1<=a_i<=10^6\)). Они ходят по очереди, первой ходит Маша.
  • Сначала Маша выбирает некоторое положительное число s1 и удаляет s1 камешков из некоторой кучки, в которой есть не менее s1 камешков.
  • Затем Даша выбирает некоторое положительное число s2 такое, что s2 делится на s1 и удаляет s2 камешков из некоторой кучки, содержащей не менее s2 камешков.
  • Затем Маша выбирает некоторое положительное число s3, которое делится на s2 и удаляет s3 камешков из некоторой кучки, в которой есть не менее s3 камешков.
  • В общем случае si, количество камешков, которое убирается на ходу i, должно быть делителем si+1.

Проигрывает тот, кто не может сделать ход.

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


Входные данные
Первая строка содержит N.
Вторая строка содержит N разделённых одиночными пробелами целых чисел a1,…,aN.


Выходные данные
Выведите количество способов, которыми Маша может удалить камушки на первом ходу, чтобы гарантировать себе выигрыш.
Для вычислений используйте 64-ное целое например, "long long" в C/C++.
 
 
Примеры
№ Входные данные Выходные данные Примечание
1 1
7		 4 Маша выбирает 4, 5, 6, 7 камушков из одной кучи и игра закончится сразу.
2 6
3 2 3 2 3 1		 8 Маша выиграет, если удалит 2 или 3 камушка из любой кучи. Затем игроки будут по очереди брать одно и то же количество камушков, но Маша сделает последний ход.
Игры и выигрышные стратегии
✓ 2✗ 14—Войти и решать
Подсчёт коров#38143
Коровы Фермера Джона разбрелись по огромному пастбищу, представленному в виде 2D-решётки (шахматной доски).  Размещение коров весьма занимательно. Для каждой ячейки (x,y) с \(x>=0\) и \(y>=0\), существует корова в ячейке (x,y), если для всех целых чисел \(k>=0\), остатки \(\lfloor {\frac {x}{3^k} }\rfloor\) и \(\lfloor {\frac {y}{3^k} }\rfloor\) по модулю 3 имеют одну и ту же четность. Другими словами оба эти остатка нечётные (равны 1) или оба чётные (равны 0 или 2). Например, ячейки для \(0<=x,y<9\), которые содержат коров обозначены цифрой 1 на рисунке ниже. 
 x
    012345678

  0 101000101
  1 010000010
  2 101000101
  3 000101000
y 4 000010000
  5 000101000
  6 101000101
  7 010000010
  8 101000101
Ферме Джон интересуется сколько коров присутствует в определённом квадратном регионе его пастбища. Он задаёт Q вопросов, кажый содержит три целых числа xi,yi,di. Для каждого вопроса Фермер Джон хочет знать, сколько коров в ячейках с (xi, yi) до (xi+di, yi+di) (включая конечные точки).


Входные данные
Первая строка содержит Q (\(1<=Q<=10^4\)) - количество вопросов.
Каждая из следующих Q строк содержит 3 целых числа di, xi, и yi (\(0<=x_i,y_i,d_i<=10^{18}\)).


Выходные данные
Q строк, по одной для каждого вопроса - одно целое число - ответ.
 
 
Примеры
№ Входные данные Выходные данные
1 8
10 0 0
10 0 1
9 0 2
8 0 2
0 1 7
1 1 7
2 1 7
1000000000000000000 1000000000000000000 1000000000000000000		 11
0
4
3
1
2
2
1000000000000000001
Динамическое программирование
✓ 2✗ 5—Войти и решать
Забор по часовой стрелке#38137
Фермер Джон решил заменить изгородь вокруг своего пастбища.
Эта новая изгородь описывается строкой символов, каждый из которых "N" (north), "E" (east), "S" (south), или "W" (west). Каждый символ описывает 1 метр изгороди. Например, если строка NESW, это означает, что изгородь начинатся одним метром на север, затем 1 метр на восток, затем 1 метр на юг, и затем 1 метр на запад, возвращаясь в стратовую точку.

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

Фермер Джон хочет узнать, указанный путь обходится по часовой стреле или против часовой стрелки? По часовой стрелке - огороженный регион находится по правую сторону от изгороди, если идти по пути, определённому строкой. Против часовой стрелки - огороженный регион находится по левую сторону от изгороди, если идти по пути, определённому строкой.

Входные данные: 
Первая строка содержит целое число N (1≤N≤20). Каждая из последующих N строк содержит строку длиной не менее 4 символов и не более 100, описывающую путь изгороди.
Выходные данные: 
Для каждого из N путей, описанных по вводе, выведите строку содержащую "CW" (clockwise - по часовой стрелке) или "CCW" (counterclockwise - против часовой стрелки).
 
Примеры
№ Входные данные Выходные данные Пояснение
1 2
NESW
WSSSEENWNEESSENNNNWWWS 		 CW
CCW		 Оба пути   (? символ "пробел") обозначает стартовую точку:

*>*
^ v

<*

  *<*<*<*
  v     ^
*<
     *
v       ^
* *>*>* *
v ^   v ^
* *<* * *
v   ^ v ^
*>*>* *>*
Элементарная геометрия
✓ 4✗ 10—Войти и решать
Схемы маршрутизации#38135
Рассмотрим сеть из N (2≤N≤100) вершин, помеченных 1…N. Каждая вершина обозначена как посылатель, получатель или ни то, ни другое. Количество посылателей S равно количеству получателей (S≥1).
Связи между двумя вершинами в сети могут быть описаны как список направленных ребер каждое в виде i→j, обозначающее, что вершина i может передать информацию вершине j. Интересно, что все эти рёбра удовлетворяют свойству i<j, кроме K которые удовлетворяют свойству i>j (0≤K≤2). Нет циклов (ребер вида i→i).

Описание схемы маршрутизации состоит из множества S направленных путей от посылателей к получателям таких, что никакие два из этих путей не имею общую конечную точку. То есть пути соединяют различных посылателей с различными получателями. Путь от посылателя s к получателю r может быть описан как последовательность вершин
s=v0→v1→v2→?→ve=r
такая что направленные ребра vi→vi+1 существуют для всех 0≤i<e. Одна вершина может появиться более чем один раз в одном и том же пути.
Посчитайте количество различных схем маршрутизации, таких, что каждое направленное ребро проходится ровно один раз. Поскольку ответ может быть очень большим, выводите его по модулю 109+7. Гарантируется, что существует хотя бы одна схема маршрутизации, удовлетворяющая ограничениям.

Каждый ввод содержит T (1≤T≤20) тестов, которые требуется решать независимо. Гарантируется, что сумма N2 всех тестов не превысит 2⋅104.


Входные данные: 
Первая строка содержит T, количество тестов.
Первая строка каждого теста содержит целые числа N и K. Заметим, что S не определяется явно во вводе.

Вторая строка каждого теста содержит строку длины N. i-ый символ строки равен S если i-ая вершина посылатель, R - если i-ая вершина - получатель, . - если i-ая вершина - ни то, ни другое. Количества символов R и S равны. Есть хотя бы один символ S.

Каждая из N последующих строк теста содержит битовую строку из N нулей и единиц. j-ый бит в i-ой строке равен 1, если существует направленное ребро от вершины i к вершине j, и 0 в протвном случае. Поскольку петель нет, на главной диагонали все нули. Более того имеется ровно K единиц ниже главной диагонали.

Последовательные тесты разделены пустыми строками для читабельности.

Выходные данные: 
Для каждого теста выведите количество схем маршрутизации таких, что каждое ребро проходится ровно один раз, по модулю 109+7. Гарантируется, что существует хотя бы одна валидная схема маршрутизации.
 
Примеры
№ Входные данные Выходные данные Пояснение
1 2

8 0
SS....RR
00100000
00100000
00011000
00000100
00000100
00000011
00000000
00000000

13 0
SSS.RRRSS.RR.
0001000000000
0001000000000
0001000000000
0000111000000
0000000000000
0000000000000
0000000000000
0000000001000
0000000001000
0000000000110
0000000000000
0000000000000
0000000000000		 4
12		 Для первого теста ребра таковы 1→3,2→3,3→4,3→5,4→6,5→6,6→7,6→8.

Имеется четыре схемы маршрутизации:

1→3→4→6→7,2→3→5→6→8
1→3→5→6→7,2→3→4→6→8
1→3→4→6→8,2→3→5→6→7
1→3→5→6→8,2→3→4→6→7
Для второго теста 1→4,2→4,3→4,4→5,4→6,4→7,8→10,9→10,10→11,10→12.

Одна из возможных схем маршрутизации:

1→4→5
2→4→7
3→4→6
8→10→12
9→10→11
В общем случае посылатели {1,2,3} могут маршрутизироваться некоторой перестановкой получателей {5,6,7}, и посылатели {8,9} могут маршрутизироваться некоторой перестановкой получателей {11,12} давая ответ 6 ⋅ 2=12.
 
2 2

5 1
SS.RR
00101
00100
10010
00000
00000

6 2
S....R
001000
000100
010001
000010
001000
000000		 3
1		 Для первого теста, ребра 1→3,1→5,2→3,3→1,3→4.

имеется три схемы маршрутизации:

1→3→1→5, 2→3→4
1→3→4, 2→3→1→5
1→5, 2→3→1→3→4
Для второго теста 1→3,2→4,3→2,3→6,4→5,5→3.

Имеется только одна схема мартшрутизации: 1→3→2→4→5→3→6.
3 5

3 2
RS.
010
101
100

4 2
.R.S
0100
0010
1000
0100

4 2
.SR.
0000
0011
0100
0010

5 2
.SSRR
01000
10101
01010
00000
00000

6 2
SS..RR
001010
000010
000010
000010
100101
000000		 2
1
2
6
24		  
Динамическое программирование на графахДревовидные структуры данных
✓ 1✗ 0—Войти и решать
Перестановка#38131
У Беси есть N (3≤N≤40)любимых точек на 2D-решётке, никакие три из которых не коллинеарны. Для каждого 1≤i≤N, i-ая точка задаётся двумя целочисленными координатами xi и yi (0≤xi,yi≤104).
Беси рисует некоторые отрезки между точками следующим образом:

Она выбирает некоторую перестановку p1,p2,…,pN из N точек
Она рисует отрезки между p1 и p2, p2 и p3, p3 и p1.
Затем для каждого целого i от 4 до N по порядку, она рисует отрезки прямых от pi до pj для всех j<i так, этот отрезок не пересекает никакой из ранее нарисованных отрезков (вне конечных точек)
Беси заметила, что для каждого i она нарисовала ровно три новых отрезка. Вычислите количество перестановок, которые Беси могла выбрать на шаге 1, которые удовлетворяют этому свойству по модулю 109+7.

Входные данные: 
Первая строка содержит N.
Каждая из последующих N строк содержит два разделённых пробелом целых числа xi и yi.

Выходные данные: 
Количество перестановок по модулю 109+7.
 
Примеры
№ Входные данные Выходные данные Пояснение
1 4
0 0
0 4
1 1
1 2		 0 Никакая перестановка не сработает.
2 4
0 0
0 4
4 0
1 1		 24 Все перестановки работают.
3 5
0 0
0 4
4 0
1 1
1 2		 96 Одна из перестановок, удовлетворяющих свойству - (0,0),(0,4),(4,0),(1,2),(1,1).
Для этой перстановки
  • Сначала она рисует отрезки между каждой парой (0,0),(0,4), и (4,0).
  • Затем она рисует отрезки от (0,0), (0,4), и (4,0) до (1,2).
  • Наконец, она рисует отрезки от (1,2), (4,0), и (0,0) до (1,1).
Рисунок:

Перестановка не удовлетворяет свойству, если её первые четыре точки (0,0)(0,0), (1,1)(1,1), (1,2)(1,2), и (0,4)(0,4) в некотором порядке.
Рекуррентные последовательности
✓ 2✗ 1—Войти и решать
Знаете ли вы свою азбуку#38129
Коровы Фермера Джона ежедневно собираются на видео-платформе "mooZ". Они придумали простую числовую игру.
У Эльзы есть три положительных целых числа A, B, C (1≤A≤B≤C). Предполагается что они секретные, поэтому она не объявляет их явно своей сестре Беси. Вместо этого она говорит Беси N (4≤N≤7) различных целых чисел x1,x2,…,xN (1≤xi≤109), подразумевая что каждое из xi это одно из чисел A, B, C, A+B, B+C, C+A, or A+B+C. Однако Эльза может солгать. Целые числа xi могут не соответствовать ни одной корректной тройке (A,B,C).

Беси попросила Вас определить количество троек (A,B,C), соответствующих числам, которые представила Эльза (возможно 0).

Каждый входной файл будет содержать T (1≤T≤100) тестов, которые необходимо обрабатывать независимо.

ФОРМАТ ВВОДА 
Первая строка содержит целое число T.
Каждый тест начинается с числа N, количества целых числе, которые Эльза дала Беси.

Вторая строка каждого теста содержит N различных целых чисел x1,x2,…,xN.

ФОРМАТ ВЫВОДА 
Для каждого теста выведите количество троек (A,B,C), соответствующих представленным Эльзой числам.
Примеры
№ Входные данные Выходные данные Пояснение
1 10
7
1 2 3 4 5 6 7
4
4 5 7 8
4
4 5 7 9
4
4 5 7 10
4
4 5 7 11
4
4 5 7 12
4
4 5 7 13
4
4 5 7 14
4
4 5 7 15
4
4 5 7 16		 1
3
5
1
4
3
0
0
0
1		 Для x={4,5,7,9}, имеется 5 возможных комбинаций:

(2,2,5),(2,3,4),(2,4,5),(3,4,5),(4,5,7).
ПереборРазбор случаев
✓ 4✗ 2—Войти и решать
Условное форматирование#34905
В свободное от программирования время Вася увлекается экспериментами, и его любимый — переливание воды между колбами. У него есть две колбы размером a и b миллилитров соответственно, и неограниченное количество воды. Вася может производить с ними следующие действия:
  •  Налить воду в первую колбу до края (после этого в ней будет a миллилитров воды)
  •  Полностью вылить воду из первой колбы
  •  Налить воду во вторую колбу до края (после этого в ней будет b миллилитров воды)
  •  Полностью вылить воду из второй колбы
  •  Перелить воду из первой колбы во вторую. В этом случае, если во второй колбе достаточно места, чтобы уместить всю текущую воду первой колбы, вода из первой колбы переливается полностью во вторую. Если же во второй колбе места недостаточно, вторая колба заполняется до предела (в ней после этого будет b миллилитров воды), а в первой колбе остается все остальное.
Состоянием колб Вася называет упорядоченную пару (x, y), где x — текущее количество воды в первой колбе, а y— во второй. Вася хочет изучить поставленную самим собой задачу и понять, сколько различных состояний он может получить описанными выше переливаниями.
Входные данные
В единственной строке входного  через пробел записаны два натуральных числа a и b (1 ≤ a, b ≤ 100) — емкости первой и второй колбы соответственно.
Выходные данные
В единственной строке выходного выведите одно число — число различных состояний, которое можно получить описанными в задаче переливаниями воды.
 
Ввод Вывод
2 5 14
Задачи на моделированиепоиск в глубину и подобное
✓ 4✗ 1—Войти и решать
33100#33100
На вход программы подаются произвольные алфавитно-цифровые символы. Ввод этих символов заканчивается точкой. Требуется написать программу, которая будет печатать последовательность строчных английских букв ('a' 'b'... 'z') из входной последовательности и частот их повторения. Печать должна происходить в алфавитном порядке.

Например, пусть на вход подаются следующие символы:
fhb5kbfыshfm.
В этом случае программа должна вывести
b2
f3
h2
k1
m1
s1
Сортировка подсчетомСтроки
—Войти и решать
П №52#33098
Дед Мороз и Снегурочка приходят на детские утренники с мешком конфет. Дед Мороз делит конфеты поровну между всеми присутствующими детьми (детей на утреннике никогда не бывает больше 100), а оставшиеся конфеты отдает Снегурочке. Снегурочка каждый раз записывает в блокнот количество полученных конфет. Если конфеты разделились между всеми детьми без остатка, Снегурочка ничего не получает и ничего не записывает. Когда утренники закончились, Деду Морозу стало интересно, какое число чаще всего записывала Снегурочка. Дед Мороз и Снегурочка – волшебные, поэтому число утренников N, на которых они побывали, может быть очень большим. Напишите программу, которая будет решать эту задачу. Перед текстом программы кратко опишите алгоритм решения задачи и укажите используемый язык программирования и его версию. Желательно, чтобы программа была эффективной как по времени работы, так и по используемой памяти. Программу будем считать эффективной по памяти, если используемая память не зависит от размера входных данных (то есть числа утренников). Программу будем считать эффективной по времени, если при увеличении размера входных данных N в t раз (t – любое число) время её работы увеличивается не более чем в t раз.
 
Входные данные
В первой строке вводится одно целое положительное число – количество утренников N. Каждая из следующих N строк содержит два целых числа: сначала D – количество пришедших на очередной утренник детей, а затем K – количество конфет в мешке Деда Мороза на этом утреннике. Гарантируется выполнение следующих соотношений: 1 ≤ N ≤ 10000, 1 ≤ D ≤ 100 (для каждого D), D ≤ K ≤ 1000 (для каждой пары D, K)
 
Выходные данные
Программа должна вывести одно число – то, которое Снегурочка записывала чаще всего. Если несколько чисел записывались одинаково часто, надо вывести большее из них. Если Снегурочка ни разу ничего не записывала, надо вывести ноль.

Ввод Вывод
7
10 58
15 315
20 408
100 1000
32 63
32 63
11 121
 31

Сортировка подсчетом
✓ 0✗ 6—Войти и решать
Вырубка леса#33093
Фермер Николай нанял двух лесорубов: Дмитрия и Федора, чтобы вырубить лес, на месте которого должно быть кукурузное поле. В лесу растут X деревьев.
 
Дмитрий срубает по A деревьев в день, но каждый K-й день он отдыхает и не срубает ни одного дерева. Таким образом, Дмитрий отдыхает в K-й, 2K-й, 3K-й день, и т.д.
 
Федор срубает по B деревьев в день, но каждый M-й день он отдыхает и не срубает ни одного дерева. Таким образом, Федор отдыхает в M-й, 2M-й, 3M-й день, и т.д.
 
Лесорубы работают параллельно и, таким образом, в дни, когда никто из них не отдыхает, они срубают A + B деревьев, в дни, когда отдыхает только Федор — A деревьев, а в дни, когда отдыхает только Дмитрий — B деревьев. В дни, когда оба лесоруба отдыхают, ни одно дерево не срубается.
 
Фермер Николай хочет понять, за сколько дней лесорубы срубят все деревья, и он сможет засеять кукурузное поле. 
 
Требуется написать программу, которая по заданным целым числам A, K, B, M и X определяет, за сколько дней все деревья в лесу будут вырублены.

Программа должна работать быстрее, чем за линейный поиск
 
Входные данные
Входной файл содержит пять целых чисел, разделенных пробелами: A, K, B, M и X (1 ≤ A, B ≤ 109 , 2 ≤ K, M ≤ 1018, 1 ≤ X ≤ 1018).
 
Выходные данные
Выходной файл должен содержать одно целое число — искомое количество дней.

Ввод Вывод
2 4 3 3 25 7

Бинарный поиск по ответу
—Войти и решать
Классификация снежинок#31926
Стелла изучает снежинки, измеряя длину их шести лучей, и собрала уже много данных. Теперь Стелла собирается определить, сколько различных видов снежинок ей удалось обнаружить. Она считает снежинки одинаковыми, если снежинки можно совместить после поворота и/или переворачивания.
Напишите программу, которая поможет Стелле провести классификацию снежинок.
Первая строка ввода содержит одно целое число N (2 ≤ N ≤ 100000). Далее следует N строк, содержащих по 6 целых чисел a1 a2 a3 a4 a5 a6 от 1 до 109, разделенных пробелами – длины лучей снежинок в порядке обхода по часовой стрелке.
Вывести одно целое число – количество различных снежинок, обнаруженных Стеллой.

Ввод Вывод
5
1 2 3 4 5 6
3 4 5 6 1 2
3 2 1 4 5 6
6 5 4 3 2 1
2 3 6 5 4 1
 2
Примечание
Совпадают снежинки 1 и 2 и 4 после поворота или после переворачивания и снежинки 3 и 5 после переворачивания и поворота.
Быстрая сортировка
✓ 0✗ 1—Войти и решать
Лифт#30720

Лифт

В доме Вилли установили скоростной лифт новой экспериментальной модели. В этом лифте кнопки с номерами этажей заменены двумя другими кнопками. При нажатии на первую кнопку лифт поднимается на один этаж вверх, а при нажатии на вторую – опускается на один этаж вниз.
 
Младшему брату Вилли Дилли очень нравится кататься на новом лифте. Он катается на нём до тех пор, пока не побывает на каждом из этажей хотя бы по одному разу. После этого Дилли довольный возвращается домой.
 
Зная порядок, в котором Дилли нажимал на кнопки лифта, попробуйте определить общее количество этажей в доме Вилли и Дилли.
 
Входные данные
Первая строка входного файла INPUT.TXT содержит последовательность нажатий на кнопки лифта. Символ «1» означает, что была нажата первая кнопка, а символ «2» – что была нажата вторая кнопка. Символы «1» и «2» не разделены пробелами. Количество нажатий от 1 до 100. Гарантируется, что лифт никогда не опускался ниже первого и не поднимался выше последнего этажа.
 
Выходные данные
Следует вывести одно число – количество этажей в доме Вилли и Дилли.

Ввод Вывод
11 3
21212 2
1221221221221 6

Задачи на моделированиеОдномерные массивы
—Войти и решать
Поделиться
Класснуть