10062 - Tell Me the Frequencies!

[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[i]=0;
ascii[i]=i;
}

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

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

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[i],frq[i]);

}

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[i]=1;
}
n[0]=1;
k=0;
for(i=0;a[i];i=i+1)
{
if(a[i]==1)
{
continue;
}
ar[k]=a[i];
for(j=i+1;a[j];j=j+1)
{
if(a[i]==a[j])
{
n[k]=n[k]+1;
a[j]=1;
}
}
a[i]=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[i]>=33 && ar[i]<=127)
{
printf("%d %d\n",ar[i],n[i]);
}

}

}
return 0;
}

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

}



[brianfry713]

Don't print a blank line at the end of the output.

[sith]

My solution doesn't print last line!

[brianfry713]

http://ideone.com/uh8sz

For the sample input, your output is:

Code: Select all

67 1
66 2
65 3

49 1
50 2
51 3



AC output is:

Code: Select all

67 1
66 2
65 3

49 1
50 2
51 3

[sith]

There is no extra line in my IDE(IntellijIDEa) for this solution, but I still get 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));
        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;
        }
    }

}


[brianfry713]

Try putting a newline at the end of the last input line.