Jestem pewien, że wszyscy widzieli wcześniej, że kubki można układać w piramidy (i inne kształty):
A
A A A
A A A A A
A A A A A A A A
Tak, A
jest zdecydowanie odpowiednią postacią do reprezentowania filiżanki.
Nowe kubki można dodawać albo na ziemi, po prawej stronie konstrukcji, albo na dwóch sąsiadujących kubkach. Oto ponownie powyższa struktura, ale wszystkie dostępne miejsca na nowe kubki są oznaczone _
:
_ A
A A A
A _ _ A A A A
A A A A A A A A _ _ _
Powiedzmy, że chcemy zbudować robota, który może łączyć te stosy kubków. Robot zrozumie dwie proste instrukcje dotyczące manipulowania taką strukturą:
a
: Dodaj nowy kubek w pierwszym dostępnym miejscu w kolejności czytania od lewej do prawej (tzn. Zeskanuj rzędy od góry do dołu, od lewej do prawej, aż znajdziesz wolne miejsce, a następnie umieść tam kubek). Powyższy przykład wyglądałby następująco:A A A A A A A A A A A A A A A A A A
r
: Wyjmij pierwszy kubek w kolejności czytania od lewej do prawej. Powyższy przykład wyglądałby następująco:A A A A A A A A A A A A A A A A
Okazuje się, że dowolną strukturę można zbudować od zera przy użyciu tylko tych dwóch operacji. Na przykład
A
A A A
A A A A A
Może być zbudowany z sekwencji instrukcji
aaaaaaaaaaaarrrrraa
Większy przykład powyżej można zbudować za pomocą
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaarrrrrrrrrrrrrrrrrraaaaaaarr
Oto jeszcze większy:
A
A A A
A A A A A A A
A A A A A A A A A A A A
A A A A A A A A A A A A A A A
które można zbudować
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaarrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrraaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaarrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrraaaaaaaaaaaaaaaaaaarrrrrrrrrrrrrrraaaaaaaaaaaaaarrrrrrrrrrraaaaaaaa
Uwaga: Jeśli miejsca na ziemi zostaną zwolnione dzięki instrukcjom usuwania, zostaną one ponownie wykorzystane przed umieszczeniem filiżanek po prawej stronie wszystkich istniejących filiżanek. Na przykład
aaaarrra
ustąpi
A A
nie
A A
Możesz myśleć o ziemi jako o pół-nieskończonym rzędzie filiżanek.
Wyzwanie
Biorąc pod uwagę strukturę stosów kubków, zwróć sekwencję przedstawiającą instrukcje dotyczące budowy tej struktury. Twój wynik główny to suma liczb instrukcji dla przypadków testowych podanych na dole. W przypadku remisu (co jest prawdopodobne, ponieważ jestem przekonany, że możliwe jest skuteczne i optymalne rozwiązanie), najkrótsze rozwiązanie wygrywa.
Oto kilka szczegółów na temat zasad:
- Możesz założyć, że w dolnym rzędzie wejścia nie ma żadnych spacji wiodących, więc zawsze używaj lewego skrajnego miejsca na filiżankę.
- Możesz założyć dowolną rozsądną liczbę końcowych spacji (bez spacji, jedna spacja, dopełniona do prostokąta, dopełniona do prostokąta z jedną spacją końcową).
- Opcjonalnie możesz oczekiwać, że dane wejściowe zakończą się jednym końcowym znakiem nowej linii.
- Możesz wybrać dowolne dwa odrębne drukowalne znaki ASCII (0x20 do 0x7E włącznie) zamiast
A
spacji (reguły dotyczące spacji przenoszą się na wybraną postać). - Twój wynik powinien zawierać tylko dwa różne znaki reprezentujące operacje (możesz wybrać inne znaki niż
a
ir
). Możesz opcjonalnie wydrukować jedną końcową linię nowego wiersza. - Twój kod musi być w stanie rozwiązać dowolny z poniższych przypadków testowych w ciągu niecałej minuty na rozsądnym komputerze stacjonarnym (jeśli zajmie to dwie minuty w moim przypadku, dam ci korzyść z wątpliwości, ale jeśli zajmie to dziesięć, wygrałem 't - Uważam, że możliwy jest optymalny algorytm, który rozwiąże którykolwiek z nich w mniej niż sekundę).
- Nie wolno optymalizować kodu pod kątem indywidualnych przypadków testowych (np. Poprzez ich kodowanie na stałe). Jeśli podejrzewam, że ktoś to robi, zastrzegam sobie prawo do zmiany przypadków testowych.
Możesz użyć tego skryptu CJam do operacji odwrotnej: zajmie ciąg instrukcji budowania i wydrukuje powstały stos kubków. (Podziękowania dla Dennisa za przepisanie fragmentu i znaczne przyspieszenie).
Sp3000 również uprzejmie dostarczył ten alternatywny skrypt Pythona do tego samego celu.
Przypadki testowe
Po każdym przypadku testowym znajduje się liczba wskazująca optymalną liczbę instrukcji zgodnie z odpowiedzią Ell.
A
A A
A A A
A A A A
A A A A A
A A A A A A
A A A A A A A
A A A A A A A A
A A A A A A A A A
A A A A A A A A A A
A A A A A A A A A A A
A A A A A A A A A A A A
A A A A A A A A A A A A A
A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
820
A
A A
A A A
A A A A
A A A A A
A A A A A A
A A A A A A A
A A A A A A A A
A A A A A A A A A A
A A A A A A A A A A A A
A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
1946
A
A A
A A A
A A A A
A A A A A
A A A A A A
A A A A A A A
A A A A A A A A
A A A A A A A A A A
A A A A A A A A A A A A
A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
2252
A A
A A A A
A A A A A A
A A A A A A A A
A A A A A A A A A A
A A A A A A A A A A A A
A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
9958
A A
A A A A
A A A A A A
A A A A A A A A
A A A A A A A A A A
A A A A A A A A A A A A
A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
5540
A A A A A A A A A A A A A A A A A A A A
10280
A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
10320
A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
5794
A
A A
A A A
A A A A A
A A A A A A A
A A A A A A A A A A
A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
3297
A A
A A A
A A A A
A A A A A
A A A A A A
A A A A A A A
A A A A A A A A
A A A A A A A A A
A A A A A A A A A A A
A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
4081
A
A A A A
A A A A A A A A A
A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
4475
A
A A A A A A A A
A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
5752
Oznacza to, że najlepszy możliwy wynik to 64 515 instrukcji.
źródło