110 - Meta-Loopless Sorts
Moderator: Board moderators
This is why we have Search functionality on this board. Before submitting a new thread, its always a good idea to see if someone has covered your problem before. If they have, see if your question about the problem has already been raised. Whether or not it has, questions about the same problem should be handled in the same thread.
http://acm.uva.es/board/viewtopic.php?t=933
http://acm.uva.es/board/viewtopic.php?t=901
In this case, your question has already been answered. You are experiencing the same common mistake that the rest of us did. This is a multiple-input program. Please read about multiple-inputs:
http://acm.uva.es/problemset/minput.html
http://acm.uva.es/board/viewtopic.php?t=933
http://acm.uva.es/board/viewtopic.php?t=901
In this case, your question has already been answered. You are experiencing the same common mistake that the rest of us did. This is a multiple-input program. Please read about multiple-inputs:
http://acm.uva.es/problemset/minput.html
but i have a new thorny problem now.
during solving program, i always send solved program. and get WA..
and i think my program is no problem. and i have some test data.
and all result is right . but always get WA.
i already have four programs with problem like above description
it is respective 112 , 114 , 123 , 147.
i always think that output form may be error.
but i don't find bug all the way.
so.....i hope someone can help me find bug.
during solving program, i always send solved program. and get WA..
and i think my program is no problem. and i have some test data.
and all result is right . but always get WA.
i already have four programs with problem like above description
it is respective 112 , 114 , 123 , 147.
i always think that output form may be error.
but i don't find bug all the way.
so.....i hope someone can help me find bug.
110
why does this code get WA?
[pascal]
const
c : string = 'abcdefgh';
var
d : array[1..8] of char;
i, n, cases : integer;
procedure search(k : integer);
var
i, j : integer;
old : array[1..8] of char;
begin
if k > n then
begin
for i := 1 to k - 1 do write(' ');
write('writeln(');
for i := 1 to n - 1 do write(d,',');
writeln(d[n], ')');
exit;
end;
for i := 1 to 8 do old := d;
for i := 1 to k - 1 do
write(' ');
writeln('if ',old[k-1],' < ',c[k],' then');
d[k] := c[k];
search(k + 1);
for i := k - 1 downto 2 do
begin
for j := 1 to k - 1 do write(' ');
writeln('else if ', old, ' < ', c[k], ' then');
for j := 1 to i do d[j] := old[j];
for j := i + 1 to k do d[j] := old[j - 1];
d := c[k];
search(k + 1);
end;
for i := 1 to k - 1 do write(' ');
writeln('else');
for i := 1 to k - 1 do d[i + 1] := old;
d[1] := c[k];
search(k + 1);
for i := 1 to 8 do d := old;
end;
begin
readln(cases);
repeat
readln(n);
writeln('program sort(input,output);');
writeln('var');
for i := 1 to n - 1 do write(c, ',');
writeln(c[n],' : integer;');
writeln('begin');
write(' readln(');
for i := 1 to n - 1 do write(c,',');
writeln(c[n],');');
if n = 1 then
begin
writeln(' writeln(a);');
writeln('end.');
end
else
begin
writeln(' if a < b then');
d[1] := 'a';
d[2] := 'b';
search(3);
writeln(' else');
d[1] := 'b';
d[2] := 'a';
search(3);
writeln('end.');
end;
dec(cases);
if cases > 0 then writeln;
until cases = 0;
end.
[/pascal]
[pascal]
const
c : string = 'abcdefgh';
var
d : array[1..8] of char;
i, n, cases : integer;
procedure search(k : integer);
var
i, j : integer;
old : array[1..8] of char;
begin
if k > n then
begin
for i := 1 to k - 1 do write(' ');
write('writeln(');
for i := 1 to n - 1 do write(d,',');
writeln(d[n], ')');
exit;
end;
for i := 1 to 8 do old := d;
for i := 1 to k - 1 do
write(' ');
writeln('if ',old[k-1],' < ',c[k],' then');
d[k] := c[k];
search(k + 1);
for i := k - 1 downto 2 do
begin
for j := 1 to k - 1 do write(' ');
writeln('else if ', old, ' < ', c[k], ' then');
for j := 1 to i do d[j] := old[j];
for j := i + 1 to k do d[j] := old[j - 1];
d := c[k];
search(k + 1);
end;
for i := 1 to k - 1 do write(' ');
writeln('else');
for i := 1 to k - 1 do d[i + 1] := old;
d[1] := c[k];
search(k + 1);
for i := 1 to 8 do d := old;
end;
begin
readln(cases);
repeat
readln(n);
writeln('program sort(input,output);');
writeln('var');
for i := 1 to n - 1 do write(c, ',');
writeln(c[n],' : integer;');
writeln('begin');
write(' readln(');
for i := 1 to n - 1 do write(c,',');
writeln(c[n],');');
if n = 1 then
begin
writeln(' writeln(a);');
writeln('end.');
end
else
begin
writeln(' if a < b then');
d[1] := 'a';
d[2] := 'b';
search(3);
writeln(' else');
d[1] := 'b';
d[2] := 'a';
search(3);
writeln('end.');
end;
dec(cases);
if cases > 0 then writeln;
until cases = 0;
end.
[/pascal]
-
- Experienced poster
- Posts: 167
- Joined: Fri Oct 19, 2001 2:00 am
- Location: Saint Petersburg, Russia
There can be input like:As I can understand your solution cannot handle such input properly.
Code: Select all
2
1
2
3
4
5
6
7
8
but the problem said "The input is a single integer n on a line by itself with 1 <= n <= 8". so i don't think the input above is legal. it should be
Code: Select all
8
1
2
3
4
5
6
7
8
-
- Experienced poster
- Posts: 167
- Joined: Fri Oct 19, 2001 2:00 am
- Location: Saint Petersburg, Russia
-
- Experienced poster
- Posts: 169
- Joined: Wed Oct 31, 2001 2:00 am
- Location: Singapore
-
- Experienced poster
- Posts: 167
- Joined: Fri Oct 19, 2001 2:00 am
- Location: Saint Petersburg, Russia
-
- New poster
- Posts: 4
- Joined: Mon Jan 27, 2003 10:32 am
- Location: China ( Mainland )
#110 WA Why? I'm going to be mad!
I have read all the threads about this problem, and havenot found the bug in my program.
Can you help me, thanks.
[cpp]
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
const int _maxN = 10;
char _a [_maxN];
int _n;
void OutputA ()
{
int i;
for (i = 0; i < _n - 1; i ++)
cout << _a << ',';
cout << _a ;
}
void P (int ind)
{
int i, j, t;
if (ind == _n)
{
cout << string (ind * 2, ' ');
cout << "writeln(";
OutputA ();
cout << ')' << endl;
}
else if (ind > 0)
{
cout << string (ind * 2, ' ');
cout << "if " << _a [ind - 1] << " < " << _a [ind] <<
" then" << endl;
P (ind + 1);
for (i = ind - 1; i > 0; i --)
{
swap (_a , _a [i + 1] );
cout << string (ind * 2, ' ');
cout << "else if " << _a << " < " << _a <<
" then" << endl;
P (ind + 1);
}
swap(_a [0], _a [1]);
cout << string (ind * 2, ' ');
cout << "else" << endl;
P (ind + 1);
t = _a [0];
for (j = 0; j < ind; j ++) _a [j] = _a [j + 1];
_a [ind] = t;
}
}
main ()
{
int i;
while (cin >> _n)
{
for (i = 0; i < _n; i ++)
_a = char ('a' + i);
cout << "program sort(input,output);" << endl <<
"var" << endl;
OutputA ();
cout << " : integer;" << endl;
cout << "begin" << endl;
cout << " readln(";
OutputA ();
cout << ");" << endl;
P (1);
cout << "end." << endl;
}
}
[/cpp]
I am afaid of seeing "WA" again
Can you help me, thanks.
[cpp]
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
const int _maxN = 10;
char _a [_maxN];
int _n;
void OutputA ()
{
int i;
for (i = 0; i < _n - 1; i ++)
cout << _a << ',';
cout << _a ;
}
void P (int ind)
{
int i, j, t;
if (ind == _n)
{
cout << string (ind * 2, ' ');
cout << "writeln(";
OutputA ();
cout << ')' << endl;
}
else if (ind > 0)
{
cout << string (ind * 2, ' ');
cout << "if " << _a [ind - 1] << " < " << _a [ind] <<
" then" << endl;
P (ind + 1);
for (i = ind - 1; i > 0; i --)
{
swap (_a , _a [i + 1] );
cout << string (ind * 2, ' ');
cout << "else if " << _a << " < " << _a <<
" then" << endl;
P (ind + 1);
}
swap(_a [0], _a [1]);
cout << string (ind * 2, ' ');
cout << "else" << endl;
P (ind + 1);
t = _a [0];
for (j = 0; j < ind; j ++) _a [j] = _a [j + 1];
_a [ind] = t;
}
}
main ()
{
int i;
while (cin >> _n)
{
for (i = 0; i < _n; i ++)
_a = char ('a' + i);
cout << "program sort(input,output);" << endl <<
"var" << endl;
OutputA ();
cout << " : integer;" << endl;
cout << "begin" << endl;
cout << " readln(";
OutputA ();
cout << ");" << endl;
P (1);
cout << "end." << endl;
}
}
[/cpp]
I am afaid of seeing "WA" again

-
- Experienced poster
- Posts: 167
- Joined: Fri Oct 19, 2001 2:00 am
- Location: Saint Petersburg, Russia
Re: #110 WA Why? I'm going to be mad!
All threads? Really? So why you aren't handle multiple input properly?chinaluoqi wrote:I have read all the threads about this problem, and havenot found the bug in my program.
Ivan Golubev is right about multiple input. read the page about multiple input format!
i just solved this problem and i thought it was hard! until i found a simple recursion to do it.
btw is anyone able to compile the pascal program from n = 8? it almost stuck my box. 20000+ lines of if/then/else !!!
i'm glad i "finally" solved it (being stuck a few hours is a long time for me
)
i just solved this problem and i thought it was hard! until i found a simple recursion to do it.
btw is anyone able to compile the pascal program from n = 8? it almost stuck my box. 20000+ lines of if/then/else !!!
i'm glad i "finally" solved it (being stuck a few hours is a long time for me

We never perform a computation ourselves, we just hitch a ride on the great Computation that is going on already. --Tomasso Toffoli
-
- New poster
- Posts: 4
- Joined: Mon Jan 27, 2003 10:32 am
- Location: China ( Mainland )