[讨论]ZJU P1159求教！ — 编程爱好者社区

主题：[讨论]ZJU P1159求教！

morethan [专家分：10] 发布于 2007-11-06 16:27:00

[题目]：Businesses like to have memorable telephone numbers. One way to make a telephone number memorable is to have it spell a memorable word or phrase. For example, you can call the University of Waterloo by dialing the memorable TUT-GLOP. Sometimes only part of the number is used to spell a word. When you get back to your hotel tonight you can order a pizza from Gino's by dialing 310-GINO. Another way to make a telephone number memorable is to group the digits in a memorable way. You could order your pizza from Pizza Hut by calling their ``three tens'' number 3-10-10-10.

The standard form of a telephone number is seven decimal digits with a hyphen between the third and fourth digits (e.g. 888-1200). The keypad of a phone supplies the mapping of letters to numbers, as follows:

A, B, and C map to 2

D, E, and F map to 3

G, H, and I map to 4

J, K, and L map to 5

M, N, and O map to 6

P, R, and S map to 7

T, U, and V map to 8

W, X, and Y map to 9

There is no mapping for Q or Z. Hyphens are not dialed, and can be added and removed as necessary. The standard form of TUT-GLOP is 888-4567, the standard form of 310-GINO is 310-4466, and the standard form of 3-10-10-10 is 310-1010.

Two telephone numbers are equivalent if they have the same standard form. (They dial the same number.)

Your company is compiling a directory of telephone numbers from local businesses. As part of the quality control process you want to check that no two (or more) businesses in the directory have the same telephone number.

This problem contains multiple test cases!

The first line of a multiple input is an integer N, then a blank line followed by N input blocks. Each input block is in the format indicated in the problem description. There is a blank line between input blocks.

The output format consists of N output blocks. There is a blank line between output blocks.

Input

The input will consist of one case. The first line of the input specifies the number of telephone numbers in the directory (up to 100,000) as a positive integer alone on the line. The remaining lines list the telephone numbers in the directory, with each number alone on a line. Each telephone number consists of a string composed of decimal digits, uppercase letters (excluding Q and Z) and hyphens. Exactly seven of the characters in the string will be digits or letters.

Output

Generate a line of output for each telephone number that appears more than once in any form. The line should give the telephone number in standard form, followed by a space, followed by the number of times the telephone number appears in the directory. Arrange the output lines by telephone number in ascending lexicographical order. If there are no duplicates in the input print the line:

No duplicates.

Sample Input

1

12
4873279
ITS-EASY
888-4567
3-10-10-10
888-GLOP
TUT-GLOP
967-11-11
310-GINO
F101010
888-1200
-4-8-7-3-2-7-9-
487-3279

Sample Output

310-1010 2
487-3279 4
888-4567 3

本帖地址： http://bbs.pfan.cn/post/257242.html

回复列表（共6个回复）

沙发

morethan [专家分：10] 发布于 2007-11-06 16:33:00

我的程序如下：
program p1159;
var
   str1,str3:array[1..100000] of string;
   sum:array[1..100000] of word;
   str2,tmp1:string;
   i,j,s,k,m,n,tmp2,flag:word;
begin
     readln(n);
     for i:=1 to n do readln(str1[i]);
     for i:=1 to n do
     begin
          m:=length(str1[i]);
          str2:=str1[i];
          for j:=1 to m do
          begin
               case str2[j] of
               'A','B','C':str2[j]:='2';
               'D','E','F':str2[j]:='3';
               'G','H','I':str2[j]:='4';
               'J','K','L':str2[j]:='5';
               'M','N','O':str2[j]:='6';
               'P','R','S':str2[j]:='7';
               'T','U','V':str2[j]:='8';
               'W','X','Y':str2[j]:='9';
               end;
          end;
          for j:=1 to m do if str2[j]='-' then delete(str2,j,1);
          str1[i]:=str2;
          insert('-',str1[i],4);
     end;
     m:=length(str1[1]);flag:=0;
     for i:=1 to n-1 do
     begin
          s:=1;
          for j:=i+1 to n do
          begin
               if (length(str1[i])=m) and (str1[j]=str1[i]) then
               begin
                    s:=s+1;
                    insert('0',str1[j],m+1);
               end;
          end;
          if s<>1 then
          begin
               flag:=flag+1;
               sum[flag]:=s;
               str3[flag]:=str1[i];
          end;
     end;
     if flag<>0 then
     begin
          for i:=1 to flag-1 do
          begin
               str2:=str3[i];
               for j:=i to flag do
               begin
                    if str3[j]<str2 then
                    begin
                         tmp1:=str2;str2:=str3[j];str3[j]:=tmp1;
                         tmp2:=sum[i];sum[i]:=sum[j];sum[j]:=tmp2;
                    end;
               end;
               str3[i]:=str2;
          end;
          for i:=1 to flag do writeln(str3[i],' ',sum[i]);
     end
     else
         writeln('No duplicates');
end.

板凳

angwuy [专家分：2280] 发布于 2007-11-06 17:37:00

有译题吗?

3 楼

morethan [专家分：10] 发布于 2007-11-07 08:20:00

译文如下：（可能在翻译过程中有些出入，毕竟笔者水平有限）

描述
企业喜欢拥有让人难忘的电话号码。一种方法是将它拼写成一个难忘的词或词组。例如, 您能叫滑铁卢大学（University of Waterloo）为难忘的TUT-GLOP 。有时只有部分的数字被使用拼写词。当您今晚回到旅馆，您能通过拨310-GINO从Gino点一个薄饼。其它使电话号码难忘的方式是用一个难忘的方式对数字进行编组。您能点薄饼从PIZZA HUT 通过拨叫他们的"三十的'号3-10-10-10 。
电话号码的标准格式是七个十进制数以一个连字号在第三个和第四个数字(即888-1200 之间) 。电话的keypad 提供大写字母到数字的映射如下:
A 、B, 和C 地图到2
D 、E, 和F 地图到3
G、H，和I 映射到4
J 、K, 和L 地图到5
M 、N, 和O 地图到6
P 、R, 和S 地图到7
T 、U, 和V 地图到8
W 、X, 和Y 地图到9
没有映射的为Q 或Z。 Hyphens 不拨号, 和可能增加和被去除当有必要。TUT-GLOP 的标准格式是888-4567, 310-GINO 的标准格式是310-4466, 并且标准格式的3-10-10-10 是310-1010 。
有同样标准格式的二个电话号码是等效的。(他们拨同样数字。)
您的公司从事编写电话号码目录从地方企业。作为质量管理过程一部分您想要检查没有二个(或更多) 企业在目录有同样电话号码。
问题包含多个测试数据。
多重测试数据的第一行是一个整数N，后面接着一个空行跟N个测试数据块。每个数据块的格式如问题描述中所述，每个数据块之间有一空行。
[程序输入]：
输入将包括一个测试样本。输入的第一行指定在样本中电话号码的数量(<100,000)，为一个正整数单独在一行。余下各行列出电话号码, 以各个数字单独在一行。各个电话号码的组成由十进制数, 大写字母(除了Q 和Z) 和连字号。七个字符确切地说是数字或大写字母。
[程序输出]：
输出出现多次的各个电话号码，以标准电话格式输出，每个电话后面跟一个空格，再输出出现在目录中的次数，每行输出一个号码。输出的电话号码应按字典次序排序。
如果没有相同号码则输出:
No duplicates。

样例输入

12
4873279
ITS-EASY
888-4567
3-10-10-10
888-GLOP
TUT-GLOP
967-11-11
310-GINO
F101010
888-1200
-4-8-7-3-2-7-9-
487-3279

样例输出

310-1010 2
487-3279 4
888-4567 3

4 楼

angwuy [专家分：2280] 发布于 2007-11-07 18:07:00

转贴自衡阳八中论坛:
http://cache.baidu.com/c?word=zju%3B1159&url=http%3A//61%2E187%2E179%2E132%3A82/printpage%2Easp%3FBoardID%3D28%26ID%3D5915&p=882a9345cc9b52f612a5c7710c1480&user=baidu

ZJU1159简析

  这题的算法很简单，就是排序后扫描。关键是看到很多人TLE到天昏地暗，我就稍微提示一下。

  首先把输入数据处理一下，把它们变成数字。别小看这一步，这是最关键的。应为数字的比较是O(1)的复杂度而串的比较是O(length)的复杂度。

  这样算来，快排的复杂度是O(nlogn)，所以如果做串的排序就会多O(nlogn*(length-1))次比较。当然容易TLE。

  就是这么简单了。

  程序如下：

  program z1159(input,output);

const maxn=100000;
      letter:array[\'A\'..\'Z\']of byte=(2,2,2,3,3,3,4,4,4,5,5,5,6,6,6,7,7,7,7,8,8,8,9,9,9,9);
      min:array[1..7]of longint=(1,10,100,1000,10000,100000,1000000);

var nums:array[1..maxn]of longint;
    total,n:longint;
    {input,output:text;}

procedure swap(var a,b:longint);
var c:longint;
begin
    c:=a;a:=b;b:=c;
end;

procedure qsort(l,r:longint);
var mid,i,j:longint;
begin
    i:=l;j:=r;mid:=nums[(l+r)div 2];
    repeat
         while nums[i]<mid do inc(i);
         while nums[j]>mid do dec(j);
         if j>=i then
         begin
             swap(nums[i],nums[j]);
             inc(i);dec(j);
         end;
    until i>j;
    if i<r then qsort(i,r);
    if j>l then qsort(l,j);
end;

procedure init;
var i,times,value:longint;
    ch:char;
    s:string;
begin
    readln({input,}n);
    for i:=1 to n do
    begin
        times:=7;value:=0;
        repeat
             read({input,}ch);
             if ch in [\'0\'..\'9\'] then
             begin
                 inc(value,min[times]*(ord(ch)-ord(\'0\')));
                 dec(times);
             end
             else if ch in [\'A\'..\'Z\'] then
             begin
                 inc(value,min[times]*letter[ch]);
                 dec(times);
             end;
        until eoln{(input)};
        readln{(input)};
        nums[i]:=value;
    end;
    qsort(1,n);
end;

procedure main;
var i,tota,k:longint;
    s:string;
    found:boolean;
begin
    found:=false;
    i:=1;
    repeat
         tota:=1;
         while nums[i]=nums[i+1] do
         begin
             inc(i);
             inc(tota);
         end;
         if tota>=2 then
         begin
             found:=true;
             str(nums[i],s);
             while length(s)<7 do s:=\'0\'+s;
             writeln({output,}copy(s,1,3),\'-\',copy(s,4,4),\' \',tota);
         end;
         inc(i);
    until i>n;
    if not found then writeln({output,}\'No duplicates.\');
end;

begin
    {assign(input,\'z1159.in\');reset(input);
    assign(output,\'z1159.out\');rewrite(output);}
    readln({input,}total);
    repeat
         dec(total);
         readln{(input)};
         init;
         main;
         if total<>0 then writeln;
    until total=0;
    {close(input);close(output);}
end.

5 楼

morethan [专家分：10] 发布于 2007-11-08 09:04:00

有一个问题，他的这个程序不管是用TP还是FP，都出现“缺少有序类型”错误。
而我的则是堆栈溢出错误。

6 楼

angwuy [专家分：2280] 发布于 2007-11-08 18:02:00

这是衡阳八中的程序的一个特点,要把字符串的\'中的\删掉

我来回复

您尚未登录，请登录后再回复。点此登录或注册

主题：[讨论]ZJU P1159求教！

回复列表（共6个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

主题：[讨论]ZJU P1159求教！

回复列表 （共6个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

回复列表（共6个回复）