✓ Решено Сложный Python для чайников.

Языки программирования, IDE, компиляторы, интерпретаторы
Правила форума
Правильно сформулированный вопрос и его грамотное оформление способствует высокой вероятности получения достаточно содержательного и по существу ответа.
Аватара пользователя
SemenSinchenko
Сообщения: 314
Зарегистрирован: 17 фев 2017, 09:01
Решено: 2
Откуда: Москва
Благодарил (а): 40 раз
Поблагодарили: 40 раз

Сложный Python для чайников.

Сообщение SemenSinchenko » 30 авг 2017, 08:10

Прохожу курс по теории алгоритмов. Там задача:
По данным n отрезкам необходимо найти множество точек минимального размера, для которого каждый из отрезков содержит хотя бы одну из точек.

В первой строке дано число 1≤n≤100
отрезков. Каждая из последующих n строк содержит по два числа 0≤l≤r≤109, задающих начало и конец отрезка. Выведите оптимальное число m точек и сами m точек. Если таких множеств точек несколько, выведите любое из них.


Тестируется через stdin → stdout

Сразу оговорюсь, прошу не комментировать само мое решение, мне важно чтобы алгоритмическую часть я решал самостоятельно, это все же обучение.
Мой код:
► Показать


Но система проверки ругается, говорит следующее:
► Показать


То есть решение по ходу то правильное, но неверный формат вывода! Подскажите, как нужно переформатировать вывод?

Решение SemenSinchenko » 30 авг 2017, 08:34
Итоговый вариант, который был принят:
► Показать


Всем спасибо! Очень помогли!
► Показать

Перейти к ответу ➙

Аватара пользователя
darkfenix
Сообщения: 323
Зарегистрирован: 27 июн 2017, 10:36
Решено: 3
Благодарил (а): 25 раз
Поблагодарили: 54 раза

Сложный Python для чайников.

Сообщение darkfenix » 30 авг 2017, 08:14

Ты пытаешь ей скормить массив m_coord,
SemenSinchenko писал(а):Источник цитаты sys.stdout.write(str([m, m_coord]))

Аватара пользователя
SemenSinchenko
Сообщения: 314
Зарегистрирован: 17 фев 2017, 09:01
Решено: 2
Откуда: Москва
Благодарил (а): 40 раз
Поблагодарили: 40 раз

Сложный Python для чайников.

Сообщение SemenSinchenko » 30 авг 2017, 08:15

darkfenix, Ну так задание говорит, что я должен вывести координаты точек:
Выведите оптимальное число m точек и сами m точек.
А координаты у меня в массиве хранятся

Аватара пользователя
Chocobo
Сообщения: 4581
Зарегистрирован: 27 авг 2016, 19:57
Решено: 108
Откуда: НН
Благодарил (а): 374 раза
Поблагодарили: 1227 раз

Сложный Python для чайников.

Сообщение Chocobo » 30 авг 2017, 08:22

sys.stdout.write(str(m) + '\n' + str(m_coord[0]))
Изображение

Аватара пользователя
SemenSinchenko
Сообщения: 314
Зарегистрирован: 17 фев 2017, 09:01
Решено: 2
Откуда: Москва
Благодарил (а): 40 раз
Поблагодарили: 40 раз

Сложный Python для чайников.

Сообщение SemenSinchenko » 30 авг 2017, 08:25

Chocobo, Теперь выводится только первая точка...
► Показать

Аватара пользователя
darkfenix
Сообщения: 323
Зарегистрирован: 27 июн 2017, 10:36
Решено: 3
Благодарил (а): 25 раз
Поблагодарили: 54 раза

Сложный Python для чайников.

Сообщение darkfenix » 30 авг 2017, 08:29

Код: Выделить всё

sys.stdout.write(str(m) + '\n')
цикл от 0 до длина(m_coord)
  sys.stdout.write(str(m_coord[i]))

Аватара пользователя
Chocobo
Сообщения: 4581
Зарегистрирован: 27 авг 2016, 19:57
Решено: 108
Откуда: НН
Благодарил (а): 374 раза
Поблагодарили: 1227 раз

Сложный Python для чайников.

Сообщение Chocobo » 30 авг 2017, 08:30

SemenSinchenko, Я не вникал в текст задачи, только аут подбил под корректный на заданных в первом посте числах числах :joke:
Сейчас гляну тогда и по коду
Изображение

Аватара пользователя
SemenSinchenko
Сообщения: 314
Зарегистрирован: 17 фев 2017, 09:01
Решено: 2
Откуда: Москва
Благодарил (а): 40 раз
Поблагодарили: 40 раз

Сложный Python для чайников.

Сообщение SemenSinchenko » 30 авг 2017, 08:32

darkfenix, как же сложно с этим stdout... Курс входит в программу "Анлиз данных", а не программирование...
Теперь пробела не хватает:
► Показать

Аватара пользователя
SemenSinchenko
Сообщения: 314
Зарегистрирован: 17 фев 2017, 09:01
Решено: 2
Откуда: Москва
Благодарил (а): 40 раз
Поблагодарили: 40 раз

Сложный Python для чайников.

Сообщение SemenSinchenko » 30 авг 2017, 08:34

Итоговый вариант, который был принят:
► Показать


Всем спасибо! Очень помогли!
► Показать

Аватара пользователя
darkfenix
Сообщения: 323
Зарегистрирован: 27 июн 2017, 10:36
Решено: 3
Благодарил (а): 25 раз
Поблагодарили: 54 раза

Сложный Python для чайников.

Сообщение darkfenix » 30 авг 2017, 08:37

SemenSinchenko, так и не давал готового решения. Только указал как нужно выводить данные из массива. А форматирование вывода это уж сами как-нибудь)))

Аватара пользователя
Chocobo
Сообщения: 4581
Зарегистрирован: 27 авг 2016, 19:57
Решено: 108
Откуда: НН
Благодарил (а): 374 раза
Поблагодарили: 1227 раз

Сложный Python для чайников.

Сообщение Chocobo » 30 авг 2017, 08:38

Ну раз ошибка ушла - давай и решение чуть разжуем чтоль :)

Тут stdin → stdout был прям в уловиях прописан?)
простой print туда же зашлет, по идее
Изображение

Аватара пользователя
SemenSinchenko
Сообщения: 314
Зарегистрирован: 17 фев 2017, 09:01
Решено: 2
Откуда: Москва
Благодарил (а): 40 раз
Поблагодарили: 40 раз

Сложный Python для чайников.

Сообщение SemenSinchenko » 30 авг 2017, 08:40

Chocobo, прямо написано так "Программирование — Напишите программу. Тестируется через stdin → stdout" (на скриншоте даже видно)...

П.С. Так как я решил задачу, то приветствуются комментарии по моему "говнокодингу", что можно было сделать лучше, в чем я сделал как индус =) Спасибо!)))

П.П.С. Я правильно понял, что сложность моего решения есть O(n*log(n)) из-за наличия сортировки?

Аватара пользователя
Chocobo
Сообщения: 4581
Зарегистрирован: 27 авг 2016, 19:57
Решено: 108
Откуда: НН
Благодарил (а): 374 раза
Поблагодарили: 1227 раз

Сложный Python для чайников.

Сообщение Chocobo » 30 авг 2017, 08:44

SemenSinchenko, Это я увидел, просто и думаю что с тем же успехом пойдут стандартные функции input() на ввод и print() на вывод
Изображение

Аватара пользователя
Chocobo
Сообщения: 4581
Зарегистрирован: 27 авг 2016, 19:57
Решено: 108
Откуда: НН
Благодарил (а): 374 раза
Поблагодарили: 1227 раз

Сложный Python для чайников.

Сообщение Chocobo » 30 авг 2017, 09:26

Вот этот кусок ввода отрезков

Код: Выделить всё

for i in range(n):
    lineIn = sys.stdin.readline().split(" ")
    l_tmp = (int(lineIn[0]))
    r_tmp = (int(lineIn[1]))
    r_l.append([r_tmp, l_tmp])

я бы представил так

Код: Выделить всё

for i in range(n):
    r_l.append(map(int,raw_input().split()))
    r_l[i].sort(reverse=True)

В первой строке пользовательский ввод сразу обращаем в числовой список и вкладываем в исходный
Второй строкой - обратная сортировка добавленного элемента, чтоб не гонять через переменные.
Ну и импортировать весь sys ни к чему будет
Изображение


Вернуться в «Скриптинг и программирование»

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и 0 гостей