Страница: << 100 101 102 103 104 105 106 >> Отображать по:

#111976

Гномы и одинокая гора

Источники: [ Командные олимпиады, ВКОШП, 2013, Задача C ]

Гномы продолжают искать золото предков в недрах Одинокой горы. Недра Одинокой горы представляют собой $n$ пещер, некоторые из которых соединены двусторонними переходами. При этом из каждой пещеры в любую другую можно попасть по переходам, причем это можно сделать единственным способом.

Гномы разделились на два отряда, которые начали свои поиски с пещер $u_0$ и $v_0$, соответственно. Гномы каждого из отрядов перемещаются вместе. На обследование пещеры у отряда гномов уходит ровно одна минута, после чего каждый отряд быстро перемещается по переходу в одну из соседних пещер. При этом гномы никогда не заходят в пещеру, если они или другой отряд в ней уже побывали. Оба отряда никогда не заходят в одну и ту же пещеру. Если хотя бы один из отрядов гномов не может переместиться в соответствии с этими правилами, оба отряда сразу прекращают поиски сокровищ.

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

Формат входного файла

В первой строке число $n$ ($2 \le n \le 200\,000$) - число пещер в Одинокой горе.

В следующих $n - 1$ строках заданы переходы между пещерами. В каждой строке записаны номера двух пещер $v$ и $u$, соединенных переходом

($1 \le v, u \le n$).

В следующей строке заданы номера пещер $v_0$ и $u_0$, в которых исходно находятся два отряда гномов ($1 \le v_0, u_0 \le n$, $v_0 \ne u_0$).

Формат выходного файла

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

Примеры

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

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

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

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

#111977

Покраска забора

Источники: [ Командные олимпиады, ВКОШП, 2013, Задача D ]

Том Сойер уговорил $n$ своих друзей помочь ему в нелегком деле покраски забора, окружающего дом тетушки Полли. Забор представляет собой $k$ последовательных досок, пронумерованных от 1 до $k$, причем после $k$-й доски опять идет первая.

Друзья Тома очень привередливы, $i$-й друг согласен участвовать в покраске только в том случае, если ему дадут покрасить участок из ровно $a_i$ последовательных досок.

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

При этом каждый из друзей Тома готов красить как еще неокрашенную доску забора, так и доску, которую уже покрасил один из его предшественников. Тем не менее, друзья получают больше удовольствия от покраски неокрашенной доски. Том хочет выбрать число $x$ и распределить отрезки забора для покраски таким образом, чтобы каждый из его друзей покрасил хотя бы $x$ неокрашенных досок. Том очень любит своих друзей и хочет, чтобы каждый из них получил от процесса покраски забора максимальное удовольствие, поэтому он пытается максимизировать $x$.

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

Формат входного файла

Первая строка входного файла содержит два целых числа $n$ ($1 \le n \le 10^5$) и $k$ ($1 \le k \le 10^9$). Следующая строка содержит $n$ целых чисел - значения $a_i$ ($1 \le a_i \le k$).

Формат выходного файла

Выведите одно число - максимальное возможное значение $x$.

Пояснения к примерам

В первом примере $x = 5$, так как один из друзей просто не хочет красить больше пяти досок. Он придет первым, покрасит свои пять, после чего еще 10 неокрашенных досок достанется второму другу Тома. Оставшиеся 85 досок Тому придется красить самому.

Во втором примере достичь $x = 2$ можно, например, так. Сначала третий друг красит доски с 4 по 6 (3 неокрашенных доски). Затем четвертый друг красит доски с 1 по 5 (3 неокрашенных доски). Затем второй друг красит доски с 1 по 8 (2 неокрашенных доски). Наконец, первый друг красит доски с 6 по 10 и с 1 по 2 (2 неокрашенных доски, заметим, что забор идет по циклу и эти доски образуют последовательный отрезок).

Примеры

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

2 100
5 10

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

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

4 10
7 8 3 5

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

#111978

Телефонные номера

Источники: [ Командные олимпиады, ВКОШП, 2013, Задача E ]

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

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

При отображении телефонного номера на экране телефона, части этого номера принято отделять друг от друга различными символами так, чтобы номер было проще прочитать и запомнить. Так, перед кодом страны обычно ставится символ <<+>>, код региона или оператора берется в скобки, номер абонента разделяется символами <<->> на несколько частей. При этом, то, на сколько частей он разбивается, напрямую зависит от количества цифр в нем:

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

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

Формат входного файла

Первая строка файла содержит одно целое число $n$ ($1 \le n \le 100$) - количество государств, информация про телефонные коды которых записана в память телефона. Далее следуют $n$ описаний этих государств, разделенных переводами строк.

Первая строка описания каждого государства содержит два целых числа $c$ и $k$ ($1 \le c \le 999$, $1 \le k \le 100$) - телефонный код этого государства и количество операторов или регионов, существующих в этом государстве. Следующие $k$ строк описания этого государства содержат целые числа, каждое из которых не меньше 100 и не больше 99999 - коды операторов или регионов, зарегистрированных в этом государстве.

Следующая строка входного файла содержит одно целое число $m$ ($1 \le m \le 10{\,}000$) - количество телефонных номеров, которые необходимо отформатировать. Следующие $m$ строк содержат сами номера - строки, состоящие ровно из 11 цифр.

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

Формат выходного файла

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

Вместо номеров, корректного разбиения которых на код государства, код оператора или региона и номер абонента не существует, необходимо вывести слово "Incorrect".

Примеры

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

2
7 3
981
3517
812
351 3
34712
1234
963
8
79818266456
35196328463
78122472557
01234567890
73517960326
35134712239
35112342013
78120102030

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

+7(981)826-64-56
+351(963)284-63
+7(812)247-25-57
Incorrect
+7(3517)96-03-26
+351(34712)239
+351(1234)20-13
Incorrect

#111979

Вращающаяся пластина

Источники: [ Командные олимпиады, ВКОШП, 2013, Задача F ]

Мальчик Вася очень любит геометрию. Кроме того, ему очень нравится забивать гвозди в доску. Сегодня он изучает свою любимую металлическую пластину, которую он собирается прибить к деревянной доске.

Пластина имеет форму, ограниченную многоугольником без самопересечений и самокасаний. В первой вершине многоугольника пластина имеет маленькую петлю.

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

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

Формат входного файла

В первой строке входного файла задано число $n$ ($3 \le n \le 2\,000$) - количество вершин многоугольника. В следующих $n$ строках заданы координаты вершин многоугольника в порядке обхода.

В следующей строке задано число $m$ ($1 \le m \le 2\,000$) - количество точек, которые Вася рассматривает как возможные положения второго гвоздя. В следующих $m$ строках заданы координаты этих точек. Все эти точки находятся снаружи от исходного положения пластины.

Все координаты во входном файле целые и не превосходят $10^6$ по модулю.

Формат выходного файла

Выходной файл должен содержать $m$ строк.

В $i$-й строке выведите два вещественных числа $\alpha_i$ и $\beta_i$, где $\alpha_i$ - максимальный угол в градусах, на который можно повернуть пластину по часовой стрелке, если Вася забьет гвоздь в $i$-ю точку, а $\beta_i$ - максимальный угол в градусах ,на который в этом случае можно повернуть пластину против часовой стрелки.

Если гвоздь не мешает пластине поворачиваться, выведите $\alpha_i = \beta_i = 360$.

Ответ считается верным, если его абсолютная или относительная погрешность относительно правильного не превосходит $10^{-6}$.

Пояснения к примеру

$\text{[math]}$

На рисунке выше изображен тест из примера. Прямоугольник показывает начальное положение пластины. Точками показаны позиции, в которые Вася планирует забить гвоздь.

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

Гвоздь, забитый во вторую точку, позволяет повернуть пластину на $45^\circ$ по часовой стрелке или на $225^\circ$ против часовой стрелки.

Примеры

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

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

360.000000000000 360.000000000000
45.000000000000 225.000000000000
251.565051177078 18.434948822922

#111980

Призы

Источники: [ Командные олимпиады, ВКОШП, 2013, Задача G ]

Организаторы Всероссийской командной олимпиады школьников по программированию всегда ответственно относятся ко всем этапам проведения соревнования. Недавно организаторам были доставлены футболки для участников олимпиады. Они были сложены в ящик, который является кубом со стороной в один метр. Ящик был поставлен в углу комнаты прямоугольной формы размером $m \times n$ метров. Чтобы никто случайно не забрал ящик, на его верхней грани красной краской написали слово <<ВКОШП>>.

Сегодня организаторам вдруг понадобилось переставить этот ящик в противоположный угол комнаты. Но, к сожалению, ящик оказался настолько тяжелым, что никто не мог сдвинуть его с места. Выяснилось, что все, что можно сделать с ящиком - перекатить его через ребро нижней грани. Соответствующее ребро при этом остается на том же месте, а нижней становится другая смежная с этим ребром грань.

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

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

Помогите организаторам - посчитайте, сколько раз надпись <<ВКОШП>> коснется пола при оптимальном перекатывании куба с футболками.

Формат входного файла

В первой строке задано два числа $n$ и $m$ ($1 \le n, m \le 10^9$) - размеры комнаты в метрах.

Формат выходного файла

Выведите одно число - сколько раз надпись <<ВКОШП>> окажется на нижней грани при оптимальном перемещении ящика.

Пояснения к примерам

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

Во втором примере необходимо четыре перекатывания. В любом случае хотя бы один раз надпись <<ВКОШП>> коснется пола. Один из способов сделать перекатывания так, чтобы это произошло один раз, следующий. Сначала два раза перекатим куб в одном направлении (он окажется в соседнем углу комнаты). Сейчас надпись <<ВКОШП>> находится на нижней грани и касается пола. Затем перекатим куб еще два раза в перпендикулярном направлении. Теперь куб находится в требуемом положении.

Примеры

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

1 2

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

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

3 3

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

Страница: << 100 101 102 103 104 105 106 >> Отображать по:

Выбрано

Отменить

Добавить в контест