110 - Meta-Loopless Sorts

[Dion]

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
readln(a,b,c,d);
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]

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[0]);
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);
printf(" : integer;nbeginn readln(");
printvar(var);
printf(");n");
sort(var, 1);
printf("end.n");
}
return 1;
}

[Ivan Golubev]

Don't care about indentation, this problem has multiple input and you aren't handle it.

[Dion]

Doh! Taught me to read the docs first. I thought multiple input was simply a different number on a separate line.

Thanks!

[lundril]

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]

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]

Sure problem has a multiple input.

Check your output for
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]

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";
	
	outs << "  readln(";
    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[2] = " ";

    strcpy(s, ins);
    
    indentLevel++;
    
    if(strlen(s) == length) {
		PrintIt(s);
    } else {
		Indent();
		len = strlen(s);
		buf[0] = '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]

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]

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[10];

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[10];
			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[10];
		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";
		outs << "  readln(";
		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
readln(a,b,c,d,e);
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]

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]

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]

Multiple input is BLUE icon:)

[Stefan Pochmann]

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]

I never do green problems. Special correction scares me; never got one of those AC yet...