|
3 / 3 / 0
Регистрация: 25.06.2020
Сообщений: 11
|
|
Разделение королевства25.06.2020, 13:22. Показов 29673. Ответов 27
Метки python 3.7 (Все метки)
Разделение королевства
Королевство Флатландия имеет вид бесконечной двумерной плоскости. В королевстве находятся n замков. Для более удобного составления карт в Флатландии была введена Декартова система координат. Известно, что i-й замок находится в точке с координатами (xi+0.5, yi+0.5), где xi, yi — целые числа. Местоположения всех замков попарно различны. На старости лет король решил разделить на карте королевство между своими сыновьями прямыми, параллельными осям координат. Если прямая параллельна оси Ox, то y координата у всех точек на прямой должна быть целым числом, иначе x координата у всех точек должна быть целым числом. В обоих случаях соответствующие целые координаты по модулю не должны превышать 2⋅109. При этом Его величество хочет, что бы после разделения королевства любые два замка оказались бы в различных частях. Помогите королю разделить королевство, используя не более чем n−1 прямых. У любой пары прямых должно быть не более одной общей точки. Входные данные В первой строке задано целое число n (1≤n≤100000) — количество замков в королевстве. В следующих n строках записано по два числа xi и yi (−109≤xi≤109, −109≤yi≤109) — целые части координат замков. Выходные данные В первой строке выходного файла выведите количество используемых прямых. В следующих строчках выведите сами прямые, по одной в каждой строке. Если прямая параллельна оси Ox, то выведите символ "y", а затем через пробел y координату всех точек на этой прямой, иначе выведите символ "x", а затем через пробел x координату всех точек на этой прямой. Примеры Ввод Вывод 4 0 2 0 3 1 2 1 3 2 y 3 x 1
0
|
|
| 25.06.2020, 13:22 | |
|
Ответы с готовыми решениями:
27
Разделение королевства Разделение Королевства |
|
3 / 3 / 0
Регистрация: 25.06.2020
Сообщений: 11
|
|
| 25.06.2020, 14:05 [ТС] | |
|
Вот примерный порядок решения, но я не знаю как его реализовать:
1.Отсортируем замки по координате x, между каждой парой соседних замков проведем прямую 2.Посмотрим на замки, которые имеют одинаковую координату x. Для каждого такого замка отсортируем по y. Проведем прямую между соседними замками
1
|
|
|
3 / 3 / 0
Регистрация: 25.06.2020
Сообщений: 11
|
|
| 25.06.2020, 16:44 [ТС] | |
|
А как делать дальше?
1
|
|
|
3 / 3 / 0
Регистрация: 25.06.2020
Сообщений: 11
|
||||||
| 25.06.2020, 18:17 [ТС] | ||||||
|
Программа работает нормально, но не проходит по времени:
Уже решил
0
|
||||||
|
0 / 0 / 0
Регистрация: 26.06.2020
Сообщений: 1
|
|
| 26.06.2020, 18:32 | |
|
Ну что зашла задача?
0
|
|
|
1 / 1 / 0
Регистрация: 26.06.2020
Сообщений: 30
|
|
| 26.06.2020, 19:11 | |
|
Можешь код отправить, пожалуйста
0
|
|
|
25 / 14 / 2
Регистрация: 28.06.2020
Сообщений: 50
|
|
| 28.06.2020, 01:38 | |
|
Код данный ранее работает, просто там ведется лишний список b, который и замедляет программу.
1
|
|
|
1 / 1 / 0
Регистрация: 26.06.2020
Сообщений: 30
|
|
| 28.06.2020, 12:59 | |
|
Я убирал список b, все равно медленно
Добавлено через 12 минут Все, решил
0
|
|
|
8 / 7 / 1
Регистрация: 15.05.2020
Сообщений: 10
|
|
| 30.06.2020, 15:25 | |
|
Я тоже убрал список, но все равно медленно работает, что нужно еще сделать?
0
|
|
|
11 / 15 / 1
Регистрация: 13.05.2020
Сообщений: 49
|
||||||
| 30.06.2020, 19:34 | ||||||
2
|
||||||
|
6 / 5 / 1
Регистрация: 25.05.2020
Сообщений: 17
|
|
| 30.06.2020, 22:55 | |
|
По времени не пройдёт
0
|
|
|
11 / 15 / 1
Регистрация: 13.05.2020
Сообщений: 49
|
|
| 01.07.2020, 09:34 | |
|
AndreyNill, У меня прошло.
ниже скрины.
1
|
|
|
1 / 1 / 0
Регистрация: 07.03.2020
Сообщений: 15
|
|
| 10.07.2020, 11:46 | |
|
Евгений, не проходит по времени, я проверил.
Добавлено через 9 минут Я не понимаю как и почему, но можно добавить пробел в конец кода и тогда заработает. Я не знаю как, но у меня зачиталось. Приношу извинения за то, что сказал неправду в сообщении выше.
0
|
|
|
2 / 2 / 0
Регистрация: 11.07.2021
Сообщений: 2
|
|
| 11.07.2021, 23:52 | |
|
AndreyNill, у меня тоже в сириусе ,по времени не проходит.
.
2
|
|
|
0 / 0 / 0
Регистрация: 27.07.2021
Сообщений: 1
|
|
| 29.07.2021, 11:45 | |
|
у меня ничего не получается(((((( на всех попытках -- сваливается на времени
0
|
|
|
1 / 1 / 0
Регистрация: 11.10.2020
Сообщений: 2
|
|
| 18.08.2021, 12:53 | |
|
Актуально
0
|
|
|
8851 / 4502 / 1864
Регистрация: 27.03.2020
Сообщений: 7,317
|
||||||
| 18.08.2021, 16:16 | ||||||
|
Лол123, вроде так
0
|
||||||
|
5517 / 2870 / 571
Регистрация: 07.11.2019
Сообщений: 4,761
|
||||||
| 18.08.2021, 18:42 | ||||||
|
Gdez, вы думаете что нужна сортировка?
![]() Вариант:
1
|
||||||
|
8851 / 4502 / 1864
Регистрация: 27.03.2020
Сообщений: 7,317
|
||||||
| 18.08.2021, 19:18 | ||||||
|
u235, полтора года назад была нужна
- сириус...Верхний вариант (пробовал найти минимум прямых) не верен. А так
1
|
||||||
| 18.08.2021, 19:18 | |
|
Помогаю со студенческими работами здесь
20
Разделение королевства
Задание про 2 королевства Задача про раздел королевства Посчитать минимальные расходы королевства на подарок короля Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |
|
Новые блоги и статьи
|
|||
|
модель ЗдравоСохранения 8. Подготовка к разному выполнению заданий
anaschu 08.04.2026
https:/ / github. com/ shumilovas/ med2. git
main ветка * содержимое блока дэлэй из старой модели теперь внутри зайца новой модели
8ATzM_2aurI
|
Блокировка документа от изменений, если он открыт у другого пользователя
Maks 08.04.2026
Алгоритм из решения ниже реализован на примере нетипового документа, разработанного в конфигурации КА2.
Задача: запретить редактирование документа, если он открыт у другого пользователя.
/ / . . .
|
Система безопасности+живучести для сервера-слоя интернета (сети). Двойная привязка.
Hrethgir 08.04.2026
Далее были размышления о системе безопасности. Сообщения с наклонным текстом - мои.
А как нам будет можно проверить, что ссылка наша, а не подделана хулиганами, которая выбросит на другую ветку и. . .
|
Модель ЗдрввоСохранения 7: больше работников, больше ресурсов.
anaschu 08.04.2026
работников и заданий может быть сколько угодно, но настроено всё так, что используется пока что только 20%
kYBz3eJf3jQ
|
|
Дальние перспективы сервера - слоя сети с космологическим дизайном интефейса карты и логики.
Hrethgir 07.04.2026
Дальнейшее ближайшее планирование вывело к размышлениям над дальними перспективами. И вот тут может быть даже будут нужны оценки специалистов, так как в дальних перспективах всё может очень сильно. . .
|
Горе от ума
kumehtar 07.04.2026
Эта мне ментальная установка, что вот прямо сейчас, мол, мне для полного счастья не хватает (нужное вписать), и когда я этого достигну - тогда и полный кайф. Одна из самых сильных ловушек на пути. . . .
|
Использование значений реквизитов справочника в документе, с определенными условиями и правами
Maks 07.04.2026
1. Контроль срока действия договора
Алгоритм из решения ниже реализован на примере нетипового документа "ЗаявкаНаРаботу", разработанного в конфигурации КА2.
Задача: уведомлять пользователя, если. . .
|
Доступность команды формы по условию
Maks 07.04.2026
Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2.
Задача: сделать доступной кнопку (команда формы "ЗавершитьСписание") при. . .
|