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

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:

Post by yiuyuho »

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

Post by Hedge »

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
Location: Dhaka, Bangladesh

Post by Junayeed »

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

Post by Hedge »

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

Post by Antonio Ocampo »

Please, help me I got WA. This is my code


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

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


int tokeniza(char cad[], inputs input[])
{
int leidos=0,i,j,n=strlen(cad);
char num[50]="";

for(i=0;i<n;)
{
while( cad==' ')
++i;

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

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;
char cad[100000];
inputs input[1000];

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

do
{
gets(cad);
n=tokeniza(cad,input);

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

Post by chops »

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

Post by Raj Ariyan »

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

Post by MUBBASHER »

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)

Post by mohiul alam prince »

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
Location: Kitchener, Ontario, Canada

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

Post by rmotome »

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

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

482 TLE

Post by thirddawn »

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????????????

Post by sohel_cuet_cse »

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
Location: Dhaka, Bangladesh
Contact:

Post by Jan »

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
Location: Dhaka, Bangladesh
Contact:

Post by Jan »

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:

Post by sohel_cuet_cse »

Hi Jan thanx a lot.I got ac. There was a silly mistake in taking input.Again thanx a lot.:D
Listen to your heart.

Post Reply

Return to “Volume 4 (400-499)”