Тренировочное задание по программированию: Ставки

@Deneno · Регистрация: 28.01.2021

Студворк — интернет-сервис помощи студентам

Доброго времени! Прошу помочь с муторной задачей на функциональный стиль:
Перед началом тараканьих бегов всем болельщикам было предложено сделать по две ставки на результаты бегов. Каждая ставка имеет вид "Таракан №A придет раньше, чем таракан №B". Организаторы бегов решили выяснить, могут ли тараканы прийти в таком порядке, чтобы у каждого болельщика сыграла ровно одна ставка из двух (то есть чтобы ровно одно из двух утверждений каждого болельщика оказалось верным). Считается, что никакие два таракана не могут прийти к финишу одновременно.

Формат ввода
В первой строке входных данных содержатся два разделенных пробелом натуральных числа: число K, не превосходящее 10, - количество тараканов и число N, не превосходящее 100, - количество болельщиков. Все тараканы пронумерованы числами от 1 до K. Каждая из следующих N строк содержит 4 натуральных числа A, B, C, D, не превосходящих K, разделенных пробелами. Они соответствуют ставкам болельщика "Таракан №A придет раньше, чем таракан №B" и "Таракан №C придет раньше, чем таракан №D".

Формат вывода
Если завершить бега так, чтобы у каждого из болельщиков сыграла ровно одна из двух ставок, можно, то следует вывести номера тараканов в том порядке, в котором они окажутся в итоговой таблице результатов (сначала номер таракана, пришедшего первым, затем номер таракана, пришедшего вторым и т. д.) в одну строку через пробел. Если таких вариантов несколько, выведите любой из них. Если требуемого результата добиться нельзя, выведите одно число 0.

Тест 1
Входные данные:
3 2
2 1 2 3
1 2 3 2
Вывод программы:
3 2 1

Тест 2
Входные данные:
3 4
1 2 1 3
1 2 3 1
1 2 2 3
1 2 3 2
Вывод программы:
0

Собственно я прохожу эти тесты, как и остальные 15. Но на 18 тесте ловлю Time Limit Exceeded.
Подскажите пожалуйста как ускорить программу:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from itertools import permutations, repeat
from sys import stdin
print(
    *next(
        filter(
            lambda w:
                all(
                    map(
                        lambda e: (str(w[0]).index(e[0]) >= str(w[0]).index(e[2])) ^ (str(w[0]).index(e[4]) >= str(w[0]).index(e[6])),
                        w[1]
                    )
                ), 
            zip(
                permutations(
                    range(1, int(input().split()[0]) + 1)),
                    repeat(stdin.readlines()
                )
            )
        ),'0'
    )[0]
)

@Welemir1 · 08.02.2021, 16:56

Deneno, задача была написать максимально длинный и хреново читаемый код? вместо того чтобы на функции разбить?

@Deneno · 08.02.2021, 17:03 **[ТС]**

В том то и соль©

@Arsegg · 08.02.2021, 17:28

Не по теме:

Welemir1, такая монструозная дичь))) Химера мира программирования)))

По теме: предположу, что задачу можно решить с помощью backtracking'а.

@Deneno · 08.02.2021, 17:37 **[ТС]**

[/Arsegg] На сколько я согласен с вами, настолько этот бред помогает разобраться методом тыка в том, что можно делать, а что нельзя с различными функциями) Но в целом помимо это бреда, требуется ещё и оптимизировать его чтобы пройти неведомый тест

@Welemir1 · 08.02.2021, 17:39

Не по теме:

да уж, действительно помогает. как тыкание гвоздиком в розетку помогает понять закон Ома

@Arsegg · 08.02.2021, 17:41

Сообщение от Deneno

пройти неведомый тест

Судя по твоему коду, ты тупо перебираешь все перестановки, что не укладывается в TL. Если будешь отсекать заведомо ложные решения (в т. ч. с помощью Backtracking'а), то должно пройти.

P. S. Код в функциональном стиле я писать категорически отказываюсь...

@Welemir1 · 08.02.2021, 17:47

Arsegg, а это и не код в функциональном стиле. вернее этот тоже, но цель то фп не в том чтобы нагородить вложенностей. Все это можно разбить на короткие читаемые функции и вот это будет крутой код в функциональном стиле.

@Arsegg · 08.02.2021, 17:52

Не по теме:

Сообщение от Welemir1

Все это можно разбить на короткие читаемые функции и вот это будет крутой код в функциональном стиле.

Не все так просто, к сожалению... Взять ту же Scala и ко: без валерьянки такой код сложно читать...

@Welemir1 · 08.02.2021, 18:00

Не по теме:

Arsegg, так это уже их подход к написанию кода) я к тому что в ФП нет требования писать непонятно и вкладывать все друг в друга.

@Arsegg · 08.02.2021, 18:20

Не по теме:

Сообщение от Welemir1

я к тому что в ФП нет требования писать непонятно и вкладывать все друг в друга.

В ФП - все есть функция. И там все вложено, если на то дело пошло)) Просто компилятор позволяет скрыть эту данность с помощью "синтаксического сахара".

@Deneno · 08.02.2021, 19:02 **[ТС]**

Сделал так и до этого еще отсекал варианты сразу при получении данных (на 16 строке), к сожалению все также TL

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from itertools import permutations, repeat
from sys import stdin
print(
    *next(
        filter(
            lambda w:
            all(
                map(
                    lambda e: set(range(1, int(x[0]) + 1)) >= set(map(int, e.split())) and
                    (str(w[0]).index(e[0]) >= str(w[0]).index(e[2])) ^ (str(w[0]).index(e[4]) >= str(w[0]).index(e[6])),
                    w[1]
                )
            ),
            zip(
                permutations(range(1, int(input().split()[0]) + 1)),
                repeat(stdin.readlines())
            )
        ), '0'
    )[0]
)

Добавлено через 7 минут
В общем вот так пытался, не прошло

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from itertools import permutations, repeat
from sys import stdin
print(
    *next(
          filter(
              lambda w:
              all(
                  map(
                      lambda e: set(w[0]) >= set(map(int, e.split())) and
                      (str(w[0]).index(e[0]) >= str(w[0]).index(e[2])) ^ (str(w[0]).index(e[4]) >= str(w[0]).index(e[6])),
                      w[1]
                  )
              ),
              zip(
                  permutations(range(1, int(input().split()[0]) + 1)),
                  repeat(stdin.readlines())
              )
         ), '0'
    )[0]
)

@Arsegg · 08.02.2021, 19:08

Не по теме:

Сообщение от Deneno

Сделал так и до этого еще отсекал варианты сразу при получении данных (на 16 строке),

Почитай на досуге про бектрекинг. Ты совершенно не понимаешь теорию...

@Deneno · 08.02.2021, 19:18 **[ТС]**

Не по теме:

Сообщение от Arsegg

Почитай на досуге про бектрекинг. Ты совершенно не понимаешь теорию...

Такое бывает, когда средненький инженер-строитель начинает проходить курсы)

Новые блоги и статьи Все статьи Все блоги /
Программный контроль заполнения реквизита табличной части документа Maks 02.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: реализовать контроль заполнения реквизита табличной части. . .	wmic не является внутренней или внешней командой Maks 02.04.2026 Решение: DISM / Online / Add-Capability / CapabilityName:WMIC~~~~ Отсюда: https:/ / winitpro. ru/ index. php/ 2025/ 02/ 14/ komanda-wmic-ne-naydena/	Программная установка даты и запрет ее изменения Maks 02.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: при создании документов установить период списания автоматически. . .	Вывод данных в справочнике через динамический список Maks 01.04.2026 Реализация из решения ниже выполнена на примере нетипового справочника "Спецтехника" разработанного в конфигурации КА2. Задача: вывести данные из ТЧ нетипового документа. . .
Функция заполнения текстового поля в реквизите формы документа Maks 01.04.2026 Алгоритм из решения ниже реализован на нетиповом документе "ВыдачаОборудованияНаСпецтехнику" разработанного в конфигурации КА2, в дополнении к предыдущему решению. На форме документа создается. . .	К слову об оптимизации kumehtar 01.04.2026 Вспоминаю начало 2000-х, университет, когда я писал на Delphi. Тогда среди программистов на форумах активно обсуждали аккуратную работу с памятью: нужно было следить за переменными, вовремя. . .	Идея фильтра интернета (сервер = слой+фильтр). Hrethgir 31.03.2026 Суть идеи заключается в том, чтобы запустить свой сервер, о чём я если честно мечтал давно и давно приобрёл книгу как это сделать. Но не было причин его запускать. Очумелые учёные напечатали на. . .	Модель здравосоХранения 6. ESG-повестка и устойчивое развитие; углублённый анализ кадрового бренда anaschu 31.03.2026 В прикрепленном документе раздумья о том, как можно поменять модель в будущем

@Welemir1 Автоматизируй это! 7392 / 4819 / 1246 Регистрация: 30.03.2015 Сообщений: 13,694 Записей в блоге: 29
	08.02.2021, 16:56
	Deneno, задача была написать максимально длинный и хреново читаемый код? вместо того чтобы на функции разбить? 1

@Deneno 0 / 0 / 0 Регистрация: 28.01.2021 Сообщений: 9
	08.02.2021, 17:03 [ТС]
	В том то и соль© 0

@Arsegg 3582 / 2182 / 571 Регистрация: 02.09.2015 Сообщений: 5,510
	08.02.2021, 17:28
	Не по теме: Welemir1, такая монструозная дичь))) Химера мира программирования))) По теме: предположу, что задачу можно решить с помощью backtracking'а. 0

@Deneno 0 / 0 / 0 Регистрация: 28.01.2021 Сообщений: 9
	08.02.2021, 17:37 [ТС]
	[/Arsegg] На сколько я согласен с вами, настолько этот бред помогает разобраться методом тыка в том, что можно делать, а что нельзя с различными функциями) Но в целом помимо это бреда, требуется ещё и оптимизировать его чтобы пройти неведомый тест 0

@Welemir1
	08.02.2021, 17:39
	Не по теме: да уж, действительно помогает. как тыкание гвоздиком в розетку помогает понять закон Ома 0

@Welemir1 Автоматизируй это! 7392 / 4819 / 1246 Регистрация: 30.03.2015 Сообщений: 13,694 Записей в блоге: 29
	08.02.2021, 17:47
	Arsegg, а это и не код в функциональном стиле. вернее этот тоже, но цель то фп не в том чтобы нагородить вложенностей. Все это можно разбить на короткие читаемые функции и вот это будет крутой код в функциональном стиле. 0

@Welemir1
	08.02.2021, 18:00
	Не по теме: Arsegg, так это уже их подход к написанию кода) я к тому что в ФП нет требования писать непонятно и вкладывать все друг в друга. 0