110 - Meta-Loopless Sorts

[nghiank]

???

[epsilon0]

chinaluoqi your program is very good, you just need to read this:
http://acm.uva.es/problemset/minput.html
to make multiple input work.

just add a cin >> n; in start of your prog and it will work.

nghiank what do you mean ???

[nghiank]

I don't know if the following output is correct:

program sort(input,output);
var
a,b,c : integer;
begin
readln(a,b,c);
if a < b then
if b < c then
writeln(a,b,c)
else
if a < c then
writeln(a,c,b)
else
writeln(c,a,b)
else
if a < c then
writeln(b,a,c)
else if b < c then
writeln(b,c,a)
else
writeln(c,b,a)
end.


I mean that we don't need to differ between "else" and "else if".We can write " else
if
" instead of "else if"

[epsilon0]

of course,

"else if" is not a keyword.

it's exactly the same as C/C++, each else is in relation with the closest if that is not already in relation with an else.

example:
if a then if b then c else d else e

the first else is related to the second if and the second else to the first if.

remove the "then"'s and add a couple of parenthesis around predicates and you got working C/C++ code. oh and a semicolon after instructions

if (a) if (b) c; else d; else e;

u don't need to take care of any "else if" case indeed.... my code for this problem doesn't anyway.

[nealzane]

i have got many w.a. for 110 but can't see anything wrong with the algorithm.

besides, there is a note for the problem that:

110 - Meta-Loopless Sorts
25/05/01, Warning: The limit for the value of n is now 8, to prevent people from sending just a table. Furthermore, now it's a multiple_input-special_corrector problem.

does this mean that the problem is now multiple-input? but in the problem description, it is still single input. which one shall i take? if it is multiple-input, is there any special formatting?

my code is as following:
[cpp]
/*
* Challenge Title: Meta-Loopless Sorts
* Created by : Neal Zane
* Date : April 30, 2003
*
* */

#include <iostream>
using namespace std;

int all, n;

void wln(char* s) {
int i;
for (i = 0; i < n; i ++)
cout << " ";
cout << "writeln(";
cout << s[0];
for (i = 1; i < n; i ++)
cout << ',' << s;
cout << ')' << endl;
}

char* insert(char* ret, char* org, int len, int pos, char ch) {
while (len > pos) {
ret[len ] = org[len - 1];
len --;
}
ret[len] = ch;
while (len --)
ret[len] = org[len];
return ret;
}

void indent(int d) {
while (d --) cout << " ";
}

void gen(char* pre, int used, int d) {
int i, j;
char buf[12];
if (used == all) {
wln(pre);
return;
}

for (i = 0; i < n; i ++)
if (!(used & (1 << i))) break;
{
indent(d);
insert(buf, pre, d, d, i + 'a');
cout << "if " << buf[d - 1] << " < " <<
buf[d] << " then" << endl;
gen(buf, used | (1 << i), d + 1);
for (j = d - 1; j; j --) {
indent(d);
insert(buf, pre, d, j, i + 'a');
cout << "else if " << buf[j - 1] << " < " <<
buf[j] << " then" << endl;
gen(buf, used | (1 << i), d + 1);
}
indent(d);
insert(buf, pre, d, 0, i + 'a');
cout << "else" << endl;
gen(buf, used | (1 << i), d + 1);
}
}

int main (void) {
int i;

while (cin >> n) {
all = (1 << n) - 1;

cout << "program sort(input,output);" << endl;
cout << "var" << endl;
cout << 'a';
for (i = 1; i < n; i ++)
cout << ',' << (char)(i + 'a');
cout << " : integer;" << endl;
cout << "begin" << endl;
cout << " readln(";
cout << 'a';
for (i = 1; i < n; i ++)
cout << ',' << (char)(i + 'a');
cout << ");" << endl;

gen("a", (1 << 0), 1);

cout << "end." << endl;
}

return 0;
}

[/cpp]

[Hisoka]

hello...

Yes this is multiple input problem. And for output format, like in sample output. I'm sorry, I'm not check your program in detail. but I think this is like knuth permutation, and output format.

[nealzane]

thanks.

but i am still in confusion. i even compared to official output (single case),
mine is identical to it.

[Diskerr]

Multiple input consists of
T <- the number of test cases
(A blank line)
Single test case 1
(A blank line)
Single test case 2
.
.
.
Single test case T

so, you must output following :
Answer for test case 1
(A blank line)
.
.
.
Answer for test case T
(If here exists a blank line, you will get PE)

Sample multiple input for problem 110

3 <- the number of test cases

3 <- test case 1

5 <- test case 2

6 <- test case 3

[nealzane]

thanks a lot. that's gonna help much.

[nealzane]

finally it seems UVA is setting this kind of format for multiple-input problems.

yet i can not find it in FAQ.

should ask the moderators to state the conditions clearer.

[nealzane]

i see it.
http://acm.uva.es/problemset/minput.html

i have wasted a lot of w.a.!

got to take care later.

[Krzysztof Duleba]

Hi!

First of all, is the example output for value 3 correct? Compiled with fpc, it doesn't show any spaces between numbers. Shouldn't all the writelines look like writeln(a,' ',b,' ',c, ...) instead of writeln(a,b,...)?
I tried both possibilites with no result. My output for value n=1,...,8 can be found on http://rainbow.mimuw.edu.pl/~kd209203/110/nx.gz, where x is a or b. Version a is such that 3a is the same as the example output, version b is the other one.
Can any of you take a look on my outputs and give me a hint what's wrong?

Regards

[Ryan Pai]

The output shouldn't have any space characters printed.

Your output for version A looks fine.

Did you notice that 110 is a multiple input problem?

http://acm.uva.es/problemset/minput.html

[Krzysztof Duleba]

Thanks for looking into my output files.
You're right that I missed that it's a multiple-input problem. I was misled by "The input is a single integer n on a line by itself".
I changed my solution to work this way but still I receive WA. I think there's no point to show my code here as everything it does is to display the metasorters that are in the files I published (and generate them at first). After every program blank-line is placed, so that's OK too. Anything else that I could have spoiled? Or should I show my code anyway?

[Ryan Pai]

Well, posting code can't hurt (it's easier to look for what's going wrong than idly guess at it).

Remember that the first number in the input isn't to be processed, it just tells how many input sets there are.