10062 - Tell me the frequencies!

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

[mf]

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.

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

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

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

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

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

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

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

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

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

[brianfry713]

It could be because fgets includes the newline characters in the string but gets does not.

[vril4296]

but I have considered about the newline

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

[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."

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

}