<Wyślij rozwiązanie> [0/100]

Funkcja

Limit pamięci: 32 MB

Dana jest pewna funkcja . Funkcja ta jest z początku nieznana i Twoim zadaniem jest wyznaczenie jej używając operacji z dostępnego modułu.

Wszystkie operacje działają na zbiorze testowym . Na początku . Do modyfikacji zbioru dostępne są operacje:

• dodaj() - dodaje element do zbioru ,
• usun() - usuwa element ze zbioru .

Do uzyskiwania informacji o funkcji służy operacja pytaj(), która mówi, czy .

Zadanie

Napisz program, który znajdzie funkcję używając możliwie najmniejszej łącznej liczby operacji.

Interfejs biblioteki

W tym archiwum udostępniona jest przykładowa implementacja biblioteki.

Biblioteka zawiera 5 funkcji/procedur.

• parametry(, ) - ta procedura powinna być wywoływana raz na początku programu w celu poznania parametrów testu. Na zmienne i , , zostaną przypisane odpowiednio rozmiar dziedziny funkcji i rozmiar przeciwdziedziny.
• dodaj() - dodaje do zbioru wartość .
• usun() - usuwa ze zbioru wartość .
• pytaj() - ta funkcja zwraca 1 jeśli i 0 w przeciwnym przypadku.
• wynik() - ta procedura powinna zostać wywołana raz na zakończenie programu podając funkcję . Funkcja reprezentowana będzie przez tablicę składającą się z wartości .

Twój program powinien wywołać jak najmniej razy funkcje dodaj, usun i pytaj. Poniżej podajemy nagłówki funkcji i sposoby kompilacji dla poszczególnych języków.

C/C++

Nagłówki funkcji:

void parametry(int *n, int *m);
void dodaj(int y);
void usun(int y);
int pytaj(int x);
void wynik(int *f);

Kompilacji programu wraz z modułem można dokonać za pomocą polecenia:

g++ -O2 -static fun.cpp funlib.cpp -lm
gcc -O2 -static fun.c funlib.c -lm

Pascal

Nagłówki funkcji i procedur:

procedure parametry( var n,m: longint );
procedure dodaj( y: longint );
procedure usun( y: longint );
function pytaj( x: longint ):longint;
procedure wynik( f: array of longint );

Do kompilacji można posłużyć się poleceniem:

ppc386 -O2 -XS fun.pas

Sprawdzanie

W każdym teście będzie ustawiony pewien sztywny limit na liczbę operacji. Program zaliczy dany test, jeżeli nie przekroczy limitu operacji oraz poda poprawną funkcję. W związku z tym, w większości testów nie ma konieczności używania minimalnej liczby operacji, aby przejść dany test. Testy i limity na liczbę pytań będą ustawione w ten sposób, aby programy zadające mniejszą liczbę pytań dostały więcej punktów.

Należy wysyłać sam program, a nie bibliotekę. Program będzie kompilowany z biblioteką. Nie wolno czytać ze standardowego wejścia, ani pisać na standardowe wyjście.

Przykład

W teście przykładowym przyjęte są parametry i , a funkcja przyjmuje wartości . Limit na liczbę pytań ustawiony jest na . Poniżej przykładowa interakcja programu z biblioteką.

wywołanie funkcji	wynik
parametry(n, m)
dodaj(0)
pytaj(0)	0
pytaj(1)	0
pytaj(2)	0
dodaj(1)
pytaj(0)	1
pytaj(1)	1
pytaj(2)	0
dodaj(2)
pytaj(2)	0
wynik(,,)

Program użył 10 operacji, mieszcząc się w limicie.

Autor zadania: Jakub Pawlewicz (na podstawie zadania z IOI 1995).

<Wyślij rozwiązanie> [0/100]