|
| |||||
|
|
|
||||
|
К берегу реки, текущей по равнине, подошел турист. До заката солнца остался один час. Туристу хочется отметить на карте ту область, куда за это время он может добраться для организации ночлега. Турист может передвигаться по суше со скоростью v (0 £ v £ 100), а по воде — со скоростью w (0 £ w £ 100). Напишите программу, определяющую площадь отмеченной на карте области суши. Река течет прямолинейно и имеет постоянную ширину h (0 £ h £ 100). Считается, что скорость реки равна нулю. Входные данные В единственной строке входного файла записаны через пробел три действительных числа v , w и h с точностью до 0.01. Выходные данные В выходной файл нужно вывести одно число S — искомую площадь с точностью до 0.01. Пример
В государстве есть N городов (1 £ N £ 100), и каждый город соединен с каждым дорогой с односторонним движением (всего дорог). Царь однажды заметил, что не из любого города можно добраться до любого другого. Он подумал: а нельзя ли найти один такой город, чтобы, изменив направления всех входящих в него и выходящих из него дорог на противоположные, можно было проехать из каждого города в любой другой. Входные данные Входной файл состоит из нескольких подряд идущих тестовых блоков, количество которых не превосходит 1000. В первой строке каждого тестового блока записано целое число N — количество городов. Города занумерованы числами от 1 до N . В следующих N строках для каждого города по порядку описаны дороги, выходящие из него. Каждая строка состоит из последовательности целых чисел, записанных через пробел. Первое в строке число M i — это количество выходящих из города дорог, а следующие за ним M i чисел — номера городов, в которые ведут эти дороги (1 £ i £ N , 0 £ M i £ N – 1). Выходной файл заканчивается строкой, содержащей один 0 . Выходные данные В выходной файл для каждого тестового блока нужно в отдельную строку записать номер города, для которого достаточно изменить направления входящих и выходящих дорог, чтобы после этого можно было попасть из любого города в любой. Если такого города нет, то выдать –1, а если ничего менять не нужно, то выдать 0. Пример
На одном вокзале построили автоматизированную камеру хранения багажа: выкопали много подземных этажей, а вместо кладовщика поставили робота. Чем глубже под землю, тем большую площадь могли занимать ячейки камеры хранения: на верхних этажах им приходилось конкурировать с подземными парковками и т.п., и арендная плата была выше. Программисты заставили строителей выкопать много ячеек, а потом соединить их в виде древесной структуры: из любой ячейки (за исключением самых нижних, разумеется) вниз шли две лестницы — в левом и в правом углу. Таким образом, на k -м этаже находилось 2 k -1 ячеек. К сожалению, программисты написали для механического кладовщика неудачную программу (наверное, они рассчитывали на проценты с выручки): робот ни за что не хотел располагать в одной ячейке багаж, принадлежащий одному пассажиру. Самый первый баул он размещал на первом этаже, а для каждого последующего искал подходящую ячейку следующим образом: если чемодан был тяжелее, чем оставленный на первом этаже, то робот спускался на один этаж вправо, а если легче — на один этаж ниже влево. Аналогичным образом он поступал и с остальными баулами. Каждый раз, взяв очередной чемодан у пассажира, робот начинал поиски подходящей ячейки с первого этажа и спускался, следуя своему алгоритму ("тяжелее: вниз вправо; легче: вниз влево") до тех пор, пока не находил ячейку, где еще не было ни одного баула, принадлежащего данному пассажиру. А если робот находил два одинаковых по весу чемодана, то его программа зацикливалась, робот впадал в панику и громким воем сирены призывал ремонтника. Вместо того чтобы исправлять программу, ленивые программисты порекомендовали всем пассажирам не иметь в багаже чемоданов одинакового веса. Пассажирам было некогда спорить, и они подчинились этому нелепому требованию. Стоимость хранения одного места багажа в этой камере хранения высчитывается как произведение веса на коэффициент глубины этажа: чем ниже, тем дороже. Для первого этажа коэффициент всегда равен 1, для второго — S , для N -го – S N –1 . Напишите программу, которая построит имеющийся у вас багаж в такую последовательность, чтобы стоимость его хранения была минимальной. Входные данные В первой строке входного файла записано через пробел два целых числа S и К (1 £ S £ 10, 1 £ К £ .50), где K — количество мест багажа. Во второй строке даны К различных целых чисел X i , характеризующих вес каждого места багажа (0 £ X i £ 100, 1 £ i £ K ). Считается, что количество этажей и количество пустых мест в камере хранения всегда достаточно, чтобы разместить весь ваш багаж. Входные данные В выходной файл нужно записать одно число: минимальную стоимость хранения всего багажа. Пример
ОАО «Средняя миля» занимается прокладкой территориальной сети по микрорайону города Урюпинска. Перед сотрудниками ОАО встала задача соединить два здания, находящихся в разных концах микрорайона. Будучи в плохих отношениях с телефонистами, ОАО не может использовать существующую сеть кабельной канализации. Было решено соединять здания радиорелейной сетью, возможно, устанавливая ретрансляторы на крышах других зданий. Дальность используемого оборудования достаточна, чтобы соединить данные здания (и вообще любые два здания в микрорайоне). Проблема состоит в том, что приемники и передатчики радиорелейных станций, работающие в СВЧ-диапазоне, должны находиться в зоне прямой видимости, т.е. приемник не должен быть закрыт от передатчика другими зданиями микрорайона. Причём, если приёмник, передатчик и край какого-либо здания находятся на одной линии, то связь невозможна. По требованию местного жилищно-коммунального управления, ретрансляторы можно ставить только на северный или на южной края крыши здания, или на оба. Передача сигнала от одного конца здания до другого осуществляется без использования ретрансляторов. Вам необходимо написать программу, которая могла бы помочь сотрудникам ОАО проложить оптимальный путь, соединяющий необходимые здания. Оптимальным в данном случае является путь, использующий минимальное число промежуточных ретрансляторов. Входные данные В первой строке входного файла вводятся три числа: общее количество зданий в микрорайоне N , и номера зданий i и j , которые необходимо соединить радиорелейной линией (2 £ N £ 100, 1 £ i , j £ N ). В следующих N строках вводится расположение зданий микрорайона. Каждая строка описывает одно здание. Микрорайон строился по принципу меридиональной застройки, т.е. каждое здание в плане представляет собой отрезок прямой, направленный точно с юга на север. Благодаря этому, каждое здание может быть описано четырьмя целыми числами: долготой l , широтой южной и северной стен s , n соответственно , и высотой крыши h . Долгота, широты и высота измеряются в метрах и отсчитываются от некоторой точки в пределах микрорайона так, что –1000 £ l , s , n , £ 1000, 0 £ h £ 500. Шириной здания по долготе можно пренебречь. Выходные данные В первую строку необходимо вывести целое число — минимальное количество необходимых промежуточных ретрансляторов. Если оконечные станции могут быть соединены напрямую, это число должно быть равно 0. В последующих строках выводятся номера зданий, на которых стоят ретрансляторы. Первым должен быть выведен номер здания i , затем все номера в порядке, соответствующем порядку прохождения радиолуча; последним должен быть выведен номер здания j . Пример
Во время войны 3050 г. с пришельцами разведчикам удалось выяснить, каким алгоритмом пользуются враги для кодирования особо важных радиосообщений. Этот алгоритм предназначен для шифрования коротких текстовых сообщений длиной до 10000 символов, состоящих из букв латинского алфавита и пробелов. При выполнении особо важной операции срочно понадобилось ввести в заблуждение силы противника путем посылки по их сетям связи ложной информации, закодированной соответствующим образом. Главнокомандующий Василий Пупкин предложил Вам написать программу, которая бы выполняла такое кодирование. Алгоритм кодирования состоит в следующем.
Входные данные В первой строке входного файла записано целое число K (1 £ K £ 100) — длина буфера. В следующей строке записано сообщение для кодирования, содержащее только символы латинского алфавита, цифры, знаки препинания (всевозможные символы, исключая квадратные скобки) и пробелы. Длина одного сообщения не превосходит 10000 символов. Выходные данные В выходной файл необходимо вывести закодированное сообщение. Примеры
Чебурашка, крокодил Гена, Шапокляк и другие известные вам персонажи решили поступить в университет — авось, чему-нибудь да и научат: может, крокодиловедению, а может, и чему покруче. Приемная комиссия университета постановила: пусть все сдают один экзамен в один день, а потом мы с ними как-нибудь разберемся. Решили поступить следующим образом: каждый абитуриент при поступлении указывает, на какой факультет он желает поступить в первую очередь, на какой — во вторую и т.д. А затем, в зависимости от набранных баллов, его зачисляют на наиболее желательный, с его точки зрения, факультет. Если же это невозможно, т.е. все места на этом факультете уже заняты, его зачисляют на второй факультет, указанный абитуриентом в своем списке и т.д. Если все факультеты, указанные в списке, уже полностью укомплектованы, то абитуриент никуда не зачисляется. Подобным образом поступают со всеми, начиная с лучшего и вплоть до абитуриента, набравшего наименьшее количество баллов. Ваша задача — для некоторого абитуриента определить, на какой факультет он поступит. Входные данные В первой строке входного файла записаны три числа N , K и L (1 £ N £ 1000, 1 £ K £ 10, 1 £ L £ N ), где N — число студентов, K — число факультетов, L — номер выбранного абитуриента. Все факультеты перенумерованы числами от 1 до K, а абитуриенты — от 1 до N . Во второй строке расположено K чисел – плановый набор на первый, второй и т.д. факультеты, соответственно. Каждое число дано в диапазоне от 0 до 1000, включительно. В последующих N строках записана информация о каждом студенте по порядку от 1-го до N -го. Каждая строка состоит из нескольких чисел, записанных через пробел. Первое число — это набранные данным абитуриентом баллы (неотрицательное целое число, не превышающее 10000), а следующие числа в этой строке — номера факультетов, на которые хотел бы поступить данный абитуриент, они даны в порядке убывания приоритетности (первым идет номер самого желаемого факультета и т.д.). При этом у всех абитуриентов разное число набранных баллов. Выходные данные В выходной файл необходимо вывести номер факультета, на который поступит абитуриент с номером L . Если он никуда не пройдет по конкурсу, то вывести число 0. Пример
Королевство Полигонландия представляет собой, как нетрудно догадаться, многоугольник. Великий исследователь Миклуха V нашел широту и долготу всех вершин многоугольника, а его предшественник Маклай IV открыл, что Земля — шар с радиусом 6400 км и что все вершины многоугольника соединяются дугами большого круга, т.е. по кратчайшему пути. И задумался великий правитель Полигонландии король Здесянхамон: а какую площадь имеет подвластная ему территория (ну, хотя бы с точностью до тысячи-другой квадратных километров)? И решил, что тому, кто точнее всех ответит на этот вопрос, он отдаст в жёны свою дочь, очертания которой напоминают эту самую Полигонландию. Ну что же, может, и мы тоже попытаемся победить в этом конкурсе? Входные данные Во входном файле в первой строке 3 £ N £ 100 – число вершин многоугольника, затем в последующих N строках идут координаты вершин многоугольника – по два вещественных числа в каждой строке – широта и долгота каждого пункта. Напоминаем, что широта меняется от –90 градусов (южная широта) до +90 градусов (северная широта), а долгота меняется от –180 градусов (западная долгота) до +180 градусов (восточная долгота). Точки перечисляются в порядке обхода либо по часовой стрелке, либо против часовой стрелки. Среди соседних точек нет диаметрально противоположных (первая и последняя точки тоже считаются соседними). При этом получается многоугольник без самопересечений и заранее известно, что площадь Полигонландии не больше половины площади Земного шара. Выходные данные В выходной файл необходимо вывести одно вещественное число S – площадь Полигонландии, округленную до целого числа тысяч квадратных километров. Пример
Последовательность начинается с произвольного четырехзначного числа в десятичной записи N 1 . Каждый следующий элемент последовательности N i + 1 = M i – m i , где M i – максимально возможное число, которое можно составить перестановкой всех цифр числа N i , а m i — соответственно, минимальное. Поскольку все элементы последовательности представляют собой четырехзначные целые числа, такая последовательность должна содержать цикл. Вам необходимо определить длину цикла и вывести все его элементы в том порядке, в каком они встречаются в последовательности. Входные данные Задача предполагает множественный ввод. В первой строке входного файла указывается количество входных чисел K (1 £ K £ 300000). Затем вводятся K значений числа N 1 , каждое число на отдельной строке. Выходные данные Выходной файл должен содержать K строк. В начале каждой строки должно выводиться количество элементов цикла последовательности, затем через пробел — элементы цикла этой последовательности. Числа менее 1000 должны выводиться с лидирующими нулями, дополняющими их представление до четырех знаков. Пример
Ученые взялись за какую-то большую и сложную проблему. Для ее решения написали распределенное приложение. Процессы приложения во время решения задачи должны обмениваться сообщениями. Каждый ученый запустил один или несколько процессов приложения на своем компьютере, и спустя некоторое время решение проблемы было найдено. После того, как решение было получено, возник вопрос о том, как происходил обмен данными между компьютерами. Но вот незадача — времена на компьютерах не были синхронизованы и осталась только информация о времени запуска приложения, времена вызовов функций пересылки и приема данных и их продолжительность. Ваша задача найти, на сколько отличаются времена на компьютерах, на которых считалась задача. Но из-за того, что время отправления сигнала регистрировалось в момент окончания отправления, а время получения сигнала регистрировалось в момент начала приема сигнала, может сложиться такая ситуация, что определение возможной разности времен на компьютерах невозможно. Входные данные В первой строке входного файла вводятся через пробел два числа N и M (1 ≤ N ≤ 100, 0 ≤ M ≤ 10000), где N — количество компьютеров, а M — количество пересланных пакетов данных. В следующих M строках задаются параметры пакетов данных: в каждой строке по три числа, записанных через пробел, i , j и Δ t (1 ≤ i ≤ N , 1 ≤ j ≤ N , –10000 ≤ Δ t ≤ 10000). Здесь i — номер компьютера, получившего пакет данных, j — номер компьютера, пославшего пакет данных, а Δ t — разница между временем начала получения i -м компьютером и временем окончания отправки j -м компьютером пакета данных. В Δt входят относительные времена, которые измерялись на i -м и j -м компьютерах соответственно. Поэтому разность реальных времен начала получения и окончания отправки данных могла быть отлична от Δt , если времена на компьютерах отличались. Выходные данные Выходной файл должен состоять из N чисел, по одному в каждой строке. В i -й строке должна содержаться возможная разность между временем i -го компьютера и сервера (сервер — компьютер c номером 1). При этом рассчитанные времена должны удовлетворять тому условию, что момент начала получения был позже момента окончания отправки каждого из пакетов данных. Если возможных наборов времен несколько, то нужно выдать любой из них. Если возможных наборов времен нет, то нужно выдать строку " NO SOLUTION " (все символы — заглавные латинские буквы). Пример
|
||||||||||||||||||||||||||||||||||||||||||
| |