153  Permalex
Moderator: Board moderators
Read the post given by Nikolay Archak in the following forum...
http://onlinejudge.uva.es/board/viewto ... hlight=153
If you are still facing problems, I will help you.
http://onlinejudge.uva.es/board/viewto ... hlight=153
If you are still facing problems, I will help you.
Ami ekhono shopno dekhi...
HomePage
HomePage
153 help....(WA)
I don't know why do I got WA!?
Please give me some input and output data to test my program.
Or help me to find the mistake.....Please
Thanks in advance...
Please give me some input and output data to test my program.
Or help me to find the mistake.....Please
Thanks in advance...
Code: Select all
Acc
Maybe you didn't deal with the empty lines.
I've just solved this problem. Try this testcase. I generated it randomly.
Input:
Output:
I've just solved this problem. Try this testcase. I generated it randomly.
Input:
Code: Select all
h
ghum
aylnlfdx
ircvs
xg
bw
fnqduxwf
fozvsrtkj
r
pggxrpnr
ystmwcysy
cqpe
ikeffmzni
kkas
w
renz
ycxfxtls
ypsf
dpooef
zbcoeju
pvabo
o
ylfpbn
ljvrvip
amyehwqn
rq
mxujjloov
owuxwh
sncbxcok
fzkvatxd
lyjyhfi
jswnkkufn
xx
rzb
nmgq
oketlyhn
oa
gz
cddiute
ojwa
yz
vsc
psajlf
gubfaao
lzy
n
#
Code: Select all
1
2
2367
32
2
1
4212
15090
1
1947
23846
6
40332
6
1
13
17903
22
59
4333
91
1
1
1
659
833
2046
2
39961
96
16640
14716
1
1773
17573
1
4
15
26723
2
1
1
12
16
1
6
580
1771
2
1
I stay home. Don't call me out.

 New poster
 Posts: 16
 Joined: Mon Jun 26, 2006 9:33 am
 Contact:
153 Permalex TLE
hello have tried permalex. my method is to sort the initial string and permutate till a match is found (using strcmp)
any other shorter way? can't seem to figure out the trick (especially those who manage to have 0 CPU time)
any other shorter way? can't seem to figure out the trick (especially those who manage to have 0 CPU time)
Code: Select all
#include <cstdio>
#include <cstring>
#define MAXLENGTH 32
using namespace std;
bool nextPer(char a[],int length)
{
register int index,next_min;
char tmp;
for(index=length2;index>=0;index)
if(a[index]<a[index+1])
break;
if(index<0)
return false;
next_min=index+1;
for(int i=index+1;i<length;i++)
if(a[i]>a[index]&&a[i]<a[next_min])
next_min=i;
tmp = a[index];
a[index] = a[next_min];
a[next_min] = tmp;
for(int i=index+1;i<length1;i++)
{
next_min = i;
for(register int j=i+1;j<length;j++)
if(a[j]<a[next_min])
next_min=j;
tmp = a[i];
a[i] = a[next_min];
a[next_min] = tmp;
}
return true;
}
int main()
{
char string[MAXLENGTH],orig[MAXLENGTH],tmp;
int index,length;
while(scanf("%s",string),*string!='#')
{
length = strlen(string);
strcpy(orig,string);
for(int i=0;i<length1;i++)
{
index = i;
for(int j=i+1;j<length;j++)
if(string[j]<string[index])
index = j;
tmp = string[index];
string[index] = string[i];
string[i] = tmp;
}
index = 1;
do
{
if(!strcmp(string,orig))
break;
index++;
}while(nextPer(string,length));
printf("%10d\n",index);
}
return 0;
}
Search your problem first. And dont open a new thread if there is one already.
Read the post given by Nikolay Archak in the following thread...
http://onlinejudge.uva.es/board/viewto ... hlight=153
Read the post given by Nikolay Archak in the following thread...
http://onlinejudge.uva.es/board/viewto ... hlight=153
Ami ekhono shopno dekhi...
HomePage
HomePage
i solve this problem by counting.my algo is follow.
get input;copy to another,sort 2nd one,then compare if 1st elements in
2nd str is smaller then 1st elements in 1st str then get rest of data from 2nd str,again sort and compare as before and did it recursevely.
i have passed all sample input in board but wrong answer.
give some critical input.
sorry for my poor english.
thnx.
get input;copy to another,sort 2nd one,then compare if 1st elements in
2nd str is smaller then 1st elements in 1st str then get rest of data from 2nd str,again sort and compare as before and did it recursevely.
i have passed all sample input in board but wrong answer.
give some critical input.
sorry for my poor english.
thnx.
Strange problem!!!
I am having a strange kind of problem...n i have no clue
if the input is
my output is correct
but if i change the first input like this
then my output for last value goes wrong
i dont understand why....i m not using any global variable so different inputs are independent of each other
if the input is
Code: Select all
xzbcoeju
aboygp
eylfp
npljvrvi
Code: Select all
34573
11
21
8782
Code: Select all
xzbcoejuvp
aboygp
eylfp
npljvrvi
Code: Select all
3225844
11
21
2930
Code: Select all
Code Removed
Last edited by soddy on Wed Jan 30, 2008 7:02 pm, edited 1 time in total.
I am not selfish, I just want everything.
i already tried clearing each variable before a new test case....but still the problem persists.....i dont think clearing variables is the problem since i am initializing new variables for every test case
n i dont know y its working fine on VC++.....i am using cygwin compiler and getting wrong n i hv also tried submitting to online judge and got WA
problem is occuring for very few test cases....i tried a set of 500 test cases and got 3 results wrong but if i try those 3 test cases individually, i am getting correct result.....and i am not using any variable wid previously stored value....dont know y is it happening
n i dont know y its working fine on VC++.....i am using cygwin compiler and getting wrong n i hv also tried submitting to online judge and got WA
problem is occuring for very few test cases....i tried a set of 500 test cases and got 3 results wrong but if i try those 3 test cases individually, i am getting correct result.....and i am not using any variable wid previously stored value....dont know y is it happening
I am not selfish, I just want everything.
Got Accepted
I had left the problem and after a few months i tried again and got Accepted in 0.00 time(14th rank) ...things change with time
I am not selfish, I just want everything.

 Experienced poster
 Posts: 147
 Joined: Mon Jun 07, 2010 11:43 am
 Location: University Of Dhaka,Bangladesh
 Contact:
Re: 153
Its easier to write the whole thing in java bigint than trying to optimize the intermediate calculation. some io:
output:
Code: Select all
sdfretf
gggfrtttereee
dfffrrrdfdf
zzffffferrrre
aaseajwelrkjlsdj
ewrwerjwelrjwe
#
Code: Select all
1826
1801379
1130
535920
1468380809
3265624
UVa stats: http://felixhalim.net/uva/hunting.php?id=63448
My blog on programming: http://www.shafaetsplanet.com/planetcoding/
My blog on programming: http://www.shafaetsplanet.com/planetcoding/
Re: 153
I am currently working on permalex 153 and my c++ code is being rejected for being "wrong/incorrect"
my current guess is that I am not accounting for some fringe cases
I tried most of the strings given in the forum and got correct results
any help would be appreciated
my current guess is that I am not accounting for some fringe cases
I tried most of the strings given in the forum and got correct results
Code: Select all
using namespace std;
#include <iostream>
#include <stdlib.h>
#include <string>
#include <new>
#include <algorithm>
#include <iomanip>
/*
currently suffering the dreaded wrong output
I know it works for arrays of length 15 (regardless of character values)
I have looked on the help board and tried other peoples input and I have gotten identical output
I am assuming either I am messing up the output or messing up some fringe cases
*/
int permutations(string);
//finds the permutations of a sorted string (does not double count)
int permutations(string list)
{
int length=list.length();
long int sum =1;
if (length==0)
return(0);
if (length == 1)
return(sum);
for(int counter=2; counter<=length;counter++)
{
sum=sum*counter;
}
int count=1;
for(int j=1;j<length;j++)
{
if(list[j1]==list[j])
{
count++;
sum=sum/count;
}
else
count=1;
}
return(sum);
}
//runs the program
int main()
{
string tested;
cin>>tested;
string test="#";
while( tested!=test)
{
int length=tested.length();
string sorted =tested;
sort(sorted.begin(), sorted.end());
long int sum=1;
for(length;length>1;length)
{
int i=0;
while(sorted[i]!=tested[0]) //test for first letter and find its place
{
string temp=sorted;
temp.erase(i,1);
sum+=permutations(temp);
while(sorted[i]==sorted[i+1])
{
i++;
}
i++;
}
tested.erase(0,1);
sorted.erase(i,1);
}
std::cout << std::right << std::setw(11) << sum << std::endl;
cin>>tested;
}
}

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