루미 알고리즘

#1396플래티넘Number Plates

PO 2016 훈련 캠프코딩출제 Johan Sannemo영어 원문이 문제가 어렵다면 — 배우는 순서 보기

영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

Problem

Simon is in charge of a top secret spy network. Often when you're a spy, you are yourself spied upon. Simon's enemies usually spy on him from their cars, but unfortunately he doesn't know what cars they are in.

For every car he sees, he records its number plate on his cell phone. If he's been seeing a certain number plate very often recently, there's a good chance the car is being used to spy on Simon. Thus, he needs you to implement a program that tells him how many times he's seen a certain number plate.

However, there is an additional complication. Simon can sometimes only see a partial plate, for example when the car he is observing is moving very fast. In this case, he wants to know the total number of times he's seen all the plates that match the partial plate.

A number plate is a string of exactly 6 digits 0-9. We say that a new observed plate X matches a previously observed plate Y, if for every possible plate that Y could have been, it is also possible that X could be that plate. In particular, if Simon observes the new plate 00x000, it will not match a previously observed plate 00xx00, since the latter could have been 000100 while the new plate could not. However, if 00xx00 was the new plate and 00x000 was the old they would have matched.

Example

Say that the first plate Simon sees is 000000. The answer is 0, since he's never seen a plate before. The next plate is yet again 000000, which he has seen once before. Thus the answer is 1. The third plate he sees is 001000, which he has never seen, making the answer 0. The fourth plate he sees is only partial: 00x000, where x denotes a digit he didn't see. This can match both the plates he's previously seen, so in this case the answer is 3. The fifth plate he sees is also partial: 00xx00. Note that this partial plate matches partial plate Simon just saw - the partial plate should then be included as well (making the answer 4). Finally, Simon sees 00x000, which matches 4 previous plates (see the explanation above).

Task

Given all the plates (either partial or complete) that Simon sees, determine how many of the plates he've seen before could match the plate he just saw.

You should implement this as the function plate(P).

• plate(P) - this function will be called for every plate that Simon sees.

  • P: an array with exactly 6 elements, where P[i] denotes the i:th digit in the plate Simon saw. If he didn't see the i:th digit, it will instead be -1.
  • The function should return the number of previous plates that this one could match.

A code skeleton containing the function to be implemented, together with a sample grader, can be found at http://progolymp.se/uploads/kattis-attachments/regskylt.zip.

Subtasks

The problem consists of a number of subtasks. Each subtask gives some amount of points, and to pass the subtask you must pass all the test cases in the subtask.

Let P be the number of calls to plate.

SubtaskPointsLimits
113P ≤ 100000, P[i] ≠ -1
231P ≤ 100000, P[i] is either 0 or -1
320P ≤ 1000
436P ≤ 100000

Input format

The sample judge reads input in the following format:

  • line 1: N - the number of plates.
  • lines 2 to 2 + N - 1: P[0] P[1] .. P[5]

Output format

For every plate, the judge writes a line with the return value of plate(P).

예제

예제 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

출처 표기

출처: Programmeringsolympiaden 2016년 훈련 캠프 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.