484 - The Department of Redundancy Department

All about problems in Volume 4. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

Problem 484 (Pascal)

Post by WR »

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]

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

Help and Criticla Input needed.

Post by _.B._ »

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 :o
Thanks in advance.

< Ding!, another WA! >

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

Post by Aleksandrs Saveljevs »

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

Post by _.B._ »

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:

Post by Aleksandrs Saveljevs »

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

Post by _.B._ »

Greetings Aleksandrs!.
I'll change the code to char by char right now :D
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 :D
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!!!!.

Post by _.B._ »

I got AC!!.
Sweet!!.
Thakns Aleksandrs, your help was priceless :D
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????

Post by WR »

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.

Post by _.B._ »

Greetings!.
Tried to test your program, but still don't understand it :o
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:

Post by Aleksandrs Saveljevs »

WR, hi.
Sorry for leaving you waiting for so long. :oops:

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!.. :wink:
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

Post by WR »

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

Post by WR »

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

Post by Ghust_omega »

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
Location: Bangladesh
Contact:

Post by Raiyan Kamal »

This problem can be solved in linear time very easily using array, you dont need stack or any andvanced data structure. Just take the input and on reaching the end, print the output.

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

Post by Ghust_omega »

thanks Raiyan i try another way to solve with array if someone can tell me how long ?
thanks in advance

Post Reply

Return to “Volume 4 (400-499)”