LinuxMint.com.ru

Прохожу курс по теории алгоритмов. Там задача:

По данным 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

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

Ты пытаешь ей скормить массив m_coord,

SemenSinchenko писал(а): sys.stdout.write(str([m, m_coord]))

darkfenix, Ну так задание говорит, что я должен вывести координаты точек:

Выведите оптимальное число m точек и сами m точек.

А координаты у меня в массиве хранятся

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

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

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

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

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

Сейчас гляну тогда и по коду

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

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

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

sys.stdout.write(str(m) + '\n')
for i in range(len(m_coord)):
  sys.stdout.write(str(m_coord[i]) + ' ')

Всем спасибо! Очень помогли!

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

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

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

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

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

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

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

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

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

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 ни к чему будет

Не по теме

SemenSinchenko писал(а): ↑
30 авг 2017, 11:34

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

LinuxMint.com.ru

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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