## 110 - Meta-Loopless Sorts

Moderator: Board moderators

nghiank
New poster
Posts: 31
Joined: Wed Nov 20, 2002 3:10 pm
Contact:
???
Last edited by nghiank on Sun Apr 22, 2007 3:35 pm, edited 1 time in total.

epsilon0
Experienced poster
Posts: 112
Joined: Tue Nov 12, 2002 11:15 pm
Location: Paris, France.
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 ???
We never perform a computation ourselves, we just hitch a ride on the great Computation that is going on already. --Tomasso Toffoli

nghiank
New poster
Posts: 31
Joined: Wed Nov 20, 2002 3:10 pm
Contact:
I don't know if the following output is correct:

program sort(input,output);
var
a,b,c : integer;
begin
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

epsilon0
Experienced poster
Posts: 112
Joined: Tue Nov 12, 2002 11:15 pm
Location: Paris, France.
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.
We never perform a computation ourselves, we just hitch a ride on the great Computation that is going on already. --Tomasso Toffoli

nealzane
New poster
Posts: 23
Joined: Tue Dec 10, 2002 2:13 am
Location: China
Contact:

### 110 w.a.

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 << '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
Experienced poster
Posts: 120
Joined: Wed Mar 05, 2003 10:40 am
Location: Indonesia
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
New poster
Posts: 23
Joined: Tue Dec 10, 2002 2:13 am
Location: China
Contact:
thanks.

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

Diskerr
New poster
Posts: 16
Joined: Sun Apr 06, 2003 8:43 am
Location: Korea, Republic of

### .

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 :
(A blank line)
.
.
.
(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
Last edited by Diskerr on Sun May 18, 2003 6:45 pm, edited 3 times in total.
Sorry for my poor English.

nealzane
New poster
Posts: 23
Joined: Tue Dec 10, 2002 2:13 am
Location: China
Contact:
thanks a lot. that's gonna help much.

nealzane
New poster
Posts: 23
Joined: Tue Dec 10, 2002 2:13 am
Location: China
Contact:
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
New poster
Posts: 23
Joined: Tue Dec 10, 2002 2:13 am
Location: China
Contact:
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
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

### 110 - WA

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
Learning poster
Posts: 67
Joined: Fri Jul 04, 2003 9:59 am
Location: USA
Contact:

### Looks like you're doing fine.

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
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:
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
Learning poster
Posts: 67
Joined: Fri Jul 04, 2003 9:59 am
Location: USA
Contact:
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.