https://acm.timus.ru/problem.aspx?space=1&num=1005
Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
У вас есть несколько камней известного веса w1, …, wn. Напишите программу, которая распределит камни в две кучи так, что разность весов этих двух куч будет минимальной.
Ввод содержит количество камней n (1 ≤ n ≤ 20) и веса камней w1, …, wn (1 ≤ wi ≤ 100 000) — целые, разделённые пробельными символами.
Ваша программа должна вывести одно число — минимальную разность весов двух куч.
| исходные данные | результат |
|---|---|
| 5 | |
| 5 8 13 27 14 | 3 |
https://acm.timus.ru/problem.aspx?space=1&num=1296
Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Гиперпереход, открытый ещё в начале XXI-го века, и сейчас остаётся основным способом перемещения на расстояния до сотен тысяч парсеков. Но совсем недавно физиками открыто новое явление. Оказывается, длительностью альфа-фазы перехода можно легко управлять. Корабль, находящийся в альфа-фазе перехода, накапливает гравитационный потенциал. Чем больше накопленный гравитационный потенциал корабля, тем меньше энергии потребуется ему на прыжок сквозь пространство. Ваша цель — написать программу, которая позволит кораблю за счёт выбора времени начала альфа-фазы и её длительности накопить максимальный гравитационный потенциал. В самой грубой модели грави-интенсивность — это последовательность целых чисел pi. Будем считать, что если альфа-фаза началась в момент i и закончилась в момент j, то накопленный в течение альфа-фазы потенциал — это сумма всех чисел, стоящих в последовательности на местах от i до j.
В первой строке входа записано целое число N — длина последовательности, отвечающей за грави-интенсивность (0 ≤ N ≤ 60000). Далее идут N строк, в каждой записано целое число pi (−30000 ≤ pi ≤ 30000).
Максимальный гравитационный потенциал, который может накопить корабль в альфа-фазе прыжка. Считается, что потенциал корабля в начальный момент времени равен нулю.
| исходные данные | результат |
|---|---|
| 10 | |
| 31 -41 59 26 -53 58 97 -93 -23 84 | 187 |
| ___________________________________ | ___________ |
| 3 | |
| -1 -5 -6 | 0 |
https://acm.timus.ru/problem.aspx?space=1&num=2025
Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Бокс, каратэ, самбо… Классические боевые единоборства пресытили аудиторию. Поэтому известный спортивный канал запускает новый формат соревнований, основанный на традиционной русской забаве — боях стенка на стенку. В соревновании могут участвовать от двух до k команд, каждая из которых будет соперничать с остальными. Всего в соревновании примут участие n бойцов. Перед началом боя они должны разделиться на команды, каждый боец должен войти ровно в одну команду. За время боя два бойца сразятся, если они состоят в разных командах. Организаторы считают, что популярность соревнований будет тем выше, чем больше будет количество схваток между бойцами. Помогите распределить бойцов по командам так, чтобы максимизировать количество схваток между бойцами, и выведите это количество.
В первой строке дано количество тестов T (1 ≤ T ≤ 10). В следующих T строках перечислены тесты. В каждой из них записаны целые числа n и k через пробел (2 ≤ k ≤ n ≤ 104).
Для каждого теста в отдельной строке выведите одно целое число — ответ на задачу.
| исходные данные | результат |
|---|---|
| 3 | |
| 6 3 | 12 |
| 5 5 | 10 |
| 4 2 | 4 |
https://acm.timus.ru/problem.aspx?space=1&num=1207
Ограничение времени: 0.5 секунды
Ограничение памяти: 64 МБ
На плоскости находятся N точек (N чётно). Никакие три точки не лежат на одной прямой. Ваша задача — выбрать две точки так, что прямая линия, проходящая через них, делит множество точек на две части одинакового размера.
Первая строка содержит целое число N (4 ≤ N ≤ 10 000). Каждая из следующих N строк содержит пары целых чисел xi, yi (−106 ≤ xi, yi ≤ 106) — координаты i-й точки.
Выведите номера выбранных точек.
| исходные данные | результат |
|---|---|
| 4 | 1 4 |
| 0 0 | |
| 1 0 | |
| 0 1 | |
| 1 1 |
https://acm.timus.ru/problem.aspx?space=1&num=1604
Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Главный бульдог-полицейский Страны Дураков решил ввести ограничение скоростного режима на автомобильной трассе, ведущей от Поля Чудес к пруду Черепахи Тортиллы. Для этого он заказал у Папы Карло n знаков ограничения скорости. Папа Карло слабо разбирался в дорожном движении и поэтому изготовил знаки с разными ограничениями на скорость: 49 км/ч, 34 км/ч, 42 км/ч, и т.д. Всего получилось k различных ограничений: n1 знаков с одним ограничением, n2 знаков со вторым ограничением, и т.д. (n1 + … + nk = n) Бульдог-полицейский ничуть не расстроился, получив такие знаки, напротив, он решил извлечь из этого экономическую выгоду. Дело в том, что по Правилам дорожного движения Страны Дураков ограничение на скорость действует вплоть до следующего знака. Если на знаке написано число 60, это означает, что участок от данного знака до следующего нужно проехать ровно со скоростью 60 километров в час — не больше и не меньше. Бульдог распорядился расставить знаки так, чтобы обогатившимся на Поле Чудес автолюбителям во время своего движения по трассе приходилось как можно больше раз менять скорость. Для этого нужно расставить имеющиеся знаки в правильном порядке. Если Вы поможете бульдогу это сделать, то он готов будет поделиться с Вами частью своих доходов.
В первой строке дано число k — количество различных типов знаков с ограничением скорости (1 ≤ k ≤ 10000). Во второй строке через пробел перечислены целые положительные числа n1, …, nk. Сумма всех ni не превосходит 10000.
Выведите n целых чисел в пределах от 1 до k — порядок, в котором нужно расставить по трассе имеющиеся знаки. Вне зависимости от того, какой знак стоит первым, считается, что, проезжая его, водитель меняет скорость, так как до этого ограничения не действовали. Если задача имеет несколько решений, выведите любое.
| исходные данные | результат |
|---|---|
| 2 | |
| 2 2 | 2 |
https://acm.timus.ru/problem.aspx?space=1&num=1726
Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Программный комитет школьных соревнований по программированию, проходящих в УрГУ — многочисленная, весёлая и дружная команда. Дружная настолько, что общения в университете им явно не хватает, поэтому они часто ходят друг к другу в гости. Все ребята в программном комитете очень спортивные и ходят только пешком. Однажды хранитель традиций олимпиадного движения УрГУ подумал, что на пешие прогулки от дома к дому члены программного комитета тратят слишком много времени, которое могли бы вместо этого потратить на придумывание и подготовку задач. Чтобы доказать это, он решил посчитать, какое расстояние в среднем преодолевают члены комитета, когда ходят друг к другу в гости. Хранитель традиций достал карту Екатеринбурга, нашёл на ней дома всех членов программного комитета и выписал их координаты. Но координат оказалось так много, что хранитель не смог справиться с этой задачей самостоятельно и попросил вас помочь ему. Город Екатеринбург представляет собой прямоугольник со сторонами, ориентированными по сторонам света. Все улицы города идут строго с запада на восток или с севера на юг, проходя через весь город от края до края. Дома всех членов программного комитета расположены строго на пересечении каких-то двух перпендикулярных улиц. Известно, что все члены комитета ходят только по улицам, поскольку идти по тротуару гораздо приятнее, чем по дворовым тропинкам. И, конечно, при переходе от дома к дому они всегда выбирают кратчайший путь. Программный комитет очень дружный, и все его члены ходят в гости ко всем одинаково часто.
Первая строка содержит целое число n — количество членов программного комитета (2 ≤ n ≤ 105). В i-й из следующих n строк через пробел записаны целые числа xi, yi — координаты дома i-го члена программного комитета (1 ≤ xi, yi ≤ 106).
Выведите среднее расстояние, которое проходит член программного комитета от своего дома до дома своего товарища, округлённое вниз до целых.
| исходные данные | результат |
|---|---|
| 3 | 13 |
| 10 10 | |
| 20 20 | |
| 10 20 |
https://acm.timus.ru/problem.aspx?space=1&num=1067
Ограничение времени: 2.0 секунды Ограничение памяти: 64 МБ
Hacker Bill has accidentally lost all the information from his workstation's hard drive and he has no backup copies of its contents. He does not regret for the loss of the files themselves, but for the very nice and convenient directory structure that he had created and cherished during years of work. Fortunately, Bill has several copies of directory listings from his hard drive. Using those listings he was able to recover full paths (like "WINNT\SYSTEM32\CERTSRV\CERTCO~1\X86") for some directories. He put all of them in a file by writing each path he has found on a separate line. Your task is to write a program that will help Bill to restore his state of the art directory structure by providing nicely formatted directory tree.
The first line of the input contains single integer number N (1 ≤ N ≤ 500) that denotes a total number of distinct directory paths. Then N lines with directory paths follow. Each directory path occupies a single line and does not contain any spaces, including leading or trailing ones. No path exceeds 80 characters. Each path is listed once and consists of a number of directory names separated by a back slash (""). Each directory name consists of 1 to 8 uppercase letters, numbers, or the special characters from the following list: exclamation mark, number sign, dollar sign, percent sign, ampersand, apostrophe, opening and closing parenthesis, hyphen sign, commercial at, circumflex accent, underscore, grave accent, opening and closing curly bracket, and tilde ("!#$%&'()-@^_`{}~").
Write to the output the formatted directory tree. Each directory name shall be listed on its own line preceded by a number of spaces that indicate its depth in the directory hierarchy. The subdirectories shall be listed in lexicographic order immediately after their parent directories preceded by one more space than their parent directory. Top level directories shall have no spaces printed before their names and shall be listed in lexicographic order. See sample below for clarification of the output format.
| исходные данные | результат |
|---|---|
| 7 | GAMES |
| WINNT\SYSTEM32\CONFIG | DRIVERS |
| GAMES | HOME |
| WINNT\DRIVERS | WIN |
| HOME | SOFT |
| WIN\SOFT | WINNT |
| GAMES\DRIVERS | DRIVERS |
| WINNT\SYSTEM32\CERTSRV\CERTCO~1\X86 | SYSTEM32 |
| CERTSRV | |
| CERTO~1 | |
| X86 | |
| CONFIG |
https://acm.timus.ru/problem.aspx?space=1&num=1494
Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Стол для монобильярда, установленный в игровом доме уездного города N, оказался очень прибыльным вложением. До того, как в городе появился небезызвестный господин Чичиков. Раз за разом он выигрывал, и хозяин, подсчитывая убытки, понимал, что дело тут нечисто. Однако уличить подлеца в жульничестве не удавалось до прибытия в город N ревизора из Петербурга. Правила игры в монобильярд очень просты: нужно последовательно закатить в единственную лузу шары с номерами 1, 2, …, N (именно в этом порядке). Пока господин Чичиков играл, ревизор несколько раз подходил к столу и забирал из лузы последний закатившийся туда шар. В конце концов, оказалось, что Чичиков закатил в лузу все шары, а ревизор все шары достал и обследовал. Аферист утверждал, что закатил шары в правильном порядке. Хозяин понял, что это его шанс: ревизор должен помнить, в каком порядке он доставал шары. Однако так ли легко будет доказать жульничество?
В первой строке записано целое число N — количество бильярдных шаров (1 ≤ N ≤ 100000). В следующих N строках даны номера этих шаров в том порядке, в котором ревизор забирал их из лузы.
Выведите слово «Cheater», если Чичиков не мог закатить все N шаров в правильном порядке. Иначе выведите «Not a proof».
| исходные данные | результат |
|---|---|
| 2 | Not a proof |
| 2 | |
| 1 | |
| ----------------- | ------------ |
| 3 | |
| 3 | |
| 1 | |
| 2 |
В первом примере Чичиков мог закатить шары в правильном порядке, если ревизор достал их оба по очереди уже после того, как Чичиков закатил второй шар. Во втором примере Чичиков мог закатить шары в любом порядке, кроме правильного 1-2-3.
https://acm.timus.ru/problem.aspx?space=1&num=1521
Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
В ходе недавних военных учений (более подробно эта история рассказана в задаче «Военные учения») министр обороны Советской Федерации товарищ Иванов имел возможность лично убедиться в блестящей боевой готовности солдат вверенной ему Советской Армии. Но одна вещь всё же продолжала беспокоить выдающегося военачальника. Прославленный генерал понимал, что была продемонстрирована лишь физическая подготовка солдат. Теперь настало время организовать очередные учения и проверить интеллектуальные способности личного состава. Генерал Шульман, вновь назначенный ответственным за проведение учений, пожертвовал все выделенные деньги бедным и с чистой совестью лёг спать. Во сне генералу явился учебник по тактике и изложил схему, руководствуясь которой можно провести учения совершенно бесплатно.
В соответствии с этой схемой учения делятся на N раундов, в течение которых N солдат, последовательно пронумерованных от 1 до N, маршируют друг за другом по кругу, т.е. первый следует за вторым, второй за третьим, ..., (N-1)-й за N-м, а N-й за первым. В каждом раунде очередной солдат выбывает из круга и идёт чистить унитазы, а оставшиеся продолжают маршировать. В очередном раунде выбывает солдат, марширующий на K позиций впереди выбывшего на предыдущем раунде. В первом раунде выбывает солдат с номером K. Разумеется, г-н Шульман не питал никаких надежд на то, что солдаты в состоянии сами определить очерёдность выбывания из круга. «Эти неучи даже траву не могут ровно покрасить», – фыркнул он и отправился за помощью к прапорщику Шкурко.
Единственная строка содержит целые числа N (1 ≤ N ≤ 100000) и K (1 ≤ K ≤ N).
Вывести через пробел номера солдат в порядке их выбывания из круга.
| исходные данные | результат |
|---|---|
| 5 3 | 3 1 5 2 4 |
https://acm.timus.ru/problem.aspx?space=1&num=1650
Ограничение времени: 3.0 секунды
Ограничение памяти: 64 МБ
Возможно, вы знаете, что из всех городов мира больше всего миллиардеров живёт в Москве. Но, поскольку работа миллиардера подразумевает частые перемещения по всему свету, в определённые дни какой-то другой город может занимать первую строчку в таком рейтинге. Ваши приятели из ФСБ, ФБР, MI5 и Шин Бет скинули вам списки перемещений всех миллиардеров за последнее время. Ваш работодатель просит посчитать, сколько дней в течение этого периода каждый из городов мира был первым по общей сумме денег миллиардеров, находящихся в нём.
В первой строке записано число n — количество миллиардеров (1 ≤ n ≤ 10000). Каждая из следующих n строк содержит данные на определённого человека: его имя, название города, где он находился в первый день данного периода, и размер состояния. В следующей строке записаны два числа: m — количество дней, о которых есть данные (1 ≤ m ≤ 50000), k — количество зарегистрированных перемещений миллиардеров (0 ≤ k ≤ 50000). Следующие k строк содержат список перемещений в формате: номер дня (от 1 до m − 1), имя человека, название города назначения. Вы можете считать, что миллиардеры путешествуют не чаще одного раза в день, и что они отбывают поздно вечером и прибывают в город назначения рано утром следующего дня. Список упорядочен по возрастанию номера дня. Все имена и названия городов состоят не более чем из 20 латинских букв, регистр букв имеет значение. Состояния миллиардеров лежат в пределах от 1 до 100 миллиардов
В каждой строке должно содержаться название города и, через пробел, количество дней, в течение которых этот город лидировал по общему состоянию миллиардеров, находящихся в нём. Если таких дней не было, пропустите этот город. Города должны быть отсортированы по алфавиту (используйте обычный порядок символов: ABC...Zabc...z).
| исходные данные | результат |
|---|---|
| 5 | Anadyr 5 |
| Abramovich London 15000000000 | London 14 |
| Deripaska Moscow 10000000000 | Moscow 1 |
| Potanin Moscow 5000000000 | |
| Berezovsky London 2500000000 | |
| Khodorkovsky Chita 1000000000 | |
| 25 9 | |
| 1 Abramovich Anadyr | |
| 5 Potanin Courchevel | |
| 10 Abramovich Moscow | |
| 11 Abramovich London | |
| 11 Deripaska StPetersburg | |
| 15 Potanin Norilsk | |
| 20 Berezovsky Tbilisi | |
| 21 Potanin StPetersburg | |
| 22 Berezovsky London |
https://acm.timus.ru/problem.aspx?space=1&num=1080
Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Рассмотрим географическую карту с N странами, занумерованными от 1 до N (0 < N < 99). Для каждой страны известны номера соседних стран, т.е. имеющих общую границу с данной. Из каждой страны можно попасть в любую другую, перейдя некоторое количество границ. Напишите программу, которая определит, возможно ли покрасить карту только в два цвета — красный и синий — так, что если две страны имеют общую границу, их цвета различаются. Цвет первой страны — красный. Ваша программа должна вывести одну возможную раскраску для остальных стран или сообщить, что такая раскраска невозможна.
В первой строке записано число N. Из следующих N строк i-я строка содержит номера стран, с которыми i-я страна имеет границу. Каждое целое число в i-й строке больше, чем i, кроме последнего, которое равно 0 и обозначает конец списка соседей i-й страны. Если строка содержит 0, это значит, что i-я страна не соединена ни с одной страной с бoльшим номером.
Вывод содержит ровно одну строку. Если раскраска возможна, эта строка должна содержать список нулей и единиц без разделителей между ними. i-я цифра в этой последовательности обозначает цвет i-й страны. 0 соответствует красному цвету, единица — синему. Если раскраска невозможна, выведите целое число –1.
| исходные данные | результат |
|---|---|
| 3 | 010 |
| 2 0 | |
| 3 0 | |
| 0 |
https://acm.timus.ru/problem.aspx?space=1&num=1160
Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Andrew is working as system administrator and is planning to establish a new network in his company. There will be N hubs in the company, they can be connected to each other using cables. Since each worker of the company must have access to the whole network, each hub must be accessible by cables from any other hub (with possibly some intermediate hubs). Since cables of different types are available and shorter ones are cheaper, it is necessary to make such a plan of hub connection, that the maximum length of a single cable is minimal. There is another problem - not each hub can be connected to any other one because of compatibility problems and building geometry limitations. Of course, Andrew will provide you all necessary information about possible hub connections. You are to help Andrew to find the way to connect hubs so that all above conditions are satisfied.
The first line contains two integer: N - the number of hubs in the network (2 ≤ N ≤ 1000) and M — the number of possible hub connections (1 ≤ M ≤ 15000). All hubs are numbered from 1 to N. The following M lines contain information about possible connections - the numbers of two hubs, which can be connected and the cable length required to connect them. Length is a positive integer number that does not exceed 106. There will be no more than one way to connect two hubs. A hub cannot be connected to itself. There will always be at least one way to connect all hubs.
Output first the maximum length of a single cable in your hub connection plan (the value you should minimize). Then output your plan: first output P - the number of cables used, then output P pairs of integer numbers - numbers of hubs connected by the corresponding cable. Separate numbers by spaces and/or line breaks.
| исходные данные | результат |
|---|---|
| 4 6 | 1 |
| 1 2 1 | 4 |
| 1 3 1 | 1 2 |
| 1 4 2 | 1 3 |
| 2 3 1 | 2 3 |
| 3 4 1 | 3 4 |
| 2 4 1 |
https://acm.timus.ru/problem.aspx?space=1&num=1450
Ограничение времени: 0.5 секунды
Ограничение памяти: 64 МБ
Большими неприятностями обернулся прошедший год для Государства Российского. То неурожай, то птичий грипп, то вечные споры хозяйствующих субъектов... A тут ещё и Президент задумал, наконец, собрать средства на покупку новой балалайки и ручного медведя для своего двоюродного племянника. Все эти факторы (в особенности, конечно, последний) сильно ударили по экономике государства. Посовещавшись со своими друзьями в валенках и ушанках, Президент решил воспользоваться традиционным методом укрепления национального бюджета - увеличением налога на транспортировку газа.
Сеть российских газопроводов представляет собой N перекачивающих станций, некоторые из которых соединены газопроводами. Для каждого из M газопроводов известны номера станций A[i] и B[i], которые он соединяет, и его прибыльность C[i], т.е. то количество долларов, которое будет ежесуточно приносить в виде налогов перекачка газа по этому газопроводу. Каждая пара станций соединена не более чем одним газопроводом. Сеть была построена советскими инженерами, которые точно знали, что газ поставляется из месторождений Украины в Сибирь, а не наоборот. Поэтому все газопроводы являются однонаправленными, т.е. для каждого газопровода перекачка газа возможна только в направлении из станции с номером A[i] на станцию с номером B[i]. Более того, для любых двух станций X и Y верно, что если возможна перекачка газа из X на Y (возможно, через промежуточные станции), то обратная перекачка из Y на X невозможна. Известно, что газ поступает на начальную станцию с номером S и отгружается потребителям на конечной станции с номером F. Президент потребовал от Правительства указать маршрут (т.е. линейную последовательность попарно соединённых газопроводами станций) перекачки газа из начальной станции на конечную, причём прибыльность этого маршрута должна быть максимальной. Под прибыльностью маршрута понимается суммарная прибыльность входящих в него газопроводов. К сожалению, Президент не учёл того факта, что многие газопроводы изначальной сети уже давно прекратили существование, в результате чего может оказаться, что перекачка газа из начальной станции на конечную вообще невозможна...
Первая строка содержит целые числа N (2 ≤ N ≤ 500) и M (0 ≤ M ≤ 124750). Каждая из следующих M строк содержит целые числа A[i], B[i] (1 ≤ A[i], B[i] ≤ N) и C[i] (1 ≤ C[i] ≤ 10000) для соответствующего газопровода. Последняя строка содержит целые числа S и F (1 ≤ S, F ≤ N; S ≠ F).
Если искомый маршрут существует, выведите его прибыльность. Иначе выведите "No solution".
| исходные данные | результат |
|---|---|
| 6 7 | 17 |
| 6 5 10 | |
| 1 4 11 | |
| 1 2 4 | |
| 3 1 5 | |
| 2 4 5 | |
| 6 3 1 | |
| 6 1 3 | |
| 6 4 |
В примере искомым маршрутом является маршрут 6>3>1>4.