## 755 - 487-3279

Moderator: Board moderators

Thanks for help
I've fixed some bugs
But still WA

My Code

[pascal]Program p755;

Const MaxN = 110000;
LDig : Array['A'..'Z']of Integer = ( 2, 2, 2,
3, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6,
7, 0, 7, 7, 8, 8, 8, 9, 9, 9, 0 );

Type Point = Record i : Integer; s : String[7]; End;

Var T,tt,i : Integer;
p,j,k,c : Integer;
Amount : Array[1..MaxN]of Point;
Tmp : Array[0..MaxN]of Point;

Var S : String;
Ch : Char;
i : Integer;
begin
S:='';
While (Not Eoln) And (Not Eof) do begin
if Ch in ['0'..'9'] then S:=S+Ch;
if Ch in ['A'..'Z'] then S:=S+Ch;
end;
Ph.s := S;
Ph.i := 0;
for i := 1 to length(S) do
if S[i] in ['A'..'Z'] then
Ph.i := Ph.i * 10 + LDig[S[i]]
else
Ph.i := Ph.i * 10 + Ord(S[i])-Ord('0');
end;

Procedure Swap(Var A1, A2 : Point);
Var t : Point;
begin
t := A1;
A1 := A2;
A2 := t;
end;

Procedure Merge(left,middle,rigth : integer);
Var Ileft,Irigth,Cur,i : integer;
begin
Ileft:=left;
Irigth:=middle+1;
Cur:=0;
While True do begin
Cur:=Cur+1;
if Amount[Ileft].i<Amount[Irigth].i then begin
Tmp[Cur]:=Amount[Ileft];
Ileft:=Ileft+1;
end else begin
Tmp[Cur]:=Amount[Irigth];
Irigth:=Irigth+1;
end;
if Ileft=middle+1 then begin
for i:=Irigth to rigth do begin
Cur:=Cur+1;
Tmp[Cur]:=Amount[i];
end;
break;
end;
if Irigth=rigth+1 then begin
for i:=Ileft to middle do begin
Cur:=Cur+1;
Tmp[Cur]:=Amount[i];
end;
break;
end;
end;
for i:=1 to rigth-left+1 do
Amount[left+i-1]:=Tmp[i];
end;

Procedure MergeSort(left,rigth : integer);
Var middle : integer;
begin
if rigth-left<=0 then exit;
if rigth-left=1 then begin
if Amount[left].i>Amount[rigth].i then
Swap(Amount[left],Amount[rigth]);
exit;
end;
middle:=(left + rigth) div 2;
MergeSort(left,middle);
MergeSort(middle+1,rigth);
Merge(left,middle,rigth);
end;

begin
for tt:=1 to T do begin
for i:=1 to k do ReadPhone(Amount[i]);
j := 0;
MergeSort(1,k);
p := -1;
c := 0;
for i:=1 to k do
if Amount[i].i = p then begin
c := c + 1;
j := 1;
end else begin
if c >= 1 then Writeln(Amount[i - 1].S, ' ', c);
c := 1;
p := Amount[i].i;
end;
Writeln(Amount[k].S, ' ', c);
if j = 0 then Writeln('No duplicates.');
Writeln;
end;
end.[/pascal]
Revenger
Experienced poster

Posts: 132
Joined: Sun Apr 14, 2002 12:27 pm
Location: Russia

Ok, try this sample input.

1

11
0-0-0-0-0-0-0
00-0-0-0-0-0
000-0-0-0-0
0000-0-0-0
00000-0-0
000000-0
001-----------------------------------0000
001-------------------------------------------------0000
0---------00000--------1
0000--------------------------------001
---------------------------------1000000

The output should be as follows
<no blank line>
000-0000 6
000-0001 2
001-0000 2
<no blank line>

Good luck.

Ghost77 dimen
Learning poster

Posts: 67
Joined: Sun Sep 22, 2002 5:40 am
Location: Taiwan

Ops
I should find these bugs, but no with your help I have fixed all of them and get Accepted
Thank you!
Revenger
Experienced poster

Posts: 132
Joined: Sun Apr 14, 2002 12:27 pm
Location: Russia

My program works for all of these, but still WA, does anyone have any good valid cases?
Larry
Guru

Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City

### 755 - Time Limit

Hi,

I was just wondering if anybody could help me out with problem 755. I keep getting time limit exceeded.

I have tried storing the phone numbers in an array and doing a heapsort. Time Limit Exceeded...

I have tried a linked list using sorted insertion.
Time Limit Exceeded...

Could anybody please give me a hint... Thanks!
Wolfgang Haas
New poster

Posts: 2
Joined: Tue Oct 21, 2003 4:41 am

### 755 ,WA WHY ?????????????????:(

for some unknown reason i am getting wa in the problem . i guess i have handled the multiple input rightly . more over my program passed the sample input test given in the board . i did not used any array , more over put them in to a binary tree and made in order traversal . so why wa ? cant understand .

here is my code , \pliz check this for me .

#include<stdio.h>
#include<string.h>
[c]#include<stdlib.h>

char input[150];
char result[150];
int flag=0;
struct tnode {
char *word;
int count ;
struct tnode *left;
struct tnode *right;
};

struct tnode * talloc(void);
char * strdup(char *);
struct tnode * addtree(struct tnode*,char *);
void treeprint(struct tnode*);
void FreeTree(struct tnode *);

int Map(char ch){

if(ch=='A' ||ch=='B' ||ch=='C' )
return '2';
else if(ch=='D' ||ch=='E' ||ch=='F' )
return '3';
else if(ch=='G' ||ch=='H' ||ch=='I' )
return '4';
else if(ch=='J' ||ch=='K' ||ch=='L' )
return '5';
else if(ch=='M' ||ch=='N' ||ch=='O' )
return '6';
else if(ch=='P' ||ch=='R' ||ch=='S' )
return '7';
else if(ch=='T' ||ch=='U' ||ch=='V' )
return '8';
else if(ch=='W' ||ch=='X' ||ch=='Y' )
return '9';
else
return ch;

}

void create(char input[], char result[]){

int i,j ;
for(i=0,j=0;input[i]!='\0';){

if(input[i]=='-'){
i++;
continue;
}

else if(j!=3) {
result[j++]=Map(input[i++]);

}

if(j==3){
result[j++]='-';

}

}
result[j]='\0';

}

int main(){

struct tnode* root;
long int count ,mcount;

freopen("input.txt","r",stdin);

gets(input);
sscanf(input,"%ld",&mcount);
gets(input);

while(mcount>0){

root=NULL;

scanf("%ld",&count);
getchar();

while(count>0){

gets(input);
if(input[0]=='\0')
continue;
create(input,result);
count--;

}

treeprint(root);

if(flag==0)
printf("No duplicates.\n");
printf("\n");

FreeTree(root);

mcount--;
}

return 0;
}

struct tnode* addtree(struct tnode* p , char * w){
int cond;
char* temp;
if(p==NULL){

p=(struct tnode*) malloc( sizeof(struct tnode));
temp = (char*) malloc( strlen( w)+1);
strcpy( temp, w);
p->word = temp;
p->count=1;
p->left=p->right=NULL;

}
else if((cond=strcmp(w,p->word))==0)
p->count++;
else if(cond<0)
else

return p;

}

void treeprint(struct tnode *p){

if(p!=NULL){
treeprint(p->left);
if(p->count > 1){
printf("%s %d\n",p->word,p->count);
flag=1;
}

treeprint(p->right);
}
}

struct tnode *talloc(void){
return (struct tnode *) malloc(sizeof(struct tnode));
}

char * strdup(char *s){
char *p;
p=(char *) malloc(strlen(s)+1);

if(p!=NULL)
strcpy(p,s);
return p;

}

void FreeTree(struct tnode *t)
{
if(t==NULL)return;
if(t->left!=NULL)FreeTree(t->left);
if(t->right!=NULL)FreeTree(t->right);
free(t->word);
free(t);
}[/c]

HOLD ME NOW ,, I AM 6 FEET FROM THE EDGE AND I AM THINKIN.. MAY BE SIX FEET IS SO FAR DOWN

Experienced poster

Posts: 131
Joined: Thu Aug 14, 2003 10:23 pm
Location: BUET

sorry for my being stupid . i made a stupid mistake handling multiple input .all the other things are perfectly alright . and i did not make flag ==0 in the main function before calling the routine printtree();

thanx any way
Bye
HOLD ME NOW ,, I AM 6 FEET FROM THE EDGE AND I AM THINKIN.. MAY BE SIX FEET IS SO FAR DOWN

Experienced poster

Posts: 131
Joined: Thu Aug 14, 2003 10:23 pm
Location: BUET

### 755 WA

#include <iostream>
#include <algorithm>
using namespace std;
int main() {
unsigned long i,n;
long t;
unsigned time=1;
unsigned s,q;
bool tr=0;
bool all=0;
char p[7];
unsigned long *phone;
cin>>n;
phone=new unsigned long[n+1];
phone[n]=10000000;

for(i=0;i<n;i++) {
for(t=0;t<7;t++) {
cin>>p[t];
if(p[t]=='-')
t--;
}

for(t=0;t<7;t++) {
switch(p[t]) {
case 'A':
case 'B':
case 'C':
case '2':
p[t]=2;
break;
case 'D':
case 'E':
case 'F':
case '3':
p[t]=3;
break;
case 'G':
case 'H':
case 'I':
case '4':
p[t]=4;
break;
case 'J':
case 'K':
case 'L':
case '5':
p[t]=5;
break;
case 'M':
case 'N':
case 'O':
case '6':
p[t]=6;
break;
case 'P':
case 'R':
case 'S':
case '7':
p[t]=7;
break;
case 'T':
case 'U':
case 'V':
case '8':
p[t]=8;
break;
case 'W':
case 'X':
case 'Y':
case '9':
p[t]=9;
break;
case '1':
p[t]=1;
break;
case '0':
p[t]=0;
break;
}
}
phone[i]=1000000*p[0]+100000*p[1]+10000*p[2]+1000*p[3]+100*p[4]+10*p[5]+p[6];
}

sort(phone,phone+n);

for(i=1;i<=n;i++) {
if(phone[i]==phone[i-1]) {
tr=all=1;
time++;
}
else{
if(tr==1) {
s=phone[i-1]/10000;
q=phone[i-1]%10000;
if(s<100)
cout<<'0';
if(s<10)
cout<<'0';
cout<<s<<'-';
if(q<1000)
cout<<'0';
if(q<100)
cout<<'0';
if(q<10)
cout<<'0';
cout<<q<<' '<<time<<endl;
}
time=1;
tr=0;
}
}
delete[]phone;

if(all==0)
cout<<"No duplicates."<<endl;
return 0;
}

Yu Fan
New poster

Posts: 26
Joined: Thu Nov 13, 2003 3:52 am

This is a multiple input problem.

notice the blue check mark on the left of the
problem number?? that blue check mark
indicated the muliple input problem.

your code doesn't support the multiple input cases.
deddy one
Experienced poster

Posts: 120
Joined: Tue Nov 12, 2002 7:36 pm

if you use C language, the quicksort built in
function could easily save the day
deddy one
Experienced poster

Posts: 120
Joined: Tue Nov 12, 2002 7:36 pm

Thanx!!
I'd never noticed that there were checks beside the questions......

Yu Fan
New poster

Posts: 26
Joined: Thu Nov 13, 2003 3:52 am

### 755 WA

[c]#include <stdio.h>
#include <stdlib.h>

int ict = 0;

struct sort_tree
{
struct sort_tree *left;
int data[2];
struct sort_tree *right;
};

typedef struct sort_tree Sort_Tree;
typedef Sort_Tree *tree;

void insert(tree *Tree, int tel_input)
{
if (*Tree == NULL)
{
*Tree = malloc(sizeof(Sort_Tree));
if (*Tree != NULL)
{
(*Tree) -> data[0] = tel_input;
(*Tree) -> data[1] = 1;
(*Tree) -> left = NULL;
(*Tree) -> right = NULL;
}
else
printf("Error\n");
}
else
{
if (tel_input < (*Tree) -> data[0])
insert(&((*Tree) -> left), tel_input);
if (tel_input > (*Tree) -> data[0])
insert(&((*Tree) -> right), tel_input);
if (tel_input == (*Tree) -> data[0])
{
((*Tree) -> data[1]) = ((*Tree) -> data[1]) + 1;
ict++;
}
}
}

void sort(tree Tree)
{
int v;
char tel[7];
if (Tree != NULL)
{
sort(Tree -> left);
if (Tree -> data[1] > 1)
{
sprintf(tel, "%d", Tree -> data[0]);
for (v = 0; v < 3; v++)
printf("%c", tel[v]);
printf("-");
for (v = 3; v < 7; v++)
printf("%c", tel[v]);
printf(" %d\n", Tree -> data[1]);
}
sort(Tree -> right);
}
}

int main()
{
int c, n, v1, v2, v3, v4, tel_input;
char input[9999], tel[7];
tree root = NULL;

scanf("%d", &c);
for (v4 = 0; v4 < c; v4++)
{

scanf("%d", &n);
for (v1 = 0; v1 < n; v1++)
{
scanf("%s", input);
v2 = 0;
v3 = 0;
while (v2 < 7)
{
switch (input[v3])
{
case 'A':
case 'B':
case 'C':
tel[v2] = '2';
break;
case 'D':
case 'E':
case 'F':
tel[v2] = '3';
break;
case 'G':
case 'H':
case 'I':
tel[v2] = '4';
break;
case 'J':
case 'K':
case 'L':
tel[v2] = '5';
break;
case 'M':
case 'N':
case 'O':
tel[v2] = '6';
break;
case 'P':
case 'R':
case 'S':
tel[v2] = '7';
break;
case 'T':
case 'U':
case 'V':
tel[v2] = '8';
break;
case 'W':
case 'X':
case 'Y':
tel[v2] = '9';
break;
case '0':
case '1':
case '2':
case '3':
case '4':
case '5':
case '6':
case '7':
case '8':
case '9':
tel[v2] = input[v3];
break;
default:
v2--;
break;
}
v2++;
v3++;
}
tel_input = atoi(tel);
insert(&root, tel_input);
}

if (ict == 0)
printf("No duplicates.\n");
else
sort(root);

if (v4 != c - 1)
printf("\n");
}

return 0;
}[/c]

Thanks.
Rabby250
New poster

Posts: 1
Joined: Mon Jan 05, 2004 1:53 pm
Location: 219 Labs, NTU

Unfortunately the following C++ code takes almost 7 seconds.... for me it means this problem was set up only for C (printf/scanf addicted) or pascal fans....

[cpp]
#include <iostream>
#include <algorithm>
#include <string>
#include <map>

using namespace std;

int main(int argv, char **args) {

int casos = 0;
cin >> casos;
map<string,long> meuMapa;
for(int i=0;i!=casos;i++) {

if(i!=0) cout << endl;

int num;
cin >> num;

meuMapa.clear();

for(int z=0;z!=num;z++) {

string s;
cin >> s;

}

}

}

[/cpp]
technobug
Learning poster

Posts: 88
Joined: Sat Nov 15, 2003 6:41 pm
Location: Brasilien

i have just changed CIN to SCANF in the 3 input lines and it ran in 0.6 second. hmm.... shouldnt the time limit be extended to allow other competitors who use java/c++ functions to also get it right?
technobug
Learning poster

Posts: 88
Joined: Sat Nov 15, 2003 6:41 pm
Location: Brasilien

It's well known , that object stream as input is much slower than printf / scanf pair.
Your proposal means, that you have to create distinct rankings for every lnguage in which we can solve any problem. It's not fair for me ... Why people who solve problem in i.e. C, can be treated diffrent from C++ users ? Or Java users ?
I don't want to be offensive, but if you want to improve your time, sometimes you must change your coding style and code something in pure C or Pascal instead of C++ or Java Personally I solve all problems in C (excluding one or two). Pay attention that in some problems is written explicite, that you should use C-like input ...

Best regards
DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)
Dominik Michniewski
Guru

Posts: 828
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland

PreviousNext