Specyfikacja
Wyzwanie to jest łatwe do stwierdzenia: dane wejściowe to niepusta tablica nieujemnych liczb całkowitych, a Twoim zadaniem jest podzielenie ich na jak najmniej rosnących podsekwencji. Bardziej formalnie, jeśli tablica wejściowa jest A
, to dane wyjściowe to tablica tablic B
takich, że:
- Każda tablica
B
tworzy podziałA
na rozłączne (niekoniecznie ciągłe) podsekwencje. Indukcyjnie oznacza to, że alboB
zawiera tablicę singletonówA
, albo pierwszy elementB
jest podsekwencją,A
a reszta tworzy partycjęA
z usuniętą podsekwencją. - Każda tablica
B
rośnie (niekoniecznie ściśle). - Liczba tablic
B
jest minimalna.
Zarówno dane wejściowe, jak i wyjściowe mogą być pobierane w rodzimym formacie tablicowym Twojego języka. Pamiętaj, że może istnieć kilka poprawnych wyników.
Przykład
Rozważ tablicę wejściową A = [1,2,1,2,5,4,7,1]
. Jednym z możliwych wyników jest B = [[1],[1,2,4,7],[1,2,5]]
. Warunki partycji są widoczne na tym schemacie:
A 1 2 1 2 5 4 7 1
B[0] 1
B[1] 1 2 4 7
B[2] 1 2 5
Z każdą kolejną tablicą B
rośnie. Wreszcie, A
nie można podzielić na dwa rosnące podsekwencje, więc długość B
jest również minimalna. Dlatego jest to poprawny wynik.
Zasady i punktacja
Możesz napisać funkcję lub pełny program. Wygrywa najniższa liczba bajtów, a standardowe luki są niedozwolone. Nie ma ograniczenia czasowego, ale powinieneś ewakuować swoje rozwiązanie na wszystkich testowych przypadkach przed jego przesłaniem.
Przypadki testowe
Wyświetlane jest tylko jedno możliwe wyjście, ale może istnieć kilka prawidłowych opcji. W szczególności kolejność tablic w wyniku nie ma znaczenia (ale każda pojedyncza tablica powinna być w kolejności rosnącej).
[0] -> [[0]]
[3,5,8] -> [[3,5,8]]
[2,2,2,2] -> [[2,2,2,2]]
[1154,1012,976,845] -> [[845],[976],[1012],[1154]]
[6,32,1,2,34,8] -> [[1,2,8],[6,32,34]]
[1,12,1,12,1,13] -> [[1,1,1,13],[12,12]]
[6,4,6,13,18,0,3] -> [[0,3],[4,6,13,18],[6]]
[1,2,3,2,3,4,7,1] -> [[1,1],[2,2,3,4,7],[3]]
[0,9,2,7,4,5,6,3,8] -> [[0,2,3,8],[4,5,6],[7],[9]]
[7,1,17,15,17,2,15,1,6] -> [[1,1,6],[2,15],[7,15,17],[17]]
[4,12,2,10,15,2,2,19,16,12] -> [[2,2,2,12],[4,10,15,16],[12,19]]
[10,13,9,2,11,1,10,17,19,1] -> [[1,1],[2,10,17,19],[9,11],[10,13]]
[3,7,3,8,14,16,19,15,16,2] -> [[2],[3,3,8,14,15,16],[7,16,19]]
[15,5,13,13,15,9,4,2,2,17] -> [[2,2,17],[4],[5,9],[13,13,15],[15]]
[0,5,2,0] -> [[0,5],[0,2]]
(np. Recykling pierwszego zera zamiast korzystania z każdego z nich raz). Czy to celowe?B
, mam nadzieję, że są teraz jaśniejsze.Odpowiedzi:
Haskell, 54 bajty
Przykład użycia:
foldr(#)[] [4,12,2,10,15,2,2,19,16,12]
->[[2,2,2,12],[4,10,15,16],[12,19]]
Jak to działa: przejrzyj listę danych wejściowych, zaczynając od prawego końca. Zbuduj listę wyjściową (list), przygotowując bieżący element
n
do pierwszej podlisty,l
gdzien
jest mniejsza lub równa główcel
. Jeśli nie ma, utwórz nową listę singletonówn
na końcu listy wyników.źródło
Pyth, 20 bajtów
Wypróbuj online: pakiet demonstracyjny lub testowy
Chciwe podejście. Tworzę
len(input)
puste listy. Następnie iteruję każdą liczbę na liścieinput
wyboru pierwszej, która nadal jest sortowana po dodaniu liczby.Wyjaśnienie:
źródło