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

shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Post by shamim »

Your code is difficult to follow because you have used no allignment.
Please submit your code with proper allignment.

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

Post by mohiul alam prince »

shamim i have modify my source code
please chake it

prince

Mahmud776
New poster
Posts: 22
Joined: Mon Dec 22, 2003 9:29 am
Location: Canada

Not specified

Post by Mahmud776 »

I took 50010 for the size of the array for the first line . And the highest value for the first line of the input would be 1000.

I got accepted by using these size.

Mahmud776
New poster
Posts: 22
Joined: Mon Dec 22, 2003 9:29 am
Location: Canada

Not specified

Post by Mahmud776 »

You have to be more carefull about every things.This is a multiple input(blue tick) problem.So, you have to process inputs in this way.

For your convenience in understanding this problem I gave some sample inputs and outputs.
Inputs:
2

4 1 5 2 3
-.000045 -0.00045 .456 .056987 25.26589456987

1 3 5 6 4 2
.004 .001 0.000007 0.23 -.0007 -56

Output:
-0.00045
.056987
25.26589456987
-.000045
.456

.004
-56
.001
-.0007
0.000007
0.23

Salmin Sultana
New poster
Posts: 16
Joined: Sun Mar 07, 2004 12:19 pm
Location: Dhaka

why compile error 482

Post by Salmin Sultana »

why compile error?
#include<stdio.h>
#include<string.h>
#include<stdlib.h>

int main()
{
long int a[1000];
char array[1000][20];
char str[1000],s[100];

long int in,i,num,n,j,len,k;
double p;
scanf("%ld",&n);
fflush(stdin);

for(k=0;k<n;k++){

in=0;
gets(str);
len=strlen(str);

for(i=0;i<len;){

while(str==' ')
i++;
sscanf(&str,"%s",s);

i=i+strlen(s)+1;

a[in]=atol(s);
in++;
}

gets(str);
len=strlen(str);

for(i=0,j=0;j<in&&i<len;j++){

while(str==' ')
i++;
sscanf(&str,"%s",s);

i=i+strlen(s)+1;
num=a[j]-1;
strcpy(array[num],s);
}
for(i=0;i<in;i++)
printf("%s\n",array);
}
return 0;
}

sidky
New poster
Posts: 50
Joined: Wed Nov 06, 2002 1:37 pm
Location: Planet Earth, Universe
Contact:

Post by sidky »

I just submitted your code with the language C++, and it didn't produce any compile error. Please recheck your submission method.

Salmin Sultana
New poster
Posts: 16
Joined: Sun Mar 07, 2004 12:19 pm
Location: Dhaka

why compile error 482

Post by Salmin Sultana »

why compile error?
is my algorithm correct?

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

int main()
{
long int a[1000000];
char array[1000000][1000];
char str[1000000],s[1000];

long int in,i,num,n,j,len,k;
double p;
scanf("%ld",&n);
fflush(stdin);

for(k=0;k<n;k++){

in=0;
gets(str);
len=strlen(str);

for(i=0;i<len;){

while(str==' ')
i++;
sscanf(&str,"%s",s);

i=i+strlen(s)+1;

a[in]=atol(s);
in++;
}

gets(str);
len=strlen(str);

for(i=0,j=0;j<in&&i<len;j++){

while(str==' ')
i++;
sscanf(&str,"%s",s);

i=i+strlen(s)+1;
num=a[j]-1;
strcpy(array[num],s);
}
for(i=0;i<in;i++)
printf("%s\n",array);
}
return 0;
}[/cpp]
Last edited by Salmin Sultana on Tue Mar 09, 2004 11:58 am, edited 2 times in total.

shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Post by shamim »

I compiled your code using Cygwin, and there was no compile error.
However, you have declared large inside your main function; so even if your code had compiled, it would receive run time error.

Salmin Sultana
New poster
Posts: 16
Joined: Sun Mar 07, 2004 12:19 pm
Location: Dhaka

Post by Salmin Sultana »

it's a multiple input problem.i think i can't manage multiple input
problem.please tell what should be code change to provide multiple
input correctly.i took array outside main function but got wa.

shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Post by shamim »

One thing i have noticed from your code is, you are first taking all the input and then giving all the output. For this, you are required to declare large arrays.

Simply take input for one set, process it, and give output. Then move on to take more input till the last case.

alu_mathics
Learning poster
Posts: 55
Joined: Sat Jan 24, 2004 9:30 pm
Location: Chittagong
Contact:

Post by alu_mathics »

Multiple inputs are of the following form
Example:

3

100
1011
11231

3990
34

313
43

----
test case number.
blankline
block of input1
blank line
block of input2
blank line
block of input3

you can read this as:

gets(str);
test=atol(str);//sscanf(str,"%d",&test);
gets(str);

while(test--)
{
while(gets(str)&&str[0])
{
//here u can modify str as required
}
if(test)printf("\n");
}
cuii e

Hedge
New poster
Posts: 11
Joined: Thu Jul 29, 2004 8:59 pm

Post by Hedge »

Hello.
I am trying to solve the problem too, but i cant get it accepted.
Are there any tricky inputs? My programm can handle following input correctly:
Input:

Code: Select all

1

4 3 2 1
-7.+.3.9     9.9
Output:

Code: Select all

9.9
.9
+.3
-7.
The length of my input line is 50000 and i handle up to 2048 different numbers.

Hedge
New poster
Posts: 11
Joined: Thu Jul 29, 2004 8:59 pm

482 - Permutation Arrays

Post by Hedge »

Hello,
i have some problems with 482. Acually it seems not very hard, but the lack of given sizes makes it a bit trickier.
What i am doing to try to solve it:
First i read every indices and store them in an array. Then i read the next line and parse every number and remember
each start position in a second array. I dont save them at secondArray[ i ] but at secondArray[ firstArray[ i ] -1 ],
so i do some kind of bucket sort right by reading. This seems to work quite fine for my own test cases.
Finally i just output every 'String' in the second array from 0 to the number of inputs.
I am quite aware that this is a multiple input problem and i think i handle it correctly, but i get WA all the time.
So my questions: How long can an input line be? I tried several hight figueres and am sticking with 50000.
How much numbers can be in one input line? I am taking 2048 but even much higher values get me WA.
What should i do with inputs like:

Code: Select all

1

1 2
1.2.3
Is this:

Code: Select all

1.2
.3
or

Code: Select all

1.
2.3
Is there any case, my Algorithm is wrong?
Input:

Code: Select all

1

4 3 2 1
-7.+.3.9     9.9
Output:

Code: Select all

9.9
.9
+.3
-7. 
I hope anyone can give me a slight hint, where I am wrong.

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

Post by Junayeed »

I got AC with array size of 1000000.
Try with this.
Junayeed

Hedge
New poster
Posts: 11
Joined: Thu Jul 29, 2004 8:59 pm

Post by Hedge »

Unfortunately i had no luck, even with your high number.
Has anyone mean test cases?

Post Reply

Return to “Volume 4 (400-499)”