Темы
    Информатика(2656 задач)
---> 168 задач <---
Источники --> Личные олимпиады --> Московская олимпиада школьников
    6-9 классы(30 задач)
    7-9 классы(25 задач)
    10-11 классы(114 задач)
Страница: << 12 13 14 15 16 17 18 >> Отображать по:
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Группа школьников решила сходить в поход вдоль Москвы-реки. У Москвы-реки существует множество притоков, которые могут впадать в нее как с правого, так и с левого берега.

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

Школьники заранее изучили карту и записали, в какой последовательности в Москву-реку впадают притоки на всем их маршруте.

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

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

Единственная строка содержит описание Москвы-реки между начальной и конечной точкой похода. Длина строки не превосходит \(10^5\) символов.

Каждый символ строки может быть одной из трех латинских букв L, R или B. Буква L означает, что очередной приток впадает в реку с левого берега, R - приток впадает в реку с правого берега и B - притоки впадают с обоих берегов реки в одном месте. Поход начинается на левом берегу перед описанной частью реки и заканчивается на правом берегу после описанной части.

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

Выведите одно целое число - минимальное количество переправ.

Примечания

Рисунок к приведенному выше примеру.

Примеры
Входные данные
LLBLRRBRL
Выходные данные
5
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

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

Эми, недовольная возможностями профессорского тела в плане обжорства, уговаривает поменяться Лилу. Фрай приходит в ужас. Лила обижена и обвиняет Фрая в том, что его заботит только ее внешность. Фрай в отместку меняется телами с Зойдбергом.

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

Фрай в теле Зойдберга и Лила в теле Профессора встречаются в ресторане, чтобы выяснить отношения. В конце концов они понимают, что любят друг друга вовсе не за внешность. При виде сцены их бурного примирения Эми, на этот раз уже в теле Гермеса, надолго теряет аппетит.

Бендер, поменявшись телами с правителем Робо-Венгрии, наслаждается жизнью на его яхте. Однако именно в этот вечер заговорщики совершают покушение на императора. Жизнь Бендеру спасает появление профессора Фарнсворта.

После того, как все герои решают свои личные проблемы, профессору с помощью Бубльгума Тэйта и Сладкого Клайда из команды "Ударники" удается вернуть всех в свои тела.

"Футурама". Десятый эпизод шестого сезона.

В очередной серии Футурамы было проведено несколько обменов разумами между телами героев,но, по крайней мере Бубльгум Тэйт и Сладкий Клайд в обменах не участвовали. Теперь необходимо вернутьразумы всех героев в свои тела. К сожалению, два тела могут участвовать только в одном обмене,поэтому обратные обмены для этого произвести невозможно. Например, если тело 1поменялось разумом с телом 2, а потом тело 1 поменялось разумом с телом 3,то в теле 1 находится разум третьего героя, в теле 2 - разум первого героя,а в теле 3 - второго.Теперь можно произвести обмен разумами только между телами 2 и 3, тогда разум второго героявернется в свое тело, а первому и третьему героям могут помочь только Тэйт с Клайдом.

Помогите героям Футурамы вернуться в свои тела.

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

Во входном файле записаны целые числа \(N\) (\(4\leq N\leq 20\)) и \(M\)(\(1\leq M\leq 100\)) - количество героев Футурамы и количество произведенных обменов разумами.Герои занумерованы числами от \(1\) до \(N\), изначально разум каждого из героев находится в своем теле. В последующих \(M\) строчках записана последовательность совершенных обменов разумами. Каждый обмен описывается двумя различными числами - номерами тел, которые, в этом обмене меняются разумами. Бубльгум Тэйт и Сладкий Клайд, как наиболее разумные герои, имеют номера \(N-1\) и \(N\), и гарантируется, что в исходных обменах они не участвовали.

Решения, верно работающие в случаях, когда каждое тело участвовало в обмене не больше одного раза будут набирать не менее 40 баллов.

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

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

Вернуть разумы героев в свои тела всегда возможно.

Примечание

Приведем таблицу положения героев в телах после каждого из обменов:

ОбменТело 1Тело 2Тело 3Тело 4
До обменов1234
1-22134
1-33124
2-43421
1-41423
2-31243
3-41234
Примеры
Входные данные
4 1
1 2
Выходные данные
1 3 
2 4
1 4
2 3
3 4
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Завод по производству Крым-колы изготавливает ее не только для магазинов, но и для всемирно известной сети ресторанов быстрого питания.

Ежедневно завод отгружает один и тот же объем колы в литрах. Служба доставки сети ресторанов обычно использует для транспортировки колы емкости объемом или только 50 литров, или только 70 литров. Если доставка осуществляется с помощью емкостей в 50 литров, то для перевозки имеющегося объема колы необходимо A емкостей. А если с помощью емкостей в 70 литров, то необходимо B емкостей. При этом в каждом из случаев одна из емкостей может быть заполнена не полностью.

Недавно сеть ресторанов решила утвердить новый объем емкостей для доставки колы — 60 литров. Сколько емкостей теперь может понадобиться для доставки того же самого объема колы?

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

Входные данные содержат 2 числа A и B, расположенных каждое в отдельной строке (1 ≤ A, B ≤ 10 000 000).

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

Выведите все возможные значения для количества емкостей по 60 литров, которые окажутся заполненными (в том числе одна возможно частично), в порядке возрастания или число  - 1, если значения A и B противоречат друг другу, то есть они были записаны неверно.

Примеры тестов

Входные данные
3
2
Выходные данные
2 3
Входные данные
1
2
Выходные данные
-1

Примечание

В первом примере колы могло быть, например, 115 литров, в этом случае понадобится две емкости в 60 литров, а могло быть — 135 литров, в этом случае понадобятся уже три емкости по 60 литров. Четыре емкости не могут понадобиться никогда.

Online-группа тестов оценивается в 60 баллов, в этой группе 1 ≤ A, B ≤ 1 000.

Offline-группа тестов оценивается в 40 баллов.

ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Саша и Катя учатся в начальной школе. Для изучения арифметики при этом используются карточки, на которых написаны цифры (на каждой карточке написана ровно одна цифра). Однажды они пришли на урок математики, и Саша, используя все свои карточки, показал число A, а Катя показала число B. Учитель тогда захотел дать им такую задачу, чтобы ответ на нее смогли показать и Саша, и Катя, каждый используя только свои карточки. При этом учитель хочет, чтобы искомое число было максимально возможным.

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

Во входном файле записано два целых неотрицательных числа A и B (каждое число в одной строке). Длина каждого из чисел не превосходит 100 000 цифр.

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

Выведите одно число — максимальное целое число, которое можно составить используя как цифры первого числа, так и цифры второго числа. Если же ни одного такого числа составить нельзя, выведите -1.

Примеры тестов

Входные данные
280138
798081
Выходные данные
8810
Входные данные
123
456
Выходные данные
-1

Примечание

Online-группа тестов оценивается в 60 баллов, в этой группе числа A и B содержат не более 1000 цифр каждое. При этом решения, правильно работающие для случая, когда A и B содержат не более 6 цифр, будут оценены не менее, чем в 20 баллов. Решения, правильно работающие для случая, когда A и B содержат не более 9 цифр, будут оценены не менее, чем в 40 баллов.

Offline-группа тестов оценивается в 40 баллов.

ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Как известно, командные спортивные соревнования часто проводятся по круговой системе, когда любые две команды должны сыграть между собой ровно один матч. Круговой турнир проводится в несколько туров, в одном туре каждая команда может сыграть не более одного матча. Например, если в турнире участвуют 4 команды, то турнир можно провести в три тура: в первом туре команда 1 играет с командой 2, а команда 3 играет с командой 4, во втором туре 1 играет с 3, а 2 играет с 4, в третьем туре — 1 играет с 4, а 2 играет c 3.

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

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

Во входном файле записано одно натуральное число N — количество команд, участвующих в турнире (2 ≤ N ≤ 100).

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

В первой строке выведите минимальное количество туров K, необходимых для проведения кругового турнира из N команд. Каждая из K следующих строк содержит описание одного тура. В начале строки выведите количество игр ni, которое необходимо сыграть в i-м туре. Далее идет ni пар чисел — команды, которые играют в этом туре. Команды, играющие между собой, разделяются символом «-» (минус), а разные игры разделяются пробелом.

Примеры тестов

Входные данные
4
Выходные данные
3
2 1-2 3-4
2 1-3 2-4
2 1-4 2-3
Входные данные
3
Выходные данные
3
1 1-2
1 2-3
1 3-1

Примечание

Online-группа тестов содержит тесты для N ≤ 10 и оценивается в 40 баллов.

Offline-группа тестов оценивается в 60 баллов.


Страница: << 12 13 14 15 16 17 18 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест