--->
71 задач
<---
Источники
#3865
Темы:
[Жадный алгоритм]
Источники:
[
Личные олимпиады,
Всероссийская олимпиада школьников,
Региональный этап,
2012,
1 день,
Задача B
]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
Возрождая древние традиции английских рыцарей, в одном городе члены школьного клуба любителей информатики каждую неделю собираются за круглым столом и обсуждают результаты последних соревнований.
Руководитель клуба Иван Петрович недавно заметил, что не все ребята активно участвуют в обсуждении. Понаблюдав за несколькими заседаниями клуба, он заметил, что активность члена клуба зависит от того, кто с кем сидит рядом.
В клуб приходят на занятия m мальчиков и n девочек. Иван Петрович заметил, что мальчик активно участвует в обсуждении только тогда, когда непосредственно рядом с ним с обеих сторон от него сидят девочки, а девочка активно участвует в обсуждении только тогда, когда непосредственно рядом с ней с одной стороны от нее сидит мальчик, а с другой — девочка.
Желая сделать заседание клуба как можно более интересным, Иван Петрович решил разместить участников за круглым столом таким образом, чтобы как можно больше членов клуба приняло активное участие в обсуждении.
Требуется написать программу, которая по заданным числам m и n выведет такой способ размещения m мальчиков и n девочек за круглым столом, при котором максимальное количество членов клуба будет активно участвовать в обсуждении.
Входные данные
Входной файл содержит два целых числа m и n, разделенных ровно одним пробелом (0 ≤ m ≤ 1000, 0 ≤ n ≤ 1000, m + n ≥ 3).
Выходные данные
Выходной файл должен содержать строку с расположенными в некотором порядке m символами «B» (заглавная латинская буква) и n символами «G» (заглавная латинская буква). Символ «B» означает мальчика, а символ «G» — девочку.
Символы следует расположить в том порядке, в котором нужно разместить членов клуба вокруг стола. Соседние символы соответствуют членам клуба, которые сидят рядом. Рядом сидят также члены клуба, соответствующие первому и последнему символу выведенной строки.
Примечание к примерам тестов
В первом примере все члены клуба примут активное участие в обсуждении.
Во втором примере мальчики примут активное участие в обсуждении, а девочки нет. В этом примере можно также разместить членов клуба следующим образом: «BBGG». В этом случае активное участие в обсуждении примут обе девочки, а мальчики — нет. Разместить всех так, чтобы три или четыре члена клуба приняли активное участие в обсуждении, нельзя.
Примеры
Входные данные
1 2
Выходные данные
BGG
Входные данные
2 2
Выходные данные
BGBG
#3882
Темы:
[Жадный алгоритм]
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
256 megabytes
Вы по-прежнему работаете под руководством д.б.н., проф. О.Б. Ломова и изучаете интеллект обезьян. Ваши подопечные уже очень далеко ушли от столь элементарной задачи, как сбор квадрата. Теперь вы работаете над тем, чтобы обучить их намного более сложной задаче. Вы по-прежнему даёте обезьянам набор из \(N\) палочек, но на этот раз вы хотите, чтобы они собрали из этих палочек треугольник.
Конечно, решить эту задачу в элементарном варианте — выбрать три палочки и собрать из них треугольник — ваши подопечные могут без каких-либо проблем; вы же хотите их обучить, чтобы они собирали один большой треугольник из всех выданных им палочек сразу. Таким образом, они должны разбить палочки на три группы так, чтобы, сложив палочки каждой группы в один большой отрезок, получить три отрезка, из которых можно собрать треугольник. Полученный треугольник должен быть невырожденным, т.е. его площадь должна быть строго больше нуля.
Как и в прошлый раз, вам понадобилась программа, которая определит, разрешима ли задача для данного набора палочек.
Входные данные
На первой строке входного файла находится одно натуральное число \(N\) — количество палочек в наборе (\(1\leq N \leq 16\,000\)). На второй строке находятся \(N\) натуральных чисел — длины палочек. Гарантируется, что суммарная длина палочек не превосходит \(100\,000\,000\).
Выходные данные
Если решения не существует, то в первую строку выходного файла выведите одно слово “no”
(без кавычек). В противном случае в первую строку выведите одно слово “yes”, а в
следующие три строки выведите какой-нибудь способ собрать треугольник из данных палочек. Каждая
из этих трёх строк должна описывать очередную сторону получающегося треугольника: в каждой строке
сначала должно идти количество палочек, из которых состоит эта сторона, а потом длины этих палочек.
Каждую палочку, конечно, можно использовать только один раз.
Если есть несколько способов собрать треугольник из данных палочек, выведите любой.
Примеры
Входные данные
5 1 2 3 4 5
Выходные данные
yes 2 4 3 1 5 2 1 2
Входные данные
5 1 2 3 4 100
Выходные данные
no
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes
Вы отвечаете за электрическую сеть для некоторого соревнования по программированию и вам надо подключить много компьютеров к источнику питания. К сожалению, есть два стандарта для вилок и розеток: A и B. Эти стандарты несовместимы между собой, так что вилка стандарта A может быть включена только в розетку стандарта А, и вилка стандарта B может быть включена только в розетку стандарта B.
В зале соревнований есть только одна розетка стандарта A. Каждый компьютер, который будет использован в соревновании, имеет вилку стандарта A. Таким образом, только один компьютер может быть подключен напрямую к главной розетке. Но вы можете использовать разветвители питания двух типов.
- Разветвитель первого типа имеет одну вилку стандарта A и несколько розеток стандарта B.
- Разветвитель второго типа имеет одну вилку стандарта B и несколько розеток стандарта A.
Все разветвители питания очень мощные и могут выдержать любую нагрузку. Так что вы можете создать электрическую сеть, подключив один разветвитель первого типа к главной розетке, затем несколько разветвителей второго типа к этому разветвителю, и так далее. В конце вы получите несколько розеток, к которым вы можете присоединить компьютеры.
Вы должны найти максимальное число компьютеров, которые могут быть подключены к сети, используя доступные разветвители.
Возможное решение для первого примера: 
Возможное решение для второго примера: 
Входные данные
Первая строка входного файла содержит два целых числа n и m — количество разветвителей первого и второго типа (0 ≤ n, m ≤ 100 000).
Вторая строка содержит n целых чисел ai — количество розеток на i-том разветвителе первого типа (1 ≤ ai ≤ 1000).
Третья строка содержит m целых чисел bi — количество розеток на i-том разветвителе второго типа (1 ≤ bi ≤ 1000).
Выходные данные
Выведите максимальное количество компьютеров, которое может быть подключено к сети.
Примеры тестов
Входные данные
3 2
3 2 1
2 3
Выходные данные
5
Входные данные
2 3
2 2
2 3 1
Выходные данные
5
Решения, работающие в случае, если N и M не превосходят 100, будут набирать не менее 30 баллов.
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes
Шаблоном называется любая непустая строка, состоящая из маленьких латинских букв и символов "*".
Будем говорить, что строка T подходит под шаблон P, если в P можно символы "*" так заменить на последовательности букв латинского алфавита (возможно, пустые), что в итоге получится строка T. К примеру, строка aadbc походит под шаблон a*b*c, т.к. можно первую звездочку заменить на последовательность букв ad, а вторую — на пустую последовательность, в результате чего получится искомая строка.
Циклическом сдвигом строки называется строка, полученная перемещением нескольких букв из строки в ее начало. Для заданного шаблона P и строки T найдите, сколько циклических сдвигов строки T подходят под шаблон P.
Входные данные
Первая строка входных данных содержит шаблон P, длиной не более 100 символов. Вторая строка содержит исходную строку T, длиной не более 100 000 символов. Все строки имеют длину не менее одного символа.
Выходные данные
Выведите единственное число — искомое число циклических сдвигов, подходящих под шаблон.
Примеры тестов
Входные данные
aaaa
aaaa
Выходные данные
4
Входные данные
a*a
aaaaaa
Выходные данные
6
Входные данные
*a*b*c*
abacabadabacaba
Выходные данные
15
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes
Вася не выполнил ни одной лабораторной работы в этом семестре, поэтому его отчисляют. Наконец, под угрозой отчисления, Вася решил начать учиться.
Вася должен выучить N различных дисциплин, для этого по каждой из них ему необходимо выполнить Ki лабораторных работ. Вася решил, что он сначала выполнит все лабораторные работы по одному из предметов, затем по другому и т.д.
Вася, мягко говоря, запоздал с выполнением работ, поэтому каждый преподаватель будет требовать с Васи взятку в размере w·t иностранных тугриков, где w — коэффициент сложности работы, а t — время сдачи работы. Если Вася начал выполнять лабораторную работу, то он не остановится ни перед чем, пока не закончит ее выполнение.
Вася знает сложность каждой лабораторной работы wj и время tj, которое ему потребуется на ее выполнение. Помогите ему выбрать такой порядок выполнения работ, чтобы суммарный размер взяток был минимален.
Все работы пронумерованы числами от 1 до T, где T = K1 + ... + KN, первые K1 работ относятся к первому предмету, следующие K2 ко второму предмету и т.д.
Входные данные
В первой строке входных данных содержится одно число N — количество предметов (1 ≤ N ≤ 500). Далее содержатся числа Ki — число лабораторных работ по соответствующему предмету (1 ≤ Ki ≤ 100).
В следующей строке содержится T целых чисел pj — времена выполнения соответствующих работ (1 ≤ pj ≤ 10 000).
В последней строке содержится T целых чисел wj, обозначающих коэффициенты сложности соответствующих работ (1 ≤ wj ≤ 10 000).
Выходные данные
(student.in, student.out) В первой строке выведите одно число — искомую минимальную величину взяток. В следующей строке выведите перестановку чисел от 1 до T, обозначающих порядок выполнения работ в оптимальном расписании. Помните, что Вася сначала должен изучить какой-то один предмет целиком, а только потом приступить к следующему и также изучать его целиком. В случае, если существует несколько решений, выведите любое из них.
Примеры тестов
Входные данные
1
5
1 2 3 4 5
5 4 3 2 1
Выходные данные
70
1 2 3 4 5
Входные данные
2
2 2
1 1 2 2
1 1 2 2
Выходные данные
23
1 2 3 4
Выбрано
:
|