Polish version    English version  
  XVIII OI 2010/2011


 Aktualności
 O olimpiadzie
 Komitety
 XVIII OI 2010/2011
Terminarz
Zadania
II Etap
Przepisy
Wyniki I etapu
Wyniki II etapu
Dla zawodników
Przydatne zasoby
 Historia OI
 Książeczki OI
 Reprezentacja
 Obozy Olimpiady
 Galeria zdjęć
 Ciekawe odsyłacze
 OIG LiveCD
 IV OIG 2009/2010
 Historia OIG
 SIO
 MAIN
XI Olimpiada Informatyczna 2003/2004

Zadanie: pin

PIN-kod

Zawody I stopnia  
Plik źródłowy: pin.xxx (xxx=pas,c,cpp)
Limit pamięci: 32 MB

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