Problem description

.desc_header { margin-bottom: 2em; text-align: center; } .desc_title { font-size: 200%; text-decoration: underline; padding: 0em 0.2em; display: inline-block; } .desc_code { padding: 0em 0.2em; font-weight: bold; display: inline-block; } .desc_meta { margin: 0.5em; } .desc_memlimit { padding: 0em 1.25em; display: inline-block; } .desc_timelimit { padding: 0em 1.25em; display: inline-block; } .desc .example-test { width: 100%; margin-top: 10px; } .desc .example-test td { vertical-align: top; } .desc .example-test pre { margin-top: 5px; } Superpermutacja (G) Limit pamięci: 256 MB Limit czasu: 2.00 s Jasio, Jasio, Jasio. Możesz już mieć dość zadań o Jasiu, dlatego to zadanie będzie inne i nie będzie już nic o Jasiu. Bo nadszedł czas, żeby w końcu na turnieju rozwiązać jakiś prawdziwy problem matematyczny. Taki, którego jeszcze nikt wcześniej (no, może poza autorem tego zadania, który musiał przecież zaimplementować wzorcówkę) nie rozwiązał. Najlepiej przeczytaj po prostu historię, bo jest “z życia wzięta”. Istnieje taki problem matematyczny (nazwijmy go roboczo problemem superpermutacji), w którym chcemy wygenerować możliwie krótki napis, zawierający w sobie (jako spójne fragmenty) wszystkie permutacje napisu 123…N. Przykładowo: dla N = 2 wystarczy wziąć napis 121, który zawiera w sobie zarówno fragment 12 oraz 21. Dla N = 3, pasuje na przykład 123121321 (który zawiera jako spójne fragmenty wszystkie te napisy: 123, 132, 213, 231, 312 oraz 321). Naturalnym jest oczywiście pytanie: ile znaków musi mieć najkrótszy napis zawierający wszystkie permutacje, dla ustalonego N? Problem jest na tyle ciekawy, że pojawiły się nawet interesujące filmy popularnonaukowe na jego temat. Przykładowo: https://www.youtube.com/watch?v=wJGE4aEWc28 W dużym skrócie: przez jakiś czas wierzono (postawiono hipotezę), że optymalny napis ma zawsze 1! + 2! + 3! + … + N! znaków. Istnieje prosta konstrukcja, która generuje ciąg takiej długości. Została ona opisana na przykład tutaj: https://njohnston.ca/2013/04/the-minimal-superpermutation-problem/ Jakiś czas później okazało się jednak, że hipoteza nie jest prawdziwa. Dla N = 6 udało się bowiem skonstruować napis o długości 872 (zamiast oczekiwanego 873). Konstrukcja oraz sam napis, podane zostały w tej pracy: https://arxiv.org/abs/1408.5108 Autora tej pracy zaproszono nawet do wystąpienia na innym popularnonaukowym kanale, żeby opowiedział o swoim osiągnięciu. Możesz zobaczyć jego opowieść tutaj: https://www.youtube.com/watch?v=OZzIvl1tbPo Jak widać, czasami okazuje się, że gdy hipotezie brakuje dowodu, to może być ona fałszywa. No dobrze, ale gdzie tutaj ten zapowiadany prawdziwy problem matematyczny? Czas wcielić się w rolę naukowców przełamujących bariery. Rozważamy problem superpermutacji dla N = 9. Celem jest napisanie programu, który wygeneruje napis krótszy o co najmniej 5 znaków od tego, który wynikałby z hipotezy. Należy więc napisać program, który na wyjście wypisuje napis zawierający wszystkie permutacje napisu 123456789 jako spójne podsłowa, którego długość nie przekracza 409 108. Powodzenia! Wejście W tym zadaniu nie ma wejścia. Twój program nie musi nic wczytywać. Możesz założyć, że jest tylko jeden test, w którym rozpatrujemy zadanie dla N = 9. Wyjście W pierwszym (jedynym) wierszu wyjścia powinien się znaleźć ciąg znaków 1-9 (bez żadnych odstępów) o długości co najwyżej 1! + 2! + 3! + … + N! − 5 (dla N = 9 suma ta jest równa 409 108). Każda spośród wszystkich N! permutacji napisu 123…N ma występować choć raz w wygenerowanym napisie jako spójny fragment. Przykład W tym zadaniu podawanie przykładu nie ma sensu. Możesz założyć, że gdybyśmy rozpatrywali zadanie dla N = 6, a limit długości wynosiłby 1! + 2! + 3! + 4! + 5! + 6! − 1, to program mógłby po prostu wypisać napis z pracy Houstona.