110 - Meta-Loopless Sorts

All about problems in Volume 1. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

problem 110 for help

Post by 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
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:

Post by Stefan Pochmann »

Where do you handle the multiple input?

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

Post by 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
New poster
Posts: 10
Joined: Mon May 13, 2002 9:42 am

Post by 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. :oops:

Stefan Pochmann
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:

Post by 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
New poster
Posts: 10
Joined: Mon May 13, 2002 9:42 am

Post by click xx »

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??

Post by youngwook »

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

[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

Post by Ivan Golubev »

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

Post by youngwook »

thanx!!

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

WA: Problem 110 Why???

Post by 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
New poster
Posts: 47
Joined: Fri Jun 21, 2002 3:08 pm

Post by 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
New poster
Posts: 6
Joined: Sun Jul 21, 2002 10:45 am

Post by yeung »

thanks

dawynn
New poster
Posts: 47
Joined: Fri Jun 21, 2002 3:08 pm

Post by 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
New poster
Posts: 6
Joined: Sun Jul 21, 2002 10:45 am

Post by yeung »

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....

Post by 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]

Post Reply

Return to “Volume 1 (100-199)”