| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 | 1024 MB | 15 | 3 | 1 | 10.000% |
Tarkvarafirma Gold \& Silver Soft on arendamas uut graafikaprogrammi. Üks selle mooduleid on värvipaleti haldus. Programmi käivitudes on palett tühi. Edasi võib kasutaja lisada paletti uusi värve või küsida, milline paletis olevatest värvidest on antud värvile sarnaseim.
Värve esitatakse $K$-bitiste arvudena (väärtustega 0ドル$ kuni 2ドル^K-1$) ja kahe värvi sarnasuseks loetakse nende esitustes kokkulangevate bittide arvu. Näiteks $K = 5$ korral on värvide 00110 ja 10101 sarnasus 2ドル,ドル sest kokku langevad ainult vasakult teise ja kolmanda biti väärtused.
Kirjutada programmile värvipaleti haldamise moodul, milles on järgmised funktsioonid:
| Funktsioon | Kirjeldus |
|---|---|
void init(int k, int n) |
Paleti initsialiseerimine $k$-bitiste värvide kasutamiseks. Seda funktsiooni kutsutakse välja üks kord programmi töö alguses ja sellele järgnevad kokku $n$ add ja find väljakutset. |
void add(int c) |
Värvi $c$ lisamine paletti. |
int find(int c) |
Värvile $c$ paletist parima vaste leidmine. Funktsioon peab tagastama paletis olevate värvide hulgast värviga $c$ maksimaalselt sarnase. Kui maksimaalselt sarnaseid on mitu, tagastada ükskõik milline neist. Seda funktsiooni kutsutakse välja ainult siis, kui paletis on juba vähemalt üks värv. |
void done() |
Töö lõpp. Seda funktsiooni kutsutakse välja üks kord programmi töö lõpus. |
Tekstifaili esimesel real on värvide esitamiseks kasutatavate bittide arv $K$ (1ドル \le K \le 20$) ja operatsioonide arv $N$ (1ドル \le N \le 10^6$). Järgmisel $N$ real on igaühel täisarvud $T_i$ ja $C_i$ (0ドル \le C_i < 2^K$), kus $T_i = 1$ tähendab värvi $C_i$ lisamist paletti ja $T_i = 2$ värvile $C_i$ parima vaste leidmist paletist.
Tekstifaili väljastatakse hindamisprogrammi ja mooduli vahelise suhtluse logi.
2 3 1 1 2 0 2 1
init(2, 3) add(1) find(0) = 1 find(1) = 1 done()
3 5 1 0 1 7 2 1 1 1 2 1
init(3, 5) add(0) add(7) find(1) = 0 add(1) find(1) = 1 done()
C++17, C++20, C++17 (Clang), C++20 (Clang)