[C++] Poprawa kodu, algorytm na (stara) olimpiade

Przygotowuję się na II etap OIG i postanowiłem, że zrobię sobie zadania z zeszłego roku. No i mam zadanie o takiej mniej więcej treści:

Dany jest zbiór liczb A oraz liczba k. Zadaniem jest znalezienie najmniejszej wielokrotności liczby k, która nie należy do zbioru A.

No i nakodziłem coś takiego:

#include <iostream>
#include <set>

using namespace std;

typedef unsigned long long int ullint;

int main( int argc, char* argv[] ) {
	int size = 0; // rozmiar zbioru
	int k = 2; // liczba k
	cin >> size >> k;
	set< ullint > tab; // zbiór wszystkich liczb ( zbiór A z zadania )

	for( int i = 0; i < size; i++ ) {
		ullint tmp; // tymczasowa zmienna, która ma zostać dodana do zbioru
		scanf( "%llu", &tmp );
		tab.insert( tmp );
	}

	ullint mnoznik = 1; // która wielokrotność liczby k
	for( ;; mnoznik++ )
		if( tab.find( mnoznik * k ) == tab.end() ) // jeśli liczby nie ma w zbiorze
			break; // wyskakujemy z pętli

	cout << ullint(k * mnoznik); // wywalamy wynik na ekran
	return 0;
}

No i mi teraz dla pewnego wyniku wyrzuca zły wynik ( jest to za wielkie żeby tu wkleić, ale można pobrać stąd http://www.oi.edu.pl/oig/user.php/testy-min.tgz?op=get&id=1394 - test min15.in, a plik wynikowy min15.out ). Z góry dzięki.

Jejuuu to jest olimpiada, pomyśl że troszkę. Każdy element podziel przez 'k' - elementy niepodzielne odrzucaj, ilorazy elementów podzielnych zapisuj. Wynikiem jest najmniejsza liczba nienależąca do zapisanych ilorazów (oczywiście pomnożona przez 'k'). Również zamiast zwykłego set można o wiele lepszą strukturę danych zaimplementować do tego zadania. Można w drzewku zapisywać pełne zakresy, wynikiem jest górny brzeg pierwszego zakresu jeśli ten zaczyna się od 1, w przeciwnym wypadku wynikiem jest 1 (jednokrotność).

Wymyśliłem jeszcze lepszy algorytm. Mianowicie Podczas wczytywania sprawdzam czy liczba jest podzielna przez 'k' i czy wczytana liczba podzielona przez 'k' jest równa zmiennej mnoznik + 1 jeśli tak to zwiększamy zmienną mnoznik o 1. Następnie na wyjściu podajemy 'k' razy mnoznik. Tylko wynik dalej jest zły :/
Kod:

#include <cstdio>

typedef unsigned long long int ullint;

int main( int argc, char* argv[] ) {
	int size = 0;
	ullint k = 2;
	scanf( "%d %llu", &size, &k );
	ullint mnoznik = 0;

	for( int i = 0; i < size; i++ ) {
		ullint tmp;
		scanf( "%llu", &tmp );
		if( tmp % k == 0 && tmp / k == mnoznik + 1 )
			mnoznik++;
	}

	printf( "%llu", k * ( mnoznik + 1 ) );
	return 0;
}

PS
Ja się po prostu uczę na starych zadaniach, a nie proszę o napisanie na tegoroczną olimpiadę!!!

winerfresh napisał(a)

Wymyśliłem jeszcze lepszy algorytm. ... Tylko wynik dalej jest zły :/

Niestety nie najlepiej to wymyśliłeś.
Dajmy na to k=2. Mnożnik = 1.
Wczytujesz 4, kmnożnik <> 4 więc wczytujesz dalej.
Wczytujesz 2, kmnożnik == 2 więc zwiększasz mnożnik o jeden. Teraz k*mnożnik==4 i mamy błąd bo 4 już było.

Trzeba pamiętać wczytane liczby.
Np. dla k=2 i wczytywanych liczb
14, 3, 4, 2, 9, 5, 6, 16
odrzucasz liczby niepodzielne przez k, a pozostałe dzielisz przez k, co da:
7, 2, 1, 3, 8
W tak powstałym zbiorze wyszukujesz najmniejszą liczbę naturalną nie należącą do niego - 4 (4-krotność).
Jak pisałem wcześniej wystarczy pamiętać pełne zakresy, czyli w tym przypadku mamy 2 pełne zakresy:
1-3 oraz 7-8
Wynikiem jest górny brzeg pierwszego zakresu +1 (jeżeli zakres zaczyna się od 1) czyli 3+1=4 (4-krotność).
Jeśli pierwszy zakres nie zaczyna się od jeden, to wynikiem jest jednokrotność.

Takie zakresy można ładnie pamiętać w drzewku binarnym, gdzie każdy węzeł to numer pierwszego elementu w zakresie oraz długość zakresu.

Ja się po prostu uczę na starych zadaniach, a nie proszę o napisanie na tegoroczną olimpiadę!!!
Wiem. Na olimpiadzie nie wystarczy, że coś działa. Liczy się jak to działa.

Już zrobiłem, ale dalej na zbiorach bo bo drzew binarnych jeszcze nie podchodziłem :)