Forum matematyczne: miliony postów, setki tysięcy tematów, dziesiątki tysięcy użytkowników - pomożemy rozwiązać każde zadanie z matematyki https://matematyka.pl/
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..
Podobno wzorcówka znajduje rozwiązanie dla każdego testu w \(\displaystyle{ O(n)}\).. Jakaś wskazówka, bo trochę utknąłem?
[Algorytmy] Nieosiągalna liczba
: 21 sie 2011, o 13:08
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ść:
Sumujemy po kolei wczytane liczby i ustalamy przedział, w którym może się znaleźć następna (możemy dla wygody pominąć fakt, ze na wejściu mamy ciąg rosnący), aby zachowana była możliwość uzyskania sumy równej dowolnej liczbie od 1 do n (gdzie n jest sumą liczb). Jeżeli następna wczytana liczba nie trafia w pożądany przedział, to mamy odpowiedź - jest nią suma liczb + 1.
Przykład:
7
1 2 3 4 5 7 100
Wczytujemy jedynkę, zatem możemy poprzez różnorakie sumowanie uzyskać dowolną liczbę od 0 do 1. Następna oczekiwana liczba musi być w przedziale domkniętym 0-2. Wczytujemy kolejną liczbę, jest nią dwójka, więc wszystko jest okej. Aktualizujemy sumę - wynosi teraz 1 + 2 = 3, czyli możemy uzyskać dowolne liczby od 0 do 3. Kontynuujemy postępowanie aż do wczytania liczby 7. Teraz nasza suma wynosi 22, więc możemy uzyskać dowolne liczby od 0 do 22 włącznie. Następna liczba powinna być w przedziale 0 - 23. Niestety kolejną liczbą jest 100, więc mamy rozwiązanie - najmniejszą liczbą nie do uzyskania jest 23.
Przykład 2:
3
1 2 3
Tutaj wszystkie liczby nam pasują, więc po wczytaniu całego wejścia podajemy wynik, którym jest 7.
Przykład 3:
5
100 101 102 103 104
Tutaj pierwsza liczba powinna być w przedziale 0-1, ale niestety jest ona równa 100, więc od razu kończymy
[Algorytmy] Nieosiągalna liczba
: 21 sie 2011, o 13:13
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).
[Algorytmy] Nieosiągalna liczba
: 21 sie 2011, o 13:40
autor: adambak
Fakt.. Nie wiem czemu zupełnie tego nie widziałem i nagle.. błysk! i wszystko jasne. Dziękuję Wam obu