Портал обучения информатике. Подготовка к ЕГЭ, ОГЭ, олимпиадам

Простое произведение#50347

Натуральное число \(p\) называется простым, если оно имеет ровно два различных делителя: \(1\) и \(p\). Например, числа \(2\), \(3\), \(5\) являются простыми. Число \(1\) простым не считается.

Целое число \(p\) будем называть квазипростым, если \(p\) или \(-p\) является простым. Например, числа \(-2\), \(2\), \(-3\), \(3\), \(-5\), \(5\) являются квазипростыми.

Хотя любое натуральное число можно единственным образом представить в виде произведения простых, для целых чисел и квазипростых это уже неверно. Например, число \(12\) можно тремя способами представить в виде произведения квазипростых: \(12=2\cdot 2\cdot 3\), \(12=(-2)\cdot 2\cdot (-3)\), \(12=(-2)\cdot (-2)\cdot 3\).

Задано целое число \(n\). Выведите все способы представить \(n\) в виде произведения квазипростых. Произведения, которые отличаются только порядком множителей, считаются одним способом.

Формат входных данных
На первой строке ввода находится число \(n\) (\(-10^9 \le n \le 10^9\), \(n \ne 0\), \(n \ne \pm 1\)).

Формат выходных данных
На первой строке выведите \(k\) — количество способов представить \(n\) в виде произведения квазипростых. В следующих \(k\) строках выведите все способы представить \(n\) в виде произведения квазипростых. Произведения можно выводить в любом порядке, множители в каждом произведении можно выводить в любом порядке.

Перебор Простые числа и разложение на множители

✓ 3✗ 41 100средняяВойти и решать

Сумма#50342

Даша очень любит представлять числа в виде суммы. Сегодня Даша хочет выписать все возможные представления числа \(n\) в виде суммы \(k\) слагаемых.

При этом она не любит, когда слагаемые меняются слишком быстро. А именно, соседние слагаемые в представлении Даши должны различаться не больше, чем на единицу. Она использует и положительные, и отрицательные, и даже нулевые слагаемые, порядок слагаемых важен.

Выведите все представления, которые подходят по Дашины ограничения. Разбиения следует упорядочить по первому слагаемому, при равном первом слагаемом — по второму, при равных первых двух — по третьему, и так далее.

Формат входных данных
Первая строка ввода содержит число \(n\) (\(-15\le n \le 15\)).

Вторая строка содержит число \(k\) (\(1 \le k \le 15\)).

Гарантируется, что общее число представлений не превышает \(10^5\).

Формат выходных данных
Выводите представления по одному на строке, перед положительными и нулевыми слагаемыми, кроме первого в представлении, выводите знак плюс. Не выводите пробелы.

Простые задачи на перебор

✓ 1✗ 161 100средняяВойти и решать

Генераторы квадратов#48941

Множество \(A = \{a_1, a_2, \ldots, a_k\}\) различных натуральных чисел с суммой \(a_1+a_2+\ldots+a_k=n\) называется генератором квадратов, если сумма любых \(k-1\) элементов этого множества является полным квадратом целого числа.

Например, множество \(\{1, 22, 41, 58\}\) является генератором квадратов, так как \(1 + 22 + 41 = 64 = 8^2\), \(1 + 22 + 58 = 81 = 9^2\), \(1 + 41 + 58 = 100 = 10^2\), \(22 + 41 + 58 = 121 = 11^2\).

По заданным \(n\) и \(k\) постройте множество из \(k\) различных натуральных чисел с суммой \(n\), которое является генератором квадратов, либо выясните, что такого нет.

Формат входных данных
На ввод подаются два целых числа \(n\) и \(k\) (\(2 \le n \le 200\,000\), \(2 \le k \le 30\)).

Формат выходных данных
Если искомый генератор квадратов существует, выведите <<YES>> на первой строке, а на второй строке выведите \(k\) натуральных чисел "— искомое множество.

Если генератора квадратов с заданными параметрами не существует, выведите <<NO>>.

Вывод формулы Перебор реализация

✓ 1✗ 151 200средняяВойти и решать

Вордл наоборот#48935

Камила и Динара играют в <<Wordle>>. Камила загадала слово длины \(n\), состоящее из различных латинских букв. Динара сделала одну попытку угадать и назвала слово длины \(n\), также состоящее из различных латинских букв. Камила раскрасила буквы в догадке Динары в соответствии со следующими правилами:

Буква, совпадающая с буквой в загаданном слове, красится в зеленый цвет и обозначается G.
Буква, которая присутствует в загаданном слове, но стоит не своей позиции, красится в жёлтый цвет и обозначается Y.
Буква, отсутствующая в загаданном слове, красится в белый цвет и обозначается W.

Например, если было загадано слово ALERT, а догадка была ALONE, то буквы будут раскрашены в цвета GGWWY. Первые две буквы в словах совпадают, поэтому они зеленые. Буква E есть в загаданном слове, но находится на другой позиции, поэтому она жёлтая. Остальные буквы белые, так как их нет в загаданном слове.

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

В первой строке вводится одно целое число \(n\) \((1 \le n \le 10)\) — длина загаданного слова.

Во второй строке вводится строка длины \(n\), состоящая из заглавных латинских букв — загаданное слово. Гарантируется, что все буквы в нем различны.

В третьей строке вводится строка длины \(n\), состоящая из букв G, Y, W — цвета, в которые были раскрашены буквы в слове Динары.

Если подходящих слов не существует, выведите No.

Если хотя бы одно подходящее слово существует, в первой строке выведите Yes, во второй — любое подходящее слово.

Разберем первый пример из условия.

Буквы H и G не встречаются в загаданном слове, поэтому они белые.

Буквы E и B встречаются, но на других позициях, поэтому они жёлтые

Буквы C и D совпадают с буквами на соответствующих позициях в загаданном слове, поэтому они зелёные.

Есть и другие ответы, любой правильный ответ будет зачтен.

Обратите внимание, что строка HECDBH не является ответом, так как в ней есть совпадающие буквы.

Задача на реализацию Перебор Строки

✓ 10✗ 54900средняяВойти и решать

Все сочетания из n по k#47937

Даны два целых числа n и k, выведите все возможные комбинации из k чисел, выбранных из диапазона [1, n]. Порядок элементов в одной комбинации не важен. То есть комбинация (1, 2, 3) и (3, 2, 1) считается одинаковой.
Выведите на экран все такие комбинации в лексикографическом порядке.

Входные данные
В первой строке записано целое число n, во второй - целое число k.

Ограничения

1 <= n <= 20
1 <= k <= n

Выходные данные
Выведите в лексикографическом порядке все возможные комбинации из k чисел, выбранных из диапазона [1, n]. Каждая комбинация чисел должна выводиться в отдельной строке, числа в одной комбинации разделяются одним пробелом.

Перебор с возвратом Рекурсия

✓ 61✗ 50700средняяВойти и решать

XOR-cумма массива#47936

XOR-cумма массива определяется как побитовое XOR всех его элементов или 0, если массив пуст.

Например, XOR-сумма массива [2,5,6] равна 2 XOR 5 XOR 6 = 1.
Для заданного массива nums, верните сумму всех XOR-сумм для каждого подмножества nums.

Примечание: подмножества, состоящие из одинаковых элементов, считаются различными и должны подсчитываться несколько раз.
Массив a является подмножеством массива b, если a может быть получено из b путем удаления некоторых (возможно не удалением никаких) элементов b.

Входные данные
Программа получает на вход в первой строке натуральное число n - количество элементов массива nums. Во второй строке записаны n чисел nums_i.

Ограничения

1 <= n <= 12
1 <= nums_i <= 20

Выходные данные
Выведите ответ на задачу.

Пояснения к тестовым примерам
В первом примере
В [1,3] существует 4 подмножества:
- Пустое подмножество имеет XOR-сумму 0.
- [1] имеет XOR-сумму, равную 1.
- [3] имеет XOR-сумму, равную 3.
- В [1,3] сумма XOR равна 1 XOR 3 = 2.
0 + 1 + 3 + 2 = 6

Во втором примере
В [5,1,6] 8 подмножеств:
- Пустое подмножество имеет XOR-сумму 0.
- [5] имеет XOR-сумму, равную 5.
- [1] имеет XOR-сумму, равную 1.
- [6] имеет XOR-сумму, равную 6.
- [5,1] имеет XOR-сумму 5 XOR 1 = 4.
- [5,6] имеет XOR-сумму 5 XOR 6 = 3.
- [1,6] имеет XOR-сумму 1 XOR 6 = 7.
- [5,1,6] имеет XOR-сумму 5 XOR 1 XOR 6 = 2.
0 + 5 + 1 + 6 + 4 + 3 + 7 + 2 = 28

Перебор с возвратом Рекурсия

✓ 73✗ 48800средняяВойти и решать

Гармоничная последовательность lite - 2#47740

Цикл лекций в университете Флатландии посвящен изучению последовательностей.

Профессор называет последовательность целых чисел \(a_1, a_2, ..., a_n\) гармоничной, если каждое число, кроме \(a_1\) и \(a_n\), равно сумме соседних: \(a_2 = a_1 + a_3, a_3=a_2+a_4, ..., a_{n-1}=a_{n-2}+a_n\). Например, последовательность [1,2,1,–1] является гармоничной, поскольку 2=1+1, и 1=2+(–1) .

Рассмотрим последовательности равной длины: \(A=[a_1,a_2, ... a_n]\) и \(B=[b_1,b_2, ... b_n]\). Расстоянием между этими последовательностями будем называть величину \(d(A,B)= |a_1-b_1|+|a_2-b_2|+...+|a_n-b_n|\) . Например, \(d([1,2,1,–1][1,2,0,0])=|1–1|+|2–2|++|1–0|+|–1–0|=0+0+1+1=2 \)

В конце лекции профессор написал на доске последовательность из n целых чисел \(B=[b_1,b_2, ... b_n]\)и попросил студентов в качестве домашнего задания найти гармоничную последовательность \(A=[a_1,a_2, ... a_n]\), такую, что \(d(A, B)\) минимально. Чтобы облегчить себе проверку, профессор просит написать в качестве ответа только искомое минимальное расстояние \(d(A,B)\) .

Требуется написать программу, которая по заданной последовательности B определяет, на каком минимальном расстоянии от последовательности B найдется гармоничная последовательность A.

Входные данные
Первая строка содержит целое число n – количество элементов в последовательности ( \(3 \le n \le 500\)).
Вторая строка содержит n целых чисел \(b_1, b_2, …, b_n (–100 \le b_i \le 100 )\) .

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

Примеры

№	Входные данные	Выходные данные
1	4 1 2 0 0	2

Перебор

—Войти и решать

Добраться до игрушек#44034

Дед Мороз решил проверить фабрику игрушек, все ли подарки для детей готовы. Чтобы дойти до места хранения игрушек, ему необходимо пройти по узкому секретному коридору. В коридоре на каждом метре пути указано число метров от двери. У двери, возле которой стоит Дед Мороз, записано число 0. По коридору можно двигаться как влево, так и вправо. При движении влево числа отрицательные, при движении вправо - положительные.

Так как место засекречено, завод постоянно меняет вход в хранилище игрушек.

Дед Мороз знает, что вход в фабрику сегодня расположен у двери с числом X. Также известно, что в коридоре, рядом с числом Y находится дверь, перекрывающая проход по коридору. Чтобы ее открыть необходимо взять ключ, который располагается на стене на полке в коридоре рядом с числом Z.

Определите сможет ли Дед Мороз сам добраться до двери к игрушкам. Если сможет, определите минимальное расстояние, которое необходимо будет пройти Деду Морозу. Если не сможет, то выведите -1.

Входные данные
Программа получает на вход строку, содержащую 3 различных ненулевых числа: X, Y, Z (-10³ <= X, Y, Z <= 10³).

Выходные данные
Выведите минимальное расстояние, которое необходимо пройти Деду Морозу от двери, у которой он стоит, до двери, за которой расположено место хранения игрушек. Если Дед Мороз не сможет добраться до этой двери, выведите -1.

Примеры

№	Входные данные	Выходные данные
1	10 -10 1	10
2	20 10 -10	40
3	100 1 1000	-1

Простые задачи на перебор Условный оператор

✓ 102✗ 573900средняяВойти и решать

Мишины кубики#43718

У маленького Миши есть кубики, на каждом из которых написана одна английская строчная буква. Вчера он выкладывал кубики в два ряда. В первом ряду у Миши n кубиков с буквами, во втором - m кубиков с буквами. Так получилось, что в двух этих рядах нет совпадающих букв. Другими словами, ни одна буква не содержится одновременно в обоих рядах.
Сегодня маленький Миша решил продолжить играть с кубиками. Но теперь он берет один любой кубик из какого-либо ряда и составляет из них третий ряд, добавляя кубик всегда в конец. Маленький Миша никогда не берет более k кубиков подряд из одного и того же ряда. Миша закончил играть тогда, когда у него закончились кубики в каком-то одном ряду (в первом или во втором).
Наблюдавший за игрой папа заметил, что играя таким образом у Миши получилась лексикографически наименьшая строка. По известным двум строкам, которые образуются путем прочтения букв первого и второго ряда и числу k определите строку, которую получил маленький Миша.

Строка x лексикографически меньше строки y только и только тогда, когда выполняется одно из следующих условий:
- x является префиксом y, но x != y;
- в первой позиции, где x и y различаются, в строке x находится буква, которая стоит в алфавите раньше, чем соответствующая буква y.

Входные данные
Программа получает на вход несколько строк. В первой строке записаны три числа: n - количество кубиков в первом ряду, m - количество кубиков во втором ряду, k - целое число(1 <= n, m, k <= 100). Во второй строке записана строка a длиной n - строка, образованная прочтением букв, написанных на кубиках первого ряда. В третьей строке - строка b длиной m - строка, образованная прочтением букв, написанных на кубиках второго ряда.

Выходные данные
Выведите ответ на задачу.

Примеры

№	Входные данные	Выходные данные
1	6 4 2 aaaaaa bbbb	aabaabaa

"Два указателя"Жадный алгоритм Задача на реализацию Использование сортировки Простые задачи на перебор

✓ 28✗ 1141 100средняяВойти и решать

Громозека и валерьянка#43474

Громозека очень любит валерьянку. На его родной планете Чумароза можно купить за k чумриков (местная валюта) первую упаковку валерьянки, за 2·k чумриков - вторую и так далее (иными словами, за i-ю упаковку надо заплатить i·k чумриков). Громозека хочет купить w упаковок валерьянки. У него есть n чумриков. Сколько чумриков ему придется взять в кредит в чумарозском банке, чтобы купить w упаковок валерьянки?

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

В первой строке записано три положительных целых числа k, n, w (1 <= k, w <= 1000, 0 <= n <= 10⁹), стоимость первой упаковки, изначальное количество чумарозиков у Громозеки и количество упаковок валерьянки, которые он хочет купить.

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

Выведите единственное целое число - количество чумарозиков, которое Громозеке необходимо взять в кредит в банке. Если брать кредит не надо, выведите 0.

Примеры

№	Входные данные	Выходные данные
1	3 17 4	13

Задача на реализацию Простые задачи на перебор Цикл for Циклы

✓ 160✗ 448500лёгкаяВойти и решать

Чебаркульские спортсмены#43136

Алексей Юрьевич и Михаил Леонидович — тренера чебаркульской сборной по американскому футболу. Сегодня им нужно заполнить очень важную анкету на чемпионат мира, в которой необходимо указать всех членов команды в порядке возрастания их силы.
Для решения этой непростой задачи были собраны все игроки сборной, и каждый из спортсменов сказал несколько (возможно ноль) фраз вида: «Я сильнее, чем игрок k» (k может отличаться от высказывания к высказыванию, ни один спортсмен не говорил одинаковых фраз). Когда опрос был окончен, тренера поняли, что теперь могут однозначно упорядочить спортсменов по силе, соответствуя всем высказываниям.
Сразу после того, как Алексей Юрьевич и Михаил Леонидович написали ответ организаторам олимпиады, они задумались, а что было бы, если бы футболисты отвечали иначе? Ведь далеко не во всех случаях можно восстановить единственно возможный порядок игроков.
Теперь им интересно, сколько наборов ответов спортсменов однозначно задают их порядок? Так как это число может быть слишком большим, они просят найти лишь его остаток от деления на 10⁹+7.
Входные данные
Во входных данных записано единственное число n — количество спортсменов в сборной (1 <= n <= 10⁵) .
Выходные данные
Выведите единственное число — количество наборов ответов спортсменов, однозначно позволяющих упорядочить их по силе.

Примеры

№	Входные данные	Выходные данные
1	2	2

Замечание
В данном тесте вариантов ответов всего 2: первый сказал, что сильнее второго, второй не сказал ничего, или первый не сказал ничего и второй сказал, что он сильнее первого.

Вывод формулы Комбинаторика

✓ 2✗ 0—Войти и решать

Xor-пути в матрице#39836

Задано прямоугольное поле размера n*m. В каждой клетке записано целое неотрицательное число. Требуется посчитать количество путей из клетки (1,1) в клетку (n,m), удовлетворяющих следующим условиям.
1) Из каждой клетки можно перемещаться только вниз или вправо, не выходя при этом за пределы поля.
2) Побитовое исключающее ИЛИ всех чисел на пути должно быть равно k.
Найдите количество подходящих путей для заданного поля.

Входные данные
Первая строка содержит три целых числа n, m и k (1 <= n, m <= 20, 0 <= k <= 10¹⁸) - высота и ширина поля, и число k.
Следующие n строк содержат по m целых чисел a_i,j, где j-й элемент i-й строки равен a_i,j (0 <= a_i,j <= 10¹⁸).

Выходные данные
Выведите одно целое число - количество путей, удовлетворяющих всем условиям.

Примеры

№	Входные данные	Выходные данные
1	3 3 11 2 1 5 7 10 0 12 6 4	3
2	3 4 2 1 3 3 3 0 3 3 2 3 0 1 1	5

meet in the middle Перебор

✓ 3✗ 01 000средняяВойти и решать

Культурный контакт#39675

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

Для успешного налаживания контактов с аборигенами руководитель группы планирует делать подарок вождю каждого встреченного племени. С этой целью он привёз длинную цепочку из стекляшек, похожих на драгоценные камни.
Представим цепочку как строку s, состоящую из маленьких букв английского алфавита, где каждая буква означает тип кусочка стекла на соответствующей позиции.
Исследователи собираются разрезать цепочку на некоторые фрагменты, после чего вручать ровно один фрагмент вождю каждого встреченного группой племени. Руководитель исследователей решил разделить цепочку на фрагменты согласно следующим правилами:

Чтобы не тратить на разрезания много времени, каждый фрагмент должен являться группой соседних стекляшек цепочки, то есть подстрокой строки s.
Все стекляшки должны быть использованы, то есть каждая стекляшка должна оказаться включённой ровно в один фрагмент.
Поскольку исследователи не знают, как аборигены оценят те или иные виды стекляшек, они хотят, чтобы каждому вождю достался один и тот же набор стекляшек без учёта порядка. Иными словами, для любого типа стекляшек количество стекляшек этого типа должно быть одинаковым в каждом из фрагментов.
Исследователи не знают, сколько племён обитает на острове, поэтому количество подготовленных фрагментов должно быть максимальным.

Помогите руководителю определить максимальное количество фрагментов, которое может получиться.

Входные данные:
В первой строке дана строка s (1 <= |s| <= 5000000).

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

Примеры:

Входные данные	Выходные данные
abbabbbab	3
aabb	1

Пояснения:
В первом примере исследователи могут разбить цепочку 'abbabbbab' на фрагменты 'abb', 'abb', 'bab', тогда вождю каждого встреченного ими племени достанется по одной стекляшке типа 'a' и по две стекляшки типа 'b'.

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

Перебор Префиксные суммы(минимумы, ...)Хеш

✓ 3✗ 16—Войти и решать

Гекльберри Финн и две строки#39674

У Гекльберри Финна есть две строки s и t одинаковой длины n.
Гекльберри Финну нравится, когда у строк одинаковые префиксы (начала), поэтому он может поменять местами два символа в строке s, чтобы общий префикс строк s и t стал больше.
Однако этот трюк довольно утомительный, поэтому Гекльберри Финн либо совсем не будет его делать, либо сделает ровно один раз.

Помогите Гекльберри Финну определить наибольшую длину общего префикса строк s и t, которую он может получить.

Входные данные:
В первой строке дано натуральное число n (1 <= n <= 200000) - длина строк s и t
Во второй строке дана строка s, состоящая из строчных латинских букв.
В третьей строке дана строка t, состоящая из строчных латинских букв.

Выходные данные:
Выведите одно натуральное число - наибольшую длину общего префикса s и t, которую можно получить, применив операцию обмена двух символов в строке s не более одного раза.

Примеры:

Входные данные	Выходные данные
3 wai add	1
5 qdyid xreac	0

Перебор Префиксные суммы(минимумы, ...)Хеш

✓ 1✗ 01 000средняяВойти и решать

Танцевальные движения#39575

Коровы Фермера Джона танцуют.
Сначала все N коров (2≤N≤10⁵) стоят в ряд и корова i находится на позиции i. Последовательность танцевальных движений задаётся K (1≤K≤2⋅10⁵) парами позиций (a₁,b₁),(a₂,b₂),…,(a_K,b_K). Каждую минуту i=1…K танца коровы на позициях a_i и b_i меняются местами. Такие же K обменов делаются на минутах K+1…2K, затем опять на минутах 2K+1…3K, и т.д. Другими словами,

на минуте 1 меняются местами коровы на позициях a₁ и b₁.
на минуте 2 меняются местами коровы на позициях a₂ и b₂.
...
На минуте K меняются местами коровы на позициях a_K и b_K swap.
На минуте K+1, меняются местами коровы на позициях a₁ и b₁.
На минуте K+1, меняются местами коровы на позициях a₂ и b₂.
и т.д. ...
Для каждой коровы определите количество уникальных позиций, которые она посетит во время бесконечного танца.

Входные данные
Первая строка ввода содержит целые числа N и K. Каждая из последующих K строк содержит (a₁,b₁)…(a_K,b_K) (1≤a_i<b_i≤N).
Выходные данные
Выведите N строк, где i-ая строка содержит количество уникальных позиций, которые посетит корова i.

Примеры

№	Входные данные	Выходные данные	Пояснение
1	5 4 1 3 1 2 2 3 2 4	4 4 3 4 1	Корова 1 достигнет позиций {1,2,3,4}. Корова 2 достигнет позиций {1,2,3,4}. Корова 3 достигнет позиций {1,2,3}. Корова 4 достигнет позиций {1,2,3,4}. Корова 5 не будет двигаться, и не покинет позицию 5.

Обход в глубину Перестановки

✓ 1✗ 11 100средняяВойти и решать

Фотография коров#39570

Фермер Джон хочет сфотографировать своих пасущихся коров, чтобы повесить эту фотографию на стене. Пастбище представлено решёткой из N * N ячеек (как шахматная доска размером N×N) (2≤N≤1000). ФД хочет, чтобы коровы были распределены по пастбищу с выполнением следующих правил:
Никакие две коровы не могут находится в одной и той же ячейке.
Каждая подрешётка размером 2×2 (всего таких подрешёток (N−1)×(N−1)) должна содержать ровно 2 коровы
Например, такое размещение соотвествует правилам:

CCC
...
CCC
А такое размещение - нет

C.C
.C.
C..
поскольку 2×2 регион в правом нижем углу содержит только одну корову.
Других ограничений нет. Вы можете считать, что у ФД есть бесконечное количество коров.

Некоторые ячейки более предпочтительный для ФД, нежели другие. В частности, ФД считает. что если корова размещена в ячейке (i,j), красота фотографии увеличивается на a_ij (0≤a_ij≤1000) единиц.

Определите максимально возможную красоту корректного размещения коров.

Входные данные
Первая строка содержит число N. Каждая из следующих N строк содержит по N целых чисел. j-ое число в i-ой строке сверху есть значение a_ij.
Выходные данные
Выведите одно целое число - максимально возможную красоту результирующего фото.

Примеры

№	Входные данные	Выходные данные	Пояснения
1	4 3 3 1 1 1 1 3 1 3 3 1 1 1 1 3 3	22	В этом примере максимальная красота может быть достигнута следующим размещением: CC.. ..CC CC.. ..CC Красота этого размещения 3+3+3+1+3+3+3+3=22.

Перебор

✓ 2✗ 341 000средняяВойти и решать

Коровий алфавит#39561

Малоизвестен тот факт, что у коров свой алфавит "cowphabet". Он состоит из тех же 26 букв от 'a' до 'z', но в другом порядке.
Чтобы скоротать время, Беси бормочет cowphabet опять и опять. Фермеру Джону интересно, сколько раз она его пробормотала.

По заданной строке букв, которые ФД расслышал из бормотания Беси, определите минимальное количество раз, которое Беси должна пробормотать cowphabet, чтобы ФД услышал заданную строку. ФД не всегда обращает внимание на бормотание Беси, поэтому он может не расслышать некоторые буквы из бормотания Беси. Данная Вам строка содержит только те буквы, которые он услышал.

Входные данные
Первая строка ввода содержит 26 маленьких латинских букв от 'a' до 'z' в порядке их появления в cowphabet. Следующая строка содержит строку из маленьких латинских букв, которые услышал ФД. Эта строка имеет длину от 1 до 1000.
Выходные данные
Выведите минимальное количество раз, которое Беси пробормотала алфавит.

Примеры

№	Входные данные	Выходные данные	Пояснение
1	abcdefghijklmnopqrstuvwxyz mood	3	В этом примере cowphabet упорядочен как нормальный алфавит. Бесси пробормотала cowphabet как минимум 3 раза. Ниже показано, как Беси бормотала, и большими буквами - какие буквы услышал ФД. abcdefghijklMnOpqrstuvwxyz abcdefghijklmnOpqrstuvwxyz abcDefghijklmnopqrstuvwxyz

Перебор Строки

✓ 9✗ 7800средняяВойти и решать

Треугольники#39517

Фермер Джон хочет создать треугольное пастбище для своих коров.
Всего имеется N столбов забора (3 ≤ N ≤ 100) как различных (X₁,Y₁)…(X_N,Y_N) точек на карте фермы. Он может выбрать три из них чтобы сформировать вершины треугольного пастбища, но так чтобы одна из сторон была параллельна оси x, а другая - параллельно оси y.

Какова сумма площадей всех возможных пастбищ, которые может сформировать ФД?

Входные данные
Первая строка содержит N.
Каждая из последующих N строк содержит два целых числа Xi и Yi, каждое в интервале −10⁴…10⁴ включительно, описывающих положение столба.

Выходные данные
Поскольку сумма площадей может быть числом не целым и очень большим, выведите остаток от деления удвоенной суммы площадей на 10⁹+7.

Примеры

№	Входные данные	Выходные данные	Пояснение
1	4 0 0 0 1 1 0 1 2	3	Точки (0,0), (1,0), (1,2) образуют треугольник с площадью 1. Точки (0,0), (1,0), (0,1) образуют треугольник с площадью 0.5. Поэтому ответ 2⋅(1+0.5)=3.

Вывод формулы Перебор

✓ 2✗ 41 000средняяВойти и решать

Раз-два-три-четыре-пять корову поменять#39514

N коров (1 ≤ N ≤ 10⁵) Фермера Джона стоят в ряд. i-ая корова слева имеет метку i (1 ≤ i ≤ N).
ФД дал коровам M пар целых чисел s (L₁,R₁)…(L_M,R_M), где 1 ≤ M ≤ 100. Затем он сказал коровам повторить ровно K (1 ≤ K ≤ 10⁹) раз процесс из M шагов:

Для каждого i от 1 до M:
Последовательность коров на позициях Li…Ri слева реверсивно меняют свой порядок.
Выведите метки всех коров слева направо для каждого i, (1 ≤ i ≤ N) после завершения описанного процесса.

Входные данные
Первая строка содержит числа N, M, K. Для каждого 1 ≤ i ≤ M строка i+1 содержит L_i и R_i, два целых числа в интервале 1…N, где L_i<R_i.

Выходные данные
На i-ой строке вывода, выведите i-ый элемент массива после выполнения всех инструкций K раз.

Примеры

№	Входные данные	Выходные данные	Пояснение
1	7 2 2 2 5 3 7	1 2 4 3 5 7 6	Изначально порядок коров слева направо такой [1,2,3,4,5,6,7] После первого шага процесса порядок станет таким [1,5,4,3,2,6,7] После второго шага процесса порядок станет таким [1,5,7,6,2,3,4]. Повторив оба шага ещё раз получим результат, приведенный в выводе.

Быстрое возведение в степень Вывод формулы Перестановки

✓ 1✗ 121 200средняяВойти и решать

Социальное дистанцирование I#39390

Ужасная болезнь поражает коров. Фермер Джон хочет их защитить.
Амбар ФД - это узкое длинное здание, содержащее N стойл в ряд (2≤N≤105). Некоторые из этих стойл уже заняты коровами, некоторые - свободны. Прочитав о необходимости социального дистанцирования, ФД хочет максимизировать D, где D, это расстояние между двумя ближайшими занятыми стойлами. Например, если стойла 3 и 8 ближайшие, которые заняты, тогда D=5.

Две новых коровы пополнили стадо ФД и он должен решить, в какое не занятое стойло разместить каждую из них. Определите, ка к он должен разместить этих коров, чтобы в результате D, стало максимальным из возможных. ФД не может передвигать никакую из имеющихся коров, он может только назначить стойла новым коровам.

Входные данные
Первая строка ввода содержит N. Следующая строка содержит строку длиной N из 0 и 1, описывающая последовательность стойл в амбаре. 0 означает пустое стойло, 1 означает занятое стойло. В строке имеется как минимум два нуля, что достаточно для размещения двух коров.
Выходные данные
Выведите наибольше значение D (наименьшее расстояние между двумя занятыми стойлами), которое ФД может получить добавлением двух новых коров оптимальным образом.

Примеры

№	Входные данные	Выходные данные
1	14 10001001000010	2	В этом примере ФД может добавить коров так: 10x010010x0010 где x показывает новых коров. В этом случае D=2. Невозможно разметить коров так, чтобы получить D больше.

Простые задачи на перебор Разбор случаев Условный оператор

✓ 1✗ 1—Войти и решать