110 - Meta-Loopless Sorts
Moderator: Board moderators
problem 110 for help
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]
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]
-
- A great helper
- Posts: 284
- Joined: Thu Feb 28, 2002 2:00 am
- Location: Germany
- Contact:
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
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
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.
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.

-
- A great helper
- Posts: 284
- Joined: Thu Feb 28, 2002 2:00 am
- Location: Germany
- Contact:
Wrong Answer: 110 - why??
????????????
[c]@BEGIN_OF_SOURCE_CODE
/* @JUDGE_ID: ******* 110 C "Recursive" */
@END_OF_SOURCE_CODE[/c]
[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.
-
- Experienced poster
- Posts: 167
- Joined: Fri Oct 19, 2001 2:00 am
- Location: Saint Petersburg, Russia
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');
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.
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.
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.
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
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
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;
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]
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]