Page 13 of 16

10062 -WA- Tell Me the Frequencies!

Posted: Sun Jan 18, 2009 11:52 am
by sazzadcsedu
whats wrong with my code??
WA.

Code: Select all

 #include<stdio.h>
            #include<memory.h> 


              int main()



			  { 
				  char str[1002];
				  int i,a,k,min,j,dis_chr;
				  int count[256];
 
				 
				  while(gets(str))

				  { 
                       dis_chr=0; 
					   memset(count,0,sizeof(count));

					  for(i=0;str[i];i++)

					  { 
						  a=int(str[i]);
						  //printf("%d\n",a);

						  if(count[a]==0)
                             dis_chr+=1; 

						  count[a]+=1;

					  }

					//  printf("%d\n",);
                     
                        
					    for(i=1;i<=dis_chr;i++)
						{ 
							
					            min=1010;  
					    
					       for(j=256;j>=0;j--)

							{ 
								if(count[j]<min && count[j]>0)
								{ 
									min=count[j];
                                    k=j;  
								}

							}
                               printf("%d %d\n",k,count[k]);
							   count[k]=1100;
							  
                                  
						}

						 printf("\n");
				  }
				      return 0;
			  }
[\code]

Re: 10062 - Tell Me the Frequencies!

Posted: Mon Jan 19, 2009 5:01 am
by mf
sazzadcsedu wrote: for(j=256;j>=0;j--)

{
if(count[j]<min && count[j]>0)
{
min=count[j];
k=j;
}

}
In this section your program accesses count[256], which is undefined.

Also don't print the blank line at the end of output.

10062 - Tell Me the Frequencies!

Posted: Sat May 30, 2009 9:14 pm
by bm_anas
i m getting wa wa wa!
could anyone check and tell my errors.
here is my code-

#include<stdio.h>
#include<string.h>
#include<ctype.h>

int main()
{
int value[258],ascii[258],frq[130],i,j,k,tmp,start=0,len;
char input[1000];

while(gets(input)!=NULL)
{


if(start)
printf("\n");
start=1;

for(i=0;i<258;i++)
{
value=0;
ascii=i;
}

len=strlen(input);
for(i=0;i<len;i++)
value[input]++;

for(i=0,j=0;i<256;i++)
if(value)
{
ascii[j]=i;
frq[j++]=value;
}

for(i=0;i<j-1;i++)
for(k=0;k<j-1;k++)
if(frq[k]<=frq[k+1])
if((frq[k]<frq[k+1])||(ascii[k]<ascii[k+1]))
{
tmp=frq[k];
frq[k]=frq[k+1];
frq[k+1]=tmp;
tmp=ascii[k];
ascii[k]=ascii[k+1];
ascii[k+1]=tmp;
}
for(i=0;i<j;i++)
printf("%d %d\n",ascii,frq);

}

return 0;
}

Re: 10062 - Tips to solve this problem

Posted: Wed Jun 17, 2009 4:49 pm
by allenlam
How to solve
1. do a character count for each existing chars in the input string. Store the counting result in a map-like structure, mapping each char to its count. You get an array of the map structure.
2. sort the array by the char, in descending order.
3. sort the array by the count, in ascending order.
4. output the array according to the needed format.

How to sort
You need a sorting algorithm that is stable. It means the relative order of records with equal key is maintained.
Bubble sort is the most well-known and easy-to-implement stable sorting. Insertion sort and merge sort are stable and fast. Quick sort is unstable. Better avoid it in this problem. My AC solution is using bubble sort.

Test cases
input

Code: Select all

sort me by bubblesort
std::stable_sort(), std::list<T>.sort(), std::stable_partition().
output

Code: Select all

121 1
117 1
109 1
108 1
116 2
115 2
114 2
111 2
101 2
32 3
98 4

112 1
110 1
84 1
62 1
60 1
101 2
98 2
95 2
46 2
44 2
32 2
114 3
111 3
108 3
105 3
100 3
97 3
41 3
40 3
58 6
115 8
116 10
The blank line between cases issue has been talked hundred times in previous messages. I don't repeat it here.

Good luck.

Re: 10062 - Tell Me the Frequencies!

Posted: Mon Aug 24, 2009 4:52 pm
by etameem
this is my code:

Code: Select all

#include <iostream>

using namespace std;

int main()
{
string a;
char b[200];

int c,d,i,j,k,array[1000],l=0,count[1000],count2[1000],array2[1000],q=0,u,y,temp,temp2;

while(cin>>a)

{q=0;

for(i=0;a[i]!='\0';i++)
{
    array[i]=a[i];

}

for(y=0;y<i;y++)
    for(u=0;u<i-1;u++)
        {
            if(array[u]<array[u+1])
                {
                    temp=array[u];
                    array[u]=array[u+1];
                    array[u+1]=temp;



                    }



            }


for(j=0;j<i;j++)
count[j]=0;

for(j=0;j<i;j++)
    {
        if(array[j]!=0)
            {count[j]=1;
                for(k=j+1;k<i;k++)
                    {
                        if(array[j]==array[k])
                            {
                                count[j]++;
                                array[k]=0;

                                }


                        }


                }


        }
for(j=0;j<i;j++)
{
    if(count[j]!=0 && array[j]!=0)
        {
            count2[q]=count[j];
            array2[q]=array[j];
            q++;

            }



    }




for(y=0;y<q;y++)
    for(u=0;u<q-1;u++)
        {
            if(count2[u]>count2[u+1])
                {
                    temp=count2[u];
                    count2[u]=count2[u+1];
                    count2[u+1]=temp;

                    temp2=array2[u];
                    array2[u]=array2[u+1];
                    array2[u+1]=temp2;



                    }


            }




for(j=0;j<q;j++)
    {
        cout<<array2[j]<<" "<<count2[j]<<endl;



        }


  cout<<endl;
  //printf("\r");

}

    return 0;
    }



i am getting a WA. please help me with this...

Re: 10062 - Tell Me the Frequencies!

Posted: Tue Aug 25, 2009 1:10 am
by tryit1
uvatoolkit.com has program which accepts inputs and produces outputs for AC solution. You can generate some test cases and check it if it is the same as uvatoolkit.com. It doesn't have source , only it produces output for AC solution.

Re: 10062 - Tell Me the Frequencies!

Posted: Tue Aug 25, 2009 3:59 pm
by etameem
yes. i know about uvatoolkit.com and i have checked some input there. but can't find any difference between my output and uvatoolkit.com output. but then why i am getting WA ???

Re: 10062 - Tell Me the Frequencies!

Posted: Sun Nov 08, 2009 11:47 am
by noor_aub
I have change My Code. But Still W/A

My Code is

Code: Select all

#include<iostream>
//#include<conio.h>
using namespace std;
int flag=0;
void p(char a,int n,int cf[100],int c[100])
{
	int j=0,i=0;
	if(a=='\n')
	{
	 n++;
	 for(i=0;i<96;i++)
	 {
		for(j=0;j<95;j++)
		{
		   if(cf[j]>cf[j+1])
		   {
			  swap(cf[j],cf[j+1]);
			  swap(c[j],c[j+1]);
		   }
		   else if((cf[j]==cf[j+1]&&c[j]<c[j+1]))
		   {
			  swap(cf[j],cf[j+1]);
			  swap(c[j],c[j+1]);
		   }
		}
	 }
	 if(flag==1)
		  cout<<endl;
	 flag=1;
	 for(j=0;j<96;j++)
	 {
		if(cf[j]&&c[j])
		cout<<c[j]<<' '<<cf[j]<<endl;
		c[j]=0;
	 }
	 int b=0;
	}
}
int main()
{
   freopen("in.txt","r",stdin);
   char a;
   int i=0;
   int cf[100];
   for(i=0;i<100;i++)
      {
         cf[i]=0;
      }
   int n=0;
   while(1)
   {
	  int c[100];
	  if((a=getchar())==EOF)
	  {
		  a='\n';
		  p(a,n,cf,c);
		  break;
	  }
      i=0;
      int x=(int)a;
      if(x>=32&&x<=128)
      {
         i=x-32;
         //cout<<i;
         c[i]=i+32;
         cf[i]++;

      }
	  p(a,n,cf,c);
   }
   //getch();
   return 0;
}



I Have check uvatoolkit all my I/O are OK. But Still W/A
Thanks in advance.

Re: 10062 - Tell Me the Frequencies!

Posted: Fri Jan 29, 2010 7:31 am
by smilitude
I can't see why I am getting WA. I tried to read the older post and got more confused. Am I missing something or there is something stupid with the dataset?

Code: Select all

#include<cstdio>
#include<sstream>
#include<cstdlib>
#include<cctype>
#include<cmath>
#include<algorithm>
#include<set>
#include<queue>
#include<stack>
#include<list>
#include<iostream>
#include<fstream>
#include<numeric>
#include<string>
#include<vector>
#include<cstring>
#include<map>
#include<iterator>
using namespace std;

#define REP(i,n) for(int i=0; i<(n); i++)
#define ALL(x) x.begin(), x.end()
#define pb push_back
#define sz size()

typedef pair<int,int> pii;

bool comp( pii a, pii b ) {
    if( a.second == b.second ) return a.first > b.first;
    else return a.second < b.second;
}

int main() { 
    char line[1005];
    bool newln = 0;
    while( gets( line ) ) {
        char freq[500] = {}; 
        int len = strlen( line );
        REP(i,len) freq[ line[i] ] ++; 
        vector< pii > v;
        REP(i,500) if( freq[i] ) v.pb( make_pair( i, freq[i] ) );
        sort( ALL(v), comp );
        if( newln ) cout << endl; newln = 1;
        REP(i,v.sz) cout << v[i].first <<" " << v[i].second << endl;
    }
    return 0;
}


10062 - Tell Me the Frequencies!

Posted: Wed Dec 14, 2011 2:26 pm
by rage009
any body plz help me with my code


#include <stdio.h>

int main()
{
int i,j,k,n[100],ar[100],asc,temp,e=1;
char a[1005];
while(gets(a))
{
if(e!=1)
{
printf("\n");
}
e=0;
for(i=0;i<=100;i=i+1)
{
n=1;
}
n[0]=1;
k=0;
for(i=0;a;i=i+1)
{
if(a==1)
{
continue;
}
ar[k]=a;
for(j=i+1;a[j];j=j+1)
{
if(a==a[j])
{
n[k]=n[k]+1;
a[j]=1;
}
}
a=1;
k=k+1;
}
for(i=0;i<k;i=i+1)
{
for(j=0;j<k-1;j=j+1)
{
if(ar[j]<ar[j+1])
{
temp=ar[j];
ar[j]=ar[j+1];
ar[j+1]=temp;
temp=n[j];
n[j]=n[j+1];
n[j+1]=temp;
}
}
}
for(i=0;i<k;i=i+1)
{
for(j=0;j<k-1;j=j+1)
{
if(n[j]>n[j+1])
{
temp=ar[j];
ar[j]=ar[j+1];
ar[j+1]=temp;
temp=n[j];
n[j]=n[j+1];
n[j+1]=temp;
}
}
}
for(i=0;i<k;i=i+1)
{
if(ar>=33 && ar<=127)
{
printf("%d %d\n",ar,n);
}

}

}
return 0;
}

10062 - what's different???

Posted: Wed Mar 28, 2012 1:30 pm
by vril4296
i get ac when i use gets, but get wa when i use fgets
can anyone tell me why???
thanks~

code use fgets

Code: Select all

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main()
{
    char text[1001];    //Maximum length of each line is 1000.(max 1001,include '\n' or '\r')
    int ascii[95],length,i,j,n=0;  //The given lines will contain none of the first 32 or last 128 ASCII characters.((0~31,)32~127,total 95)
    while(fgets(text,1001,stdin)!=NULL){
        if(n>0)
            printf("\n");
        for(i=0;i<95;i++)
            ascii[i]=0;
        length=strlen(text)-1;
        for(i=0;i<length;i++)
            ascii[text[i]-32]++;
        for(i=1;i<=length;i++)
            for(j=94;j>=0;j--)
                if(ascii[j]==i)
                    printf("%d %d\n",j+32,i);
        n++;
    }
    return 0;
}
I'm sorry for my poor English!

Re: 10062 - what's different???

Posted: Thu Mar 29, 2012 12:58 am
by brianfry713
It could be because fgets includes the newline characters in the string but gets does not.

Re: 10062 - what's different???

Posted: Thu Mar 29, 2012 1:23 am
by vril4296
but I have considered about the newline

fgets : length=strlen(text)-1
gets : length=strlen(text)

Re: 10062 - what's different???

Posted: Fri Mar 30, 2012 3:06 am
by brianfry713
What would happen to your code if it's encoded in DOS format "\r\n" instead of UNIX "\n"? How about if there is no newline on the last line of the input but it ends with EOF?

From the problem description "Of course lines may end with ‘\n’ and ‘\r’ but always keep those out of consideration."

Re: 10062 - Tell Me the Frequencies!

Posted: Fri Jun 29, 2012 6:43 pm
by sith
Hello
Why am I getting WA?

Code: Select all

import java.io.*;
import java.util.*;

class Main {


    private static final char NEW_LINE = '\n';

    public static void main(String[] args) {

        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in), 1024 * 1024);
        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

        int intchr;
        try {
            Map<Integer, Entry> map = new HashMap<Integer, Entry>();
            while ((intchr = reader.read()) != -1) {
                if (intchr == NEW_LINE || intchr == '\r') {
                    if (map.isEmpty()) {
                        continue;
                    }
                    printResult(writer, map, true);
                    writer.write("\n");
                    map = new HashMap<Integer, Entry>();
                    continue;

                }

                Entry integer = map.get(intchr);
                if (integer == null) {
                    integer = new Entry(intchr);
                    map.put(intchr, integer);
                }
                integer.frequency++;
            }
            printResult(writer, map, false);
            writer.flush();
        } catch (IOException e) {

        }
    }

    private static void printResult(BufferedWriter writer, Map<Integer, Entry> map, boolean printLastN) throws IOException {
        Entry[] values = map.values().toArray(new Entry[map.size()]);

        Arrays.sort(values, new Comparator<Entry>() {
            public int compare(Entry o1, Entry o2) {
                int compare = o1.compareTo(o2);
                if (compare == 0) {
                    return o2.value - o1.value;
                }
                return compare;
            }
        });

        for (int i = 0; i < values.length; i++) {
            Entry value = values[i];
            writer.write(String.valueOf(value.value));
            writer.write(" ");
            writer.write(String.valueOf(value.frequency));

            if (i + 1 == values.length && !printLastN) {
                continue;
            }
            writer.write("\n");
        }

    }

    static class Entry implements Comparable<Entry> {
        int frequency;
        final int value;

        Entry(int value) {
            this.value = value;
        }


        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;

            Entry entry = (Entry) o;

            if (value != entry.value) return false;

            return true;
        }

        @Override
        public int hashCode() {
            return value;
        }

        public int compareTo(Entry o) {
            return frequency - o.frequency;
        }
    }

}