Registreringsskyltar

Simon är chef för ett tophemligt spionnätverk. Problemet med att vara spion är att oftast är du samtidigt spionerad på. Simons fiender spionerar oftast på honom från deras bilar, men tyvärr vet han inte vilka bilar dom är i.

För varje bil han ser skriver han ner vilken registreringsskylt han såg. Om han sett en viss registreringsskylt väldigt ofta är risken stor att det det är en spion som spionerar på Simon. Därför har han gett dig i uppgift att implementera ett program som berättar hur många gånger han har sett en viss registringsskylt.

Tyvärr finns det en ytterligare komplikation. Simon kan ibland bara se en del av skylten, t.ex. när bilen han observerar åker förbi jättesnabbt. I det fallet vill han veta hur många gånger han sett en registeringsskylten som matchar den delvist observerade skylten.

En skylt består av exakt 6 siffror $0-9$. Vi säger att en skylt $X$ som Simon precis observerade matchar en tidigare observerad skylt $Y$, om för varje skylt som $Y$ hade kunnat vara, så är det också fallet att $X$ hade kunnat vara den skylten. Om Simon observerar skylten 00x000, så skulle den alltså inte matchat den tidigare skylten 00xx00, eftersom den senare hade kunnat vara 000100, men den nya skylten hade inte kunnat vara det. Däremot gäller det omvända, att 00xx00 hade matchat den gamla skylten 00x000.

Exempel

Säg att den första skylten Simon ser är 000000. Då är svaret $0$, eftersom Simon aldrig sett någon annan skylt. Nästa skylt är återigen 000000, som han tidigare sett. Svaret är då $1$. Den tredje skylten han ser är 001000, som han aldrig sett förr. Svaret är återigen $1$. Den fjärde skylten ser han bara delvist: 00x000. Denna kan matcha alla tidigare skyltar han sett, så svaret är $3$. Den femte skylten är också delvis: 00xx00. Återigen matchar denna samtliga tidigare skyltar, inklusive den partiella skylten han precis såg, så svaret är $4$. Den sista skylten Simon ser är 00x000, som matchar alla skyltar förutom den femte. Svaret är då $4$.

Uppgift

Givet alla skyltar (antingen partiella eller fullständiga) som Simon ser, avgör hur många av de tidigare skyltar han sett som den nya skylten matchar.

Du ska implementera detta som en funktion plate(P).

  • plate(P) - denna funktion anropas en gång för varje skylt Simon ser.

    • P: en vektor med exakt 6 element, där P[i] betecknar den $i$:te siffran på skylte. Om han inte såg den $i$:te siffran är detta värde istället $-1$. If he didn’t see the $i$:th digit, it will instead be $-1$.

    • Funktionen ska returnera antalet tidigare observerade skyltar som den nya skylten matchar.

Ett kodskelett som innehåller funktionen du ska implementera, tillsammans med en exempeldomare, finns tillgängligt på http://progolymp.se/uploads/kattis-attachments/regskylt.zip.

Delpoäng

Uppgiften består av ett antal grupper. Varje grupp ger ett visst antal poäng, och för att klara gruppen måste du klara samtliga testfall i gruppen.

Låt $P$ vara antalet anrop till plate.

Grupp

Poäng

Gränser

1

13

$P \le 100\, 000$, $P[i] \not= -1$

2

31

$P \le 100\, 000$, $P[i]$ är antingen $0$ eller $-1$

3

20

$P \le 1\, 000$

4

36

$P \le 100\, 000$

Indataformat

Exempeldomaren läser indata i följande format:

  • rad $1$: N - antalet skyltar.

  • rad $2$ till $2 + N - 1$: P[0] P[1] .. P[5]

Utdataformat

För varje skylt skriver domaren ut en rad med returvärdet av plate(P).

Sample Input 1 Sample Output 1
6
0 0 0 0 0 0
0 0 0 0 0 0
0 0 1 0 0 0
0 0 -1 0 0 0
0 0 -1 -1 0 0
0 0 -1 0 0 0
0
1
0
3
4
4