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

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

Post by 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
New poster
Posts: 9
Joined: Thu Aug 22, 2002 7:32 am
Location: Taiwan

Post by ywliu »

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

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

Post by 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
New poster
Posts: 48
Joined: Mon Apr 29, 2002 1:26 pm

110

Post by 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
Experienced poster
Posts: 167
Joined: Fri Oct 19, 2001 2:00 am
Location: Saint Petersburg, Russia

Post by 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
New poster
Posts: 48
Joined: Mon Apr 29, 2002 1:26 pm

Post by 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
Experienced poster
Posts: 167
Joined: Fri Oct 19, 2001 2:00 am
Location: Saint Petersburg, Russia

Post by 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
Experienced poster
Posts: 169
Joined: Wed Oct 31, 2001 2:00 am
Location: Singapore

Post by 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
New poster
Posts: 48
Joined: Mon Apr 29, 2002 1:26 pm

Post by lowai »

what is the correct output of n==1?

Ivan Golubev
Experienced poster
Posts: 167
Joined: Fri Oct 19, 2001 2:00 am
Location: Saint Petersburg, Russia

Post by Ivan Golubev »

lowai wrote: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
New poster
Posts: 48
Joined: Mon Apr 29, 2002 1:26 pm

Post by lowai »

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

chinaluoqi
New poster
Posts: 4
Joined: Mon Jan 27, 2003 10:32 am
Location: China ( Mainland )

#110 WA Why? I'm going to be mad!

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

Post by Ivan Golubev »

chinaluoqi wrote: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
Experienced poster
Posts: 112
Joined: Tue Nov 12, 2002 11:15 pm
Location: Paris, France.

Post by 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 :P)
We never perform a computation ourselves, we just hitch a ride on the great Computation that is going on already. --Tomasso Toffoli

chinaluoqi
New poster
Posts: 4
Joined: Mon Jan 27, 2003 10:32 am
Location: China ( Mainland )

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

Post Reply

Return to “Volume 1 (100-199)”