## 482 - Permutation Arrays

Moderator: Board moderators

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:
It says in the description that there's a blank line after the number of test cases....I honestly dont see it.

Hedge
New poster
Posts: 11
Joined: Thu Jul 29, 2004 8:59 pm
can anyone who got accepted give me the output to:

Code: Select all

``````5

3 1 2
32.0 54.7 -2
4 1 3 2
- 9.1 + 3. .9 .7
1 2 3
.1.2.3
4 3 2 1
-7.+.3.9     9.9
1 2
1.2.3
``````

Junayeed
New poster
Posts: 50
Joined: Sat Oct 26, 2002 9:02 am
I just change some of ur inputs that is the space between the sign and the number and give some spaces between the numbers.
Hope this will help.

Code: Select all

``````5

3 1 2
32.0 54.7 -2
4 1 3 2
-9.1 +3..9 .7
1 2 3
.1 .2 .3
4 3 2 1
-7 +.3 .9     9.9
1 2
1.2 .3
``````

Code: Select all

``````54.7
-2
32.0

+3..9
.7
-9.1

.1
.2
.3

9.9
.9
+.3
-7

1.2
.3
``````
Junayeed

Hedge
New poster
Posts: 11
Joined: Thu Jul 29, 2004 8:59 pm
Thanks, i finally got accepted by parsing the numbers just until whitespaces. They seems so be seperated by whitespaces in the sample in. There are no test cases like .5.5 but always .5 .5
This makes this problem a lot easier, because the numbers in the inputs seems not just be of the form +1.2 but maybe -3.4e-5 or such. Actually this is not that hard to parse, but i just didnt thought about it .

Antonio Ocampo
Experienced poster
Posts: 131
Joined: Sat Jul 17, 2004 4:09 am
Location: Lima, Per
Please, help me I got WA. This is my code

#include <iostream>
#include <algorithm>
#include <cstdio>

typedef struct
{
int orden;
char num[50];
}
inputs;

{
char num[50]="";

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

for(j=0; cad!=' '&& i<n; ++i, ++j)

input[++leidos].orden=atoi(num);
}

return leidos;
}

bool orden(inputs a, inputs b)
{
if( a.orden<b.orden )
return true;

return false;
}

void main()
{
int i,n,casos;
inputs input[1000];

scanf("%i\n",&casos);

do
{

for(i=1;i<=n;++i)
scanf("%s",input.num);

sort(input+1,input+n+1,orden);

for(i=1;i<=n;++i)
puts(input.num);

if(casos>1)
putchar('\n');
}
while(--casos);
}

chops
New poster
Posts: 9
Joined: Sat Jan 29, 2005 10:48 pm
Location: dhaka
Contact:

### 482-help me find the bug

here is my got.got wrong answer.help

#include<stdio.h>
#include<string.h>
#include<assert.h>
#include<stdlib.h>

#define SIZE 1000001

long pos[SIZE];
char val[SIZE][30];
char inp[SIZE*12];

void main()
{
long i,j,N;
char *q;

gets(inp);
sscanf(inp,"%ld",&N);
while(N--)
{
gets(inp);
q=strtok(inp," ");
i=0;
while(q)
{
pos=atol(q);
q=strtok(NULL," ");
i++;
}
assert(i<SIZE);
gets(inp);
q=strtok(inp," ");
i=0;
while(q)
{
strcpy(val[pos-1],q);
q=strtok(NULL," ");
i++;
}
for(j=0;j<i;j++)
{
puts(val[j]);
}
if(N>0)printf("\n");
}
}

Raj Ariyan
Learning poster
Posts: 70
Joined: Sat Feb 05, 2005 9:38 am
Location: Gurukul

### Help

Hi chops,
I think in this problem you only need sort. Nothing else. Here is some hints.

1. For this problem structure will be the best approach i think. Build a structure with two elements, index and num.

2. At first input index value until u get new line. Something like..
while(ch!='\n')
{
cin>>.s[n++].index
cin.get(ch)
}

3. Then take all the floating value upto n
4. Sort them in ascending order.
5. Print those float value after sort.

Hope it helps. Good luck.
Some Love Stories Live Forever ....

MUBBASHER
New poster
Posts: 10
Joined: Mon Oct 04, 2004 5:23 am

### Test Cases of problem # 482

Hello every One if any one can send me the test cases of my problem and i am already getting the error of wrong answer so i have submitted the code if any one can help me.

mohiul alam prince
Experienced poster
Posts: 120
Joined: Sat Nov 01, 2003 6:16 am
Location: Dhaka (EWU)
Hi
u can explain ur algorithm or sent me ur code
I will help u.

MAP

rmotome
New poster
Posts: 14
Joined: Mon Jan 10, 2005 12:20 pm

### 482 (Permutation Arrays) WA?????? Look here first!!!!!!!!!!!

Do not treat the doubles as doubles, read them in as strings. Ohh dear, have I said too much

thirddawn
New poster
Posts: 9
Joined: Sat Oct 15, 2005 4:41 am

### 482 TLE

Sorry...I know it's wierd to get TLE in this problem...

But I just did it ...|||

My code are as follow

Code: Select all

``````#include <stdio.h>

int main(){
int counter,run[1000],i,test,j,k,l;
char number[1000][1000];
scanf("%d",&counter);
for (i = 0;i<counter;i++){
j = 0;
while (scanf("%d",&run[j])){
test = 0;
for (k =0;k<=j;k++){
for (l = 1;l<=j+1;l++){
if (run[k] == l)
test = test + 1;
}
}
if (test == j + 1)
break;
else
j = j + 1;
}
for (k = 0; k <=j ; k ++)
scanf("%s",&number[k]);
for (l = 1;l<=j+1;l++){
for (k = 0; k <=j ; k ++){
if (run[k] == l)
printf("%s\n",number[k]);
}
}
printf("\n");
}
}
``````
Can anyone provide some idea to fix the TLE problem?

Thank you very much for reading this article, I deliver my deepest appreciation to you from the bottom of my heart

sohel_cuet_cse
New poster
Posts: 3
Joined: Sun Dec 11, 2005 7:46 pm
Location: chittagong
Contact:

### 482 WA why????????????

Can anyone tell me where is my fault???????
I have used string to take input and for output.
here is my code:
#include<stdio.h>
#include<string.h>
#define M 100000
#define MAX 1000000

typedef long int dt;

struct per
{
dt index;
char num[110];
}ar[M];

void main()
{
dt i,j,end,k,l,start,t,test;
char temp2[MAX],temp[110],input1[MAX],input2[MAX],ch,t2[MAX];
scanf("%ld",&test);
scanf("%c",&ch);
for(i=0;i<test;i++)
{
gets(input1);
gets(input2);
j=0;
l=0;
start=0;
k=0;
while(input1[j])
{

if(input1[j]!=32)
{
temp[k]=input1[j];
k++;
start=1;
end=0;
}
if(input1[j]==32&&start==1)
{
temp[k]='\0';
sscanf(temp,"%ld",&ar[l].index);
l++;
k=0;
start=0;
end=1;
}
j++;
}
if(end==0)
{
temp[k]='\0';
sscanf(temp,"%ld",&ar[l].index);
l++;
k=0;
start=0;
end=1;
}
j=0;
l=0;
start=0;
k=0;
while(input2[j])
{
if(input2[j]!=32)
{
temp2[k]=input2[j];
k++;
start=1;
end=0;
}
if(input2[j]==32&&start==1)
{
temp2[k]='\0';
strcpy(ar[l].num,temp2);
l++;
k=0;
start=0;
end=1;
}
j++;
}
if(end==0)
{
temp2[k]='\0';
strcpy(ar[l].num,temp2);
l++;
k=0;
start=0;
end=1;
}
for(j=0;j<l-1;j++)
for(k=0;k<l-1;k++)
{
if(ar[k].index>ar[k+1].index)
{
t=ar[k].index;
ar[k].index=ar[k+1].index;
ar[k+1].index=t;

strcpy(t2,ar[k].num);
strcpy(ar[k].num,ar[k+1].num);
strcpy(ar[k+1].num,t2);
}
}
for(j=0;j<l;j++)
printf("%s\n",ar[j].num);
printf("\n");
scanf("%c",&ch);
}

}

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
Try the samples below:

Input:

Code: Select all

``````3

3 1 2
32.0 54.7 -2

3 1 2
32.0 54.7 -2

3 1 2
32.0 54.7 -2``````
Output:

Code: Select all

``````54.7
-2
32.0

54.7
-2
32.0

54.7
-2
32.0``````
Hope it works.
Ami ekhono shopno dekhi...
HomePage

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
Your method of taking input is totally wrong. I think thats the reason you are getting TLE.

Here is my algorithm for taking input...

Code: Select all

``````    int testcase;
char p[1000];
scanf("%d",&testcase);       // taking test case

while(testcase)
{
gets(p);  // This is for taking a blank line
gets(p);  // For input line
/*Now divide the string and find out how many integers are there*/
/*Suppose the number is n*/
/*Take n strings*/
/*print them as the problem states*/
testcase--;
}
``````
Hope it helps...
Ami ekhono shopno dekhi...
HomePage

sohel_cuet_cse
New poster
Posts: 3
Joined: Sun Dec 11, 2005 7:46 pm
Location: chittagong
Contact:
Hi Jan thanx a lot.I got ac. There was a silly mistake in taking input.Again thanx a lot.