Każda karta bankomatowa ma swój 4-cyfrowy numer identyfikacyjny, tzw. PIN (ang. personal identification number). To, czy transakcja z użyciem karty zostanie wykonana, zależy od tego, czy numer karty i jej PIN są zgodne. Zgodność PIN-u i numeru karty sprawdza moduł HSM (ang. hardware security module). Moduł ten otrzymuje trzy parametry: numer karty x, PIN p oraz tablicę konwersji a (16-elementową tablicę liczb od 0 do 9, indeksowaną od 0 do 15). Moduł HSM działa w następujący sposób:

• szyfruje numer karty x, otrzymując liczbę y zapisaną szesnastkowo,
• z otrzymanej liczby y pozostawia tylko 4 pierwsze cyfry szesnastkowe,
• pozostawione cyfry szesnastkowe zamienia na dziesiętne za pomocą tablicy a (tzn. cyfra h zamieniana jest na a[h], gdzie h = A jest utożsamiane z 10, h = B z 11, h = C z 12, h = D z 13, h = E z 14 i h = F z 15),
• tak otrzymany 4-cyfrowy numer dziesiętny musi być identyczny z podanym PIN-em.

Standardową tablicą konwersji jest a = (0, l, 2, 3, 4, 5, 6, 7, 8, 9, 0, l, 2, 3, 4, 5). Załóżmy na przykład, że numerem karty jest x = 4556 2385 7753 2239, a po zaszyfrowaniu uzyskujemy numer szesnastkowy y = 3F7C 2201 00CA 8AB3. Żeby uzyskać 4-cyfrowy PIN: bierzemy pierwsze 4 cyfry szesnastkowe (3F7C) i kodujemy je za pomocą standardowej tablicy konwersji. Wynikiem jest PIN p = 3572. Niestety, nieuczciwy pracownik banku lub komputerowy włamywacz może uzyskać dostęp do modułu HSM i próbować odgadnąć PIN manipulując tablicą konwersji.

Zadanie

Napisz program, który będzie starał się odgadnąć PIN za pomocą zapytań do modułu HSM, przy czym może on zadać co najwyżej 30 zapytań.

Opis interfejsu

Twój program powinien komunikować się ze "światem zewnętrznym" jedynie poprzez funkcje udostępniane przez moduł hsm (hsm.pas w Pascalu i hsm.h w C/C++). Oznacza to, że nie może on otwierać żadnych plików, ani korzystać ze standardowego wejścia/wyjścia.

Przy każdym uruchomieniu Twój program powinien odgadnąć jeden PIN, zgodny z numerem karty znanej modułowi hsm, przy standardowej tablicy konwersji. Moduł hsm udostępnia funkcje: sprawdz oraz wynik. Ich deklaracje w Pascalu wyglądają następująco:

function sprawdz (pin:array of Longint, a:array of Longint):Boolean; 
procedure wynik (pin:array of Longint);

a w C/C++ następująco:

int sprawdz (int pin[], int a[]); 
void wynik (int pin[]);

Parametrami funkcji sprawdz są: badany PIN (w postaci 4-elementowej tablicy cyfr) oraz tablica konwersji (16-elementowa). Jej wynikiem jest wartość logiczna określająca, czy podany PIN jest zgodny z numerem karty, przy podanej tablicy konwersji. Twój program powinien co najwyżej 30 razy wywoływać funkcję sprawdz i dokładnie raz funkcję wynik. Wywołanie procedury wynik kończy działanie programu. Jej parametrem powinien być PIN zgodny z numerem karty, przy standardowej tablicy konwersji.

Żeby przetestować swoje rozwiązanie powinieneś napisać własny moduł hsm. Nie jest on jednak elementem rozwiązania i nie należy go przesyłać wraz z programem.

Przykład

Przykładowa interakcja programu z modułem hsm może wyglądać następująco:

sprawdz ((1,1,1,1), (0,0,1,1,0,1,0,1,0,0,0,0,1,1,0,1)) = true
sprawdz ((1,1,0,0), (0,0,0,1,0,1,0,0,0,0,0,0,0,1,0,1)) = true
sprawdz ((1,1,0,0), (0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,0)) = false
sprawdz ((1,0,0,0), (0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,0)) = true
sprawdz ((0,0,1,0), (0,0,1,0,0,0,0,0,0,0,0,0,1,0,0,0)) = false
sprawdz ((0,0,0,1), (0,0,1,0,0,0,0,0,0,0,0,0,1,0,0,0)) = true
wynik ((3,5,7,2))

Wersja do druku