• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Algorytmika | Problem - Podział ciągu na odpowiednie podciągi

VPS Starter Arubacloud
0 głosów
739 wizyt
pytanie zadane 9 stycznia 2017 w Algorytmy przez WWOTEX Mądrala (6,200 p.)
Witam,
Ostatnio zajmuję się algorytmiką i mam tu zadanie, do którego sam odpowiedzi nie znajdę. Nie oczekuję koniecznie gotowego sposobu. Czy zna się ktoś na tym i mógłby mi wytłumaczyć co w takich zadaniach się robi i dlaczego?

Zadanie:
Podziałem ciągu cyfr na sumy nazwiemy podział go na spójne podciągi, które mają tę własność, że suma cyfr w i-tym podciągu jest mniejsza bądź równa sumie cyfr w i+1-tym podciągu. Przykładowo dla ciągu ‘11157’ poprawnym podziałem jest ’11-15-7’. Twoim zadaniem, jest dla podanego ciągu, obliczyć liczbę jego różnych podziałów na sumy.

Przykład:
Wejściowy ciąg: 112                 Poprawna odpowiedź: 4
Wejściowy ciąg: 11                   Poprawna odpowiedź: 2

Ilość liczb w ciągu to maksymalnie 50, a każdy program ma maksymalnie 1000 zestawów testowych(ciągów do obliczenia).

Z góry dziękuję chętnym za poświęcenie cennego czasu! :)

2 odpowiedzi

+1 głos
odpowiedź 12 stycznia 2017 przez Benek Szeryf (90,690 p.)
wybrane 12 stycznia 2017 przez WWOTEX
 
Najlepsza

To zadanie faktycznie jest złożone i liczenie wszystkich przypadków nie ma sensu. Mamy jednak tutaj pewne ograniczenie górne, które eliminuje nam pewne rozwiązania bez potrzeby ich dalszego badania i tracenia zasobów obliczeniowych.

TEORIA

Punktem wyjścia niech będzie definicja nowego ciągu utworzonego z ciągu pierwotnego. Każdy N-elementowy ciąg K możemy przekształcić do nowego ciągu Q :

K = {k1, k2, ... , kN}, N <= 50
Q = {q0, q1, ... , qM}, M <= N

Ciąg Q ma tę własność, że jest nierosnący i może być złożony z dowolnej kombinacji sum cyfr z ciągu K, przykładowo zakładając N=9 możemy skonstruować ciąg:

q0 = k8 + k9
q1 = k7
q2 = k6 + k5
q3 = k4 + k3 + k2 + k1

wtedy i tylko, gdy:
q3 <= q2 <= q1 <= q0

Na przykład wiemy, że każdy ciąg K będzie zawierał podciąg zupełny, który po przekształceniu do ciągu Q da nam ciąg jednoelementowy:

K = {1,2,6,3,4}
Q = {16}, bo q0 = 1 + 2 + 6 + 3 + 4

Z założeń zadania wiemy, że ostatni wyraz dowolnego podciągu ma osiągać maksimum. Taki wyraz możemy wyznaczyć, czyli wyznaczyć ostatnie j cyfr, które będą stanowić q0. Niestety jest to zadanie wieloetapowe, ponieważ zależy ono od pozostałych wyrazów ciągu Q, idąc od końca do początku ciągu K .

WYZNACZENIE ELEMENTU q0

Najpierw wędrujemy od końca ciągu K ku jego początkowi, szukając lokalnego maksimum. Jeśli na ostatniej N-tej pozycji mamy cyfrę taką że:

k(N-1) <= k(N)

to zakładamy, że jest to lokalne maksimum i przechodzimy do badania elementu q1. Jeśli tak nie jest, to sumujemy elementy i porównujemy ich sumę. Załóżmy, że lokalne maksimum jest na pozycji N-3. Wtedy zajdzie:

k(N-3) > k(N-2) + k(N-1) + k(N)

Przykładem niech będzie ciąg 12457321. Widzimy, że jego podział będzie zawsze taki, że ostatnie cztery cyfry będą razem 7321. Nie da się tego już podzielić, bo 7 zawsze będzie większa od sumy 3, 2 i 1. Dla tego ciągu q0 = 13. To jednak nie jest odpowiedź, bo q0 może być większe, a to wszystko zależy od tego, czy pozostałe elementy spełnią założenie relacji <=.

POZOSTAŁE ELEMENTY CIĄGU Q

Z poprzedniego kroku mamy już pewne górne ograniczenie. Otóż element q1 musi być mniejszy bądź równy q0. Najrozsądniej będzie dokładać kolejne cyfry tworząc sumy q1 dopóki warunek q0 => q1 będzie spełniony. Gdy przekroczymy tę barierę, to wyznaczyliśmy q1. Teraz należy analogicznie wyznaczyć q2 i pozostałe elementy, dochodząc do początku ciągu. Oczywiście może się zdarzyć, że q1 < q2 nawet jeśli q2 składa się z jednego elementu. Przykład 13281237321. W tym przypadku:

q0 = 13 = 7 + 3 + 2 + 1
q1 = 6 = 1 + 2 + 3
q2 = 8

Widzimy więc, że nie ma sensu badanie ciągów, dla których q0 = 7 + 3 + 2 + 1. Innymi słowy z sekwencji 12457321 nie da się zbudować pociągu, który miałby ostatni wyraz równy 7321, oszczędzamy więc czas. Co wtedy? Wtedy należy wrócić do q0 i powiększyć je o dodatkową cyfrę i powtórzyć całą procedurę, czyli wracając do przykładu wyżej teraz q0 będzie równe 5+7+3+2+1=18.

CIĄG Q SPEŁNIA ZAŁOŻENIA

Postępując z powyższą instrukcją w końcu dojdziemy do sytuacji, kiedy to:

qM <= ... <= q1 <= q0

Niestety to nie koniec. Po pierwsze wyznaczyliśmy tylko q0 graniczne. Dokładając kolejną liczbę z lewej strony otrzymamy nowe q0 i w rzeczywistości tak musimy zrobić, bo mamy zbadać przecież wszystkie podciągi. Zwróćmy uwagę, że dokładając cyfry z lewej strony w końcu dojdziemy do sytuacji, gdzie podciąg będzie równy wyjściowemu ciągowi K. Po drugie, co gorsze, musimy również zbadać pozostałe przypadki zmniejszając i-ty wyraz qi. Niemniej, procedury zawsze zostaną przerwane, jeśli zajdzie:

q'(i+1) > q'(i)

i dalsze badanie wyrazów nie ma sensu.

0 głosów
odpowiedź 10 stycznia 2017 przez morele123 Gaduła (4,790 p.)
No ja to bym po prostu wypisał wszystkie możliwe takie podciągi i policzył ile ich jest, a nawet nie wypisywał tylko sprawdzał czy taki ciąg istnieje. Sprawdzałbym poprzez porównywanie wszysttkich elementów.
komentarz 11 stycznia 2017 przez WWOTEX Mądrala (6,200 p.)
W ten sposób byłoby za prosto. To by dało rozwiązanie zbyt dużej złożoności. Nie umiem ci jej na szybko podać, ale wiem, że byłaby za duża. Potrzebne mi rozwiązanie liniowe lub kwadratowe ewentualnie, bo też powinno wejść. (ale założę się że jest rozwiązanie liniowe)
komentarz 11 stycznia 2017 przez morele123 Gaduła (4,790 p.)
Mam tego świadomość i nie widzę innego sposobu. Co nie znaczy, że go nie ma. Co do złożoności no to kwadratowa powinna być, jeśli nie mniejsza.

Podobne pytania

0 głosów
2 odpowiedzi 285 wizyt
pytanie zadane 23 listopada 2016 w Algorytmy przez Piotr Ponikwia Początkujący (330 p.)
0 głosów
1 odpowiedź 268 wizyt
pytanie zadane 21 czerwca 2022 w Algorytmy przez pasjonat_algorytmiki Pasjonat (19,540 p.)
+1 głos
3 odpowiedzi 879 wizyt

92,451 zapytań

141,261 odpowiedzi

319,073 komentarzy

61,853 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Akademia Sekuraka 2024 zapewnia dostęp do minimum 15 szkoleń online z bezpieczeństwa IT oraz dostęp także do materiałów z edycji Sekurak Academy z roku 2023!

Przy zakupie możecie skorzystać z kodu: pasja-akademia - użyjcie go w koszyku, a uzyskacie rabat -30% na bilety w wersji "Standard"! Więcej informacji na temat akademii 2024 znajdziecie tutaj. Dziękujemy ekipie Sekuraka za taką fajną zniżkę dla wszystkich Pasjonatów!

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...