484 - The Department of Redundancy Department

[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._]

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

< Ding!, another WA! >

[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._]

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]

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!

[_.B._]

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._]

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]

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._]

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]

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

[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]

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]

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]

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]

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