## 110 - Meta-Loopless Sorts

Moderator: Board moderators

click xx
New poster
Posts: 10
Joined: Mon May 13, 2002 9:42 am

### problem 110 for help

#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;
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
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:
Where do you handle the multiple input?

click xx
New poster
Posts: 10
Joined: Mon May 13, 2002 9:42 am
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
New poster
Posts: 10
Joined: Mon May 13, 2002 9:42 am
oh,I finally know what's going on now.
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
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:
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
New poster
Posts: 10
Joined: Mon May 13, 2002 9:42 am
Thanks.I'll be more careful next time.

youngwook
New poster
Posts: 5
Joined: Wed Jul 17, 2002 8:15 am
Location: Seoul

### Wrong Answer: 110 - why??

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

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

@END_OF_SOURCE_CODE[/c]
Last edited by youngwook on Thu Jul 18, 2002 1:01 pm, edited 3 times in total.

Ivan Golubev
Experienced poster
Posts: 167
Joined: Fri Oct 19, 2001 2:00 am
Location: Saint Petersburg, Russia
It's multiple input problem. Did you read message under exclamation icon?

youngwook
New poster
Posts: 5
Joined: Wed Jul 17, 2002 8:15 am
Location: Seoul
thanx!!

yeung
New poster
Posts: 6
Joined: Sun Jul 21, 2002 10:45 am

### WA: Problem 110 Why???

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');
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
for i:=1 to m do
begin
doing;
writeln;
end;
end.

dawynn
New poster
Posts: 47
Joined: Fri Jun 21, 2002 3:08 pm
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
New poster
Posts: 6
Joined: Sun Jul 21, 2002 10:45 am
thanks

dawynn
New poster
Posts: 47
Joined: Fri Jun 21, 2002 3:08 pm
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
New poster
Posts: 6
Joined: Sun Jul 21, 2002 10:45 am
Thank you very much!

ywliu
New poster
Posts: 9
Joined: Thu Aug 22, 2002 7:32 am
Location: Taiwan

### 110 i don't find bug....

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;
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]