Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 
[Вернуться к задаче]   1
  1  Черкасов Даниил Аркадьевич, 20 июня 2016 г. 19:20:20
     эмм... вы не подумавшись, а не обязательно же к первому поросёнку тащить? можно выщитать минимум!
  2  Федотов Богдан Сергеевич, 07 июня 2016 г. 14:51:27
     Спасибо Моисееву Борису Дмитриевичу. Действительно, стоит добавить в условие задачи замечание, что можно покупать провод дробной длины.
  3  Егоров Андрей, 06 апреля 2016 г. 0:39:35
     не понимаю, почему проходит только при "double p;" ,по условию же целое число
  4  Денис Розимовски, 24 августа 2014 г. 12:08:37
     А того одного поросенка нужно соединить с точкой подключения.
  5  Денис Розимовски, 24 августа 2014 г. 12:07:49
     Думал сначала решать через минимальный остов и дейкстры всякие. Но тут нужна именно сеть с топологией "Звезда"
То бишь нужно выбрать такого одного поросенка, чтобы от него ПРЯМЫМ ПРОВОДОМ соединить всех остальных. Задача легкая. Решил под конец перебором, хоть и замучился с этими остовами
  6  Меньшиков Фёдор Владимирович, 21 октября 2013 г. 17:30:48
     Добавьте пожалуйста тесты
6 1 1307
102 0
199 100
199 -100
-100 0
-200 200
-200 -200
0 0
и
6 1 1308
102 0
199 100
199 -100
-100 0
-200 200
-200 -200
0 0
они заваливают проходящую через текущие тесты эвристику, когда выбирается точка ближайшая к центру тяжести.
  7  Бондарчук Юрий Павлович, 07 августа 2013 г. 14:36:25
     O(N^2) на ура...
всего 10^6 операций в худшем случае...пишите и не парьтесь
  8  Гришин Евгений Сергеевич, 07 октября 2012 г. 21:27:10
     А можно добавить один тест - у меня код даёт по нему не правильный ответ, но здесь тесты все проходит, задача сдается.

3 1 11
0 0
6 0
4 2
0 0
  9  Моисеев Борис Дмитриевич, 18 января 2012 г. 2:45:46
     На мой взгляд, совершенно не очевидно, что 2,5 метра провода по цене 2 тугрика/метр будут стоит 5 тугриков. Привычно, что провод продаётся дискретно кратно метрам.
  10  Балакший Андрей Владимирович, 30 апреля 2011 г. 15:44:17
     Хм. Убрал эпсилон - прошло....
  11  Гамисония <Censored> Эльдар, 22 ноября 2010 г. 12:48:10
     сократил формулу просто и прошло=)
  12  Гамисония <Censored> Эльдар, 21 ноября 2010 г. 20:18:41
     почему N^2 не проходит?
     проходит, постарайтесь оптимизировать программу. попробуйте подключить библиотеки SysUtils и Math.
  13  Ситдыкова, 21 января 2008 г. 12:35:59
     Здраствуйте, у меня задчка компилируется, а у вас нет, с чем бы это могло быть связано?
     Вы эту ошибку можете видеть самостоятельно, нажав на номер сдачи задачи в разделе "Состояние системы", залогинившись под собой. Под текстом вашей программы увидите ошибку (она пишется красным цветом).
  14  Moonfall, 11 июля 2007 г. 11:28:58
     Вы уж извините, но честно говоря не совсем понятно - если провод идет напрямую и при этом до первого поросенка не считается, то для второго примера получаем неправильный ответ, так как (xnet, ynet) = (4,4) , близжайшая точка подключения (поросенок) (3,3) (до нее мы не считаем), а дальше до второго поросенка получаем расстояние корень из 2 (его координаты (2, 2) - если по прямой и до первого с координатами (1, 1) так же получаем корень из 2 то есть где-то 1,4 + 1, 4 то есть 2,8 - при стоимости 1 тубрик и имеющихся у поросятах 5 должно хватить. Ответ получается верный только если считать подключение по сетке (+1 по x и +1 по y) и так же считать подкючение до первого поросенка, тогда мы получим (1+1)+(1+1)+(1+1) и *1 = 6 тубриков, что на 1 меньше чем есть у поросят. Объясните, пожалуйста.
     Вы хоть и неправильно все подсчитали, но у вас все равно получилось, что во втором тесте денег поросятам не хватило (6>5, у поросят там 5 тугриков), почему же вы считаете что ответ неправильный? Ведь там написано NO, это как раз соответствует тому, что у поросят денег не хватит. На самом деле оптимальная стоимость там получается 4*sqrt(2), что больше чем 5, но меньше чем 6.
  15  Kaliostro, 09 июля 2007 г. 10:16:32
     тоесть от всех поросят провод должен идти именно к первому? или к любому другому подключенному? И от провайдера только к одному поросенку или можно к нескольким в целях экономии..?
     По-моему я уже достаточно однозначно сказал, да и задача довольно однозначно сформулирована. Сколько раз еще отвечать "да"? От всех поросят именно к первому, подключенному к провайдеру (на всякий случай уточню, что кроме самого его, т.е от подключенного к провайдеру провод к самому к нему не идет, хотя можете считать, что идет с нулевой длиной).
  16  Нарат Алексей Геннадиевич, 07 июля 2007 г. 14:50:40
     Вопрос первый: можно ли двух поросят соединять прямым куском провода, или провод обязательно должен идти вдоль линий сетки?
Вопрос второй: полученная сеть должна иметь топологию "Звезда", т. е. все свинки должны быть подключены напрямую к счастливцу (первому подключенному поросенку), или же сеть может иметь произвольный вид?
     1) нужно прямым проводом соединять, нет никакой сетки 2) топология именно "звезда" получается, ведь очевидно, что если это не так, то суммарная длина станет больше (или же прийдется платить больше)
 1

Чтобы оставить сообщение необходимо зарегистрироваться и авторизоваться!

Красноярский краевой Дворец пионеров, (c)2006 - 2018, ICQ: 151483, E-mail: admin@acmp.ru