## 110 - Meta-Loopless Sorts

Moderator: Board moderators

Dion
New poster
Posts: 3
Joined: Sun Jan 20, 2002 2:00 am
Contact:
I keep getting WA for problem 110, even though the output program contains all possible cases, n! writeln and n!-1 if statements, and handles multiple inputs. Can anyone tell me what's wrong with this output?

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

Dion
New poster
Posts: 3
Joined: Sun Jan 20, 2002 2:00 am
Contact:
FWIW this is the source code of my program. BTW, all the indentation of the output is there, it's just not shown on the page after posting it.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_VAR 8
int n;

void printvar(char buf[MAX_VAR]) {
int i;

printf("%c", buf);
for (i = 1; i < n; i++)
printf(",%c", buf);
}

void printmargin(int m) {
int i;

for (i = 0; i < m * 2; i++)
printf(" ");
}

void sort(char old[MAX_VAR], int m) {
char buf[MAX_VAR];
char tmp;
int i;

if (m == n) {
printmargin(m);
printf("writeln(");
printvar(old);
printf(")n");
return;
}

memcpy(buf, old, sizeof(char) * MAX_VAR);
printmargin(m);
printf("if %c < %c thenn", buf[m - 1], buf[m]);
sort(buf, m + 1);

for (i = m - 1; i >= 0; i--) {
tmp = buf;
buf = buf[i + 1];
buf[i + 1] = tmp;
printmargin(m);
if (i > 0)
printf("else if %c < %c thenn", buf, buf);
else
printf("elsen");
sort(buf, m + 1);
}
}

int main(void) {
char var[MAX_VAR];
int i;

for (i = 0; i < MAX_VAR; i++)
var = 97 + i;

while (scanf("%d", &n) == 1) {
printf("program sort(input,output);nvarn");
printvar(var);
printvar(var);
printf(");n");
sort(var, 1);
printf("end.n");
}
return 1;
}

Ivan Golubev
Experienced poster
Posts: 167
Joined: Fri Oct 19, 2001 2:00 am
Location: Saint Petersburg, Russia
Don't care about indentation, this problem has multiple input and you aren't handle it.

Dion
New poster
Posts: 3
Joined: Sun Jan 20, 2002 2:00 am
Contact:
Doh! Taught me to read the docs first. I thought multiple input was simply a different number on a separate line.

Thanks!

lundril
New poster
Posts: 6
Joined: Tue Mar 19, 2002 2:00 am
Contact:
Hi,

I just solved problem 110 with a presentation
error. Now I am curious why I get one...

Is this problem multiple input or not
(it says so in the problem list, but not
in the text of the problem itself...)

so long
lundril

shahriar_manzoor
Posts: 399
Joined: Sat Jan 12, 2002 2:00 am
Hello,
There will be no such indication in the problem statement that the problem is multiple input. If there was then it would have been a problem with multiple dataset and not multiple input problem. You should not worry about PE in case of multiple input problems as in real contests there will be no such multiple input problems but there may be problems with multiple datasets.

Max Fate
New poster
Posts: 6
Joined: Fri Mar 15, 2002 2:00 am
Sure problem has a multiple input.

1) single blank line between testcases
2) no blank line at the end of the file
3) I'm not sure but you may check if any line contains space(s) at the end

With 1) and 2) I have fixed PE

paulhryu
New poster
Posts: 45
Joined: Sat Jan 26, 2002 2:00 am
Contact:

### 110 - Meta-Loopless Sorts

See, I have solved this, found it doesn't work (though it looks fine to me), found two other solutions floating around on the web which produce the same answer, and big surprise, they don't work.

Can anybody tell me if this program generates the right cases for up to n equals 8?

Code: Select all

``````[cpp]

#include <iostream.h>
#include <fstream.h>
#include <string.h>

#ifdef ONLINE_JUDGE
#define ins cin
#define outs cout
#else
#define ins fin
#define outs fout
ifstream fin("myprog.in");
ofstream fout("myprog.out");
#endif

#define MAX	400

void permute(char *);
void Indent(void);

int indentLevel, length;

int main() {
int i;
char buf[MAX], *s;

ins >> length;

outs << "program sort(input,output);\n";
outs << "var\n";

for(i = 0; i < length - 1; i++)
outs << (char) ('a' + i) << ",";

outs << (char) ('a' + i);
outs << " : integer;\n";
outs << "begin\n";

for(i = 0; i < length - 1; i++)
outs << (char) ('a' + i) << ",";

outs << (char) ('a' + i) << ");\n";

indentLevel = 0;
s = strcpy(buf, "a");
permute(s);

outs << "end.\n";
return 0;
}

void PrintIt(char *s) {
int i;

Indent();
outs << "writeln(";
for(i = 0; i < strlen(s) - 1; i++)
outs << s[i] << ",";

outs << s[i] << ")\n";
}

void Swap(char *s, int n) {
char temp;

temp = s[n - 1];
s[n - 1] = s[n];
s[n] = temp;
}

void permute(char *ins) {
int i, len;
char s[MAX];
char buf = " ";

strcpy(s, ins);

indentLevel++;

if(strlen(s) == length) {
PrintIt(s);
} else {
Indent();
len = strlen(s);
buf = 'a' + (len++);
strcat(s, buf);

outs << "if " << s[len - 2] << " < " << s[len - 1] << " then\n";
permute(s);

Swap(s, len - 1);

for(i = len - 1; i > 1; i--){
Indent();
outs << "else if " << s[i - 2] << " < " << s[i - 1] << " then\n";
permute(s);
Swap(s, i - 1);
}

Indent();
outs << "else\n";
permute(s);
}

indentLevel--;
}

void Indent() {
int i;

for(i = 0; i < indentLevel; i++)
outs << "  ";
}[/cpp]``````

Ivan Golubev
Experienced poster
Posts: 167
Joined: Fri Oct 19, 2001 2:00 am
Location: Saint Petersburg, Russia
To get accepted on this one your solution need to:

1. Contains exactly n! writeln statements.
2. Contains exactly n! - 1 if ... then statements.
3. Correctly sort all possible permutations of input data.
4. Properly handle multiple input.

paulhryu
New poster
Posts: 45
Joined: Sat Jan 26, 2002 2:00 am
Contact:

### See, I have this:

Code: Select all

``````// @BEGIN_OF_SOURCE_CODE

/* @JUDGE_ID:  17243NT  110  C++  "<img src='http://http://acm.uva.es/problemset/flags/us.gif'>" */

// Send to judge@uva.es

#include <fstream.h>
#include <iomanip.h>
#include <string.h>
#include <iostream.h>

#ifdef ONLINE_JUDGE
#define ins cin
#define outs cout
#else
#define ins fin
#define outs fout
ifstream fin("myprog.in");
ofstream fout("myprog.out");
#endif

int n;
char str;

void indent(int k) {
for(int i = 0; i < k; i++)
outs << "  ";
}

void recursion(int k) {
char c = 'a' + k;
int i, j;

str[k] = c;

for(i = k; i > 0; i--) {
indent(k);
if(i < k) outs << "else ";
outs << "if " << str[i - 1] << " < " << c << " then\n";

if(k < n - 1) {
char temp;
strcpy(temp, str);
recursion(k + 1);
strcpy(str, temp);
} else {
indent(k + 1);
outs << "writeln(";
for(j = 0; j < k; j++)
outs << str[j] << ",";
outs << str[j] << ")\n";
}

if(i == 1) {
indent(k);
outs << "else" << endl;
}

char t = str[i];
str[i] = str[i - 1];
str[i - 1] = t;
}

if(k < n - 1) {
char temp;
strcpy(temp, str);
recursion(k + 1);
strcpy(str, temp);
} else {
indent(k + 1);
outs << "writeln(";
for(j = 0; j < k; j++)
outs << str[j] << ",";
outs << str[j] << ")\n";
}
}

int main() {
int i;

while(ins >> n) {
outs << "program sort(input,output);\n";
outs << "var\n";
for(i = 0; i < n - 1; i++)
outs << (char) (i + 'a') << ",";
outs << (char) (i + 'a') << " : integer;\n";

outs << "begin\n";
for(i = 0; i < n - 1; i++)
outs << (char) (i + 'a') << ",";
outs << (char) (i + 'a') << ");\n";

recursion(0);
outs << "end.\n";
}

return 0;
}

// @END_OF_SOURCE_CODE``````
and the output I get for n = 5 is:
[pascal]program sort(input,output);
var
a,b,c,d,e : integer;
begin
if a < b then
if b < c then
if c < d then
if d < e then
writeln(a,b,c,d,e)
else if c < e then
writeln(a,b,c,e,d)
else if b < e then
writeln(a,b,e,c,d)
else if a < e then
writeln(a,e,b,c,d)
else
writeln(e,a,b,c,d)
else if b < d then
if c < e then
writeln(a,b,d,c,e)
else if d < e then
writeln(a,b,d,e,c)
else if b < e then
writeln(a,b,e,d,c)
else if a < e then
writeln(a,e,b,d,c)
else
writeln(e,a,b,d,c)
else if a < d then
if c < e then
writeln(a,d,b,c,e)
else if b < e then
writeln(a,d,b,e,c)
else if d < e then
writeln(a,d,e,b,c)
else if a < e then
writeln(a,e,d,b,c)
else
writeln(e,a,d,b,c)
else
if c < e then
writeln(d,a,b,c,e)
else if b < e then
writeln(d,a,b,e,c)
else if a < e then
writeln(d,a,e,b,c)
else if d < e then
writeln(d,e,a,b,c)
else
writeln(e,d,a,b,c)
else if a < c then
if b < d then
if d < e then
writeln(a,c,b,d,e)
else if b < e then
writeln(a,c,b,e,d)
else if c < e then
writeln(a,c,e,b,d)
else if a < e then
writeln(a,e,c,b,d)
else
writeln(e,a,c,b,d)
else if c < d then
if b < e then
writeln(a,c,d,b,e)
else if d < e then
writeln(a,c,d,e,b)
else if c < e then
writeln(a,c,e,d,b)
else if a < e then
writeln(a,e,c,d,b)
else
writeln(e,a,c,d,b)
else if a < d then
if b < e then
writeln(a,d,c,b,e)
else if c < e then
writeln(a,d,c,e,b)
else if d < e then
writeln(a,d,e,c,b)
else if a < e then
writeln(a,e,d,c,b)
else
writeln(e,a,d,c,b)
else
if b < e then
writeln(d,a,c,b,e)
else if c < e then
writeln(d,a,c,e,b)
else if a < e then
writeln(d,a,e,c,b)
else if d < e then
writeln(d,e,a,c,b)
else
writeln(e,d,a,c,b)
else
if b < d then
if d < e then
writeln(c,a,b,d,e)
else if b < e then
writeln(c,a,b,e,d)
else if a < e then
writeln(c,a,e,b,d)
else if c < e then
writeln(c,e,a,b,d)
else
writeln(e,c,a,b,d)
else if a < d then
if b < e then
writeln(c,a,d,b,e)
else if d < e then
writeln(c,a,d,e,b)
else if a < e then
writeln(c,a,e,d,b)
else if c < e then
writeln(c,e,a,d,b)
else
writeln(e,c,a,d,b)
else if c < d then
if b < e then
writeln(c,d,a,b,e)
else if a < e then
writeln(c,d,a,e,b)
else if d < e then
writeln(c,d,e,a,b)
else if c < e then
writeln(c,e,d,a,b)
else
writeln(e,c,d,a,b)
else
if b < e then
writeln(d,c,a,b,e)
else if a < e then
writeln(d,c,a,e,b)
else if c < e then
writeln(d,c,e,a,b)
else if d < e then
writeln(d,e,c,a,b)
else
writeln(e,d,c,a,b)
else
if a < c then
if c < d then
if d < e then
writeln(b,a,c,d,e)
else if c < e then
writeln(b,a,c,e,d)
else if a < e then
writeln(b,a,e,c,d)
else if b < e then
writeln(b,e,a,c,d)
else
writeln(e,b,a,c,d)
else if a < d then
if c < e then
writeln(b,a,d,c,e)
else if d < e then
writeln(b,a,d,e,c)
else if a < e then
writeln(b,a,e,d,c)
else if b < e then
writeln(b,e,a,d,c)
else
writeln(e,b,a,d,c)
else if b < d then
if c < e then
writeln(b,d,a,c,e)
else if a < e then
writeln(b,d,a,e,c)
else if d < e then
writeln(b,d,e,a,c)
else if b < e then
writeln(b,e,d,a,c)
else
writeln(e,b,d,a,c)
else
if c < e then
writeln(d,b,a,c,e)
else if a < e then
writeln(d,b,a,e,c)
else if b < e then
writeln(d,b,e,a,c)
else if d < e then
writeln(d,e,b,a,c)
else
writeln(e,d,b,a,c)
else if b < c then
if a < d then
if d < e then
writeln(b,c,a,d,e)
else if a < e then
writeln(b,c,a,e,d)
else if c < e then
writeln(b,c,e,a,d)
else if b < e then
writeln(b,e,c,a,d)
else
writeln(e,b,c,a,d)
else if c < d then
if a < e then
writeln(b,c,d,a,e)
else if d < e then
writeln(b,c,d,e,a)
else if c < e then
writeln(b,c,e,d,a)
else if b < e then
writeln(b,e,c,d,a)
else
writeln(e,b,c,d,a)
else if b < d then
if a < e then
writeln(b,d,c,a,e)
else if c < e then
writeln(b,d,c,e,a)
else if d < e then
writeln(b,d,e,c,a)
else if b < e then
writeln(b,e,d,c,a)
else
writeln(e,b,d,c,a)
else
if a < e then
writeln(d,b,c,a,e)
else if c < e then
writeln(d,b,c,e,a)
else if b < e then
writeln(d,b,e,c,a)
else if d < e then
writeln(d,e,b,c,a)
else
writeln(e,d,b,c,a)
else
if a < d then
if d < e then
writeln(c,b,a,d,e)
else if a < e then
writeln(c,b,a,e,d)
else if b < e then
writeln(c,b,e,a,d)
else if c < e then
writeln(c,e,b,a,d)
else
writeln(e,c,b,a,d)
else if b < d then
if a < e then
writeln(c,b,d,a,e)
else if d < e then
writeln(c,b,d,e,a)
else if b < e then
writeln(c,b,e,d,a)
else if c < e then
writeln(c,e,b,d,a)
else
writeln(e,c,b,d,a)
else if c < d then
if a < e then
writeln(c,d,b,a,e)
else if b < e then
writeln(c,d,b,e,a)
else if d < e then
writeln(c,d,e,b,a)
else if c < e then
writeln(c,e,d,b,a)
else
writeln(e,c,d,b,a)
else
if a < e then
writeln(d,c,b,a,e)
else if b < e then
writeln(d,c,b,e,a)
else if c < e then
writeln(d,c,e,b,a)
else if d < e then
writeln(d,e,c,b,a)
else
writeln(e,d,c,b,a)
end.[/pascal]

Any ideas?

paulhryu
New poster
Posts: 45
Joined: Sat Jan 26, 2002 2:00 am
Contact:

### Problem 110 HAS to be wrong

I am hereby convinced that... the judge for problem 110 doesn't work. It's just amazing how many things I've tried on it, even sample solutions from other websites, and guess what, they don't work.

Also, the problem description for 199 needs to be corrected. Sample b vector is -35 -188 -189 -315. And the directions for 197 need to be revised.

Anyways... last of all, C++ syntax highlighting doesn't work.

paulhryu
New poster
Posts: 45
Joined: Sat Jan 26, 2002 2:00 am
Contact:
I feel flabbergastingly stupid... but I had never done a multiple input problem before (haha, I was stuck on volume 1) so... anyways... it works, just can you make it clear about how to do multiple input IN the problem description, not by a little green icon next to it. Thanks.

C8H10N4O2
Experienced poster
Posts: 137
Joined: Wed Feb 27, 2002 2:00 am
Multiple input is BLUE icon:)

Stefan Pochmann
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:
Even though it has cost me some time, too, I'd say that the blue or green (it's indeed green there, James) icon is enough.

Furthermore, in this specific example, the multiple input thing was explicitly mentioned in the fix explanation (click on the "!" right to the problem).

What's wrong with the syntax highlighting? You know, it's always better to say *what* is wrong than to just say *that* something is wrong.

C8H10N4O2
Experienced poster
Posts: 137
Joined: Wed Feb 27, 2002 2:00 am