755 - 487-3279

[Revenger]

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;

Procedure ReadPhone(Var Ph : Point);
Var S : String;
Ch : Char;
i : Integer;
begin
S:='';
While (Not Eoln) And (Not Eof) do begin
Read(Ch);
if Ch in ['0'..'9'] then S:=S+Ch;
if Ch in ['A'..'Z'] then S:=S+Ch;
end;
Readln;
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
Readln(T);
for tt:=1 to T do begin
Readln;
Readln(k);
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]

[Ghost77 dimen]

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.

[Revenger]

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

[Larry]

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

[Wolfgang Haas]

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!

[Riyad]

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);
root=addtree(root,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)
p->left=addtree(p->left,w);
else
p->right=addtree(p->right,w);

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]

Thanx in advance ,
Riyad

[Riyad]

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();

so no need to reply
thanx any way
Bye
Riyad

[Yu Fan]

#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;
}

[deddy one]

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]

if you use C language, the quicksort built in
function could easily save the day

[Yu Fan]

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

[Rabby250]

[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]


Please help!
Thanks.

[technobug]

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]

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?

[Dominik Michniewski]

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