10062 - Tell me the frequencies!

Sedefcho · Post by **Sedefcho** » Thu Jan 27, 2005 7:47 pm

I cover the test cases above and my program seems quite
simple. I haven't tried to achive efficiency. Just to make sure
the algorithm is logically correct.
But it seems it is not.

The program is in JAVA.

Sedefcho · Post by **Sedefcho** » Thu Jan 27, 2005 7:48 pm

But still I get WA.

Here is my JAVA code:

=============================================

class Main {

public static void main(String[] args){
String line = null;
int[] frequencies_arr = null;
char[] chars_arr = null;
while ( (line = readLn(1005)) != null ){
frequencies_arr = new int[96];
chars_arr = new char[96];
for (int i=0; i<line.length(); i++){
char ch = line.charAt(i);
if (ch == '\r' || ch == '\n') continue;
frequencies_arr[((byte)ch) - 32]++;
chars_arr[((byte)ch) - 32] = ch;
}
bubble_sort_arr(frequencies_arr, chars_arr);
int i = 0;
while (frequencies_arr == 0) i++;
for (int k=i; k<=frequencies_arr.length-1; k++){
System.out.println( ((byte)chars_arr[k]) + ( " " + frequencies_arr[k] ) );
}
System.out.println();
}
}

public static String readLn (int maxLg){
byte lin[] = new byte [maxLg];
int lg = 0, car = -1;

try{
while (lg < maxLg){
car = System.in.read();
if ((car < 0) || (car == '\n')) break;
lin [lg++] += car;
}
}catch (java.io.IOException e){
return (null);
}

if ((car < 0) && (lg == 0)) return (null); // eof
return (new String (lin, 0, lg));
}

private static void bubble_sort_arr(int[] v, char[] char_arr){

int n = v.length;
int int_tmp = 0;
char ch_temp = ' ';
for (int i=0; i< n-1; i++) {
for (int j=0; j<n-1-i; j++){
if (v[j+1] < v[j] ) {
int_tmp = v[j];
v[j] = v[j+1];
v[j+1] = int_tmp;
ch_temp = char_arr[j];
char_arr[j] = char_arr[j+1];
char_arr[j+1] = ch_temp;
}
}
}

for (int i=0; i< n-1; i++) {
for (int j=0; j<n-1-i; j++){
if ( ( v[j+1] == v[j] && char_arr[j+1] > char_arr[j] ) ) {
ch_temp = char_arr[j];
char_arr[j] = char_arr[j+1];
char_arr[j+1] = ch_temp;
}
}
}

}

}

=============================================

sanbinHo · Post by **sanbinHo** » Wed Feb 16, 2005 4:44 pm

I got a W.A
but I don't know why,please help me~~>"<
here is my code.

#include "iostream.h"
#include "stdlib.h"
#include "string.h"
struct output
{
int ascii;
int number;
};
void main()
{
int i,j;
char input[1001];
int length,index=0,buffer_ascii=0,buffer_number=0;
int answer[1001]={0};
output out[1001];
int test=0;
while(cin>>input)
{
length=strlen(input);

for(i=0;i<length;i++)
{
if(input>32 &&input<=128)
answer[input]++;
}
for(i=0;i<1001;i++)
{
if(answer!=0)
{
out[index].ascii=i;
out[index].number=answer;
index++;
}
}

for(i=0;i<1000 && out.number>0;i++)
{
for(j=i;j<1001 && out[j].number>0;j++)
{

if(out.number>out[j].number)
{
buffer_ascii=out.ascii;
buffer_number=out.number;
out.ascii=out[j].ascii;
out[i].number=out[j].number;
out[j].ascii=buffer_ascii;
out[j].number=buffer_number;
}

}
}

for(i=0;i<1000 && out[i].number>0;i++)
{
for(j=i;j<1001 && out[j].number>0;j++)
{

if(out[i].number==out[j].number)
{
if(out[i].ascii<out[j].ascii)
{
buffer_ascii=out[i].ascii;
buffer_number=out[i].number;
out[i].ascii=out[j].ascii;
out[i].number=out[j].number;
out[j].ascii=buffer_ascii;
out[j].number=buffer_number;
}
}

}
}

for(i=0;i<1001 && out[i].number>0;i++)
{
cout<<out[i].ascii<<' '<<out[i].number<<endl;
}

cout<<endl;
for(i=0;i<1001;i++)
answer[i]=0;
buffer_ascii=0,buffer_number=0;
length=0;
index=0;
for(i=0;i<1001;i++)
{
out[i].ascii=-1;
out[i].number=-1;
}

}
}

lonelyone · Post by **lonelyone** » Sun Feb 20, 2005 12:01 am

Code: Select all

#include<stdio.h>

void bubbleSort(int *table,int *index,int n)
{
    int i,j,t;
    for(i=1;i<n-1;i++)
    	for(j=2;j<=n-1;j++)
    		if(table[j]>table[j-1])
    		{
    		    table[j]=table[j]+table[j-1];
    		    table[j-1]=table[j]-table[j-1];
    		    table[j]=table[j]-table[j-1];
    		    index[j]=index[j]+index[j-1];
    		    index[j-1]=index[j]-index[j-1];
    		    index[j]=index[j]-index[j-1];
    		}    
}    

main()
{
    int table[129],index[129],copy_table[129];
    int i;
    char ch,first;
    
    while(scanf("%c",&first)!=EOF)
    {
        for(i=1;i<129;i++)
        {
        	table[i]=0;
        	index[i]=i;
        }   	

        table[(int)first]++;
        while((ch=getchar())!='\n')
            table[(int)ch]++;  
        for(i=0;i<129;i++)
        	copy_table[i]=table[i];
        bubbleSort(copy_table,index,129);
        for(i=129-1;i>=1;i--)
        	if(table[index[i]]!=0 && index[i]>=32 && index[i]<=128)  
       	    		printf("%d %d\n",index[i],table[index[i]]); 	
        //putchar('\n');	 	
    }    
}

How to get AC without PE?
Could someone teach me.
Thanks a million...^^

ibrahim · Post by **ibrahim** » Mon Feb 21, 2005 7:49 am

From the sample output we see

67 1
66 2
65 3
<=== A blank line
49 1
50 2
51 3

After output of every case there should be one new line (blank line).

lonelyone · Post by **lonelyone** » Tue Feb 22, 2005 8:15 am

ibrahim wrote:From the sample output we see
67 1
66 2
65 3
<=== A blank line
49 1
50 2
51 3
After output of every case there should be one new line (blank line).

Code: Select all

aaa
97 3
<==this is a blank line
abc
99 1
98 1
97 1
<==this is a blank line
cde
101 1
100 1
99 1
<==but this is also a blank line

if cde was the last case, then did there should be a blank line below 99 1?
I think there should not be any blank line below 99 1...
is it right...
but it is hard to do..
i have no idea to implement..
could anyone give me some ideas...
thank you ^^

ibrahim · Post by **ibrahim** » Tue Feb 22, 2005 1:24 pm

Yea, there should not any blank line.

You can do it very easyly.

Code: Select all

char ch,first;
   int flag=0;
    while(scanf("%c",&first)!=EOF)
    { 
        if(flag!=0)
            printf("\h");
       flag=1;

just make change in your code.

lonelyone · Post by **lonelyone** » Tue Feb 22, 2005 3:45 pm

ibrahim wrote:Yea, there should not any blank line.

You can do it very easyly.
Code: Select all
char ch,first;
   int flag=0;
    while(scanf("%c",&first)!=EOF)
    { 
        if(flag!=0)
            printf("\h"); // \n ??
       flag=1;
just make change in your code.

No..
I work out a solution, and it works...
but the online judge give me a compile error
Q______Q
oh my god...
you could excute my program
then you would know your idea doesn't work..
thank you very much
welcome your new solution anytime...^^

Code: Select all

#include<stdio.h> 
#include<conio.h>

void bubbleSort(int *table,int *index,int n) 
{ 
    int i,j,t; 
    for(i=1;i<n-1;i++) 
       for(j=2;j<=n-1;j++) 
          if(table[j]>table[j-1]) 
          { 
              table[j]=table[j]+table[j-1]; 
              table[j-1]=table[j]-table[j-1]; 
              table[j]=table[j]-table[j-1]; 
              index[j]=index[j]+index[j-1]; 
              index[j-1]=index[j]-index[j-1]; 
              index[j]=index[j]-index[j-1]; 
          }    
}    

main() 
{ 
    int table[129],index[129],copy_table[129]; 
    int i; 
    char ch,first; 
    int flag=0;
    
    while((first=getch())!=EOF) 
    { 
        if(flag!=0)
        	printf("\n");
       	if(first)
       		printf("%c",first);
       	
        for(i=1;i<129;i++) 
        { 
           table[i]=0; 
           index[i]=i; 
        }       

        table[(int)first]++; 
        while((ch=getchar())!='\n') 
            table[(int)ch]++;  
        for(i=0;i<129;i++) 
           copy_table[i]=table[i]; 
        bubbleSort(copy_table,index,129); 
        for(i=129-1;i>=1;i--) 
           if(table[index[i]]!=0 && index[i]>=32 && index[i]<=128)  
               printf("%d %d\n",index[i],table[index[i]]);      
        flag=1;      
    }    
}

ibrahim · Post by **ibrahim** » Tue Feb 22, 2005 7:00 pm

Ok

let me compare output of your code and my code AC (with out P.E).

Mohammad Mahmudur Rahman · Wed Feb 23, 2005 11:55 pm

Just a reminder, Online Judge doesn't allow the use of conio.h. You may try getchar().

ibrahim · Post by **ibrahim** » Thu Feb 24, 2005 4:32 am

if(flag!=0)
printf("\h"); // \n ??

Dear lonelyone, It's my typing mistake.

lonelyone · Post by **lonelyone** » Sat Feb 26, 2005 5:01 pm

ibrahim wrote:
if(flag!=0)
printf("\h"); // \n ??

Dear lonelyone, It's my typing mistake.

Code: Select all

#include<stdio.h> 

void bubbleSort(int *table,int *index,int n) 
{ 
    int i,j,t; 
    for(i=1;i<n-1;i++) 
       for(j=2;j<=n-1;j++) 
          if(table[j]>table[j-1]) 
          { 
              table[j]=table[j]+table[j-1]; 
              table[j-1]=table[j]-table[j-1]; 
              table[j]=table[j]-table[j-1]; 
              index[j]=index[j]+index[j-1]; 
              index[j-1]=index[j]-index[j-1]; 
              index[j]=index[j]-index[j-1]; 
          }    
}    

main() 
{ 
    int table[129],index[129],copy_table[129]; 
    int i; 
    char ch,first; 
    int flag=0;
    
    while(scanf("%c",&first)!=EOF) 
    { 
        if(flag!=0) 
            printf("\n"); 
        flag=1; 

        for(i=1;i<129;i++) 
        { 
           table[i]=0; 
           index[i]=i; 
        }       

        table[(int)first]++; 
        while((ch=getchar())!='\n') 
            table[(int)ch]++;  
        for(i=0;i<129;i++) 
           copy_table[i]=table[i]; 
        bubbleSort(copy_table,index,129); 
        for(i=129-1;i>=1;i--) 
           if(table[index[i]]!=0 && index[i]>=32 && index[i]<=128)  
                    printf("%d %d\n",index[i],table[index[i]]);            
    }    
}

ya~
i tried, but it still failed..
it's output just like following message...

Code: Select all

123
51 1
50 1
49 1
456
<==this is a blank line
54 1
53 1
52 1
789
<==this is a blank line
57 1
56 1
55 1
abc
<==this is a blank line
99 1
98 1
97 1
|<==the input cursor

but it should like below...
you could see the differences between them...

Code: Select all

123
51 1
50 1
49 1
<==this is a blank line
456
54 1
53 1
52 1
<==this is a blank line
789
57 1
56 1
55 1
<==this is a blank line
abc
99 1
98 1
97 1
|<==the input cursor

so...in first input, a blank line should be put after the output..
next, always put a blank line before the input...
but my program is hard to do so..
as you can see, i read a character first...
and after read, put a new line before the output...
that's the problem..
so, there's a solution, and i use getch() of conio.h...
cause, it can read a character and not do anything,
it means, no character could appear in the screen,
and then i could tell this character is equal to NULL or not,
if not then i put a charater and read following message...

but acm online judge can't accept conio.h, because it's not
ANSI standard...

please help me solve this problem...
thank to ibrahim and Mohammad Mahmudur Rahman

ibrahim · Post by **ibrahim** » Sat Feb 26, 2005 8:05 pm

Please check your code with file input. Because online judge take input from file.

And there you will get your mistake.

And another thing, you alreday got AC. So just forget about the PE.

lonelyone · Post by **lonelyone** » Sat Feb 26, 2005 8:47 pm

ibrahim wrote:Please check your code with file input. Because online judge take input from file.

And there you will get your mistake.

could you descript it in details..

And another thing, you alreday got AC. So just forget about the PE.

ok~ maybe you are right...hah...

Karthekeyan · Post by **Karthekeyan** » Thu May 19, 2005 10:17 am

here's my code for 10062....can neone temme y i get WA? like some xtreme cases....

Code: Select all

#include<iostream>
#include<vector>
using namespace std;
struct asdf
{
  char unique;
  int frequency;
};
int alreadyseen(vector<asdf> &seensymbols,char a)
{
  for(int i=0;i<seensymbols.size();i++)
    {
      if(seensymbols[i].unique==a)
	{
	  seensymbols[i].frequency++;
	  return 1;
	}
    }
  return 0;
}
void sort(vector<asdf> &freq)
{
  struct asdf temp;
  int n=freq.size();
  for(int i=0;i<n-1;i++)
    for(int j=i+1;j<n;j++)
      {
	if(freq[j].frequency<freq[i].frequency)
	  {
	    temp=freq[i];
	    freq[i]=freq[j];
	    freq[j]=temp;
	  }
	else if(freq[j].frequency==freq[i].frequency)
	  {
	    if(freq[j].unique>freq[i].unique)
	      {
		temp=freq[i];
		freq[i]=freq[j];
		freq[j]=temp;
	      }
	  }
      }
} 
main()
{
  char text[1000];
  while(cin>>text)
    {
      vector<asdf> seensymbols;
      for(int i=0;i<strlen(text);i++)
	{
	  if(alreadyseen(seensymbols,text[i])==0)
	    {
	      asdf temp;
	      temp.unique=text[i];
	      temp.frequency=1;
	      seensymbols.push_back(temp);
	    }
	}
      sort(seensymbols);
      for(int i=0;i<seensymbols.size();i++)
	{
	  int temp=seensymbols[i].unique;
	  cout<<temp<<" "<<seensymbols[i].frequency<<'\n';
	}
      cout<<'\n';
    }
}

OJ Board

10062 - Tell me the frequencies!

10062 W.A

10062 P.E.

10062 - WA - someone help