[Algorytmy] Nieosiągalna liczba

adambak
Użytkownik
Użytkownik
Posty: 1272
Rejestracja: 8 sty 2011, o 18:18
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 295 razy
Pomógł: 115 razy

[Algorytmy] Nieosiągalna liczba

Post autor: adambak »

Mam do rozwiązania bardzo ciekawy problem, lecz nie mogę wymyślić nic lepszego jak metoda siłowa, która zważywszy na wielkość danych wejściowych, odpada..

Wejście:
Liczba testów \(\displaystyle{ t<=1000}\). Dla każdego testu: liczba \(\displaystyle{ n<=1000}\), a następnie \(\displaystyle{ n}\) różnych liczb podanych w kolejności rosnącej.

Wyjście:
Najmniejsza liczba jakiej nie da się uzyskać z zsumowania dowolnych z podanych liczb..


Dla jasności przykład..

in:

Kod: Zaznacz cały

3 
7 
1 2 3 4 5 7 100 
5 
100 101 102 103 104 
3 
1 2 3
out:

Kod: Zaznacz cały

23
1
7

Podobno wzorcówka znajduje rozwiązanie dla każdego testu w \(\displaystyle{ O(n)}\).. Jakaś wskazówka, bo trochę utknąłem?
Afish
Moderator
Moderator
Posty: 2828
Rejestracja: 15 cze 2008, o 15:45
Płeć: Mężczyzna
Lokalizacja: Seattle, WA
Podziękował: 3 razy
Pomógł: 356 razy

[Algorytmy] Nieosiągalna liczba

Post autor: Afish »

Nie gwarantuję poprawności rozkminy, przy czym jeżeli nie ma w niej błędu, to jest to cały algorytm (więc czytasz na własną odpowiedzialność)
Ukryta treść:    
abc666

[Algorytmy] Nieosiągalna liczba

Post autor: abc666 »

Afish, to dobra rozkmina. W sumie wystarczy sprawdzać czy
k-1>max
gdzie k to wczytana teraz liczba a max to suma poprzednio wczytanych. (No i jeszcze dać if-a jak się nie zaczyna wszystko od jedynki).
adambak
Użytkownik
Użytkownik
Posty: 1272
Rejestracja: 8 sty 2011, o 18:18
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 295 razy
Pomógł: 115 razy

[Algorytmy] Nieosiągalna liczba

Post autor: adambak »

Fakt.. Nie wiem czemu zupełnie tego nie widziałem i nagle.. błysk! i wszystko jasne. Dziękuję Wam obu
ODPOWIEDZ