10062 - Tell me the frequencies!

[chocoholic]

I've searched past threads about 10062 but still couldn't figure out what's wrong with my code... I tried i/o from the problem and from some threads here, it's giving the right answer...

anyone can help? here's my code..

Code: Select all

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

struct insert
{
    char ascii;
    int frequency;
    struct insert *next;
};
typedef struct insert Insert;
typedef Insert *INSERT;

void addToList(INSERT head, INSERT newlist)
{
    INSERT current, temp;
    
    if(head->next==NULL)
    {
        head->next = newlist;
        return;
    }
    else
    {
        if((head->next->frequency > newlist->frequency) || ((head->next->frequency == newlist->frequency) && (head->next->ascii < newlist->ascii)))
        {
            temp = head->next;
            head->next = newlist;
            newlist->next = temp;
            return;
        }    
        else
        {
            current = head->next;
            do
            {
                if(current->next==NULL)
                {
                    current->next=newlist;
                    return;
                }    
                if((current->next->frequency > newlist->frequency) || ((current->next->frequency == newlist->frequency) && (current->next->ascii < newlist->ascii)))
                {
                    temp = current->next;
                    current->next = newlist;
                    newlist->next = temp;
                    return;
                }    
                else
                {
                    current = current->next;
                    if(current->next == NULL)
                    {
                        current->next = newlist;
                        return;
                    }    
                }    
            }while(1);
        }
    }
    return;        
}    
void printList(INSERT head)
{
    INSERT current, temp; char ascii; int freq;
    current = head->next;
    while(current!=NULL)
    {
        ascii = current->ascii;
        freq = current->frequency;
        temp = current->next;
        free(current);
        current = temp;
        printf("%d %d\n", ascii, freq);
    }
    return;
}
    
int main()
{
    char input[129], string[1002];
    int i;
    INSERT head, newinsert;
    
    head=(INSERT)malloc(sizeof(Insert));
    while(gets(string)!=NULL)
    {

        head->next = NULL;
        for(i=32;i<129;i++)
            input[i]=0;
            
        i=0;
        while(string[i]!='\0')
        {
            input[string[i]]++;
            i++;
        }
        for(i=32;i<129;i++)
        {
            if(input[i]>0)
            {
                newinsert = (INSERT)malloc(sizeof(Insert));
                newinsert->ascii = i;
                newinsert->frequency = input[i];
                newinsert->next = NULL;
                addToList(head,newinsert);
            }    
        }
        
        printList(head);
        printf("\n");
    }        
    return 0;
}    

[crispus]

I have same problem, I got an WA.
There is more case tests?

[tan_Yui]

Hi. chocoholic.
Your code was failed when it faced the long length input string.
If you are using other compiler, not same one as mine, no such happening might be occurred. But, please check it.

Best regards.

[Biks]

hi, i am getting presentation error in this problem.
will any one give me some special idea to avoid this.

[claudio25_2]

Hi, i solved problem 10062 "tell me the frequencies" and i think is correct but the judge says WA. help plz. First problem with IO with EOF

here's my code:

import java.io.*;

class Ej10062 {
static String readLine(int max) {
byte [] lin = new byte [max];
int lg = 0;
int car = -1;
try {
while (lg < max) {
car = System.in.read();
if (car == '\n' || car < 0) {
break;
}
if (car != 13) {
lin [lg++] += car;
}
}
}
catch (IOException e) {
return (null);
}
if (lg == 0) {
return null;
}
return (new String(lin, 0, lg));
}

public static void main(String[] args) {
Ej10062 myWork = new Ej10062();
myWork.Begin();
}
void Begin() {
String cad;
int[] cad_n;
char[] cad_c;
int tam, tam_n, cont = 1, n = 0;
char car;
boolean existe = false;
while((cad = readLine(1010)) != null) {
tam = 0;
cad_c = new char[127];
cad_n = new int[127];
n = 0;
while(tam != cad.length()) {
car = cad.charAt(tam);
tam_n = tam + 1;
while(tam_n != cad.length()) {
if(car == cad.charAt(tam_n))
cont++;
tam_n++;
}
if(n == 0) {
cad_c[0] = car;
cad_n[0] = cont;
n++;
}
else {
for(int i = 0; i < n;i++)
if(cad_c == car)
existe = true;
if(!existe) {
cad_c[n] = car;
cad_n[n] = cont;
n++;
}
}
tam++;
cont = 1;
existe = false;
}
int i, j, aux;
char aux1;
for(i = 0;i < n-1;i++)
for(j = i+1;j < n;j++) {
if(cad_n > cad_n[j]) {
aux = cad_n;
cad_n = cad_n[j];
cad_n[j] = aux;
aux1 = cad_c;
cad_c = cad_c[j];
cad_c[j] = aux1;
}
else
if(cad_n == cad_n[j]) {
if(cad_c < cad_c[j]) {
aux = cad_n;
cad_n = cad_n[j];
cad_n[j] = aux;
aux1 = cad_c[i];
cad_c[i] = cad_c[j];
cad_c[j] = aux1;
}
}
}
for(i = 0;i < n;i++)
System.out.print((int)cad_c[i]+" "+cad_n[i]+"\n");
}
}
}


HELPPPPPPP

[tan_Yui]

Hi, Biks.

A blank line should separate each set of output.

I think your code writes a blank line after the last input case.

Fix it to correspond to the output format like this.

67 1
66 2
65 3
<<blank line>>
49 1
50 2
51 3
<<EOF>>

[jjtse]

Hi,

I've tried submitting this program doing all sorts of new lines at the end. THis current version is the version that I think should be accepted. There is a new line after every case, except for the last case. It even skips extraneous newlines in the input file. It even skips new lines that may be at the end of the input file.

Still, I get PE. Does anyone have any insights?

Code: Select all

#include <iostream>
#include <string>

using namespace std;

#define max 96

int freq[max];

int usedF[max];
int usedA[max];

int counter = 0;

void filter(){
	counter = 0;
	
	for (int i=0; i<max; i++){
		if (freq[i] == 0)
			continue;
		usedF[counter] = freq[i];
		usedA[counter] = i;
		counter++;
		freq[i] = 0;
	}
}


void swap(int i, int j){
	int temp = usedF[i];	
	usedF[i] = usedF[j];
	usedF[j] = temp;
	
	temp = usedA[i];
	usedA[i] = usedA[j];
	usedA[j] = temp;
}


//bubble sort
void sort(){
	for (int i=0; i<counter-1; i++){
		for (int j=i+1; j<counter; j++){
			if (usedF[i] > usedF[j]){
				swap(i, j);			
			}
			else if (usedF[i] == usedF[j]){
				if (usedA[i] < usedA[j]){
					swap(i,j);
				}
			}
		}	
	}
}

void resetTable(){
	for (int i=0; i<max; i++){
		freq[i] = 0;
		usedF[i] = 0;
		usedA[i] = 0;
	}
}

void print(){
	int index;
	
	for (int i=0; i<counter; i++){
		cout<<usedA[i]+32<<" "<<usedF[i];//<<endl;
		usedA[i] = 0;
		usedF[i]= 0;
		if (i != counter-1)
			cout<<endl;
	}
}

int main(){

	string line;
	
	resetTable();
	
	getline(cin, line);
	while (line.length() == 0){
		getline(cin, line);
	}	
	while (!cin.eof() || line.length() != 0){
		resetTable();
		for (int i=0; i<line.length(); i++){
			char c = line[i];
			if ((int)c >= 32 && (int)c <=127){
				//cout << "came here"<< (int)c <<endl;
				freq[(int)c - 32] ++ ;
			}		
		}
		filter();
				
		sort();
		print();

		if (cin.eof())
			return 0;
		getline(cin, line);
		while (line.length() == 0 ){
			if (cin.eof())
				return 0;
			getline(cin, line);
		}
		cout << endl << endl;
	}



	return 0;
}

[ebrahim]

I've read other posts about 10062 P.E and I've tried all kind of newline and I don't print newline after the last testcase, but still I get P.E. It's running me mad although I know that P.E is accepted!

Code: Select all

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>

#include <list>
using namespace std;

//#define DEBUG 1

#if DEBUG
#define dump(fmt, x) fprintf(stderr, #x " = " fmt "\n", x)
#else
#define dump(fmt, x)
#endif

typedef list< pair<int, int> > L;

int main()
{
        bool first = true;
        while (!feof(stdin))
        {
                char ccc = getchar();
                if (ccc == EOF || ccc == '\r' || ccc == '\n')
                        break;
                else
                        ungetc(ccc, stdin);
                if (first)
                        first = false;
                else
                        putchar('\n');

                int count[128] = {0};
                for (;;)
                {
                        char c = getchar();
                        if (c == EOF)
                                break;
                        if (c == '\n' || c == '\r')
                        {
                                char cc = getchar();
                                if (cc != '\n' && cc != '\r')
                                        ungetc(cc, stdin);
                                break;
                        }
                        ++count[(int) c];
                }
                L l;
                for (int i = 32; i < 128; ++i)
                        if (count[i])
                                l.push_front(pair<int, int>(count[i], 128 - i));
                l.sort();
                for (L::iterator it = l.begin(); it != l.end(); ++it)
                        printf("%d %d\n", 128 - it->second, it->first);
        }
        return 0;
}

[N@$!M]

Shouldn't There Be ANY '\n' After The last output line?
I'm getting P.E. With this code :

Code: Select all

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

void main()
{	
	int freq[128],i,j,highest_freq,len,tag1=0,tag2;
	char arr[1001];

	while(scanf(" %[^\n]",arr)==1){
		if(tag1==0) tag1=1;
		else printf("\n");
		len=strlen(arr);
		for(i=0;i<128;i++){
			freq[i]=0;
		}
		highest_freq=0;
		for(i=0;i<len;i++){
			freq[arr[i]]++;
			if(highest_freq<freq[arr[i]]){
				highest_freq=freq[arr[i]];
			}
		}
		
		for(i=1;i<=highest_freq;i++){
			for(j=127;j>=32;j--){
				if(freq[j]==i){					
					printf("%d %d\n",j,i);
				}
			}
		}		
	}
}

[N@$!M]

I've Submitted The Code again Using 'gets()' instead of 'scanf(" %[^\n]")',.......AND GOT Accepted ! ''

[Observer]

That's because there are empty lines in the input, and empty lines are valid input cases!!

[ashipm01]

Thank you SO much, that was my problem too. I was quitting when an empty line was detected. I switched that and it was accepted. Where does it say that empty lines are valid input, I do not recall reading that? Thanks again for all your help.

[emotional blind]

N@$!M
remove your code now.

[stcheung]

I just got AC instead of PE and this is what I do.
(1) Always print a blank line after every set of output INCLUDING the last set of output. This means after spitting out the output the cursor should be on a separate line all by itself.
(2) If you see a blank line in the input, don't just ignore it. Instead, treat it as a separate test case where you have to print a newline for it. Then follow rule (1) to print another newline to separate it from the next test case. (Recognizing that a newline is needed when the input is a blank line is how I finally got AC)

For example, this is my output to a modified version of the sample input:

Code: Select all

AAABBC
[blank line]
122333

Code: Select all

67 1
66 2
65 3
[blank line]
[blank line]
49 1
50 2
51 3
[blank line with cursor]

[helloneo]

Input doesn't have a blank line.. because..

The given lines will contain none of the first 32 or last 128 ASCII characters

And just print a blank line except for the last one..