You just made a new friend at an international puzzle conference, and you asked for a way to keep in touch. You found the following note slipped under your hotel room door the next day:
"Salutations, new friend! I have replaced every digit of my phone number with its spelled-out uppercase English representation ("ZERO", "ONE", "TWO", "THREE", "FOUR", "FIVE", "SIX", "SEVEN", "EIGHT", "NINE" for the digits 0 through 9, in that order), and then reordered all of those letters in some way to produce a string S. It's up to you to use S to figure out how many digits are in my phone number and what those digits are, but I will tell you that my phone number consists of those digits in nondecreasing order. Give me a call... if you can!"
You would to like to call your friend to tell him that this is an obnoxious way to give someone a phone number, but you need the phone number to do that! What is it?
Input
The first line of the input gives the number of test cases, T. T test cases follow. Each consists of one line with a string S of uppercase English letters.
Output
For each test case, output one line containing Case #x: y
, where x
is the test case number (starting from 1) and y
is a string of digits: the phone number.
Limits
1 ≤ T ≤ 100.
A unique answer is guaranteed to exist.
Small dataset
3 ≤ length of S ≤ 20.
Large dataset
3 ≤ length of S ≤ 2000.
Sample
Input | Output |
4 OZONETOWER WEIGHFOXTOURIST OURNEONFOE ETHER |
Case #1: 012 Case #2: 2468 Case #3: 114 Case #4: 3 |
解题思路:
由于这道题是给出的是字符串,并且是由任意数量的、0-9这10个数字的英文单词乱序组成的。那么最早的反应是动规?不过已经不会写了。但也因此找到了另一个好办法。
首先把"ZERO", "ONE", "TWO", "THREE", "FOUR", "FIVE", "SIX", "SEVEN", "EIGHT", "NINE"写出来,然后留下出现过的字母,它们是"EFGHINORSTUVWXZ",共15个。
现在我们来画一个表,它将表示每个单词所用的字母的个数及位置。
数字 | 单词 | 向量 |
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 | ||
E F G H I N O R S T U V W X Z | ||
0 | ZERO | (1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1) |
1 | ONE | (1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0) |
2 | TWO | (0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0) |
3 | THREE | (2, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0) |
4 | FOUR | (0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0) |
5 | FIVE | (1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0) |
6 | SIX | (0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0) |
7 | SEVEN | (2, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0) |
8 | EIGHT | (1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0) |
9 | NINE | (1, 0, 0, 0, 1, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0) |
如果我们将上面的10个向量组成矩阵的话,我们将得到一个10x15的矩阵,这里假定所得的矩阵为A。
接下来,由于是任意个数的0-9组合,我们可以将此题看为一个求解线性方程组xA=b的题目。x是一个1x10的列向量,其意义为每个数字的个数。b是一个1x15的列向量,其意义为每个字母的个数,且b可以通过给出的输入计算。
要求解xA=b,最简单的办法就是左右两边同时右乘A的逆。可惜这里A并非方阵,不能求逆矩阵。不过说来也巧,观察上表,正好有5列都只有唯一的一个1,它们分别是第2(G)、10(U)、12(W)、13(X)、14(Z)列,这也就意味着,只要其中一列所对应的字母出现了n次,那么唯一的那个1在行上所对应的数字一定出现了n次。比如第2列的G,在0-9的字母中,只有8, EIGHT, 才带有G,因此如果G出现了n次,那么EIGHT必定出现n次!
于是我们就可以先利用上述方法消去5列,得到一个10x10的矩阵,然后就可以利用如下式子来求解x了。(当然,在消去的过程中,b中相应字母的计数要减少)
xA = b xAA-1 = bA-1 x = bA-1
我们得到的新的矩阵D如下,
数字 | 单词 | 向量 |
0 1 3 4 5 6 7 8 9 11 | ||
E F H I N O R S T V | ||
0 | ZERO | (1 0 0 0 0 1 1 0 0 0) |
1 | ONE | (1 0 0 0 1 1 0 0 0 0) |
2 | TWO | (0 0 0 0 0 1 0 0 1 0) |
3 | THREE | (2 0 1 0 0 0 1 0 1 0) |
4 | FOUR | (0 1 0 0 0 1 1 0 0 0) |
5 | FIVE | (1 1 0 1 0 0 0 0 0 1) |
6 | SIX | (0 0 0 1 0 0 0 1 0 0) |
7 | SEVEN | (2 0 0 0 1 0 0 1 0 1) |
8 | EIGHT | (1 0 1 1 0 0 0 0 1 0) |
9 | NINE | (1 0 0 1 2 0 0 0 0 0) |
此时对D求逆,然后右乘于b,再在对应位置上加上刚才消去的5列,即可得出结果。
Solutions in J lang
#!/usr/bin/env jconsole NB. convert string to decimal atoi=: 10"_#. '0123456789'"_ i. ] NB. convert number to string itoa=: ":"0 NB. all possible letters letters=: 'EFGHINORSTUVWXZ' NB. inverted matrix inverted=: %. 10 10 $ 1 0 0 0 0 1 1 0 0 0 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 1 0 0 1 0 2 0 1 0 0 0 1 0 1 0 0 1 0 0 0 1 1 0 0 0 1 1 0 1 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 2 0 0 0 1 0 0 1 0 1 1 0 1 1 0 0 0 0 1 0 1 0 0 1 2 0 0 0 0 0 NB. handle significant columns significant=: 3 : 0 column=. > 0 { y number=. > 1 { y word=. > 2 { y value=. column { counter phonenumber=: value number } phonenumber positions=. letters i. word counter=: (value -~ counter {~ positions) positions } counter ) NB. Handle case case=: 3 : 0 NB. convert the number of cases into decimal cases=: atoi > 0 { y current=: 0 line=: 0 while. current ~: cases do. NB. take input, compute and print current=: >: current line=: >: line NB. setup counter counter=: 0 $~ # letters n=: > line { y NB. count times for each letter count=: (~. n) ;" 0 (+/ " 1 =n) NB. the number of letters, no duplication isolations=: 0 { $ count NB. fill in the counter index=: 0 while. index ~: isolations do. pair=: index { count counter=: (> 1 { pair) (letters i. > 0 { pair) } counter index=: >: index end. NB. initialize phonenumber phonenumber=: 10 $ 0 NB. there are some significant columns significant 2 ; 8 ; 'EIGHT' significant 10 ; 4 ; 'FOUR' significant 12 ; 2 ; 'TWO' significant 13 ; 6 ; 'SIX' significant 14 ; 0 ; 'ZERO' NB. solve the linear equation vector=: 1 10 $ 0 1 3 4 5 6 7 8 9 11 { counter partial=: vector (+/ . *) inverted phonenumber=: 0 { partial + 1 10 $ phonenumber NB. assemble the result number=: 0 result=: '' while. number ~: 10 do. count=: number { phonenumber while. count ~: 0 do. result=: result , itoa number count=: <: count end. number=: >: number end. NB. print the result result=: 'Case #' , (itoa current) , ': ' , result result (1!:2) 4 echo ; ":&.> '' end. ) NB. get data and handle them ] input=: <;._1 LF , stdin '' case input exit 0