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

asif_iut
New poster
Posts: 16
Joined: Mon Nov 01, 2010 8:08 am

Re: 482 Permutation Arrays

Post by asif_iut » Thu Dec 16, 2010 9:31 pm

the "sorted" array should be of 'int' type

nhrahi
New poster
Posts: 6
Joined: Tue Aug 25, 2009 7:38 pm

Re: 482 Permutation Arrays

Post by nhrahi » Fri Dec 17, 2010 3:27 pm

thanx asif,got AC :D

muctadir.dinar
New poster
Posts: 4
Joined: Sat Apr 16, 2011 10:04 pm
Location: IIT, DU
Contact:

Re: 482 Permutation Arrays

Post by muctadir.dinar » Fri Apr 22, 2011 12:58 pm

getting wrong answer over and over again. can anyone tell me what is wrong with the code...

Code: Select all

#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
using namespace std;

int main()
{
//    freopen("input", "r+", stdin);

    int testCases;
    while (scanf("%d", &testCases)!=EOF)
    {
        getchar();

        for (int a = 0; a<testCases; a++)
        {
            if (a>0)
            {
                getchar();
            //    printf("\n");
            }
            getchar();

            int index[300000];
            double number[300000];

            char ch[300000];

            gets(ch);
            char temp[20];
            int ipos = 0;
            for (int i = 0, t = 0; i<=strlen(ch); i++)
            {
                if (ch[i]>=48 && ch[i]<=57)
                {
                    temp[t] = ch[i];
                    t++;
                }
                else
                {
                    temp[t] = '\0';
                    t = 0;
                    index[ipos] = atoi(temp);
                    ipos++;
                }
            }
            index[ipos] = NULL;

            for (int i = 0; i<ipos; i++)
            {
                scanf("%lf", &number[i]);
            }

            for (int i = 0; i<ipos; i++)
            {
                for (int j = 0; j<ipos-i-1; j++)
                {
                    int k = 0;
                    float f;
                    if (index[j] > index[j+1])
                    {
                        k = index[j];
                        index[j] = index[j+1];
                        index[j+1] = k;

                        f = number[j];
                        number[j] = number[j+1];
                        number[j+1] = f;
                    }
                }
            }

            for (int i = 0; i<ipos; i++)
            {
                cout << number[i] << endl;
            }
            cout << endl;
        }
    }
    return 0;
}
You are the one, who can make a difference...

vinoth.gopi
New poster
Posts: 1
Joined: Tue May 17, 2011 7:00 pm

Re: 482 Permutation Arrays

Post by vinoth.gopi » Tue May 17, 2011 7:06 pm

Even my code is failing for unknown reasons. Fixed array sizes, no end line after last case etc have all been taken care of. But still WA. Any ideas?

Code: Select all

int main() {
	int maxSize = 100000;
	int input_arr[maxSize];
	string output[maxSize];
	int iterations;
	int x=0;
	string mystr;
	char * pch;
	bool y = false;
	
	
	cin >> iterations;
	getline (cin,mystr);
	
	while (iterations > 0){
		
		y ? getline (cin,mystr) : y = true;
		
		getline (cin,mystr);
		getline (cin,mystr);
		pch = strtok (&mystr[0]," ");
		
		while (pch != NULL){
			input_arr[x++] = atoi(pch) - 1; 
		 	pch = strtok (NULL, " ");
		}

		for (int i=0; i<x; i++)
			cin >> output[input_arr[i]];

		for (int i=0; i<=x; i++){
			cout << output[i];
			if (i != x) cout << endl;
		}
			
		if (iterations != 1) cout << endl;
			
		x = 0;
		iterations--;

	}
	
	return 0;
}

Martuza_cseiu
New poster
Posts: 2
Joined: Mon Mar 28, 2011 5:49 am

Re: 482 Permutation Arrays

Post by Martuza_cseiu » Fri Jun 10, 2011 11:39 am

Why I get Worng Ans?????????? Please Help me.............

Code: Select all

/*
Martuza, Islamic University
*/
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <string>


int main()
{
	long tc,i,s=0;
	scanf("%ld\n",&tc);
	while(tc--)
	{
		if(s>0)
			printf("\n");
		s=1;
		char a[100000]={0},tmp[15]={0},d[100000]={0},e[10000][15]={0},temp1[15]={0};
		long l,k=0,j=0,w,l1,t;
		int b[100000]={0};
		double c[100000]={0},temp;
		gets(a);
		l=strlen(a);
		for(i=0; i<l; i++)
		{
			if(isdigit(a[i]))
				tmp[k++]=a[i];
			if(a[i]==' ' || i==l-1)
			{
				b[j++]=atoi(tmp);
				for(w=0; w<15; w++)
					tmp[w]=0;
				k=0;
			}
		}
		gets(d);
		l1=strlen(d);
		j=0; k=0; t=0;
		for(i=0; i<l1; i++)
		{
			if(isdigit(d[i]) || d[i]=='.' || d[i]=='-')
				e[t][k++]=d[i];
			if(d[i]==' ' || i==l1-1)
			{
				c[j++]=atof(e[t]);
				k=0;
				t++;
			}
		}
		for(i=0; i<t; i++)
			for(j=0; j<t-1; j++)
				if(c[j]>c[j+1])
				{
					temp=c[j];
					c[j]=c[j+1];
					c[j+1]=temp;
					strcpy(temp1,e[j]);
					strcpy(e[j],e[j+1]);
					strcpy(e[j+1],temp1);
				}
		for(w=0; w<t; w++)
			printf("%s\n",e[b[w]-1]);
	}

	return 0;

} 

live_lie
New poster
Posts: 19
Joined: Mon Nov 29, 2010 11:50 pm

Re: 482 Permutation Arrays

Post by live_lie » Fri Jun 17, 2011 5:08 pm

AC

sauman biswas
New poster
Posts: 1
Joined: Fri Dec 23, 2011 4:17 pm

Re: 482 Permutation Arrays

Post by sauman biswas » Fri Dec 23, 2011 11:04 pm

#include<stdio.h>
#include<string.h>
char ab[100000];

char b[100000][100];

main()
{

long long sum,i,k,j,l,a[100000],co,m;
scanf("%lld",&m);
printf("\n");
getchar();
for(k=1;k<=m;k++)
{
gets(ab);
j=0;
l=strlen(ab);
sum=0;

for(i=0;i<=l;i++)
{
if(ab==' '||ab=='\0')
{
a[j++]=sum-1;
sum=0;
}
else
sum=sum*10+ab-48;
}
co=j;
for(i=0;i<co;i++)
{
scanf("%s",b[a]);
}
getchar();
if(k>1)
printf("\n");


for(i=0;i<co;i++)
{
printf("%s\n",b);
}

}
return 0;
}



runtime error what to do nw? ? ?

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 482 Permutation Arrays

Post by brianfry713 » Fri Jan 06, 2012 11:47 pm

sauman biswas, don't use gets(). Look at the I/O formatting again.
Check input and AC output for thousands of problems on uDebug!

warheadshot
New poster
Posts: 2
Joined: Tue Feb 07, 2012 10:20 am

Re: 482 Permutation Arrays

Post by warheadshot » Tue Feb 07, 2012 10:31 am

Hi, Why I got WA? Help D:

Code: Select all

#include<iostream>
#include <cstring>
#include<cstdio>
using namespace std;
 
char line [1000000];
int list1[50010];int list2[50010];
int cont;
 
void saca_int(){
        int aux=0;cont=0;
        for(int i=0;(size_t)(i)<=strlen(line);i++){
                if(line[i]>='0'&&line[i]<='9'){
                        aux=aux*10+(line[i]-'0');   
                }
                else{
                        if(aux!=0){
                                list1[aux-1]=cont;cont++;        
                                aux=0;
                        }
                }
        }
}
 
void busca_float(){
        int conta=0;bool passa=0;
        for(int i=0;(size_t)(i)<=strlen(line);i++){
                if((line[i]>='0'&&line[i]<='9')||line[i]=='-'||line[i]=='.'){
                        if(!passa){list2[conta]=i;passa=1;conta++;}   
                }
                else{
                        if(passa){passa=0;}
                }
        }
}
 
void saca_float(int x){
        for(int i=x;;i++){
                if((line[i]>='0'&&line[i]<='9')||line[i]=='-'||line[i]=='.'){
                        cout<<line[i];   
                }
                else{
                        return;
                }
        }
}
 
 
 
int main(){
        int N=0;float aux;scanf("%d\n",&N);
        if(N==0){return(0);}
        for(int ii=0;ii<N;ii++){
                if(ii!=0){cout<<"\n";scanf("\n");}
                gets(line);saca_int();
                memset(line,'\0',strlen(line));
                gets(line);busca_float();
                for(int j=0;j<cont;j++){
                        saca_float(list2[list1[j]]);cout<<"\n";
                }
                memset(line,'\0',strlen(line));
        }
}

asif.mist
New poster
Posts: 3
Joined: Wed Jan 26, 2011 4:43 pm

Re: 482 Permutation Arrays

Post by asif.mist » Thu Feb 23, 2012 4:49 pm

warheadshot,
u can always use c's strtok() to parse the numbers.

mostafiz93
New poster
Posts: 31
Joined: Thu Nov 24, 2011 12:08 am

Re: 482 Permutation Arrays

Post by mostafiz93 » Sat Apr 14, 2012 2:25 am

i'm assuming that the number of integers given in second line will be equal to the number of flaots given in the next line. then simply making a new array with new sequence.

but i'm getting WA.
can anyone find the bug of my code??

Code: Select all

removed after AC
my assumption was ok and don't print extra newline at the end.

bill8124
New poster
Posts: 8
Joined: Fri Jan 21, 2011 8:13 am

Re: 482 Permutation Arrays

Post by bill8124 » Fri Jul 27, 2012 6:26 pm

I got accepted.
Several Hints for everyone suffering WA:
1. The number of numbers will not exceed 40000, and there won't be more than 400000 characters in one line.
2. There are no spaces in a number. (i.e. You can use scanf("%s") to read them)
3. Be aware of output. Output for each input instance should be seperated with a blank line.

Munchor
New poster
Posts: 19
Joined: Sun Mar 03, 2013 4:03 pm

Re: 482 Permutation Arrays

Post by Munchor » Sun Mar 03, 2013 7:56 pm

Code: Select all

#include <stdio.h>
#include <vector>
#include <algorithm>
#include <string>
#include <iostream>

using namespace std;

struct combo_number
{
  string number_as_string;
  double number;
};

int main()
{
  unsigned int n, i, u, k;
  scanf("%d", &n);

  scanf("\n");

  vector<int> order;
  vector<double> numbers;
  vector<string> numbers_as_strings;
  vector<combo_number> combo_numbers;

  unsigned int order_number;
  double number;
  string number_as_string;
  char input_character;

  for (i = 0; i < n; i++)
  {
    order.clear();
    numbers.clear();
    numbers_as_strings.clear();
    number_as_string.clear();
    combo_numbers.clear();
    
    while (true)
    {
      scanf("%d", &order_number);
      order.push_back(order_number);

      scanf("%c", &input_character);

      if (input_character == ' ')
        continue;
      else
        break;
    }

    while (true)
    {
      cin >> number_as_string;

      combo_number combo;
      combo.number_as_string = number_as_string;
      combo.number = atof(number_as_string.c_str());

      numbers_as_strings.push_back(number_as_string);
      numbers.push_back(combo.number);
      combo_numbers.push_back(combo);

      scanf("%c", &input_character);

      if (input_character == ' ')
        continue;
      else
        break;
    }

    sort(numbers.begin(), numbers.end());

    for (u = 0; u < (int) order.size(); u++)
    {
      //printf("%lf\n", numbers[order[u] - 1]);
      for (k = 0; k < (int) combo_numbers.size(); k++)
      {
        if (numbers[order[u] - 1] == combo_numbers[k].number)
          cout << combo_numbers[k].number_as_string << endl;
      }
      
      //cout << numbers_as_strings[order[u] - 1] << endl;
    }

    if (i != n - 1)
      printf("\n");

    scanf("\n");
  }

  return 0;
}
I'm getting Wrong Answer and I think I know why - it doesn't solve this one correctly:

Code: Select all

2

3 1 2
32.0 54.7 -2

1 3 2 4
.004 +5.0e0 0.000007  3
It's outputting the second one instead of the first one:

Code: Select all

54.7
-2
32.0

.004
0.000007
+5.0e0
3

Code: Select all

54.7
-2
32.0

0.000007
3
.004
+5.0e0
How did you guys handle "+5.0e0" cases? I think that's why my solution is failing.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 482 Permutation Arrays

Post by brianfry713 » Tue Mar 05, 2013 1:18 am

It looks like you misunderstood the problem. Don't sort an array of doubles, just keep them as strings. Permute the strings according to the index array.
Check input and AC output for thousands of problems on uDebug!

fade36776
New poster
Posts: 1
Joined: Sun Mar 10, 2013 6:23 pm

Re: 482 Permutation Arrays

Post by fade36776 » Sun Mar 10, 2013 6:35 pm

i m still getting WA. please help.

Code: Select all

removed after AC
set buff to 40000 got AC
Last edited by fade36776 on Wed Mar 20, 2013 7:20 am, edited 1 time in total.

Post Reply

Return to “Volume 4 (400-499)”