110 - Meta-Loopless Sorts

[click xx]

I always got wrong answer.help me please!here is my program
thanks in advance
#include<iostream.h>
//#include<fstream.h>
#include<string.h>

//ifstream cin("uva110.in");
//ofstream cout("uva110.out");

const int maxn=10;

int n;
int order[maxn][maxn];

void gonext()
{
while(cin.peek()==' '||cin.peek()=='\n'||cin.peek()=='\t')
cin.ignore ();
return;
}

void outputvar()
{
int i;
for(i=0;i<n;i++)
{
cout<<((char)('a'+i));
if(i!=n-1)
cout<<",";
}
return;
}

void search(int t)
{
int i,j;
for(i=t;i>=0;i--)
{
for(j=0;j<t;j++)
order[t][j]=order[t-1][j];
for(j=t-1;j>=i;j--)
order[t][j+1]=order[t][j];
order[t]=t;
for(j=0;j<t;j++)
cout<<" ";
if(i==0)
cout<<"else"<<endl;
else{
if(i==t)
cout<<"if ";
else
cout<<"else if ";
cout<<((char)(order[t][i-1]+'a'))<<" < "<<((char)(t+'a'))<<" then"<<endl;
}
if(t!=n-1)
search(t+1);
else{
for(j=0;j<=t;j++)
cout<<" ";
cout<<"writeln(";
for(j=0;j<n;j++)
{
cout<<((char)(order[t][j]+'a'));
if(j!=n-1)
cout<<',';
else
cout<<')'<<endl;
}
}
}

return;
}

void work()
{
cout<<"program sort(input,output);"<<endl;
cout<<"var"<<endl;
outputvar();
cout<<" : integer;"<<endl;

cout<<"begin"<<endl;
cout<<" readln(";
outputvar();
cout<<");"<<endl;

if(n==1)
cout<<" writeln(a);"<<endl;
else{
order[0][0]=0;
search(1);
}
cout<<"end."<<endl;
return;
}

int main()
{
while(1)
{
gonext();
if(cin.peek()==EOF)
break;
cin>>n;
work();
}
return 1;
}[cpp][/cpp]

[Stefan Pochmann]

Where do you handle the multiple input?

[click xx]

Do you mean there will be many "n"s to input?
I think I've handled in my program.
I use the "while" loop to input every "n" then use work function to handle each input n.
But I am not sure that if my program ouput a correct format because the problem haven't said clearly about how to ouput in a multiple input case.
If you've passed this problem,can you give me your program to have a look?thanks for your help

[click xx]

oh,I finally know what's going on now.
I haven't see the statement link about multiple input ouput formats
just above the problem set in the web page.I suggest others to have a look at it before you start to solve the problems.It gave me such a big big big lesson!!! I hope others never do the foolish thing as what I've done again.

[Stefan Pochmann]

Don't worry, even guys with hundreds of solved problems sometimes get some wrong answers because they forget about multiple input (take me, for example ). This multiple input is clearly not the best solution possible, but you get used to it, so it's ok...

[click xx]

Thanks.I'll be more careful next time.

[youngwook]

????????????

[c]@BEGIN_OF_SOURCE_CODE
/* @JUDGE_ID: ******* 110 C "Recursive" */

@END_OF_SOURCE_CODE[/c]

[Ivan Golubev]

It's multiple input problem. Did you read message under exclamation icon?

[youngwook]

thanx!!

[yeung]

const
maxn=20;
type
atype=array [1..maxn] of byte;
var
n,m,i:byte;
a:atype;
procedure find(no:byte);
var
bak:atype;
j,k:byte;
begin
if no=n+1 then
begin
write('':n*2,'writeln(');
for j:=1 to n-1 do
write(chr(96+a[j]),',');
writeln(chr(96+a[n]),')');
exit;
end;
bak:=a;
a[no]:=no;
write('':(no-1)*2);
writeln('if ',chr(96+a[no-1]),' < ',chr(a[no]+96),' then');
find(no+1);
for j:=no-1 downto 2 do
begin
a:=bak;
writeln('':(no-1)*2,'else if ',chr(96+a[j-1]),' < ',chr(96+no),' then');
for k:=no-1 downto j do
a[k+1]:=a[k];
a[j]:=no;
find(no+1);
end;
writeln('':(no-1)*2,'else');
a[1]:=no;
for k:=1 to no-1 do
a[k+1]:=bak[k];
find(no+1);
end;
procedure doing;
var
c:char;
i,j:byte;
begin
writeln('program sort(input,output);');
writeln('var');
for c:='a' to chr(95+n) do
write(c,',');
writeln(chr(96+n),' : integer;');
writeln('begin');
write(' readln(');
for c:='a' to chr(95+n) do
write(c,',');
writeln(chr(96+n),');');
if n=1 then writeln(' writeln(a);') else
begin
writeln(' if a < b then');
a[1]:=1;
a[2]:=2;
find(3);
writeln(' else');
a[2]:=1;
a[1]:=2;
find(3);
end;
writeln('end.');
end;
begin
readln(m);
for i:=1 to m do
begin
readln;
readln(n);
doing;
writeln;
end;
end.

[dawynn]

OK, it's been college since I did any pascal programming. Still, your main routine seems wrong to me. I count three separate readln statements (outside of quotes of course). The problem description is quite clear that the input consists only of a single integer on a line by itself. Once you read that integer, there's nothing left to read.

[yeung]

thanks

[dawynn]

Doh! I apologize -- and stand corrected. Now that mine was also rejected with a WA, I closely read the multiple input description and found that I misspoke earlier. It looks like you're handling the multiple input correctly.

On the other hand -- I see for the base case (where n = 1), your code includes the following:

if n=1 then
writeln(' writeln(a);')

There should not be a semi-colon after the writeln statement. It looks like for the other cases, your writeln statement ends correctly (no semi-colon).

David

[yeung]

Thank you very much!

[ywliu]

it always respound "Wrong Answer"....but i really don't find bug...
anyone can tell me why...


[cpp]


#include<iostream>
//#include<fstream>
#include<string>
#include<vector>
using namespace std;

//ifstream cin("acm_110_in.txt");
//ofstream cout("acm_110_out.txt");

int n;
int iBlankNum;
string sLetter="abcdefgh";

vector<char> v;
vector<char>::iterator p;
void input_data();
void run(long d);
void main(){
input_data();
// cin.close();
// cout.close();
}
void input_data(){
int k1;
cin >> n;
cout << "program sort(input,output);" << endl;
cout << "var" << endl;
for(k1=0;k1<n-1;k1++)
cout << sLetter.at(k1) << ",";
cout << sLetter.at(k1) << " : integer;" << endl;
cout << "begin" << endl;
cout << " readln(" ;
for(k1=0;k1<n-1;k1++)
cout << sLetter.at(k1) << ",";
cout << sLetter.at(k1) << ");" << endl;
iBlankNum=0;
v.insert(v.begin(),1,sLetter.at( v.size() ));
run(1);
cout << "end." << endl;
}
void run(long d){
int k1,k2;
if(v.size()==n){
p=v.begin();
for(k2=0;k2<d;k2++) cout << " " ;
cout << "writeln(" << *p;
for(p=v.begin()+1;p!=v.end();p++)
cout << "," << *p ;
cout << ")"<< endl;
return;
}
for(k1=0;k1<=v.size();k1++){
if(k1==0){
p=v.begin()+v.size()-1;
for(k2=0;k2<d;k2++) cout << " " ;
cout << "if " << *p << " < " << sLetter.at(v.size()) << " then" << endl;
}
else if(k1==v.size()){
for(k2=0;k2<d;k2++) cout << " " ;
cout << "else" << endl;
}
else{
p=v.begin()+v.size()-k1-1;
for(k2=0;k2<d;k2++) cout << " " ;
cout << "else if " << *p << " < " << sLetter.at(v.size()) << " then" << endl;
}
v.insert(v.begin()+v.size()-k1,1,sLetter.at(v.size()));
run(d+1);
v.erase(v.begin()+v.size()-k1-1,v.begin()+v.size()-k1);
}
}
[/cpp]