484 - The Department of Redundancy Department
Moderator: Board moderators
Problem 484 (Pascal)
Hi,
as the input for this problem is arbitrarily long, I didn't use an array
but a linked list instead. Of course I checked the program
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}
type TLink = ^TData;
TData = record
value: TInt;
count: TInt;
pnter: TLink;
end;
procedure AddToList(var first,last: TLink; v: TInt);
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;
var p, root, next: TLink;
c, n, m, i: TInt;
ok: boolean;
begin
root := NIL;
c := 0;
while not eof(input) do begin
if eoln(input) then
readln(input)
else begin
read(input,n);
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
AddToList(root,next,n);
end;
end;
next := root;
while (next <> NIL) do begin
writeln(next^.value,' ',next^.count);
next := next^.pnter;
end;
end.
[/pascal]
as the input for this problem is arbitrarily long, I didn't use an array
but a linked list instead. Of course I checked the program
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}
type TLink = ^TData;
TData = record
value: TInt;
count: TInt;
pnter: TLink;
end;
procedure AddToList(var first,last: TLink; v: TInt);
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;
var p, root, next: TLink;
c, n, m, i: TInt;
ok: boolean;
begin
root := NIL;
c := 0;
while not eof(input) do begin
if eoln(input) then
readln(input)
else begin
read(input,n);
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
AddToList(root,next,n);
end;
end;
next := root;
while (next <> NIL) do begin
writeln(next^.value,' ',next^.count);
next := next^.pnter;
end;
end.
[/pascal]
Help and Criticla Input needed.
Greetings!.
A couple more of WAs for me...
I used arrays for this problem:
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
Thanks in advance.
< Ding!, another WA! >
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;
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

Thanks in advance.
< Ding!, another WA! >
-
- New poster
- Posts: 39
- Joined: Fri Nov 14, 2003 11:18 pm
- Location: Riga, Latvia
- 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
Thanks for the quick and useful response!.
Will you and anyone else please take a look to my code??.
[pascal]{ Bernardo E. L
-
- 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!
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.
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.
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.
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:
(Note that there are spaces after the numbers).
Output:
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
Output:
Code: Select all
-3 1
65535 2
0 1
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.
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.
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.
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.
_.
-
- 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!..
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.
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!
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!
-
- 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]
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]
-
- Experienced poster
- Posts: 106
- Joined: Thu Jan 29, 2004 12:07 pm
- Location: Bangladesh
- Contact:
-
- Experienced poster
- Posts: 115
- Joined: Tue Apr 06, 2004 7:04 pm
- Location: Venezuela