Язык программирования

633 задачивместе с подтемами
Число у задачи — рейтинг сложности, слово рядом — насколько она трудна по сравнению с другими задачами такого же типа. Шкалы задач с ответом и задач с кодом между собой не сравниваются. Рядом — счётчики попыток: ✓ успешные, ✗ неуспешные.
РейтингЛюбойдо 800800–11991200–15991600+Без рейтинга
СначалаПодходящиеНовыеПопулярныеПростыеСложные
Taming the Herd#90005
Однажды утром Фермер Джон проснулся от звуков дробления древесины. Это коровы ломали амбар.

ФД рассердился. Он приделал к стене счётчик дней с последнего слома. Если слом случился утром, счётчик покажет 0. Если последний слом случился 3 дня назад, счётчик показывает 3. ФД тщательно записывал значение счётчика каждый день.

В конце года ФД решил действовать. Однако с логом некоторые проблемы.

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

ФОРМАТ ВВОДА (файл taming.in):

Первая строка ввода содержит одно целое число \(N\) (\(1 \leq N \leq 100\)), обозначающее количество дней, с дня когда ФД начал логгирование.

Вторая строка содержит \(N\) целых чисел, разделённых одиночными пробелами. \(i\)-ое число это неотрицательное целое \(a_i\) (не более 100), указывающее что в день \(i\) на счётчике было \(a_i\) если коровы не подделали эту запись в логе.

ФОРМАТ ВЫВОДА (файл taming.out):

Вывод состоит из \(N\) целых чисел, по одному в строке. \(i\)-ое целое число должно содержать минимум из всех возможных последовательностей с \(i\) сломами количества записей, которые несостоятельны в этой последовательности.

Динамическое программирование: один параметрЖадный алгоритмРазбор случаев
—Войти и решать
Bessie Goes Moo#89959
Фермер Джон и корова Беси в свободное время любят обмениваться математическими головоломками. Последняя головоломка, которую ФД дал Беси была очень сложной и Беси не смогла решить ей. Теперь она хочет дать ФД очень сложную головоломку.

Беси даёт ФД выражение \((B+E+S+S+I+E)(G+O+E+S)(M+O+O)\), содержащее семь переменных \(B,E,S,I,G,O,M\) (the "\(O\)" это переменная, а не 0). Для каждой из переменных она даёт ФД список до 500 целых значений, которые та может принять. Она просит ФД посчитать количество способов, получить результат, кратный числу 7.

Заметим, что ответ на эту задачу может быть слишком большим, чтобы пометситься в 32-битную переменную, рекомендуется использовать 64-битную переменную типа long long в С/С++.

ФОРМАТ ВВОДА (файл bgm.in):

Первая строка ввода содержит целое число \(N\). Каждая из последующих \(N\) строк содержит переменную и возможное значение этой переменной. Каждая переменная появится в этом списке не менее одного и не более 500 раз. Для одной и той же переменной никакие значения не повторяются. Все возможные значения находятся в диапазоне \(-10^5\) до \(10^5\).

ФОРМАТ ВЫВОДА (файл bgm.out):

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

Вывод формулы
✓ 0✗ 1—Войти и решать
Moocryption#89953
Коровы увлекаются словесными пазлами. Например, таким 

USOPEN
OOMABO
MOOMXO
PQMROM

Как коровам, им интересно только единственное слово "MOO", которое может появиться во многих местах горизонтально, вертикально или по диагонали. Пример сверху содержит 6 таких слов.

Фермер Джон тоже любитель таких пазлов. Поскольку коровы не хотят, чтобы он разгадывал пазлы раньше коров, они зашифровали пазл, используя заменяющий шифр, который заменяет каждую букву алфавита некоторой другой, отличающейся буквой. Например, A может заменяться буквой X, B - буквой A и т.д. Никакая буква не заменяется собой и никакие две буквы не заменяются одной и той же буквой (иначе расшифровка может стать неоднозначной).

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

ФОРМАТ ВВОДА (файл moocrypt.in):

Первая строка ввода содержит \(N\) и \(M\), описывающие количество строк и столбцов в пазле (оба не более 50). Каждая из следующих \(N\) строк содержит по \(M\) символов, описывающих одну строку зашифрованного пазла. Каждый символ - большая латинская буква в диапазоне A..Z.

ФОРМАТ ВЫВОДА (файл moocrypt.out):

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

Задача на реализацию
—Войти и решать
Bessie Gets Even#89952
Фермер Джон и корова Беси в свободное время любят обмениваться математическими пазлами. Последний пазл, который ФД дал Беси, был довольно сложный и Беси не смогла решить его. Теперь она хочет дать ФД очень сложный пазл.

Беси даёт ФД выражение \((B+E+S+S+I+E)(G+O+E+S)(M+O+O)\), содержащее семь переменных \(B,E,S,I,G,O,M\) ( "\(O\)" это переменная, а не 0). Для каждой переменной она даёт ФД список до 20 целых чисел, которые эта переменная может принять. Беси просит ФД посчитать количество различных способов назначить значения переменным, чтобы вычисленное выражение было чётным числом.

ФОРМАТ ВВОДА (файл geteven.in):

Первая строка ввода содержит целое число \(N\). Каждая из \(N\) следующих строк содержит переменную и возможное значение для этой переменной. Каждая переменная появится в этом списке не менее одного раза и не более 20 раз. Для одной и той же переменной все задаваемые значения различны. Все значения находятся в диапазоне \(-300\) to \(300\).

ФОРМАТ ВЫВОДА (файл geteven.out):

Выведите единственное целое число, задающее количество способов, которыми ФД может назначить значения переменным, чтобы выражение давало чётный результат.

Вывод формулы
—Войти и решать
Code Breaking#89946

Фермер Джон спрятал ключи от трактора в сейфе. Коровы пытаются взломать этот сейф. Сейф защищён сложной парольной системой. Она организована как корневое дерево из N (1 <= N <= 20,000) вершин, каждая из которых требует цифру от 0 до 9. Вершины пронумерованы от 0 до N-1.
Единственная информация, которой владеют коровы – что определённая последовательность длины 5 не случается на путях в этом дереве.
Например, предположим, то дерево выглядит так (с корнем в A):
A <- B <- C <- D <- E ^ | F
Коровы могут знать, что последовательность 01234 не случится начиная от F, И что последовательность 91234 не случится, начиная от E. Эта информация приводит к тому, что возможными остаются 19 паролей, все такого вида:
The cows might know that the sequence 01234 does not occur starting at F, and that the sequence 91234 does not occur starting at E. This information rules out 19 possible passcodes: all those of the form
4 <- 3 <- 2 <- 1 <- * ^ | 0
или
4 <- 3 <- 2 <- 1 <- 9 ^ | *
Что даёт 19 паролей, поскольку такой
4 <- 3 <- 2 <- 1 <- 9 ^ | 0
появится дважды
По заданным M (1 <= M <= 50,000) последовательностям длины 5, вместе с их стартовой позицией в дереве помогите коровам вычислить сколько паролей будет подходить. Вы должны выводить свой ответ по модулю 1234567.

PROBLEM NAME: code
Формат ввода:
* Строка 1: Два разделённых пробелом целых числа, N и M.
* Строки 2..N: Строка i+1 содержит одно целое число p(i), означающее родителя вершин I в дереве (0 <= p(i) < i).
* Строки N+1..N+M: Строка N+i описывает i-ую последовательность про которую известно, что она не произойдёт в коде. Строка содержит v(i) и s(i), разделённые пробелом. Здесь v(i) - стартовая вершина последовательности, s(i) – строка из 5 цифр, которая не встретится в шифре начиная с вершины v(i) если двигаться вверх по дереву. Гарантируется, что корень дерева находится не менее чем в 4 шагах от v(i).

Вывод формулыграфыДеревья
—Войти и решать
Empty Stalls#89900

Новый амбар Фермера Джона представляет собой большой круг из N стойл (2 <= N <=3,000,000), пронумерованных от 0 до N-1, стойло N-1 соседствует со стойлом 0.
В конце каждого дня коровы ФД возвращаются в амбар, одна за одной, У каждой имеется предпочтительный номер стойла, который она хочет занять. Однако если это место уже занято другой коровой, она идёт вперёд последовательно от этого стойла, пока не найдёт первое не занятое стойло, которое она и займёт. Если она пройдёт стойло N-1, она продолжит поиск со стойла 0.
По заданному предпочтительному номеру для каждой коровы определите минимальный номер стойла, который останется незанятым после того как все коровы вернутся в амбар. Заметим, что ответ на этот вопрос не зависит от того, в каком порядке возвращаются коровы
Для того, чтобы избежать проблем с огромным вводом, данные вводятся в специальном формате, использующем K строк (1 <= K <=10,000) вида
X Y A B
Здесь описываются предпочтительные стойла X Y коров: X коров предпочитают каждое из стойл f(1) .. f(Y), где f(i)= (Ai + B) mod N. Значения A и B лежат в диапазоне 0...1,000,000,000.
Не забудьте про стандартное для всех задач ограничение на память – 64 Мбт.
PROBLEM NAME: empty
Формат входных данных
* Строка 1: Два разделённых пробелом целых числа: N и K.
* Строки 2..1+K: каждая строка содержит целые числа X Y A B, смысл которых описан выше. Общее количество коров описываемых этими числами не превысит N-1. Коровы могут добавляться в одно и тоже стойло разными из этих строк.
Формат выходных данных
* Строка 1: Минимальный индекс не занятого стойла.
Примечание
Все стойла будут заняты кроме стойла с номером 5.
Алгоритмы обработки
—Войти и решать
The Bessie Shuffle (gold)#89865

Беси практикуется в карточных фокусах. Она уже освоила Беси-тасование – тасование M (2 <= M <= 100,000) карт, так чтобы i-ая карта сверху становилась P[i]-ой картой сверху.
Теперь она переходит на бОльшие колоды. У неё есть колода из N (M <= N <= 1,000,000,000) карт, последовательно пронумерованных от 1 до N. Она тасует её следующим образом: берёт первые M карт, и выполняет их Беси-тасование, затем снова кладёт их наверх колоды. Далее она удаляет верхнюю карту из колоды и кладёт ее на стол значением вниз. Она повторяет этот процесс, выкладывая забираемые карты поверх друг друга, пока карты не кончатся. Когда у неё в исходной колоде остаётся меньше чем M карт, она прекращает выполнять Беси-тасование, но продолжает брать верхнюю карту и выкладывать её поверх ранее взятых.
Беси знает, что изначально колода находится в отсортированном порядке, Причём карта 1 наверху, карта 2 следующая и т.д. По заданному описанию Беси-тасования, вычислите какие карты окажутся на Q (1 <= Q <= N, Q <= 5,000) различных указанных позициях колоды.
В 50% тестов N<=100,000.
PROBLEM NAME: shufflegold
Формат входных данных
* Строка 1: Числа N, M и Q разделенные одиночными пробелами
* Строки 2..1+M: Строк i+1 указывает позицию сверху колоды, P[i], на которую переместиться i-ая карта после Беси-тасования (1 <= P[i] <= M).
* Строки 2+M..1+M+Q: Строка i+1+M содержит одно целое число qi описывающее i-ый запрос. Вы должны вычислить значение на карте, которая окажется в позиции qi сверху (1 <= qi <= N).
Формат выходных данных
* Строки 1..Q: На i-ой строке, выведите одно целое число, указывающее карту, которая окажется на позиции qi сверху.
Примечание
Тасование происходило так
[1, 2, 3, 4, 5] -> [2, 3, 1, 4, 5] (выкладываем 2 значением вниз) [3, 1, 4, 5] -> [1, 4, 3, 5] (выкладываем 1 значением вниз) [4, 3, 5] -> [3, 5, 4] (выкладываем 3 значением вниз) [5, 4] (выкладываем 5 значением вниз) [4] (выкладываем 4 значением вниз)
Финальный расклад [4, 5, 3, 1, 2]
Задача на реализацию
—Войти и решать
Record Keeping#89862

Фермер Джон детально записывает порядок прихода коров на дойку. Каждый час группа из трёх коров входит в амбар и ФД записывает их имена. Например, за 5 часов он имеет такой список, где каждая строка соответствует группе вошедших коров:
BESSIE ELSIE MATILDA FRAN BESSIE INGRID BESSIE ELSIE MATILDA MATILDA INGRID FRAN ELSIE BESSIE MATILDA
ФД заметил, что одна и та же группа коров может несколько раз появляться в этом списке. Например, группа BESSIE, ELSIE и MATILDA появляется три раза (ФД необязательно записывает их имена в одинаковом порядке при каждом входе в амбар).
Помогите ФД посчитать количество приходов той группы, которая пришла наибольшее количество раз.
PROBLEM NAME: records
Формат входных данных
* Строка 1: Количество часов, N, в течение которых ФД вёл запись (1 <= N <= 1000).
* Строки 2..1+N: Каждая строка содержит список из трёх разделенных одиночными пробелами имён. Каждое имя имеет длину от 1 до 10 символов и стоит только из символов A-Z.


Формат выходных данных
* Строка 1: Количество приходов той группы, которая пришла наибольшее количество раз.
Примечание
Группа {BESSIE, ELSIE, MATILDA} вошла в амбар 3 раза.

Словари
—Войти и решать
Cows in a Row#89851

У Фермера Джона N коров (1 <= N <= 1000) выстроены в ряд. У каждой коровы имеется ID породы. У коровы с номером i, ID породы B(i).
ФД думает, что его ряд коров выглядел бы более впечатляюще, если бы он имел как можно более длинный непрерывный блок коров с одинаковым ID коровы. Для того, чтобы создать такой блок, ФД решил удалить из своего ряда всех коров, имеющих конкретный ID породы, который он выберет.
Помогите ФД определить длину наибольшего непрерывного блока коров с одинаковым ID, который он может получить, удалив всех коров с некоторым ID, который выберет ФД.

PROBLEM NAME: cowrow
Формат входных данных
* Строка 1: Целое число N.
* Строки 2..1+N: Строка i+1 содержит B(i), целое число в диапазоне 0...1,000,000.
Формат выходных данных
* Строка 1: Наибольший размер непрерывного блока коров, с одинаковым ID коровы, который он может создать.


Примечание
При удалении всех коров с ID=3, ФД может получить ряд 2, 7, 7, 7, 7, 5, 7. В этому ряду максимальный непрерывный блок состоит из 4 коров с ID 7.

Алгоритмы обработки
✓ 1✗ 1—Войти и решать
Clumsy Cows#89849

Определите минимальное количество символов в строке из круглых скобок, которые нужно заменить на противоположный ( левую скобку на правую, или наоборот) , чтобы получить сбалансированную строку.
Существует несколько способов определить сбалансированную строку скобок. Например, такой: В строке должно быть одинаковое количество левых и правых скобок, и для любого ее префикса количество левых скобок должно быть не меньше, чем количество правых скобок.
Например, эти строки - сбалансированные () (()) ()(()())
А эти - нет: )( ())( ((())))
PROBLEM NAME: clumsy
Формат входных данных
* Строка 1: строка из скобок длиной не более 100,000 символов.


Формат выходных данных
* Строка 1: Одно целое число - минимальное количество скобок, которые нужно "переключить" , чтобы конвертировать заданную строку в сбалансированную.


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

Линейные алгоритмы
—Войти и решать
Find the Cow!#89842

нн
Беси сбежала и прячется на холме, покрытом высокой травой. Фермер Джон, пытаясь поймать Беси решил ползти по траве на руках и коленях, так чтобы подобраться незамеченным.
Трава перед Фермером Джоном выглядит как строка из N круглых скобок (1 <= N <= 50,000), например
)((()())())
Фермер джон знает, что задние ноги Беси выглядят как две соседних левых скобок ((, а пара ее передних ног выглядит, как пара соседних праваых скобок )). Поэтому местоположение Бес,и может быть описано парой индексов x < y таких, что (( находятся на позиции x, а )) находятся на позиции y.
Вычислите количество различных позиций, в которых может находится Беси.
PROBLEM NAME: cowfind
Формат входных данных
* Строка 1: строка из скобок, длиной N (1 <= N <= 50,000).
Формат выходных данных
* Строка 1: Количество позиций, в которых Беси может стоять (то есть количество таких различных пар (x,y), что x < y и (( стоят на позиции x, а )) стоят на позиции y )


Примечание
Всего имеется четыре варианта расположения Беси, они указаны ниже:
1. )((()())()) ^^ ^^
2. )((()())()) ^^ ^^
3. )((()())()) ^^ ^^
4. )((()())()) ^^ ^^

Строки
—Войти и решать
Haybale Stacking#89826

Беси согласилась помочь ФД уложить пакеты с сеном. Она начинает с N (1 <= N <= 1,000,000, N нечетное) пустых стеков, пронумерованных от 1 до N. Затем ФД дает ей последовательность из K инструкций (1 <= K <= 25,000), каждая вида A B, означающая, что Беси должна добавить по одному пакету с сеном в каждый из стеков в диапазоне от A до B. Например, инструкция 10 13 означает, что Беси должна положить по пакету сеном в стеки 10, 11, 12, 13.
После того как вся работа закончена, ФД хочет узнать медианную высоту всех N своих стеков - то есть высоту среднего стека, если все стеки упорядочить по высоте. По условию N нечетно, поэтому этот стек уникален. Пожалуйста, помогите Беси ответить на этот вопрос.
PROBLEM NAME: stacking
Формат входных данных
* Строка 1: Два разделенных пробелом целых числа, N K.
* Строки 2..1+K: Каждая строка содержит одну инструкцию ФД в виде двух целых (разделенных пробелом) чисел A B (1 <= A <= B <= N).

Формат выходных данных
* Строка 1: Медианная высота после того как Беси выполнит все инструкции


Примечание
После того, как Беси закончит, стеки будут иметь высоты 0,1,2,3,3,1,0. Если их упорядочить, получим: 0,0,1,1,2,3,3. Средний элемент равен 1.

Алгоритмы обработкиИспользование сортировкиПрефиксные суммы(минимумы, ...)
—Войти и решать
Contest Timing#89797
Problem 1: Contest Timing [Brian Dean]
Бесси надоело давать молоко, и она хочет сделать карьеру в компьютерной Индустрии. Чтобы улучшить свои навыки в кодировании, она решила поучаствовать в USACO-олимпиаде. Поскольку олимпиада начинается 11 ноября 2011 года (11/11/11), она решил загрузить условия и начать кодировать ровно в 11:11 утра 11/11/11.
К несчастью, Бесси не очень хорошо умеет планировать время, поэтому она хочет написать программу, которая поможет ей не превысить три часа (180 минут) во время выполнения заданий. По заданным дате и времени завершения работы, помогите Бесси вычислить общее количество минут, которое она потратит на контест.
PROBLEM NAME: ctiming
Формат входных данных
* Строка 1: Эта строка содержит три целых, разделенных одиночными пробелами, числа D H M, указывающих дату и время, когда Бесси закончит контест. D – целое число в диапазоне 11..14, указывает день месяца H и M часы и минуты на 24-часовыъх часах От 0 0 в полночь до H=23, M=59 в конце суток (момент времени 11:59 PM)
Формат выходных данных
* Строка 1: Общее количество минут, которое проведет Бесси на контесте, или –1, если время завершения раньше чем время начала.
Примечание
Бесси закончит контест через 1563 минуты после того как начнет.
Дата и время
✓ 1✗ 0—Войти и решать
Hay Bales#89789

Коровы вернулись! Фермер Джон аккуратно выстроил N (1 <= N <= 10,000) столбиков одинаковой высоты из пакетов сена. Однако пока он отошел ненадолго, коровы поперетаскивали некоторые пакеты между столбиками, так что теперь они необязательно имеют одинаковую высоту. По заданным новым высотам столбиков определите минимальное количество пакетов сена, которые нужно перенести, чтобы вернуть столбики к их исходным, одинаковым высотам.
PROBLEM NAME: haybales
Формат входных данных
* Строка 1: Количество столбиков, N (1 <= N <= 10,000). * Строки 2..1+N: Каждая строка содержит количество пакетов сена в одном столбике (целое число, от 1 до 10 000)
Формат выходных данных
* Строка 1: Одно целое число - минимальное количество пакетов сена, которое необходимо перенести, чтобы столбики стали одинаковой высоты.
Примечание
Переместив 7 пакетов сена, мы можем выровнять к 5 все высоты. 3 из столбика 2 в столбик 1, 2 из столбика 2 в столбик 4, 2 из столбика 3 в столбик 4.

Алгоритмы обработки
✓ 1✗ 3—Войти и решать
Род слов#89063

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

Будем рассматривать слова из строчных букв английского алфавита. Гласными считаются буквы <<a>>, <<e>>, <<i>>, <<o>>, <<u>>. Будем считать, что слово имеет женский род, если оно заканчивается на <<a>> (класс 1), либо на букву <<d>> (класс 2а), либо <<z>> (класс 2б), в этих двух случаях предпоследняя буква должна быть гласной, либо на буквосочетание <<ion>> (класс 3). В противном случае слово имеет мужской род.

Формат входных данных
На вход подана одна строка, содержащая слово, содержащее от 2 до 40 букв.

Формат выходных данных
Выведите <<f>>, если слово имеет женский род, либо <<m>>, если оно имеет мужской род.

 
Строки
✓ 3✗ 2—Войти и решать
Задача 2. Полная реализация DBSCAN#88721

Реализуйте полный алгоритм DBSCAN. Напишите программу

 

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

n eps minPts : n - число точек (натуральное число не больше 100, eps - положительное вещественное число не больше 3, minPts - натуральное число не больше 5)

n строк: x y (координаты точек, вещественные числа, по модулю меньше 10**5 )


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

n строк: номер кластера для каждой точки:

  • -1 для шума
  • нумерация кластеров с 0
Задача на реализацию
✓ 3✗ 12—Войти и решать
Уникальные числа#84689

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

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

В первой строке — число N (1 ≤ N ≤ 100000).

Во второй строке — N целых чисел первого массива (1 ≤ число ≤ 1000000).

В третьей строке — число M (1 ≤ M ≤ 100000).

В четвёртой строке — M целых чисел второго массива.

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

Одно число — количество общих уникальных элементов.

Словари
—Войти и решать
Уникальные товары#84688

Два интернет-магазина продают товары. Маркетолог хочет найти:

1. Товары, которые продаются только в первом магазине

2. Товары, которые продаются только во втором магазине

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

В первой строке — число N (1 ≤ N ≤ 100000) — количество товаров первого магазина.

Во второй строке — N целых чисел — коды товаров первого магазина (1 ≤ код ≤ 1000000).

В третьей строке — число M (1 ≤ M ≤ 100000) — количество товаров второго магазина.

В четвёртой строке — M целых чисел — коды товаров второго магазина.

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

Первая строка: товары только первого магазина (в порядке возрастания через пробел) или "NONE".

Вторая строка: товары только второго магазина (в порядке возрастания через пробел) или "NONE".

Множества
✓ 3✗ 1—Войти и решать
Поделиться
Класснуть