OJ Board

Posted: **Fri Jul 11, 2003 12:42 am**

You're my hero

After your last remark it was enough to skip the first number to have my solution accepted. Actually, I still have PE, but I don't care.
Thank you very much

Posted: **Mon Dec 01, 2003 4:43 pm**

this is the answer i got for 5, it's fine to me but it got WA.

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.

Posted: **Sun Apr 18, 2004 4:25 pm**

Hi, I have tried to submit problem 110 but got WA
I have tested my program, compiled pascal outputs, tried whether they work on all permutations (and they do), I have exactly n! writeln statements in my outputted program and exactly n!-i if statements. Could anyone help me find what's wrong ?
My code tries to optimize the "decision tree" a bit and so it is compicated (and slow) but I think it should work ..

Code: Select all

/* @JUDGE_ID: <MY_ID> 110 C */

#include <stdio.h>
#include <stdlib.h>

#define MAXV          8
#define MAXPERM   65536
#define UNDEF        -1
#define DEBUG         0

#define MIN(a,b)  (((a) < (b)) ? (a) : (b))
#define MAX(a,b)  (((a) > (b)) ? (a) : (b))

struct comp {
  int va, vb;  /* compare values */
  int poffs;   /* offset of perms in array */
  int tc, fc;  /* comparsion entries for sons */
  int tp, fp;  /* counts of "true" and "false" perms */
} comps[MAXPERM];

struct perm {
  int p[MAXV];
} perms[MAXPERM];

int V, nperms, ncomps, gap, tab, ep;

void
genperm(int depth, int *actperm, int *used)
{
  int i;

  if (depth == V) {
    for (i = 0; i < V; i++)
      perms[nperms].p[i] = actperm[i];
    nperms++;
    return ;
  }
  for (i = 0; i < V; i++)
    if (!used[i]) {
      used[i] = 1;
      actperm[depth] = i;
      genperm (depth+1, actperm, used);
      used[i] = 0;
    }
  return ;
}

void
findcomp (int offs, int permno, int *ca, int *cb)
{
  int va, vb, van, vbn, optv = 0, opta = 0, optb = 0, m;
  int i, j;

  for (va = 0; va < V; va++)
    for (vb = 0; vb < V; vb++)
      if (va != vb) {
	van = 0;
	vbn = 0;
	for (i = 0; i < permno; i++)
	  {
	    if (MAX(van, vbn) >= permno - optv)
	      goto noupdate;
	    for (j = 0; j < V; j++)
	      if (perms[offs+i].p[j] == va) {
		van++;
		break;
	      } else if (perms[offs+i].p[j] == vb) {
		vbn++;
		break;
	      }
	  }
	m = MIN(van, vbn);
	if (m > optv) {
	  optv = m;
	  opta = va;
	  optb = vb;
	}
      noupdate:
      }
  *ca = opta;
  *cb = optb;
  return ;
}

int
order (struct perm *p, int a, int b)
{
  int i;

  for (i = 0; i < V; i++)
    if (p->p[i] == a)
      return 1;
    else if (p->p[i] == b)
      return 0;
  return 0;
}

int
maketree (int offs, int permno)
{
  int ca, cb, i, j, n, p;
  struct perm actp;

  findcomp (offs, permno, &ca, &cb);
  i = 0; j = permno - 1;
  n = 0;
  while (i < j)
    {
      while (i < j && (order (&(perms[offs+i]), ca, cb)))
	i++;
      while (j > i && (! order (&(perms[offs+j]), ca, cb)))
	j--;
      if (i == j)
	break;
      actp = perms[offs+i];
      perms[offs+i] = perms[offs+j];
      perms[offs+j] = actp;
    }
  if (!order (&(perms[offs+i]), ca, cb))
    n = i;
  else
    n = i+1;
      
#if DEBUG
  if (order (&(perms[offs+n]), ca, cb) || !order (&(perms[offs+n-1]), ca, cb))
    fprintf (stderr, "N (%d) counted inproperly\n", n);
  if (n == 0 || n == permno)
    fprintf (stderr, "Redundant comparsion \n");
#endif
  comps[ncomps].va = ca;
  comps[ncomps].vb = cb;
  comps[ncomps].poffs = offs;
  comps[ncomps].tp = n;
  comps[ncomps].fp = permno - n;
  comps[ncomps].tc = -1;
  comps[ncomps].fc = -1;
  p = ncomps;
  ncomps++;
  if (n > 1)
    comps[p].tc = maketree (offs, n);
  if (permno - n > 1)
    comps[p].fc = maketree (offs + n, permno - n);

  return p;
}

void
gencomptree (void)
{
  int ap[MAXV], use[MAXV];
  int i;

  nperms = 0;
  ncomps = 0;
  for (i = 0; i < V; i++)
    use[i] = 0;
  genperm (0, ap, use);
  maketree (0, nperms);
}

void
printhead (void)
{
  int i;

  printf ("program sort(input,output);\n");
  printf ("var\n");
  for (i = 0; i < V; i++)
    printf("%c%c", 'a'+i, (i == V-1) ? ' ' : ',');
  printf (": integer;\n");
  printf ("begin\n");
  for (i = 0; i < gap; i++)
    printf (" ");
  printf ("readln(");
  for (i = 0; i < V; i++)
    printf ("%c%c", 'a'+i, (i==V-1) ? ')' : ',');
  printf(";\n");
}

void
parsetree (int cnode)
{
  int i;

  if (!ep)
    for (i = 0; i < gap; i++)
      printf (" ");
  ep = 0;
  printf ("if %c < %c then\n", comps[cnode].va+'a', comps[cnode].vb+'a');
  gap += tab;
  if (comps[cnode].tp == 1) {
    for (i = 0; i < gap; i++)
      printf (" ");
    printf ("writeln(");
    for (i = 0; i < V; i++)
      printf ("%c%c", perms[comps[cnode].poffs].p[i]+'a', (i == V-1) ? ')' : ',');
    printf ("\n");
  } else {
    parsetree (comps[cnode].tc);
  }
  gap -= tab;
  for (i = 0; i < gap; i++)
    printf (" ");
  printf ("else");

  if (comps[cnode].fp == 1) {
    gap += tab;
    printf ("\n");
    for (i = 0; i < gap; i++)
      printf (" ");
    printf ("writeln(");
    for (i = 0; i < V; i++)
      printf ("%c%c", perms[comps[cnode].poffs + comps[cnode].tp].p[i]+'a',
	      (i == V-1) ? ')' : ',');
    printf ("\n");
    gap -= tab;
  } else {
    printf (" ");
    ep = 1;
    parsetree (comps[cnode].fc);
  }

}

void
printtail (void)
{
  printf ("end.\n");
}

int
main (void)
{
  int i, j, k;

  scanf ("%d", &k);
  for (i = 0; i < k; i++)
    {
      if (i > 0)
	printf ("\n");
      scanf ("%d", &V);
      gap = 2;
      tab = 2;
      printhead ();
      if (V == 1) {
	for (j = 0; j < gap; j++)
	  printf (" ");
	printf ("writeln(a);\n");
      } else {
	gencomptree ();
	parsetree (0);
      }
      printtail ();
    }
  return EXIT_SUCCESS;
}

[/c]

Posted: **Sun Apr 18, 2004 8:06 pm**

For the input

Code: Select all

Your program produces:

Code: Select all

program sort(input,output);
var
a : integer;
begin
  readln(a);
  writeln(a);     { there should be no semicolon here }
end.

program sort(input,output);
var
a,b,c : integer;
begin
  readln(a,b,c);
  if a < b then
    if a < c then
      if b < c then
        writeln(a,b,c)
      else
        writeln(a,c,b)
    else
      writeln(c,a,b)
  else if a < c then   { not correct, see problem description }
    writeln(b,a,c)
  else if b < c then
    writeln(b,c,a)
  else
    writeln(c,b,a)
end.

Posted: **Sun Apr 18, 2004 8:41 pm**

I have also tried submitting without semicolon after writeln in n=1 case. But what is wrong with the a < c compartion? I have read problem again and again and I don't see it.

It is not redundant (I only did a < b comparsion which failed ....) so what did you mean ?

Posted: **Mon Apr 19, 2004 8:56 am**

You should spread the else and if over two lines and use extra indentation:

Code: Select all

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

Look at the sample output.
Same for n>3.

Posted: **Mon Apr 19, 2004 10:21 am**

So how do I recognize whether to write "else if" on one line or else and if on separate lines ?

Posted: **Mon Apr 19, 2004 11:34 am**

I'm terribly sorry. It's been too long ago that I solved this problem and simply compared your output with mine and noticed the difference. But on further inspection of the problem description, I can't find anything that prescribes the way the output should be formatted.
Your formatting is as good as mine...
I don't see why your code gets WA, but I will look into it when I have more time.

Posted: **Mon Apr 19, 2004 5:23 pm**

Here is the correct output for n = 4 (no indentation, so it gets PE):

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.

Hope this helps.

Posted: **Thu Oct 21, 2004 5:09 am**

I have no idea why it's still WA!
Thanks for your help!!
[c]
#include<stdio.h>
#include<string.h>
#include<stdlib.h>

char var[10]={'a','b','c','d','e','f','g','h','i','j'};
char Sorted[10];
int iArrayNum;
void fnSort(int now);
void fnPrintOut();
void fnIns(int i,char now_char);
void fnRestore(int i);
int n;
int main()
{
int j,M;
scanf("%d",&M);
for(j=0;j<M;++j)
{
scanf("%d",&n);
if(j!=0)
printf("\n");
fnPrintOut();
}
return 0;
}
void fnPrintOut()
{
int i;
printf("program sort(input,output);\n");
printf("var\n");

printf("%c",var[0]);
for(i=1;i<n;++i)
printf(",%c",var);
printf(" : integer;\n");

printf("begin\n");

printf(" readln(");
printf("%c",var[0]);
for(i=1;i<n;++i)
printf(",%c",var);
printf(");\n");

iArrayNum=1;
Sorted[0]='a';
if(n==1)
printf(" writenln(a)\n");
else
fnSort(1);
printf("end.\n");
}
void fnSort(int now)
{
char szSpace[100],now_char=var[now];
int i,j;

szSpace[0]='\0';
for(i=0;i<now;++i)
strcat(szSpace," ");

for(i=now-1;i>=0;--i)
{
if(i==now-1)
printf("%sif %c < %c then\n",szSpace,Sorted,now_char);
else
printf("%selse if %c < %c then\n",szSpace,Sorted,now_char);
fnIns(i,now_char);
if(now==n-1)
{
printf("%s writeln(%c",szSpace,Sorted[0]);
for(j=1;j<iArrayNum;++j)
printf(",%c",Sorted[j]);
printf(")\n");
}
else
fnSort(now+1);
fnRestore(i);

}
printf("%selse\n",szSpace);
fnIns(-1,now_char);
if(now==n-1)
{
printf("%s writeln(%c",szSpace,Sorted[0]);
for(j=1;j<iArrayNum;++j)
printf(",%c",Sorted[j]);
printf(")\n");
}
else
fnSort(now+1);
fnRestore(-1);
}
void fnRestore(int i)
{
int j;

++i;
for(j=i;j<iArrayNum;++j)
Sorted[j]=Sorted[j+1];
--iArrayNum;
}
void fnIns(int i,char now_char)
{
int j;

++i;
for(j=iArrayNum-1;j>=i;--j)
Sorted[j+1]=Sorted[j];
Sorted=now_char;
++iArrayNum;
}
[/c]

Posted: **Mon Nov 01, 2004 5:54 pm**

You were this close to solving this problem... Look at your excetion check (if(n==1e)). Remove the "writenln" and replace it with the writeln, that should do the trick (I hope so).

Posted: **Tue Nov 02, 2004 3:33 am**

Thank you very much!!
I made a stupid mistake!!

Posted: **Thu Jan 13, 2005 10:11 am**

I know nothing about Pascal's format, so I have a question:
The sample output is:

Code: Select all

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

Then can I write in this way?:

Code: Select all

begin
readln(a,b,c);
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 deleting the spaces at the beginning of each line. Can that be all right? please tell me. Thank you.

Posted: **Thu Jan 13, 2005 3:46 pm**

I'm sorry. I have realized it is a so stupid question. Now I have got AC in this problem.

Posted: **Sun Aug 07, 2005 7:06 am**

Whew. After changing everything in sight, I think the judge didn't like the empty line at the end of my output. I only changed two things since getting PE:
1)remove trailing empty line. Now empty lines only appear between programs
2) else if always appears on the same line instead of as else\nif

My program is correctly formatted and indented, but I'm not sure if this is necessary.

OJ Board

110 - Meta-Loopless Sorts

110: What the h.. is wrong about this answer?

110 (meta loopless sorts): WA

110 Meta Loopless Sorts WA! what wrong with my code?

I have a question about problem 110.

...

Accepted