Страница: 1 2 >> Отображать по:
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

Cреди всех прямоугольных параллелепипедов с натуральными длинами сторон и площадью поверхности не более $n$ найти тот, объём которого максимален.

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

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

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

У Поликарпа в наличии есть лист клетчатой бумаги, состоящий из $n$ клеток. Каким будет максимальный объём коробки, которую можно оклеить с использованием этого листа бумаги описанным выше способом? Поликарп может разрезать лист клетчатой бумаги по границам клеток произвольным образом и оклеивать коробку получившимися фигурами, поэтому форма листа не важна, а имеет значение только количество клеток на нём. Поликарп может использовать для оклеивания коробки не все клетки.

Напишите программу, которая по заданному количеству клеток $n$ находит размеры коробки максимального возможного объема.

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

Входной файл содержит одно целое число $n$ ($6\le n\le10^{13}$) — количество клеток на листе клетчатой бумаги.

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

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

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

Система оценивания

Решения, корректно работающие при $n\le5\,000$, будут оцениваться из 30 баллов, а решения, корректно работающие при $n\le10^8$, будут оцениваться из 70 баллов.

Примеры
Входные данные
6
Выходные данные
1
1 1 1
Входные данные
24
Выходные данные
8
2 2 2
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

Задано множество из $n$ станций и $m$ трубопроводов, соединяющих некоторые пары станций. Требуется выбрать множество из $k$ станций, чтобы один из двух концов каждого трубопровода лежал в выбранном множестве. Если построить граф, в котором станции будут служить вершинами, а трубопроводы — рёбрами, то искомое множество будет являться вершинным покрытием в этом графе.

Ханты-Мансийский автономный округ — Югра является важнейшим нефтяным регионом России. Добыча нефти составляет 267 млн т в год, её транспортировка осуществляется по трубопроводам, общая длина которых превышает длину экватора Земли.

Система транспортировки нефти представляет собой совокупность $n$ распределительных станций и $m$ трубопроводов. Каждый трубопровод соединяет две различные станции. Между любыми двумя станциями проложено не более одного трубопровода.

Эффективность работы станций существенно зависит от вязкости нефти. Поэтому компания «ЮграНефтеТранс», в ведении которой находится сеть трубопроводов, заказала инновационному исследовательскому предприятию разработку и изготовление новых сверхточных датчиков вязкости на основе самых современных технологий.

Изготовление датчиков — процесс трудоёмкий и дорогостоящий, поэтому было решено изготовить $k$ датчиков ($k\le40$) и выбрать $k$ различных станций, на которых датчики будут установлены. Необходимо осуществить выбор станций так, чтобы датчики контролировали все трубопроводы: для каждого трубопровода хотя бы один датчик должен быть установлен на станции, где начинается или заканчивается этот трубопровод.

Напишите программу, которая проверяет, существует ли требуемое расположение датчиков, и в случае положительного ответа находит это расположение.

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

В первой строке входного файла записаны три натуральных числа — $n$, $m$ и $k$ ($k\le n\le2000$, $1\le m\le10^5$, $1\le k\le40$). Далее следуют $m$ строк, каждая из которых описывает один трубопровод. Трубопровод задаётся двумя целыми числами — порядковыми номерами станций, которые он соединяет. Станции пронумерованы от 1 до $n$. Гарантируется, что к любой станции подведён хотя бы один трубопровод и между любыми двумя станциями проложено не более одного трубопровода. Числа в каждой строке разделены пробелами.

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

В первую строку выходного файла выведите слово «Yes», если требуемое расположение датчиков существует, в противном случае — слово «No». В случае положительного ответа выведите во вторую строку выходного файла $k$ различных целых чисел — номера станций, на которых необходимо установить датчики. Номера можно выводить в любом порядке. Если существует несколько подходящих расположений датчиков, выведите любое из них. Разделяйте числа во второй строке пробелами.

Система оценивания

Решения, корректно работающие при $n\le100$ и $k\le10$, будут оцениваться из 60 баллов.

Примеры
Входные данные
9 12 4
1 2
2 3
1 4
4 5
1 6
6 7
1 8
8 9
2 5
4 7
6 9
8 3
Выходные данные
Yes
2 4 6 8 
Входные данные
8 12 4
7 4
7 5
3 1
2 8
4 3
3 2
6 1
1 2
1 4
6 5
8 6
8 7
Выходные данные
No
Входные данные
4 3 1
3 1
3 2
3 4
Выходные данные
Yes
3 
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

Есть $n$ человек, которые хотят улететь из Москвы в Ханты-Мансийск. Каждый день летает один самолёт вместимостью $k$ человек. У каждого человека есть множество дней, когда он может улететь, — отрезок $[a_i,b_i]$. Нужно придумать такое распределение людей по самолётам, что до Ханты-Мансийска долетит максимальное число людей. Среди людей есть участники РОИ, которых нужно перевезти обязательно (остальных людей будем называть обычными).

В связи с проведением в Ханты-Мансийске Всероссийской олимпиады школьников по информатике агентство авиаперевозок обязано перевезти самолётами всех участников олимпиады. Всего за $m$ дней, пронумерованных от 1 до $m$, из Москвы в Ханты-Мансийск хотят вылететь $n$ пассажиров, в том числе и участники олимпиады.

Все желающие вылететь в Ханты-Мансийск заполнили анкеты, в которых указали информацию о возможных днях вылета и об участии в олимпиаде. Информация о возможных днях вылета $i$-го пассажира указана в виде пары чисел $(a_i, b_i)$. Это означает, что пассажир согласен вылететь в любой день, начиная с $a_i$ и по $b_i$ включительно, и не может вылететь в другие дни.

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

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

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

В первой строке входного файла записаны три натуральных числа — $n$, $m$ и $k$ ($1\le n\le100\,000$, $1\le m\le100\,000$, $1\le k\le100\,000$). Далее следуют $n$ строк, $i$-я из которых содержит результаты заполнения анкеты пассажиром с порядковым номером $i$ в виде трёх целых чисел, первые два из которых — самый ранний и самый поздний дни вылета $a_i$ и $b_i$ ($1\le a_i\le b_i\le m$), а последнее число равно 0, если пассажир не является участником Всероссийской олимпиады, и равно 1, если является. Гарантируется, что хотя бы один пассажир является участником Всероссийской олимпиады. Числа в каждой строке разделены пробелами.

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

В первой строке выходного файла выведите максимальное количество пассажиров $l$, которых можно перевезти из Москвы в Ханты-Мансийск. Если невозможно выполнить поставленную задачу, то в первой строке необходимо вывести число 0. В случае положительного ответа выведите во второй строке n чисел, а именно, для каждого пассажира выведите номер дня, в который запланирован его вылет, либо 0, если этому пассажиру не нашлось места в оптимальном распределении. Числа во второй строке разделяйте пробелами. Если оптимальных распределений несколько, выведите любое из них.

Система оценивания

  • Решения, корректно работающие при $n$, $m$ и $k$, не превышающих 10, будут оцениваться из 20 баллов.
  • Решения, корректно работающие при $n$, $m$ и $k$, не превышающих 100, будут оцениваться из 40 баллов.
  • Решения, корректно работающие при $n$, $m$ и $k$, не превышающих 1 000, будут оцениваться из 60 баллов.
  • Решения, корректно работающие при $n$, $m$ и $k$, не превышающих 10 000, будут оцениваться из 80 баллов.

  • Примеры
    Входные данные
    3 2 1
    1 2 1
    1 2 0
    1 2 1
    
    Выходные данные
    2
    1 0 2 
    
    Входные данные
    3 4 1
    1 2 1
    1 3 1
    1 4 0
    
    Выходные данные
    3
    1 2 3 
    
    Входные данные
    10 4 2
    2 3 0
    2 3 0
    1 3 1
    3 4 0
    3 4 1
    2 3 0
    2 2 0
    1 3 1
    4 4 0
    2 4 0
    
    Выходные данные
    8
    2 3 1 4 4 3 2 1 0 0 
    
    ограничение по времени на тест
    2.0 second;
    ограничение по памяти на тест
    256 megabytes

    В 2050 году руководство Глобальной Телефонной Сети (ГТС) приняло решение о новой системе тарификации коротких текстовых сообщений. Теперь цена отправки одного сообщения зависит от количества совпадающих цифр в начале номеров телефонов отправителя и получателя. Если первые $c$ цифр телефонов совпадают, а $(c+1)$-я цифра различается, то стоимость сообщения составляет $(10-c)$ кредитов ($0\le c\le9$). Все номера телефонов — десятизначные. При этом ГТС разрешает каждому абоненту отправлять сообщение только в пределах часового пояса своего проживания или часовых поясов, отличающихся от него на 1 час.

    Школьник Поликарп из Ханты-Мансийска (время +2 часа от московского) успешно решил все задания первого тура олимпиады школьников по информатике. Теперь он желает сообщить об этом в Париж (время −2 часа от московского) своему учителю — профессору де Коде́ру. Так как Ханты-Мансийск и Париж находятся не в соседних часовых поясах, Поликарп не может послать сообщение напрямую. Поэтому он пользуется тем, что у него есть друзья, которые проживают в Ханты-Мансийске, Париже, а также в промежуточных часовых поясах — в Дубае (время +1 час от московского), Москве и Калининграде (время −1 час от московского). Друзья Поликарпа по цепочке доставят профессору де Коде́ру столь важную информацию. Поликарп хочет организовать передачу информации таким образом, чтобы минимизировать суммарные расходы по отправке всех сообщений.

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

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

    Первые две строки входного файла содержат телефонные номера Поликарпа и профессора де Коде́ра. Далее следуют 5 блоков данных, описывающих друзей Поликарпа, живущих в Ханты-Мансийске, Дубае, Москве, Калининграде и Париже, соответственно. Каждый блок начинается со строки, содержащей одно число $n_i$ ($1\le n_i\le100\,000$) — количество друзей Поликарпа в соответствующем городе, после которой следуют $n_i$ строк — номера телефонов друзей. Все номера телефонов состоят ровно из 10 цифр. Гарантируется, что сумма всех $n_i$ не превосходит 100 000. Все номера телефонов во входных данных различны.

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

    В первой строке выходного файла выведите минимальную возможную стоимость передачи информации $w$ и количество задействованных в цепочке телефонных номеров $k$. Далее выведите $k$ номеров телефонов, описывающих саму цепочку, в порядке следования от Поликарпа к профессору де Коде́ру. Первый номер в цепочке должен совпадать с номером телефона Поликарпа, а последний — с номером телефона профессора де Коде́ра. Если решений несколько, выведите любое.

    Система оценивания

  • Решения, корректно работающие при сумме $n_i$, не превосходящей 500, будут оцениваться из 40 баллов.
  • Решения, корректно работающие при сумме $n_i$, не превосходящей 5 000, будут оцениваться из 60 баллов.

  • Примеры
    Входные данные
    2099013166
    7043239909
    1
    0258442145
    1
    0000000000
    1
    0000000001
    1
    0000000002
    1
    0147571204
    
    Выходные данные
    22 5
    2099013166
    0000000000
    0000000001
    0000000002
    7043239909
    
    Входные данные
    4261802325
    7967612531
    1
    8176476745
    1
    3084033164
    1
    1737248630
    1
    9447552231
    1
    2848478213
    
    Выходные данные
    40 5
    4261802325
    3084033164
    1737248630
    9447552231
    7967612531
    
    ограничение по времени на тест
    2.0 second;
    ограничение по памяти на тест
    256 megabytes

    Вы уже знаете, сколько нефти добывается в Ханты-Мансийском автономном округе. Другой хозяйственной отраслью Югры является оленеводство. Нередко можно увидеть, как на нефтяной площадке, окружённой изгородью, работают нефтяники, а вокруг изгороди пасутся олени.

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

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

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

    В первой строке входного файла записано целое число $n$ — количество углов изгороди ($3\le n\le100$). В последующих $n$ строках записаны координаты углов изгороди в порядке обхода по часовой стрелке. В последней строке записаны три числа — координаты точки привязывания оленя к изгороди и длина верёвки. Все координаты целые и не превосходят по модулю $10^4$. Длина верёвки — целое положительное число, не превосходящее $10^4$. Числа в каждой строке разделены пробелами. Гарантируется, что изгородь представляет собой строго выпуклый многоугольник и точка привязывания оленя лежит на его границе.

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

    В выходной файл выведите значение площади с точностью не менее $10^{-3}$.

    Система оценивания

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

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

    Примеры
    Входные данные
    4
    -5 -5
    -5 5
    5 5
    5 -5
    5 0 4
    
    Выходные данные
    25.1327412287
    
    Входные данные
    4
    0 0
    0 2
    4 2
    4 0
    2 0 4
    
    Выходные данные
    31.4159265359
    

    Страница: 1 2 >> Отображать по:
    Выбрано
    :
    Отменить
    |
    Добавить в контест