482  Permutation Arrays
Moderator: Board moderators

 Guru
 Posts: 724
 Joined: Wed Dec 19, 2001 2:00 am
 Location: Germany

 Learning poster
 Posts: 68
 Joined: Fri Oct 26, 2001 2:00 am
 Location: Dhaka, Bangladesh
 Contact:
wrong sample input and output
hi,
i also guess the sample input and output given in the problem description is wrong and yasten is right. Can anyone plz confirm me about the matter?
thwe right output for the sample input:
3 1 2
32.0 54.7 2
should be:
2
32.0
54.7
i also guess the sample input and output given in the problem description is wrong and yasten is right. Can anyone plz confirm me about the matter?
thwe right output for the sample input:
3 1 2
32.0 54.7 2
should be:
2
32.0
54.7

 Guru
 Posts: 724
 Joined: Wed Dec 19, 2001 2:00 am
 Location: Germany
No, it is ok. The description says:
"Then, we have the relationship between x and x' that x'pi = xi."
That means that at position i there is the index value for x after permutation, for example if you have
2 1
2 2
then 2 has to be at position 2 in the reordered array and 2 at position 1.
For the sample input there is p1=3, therefore in the permutated array there should be at position 3 the same value as at position 1, and so on.
"Then, we have the relationship between x and x' that x'pi = xi."
That means that at position i there is the index value for x after permutation, for example if you have
2 1
2 2
then 2 has to be at position 2 in the reordered array and 2 at position 1.
For the sample input there is p1=3, therefore in the permutated array there should be at position 3 the same value as at position 1, and so on.
can any1 tell me what the problem is in my program.
thanks in adv.
[/b]
thanks in adv.
Code: Select all
[cpp]
#include<stdio.h>
#include<stdlib.h>
#define N 10000
main()
{
int n,z,i,l,k,m,b[N];
char ch,c[50],d[N][20];
scanf("%d",&n);
scanf("%c",&ch);
for(z=0;z<n;z++)
{
k=0;
while(1)
{
m=0;
while(1)
{
scanf("%c",&ch);
if(ch=='\n' && k) break;
if(ch==' ') break;
if(ch!='\n' && ch!=' ')c[m++]=ch;
}
c[m]=0;
b[k++]=atoi(c);
if(ch=='\n') break;
}
for(i=0;i<k;i++)
scanf("%s",d[i]);
l=1;
for(m=0;m<k;m++)
{
for(i=0;i<k;i++)
if(b[i]==l)
{
printf("%s\n",d[i]);
l++;
break;
}
}
if(z!=(n1)) printf("\n");
}
return 0;
}[/cpp]
"Everything should be made simple, but not always simpler"

 Learning poster
 Posts: 94
 Joined: Wed Jul 31, 2002 12:44 pm
 Location: Dacca, Bangladesh
 Contact:
2 anupam
well, well, this problem is very good one (!) for handling the input. anyway, now let's talk 'bout your code here.
while taking the index array in the first part, you're incrementing k (the number of array element) all the time, even if a whitespace occurs!
it should be rather,
that is you should only increment k when you got a number. Secondly, your check in the inner while loop
should be simply
i think this causes a time limit exceed.
Again the check in the outer while loop should be,
rather than
it should help .
___________
the LAZBOy
while taking the index array in the first part, you're incrementing k (the number of array element) all the time, even if a whitespace occurs!
Code: Select all
b[k++]=atoi(c);
Code: Select all
if (m)
b[k++]=atoi(c);
Code: Select all
if(ch=='\n' && k) break;
Code: Select all
if(ch=='\n') break;
Again the check in the outer while loop should be,
Code: Select all
if(ch=='\n' && k) break;
Code: Select all
if(ch=='\n') break;
___________
the LAZBOy

 Experienced poster
 Posts: 169
 Joined: Wed Oct 31, 2001 2:00 am
 Location: Singapore

 Learning poster
 Posts: 94
 Joined: Wed Jul 31, 2002 12:44 pm
 Location: Dacca, Bangladesh
 Contact:
my solution that got accepted assumesjunjieliang wrote: Found my error...AC
Constants for my program
=> Max numbers: 100000
=> Max length per number: 100
Hope this will help others
=> Max numbers: 32000
=> Max len per number: 55 (54)
but later when i worked with anupam's code i got the upper bound more accurate
=> Max numbers: 2000
=> Max len per number: 15 (14)
Max bound may be lower than this even, I haven't tried .
___________
the LAZBOy
482 Permutation Arrays  WA, RE <SIGSEGV>
Guys, please check my 482 code downhere:
[cpp]#include <stdio.h>
#include <math.h>
#include <string.h>
char str[10000],n[1000][10000],chr;
int len,count,ten,temp,i,j,k,sum[10000],m,cas;
void main ()
{
scanf ("%d",&m); cas=0;
scanf ("%c",&chr); //to handle an <Enter> after inputting the m
while (cas<m)
{
cas++; count=1; k=0; temp=0;
while (scanf ("%c",&chr)==1)
{
if (chr==' '  chr=='\n')
{
temp++; len=strlen(str); sum[temp]=0;
for (i=len1;i>=0;i)
{
switch (str)
{
case '0': {sum[temp]+=0; break;} case '5': {sum[temp]+=5*pow(10,ten); break;}
case '1': {sum[temp]+=1*pow(10,ten); break;} case '6': {sum[temp]+=6*pow(10,ten); break;}
case '2': {sum[temp]+=2*pow(10,ten); break;} case '7': {sum[temp]+=7*pow(10,ten); break;}
case '3': {sum[temp]+=3*pow(10,ten); break;} case '8': {sum[temp]+=8*pow(10,ten); break;}
case '4': {sum[temp]+=4*pow(10,ten); break;} case '9': {sum[temp]+=9*pow(10,ten); break;}
}
ten++;
}
for (i=0;i<len;i++)
{
str='\0';
}
k=0;; count++; ten=0;
}
else {str[k]=chr; k++;}
if (chr=='\n') break;
}
for (i=1;i<=temp;i++)
{
scanf ("%s",n[sum]);
}
for (i=1;i<=temp;i++)
{
printf ("%s\n",n);
}
if (cas<m) printf ("\n");
scanf ("%c",&chr); //to handle the printf ("\n");
}
}[/cpp]
I played with the first and the last "scanf ("%c",&chr);" and I got either RE <SIGSEGV> or WA...
I think I've gone wrong handlin' the input... An <Enter> after the previous input is always
taken by the "scanf ("%c",&chr);" as a '\n' character, so it just passed with the wrong input ('\n')...
Anybody, please tell me how to overcome this. Or maybe found me another mistake(s)???
Thank's!
[cpp]#include <stdio.h>
#include <math.h>
#include <string.h>
char str[10000],n[1000][10000],chr;
int len,count,ten,temp,i,j,k,sum[10000],m,cas;
void main ()
{
scanf ("%d",&m); cas=0;
scanf ("%c",&chr); //to handle an <Enter> after inputting the m
while (cas<m)
{
cas++; count=1; k=0; temp=0;
while (scanf ("%c",&chr)==1)
{
if (chr==' '  chr=='\n')
{
temp++; len=strlen(str); sum[temp]=0;
for (i=len1;i>=0;i)
{
switch (str)
{
case '0': {sum[temp]+=0; break;} case '5': {sum[temp]+=5*pow(10,ten); break;}
case '1': {sum[temp]+=1*pow(10,ten); break;} case '6': {sum[temp]+=6*pow(10,ten); break;}
case '2': {sum[temp]+=2*pow(10,ten); break;} case '7': {sum[temp]+=7*pow(10,ten); break;}
case '3': {sum[temp]+=3*pow(10,ten); break;} case '8': {sum[temp]+=8*pow(10,ten); break;}
case '4': {sum[temp]+=4*pow(10,ten); break;} case '9': {sum[temp]+=9*pow(10,ten); break;}
}
ten++;
}
for (i=0;i<len;i++)
{
str='\0';
}
k=0;; count++; ten=0;
}
else {str[k]=chr; k++;}
if (chr=='\n') break;
}
for (i=1;i<=temp;i++)
{
scanf ("%s",n[sum]);
}
for (i=1;i<=temp;i++)
{
printf ("%s\n",n);
}
if (cas<m) printf ("\n");
scanf ("%c",&chr); //to handle the printf ("\n");
}
}[/cpp]
I played with the first and the last "scanf ("%c",&chr);" and I got either RE <SIGSEGV> or WA...
I think I've gone wrong handlin' the input... An <Enter> after the previous input is always
taken by the "scanf ("%c",&chr);" as a '\n' character, so it just passed with the wrong input ('\n')...
Anybody, please tell me how to overcome this. Or maybe found me another mistake(s)???
Thank's!
Please reply...
Heey... isn't there any solved this problem yet?
Please gimme answers... Really need it!!!
Thank you.
Please gimme answers... Really need it!!!
Thank you.
Answer meeee....
It's been a long time...
Why there's still no answer?
I grew the array to a million but nothing happened but another 0.023 SIGSEGV RE!!
Why??!
Why there's still no answer?
I grew the array to a million but nothing happened but another 0.023 SIGSEGV RE!!
Why??!
u'd better try to use struct and store every number as string (important! bcoz
u need to print exactly the same as input) and corresponding indices and sort
the array according to the indices. u can use qsort for sorting.
following code might help:
[c]
typedef struct
{
int index;
char num[20];
} array;
array a[100000];
[/c]
good luck
sohel
u need to print exactly the same as input) and corresponding indices and sort
the array according to the indices. u can use qsort for sorting.
following code might help:
[c]
typedef struct
{
int index;
char num[20];
} array;
array a[100000];
[/c]
good luck
sohel