#P13060. [GCJ 2020 #1C] Overrandomized

    ID: 12865 Type: RemoteJudge 20000ms 1024MiB Tried: 0 Accepted: 0 Difficulty: 4 Uploaded By: Tags>数学2020概率论Google Code Jam

[GCJ 2020 #1C] Overrandomized

题目描述

Note: Every time this statement says something is randomly chosen, it means "chosen uniformly at random across all valid possibilities, and independently from all other choices".

The company Banana Rocks Inc. just wrote a premium cloud-based random number generation service that is destined to be the new gold standard of randomness.

The original design was that a group of servers would receive a request in the form of a single positive integer M of up to U\mathbf{U} decimal digits and then respond with an integer from the range 1 through M, inclusive, chosen at random. However, instead of simply having the output written with digits 0 through 9 as usual, the servers were "overrandomized". Each server has a random subset of 10 distinct uppercase English letters to use as digits, and a random mapping from those letters to unique values between 0 and 9.

The formal description of the current situation is as follows: each server has a digit string D composed of exactly 10 different uppercase English letters. The digit string defines the mapping between letters and the base 10 digits: D's j-th character from the left (counting from 0) is the base 10 digit of value j. For example, if D were CODEJAMFUN then c would represent digit 0, o would represent digit 1 and n would represent digit 9. The number 379009 would be encoded as EFNCCN when using that digit string.

When receiving the i-th query with an integer parameter MiM_i, the server:

  • chooses an integer NiN_i at random from the inclusive range 1 through MiM_i,
  • writes it as a base 10 string with no leading zeroes using the j-th character of D (counting starting from 0) as the digit of value j, and
  • returns the resulting string as the response RiR_i.

We collected some data that we believe we can use to recover the secret digit string D from each server. We sent 10410^4 queries to each server. For each query, we chose a value MiM_i at random from the range 1 through 10U110^{\mathbf{U}} - 1, inclusive, and received the response RiR_i, a string of up to U\mathbf{U} uppercase English letters. We recorded the pairs (Mi,Ri)(M_i, R_i). As we were moving these records to a new data storage device, the values of all the integers MiM_i within the records of some servers became corrupted and unreadable.

Can you help us find each server's digit string D?

输入格式

The first line of the input gives the number of test cases, T\mathbf{T}. T\mathbf{T} test cases follow. Each test case contains the records for one server and starts with a line containing a single integer U\mathbf{U}, representing that 10U110^{\mathbf{U}} - 1 is the inclusive upper bound for the range in which we chose the integers MiM_i to query that server. Then, exactly 10410^4 lines follow. Each of these lines contains an integer Qi\mathbf{Q}_i (in base 10 using digits 0 through 9, as usual) and a string Ri\mathbf{R}_i, representing the i-th query and response, respectively. If Qi=1\mathbf{Q}_i = -1, then the integer MiM_i used for the i-th query is unknown. Otherwise, Qi=Mi\mathbf{Q}_i = M_i.

输出格式

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the digit string D for the server examined in test case x.



提示

Limits

  • 1T101 \leqslant \mathbf{T} \leqslant 10.
  • D\mathbf{D} is a string of exactly 10 different uppercase English letters, chosen independently and uniformly at random from the set of all such strings.
  • Mi\mathbf{M}_i is chosen independently and uniformly at random from the range 1 through 10U110^{\mathbf{U}} - 1, inclusive, for all i.
  • Ni\mathbf{N}_i is chosen independently and uniformly at random from the range 1 through Mi\mathbf{M}_i, inclusive, for all i.
  • Ri\mathbf{R}_i is the base 10 representation of Ni\mathbf{N}_i, using the j-th digit from the left of D\mathbf{D} (counting starting from 0) as the digit of value j, for all i.

Test Set 1 (9 Pts, Visible Verdict)

  • Qi=Mi\mathbf{Q}_i = \mathbf{M}_i, for all i.
  • U=2\mathbf{U} = 2.

Test Set 2 (10 Pts, Visible Verdict)

  • Qi=Mi\mathbf{Q}_i = \mathbf{M}_i, for all i.
  • U=16\mathbf{U} = 16.

Test Set 3 (17 Pts, Visible Verdict)

  • Qi=1\mathbf{Q}_i = -1, for all i.
  • U=16\mathbf{U} = 16.