Paczka mniejszych testów do PAK (jeśli ktoś nie lubi makstestów :D). Ktoś potwierdza?
http://www.student.ii.uni.wroc.pl/~i247961/pak.zip

Potwierdzam, aczkolwiek mam przeczucie, że poleganie na kilku małych testach wklepanych z palca oraz maxtestach mających na celu przetestować tylko wydajność, może być zwodnicze. Jak ktoś ma ochotę, pomysł i czas, to fajnie by było zobaczyć jakieś fajniejsze testy.

Ok, rzeczywiście moje testy nie spełniały warunków zadania. Natomiast te duże testy Grzegorza mój program potwierdza (czas ok. 3s)

https://github.com/lukaszb/porunga

Potwierdzam

Te też mój program potwierdza :)

Potwierdzam oba ;)
Czas na moim komputerze < 1s w obu przypadkach.

@Marcin Samsel
TAK

Test 32:
TAK
2 8 4 6 7 5 1 3 9 10

A mój TAK :P
2 8 4 6 7 5 1 3 9 10

Przygotowałem dwa maksy
http://speedy.sh/Yjq6j/sample-nie.txt
http://speedy.sh/abFmb/sample-tak.txt
Ostrzegam, ze swoje ważą

Mój bohater mówi: NIE

Potwierdzam wszystkie testy, które są poprawne.

Potwierdzam zarówno uwagi co do poprawności testów, jak i zgodność outów z moim programem.

Inna interpretacja, która sprowadza się do MST z użyciem Prima:

(1) Zauważamy, że do rozwiązania należy najtańszy z przedziałów postaci [1,x]. Dodajemy go do rozwiązania.

(2) Zauważamy, że znając [1,x] poznanie [1,y] jest równoważne poznaniu:
(a) [y+1,x] dla y<x, bo [1,y]^[y+1,x] = [1,x]
(b) [x+1,y] dla y>x bo [1,x]^[x+1,y] = [1,y]

Jeśli któryś z przedziałów [1,y] jest tańszy niż równoważny mu przedział, to ustawiamy równoważnemu cenę równą cenie [1,y].

(3) Rozwiązujemy problem dla kubków od 2 do N wracając do punktu (1).