110 - Meta-Loopless Sorts
Moderator: Board moderators
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.
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.
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;
}
#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;
}
-
- Experienced poster
- Posts: 167
- Joined: Fri Oct 19, 2001 2:00 am
- Location: Saint Petersburg, Russia
-
- System administrator & Problemsetter
- 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.
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.
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?
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]
-
- Experienced poster
- Posts: 167
- Joined: Fri Oct 19, 2001 2:00 am
- Location: Saint Petersburg, Russia
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[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
[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?
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.
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.
-
- 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.
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.