482 - Permutation Arrays

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

raysa
New poster
Posts: 40
Joined: Wed Dec 18, 2002 4:23 pm
Location: Indonesia

482 - Help me get a WA!

Post by raysa »

Hi,
Sorry to post my code here, but I really have nothing else to do to get out of this annoying RTE<SIGSEGV>. Off course, I did grow my array size but I don't think it would help at all. Someone, please gimme a hint to get a WA...

[cpp]---CODE WAS CUT---[/cpp]

Thank's :oops:
Raysa
Last edited by raysa on Wed Apr 09, 2003 8:46 am, edited 1 time in total.

turuthok
Experienced poster
Posts: 193
Joined: Thu Sep 19, 2002 6:39 am
Location: Indonesia
Contact:

Post by turuthok »

Hello Raysa, this problem has multiple-input format. Are you sure you're handling that correctly ?

-turuthok-
The fear of the LORD is the beginning of knowledge (Proverbs 1:7).

raysa
New poster
Posts: 40
Joined: Wed Dec 18, 2002 4:23 pm
Location: Indonesia

Post by raysa »

I thought so. I took the number of cases first before continue processing input. Is there anything wrong with my m_input handling in my code above? Can m_input cause an RTE?

Regards,
Raysa

turuthok
Experienced poster
Posts: 193
Joined: Thu Sep 19, 2002 6:39 am
Location: Indonesia
Contact:

Post by turuthok »

Raysa, you should be careful because there will be a blank line between consecutive test-cases.

http://acm.uva.es/problemset/minput.html

-turuthok-
The fear of the LORD is the beginning of knowledge (Proverbs 1:7).

raysa
New poster
Posts: 40
Joined: Wed Dec 18, 2002 4:23 pm
Location: Indonesia

Post by raysa »

Just found my mistake:
I used same array of char for the index and the elements. I've NULL-ed the array after inputting the index, but forgot doing so for the elements... It surely messed up the next inputs and cause an RTE. AC now...

Anyway, thank's for your help, Turuthok! Really apreciate it... :lol:

**Raysa**

Junayeed
New poster
Posts: 50
Joined: Sat Oct 26, 2002 9:02 am
Location: Dhaka, Bangladesh

Post by Junayeed »

Please help me with some input. I am trying to solve this. But i am getting WA. Pls help me.

Thanks.

Syed Mubashshir Husain
New poster
Posts: 9
Joined: Wed Apr 02, 2003 10:28 am

482 RTE

Post by Syed Mubashshir Husain »

Hi,

I got RTE in this problem.
My code (partial) given below.


scanf("%ld",&ar[0]);
gets(ch); i = 1; t = 0;
t = strtok(ch," "); ar = atol(t); i++;
while(t != NULL)
{
t = strtok(NULL," ");
if(t == NULL) break;
ar = atol(t); i++;
}

or

scanf("%ld",&ar[0]);
gets(ch); i = 1; t = 0;
p = 0; l = strlen(ch);
while(p < l)
{
sscanf(&ch[p],"%ld",&ar);
p += long(floor(log10(ar)) + 2); i++;
}

Is there any thing wrong using scanf(), after that gets.

---
SMH

User avatar
saiqbal
New poster
Posts: 36
Joined: Wed Aug 07, 2002 4:52 pm
Location: Dhaka, Bangladesh
Contact:

Post by saiqbal »

your code seems pretty wiered to me. i solved the problem in quite straight forward way. the process i followed is:
1. i made a structure array with an integer for index and a char array for the floating number.
2. i read first line and counted the number of input in that line and store them in the array as indices. suppose i got n inputs in the first line.
3. i then read n floating point number as string and store them in the array with theire indices.
4. i sorted the array according to the index value.
5. i printed all the stored floating point number.

thats it. i used qsort to sort the array. char array for float is important bcoz i need to print number exactly as the input.
hope it might help.
good luck
-sohel

ACoimbra
New poster
Posts: 14
Joined: Thu Apr 10, 2003 1:59 pm
Location: Coimbra, Portugal
Contact:

old solution

Post by ACoimbra »

Well, I solved that problem in Pascal quite long ago, I think I just used one or two arrays, and then just store the items in the correct order

InOutMoTo
New poster
Posts: 18
Joined: Sun Aug 10, 2003 12:47 pm

Post by InOutMoTo »

saiqbal wrote: following code might help:
[c]
typedef struct
{
int index;
char num[20];
} array;

array a[100000];
[/c]

good luck :)
-sohel
I am afraid this structure array's size still not big enough...
I just got AC by changing my arraysize
output[10000][20] --> output[10000][55]
So the judge input must have some number that is very very long and cause RTE.

Hope this will help. :)

Best recards

titid_gede
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut

Post by titid_gede »

just read another thread for this problem. size will not greater than 2000. be careful that there could be many spaces between numbers, so that each line could be more than 1000000 chars.
i think 20 characters per number is ok..
Kalo mau kaya, buat apa sekolah?

FaisalBD
New poster
Posts: 3
Joined: Thu Nov 27, 2003 10:24 am
Location: Dhaka, Bangladesh

482-Permutation Array WA

Post by FaisalBD »

Hello every1

To solve this i took two input in string. Using sscanf i pick the int or float number. The float number is kept in a structure. Sort the float number than print it according to problem.

Is the algorithm correct?

Code: Select all


#define max 100000
struct num           // for floating number
{
  char S[100];
  double n;
} ar[max],temp;

/* pick the number from string */

while(p != NULL)
    {
      sscanf(p,"%[-.0123456789]s",ch1);
      p += strlen(ch1);
      aa = atof(ch1);
      strcpy(ar[j].S,ch1);
      ar[j].n = aa; j++;
      if(p[0] == ' ') p++;
      else break;
    }

pavelph
Learning poster
Posts: 57
Joined: Wed Dec 10, 2003 7:32 pm
Location: Russia, Saint-Petersburg

Post by pavelph »

Are you know that this problem has multiple input!?
I know this, but have WA. Can somebody help me why it gets WA???
[pascal]
program acm482 (input, output);
const c = 1000000;
var ind: array [1..c] of integer;
zn: array [1..c] of string;
i, j, n, k: integer;
ch: char;
begin
{ assign(input, 'input.txt');
reset(input);
}
readln(k);
readln;
for j:=1 to k do begin
n:=0;
while not eoln do begin
inc(n);
read(ind[n]);
end;
readln;
for i:=1 to c do zn:='';
i:=0;
while i<>n do begin
read(ch);
if ch<>' ' then inc(i);
while (ch<>' ') and (ch<>#26) and (ch<>#13) do begin
zn[ind]:=zn[ind]+ch;
read(ch);
end;
end;
for i:=1 to n do
writeln(zn);
readln;
writeln;
end;
end.
[/pascal]

FaisalBD
New poster
Posts: 3
Joined: Thu Nov 27, 2003 10:24 am
Location: Dhaka, Bangladesh

Post by FaisalBD »

Hello
I have Consider the multiple input in my code.

Thax

mohiul alam prince
Experienced poster
Posts: 120
Joined: Sat Nov 01, 2003 6:16 am
Location: Dhaka (EWU)

482 (RT)about help(permutation arrays)

Post by mohiul alam prince »

i can not understand what is my problem.i got run time error.any boby can
help me
this is my source cord

[cpp]
#include<stdio.h>
#include<string.h>
#include<stdlib.h>

struct node
{
long x;
double y;
char str2[10000];
};

node A[100000];

int sort_function( const void *a, const void *b);


int sort_function( const void *a, const void *b)
{
long dif;
node *M,*N;

M=(node *) a;
N=(node *) b;
dif=(M->x-N->x);
if(dif==0)return 0;
if(dif>0)return 1;
if(dif<0)return -1;
}

char a[100000],b[100000],tc[100000];

int main()
{
long l,l1;
long p,t,xx,g,c,i,tt,ii,j,kk,k,v;

while(scanf("%ld\n",&tt)==1)
{
for(t=0;t<tt;t++)
{
gets(a);
gets(b);
l=strlen(a);
l1=strlen(b);
g=0;i=0;kk=0;
for(ii=kk;;ii++)
{
if(i>=l-1)break;
sscanf(a,"%ld",&v);
A[g].x=v;
g++;p=0;
for(i=0;i<l;i++)
{
if(p==1)break;
if(a!=' ')
{
a=' ';
for(j=i+1;j<l;j++)
{
if(a[j]==' '){kk=j;p=1;break;}
a[j]=' ';
}
}
}
}
c=0;i=0;kk=0;
for(ii=kk;;ii++)
{
if(i>=l1-1)break;
sscanf(b,"%s",tc);
sscanf(b,"%ld",v);
A[c].y=v;
strcpy(A[c].str2,tc);
c++;p=0;
for(i=0;i<l1;i++)
{
if(p==1)break;
if(b!=' ')
{
b=' ';
for(j=i+1;j<l1;j++)
{
if(b[j]==' '){kk=j;p=1;break;}
b[j]=' ';
}
}
}
}

qsort((void *)A, c, sizeof(A[0]), sort_function);

for (xx = 0; xx < c; xx++)
printf("%s\n", A[xx].str2);
printf("\n");
}
}
return 0;
}
[/cpp]

[/cpp]
Last edited by mohiul alam prince on Sun Feb 08, 2004 11:24 am, edited 1 time in total.

Post Reply

Return to “Volume 4 (400-499)”