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

Post Reply
Dion
New poster
Posts: 3
Joined: Sun Jan 20, 2002 2:00 am
Contact:

Post by Dion » Sun Jan 20, 2002 12:43 pm

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
New poster
Posts: 3
Joined: Sun Jan 20, 2002 2:00 am
Contact:

Post by Dion » Sun Jan 20, 2002 12:46 pm

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

Post by Ivan Golubev » Sun Jan 20, 2002 1:32 pm

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:

Post by Dion » Sun Jan 20, 2002 2:00 pm

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:

Post by lundril » Tue Mar 19, 2002 5:48 pm

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
System administrator & Problemsetter
Posts: 399
Joined: Sat Jan 12, 2002 2:00 am

Post by shahriar_manzoor » Tue Mar 19, 2002 6:10 pm

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

Post by Max Fate » Tue Mar 19, 2002 9:23 pm

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
New poster
Posts: 45
Joined: Sat Jan 26, 2002 2:00 am
Contact:

110 - Meta-Loopless Sorts

Post by paulhryu » Fri Apr 19, 2002 3:45 am

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

Post by Ivan Golubev » Fri Apr 19, 2002 12:49 pm

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:

Post by paulhryu » Sun Apr 21, 2002 10:17 pm

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
New poster
Posts: 45
Joined: Sat Jan 26, 2002 2:00 am
Contact:

Problem 110 HAS to be wrong

Post by paulhryu » Sun Apr 21, 2002 10:26 pm

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:

Post by paulhryu » Sun Apr 21, 2002 10:34 pm

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
Location: Pasadena, CA

Post by C8H10N4O2 » Mon Apr 22, 2002 12:49 am

Multiple input is BLUE icon:)

Stefan Pochmann
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:

Post by Stefan Pochmann » Mon Apr 22, 2002 4:57 am

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
Location: Pasadena, CA

Post by C8H10N4O2 » Mon Apr 22, 2002 8:24 pm

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

Post Reply

Return to “Volume 1 (100-199)”