usaco 1_4_2 the clocks 题解_leokan的blog.mht

美国USACO题库源程序

    assign<SPAN style=3D"COLOR: #66cc66">(</SPAN>input,<SPAN =
style=3D"COLOR: #ff0000">'clocks.in'</SPAN><SPAN style=3D"COLOR: =
#66cc66">)</SPAN>;reset<SPAN style=3D"COLOR: #66cc66">(</SPAN>input<SPAN =
style=3D"COLOR: #66cc66">)</SPAN>;
    <SPAN>readln</SPAN><SPAN style=3D"COLOR: #66cc66">(</SPAN>temp<SPAN =
style=3D"COLOR: #66cc66">[</SPAN><SPAN style=3D"COLOR: =
#cc66cc">1</SPAN><SPAN style=3D"COLOR: #66cc66">]</SPAN>,temp<SPAN =
style=3D"COLOR: #66cc66">[</SPAN><SPAN style=3D"COLOR: =
#cc66cc">2</SPAN><SPAN style=3D"COLOR: #66cc66">]</SPAN>,temp<SPAN =
style=3D"COLOR: #66cc66">[</SPAN><SPAN style=3D"COLOR: =
#cc66cc">3</SPAN><SPAN style=3D"COLOR: #66cc66">]</SPAN><SPAN =
style=3D"COLOR: #66cc66">)</SPAN>;
    <SPAN>readln</SPAN><SPAN style=3D"COLOR: #66cc66">(</SPAN>temp<SPAN =
style=3D"COLOR: #66cc66">[</SPAN><SPAN style=3D"COLOR: =
#cc66cc">4</SPAN><SPAN style=3D"COLOR: #66cc66">]</SPAN>,temp<SPAN =
style=3D"COLOR: #66cc66">[</SPAN><SPAN style=3D"COLOR: =
#cc66cc">5</SPAN><SPAN style=3D"COLOR: #66cc66">]</SPAN>,temp<SPAN =
style=3D"COLOR: #66cc66">[</SPAN><SPAN style=3D"COLOR: =
#cc66cc">6</SPAN><SPAN style=3D"COLOR: #66cc66">]</SPAN><SPAN =
style=3D"COLOR: #66cc66">)</SPAN>;
    <SPAN>readln</SPAN><SPAN style=3D"COLOR: #66cc66">(</SPAN>temp<SPAN =
style=3D"COLOR: #66cc66">[</SPAN><SPAN style=3D"COLOR: =
#cc66cc">7</SPAN><SPAN style=3D"COLOR: #66cc66">]</SPAN>,temp<SPAN =
style=3D"COLOR: #66cc66">[</SPAN><SPAN style=3D"COLOR: =
#cc66cc">8</SPAN><SPAN style=3D"COLOR: #66cc66">]</SPAN>,temp<SPAN =
style=3D"COLOR: #66cc66">[</SPAN><SPAN style=3D"COLOR: =
#cc66cc">9</SPAN><SPAN style=3D"COLOR: #66cc66">]</SPAN><SPAN =
style=3D"COLOR: #66cc66">)</SPAN>;
    close<SPAN style=3D"COLOR: #66cc66">(</SPAN>input<SPAN =
style=3D"COLOR: #66cc66">)</SPAN>;
    <SPAN style=3D"COLOR: #b1b100">for</SPAN> i:=3D<SPAN style=3D"COLOR: =
#cc66cc">1</SPAN> <SPAN style=3D"COLOR: #b1b100">to</SPAN> <SPAN =
style=3D"COLOR: #cc66cc">9</SPAN> <SPAN style=3D"COLOR: =
#b1b100">do</SPAN>
        temp<SPAN style=3D"COLOR: #66cc66">[</SPAN>i<SPAN =
style=3D"COLOR: #66cc66">]</SPAN>:=3Dtemp<SPAN style=3D"COLOR: =
#66cc66">[</SPAN>i<SPAN style=3D"COLOR: #66cc66">]</SPAN> <SPAN =
style=3D"COLOR: #b1b100">div</SPAN> <SPAN style=3D"COLOR: =
#cc66cc">3</SPAN>;
<SPAN style=3D"COLOR: #b1b100">end</SPAN>;
<SPAN style=3D"FONT-WEIGHT: bold; COLOR: #000000">procedure</SPAN> work;
<SPAN style=3D"COLOR: #b1b100">var</SPAN>
    i,j,k:<SPAN style=3D"COLOR: #993333">integer</SPAN>;
    s:<SPAN style=3D"COLOR: #993333">ansistring</SPAN>;
    ans:<SPAN style=3D"COLOR: #993333">array</SPAN><SPAN style=3D"COLOR: =
#66cc66">[</SPAN><SPAN style=3D"COLOR: #cc66cc">1</SPAN>..<SPAN =
style=3D"COLOR: #cc66cc">9</SPAN><SPAN style=3D"COLOR: #66cc66">]</SPAN> =
<SPAN style=3D"COLOR: #b1b100">of</SPAN> <SPAN style=3D"COLOR: =
#993333">integer</SPAN>;
<SPAN style=3D"COLOR: #b1b100">begin</SPAN>
    assign<SPAN style=3D"COLOR: #66cc66">(</SPAN>output,<SPAN =
style=3D"COLOR: #ff0000">'clocks.out'</SPAN><SPAN style=3D"COLOR: =
#66cc66">)</SPAN>;rewrite<SPAN style=3D"COLOR: =
#66cc66">(</SPAN>output<SPAN style=3D"COLOR: #66cc66">)</SPAN>;
    fillchar<SPAN style=3D"COLOR: #66cc66">(</SPAN>ans,sizeof<SPAN =
style=3D"COLOR: #66cc66">(</SPAN>ans<SPAN style=3D"COLOR: =
#66cc66">)</SPAN>,<SPAN style=3D"COLOR: #cc66cc">0</SPAN><SPAN =
style=3D"COLOR: #66cc66">)</SPAN>;
    <SPAN style=3D"COLOR: #b1b100">for</SPAN> i:=3D<SPAN style=3D"COLOR: =
#cc66cc">1</SPAN> <SPAN style=3D"COLOR: #b1b100">to</SPAN> <SPAN =
style=3D"COLOR: #cc66cc">9</SPAN> <SPAN style=3D"COLOR: =
#b1b100">do</SPAN>
            <SPAN style=3D"COLOR: #b1b100">for</SPAN> k:=3D<SPAN =
style=3D"COLOR: #cc66cc">1</SPAN> <SPAN style=3D"COLOR: =
#b1b100">to</SPAN> <SPAN style=3D"COLOR: #cc66cc">9</SPAN> <SPAN =
style=3D"COLOR: #b1b100">do</SPAN>
                inc<SPAN style=3D"COLOR: #66cc66">(</SPAN>ans<SPAN =
style=3D"COLOR: #66cc66">[</SPAN>k<SPAN style=3D"COLOR: =
#66cc66">]</SPAN>,change<SPAN style=3D"COLOR: #66cc66">[</SPAN>i,k<SPAN =
style=3D"COLOR: #66cc66">]</SPAN>*<SPAN style=3D"COLOR: =
#66cc66">(</SPAN><SPAN style=3D"COLOR: #cc66cc">4</SPAN>-temp<SPAN =
style=3D"COLOR: #66cc66">[</SPAN>i<SPAN style=3D"COLOR: =
#66cc66">]</SPAN><SPAN style=3D"COLOR: #66cc66">)</SPAN><SPAN =
style=3D"COLOR: #66cc66">)</SPAN>;
    <SPAN style=3D"COLOR: #b1b100">for</SPAN> i:=3D<SPAN style=3D"COLOR: =
#cc66cc">1</SPAN> <SPAN style=3D"COLOR: #b1b100">to</SPAN> <SPAN =
style=3D"COLOR: #cc66cc">9</SPAN> <SPAN style=3D"COLOR: =
#b1b100">do</SPAN>
        ans<SPAN style=3D"COLOR: #66cc66">[</SPAN>i<SPAN style=3D"COLOR: =
#66cc66">]</SPAN>:=3Dans<SPAN style=3D"COLOR: #66cc66">[</SPAN>i<SPAN =
style=3D"COLOR: #66cc66">]</SPAN> <SPAN>and</SPAN> <SPAN style=3D"COLOR: =
#cc66cc">3</SPAN>;
    s:=3D<SPAN style=3D"COLOR: #ff0000">''</SPAN>;
    <SPAN style=3D"COLOR: #b1b100">for</SPAN> i:=3D<SPAN style=3D"COLOR: =
#cc66cc">1</SPAN> <SPAN style=3D"COLOR: #b1b100">to</SPAN> <SPAN =
style=3D"COLOR: #cc66cc">9</SPAN> <SPAN style=3D"COLOR: =
#b1b100">do</SPAN>
        <SPAN style=3D"COLOR: #b1b100">for</SPAN> j:=3D<SPAN =
style=3D"COLOR: #cc66cc">1</SPAN> <SPAN style=3D"COLOR: =
#b1b100">to</SPAN> ans<SPAN style=3D"COLOR: #66cc66">[</SPAN>i<SPAN =
style=3D"COLOR: #66cc66">]</SPAN> <SPAN style=3D"COLOR: =
#b1b100">do</SPAN>
            s:=3Ds+<SPAN>chr</SPAN><SPAN style=3D"COLOR: =
#66cc66">(</SPAN>i<SPAN style=3D"COLOR: #cc66cc">+48</SPAN><SPAN =
style=3D"COLOR: #66cc66">)</SPAN>+<SPAN style=3D"COLOR: #ff0000">' =
'</SPAN>;
    delete<SPAN style=3D"COLOR: #66cc66">(</SPAN>s,length<SPAN =
style=3D"COLOR: #66cc66">(</SPAN>s<SPAN style=3D"COLOR: =
#66cc66">)</SPAN>,<SPAN style=3D"COLOR: #cc66cc">1</SPAN><SPAN =
style=3D"COLOR: #66cc66">)</SPAN>;
    <SPAN>write</SPAN><SPAN style=3D"COLOR: #66cc66">(</SPAN>s<SPAN =
style=3D"COLOR: #66cc66">)</SPAN>;
    <SPAN>writeln</SPAN>;
    close<SPAN style=3D"COLOR: #66cc66">(</SPAN>output<SPAN =
style=3D"COLOR: #66cc66">)</SPAN>;
<SPAN style=3D"COLOR: #b1b100">end</SPAN>;
<SPAN style=3D"COLOR: #b1b100">begin</SPAN>
    init;
    work;
<SPAN style=3D"COLOR: #b1b100">end</SPAN>.</PRE>
<PRE class=3Dpascal> </PRE>
</SPAN></PRE>
<DIV class=3Dprintfooter> </DIV>
</STRONG></PRE><PRE><STRONG>`</STRONG></PRE><PRE><STRONG>`</STRONG></PRE>=
<PRE><STRONG>`</STRONG></PRE><PRE><STRONG>`usaco=B5=C4=B7=D6=CE=F6=A3=BA<=
/STRONG></PRE><PRE><STRONG><P>Notice that the order in which we apply =
moves is irrelevant, and that applying a move four times is the same as =
applying it not at all.</P><P>Thus there are only 4<SUP>9</SUP> =3D =
262144 move sequences that need to be tried, so we might as well just =
try them all.</P><P>We don't generate them shortest first, but looking =
at sequences of the same length, we generate the lesser ones before the =
greater ones, so we only need to keep track of the shortest working =
sequence we've found.</P><PRE>#include &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;
#include &lt;string.h&gt;
#include &lt;assert.h&gt;
#include &lt;ctype.h&gt;

#define INF 60000 /* bigger than longest possible path */

char *movestr[] =3D { "abde", "abc", "bcef", "adg", "bdefh", "cfi", =
"degh",
                    "ghi", "efhi" };

int movedist[9][9];
int clock[9];

int bestmove[9];
int nbestmove;

/* translate move strings into array "movedist" of which clocks change =
on each move */
void
mkmove(void)
{
    int i;
    char *p;

    for(i=3D0; i&lt;9; i++)
 for(p=3Dmovestr[i]; *p; p++)
     movedist[i][*p-'a'] =3D 3;
}

/* apply some number of each move from k to 9 */
/* move contains the number of times each move is applied */
void
solve(int *move, int k)
{
    int i, j, n, rep;

    if(k =3D=3D 9) {
 for(j=3D0; j&lt;9; j++)
     if(clock[j]%12 !=3D 0)
  return;

 /* we have a successful sequence of moves */
 n =3D 0;
 for(j=3D0; j&lt;9; j++)
     n +=3D move[j];

 if(nbestmove =3D=3D 0 || n &lt; nbestmove) {
     nbestmove =3D n;
     for(j=3D0; j&lt;9; j++)
  bestmove[j] =3D move[j];
 }
 return;
    }

    /*
     * the for loop counts down so we
     * generate smaller numbers first by
     * trying more of small numbered
     * moves before we try less of them.
     */
    for(rep=3D3; rep&gt;=3D0; rep--) {
 /* apply move k rep times */
 for(i=3D0; i&lt;rep; i++)
     for(j=3D0; j&lt;9; j++)
  clock[j] +=3D movedist[k][j];
 move[k] =3D rep;

 solve(move, k+1);

 /* undo move */
 for(i=3D0; i&lt;rep; i++)
     for(j=3D0; j&lt;9; j++)
  clock[j] -=3D movedist[k][j];
    }
}

void
main(void)
{
    FILE *fin, *fout;
    int i, j, move[9];
    char *sep;

    fin =3D fopen("clocks.in", "r");
    fout =3D fopen("clocks.out", "w");
    assert(fin !=3D NULL &amp;&amp; fout !=3D NULL);

    mkmove();

    for(i=3D0; i&lt;9; i++)
 fscanf(fin, "%d", &amp;clock[i]);

    solve(move, 0);

    sep =3D "";
    for(i=3D0; i&lt;9; i++) {
 for(j=3D0; j&lt;bestmove[i]; j++) {
     fprintf(fout, "%s%d", sep, i+1);
     sep =3D " ";
 }
    }
    fprintf(fout, "\n");

    exit(0);
}</PRE>
<H3>Lucian Boca submitted a constant time solution</H3>
<P>You can precalculate a matrix a as following:</P>
<P>a[i][0],a[i][1],....,a[i][8] is the number of moves =
'1','2','3',...'9' necessarly to move ONLY clock i (where 0 &lt; i =
&lt;=3D 8 - there are 9 clocks: 0=3DA, 1=3DB, ... 8=3DI) 90 degrees =
clockwise. So, you have the matrix:</P>
<PRE>int a[9][9]=3D { {3,3,3,3,3,2,3,2,0},
               {2,3,2,3,2,3,1,0,1},
               {3,3,3,2,3,3,0,2,3},
               {2,3,1,3,2,0,2,3,1},
               {2,3,2,3,1,3,2,3,2},
               {1,3,2,0,2,3,1,3,2},
               {3,2,0,3,3,2,3,3,3},
               {1,0,1,3,2,3,2,3,2},
               {0,2,3,2,3,3,3,3,3} };</PRE>
<P>That means: to move ONLY the clock 0 (clock A) 90 degrees clockwise =
you have to do {3,3,3,3,3,2,3,2,0}, 3 moves of type 1, three moves of =
type 2, ..., 2 moves of type 8, 0 moves of type 9, etc.</P>
<P>To move ONLY the clock 8 (clock I), you have to do the moves =
{0,2,3,2,3,3,3,3,3}: 0 moves of type 1, 2 moves of type 2... 3 moves of =
type 9....</P>
<P>That's it! You count in a vector v[9] how many moves of each type you =
have to do, and the results will be modulo 4 (%4 - 5 moves of any type =
have the same effect 1 move has). The source code:</P>
<PRE>#include &lt;stdio.h&gt;

int a[9][9]=3D { {3,3,3,3,3,2,3,2,0},
               {2,3,2,3,2,3,1,0,1},
               {3,3,3,2,3,3,0,2,3},
               {2,3,1,3,2,0,2,3,1},
               {2,3,2,3,1,3,2,3,2},
               {1,3,2,0,2,3,1,3,2},
               {3,2,0,3,3,2,3,3,3},
               {1,0,1,3,2,3,2,3,2},
               {0,2,3,2,3,3,3,3,3} };
int v[9];

int main() {
    int i,j,k;
    freopen("clocks.in","r",stdin);
    for (i=3D0; i&lt;9; i++) {
        scanf("%d",&amp;k);
        for(j=3D0; j&lt;9; j++)
             v[j]=3D(v[j]+(4-k/3)*a[i][j])%4;
    }
    fclose(stdin);

    k=3D0;
    freopen("clocks.out","w",stdout);
    for (i=3D0; i&lt;9; i++)
        for (j=3D0; j&lt;v[i]; j++)
            if (!k) { printf("%d",i+1); k=3D1; }
            else    printf(" %d",i+1);
    printf("\n");
    fclose(stdout);
    return 0;
}</PRE>
<P>Here's a different approach from Sopot Cela -- no loops, constant =
time. It is, however, extraordinarily intricate: getting such a program =
correct in a contest environment could be extremely challenging:</P>
<PRE>program clocks;
const
  INV : array[3..12] of byte =3D(1, 0, 0, 2, 0, 0, 3, 0, 0, 0);

var inp, out: text;
    a, b, c, d, e, f, g, h, i: integer;
    ax, bx, cx, dx, ex, fx, gx, hx, ix,l: integer;
    t,an: array[1..9] of integer;
begin
    assign (inp, 'clocks.in'); reset (inp);
    readln(inp, ax, bx, cx);
    readln(inp, dx, ex, fx);
    readln(inp, gx, hx, ix);
    a:=3Dinv[ax]; b:=3Dinv[bx]; c:=3Dinv[cx]; d:=3Dinv[dx];
    e:=3Dinv[ex]; f:=3Dinv[fx]; g:=3Dinv[gx]; h:=3Dinv[hx];
    i:=3Dinv[ix];
    t[1] :=3D (8+a+2*b+c+2*d+2*e-f+g-h) mod 4;
    t[2] :=3D (a+b+c+d+e+f+2*g+    2*i) mod 4;
    t[3] :=3D (8+  a+2*b+  c  -d+2*e+2*f      -h+  i) mod 4;
    t[4] :=3D (    a+  b+2*c+  d+  e+      g+  h+2*i) mod 4;
    t[5] :=3D (4+  a+2*b+  c+2*d  -e+2*f+  g+2*h+  i) mod 4;
    t[6] :=3D (  2*a+  b+  c+      e+  f+2*g+  h+  i) mod 4;
    t[7] :=3D (8+  a  -b+    2*d+2*e  -f+  g+2*h+  i) mod 4;
    t[8] :=3D (  2*a+    2*c+  d+  e+  f+  g+  h+  i) mod 4;
    t[9] :=3D (8      -b+  c  -d+2*e+2*f+  g+2*h+  i) mod 4;
    assign(out, 'clocks.out'); rewrite(out);
    for a :=3D 1 to 9 do
 for b :=3D 1 to t[a] do Begin
     inc(l);
     an[l]:=3Da;
 end;
    for a:=3D1 to l-1 do
 write(out,an[a],' ');
    write(out,an[l]);
    writeln(out); close(out)
end.</PRE>
<PRE><PRE class=3Dpascal> </PRE>
</PRE>
</STRONG></PRE></DIV></TD></TR></TBODY></TABLE><BR>
<DIV class=3Dopt><A =
title=3D=B2=E9=BF=B4=B8=C3=B7=D6=C0=E0=D6=D0=CB=F9=D3=D0=CE=C4=D5=C2=20
href=3D"http://hi.baidu.com/leokan/blog/category/Oi">=C0=E0=B1=F0=A3=BAOi=
</A> | <A=20
title=3D=BD=AB=B4=CB=CE=C4=D5=C2=CC=ED=BC=D3=B5=BD=B0=D9=B6=C8=CB=D1=B2=D8=
 onclick=3D"return addToFavor();"=20
href=3D"http://cang.baidu.com/do/add" =
target=3D_blank>=CC=ED=BC=D3=B5=BD=CB=D1=B2=D8</A> | =E4=AF=C0=C0(<SPAN=20
id=3Dresult></SPAN>) | <A=20
href=3D"http://hi.baidu.com/leokan/blog/item/8e2ca9c2fa3aed1f0ef47784.htm=
l#send">=C6=C0=C2=DB</A>&nbsp;(0)
<SCRIPT language=3Djavascript>
/*<![CDATA[*/
var pre =3D [true,'zju1005 Jugs =
=B7=AD=D2=EB=A3=A8=D4=AD=B4=B4=B7=AD=D2=EB=A3=AC=C4=D1=B5=C3=A3=A9 =
zju1005 Jugs =CC=E2=BD=E2', 'zju1005 Jugs =
=B7=AD=D2=EB=A3=A8=D4=AD=B4=B4=B7=AD=D2=EB=A3=AC...','/leokan/blog/item/8=
c8de8dda64daceb77c6387c.html'];
var post =3D [true,'zju2416 Open the Lock =
=B7=AD=D2=EB=A3=A8=D4=AD=B4=B4=B7=AD=D2=EB=A3=AC=C4=D1=B5=C3=A3=A9 =
zju2416 Open the Lock =CC=E2=BD=E2','zju2416 Open the Lock =
=B7=AD=D2=EB=A3=A8=D4=AD...', =
'/leokan/blog/item/5bdedd16825dec1c962b4351.html'];
if(pre[0] || post[0]){
	document.write('<div =
style=3D"height:5px;line-height:5px;">&nbsp;</div><div id=3D"in_nav">');
	if(pre[0]){
		document.write('=C9=CF=D2=BB=C6=AA=A3=BA<a href=3D"' + pre[3] + '" =
title=3D"' + pre[1] + '">' +  pre[2] + '</a>&nbsp;&nbsp;&nbsp;&nbsp;');
	}
	if(post[0]){
		document.write('=CF=C2=D2=BB=C6=AA=A3=BA<a href=3D"' + post[3] + '" =
title=3D"' + post[1] + '">' +  post[2] + '</a>');
	}
	document.write('</div>');
}
/*]]>*/
</SCRIPT>
 </DIV>
<DIV class=3Dline></DIV>
<STYLE type=3Dtext/css>#in_related_doc A {
	TEXT-DECORATION: none
}
</STYLE>

<DIV id=3Din_related_tmp></DIV>
<SCRIPT language=3Djavascript type=3Dtext/javascript>
/*<![CDATA[*/
function HI_MOD_IN_RELATED_DOC_CALLBACK(arg){
    if(arg.length <=3D 1) return false;
    var hasMore =3D arg[0];
    var D=3Dfunction(A,B){A[A.length]=3DB;}