## 484 - The Department of Redundancy Department

Moderator: Board moderators

WR
Experienced poster
Posts: 145
Joined: Thu Nov 27, 2003 9:46 am

### Problem 484 (Pascal)

Hi,

as the input for this problem is arbitrarily long, I didn't use an array
with all available data. No errors found! So I need either more
test data or someone to check my program.

Sample input is preferred, so I will post the program
later if there's no response.

Thanks

No response, so program added Mar., 5th

[pascal]program p484(input, output);

{\$IFDEF ONLINE_JUDGE}
type TInt=integer;
{\$ELSE}
type TInt=longint;
{\$ENDIF}

TData = record
value: TInt;
count: TInt;
end;

begin
if (first = NIL) then begin
New(first);
last := first;
end
else begin
New(last^.pnter);
last := last^.pnter;
end;
last^.value := v;
last^.count := 1;
last^.pnter := NIL;
end;

c, n, m, i: TInt;
ok: boolean;
begin
root := NIL;
c := 0;
while not eof(input) do begin
if eoln(input) then
else begin
Inc(c);
if (c > 0) then begin
p := root;
ok := false;
while ((p <> NIL) and (ok = false)) do begin
if (p^.value = n) then begin
Inc(p^.count);
ok := true;
end;
p := p^.pnter;
end;
end;
if (ok = false) then
end;
end;
next := root;
while (next <> NIL) do begin
writeln(next^.value,' ',next^.count);
next := next^.pnter;
end;
end.
[/pascal]

_.B._
Experienced poster
Posts: 160
Joined: Sat Feb 07, 2004 7:50 pm
Location: Venezuela
Contact:

### Help and Criticla Input needed.

Greetings!.
A couple more of WAs for me...
I used arrays for this problem:

Code: Select all

``````type
MegaArr = array [0..100000] of longInt;
ArrParal = array [0..100000] of longWord;``````
Should I use more than 100000??.
Are longInt (-2147483648 .. 2147483647) and longWord (0..4294967295) not good enough for this problem??.
I've tried for only one line of input and several lines of input, and it seems to work fine... but the WAs don't seem to agree with me

< Ding!, another WA! >

Aleksandrs Saveljevs
New poster
Posts: 39
Joined: Fri Nov 14, 2003 11:18 pm
Location: Riga, Latvia
Contact:
I have this one solved in Pascal a long time ago. Longint is OK and the array size is around 100,000. The only thing I can suggest: try reading in a char by char way. Or rewrite it in C/C++.

_.B._
Experienced poster
Posts: 160
Joined: Sat Feb 07, 2004 7:50 pm
Location: Venezuela
Contact:

### Thanks!.

Greetings Aleksandrs!.
Thanks for the quick and useful response!.
Will you and anyone else please take a look to my code??.

[pascal]{ Bernardo E. L

Aleksandrs Saveljevs
New poster
Posts: 39
Joined: Fri Nov 14, 2003 11:18 pm
Location: Riga, Latvia
Contact:
Bernardo, hi.

1) I suggested reading in a char-by-char way, because there might be some spaces or blank lines in the end after the last number and Pascal might not detect the end of input properly.

2) The whole input file is one big sequence of numbers. You should not stop when end-of-line is reached.

3) Encontrado might fail if the number is 0. At the beginning, MArr is initialized to 0, so if the number is 0 and there were some numbers before, the condition "Encontrado:=(Arreglo [0] > 0) and (Arreglo [Con] = X)" holds. Obviously, not the thing you wanted, because when next number is input and it is not in the sequence, it will just overwrite that zero, because MArr[0] is not increased.

4) Thanks for eoln and eof! I thought only eoln(input) and eof(input) forms are allowed!

Good luck!
Last edited by Aleksandrs Saveljevs on Tue Apr 20, 2004 10:30 am, edited 1 time in total.

_.B._
Experienced poster
Posts: 160
Joined: Sat Feb 07, 2004 7:50 pm
Location: Venezuela
Contact:

### I will, thanks!.

Greetings Aleksandrs!.
I'll change the code to char by char right now
Thanks for all the corrections!.
And thanks for clarifying the "one line or several lines" issue to me.

By the way, I didn't know you could use (input) until several programs later, hehe.

Keep posting!.

_.B._
http://online-judge.uva.es/cgi-bin/Onli ... Info:42085

EDIT: ah!, thing about MArr [0], is that MArr [0] is my counter
That's why I initialized it with 0.

_.B._
Experienced poster
Posts: 160
Joined: Sat Feb 07, 2004 7:50 pm
Location: Venezuela
Contact:

### FINALLY!!!!.

I got AC!!.
Sweet!!.
Thakns Aleksandrs, your help was priceless
I suggest trying this I/O to whoever wants to try this problem:
Input:

Code: Select all

`````` -3
65535

65535

0
``````
(Note that there are spaces after the numbers).

Output:

Code: Select all

``````-3 1
65535 2
0 1``````

WR
Experienced poster
Posts: 145
Joined: Thu Nov 27, 2003 9:46 am

### And what about my pascal program????

Care to have a look at the first message of this thread?

Probably not as there hasn't been an answer for weeks.

Anyway, I've tried the last sample posted by _.B._ and my program
gives the correct output so I'm still stuck.

_.B._
Experienced poster
Posts: 160
Joined: Sat Feb 07, 2004 7:50 pm
Location: Venezuela
Contact:

### No idea.

Greetings!.
Tried to test your program, but still don't understand it
Are you receiving longInt input all the time??.
I used longInt input, and longWord counters.
And expected 100,000 numbers as input.
_.

Aleksandrs Saveljevs
New poster
Posts: 39
Joined: Fri Nov 14, 2003 11:18 pm
Location: Riga, Latvia
Contact:
WR, hi.
Sorry for leaving you waiting for so long.

Your code looks good to me. I still suggest reading in a char-by-char way. I think you should try it if it helped Bernardo. (Bernardo, did it?)

PS: Hey, you don't dispose anything!..
Last edited by Aleksandrs Saveljevs on Tue Apr 20, 2004 10:30 am, edited 1 time in total.

WR
Experienced poster
Posts: 145
Joined: Thu Nov 27, 2003 9:46 am
Thanks to Bernardo and Aleksandrs!

I know it's no good style not to dispose of list members but that's probably not the reason for WA.

It's more likely that the reason for this is the dirty input.

Reading char by char und using arrays may really be better.

Thanks again

And, Bernardo, sorry again for the 10041 bug!

WR
Experienced poster
Posts: 145
Joined: Thu Nov 27, 2003 9:46 am
Accepted at last!!!

I still use a linked list but now read the input on a character by character basis. So thanks again, Aleksandrs

Ghust_omega
Experienced poster
Posts: 115
Joined: Tue Apr 06, 2004 7:04 pm
Location: Venezuela

### 484 WA help

G
This is my source code I use stacks for the solution on this problem only i see if ist a new elemnt i Push else i add 1 to the frec ( frecuency ), I think that ist the input format, well hope that some one help me, and tell me whats wrong,
Thanks
[c]

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

typedef struct _nodo {
long int valor;
long int frec;
struct _nodo *sig;
} tipoNodo;

typedef tipoNodo *pNodo;
typedef tipoNodo *Pila;

void Push(Pila *pila, long int v);
long int Pop(Pila *pila);
long int contains(Pila *pila,long int v);

int main(){
Pila lista=NULL;
Pila aux=NULL;
long int n=0,x=0;

while(scanf("%ld",&n) == 1){
if(contains(&lista,n)==0){
Push(&lista,n);
lista -> frec =1;

}else{
while(1){
x = Pop(&lista);
Push(&aux,x);
if(x == n){
break;
}
}
aux -> frec = aux -> frec + 1;
while(aux !=NULL ){
x = Pop(&aux);
Push(&lista,x);
}

}

}
while(lista !=NULL ){
x = Pop(&lista);
Push(&aux,x);
}
while(aux !=NULL ){
printf("%ld %ld\n",aux -> valor,aux->frec);
x = Pop(&aux);

Push(&lista,x);
}
return 0;
}

void Push(Pila *pila, long int v) {
pNodo nuevo;

nuevo = (pNodo)malloc(sizeof(tipoNodo));
nuevo -> valor = v;
nuevo -> sig = *pila;
*pila = nuevo;
}

long int Pop(Pila *pila) {
pNodo nodo;
long int v;

nodo = *pila;
if(!nodo) return 0;
*pila = nodo->sig;
v = nodo->valor;
free(nodo);
return v;
}

long int contains(Pila *pila,long int v){
pNodo n = *pila;
long int r = 0;

while(1){
if(n == NULL){
break;
}
if(v == (long int )n -> valor){
r = 1;
break;
}
if(n -> sig == NULL)
break;
n = n -> sig;

}
return r;

}
[/c]

Raiyan Kamal
Experienced poster
Posts: 106
Joined: Thu Jan 29, 2004 12:07 pm