Страница: << 112 113 114 115 116 117 118 >> Отображать по:
#111502
Автостанции
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
256 megabytes

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

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

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

В каждом населённом пункте можно разместить ремонтную подстанцию. В принципе, фирма может размещать как крупные подстанции, которые даже в одиночку смогут обслуживать всю область, но при этом будут требовать больших расходов на содержание, так и небольшие станции, которые будут обслуживать лишь прилегающие населённые пункты, но при этом будут обходиться намного дешевле. Фирма уже определила, что каждую подстанцию можно характеризовать параметром “мощность”, которая может принимать значения, являющиеся целыми положительными числами (равна нулю мощность быть не может). Подстанция с мощностью \(k\) будет обслуживать населённый пункт u, в котором она расположена, и все другие населённые пункты, до которых можно добраться из u, использовав не более k дорог (т.е. при \(k\)=1, например, подстанция обслуживает свой населённый пункт и все, которые напрямую соединены с ним дорогой). Стоимость содержания такой подстанции пропорциональна её мощности.

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

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

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

В первой строке входного файла находится одно число \(N\) — количество населённых пунктов в области (1<=\(N\)<=300). Далее следуют \(N\)−1 строка, описывающая дороги. Каждая строка содержит два числа — номера населённых пунктов, которые соединяет эта дорога. Населённые пункты нумеруются от 1 до \(N\).

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

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

Примеры
Входные данные
5
1 2
1 3
1 4
1 5
Выходные данные
1
1 0 0 0 0
#111504
Олимпиада в Команде
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

В Команде проходит традиционная ежегодная олимпиада по теории магии среди младшекурсников. Завхозу смены Кате Медведевой поручили заняться распределением студентов по аудиториям.

Каждый факультет выставил своих лучших учеников на олимпиаду. От Звездочек участвует G студентов, от Солнышек S студентов, Травинок представляет H студентов и Подсолнухов — R студентов. В распоряжении Медведевой находится M аудиторий. На аудитории наложено особое заклятие расширения, поэтому при необходимости они могут вместить любое количество студентов. При рассадке необходимо учесть, что ученики одного факультета, находящиеся в одной аудитории, могут, воспользовавшись случаем, начать жульничать, обмениваясь идеями по решению задач. Поэтому в любой аудитории количество студентов с одного факультета, попавших в нее, следует свести к минимуму. Назовем рассадку, удовлетворяющую такому требованию, оптимальной.

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

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

В первой строке идут четыре целых числа G, S, H и R (1 ≤ G, S, H, R ≤ 1000) — количество учеников, представляющих каждый из факультетов школы.

Во второй строке идет целое число M (1 ≤ M ≤ 1000) — количество классов в распоряжении у завхоза.

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

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

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

Входные данные
4 3 4 4
2
Выходные данные
2
Входные данные
15 14 13 14
5
Выходные данные
3

#111505
Порядочные числа
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

У Миши развитое эстетическое чувство. Он считает, что не все числа одинаково порядочные. Когда ему грустно, он начинает придумывать числа и приводить их в порядок.

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

Миша настолько любит этот процесс, что он даже заменяет ему счёт овец, когда долго не получается заснуть. Он помнит, что вчера ночью, когда он в уме привёл в порядок число A, у него получилось число B. Но вот беда — он не помнит, какое именно он взял число A! Помогите ему в отыскании этого числа.

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

На ввод подаётся единственное целое число B (1 ≤ B ≤ \(10^9\) )

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

Если существует такое число A, что после приведения его в порядок, получается B, то выведите любое такое число. Если же Миша где-то ошибся в расчётах и такого числа не существует, то выведите -1.

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

Входные данные
42
Выходные данные
29
Входные данные
20
Выходные данные
-1

Примечание

Пояснение к первому примеру. Последовательность сумм цифр для 29 состоит из чисел 29, 11, 2. Соответственно, после приведения в порядок число 29 превращается в число 42 = 29 + 11 + 2.

#111506
Скучная лекция
  
Темы: [Строки]
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Лёша сидел на лекции. Ему было невероятно скучно. Голос лектора казался таким далеким и незаметным...

Чтобы окончательно не уснуть, он взял листок и написал на нём свое любимое слово. Чуть ниже он повторил своё любимое слово, без первой буквы. Ещё ниже он снова написал своё любимое слово, но в этот раз без двух первых и последней буквы.

Тут ему пришла в голову мысль — времени до конца лекции все равно ещё очень много, почему бы не продолжить выписывать всеми возможными способами это слово без какой-то части с начала и какой-то части с конца?

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

Макс хорошо знает любимое слово Лёши, а ещё у него не так много свободного времени, как у его друга, так что помогите ему быстро восстановить, сколько раз Лёше пришлось выписать каждую букву.

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

На вход подаётся строка, состоящая из строчных латинских букв — любимое слово Лёши.

Длина строки лежит в пределах от 5 до 100 000 символов.

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

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

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

Входные данные
hello
Выходные данные
e: 8
h: 5
l: 17
o: 5
Входные данные
abacaba
Выходные данные
a: 44
b: 24
c: 16

Примечание

Пояснение к первому примеру. Если любимое Лёшино слово — "hello", то на листочке у Лёши будут выписаны следующие слова:

  • "hello"
  • "hell"
  • "ello"
  • "hel"
  • "ell"
  • "llo"
  • "he"
  • "el"
  • "ll"
  • "lo"
  • "h"
  • "e"
  • "l"
  • "l"
  • "o"
Среди этих слов 8 раз встречается буква "e", 5 раз — буква "h", 17 раз — буква "l" и 5 раз буква "o".

#111507
Диадема Клеопатры
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Аня — страстный любитель ювелирных изделий. Ее коллекция насчитывает множество бриллиантов, изумрудов и алмазов.

...Срочная новость! Бесценный змеиный рубин Клеопатры был украден!

Три дня назад мир потрясло сенсационное известие: исследовательская экспедиция обнаружила в одном из храмов, построенных во времена великой египетской императрицы Клеопатры, потайную комнату. В ней кроме бронзовой статуи императрицы обнаружилась поразительной красоты диадема, ранее считавшаяся бесследно утерянной! Ученые сообщили, что диадема увенчана алым a-каратным рубином в форме змеиной головы. Однако буквально пару часов назад поступила новость, что бесценное украшение было изувечено: кто-то пробрался в камеру хранения диадемы и вырезал из нее рубин! Полиция устанавливает круг подозреваемых...

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

Купив все N камней, Глеб тут же провел несколько пробных измерений, взвесив некоторые наборы из них, и отправил результаты Ане по электронной почте. Тем временем она проконсультировалась с известным исследователем старины Андрэ Шесто-Мерта по поводу украденной драгоценности и узнала, что по всем имеющимся историческим источникам рубин весил не a карат, как утверждали журналисты, а b карат!

Зная результаты взвешиваний Глеба, и учитывая, что все поддельные камни весят a карат, и только настоящий змеиный рубин может весить b карат, определите, какие из купленных камней могут на самом деле являться потерянной реликвией великой императрицы прошлого.

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

В первой строке находятся четыре целых числа N, a, b и K (1 ≤ N ≤ 200, 1 ≤ a, b ≤ 1 000 000, a ≠ b, 1 ≤ K ≤ 1 000).

Далее идут K строк, описывающих взвешивания, проведенные Глебом.

Первое число в i-ом описании — wi (1 ≤ wi ≤ 200 000 000), суммарный вес группы камней, участвовавших в i-ом взвешивании.

Второе число — mi (1 ≤ mi ≤ N) — количество камней, участвовавших в i-ом взвешивании.

Далее следуют mi целых чисел, упорядоченных по возрастанию, — номера камней, участвовавших в i-ом взвешивании.

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

Если среди купленных Глебом камней змеиного рубина точно нет, выведите строку "Fail" (без кавычек).

Если украденный рубин может присутствовать среди камней, то выведите в первой строке количество всех возможных кандидатур на роль древней реликвии, а второй строке — номера возможных вариантов. Выводить номера можно в произвольном порядке.

Если же Глеб в некоторый момент ошибся в расчетах, и присланная им информация о взвешиваниях не может соответствовать действительности, выведите строку "Impossible" (без кавычек).

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

Входные данные
4 15 17 2
30 2 1 3
47 3 2 3 4
Выходные данные
2
2 4
Входные данные
3 15 17 3
30 2 1 2
30 2 2 3
47 3 1 2 3
Выходные данные
Impossible
Входные данные
2 1 2 2
1 1 2
1 1 1
Выходные данные
Fail

Примечание

В первом тесте из первого взвешивания мы делаем вывод, что первый и третий камни гарантированно поддельные. С другой стороны, среди второго, третьего и четвёртого камня точно есть настоящий. Значит настоящим может оказаться второй или четвёртый камень.

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

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

Страница: << 112 113 114 115 116 117 118 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест