Задача состоит в том, чтобы создать некоторое дерево подкаталогов в каталоге tmp и разместить в нём файлы так, чтобы доступ к самому далёкому файлу осуществлялся бы за минимально возможное количество действий: Альберт не хочет быть пойманным на списывании из-за промедления в поиске нужного файла
Более формально, при работе с файловой системой операционной системы CheatOS на экране телефона в каждый момент отображается содержимое текущего каталога в виде списка элементов, расположенных в следующем порядке: сперва символ «..» перехода в родительскую папку, затем список всех размещённых непосредственно в этом каталоге подкаталогов и файлов. Файлы и каталоги, содержащиеся в подкаталогах текущего каталога, не отображаются.
В каждый момент на один из элементов отображаемого списка (файл или папку) указывает курсор.
Нас будут интересовать два вида действий, которые потребуются Альберту на экзамене:
1. Войти в дочерний каталог, на который указывает курсор. При этом этот каталог становится текущим и всё его содержимое отображается на экране телефона так, как описано выше. Сразу после этого действия курсор указывает на символ «..».
2. Сдвинуть курсор на следующий по списку элемент (см. рисунок).
Изначально текущий каталог — tmp, курсор указывает на символ «..»
Расстоянием до файла будем называть минимальное суммарное число действий обоих видов, необходимое для того, чтобы курсор на экране стал указывать на этот файл.
Альберт просит вас помочь ему построить дерево каталогов и разместить в них все \(N\) файлов так, чтобы расстояние до самого далёкого файла было минимально возможным.
Времени до экзамена остается совсем немного, создавать каталоги на телефоне — трудоёмкое занятие, поэтому среди всевозможных деревьев каталогов с минимальным расстоянием он просит вас найти дерево, содержащее как можно меньше каталогов
В файловой системе допускаются каталоги, не содержащие файлов, каталоги, не содержащие дочерних каталогов, а также пустые каталоги. Каталоги должны иметь названия FOLDER_1, FOLDER_2, ... , FOLDER_M.
Каждый из файлов, подготовленных Альбертом, должен быть размещён в построенном дереве каталогов ровно один раз.
В случае, если удовлетворяющих условию деревьев несколько, выведите любое.
На вход программе подаётся одно целое число \(N\) (1 <= \(N\) <= \(10^5\)).
В первой строке выведите через пробел два числа: расстояние до самого далёкого файла и минимальное количество каталогов M, которое необходимо создать, чтобы добиться такого ответа.
В следующей строке выведите содержимое каталога tmp, а в следующих M строках выведите содержимое каталогов FOLDER_1, FOLDER_2, ... , FOLDER_M соответственно. Содержимое каталога выводится в следующем формате: сперва выводится общее число файлов и подкаталогов, содержащихся непосредственно в данном каталоге, а затем список файлов и папок в том порядке, в котором они располагаются в каталоге. В этом списке файл под номером K обозначается FILE_K, а папка под номером \(K\) обозначается FOLDER_K. Символ «..» выводить не требуется.
Для лучшего понимания формата вывода рекомендуется изучить примеры.
3
3 0 3 FILE_1 FILE_2 FILE_3
5
4 1 4 FOLDER_1 FILE_1 FILE_2 FILE_3 2 FILE_4 FILE_5
В далёкой-далёкой галактике силы Сопротивления продолжают войну против императора Палпатина. Повстанцы наконец-то одержали свою первую победу над силами Империи и захватили чертежи новейшей боевой станции "— Звезды смерти. Теперь перед повстанцами стоит непростая задача: нужно любой ценой уничтожить станцию, иначе Империя с её помощью укрепит свои позиции в галактике, и дни Сопротивления будут сочтены.
Уничтожение Звезды смерти, как и любая другая амбициозная задача, проходит этап компьютерного моделирования. По текущему плану, для уничтожения станции будет построен мощный ракетный крейсер, который станет флагманом сил Сопротивления и вступит в бой со Звездой смерти, пока остальной флот будет отвлекать внимание противника. Новый корабль будет стрелять ракетами мощностью A единиц и обладать щитами с энергией, достаточной для поглощения B единиц урона. Звезда смерти, в свою очередь, не может использовать в ближнем бою турболазер, способный уничтожать целые планеты, поэтому с неё будет вестись ответный огонь импульсами мощностью C единиц. Щиты Звезды смерти обладают энергией, достаточной для поглощения D единиц урона.
Вам поручено написать программу, моделирующую сражение крейсера мятежников с боевой станцией. Бой происходит поэтапно. На каждом этапе Звезда смерти и флагман одновременно наносят друг по другу удар. Каждый залп уменьшает энергию щита на величину, равную мощности выстрела неприятеля. Как только энергия щитов любого из противников перестает быть положительной, он терпит поражение.
Определите, удастся ли кому-либо одолеть своего врага, или же бой завершится уничтожением обеих сторон.
В первой и второй строках записаны два целых числа A и B ( 1 ≤ A , B ≤ 1 000 ) "— соответственно огневая мощь и энергия щитов флагмана флота Сопротивления.
В третьей и четвертой строках записаны два целых числа C и D ( 1 ≤ C , D ≤ 1 000 ) "— соответственно огневая мощь и энергия щитов Звезды смерти.
Если Сопротивление одержит победу, взорвав Звезду смерти на каком-то этапе, и сохранит свой флагман, выведите « WIN ».
Если флагман взорвётся, а станция уцелеет, выведите « LOSE ».
В случае, если противники уничтожат друг друга на одном и том же шаге боя, выведите « DRAW ».
3 5 1 11
WIN
4 10 5 9
LOSE
1 5 2 3
DRAW
Анализируя результаты командной олимпиады прошлого года, жюри решило помимо лиг А и В организовать ещё и лигу С. На стадии распределения задач по лигам каждая отобранная задача была помечена соответствующим набором букв: А , В , С , АВ , ВС или АВС .
Для подготовки олимпиады требуется составить единый список задач. Жюри хочет, чтобы задачи для одной лиги шли в списке подряд. Помогите жюри упорядочить задачи требуемым образом или определите, что это невозможно.
В первой строке ввода находится число N ( 3 ≤ N ≤ 32 ) "— количество задач, отобранных для олимпиады.
В каждой из следующих N строк содержится описание задачи, начинающееся с одной из пометок А , В , С , АВ , ВС или АВС , записанной заглавными латинскими буквами, за которой через пробел следует название задачи. Название задачи "— одно слово, состоящее из строчных или прописных латинских букв. Все названия задач являются различными. Длина каждой строки не превосходит 255 символов.
Выведите описания задач в требуемом порядке в том же формате, что и во входных данных. Все задачи, в пометку которых входит буква А , должны идти подряд, то же касается задач, пометка которых содержит букву В , и задач, пометка которых содержит букву С . Задачи, имеющие одинаковые пометки, могут идти в любом порядке.
В случае, если добиться требуемого невозможно, выведите в единственной строке слово Impossible .
5 C Tetris B DOOM A WOW C LINES AB CS
A WOW AB CS B DOOM C Tetris C LINES
4 A a B b C c ABC Abc
Impossible
Мэр уездного города
заботится о жителях и прислушивается к их мнению, поэтому он ежегодно даёт поручение социологической комиссии провести опрос общественного мнения. Участникам опроса предлагается
M
вопросов,
i
-й из которых содержит целое положительное количество вариантов ответа
a
i
. Жители города крайне серьёзно относятся к данному опросу, поэтому заполняют анкету добросовестно: каждый участник опроса выбирает ровно один вариант ответа в каждом вопросе.
При обработке результатов по каждому вопросу для каждого из доступных ответов считается процент людей, отдавших ему предпочтение. К большой радости сотрудников комиссии, обрабатывающих результаты опроса, в этом году все полученные числа выражаются целым количеством процентов.
В целях соблюдения конфиденциальности и анонимности все данные с бумажных анкет были занесены в электронную базу, а листы уничтожены. Но, по закону подлости, в ночь перед презентацией результатов исследования испортился жёсткий диск компьютера, на котором они хранились в единственном экземпляре. Более того, вместе с результатами был утрачен даже список вопросов и вариантов ответов на них! Единственной сохранившейся информацией являются пометки на полях тетради, сделанные во время подсчётов результатов секретаршей Жанной. После обработки каждого варианта она записывала процент людей, выбравших его, в совершенно произвольное место своей тетради ровно один раз.
Долгий и кропотливый процесс восстановления результатов предполагается начать с определения количества вопросов в исходном тестировании. Эта задача поручена вам.
В первой строке находится одно целое число K ( 1 ≤ K ≤ 100 ) "— количество чисел, записанных Жанной на полях тетради, совпадающее с суммарным количеством вариантов ответа на все вопросы.
Во второй строке записаны K неотрицательных целых чисел от 0 до 100, разделённых пробелами, каждое из которых обозначает процент жителей, проголосовавших за какой-то вариант ответа на какой-то вопрос.
Выведите единственное число M "— количество вопросов в социологическом опросе. Гарантируется, что существует ответ, удовлетворяющий записям из тетради Жанны. Если определить количество вопросов однозначно не удаётся, выведите любое подходящее значение.
В приведённом примере существует единственный способ получить подходящее разбиение: первое и третье число представляют ответы на один вопрос, а второе и четвёртое "— на другой.
4 25 50 75 50
2
Тем не менее Фёдору повезло: после прохождения многочисленных инстанций он всё-таки нашел место для нового дома. Более того, щедрое правительство даже подарило ему невероятно красивую крышу для постройки.
Важным обстоятельством является то, что Федя — совершенно плоский, как и весь мир, который его окружает. В этом плоском мире введена стандартная декартова система координат: ось \(O_x\) совпадает с землёй, а ось \(O_y\) направлена от земли вверх. Крыша представляет собой два отрезка, исходящих из одной точки (вершины крыши) вниз в разные стороны, причём оба отрезка составляют угол 45 градусов с осью \(O_x\):.
Разумеется, крыша находится над землёй, то есть отрезки находятся в верхней полуплоскости. Оба отрезка имеют ненулевую длину. Дом Феди должен представлять собой прямоугольник со сторонами, параллельными осям координат, одна сторона которого находится на земле, а другая сторона упирается в оба отрезка крыши. Дом не должен выходить за пределы крыши по горизонтали. Помогите Феде построить для себя дом наибольшей площади.
В первой строке содержатся два целых числа \(x_c\) и \(y_c\) — координаты вершины крыши (|\(x_c\)| <= \(10^4\), 1 <= \(y_c\) <= \(10^4\)).
Во второй строке содержатся два целых числа \(x_1\) и \(y_1\) — координаты одного из концов крыши (|\(x_1\)| <= \(10^4\), \(x_1\) ̸= \(x_c\), 0 <= \(y_1\) < \(y_c\)). В следующей строке в таком же формате заданы координаты \(x_2\) и \(y_2\) другого конца крыши.
Гарантируется, что отрезки, образующие крышу, направлены в разные стороны относительно верхней точки крыши, т. е. либо \(x_1\) < \(x_c\) < \(x_2\), либо \(x_2\) < \(x_c\) < \(x_1\), оба отрезка имеют одинаковую длину и составляют угол 45 градусов с осью \(O_x\).
Выведите единственное число — искомую максимальную площадь дома. Ваш ответ будет считаться правильным, если его абсолютная или относительная ошибка не будет превосходить 10-6
А именно, пусть ваш ответ равен \(A\), а ответ жюри — \(B\). Проверяющая программа будет считать ваш ответ правильным, если |\(A\)-\(B\)| / max(\(1\); \(B\)) <= 10-6.
10 10 5 5 15 5
50.0