Mam trochę książek i półkę na książki. Chciałbym umieścić jak najwięcej książek na półce, ale mam pewną zasadę. Wszystkie wymiary książek (wysokość, szerokość i głębokość) powinny tworzyć nie rosnącą sekwencję na półce.

Oznacza to, że każda książka musi być co najmniej tak wysoka, jak ta po sobie. To samo dotyczy szerokości i głębokości. Nie można obracać książek w celu zamiany ich wysokości, szerokości i głębokości.

Powinieneś napisać program lub funkcję, która podając wymiary wszystkich książek jako dane wyjściowe lub zwraca maksymalną liczbę książek, jakie mogę umieścić na półce.

Wejście

• Lista trojaczków liczb całkowitych dodatnich, przy czym każda trojaczka określa wysokość, szerokość i głębokość książki.
• Na liście wejściowej będzie co najmniej jeden triplet.
• Dwie książki mogą mieć tę samą długość wzdłuż dowolnej liczby wymiarów.

Wynik

• Pojedyncza dodatnia liczba całkowita, maksymalna liczba książek, które mieszczą się na półce, przestrzegając reguły.

Złożoność czasowa

Algorytm powinien mieć wielomian złożoności w najgorszym przypadku w liczbie książek. Oznacza to, że na przykład wszystkie złożone zawirowania czasowe są prawidłowe: O (N ^ 3), O (log (N) * N ^ 2), O (N) i następujące są nieprawidłowe: O (2 ^ N), O (N!), O (N ^ N).

Przykłady

Dane wejściowe => Dane wyjściowe

(1, 1, 1) =>  1

(5, 2, 5), (1, 3, 5) =>  1

(5, 2, 5), (1, 2, 5) =>  2

(2, 2, 2), (2, 2, 2), (2, 2, 2), (1, 3, 6) =>  3

(1, 2, 5), (1, 3, 5), (1, 2, 8), (1, 2, 5), (7, 7, 7) =>  4

(5, 19, 3), (9, 4, 16), (15, 16, 13), (7, 4, 16), (1, 13, 14), (20, 1, 15), (9, 8, 19), (4, 11, 1) =>  3

(1, 1, 18), (1, 13, 7), (14, 1, 17), (8, 15, 16), (18, 8, 12), (8, 8, 15), (10, 1, 14), (18, 4, 6), (10, 4, 11), (17, 14, 17), (7, 10, 10), (19, 16, 17), (13, 19, 2), (16, 8, 13), (14, 6, 12), (18, 12, 3) =>  5

To jest golf golfowy, więc wygrywa najkrótszy wpis.

Powiązane interesujące wyzwanie związane z sortowaniem książek: Sortowanie książek .

Python 3: 436 bajtów

Na początku widziałem to jako kompletny problem NP polegający na znalezieniu najdłuższej prostej ścieżki na ukierunkowanym wykresie z cyklami. Jednak każdy cykl na wykresie (w rzeczywistości kompletny podrozdział) może być reprezentowany jako pojedynczy wierzchołek. Innymi słowy, traktuj identyczne książki jak jedną książkę, którą należy umieścić na półce jako całość. Następnie możemy zbudować ukierunkowany wykres acykliczny, w którym a-> b oznacza, że ​​b może podążać za znakiem na półce. Na koniec znajdujemy maksymalną wysokość drzewa (drzew) za pomocą metody rekurencyjnej.

import sys
b=[]
n={}
r=[]
for L in sys.stdin.readlines():z=[int(x)for x in L.split()];r+=[z];z in b or b+=[z]
def l(a,b):return a[0]<=b[0]and a[1]<=b[1]and a[2]<=b[2]
R=range(len(b))
for i in R: 
    n[i]=[]
    for j in R:i!=j and l(b[i],b[j])and n[i]+=[j]
def L(t):
    global v;best=0
    if t in v:
            return v[t]
    for s in n[t]:best=max(best,L(s)+1)
    v[t]=best+r.count(b[t])-1;return best
m=0
for i in R:v={};m=max(L(i)+1,m)
print(m)

Pyth, 40 bajtów

KYleolNe.eaK+e+]])olNf.A.eg@YbZeT<Kk]YSQ

Nie szybko, ale jest wielomianowy.

Odpowiednik Python3:

def num_books(l):
    l = sorted(l)
    s = []
    for i, Y in enumerate(l):
        s.append(max([T for T in s[:i]
                      if all(Y[e] >= t for e, t in enumerate(T[-1]))] + [[]],
                     key=len) + [Y])
    return max(len(u) for u in s)

Python 2, 231 bajtów

Wypróbuj tutaj

Mój program obecnie źle podaje dwa ostatnie przykłady. Czy ktoś może mi pomóc to naprawić? Dzięki.

Sortuję listę wszystkich 6 możliwych rzędów permutacji 3 wymiarów, następnie sprawdzam, jaka jest najdłuższa relacja ciągłego uporządkowania na liście, a następnie znajduję maksimum z nich.

Wiem też, czy można grać w golfa o wiele więcej, ale nie mogłem wymyślić, czy mógłbym reduceto zrobić. Mówiąc najprościej, ten sposób był najłatwiejszy do zrobienia w rozsądnym czasie bez eksplozji mojego mózgu.

from operator import*
from itertools import*
def f(t):
    m=1
    for l in(sorted(t,key=itemgetter(*o))for o in permutations(range(3))):
        c=1
        for k in range(len(l)-1):
            c+=all(i<=j for i,j in zip(l[k],l[k+1]))
        m=max(m,c)
    print m