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

Языки программирования, IDE, компиляторы, интерпретаторы, гипервизоры и виртуальные среды
Правила форума
Правильно сформулированный вопрос и его грамотное оформление способствует высокой вероятности получения достаточно содержательного и по существу ответа.
Аватара пользователя

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

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

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

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

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

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

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

import sys

lineIn = sys.stdin.readline()
n = int(lineIn)

r_l = []

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])
    
r_l.sort()

m_coord = []
m_coord.append(r_l[0][0])
m = 1

for i in range(n):
    if r_l[i][1] > m_coord[(len(m_coord) - 1)]:
        m = m + 1
        m_coord.append(r_l[i][0])


sys.stdout.write(str([m, m_coord]))
Но система проверки ругается, говорит следующее:
Failed test #1. wrong output format: invalid literal for int() with base 10: '[1,'
Input:
3
1 3
2 5
3 6

Your output:
[1, [3]]
Correct output:
1
3
То есть решение по ходу то правильное, но неверный формат вывода! Подскажите, как нужно переформатировать вывод?

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

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

sys.stdout.write(str(m) + '\n')
for i in range(len(m_coord)):
  sys.stdout.write(str(m_coord[i]) + ' ')
Всем спасибо! Очень помогли!

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

Аватара пользователя

darkfenix
Сообщения: 633
Зарегистрирован: 27 июн 2017, 10:36
Решено: 9
Благодарил (а): 40 раз
Поблагодарили: 103 раза

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

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

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

Аватара пользователя

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

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

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

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

В сети
Аватара пользователя

Chocobo
Сообщения: 5556
Зарегистрирован: 27 авг 2016, 19:57
Решено: 130
Откуда: НН
Благодарил (а): 411 раз
Поблагодарили: 1440 раз

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

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

sys.stdout.write(str(m) + '\n' + str(m_coord[0]))

Аватара пользователя

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

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

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

Chocobo, Теперь выводится только первая точка...
Failed test #2. wrong output format: list index out of range
Input:
4
4 7
1 3
2 5
5 6

Your output:
2
3
Correct output:
2
3 6

Аватара пользователя

darkfenix
Сообщения: 633
Зарегистрирован: 27 июн 2017, 10:36
Решено: 9
Благодарил (а): 40 раз
Поблагодарили: 103 раза

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

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

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

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

В сети
Аватара пользователя

Chocobo
Сообщения: 5556
Зарегистрирован: 27 авг 2016, 19:57
Решено: 130
Откуда: НН
Благодарил (а): 411 раз
Поблагодарили: 1440 раз

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

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

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

Аватара пользователя

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

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

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

darkfenix, как же сложно с этим stdout... Курс входит в программу "Анлиз данных", а не программирование...
Теперь пробела не хватает:
Failed test #2. wrong output format: list index out of range
Input:
4
4 7
1 3
2 5
5 6

Your output:
2
36
Correct output:
2
3 6

Аватара пользователя

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

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

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

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

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

sys.stdout.write(str(m) + '\n')
for i in range(len(m_coord)):
  sys.stdout.write(str(m_coord[i]) + ' ')
Всем спасибо! Очень помогли!

Аватара пользователя

darkfenix
Сообщения: 633
Зарегистрирован: 27 июн 2017, 10:36
Решено: 9
Благодарил (а): 40 раз
Поблагодарили: 103 раза

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

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

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

В сети
Аватара пользователя

Chocobo
Сообщения: 5556
Зарегистрирован: 27 авг 2016, 19:57
Решено: 130
Откуда: НН
Благодарил (а): 411 раз
Поблагодарили: 1440 раз

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

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

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

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

Аватара пользователя

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

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

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

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

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

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

В сети
Аватара пользователя

Chocobo
Сообщения: 5556
Зарегистрирован: 27 авг 2016, 19:57
Решено: 130
Откуда: НН
Благодарил (а): 411 раз
Поблагодарили: 1440 раз

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

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

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

В сети
Аватара пользователя

Chocobo
Сообщения: 5556
Зарегистрирован: 27 авг 2016, 19:57
Решено: 130
Откуда: НН
Благодарил (а): 411 раз
Поблагодарили: 1440 раз

Сложный 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 ни к чему будет

В сети
Аватара пользователя

Dja
Сообщения: 2785
Зарегистрирован: 27 авг 2016, 17:03
Решено: 11
Откуда: Воскресенск
Благодарил (а): 393 раза
Поблагодарили: 284 раза

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

Сообщение Dja » 16 ноя 2017, 18:54

Не по теме
SemenSinchenko писал(а):
30 авг 2017, 08:34
Вот и выкладывай после этого в радикалы... Неужели нельзя было нормальным хостингом воспользоваться? Или вообще сюда закинуть.
Новичок? - ознакомься с правилами

В поисках истины :grabli:

Вернуться в «Программирование, скриптинг, виртуализация»