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

Cow Coupons#89818

Фермер Джон хочет купить новых коров! На продаже имеется N (1 <= N <= 50,000) коров, а у ФД может потратить не более, чем M (1 <= M <=10^14) единиц денег. Корова I стоит P_i денег (1 <= P_i <= 10^9). У ФД имеется K купонов (1<=K<=N). Когда он использует купон для покупки коровы I, то цена будет C_i вместо P_i (1<=C_i<=P_i). Для каждой коровы ФД должен использовать ровно один купон.
Какое максимальное количество коров может купить ФД?
PROBLEM NAME: coupons
Формат входных данных
* Строка 1: Три разделенных пробелом целых числа: N, K, M.
* Строки 2..N+1: Срока i+1 содержит два целых числа: P_i C_i.
Формат выходных данных
* Строка 1: Одно целое число, максимальное количество коров, которое может купить ФД.
Примечание
ФД использует купон при покупке коровы 3 и купит коров 1, 2, 3 за цену 3 + 2 + 1 = 6.

Жадный алгоритм

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

Rope Folding#89817

У Фермера Джона есть длинная веревка длины L (1 <= L <= 10,000), которую он использует на ферме. На веревке завязаны N (2 <= N <= 100) узлов на различных расстояниях, в том числе на обоих концах.
ФД заметил, что имеются определенные точки на веревке, в которой он может перегнуть веревку назад, так что узлы на обоих частях веревки станут точно рядом друг с другом.

Пожалуйста, помогите ФД посчитать количество точек перегиба, в которых соблюдается это свойство. Допускается складывание веревки в любом из узлов (кроме начала и конца веревки). Лишние узлы на более длинной части веревки не принимаются во внимание (то есть необходимо обеспечить выравнивание узлов в области, где есть обе части веревки). Делать можно только одно складывание за один раз. ФД не умеет складывать веревку много раз.
PROBLEM NAME: folding
Формат входных данных
* Строка 1: Два разделенных пробелом целых числа, N и L.
* Строки 2..1+N: Каждая строка содержит одно целое число в интервале 0...L Указывающее расположение одного узла. Две из этих строк будут всегда 0 и L.
Формат выходных данных
* Строка 1: Количество корректных позиций перегиба веревки.
Примечание
Корректные позиции перегиба 1, 2, 3, 8.

Задачи на моделирование

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

Moo#89815

Коровы придумали новую игру “Moo”. Они стоят в ряд, где каждая корова отвечает за то, чтобы назвать конкретную букву как можно быстрей.
Последовательность букв определена до бесконечности. Ее начало представлено ниже:
m o o m o o o m o o m o o o o m o o m o o o m o o m o o o o o
Эта последовательность проще всего описывается рекурсивно. Пусть S(0) будет последовательность из трех символов "m o o". S(k) получается конкатенацией: копии последовательности S(k-1), затем “m o … o” c k+2 символами ‘o’ и затем еще одна копия последовательности S(k-1). Например:
S(0) = "m o o" S(1) = "m o o m o o o m o o" S(2) = "m o o m o o o m o o m o o o o m o o m o o o m o o"
Очевидно, так можно построить строку любой длины и эта строка используется для игры в “Moo”.
Беси, которая про себя думает, что она умная корова, хочет предсказать, Каким будет символ на позиции N – ‘m’ или ‘o’. Помогите ей!
PROBLEM NAME: moo
Формат входных данных
* Строка 1: Одно целое число N (1 <= N <= 10^9).
Формат выходных данных
* Строка 1: Единственная строка вывода должна содержать один символ, ‘m’ или ‘o’.

Рекуррентные последовательности

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

Wifi Setup#89814

N (1 <= N <= 2000) коров Фермера Джона расположены на прямой линии (дороге от амбара до пастбища). ФД хочет расставить вдоль этой прямой точки беспроводного доступа в Internet, так чтобы все коровы были в зоне покрытия.
Стоимость wifi-станции зависит от расстояния, ан которое она может передавать сигнал. Станция с мощностью(радиусом действия) r стоит A + B*r , где A - фиксированная цена установки станции B - стоимость на 1 расстояния, на которое передается информация.
Если такая станция установлена в позиции x, то она может передавать данные до любой коровы, расположенной в интевале x-r...x+r. Допускается станция с мощностью передачи 0, но, поскольку r=0, она будет работать только для коровы, размещенной в самой точке x размещения станции.
По заданным величинам A и B, а также координатам коров, определите самый дешевый способ, которым ФД сможет обеспечить беспроводное покрытие всех своих коров.
PROBLEM NAME: wifi
Формат входных данных
* Строка 1: Три разделенных пробелом целых числа: N A B (0 <= A, B <= 1000).
* Строки 2..1+N: Каждая строка содержит одно целое число в диапазоне 0..1,000,000 описывающее размещение одной коровы.
Формат выходных данных
* Строка 1: Минимальная стоимость обеспечения беспроводным покрытием всех коров.
Примечание
Оптимальное решение - построить базовую станцию в позиции 3.5 (с мощностью/радиусом действия 3.5) и другую станции в позиции 100 с мощностью (радиусом действия) 0. Первая станция обеспечит покрытие коров 1 и 2, вторая - коровы 3.

Жадный алгоритм

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

Running Away From the Barn#89811

Время дойки на ферме Джона, но коровы сбежали. Ферма Джона - это множество из N (1 <= N <= 200,000) пастбищ, пронумерованных от 1 до N, и связанных N - 1 двунаправленными дорожками. Амбар расположен в пастбище 1 и любое пастбище достижимо от амбара.
Коровы бегут в сторону "от амбара" и они пробегают расстояние не больше чем L. Для каждого пастбища ФД хочет знать, в скольки различных пастбищах могут оказаться коровы, сбежавшие с этого пастбища.
Замечание: используйте 64-битные целые (int64 в Pascal, long long в C/C++ и long в Java) для хранения расстояний.
PROBLEM NAME: runaway
Формат входных данных
* Строка 1: 2 целых числа, N и L (1 <= N <= 200,000, 1 <= L <= 10^18)
* Строки 2..N: i-ая строка содержит два целых числа p_i и l_i. p_i (1 <= p_i < i) - первое пастбище на кратчайшем пути между пастбищем i и амбаром l_i (1 <= l_i <= 10^12) - длина этого пути
Формат выходных данных
* Строки 1..N: По одному числу в строке. Число в строке i - количество пастбищ, которые могут быть достигнуты из пастбища i, выбирая дороги, строго удаляясь от амбара (пастбище 1) с суммарной длиной не превышающей L.
Примечание
Корова из пастбища 1 может добежать до пастбищ 1, 2, 4. Корова из пастбища 2 может добежать до пастбищ 2, 3. Пастбища 3 и 4 - конечные, оттуда некуда бежать, можно только остаться в них.

Дерево отрезков, RSQ, RMQ Деревья

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

Gangs of Instanbull_Cowstantinople#89810

Коровы сформировали банды, пронумерованные от 1 до M.
Теперь эти банды борются за контроль над большим пастбищем.
Каждую минуту одна корова идет в поле. Если это поле пустое, считается, что ее банда взяла контроль над ним. Если поле уже под контролем этой банды, то корова просто начинает на нем пастись. Иначе возникает конфликт между новой коровой, и той коровой из другой банды, которая там паслась.
В результате этого конфликта обе коровы "аннигилируются" (то есть выходят из своих банд и покидают это поле). Поле становится пустым и бесконтрольным. Никакая банда его не контролирует.
Беси знает сколько коров в каждой банде. Беси хочет чтобы ее банда контролировала поле после завершения конфликта.
Помогите Беси определить, может ли ее банда (номер 1) контролировать поле в конце.
Если это возможно, Беси хочет знать максимальное количество коров из ее банды, которое может остаться на поле в конце.
Выведите это количество и лексикографически раннюю перестановку коров, которая приведет к этому числу.
Перестановка X называется более ранней чем перестановка Y, если есть некоторое k, для которого X[k] < Y[k] и X[i]=Y[i] для всех i < k.
PROBLEM NAME: gangs
Формат входных данных
* Строка 1: N (1 <= N <= 100) и M (1 <= M <= N) разделенные пробелом. N - общее число коров во всех бандах. M - общее число банд.
* Строки 2..1+M: (1+i)-ая строка указывает количество коров в банде i. В каждой банде есть хотя бы одна корова.
Формат выходных данных
* Строка 1: Выведите YES на одной строке, если банда Беси может взять контроль над полем, иначе выведите NO.
* Строка 2: Если банда Беси сможет взять контроль над полем выведите здесь максимальное количество коров, которые там будут пастись после окончания конфликта.
* Строки 3..2+N: На (i+2)-ой вывести индекс банды коровы, которая должна появится на i-ой минуте на поле в лексикографически ранней перестановке которая обеспечит максимальное количество коров в поле после конфликта.
Примечание
Только одна корова из банды Беси может остаться на поле

Жадный алгоритм

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

First!#89809

Беси опять играет со строками. Она обнаружила, что изменяя порядок алфавита она може добиться, чтобы некоторая строка стала лексикографически раньше всех.
Например, среди строк
"omm", "moo", "mom", "ommnom"
она может сделать первой строку "mom", используя стандартный алфавит. и она может сделать первой строку "omm" используя алфавит "abcdefghijklonmpqrstuvwxyz". Однако Беси не знает как сделать первым слово "moo" или "ommnom"
Помогите Беси вычислить строки из ввода, которые можно сделать первыми изменив порядок букв в алфавите.
Чтобы определить, что строка X лексикографически раньше cтроки Y найдите индекс первого символа в котором они различаются j. Если такого индекса нет, тогда X лексикографически меньше чем Y, если X короче чем Y, иначе, X лексикографически раньше чем Y, если X[j] находится в алфавите раньше чем Y[j].

PROBLEM NAME: first
Формат входных данных
* Строка 1: целое N (1 <= N <= 30,000),количество строк, с которыми играет Беси
* Строки 2..1+N: Каждая строка содержит не пустую строку символов. Общее количество символов во всех строках не превысит 300,000. Все символы на вводе - маленькие латинские буквы от 'a' до 'z'. Во вводе нет повторяющихся строк.

Формат выходных данных
* Строка 1: одно число K, количество строк, которые могут быть лексикографически первыми.
* Строки 2..1+K: (1+i)-ая строка должна содержать i-ую строку, которая может быть лексикографически первой. Строки нужны выводить в том же порядке, в котором они следовали на вводе.
Примечание
Только "omm" и "mom" могут стать первыми.

Бор графы Топологическая сортировка

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

Scrambled Letters#89808

Фермер Джон поддерживает алфавитно упорядоченный список имен своих N
(1 <= N <= 50,000) коров. Каждое имя коровы представлено уникальной
строкой от 1 до 20 маленьких латинских символов.

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

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

PROBLEM NAME: scramble

Формат входных данных

* Строка 1: Одно целое число N.

* Строки 2..1+N: Каждая из этиз строк содержит реорганизованное имя
одной из коров

Формат выходных данных

* Строки 1..N: Строка i должна указывать, для входной строки i,
самую маленькую и самую большую позицию в исходном списке
на котором могла быть оригинальная версия строки i.

Примечание

Строка 'a' может быть только первой, а строка 'xyz' - только последней,
вне зависимости как переупорядочены их буквы .
Строки "essieb" и "elsie" могут занимать 2 или 3-ю позицию в зависимости
от той буквы, которая была первой в оригинальном имени:
например "bessie" (позиция 2) и "bessie" (позиция 3)
и наоборот
"sisbee" (позиция 3) и "ilees" (позиция 2)).

Использование сортировки

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

Meet and Greet#89807

Коровы очень вежливы, каждый раз при встрече они приветствуют коллегу дружеским 'moo'.
Бэси и Эльза ходят вдоль прямой вперед и назад. Начинают в точке 0 и двигаются с одинаковой скоростью. По описаниям движения каждой из коров определите количество 'moo', которыми они обменялись.
Беси и Эльза могут останавливать движение в различные точки времени, и никогда не гуляют более чем 1,000,000 единиц времени.
PROBLEM NAME: greetings
Формат входных данных
* Строка 1: Два разделенных пробелом целых числа, B (1 <= B <= 50,000) и E (1 <= E <= 50,000).
* Строки 2..1+B: Эти B строк описывают движение Беси. Каждая строка содержит положительное целое, за которым следует символ "L" или "R", обозначающий пройденное Беси расстояние влево или вправо.
* Строки 2+B..1+B+E: Эти E строк описывают движение Эльзы. Каждая строка содержит положительное целое, за которым следует символ "L" или "R", обозначающий пройденное Эльзой расстояние влево или вправо.
Формат выходных данных
* Строка 1: Одно целое число, указывающее количество 'moo', которыми обменялись две коровы. Их начальное совместное положение в точке 0, не вызывает 'moo'.
Примечание
Беси и Эльза встречаются в моменты времени 7, 9, 13

Задачи на моделирование

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

Tile Exchanging#89805

Problem 3: Tile Exchanging [Ray Li]
Фермер Джон хочет покрыть пол в своем амбаре коллекцией квадратных плиток, которые он купил в магазине. К несчастью, Он не измерял точно размер своего амбара перед покупкой, поэтому сейчас он должен обменять часть плиток на другие, тоже квадратные, но других размеров.
N квадратных плиток которые ФД купил изначально имеют длины сторон A₁...A_N. Он хочет обменять часть из этих плиток так, чтобы общая сумма площадей всех плиток была ровно M.
При этом необходимо соблюсти правила обмена, установленные магазином: - плитка со стороной с длиной A_i может быть обменяна на другую плитку со стороной с длиной B_i за цену (A_i-B_i)* (A_i-B_i). Однако менять можно только ранее купленные плитки. Нельзя Менять плитку, полученную в результате обмена некоторой из ранее купленных плиток. Например, нельзя обменять плитку со стороной 3 на плитку со стороной 2 и потом плитку со стороной 2 поменять на плитку со стороной 1.
Определите минимальное количество денег, которое требуется ФД, чтобы сделать сумму площадей плиток равной M. Выведите –1, если невозможно получить площадь M.
PROBLEM NAME: tilechng
Формат входных данных
* Строка 1: Два разделенных пробелом целых числа, N (1<=N<=10) и M (1<=M<=10,000).
* Строки 2..1+N: Каждая строка содержит одно целое число (от A₁ до A_N, описывающих длины сторон входных квадратных плиток (1<=A_i<=100).
Формат выходных данных
* Строка 1: Минимальная стоимость обменов чтобы получить площадь M, или –1, если получить площадь M невозможно.
Примечание
Обменяем первую плитку со стороной 3 на плитку со стороной 2 square, а вторую плитку со стороной 3 на плитку со стороной 1. Это дает суммарную площадь 4+1+1=6 за цену 4+1=5.

Задача о рюкзаке

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

Cow Lineup#89804

Problem 2: Cow Lineup [Brian Dean]
Фермер Джон нанял профессионального фотографа, чтобы сфотографировать некоторых из своих коров. Поскольку у него есть коровы разных пород, он хочет иметь фото как минимум одной коровы каждой породы.
N коров ФД выстроены в ряд (позиция каждой указывается x-координатой) и целочисленным номером породы. ФД планирует сделать фотографию непрерывного участка коров. Стоимость фотографии равна ее размеру – то есть разностью между максимальной и минимальной x-координатами коров, представленных на фотографии.
Помогите ФД вычислить минимальную стоимость фотографии, в которой находится по крайней мере одна корова каждой породы.
PROBLEM NAME: lineup
Формат входных данных
* Строка 1: количество коров, N (1 <= N <= 50,000).
* Строки 2..1+N: Каждая строка содержит два числа, разделенных одиночным пробелом, указывающих x-координату и номер породы одной коровы. Оба числа не превосходят миллиард.
Формат выходных данных
* Строка 1: Минимальную стоимость фотографии, содержащей не менее одной коровы каждой породы.
Примечание
Диапазон от x=22 до x=26 (длиной 4) содержит коровы всех пород (1,3,7).

"Два указателя"

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

Cow Beauty Pageant (Silver Level)#89803

Problem 1: Cow Beauty Pageant (Silver Level) [Brian Dean]
Прослышав, что модно иметь коров с тремя пятнами, Фермер Джон купил целое стадо таких коров. К несчастью, мода меняется очень быстро, и сейчас в моде коровы с одним пятном.
ФД теперь хочет подкрасить своих коров так, чтобы они стали с одним пятном. Раскраска коровы задается двумерным массивом символов (N*M), например, так:
................ ..XXXX....XXX... ...XXXX....XX... .XXXX......XXX.. ........XXXXX... ..XXX....XXX....
Здесь 'X' обозначает часть пятна. Два символа 'X' принадлежат одному и тому же пятну, если они соседние вертикально или горизонтально (диагональные соседними не являются). Все коровы ФДЖ имеют ровно 3 пятна.
ФД хочет потратить как можно меньше краски, чтобы объединить три пятна в одно. На примере выше, он может сделать это, покрасив только 4 позиции, они обозначены символом ‘*’ на рис. ниже.
................ ..XXXX....XXX... ...XXXX*...XX... .XXXX..**..XXX.. ...*....XXXXX... ..XXX....XXX....
Помогите ФД определить минимальное количество клеток(символов), которые нужно закрасить, чтобы объединить три пятна в одно.
PROBLEM NAME: pageant
Формат входных данных
* Строка 1: Два разделенных пробелом целых числа, N и M (1 <= N,M <= 50).
* Строки 2..1+N: Каждая содержит строку из M символов 'X' и '.', указывающих соответствующую линию раскраски коровы.
Формат выходных данных
* Line 1: Минимальное количество сиволов 'X', которые нужно добавить ко введенным данным, чтобы получить единое пятно.
Примечание
4 символа ‘X’ нужно добавить, чтобы получить одно пятно.

Обход в ширину

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

Awkward Digits#89796

Problem 2: Awkward Digits [Brian Dean]
Бесси учиться конвертировать числа между системами счисления, с различными основаниями, но она делает ошибки, поскольку тяжело держать ручку между копытами.
Когда Бесси записывает результат конвертирования, она всегда записывает одну цифру с ошибкой. Например, если она конвертирует число 14 в двоичную систему, корректный результат будет 1110, но она может написать вместо него «0110» или «1111». Бесси никогда не добавляет и не удаляет цифры, но у нее может получится число с ведущим нулем в результате ее ошибки.
Вам дается ответ, записанный Бесси при конвертировании числа N К основаниям 2 и 3. Определите исходное значение числа N в десятичной системе счисления. Вы можете полагать, что N не превосходит 1 миллиард, и что всегда существует уникальное значение N.
PROBLEM NAME: digits
Формат входных данных
* Строка 1: представление числа N в двоичной системе счисления, одна цифра записана некорректно. (основание=2)
* Строка 2: представление числа N в троичной системе счисления, одна цифра записана некорректно (основание=3).
Формат выходных данных
* Строка 1: корректное значение числа N.
Примечание
Корректное значение числа 14 ("1110" в двоичной системе, "112" в троичной).

Системы счисления

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

Cow Photography#89793

Фермер Джон хочет сделать фотографию коров, которые стоят в ряд. А они все время перемещаются.
У ФД есть N (1 <= N <= 20,000) коров, каждая из которых имеет уникальный идентификатор - целое число. ФД хочет сфотографировать своих коров в особом порядке, который определяется содержимым массива A[1...N], где A[j] содержит ID j-ой коровы в правильном порядке.
ФД выстраивает своих коров, но прежде чем он успеет нажать кнопку "зафиксировать фотографию", группа коров (необязательно непрерывная) переходит на множество новых позиций (также необязательно непрерывных). ФД опять их выстраивает в желанном порядке, а часть коров снова перед самы нажатием меняет свои позиции. Так продолжается 5 раз.
Вам дается содержание каждой из этих 5 фотографий. Вы должны, если сможете, восстановить правильный порядок, заданныq массивом A.
Каждая фотография задает порядок, который в нескольких позициях отличается от правильного порядка. На каждой фотографии некоторые коровы перешли на другие позиции. Однако каждая корова перешла на новую позицию не более чем в одной фотографии. Более того, могут быть фотографии, на которых ни одна корова не меняла свою позицию.
PROBLEM NAME: photo
Формат входных данных
* Строка 1: Количество коров, N (1 <= N <= 20,000).
* Строки 2..5N+1: Следующие 5N строк описывают пять упорядочиваний, каждое одним блоком из N строк. Каждая строка содержит ID коровы целое число в диапазоне от 0 до 1,000,000,000.
Формат выходных данных
* Строки 1..N: Запланированный порядок A, по одному ID в строке.
Примечание
Запланированный порядок A[1..5]: 10, 20, 30, 40, 50.

Использование сортировки

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

Simplifying the Farm#89792

Фермер Джон изучает программирование на вечерних курсах при местном университете и сейчас проходит тему "минимальное остовное дерево". Он осознал, что проект его фермы не оптимален, и хочет его улучшить.
Ферма сейчас организована в виде графа, вершины которого представляют поля, а ребра представляют дорожки между этим полями, с каждой ассоциирована ее длина.
ФД заметил, что для каждой длины имеется не более трех дорожек, имеющих такую длину. ФД хочет удалить некоторые из дорожек на своей ферме так, чтобы получилось дерево - то есть, чтобы существовал единственный путь между любыми двумя полями. Более того, Фд хочет, чтобы это было минимальное остовное дерево, то есть дерево, которое имеет минимально возможную сумму длин всех дорожек.
Помогите ФД вычислить не только сумму длин всех дорожек в минимальном остовном дереве, но также количество различных возможных минимальных остовных деревьев, которые он может создать.
PROBLEM NAME: simplify
Формат входных данных
* Строка 1: Два целых числа N и M (1 <= N <= 40,000; 1 <= M <= 100,000), представляющих количество вершин и ребер соответственно. Вершины пронумерованы от 1 до N.
* Строки 2..M+1: Три целых числа a_i, b_i n_i (1 <= a_i, b_i <= N; 1 <= n_i <= 1,000,000) представляющих ребро от вершины a_i до b_i длиной n_i. Никакое ребро с длиной n_i не встретиться более трех раз.
Формат выходных данных
* Строка 1: Два целых числа, представляющих длину минимального остовного дерева и количество минимальных остовных деревьев (по модулю 1,000,000,007)
Примечание
Выбрав оба ребра с длиной 1 и любое ребро с длиной 2 мы получим минимальное остовное дерево с длиной 4.

Минимальный каркас

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

Grass Planting#89791

У Фермера Джона есть N пастбищ (2 <= N <= 100,000), соединенных N-1 двунаправленными дорогами так, что ровно один путь существует между любыми двумя пастбищами.
Бесси, любимая корова ФД пожаловалась, что на дорогах нет травы, и ФД решил посадить траву на дорогах.
Он делает это, используя процедуру, которая состоит из M шагов. (1 <= M <=100,000).
На каждом шаге происходит одна из двух вещей:
- ФД выбирает два пастбища и высаживает траву на каждой дороге пути между ними - Бесси спрашивает, сколько дорог засажено травой на конкретном пути, и ФД должен ей ответить.
Помогите ФД отвечать на вопросы.
PROBLEM NAME: grassplant
Формат входных данных
* Строка 1: Два разделенных пробелом целых числа N и M
* Строки 2..N: Два разделенных пробелом целых числа, описывающих конечные точки дороги.
* Строки N+1..N+M: Строка i+1 описывает шаг i. Первый символ этой строки либо P либо Q, которые описывают ФД садит траву или отвечает на вопрос. Затем следуют два разделенных пробелом целых числа A_i B_i (1 <= A_i, B_i <= N), которые описывают путь (для действия или вопроса)
Формат выходных данных
* Строки 1..???: Каждая строка содержит ответ на вопрос, в порядке поступления вопросов

Деревья

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

Cow Photography#89790

Использование сортировки

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

Escaping the Farm#89788

Коровы планируют сбежать от Фермера Джона на плоту, через реку. Проблема заключается в том, что плот может не выдержать всех желающих. N коров (1 <= N <= 20) имеют веса w₁ ... w_N. У коров плохо со сложением, они не умеют выполнять перенос. Вам требуется определить размер наибольшей группы коров, веса которых можно сложить без переноса при сложении.
PROBLEM NAME: escape
Формат входных данных
* Строка 1: Количество коров, N (1 <= N <= 20).
* Строки 2..N+1: Каждая строка содержит вес одной коровы, целое число от 1...100,000,000.
Формат выходных данных
* Строка 1: максимальное количество коров, чьи веса могут быть сложены без переноса.

Примечание
Три веса 522, 6, 7311, могут быть сложены без переноса.
522 6 + 7311 ------ 7839

битмаски Перебор

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

Cow Photography (Bronze Level)#89787

Problem XX: Cow Photography (Bronze) [Brian Dean, 2011]
Фермер Джон хочет сделать фотографию всех коров, выстроенных в ряд, а они не стоят на месте. N (1 <= N <= 20,000) коров помечены номерами от 1 до N. ФД хочет сфотографировать их, стоящими в ряд в конкретном порядке, заданном массивом A[1..N], где a[j] содержит номер j-той коровы в этом порядке. ФД выстроил коров в этом порядке, но прежде чем он нажал на клавишу фотоаппарата "Сделать снимок", одна корова переместилась на новую позицию. Он снова поставил их в нужном порядке (указанном массивом A), Но снова перед нажатием кнопки уже другая корова переместилась на новую позицию. Так происходило 5 раз. Вам дано содержание каждой фотографии, Вы должны реконструировать содержимое массива A. На каждой из фотографий не более чем одна корова переместилась на новую позицию. Возможно, что ни одна корова не перемещалась.
PROBLEM NAME: photo
Формат входных данных
* Строка 1: Количество коров, N (1 <= N <= 20,000).
* Строки 2..5N+1: Следующие 5N строк описывают 5 порядков, каждый состоит из N последовательных строк. Каждая строка содержит номер коровы, целое число.
Формат выходных данных
* Строки 1..N: Исходный порядок коров в массиве A, по одному ID в строке.
Примечание
Правильный исходный порядок в массиве A[1..5]: 1, 2, 3, 4, 5.

Использование сортировки

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

Выбор участка - 1 (24-25)#89300

Маша хочет построить дачу на одной приглянувшейся ей улице. Эта улица имеет длину n, то есть состоит из n одинаковых идущих подряд участков. На каждом участке указан уровень шума от 1 до 9 (где 1 — тишина, 9 — очень шумно).

Маша хочет найти участок с уровнем шума ровно 1 (тихий участок), который находится максимально далеко от шумных участков. Шумным считается участок с уровнем шума 7 или больше.

Необходимо написать программу, которая найдёт номер такого тихого участка и расстояние до ближайшего шумного участка.

Если таких участков несколько, выбрать участок с наименьшим номером.

Гарантируется, что есть хотя бы один тихий участок (уровень шума 1) и хотя бы один шумный участок (уровень шума ≥ 7).

Формат входных данных

В первой строке натуральное число n (1 ≤ n ≤ 6 000 000)
Во второй строке n чисел от 1 до 9 через пробел

Формат выходных данных

Номер участка и расстояние до ближайшего шумного (через пробел)

Линейный поиск

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