АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Примеры входа и выхода. Задача 1. «Кабели» (минимальное покрывающее дерево)

Читайте также:
  1. ALSt Состояние выхода сигнала АПС. CLOS или ОРЕn.
  2. II. Примеры, подтверждающие милость, явленную в Пророке, да благословит его Аллах и да приветствует.
  3. MS Excel.Текстовые функции, примеры использования текстовых функций.
  4. SCADA. Назначение. Возможности. Примеры применения в АСУТП. Основные пакеты.
  5. Активация точек входа и выхода энергетических нитей
  6. Аэропорт Москвы, у выхода для экипажа. Они идут
  7. Б) длительность одного полного кругооборота средств с момента их превращения из денежной формы в производственные запасы и до выхода готовой продукции и ее реализации
  8. БОЕВЫЕ ПРИМЕРЫ
  9. В поисках выхода: ответ на угрозы, связанные с нестабильностью сырьевых цен
  10. В ЧЛЕНЫ ТОВАРИЩЕСТВА И ВЫХОДА ИЗ НЕГО
  11. В. Примеры случайных процессов
  12. Взаимно исключающие связи в ER-модели. Примеры. Отображение диаграммы со взаимно исключающими связями в реляционную схему.

Задача 1. «Кабели» (минимальное покрывающее дерево)

Входной файл: cables.in

Выходной файл: cables.out

Ограничение времени: 1 секунда

Ограничение памяти: 64M байт

 

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

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

Вход

В первой строке входного файла записан диаметр планеты D (1 ≤ D ≤ 1,000,000). Во второй строке записана длина имеющегося на планете кабеля L (1 ≤ L ≤ 1,000,000). В третьей строке записано количество поселений на планете C (1 ≤ C ≤ 100). В остальных C строках записаны координаты городов в формате " X Y ", где X – широта в градусах (-90 ≤ X ≤ 90), Y – долгота в градусах (-180 ≤ Y ≤ 180).

Выход

 

Запишите в выходной файл " IS POSSIBLE ", если можно создать планетарную компьютерную сеть, либо " IS NOT POSSIBLE " в противном случае.

 

Примеры входа и выхода

cables.in cables.out
51.3 0 42.5 -75 48.8 3 IS POSSIBLE
30.266 97.75 30.45 91.1333 IS NOT POSSIBLE

Задача 2. «Магическая дорога» (минимальное покрывающее дерево)

Входной файл: magicroad.in

Выходной файл: magicroad.out

Ограничение времени: 1 секунда на тест

Ограничение памяти: 64 М байт

 

Однажды император Флатландии решил наладить, наконец, в империи дорожную сеть. Он приказал построить ровно N -1 дорогу (а в Флатландии, как известно, ровно N городов) так, чтобы из любого города в любой можно было проехать по дороге. Понятно, что при этом суммарная длина дорог должна быть минимальна. Однако придворный маг предложил построить одну из дорог с помощью магии. Магическая дорога любой длины строится мгновенно и добавляет счастья жителям двух городов, которые она связывает. Поэтому магу безразлична длина дороги, но он настаивает, чтобы суммарное население городов, связанных магической дорогой, было максимально возможным. После длительных переговоров император и маг пришли к компромиссу. Они согласились, чтобы отношение S / L, где S – суммарное население городов, связанных магической дорогой, L – суммарная длина остальных N -2 дорог, было максимально возможным. Напишите программу, которая составляет план оптимальной дорожной сети.

Вход

В первой строке входного файла записано целое число N - количество городов (3 ≤ N ≤ 1000). В остальных строках содержатся N троек целых чисел X, Y – координаты города и P – население города (0 ≤ X, Y ≤ 1000, 0 < P ≤ 100000).

Выход

Запишите в выходной файл максимальное отношение S / L с двумя дробными цифрами.

Примеры входа и выхода

magicroad.in magicroad.out
41 1 201 2 30200 2 80 200 1 100 65.00  
31 1 201 2 30 2 2 40 70.00  

 


1 | 2 | 3 | 4 | 5 |

Поиск по сайту:

Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.003 сек.)