110 - Meta-Loopless Sorts

[dawynn]

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

[ywliu]

oh....i got it.....and accept.......
and i will not take the same mistake.
thx....

[ywliu]

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.

[lowai]

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]

[Ivan Golubev]

There can be input like:

Code: Select all

2

1
2
3
4

5
6
7
8

As I can understand your solution cannot handle such input properly.

[lowai]

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

[Ivan Golubev]

Looking at the accepted percentage I won't be surprised that problem's description is a bit incomplete...

Anyway, your solution produces incorrect code for n == 1.

[junjieliang]

No, the problem is in multiple input. My program can handle these cases:

3
1
2
3

or

3
1

2
3

but will not handle

2
1
2

3

For the last case it will only produce output for 1 and 2...

Was that any help?

[lowai]

what is the correct output of n==1?

[Ivan Golubev]

what is the correct output of n==1?

Exactly three semi-colons must appear in the program

after the program header: program sort(input,output);
after the variable declaration: ...: integer;
after the readln statement: readln(...);

[lowai]

thank you.
i found my program produces a ";" after "writeln(a)" when n == 1.
i removed it and got accepted.

[chinaluoqi]

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

[Ivan Golubev]

I have read all the threads about this problem, and havenot found the bug in my program.

All threads? Really? So why you aren't handle multiple input properly?

[epsilon0]

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 )

[chinaluoqi]

multiple input ?
Does this handle it ?
[cpp]
while (cin >> _n)
{
...
}
[/cpp]

Maybe I have made mistake in understanding, Can anyone explain it exactly to me ?
Thanks for help, everyone.