Categories

USACO 1.4.2 The Clocks

穷举。
由于每次移动都是90度,因而移动4次钟又回到了原处,因而每种移动方法至多3次,至少0次
用move[0..9]表示第j种方法对九个钟产生的影响,
用i[1..9]表示第j种方法的次数,对每种方法的次数从0到3穷举,9重循环

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
/*
ID: tgh7281
LANG: C++
TASK: clocks
*/
#include <iostream>
#include <fstream>
using namespace std;
 
int move[9][9]=
{
    {3,3,0,3,3},
    {3,3,3},
    {0,3,3,0,3,3},
    {3,0,0,3,0,0,3},
    {0,3,0,3,3,3,0,3},
    {0,0,3,0,0,3,0,0,3},
    {0,0,0,3,3,0,3,3},
    {0,0,0,0,0,0,3,3,3},
    {0,0,0,0,3,3,0,3,3}
};
bool check(int*a,int*clock);
 
int main()
{
    ifstream fin("clocks.in");
    ofstream fout("clocks.out");
    int clock[10],m[10]={0};
    int i[10],j;
 
    for (j=1;j<=9;j++) fin>>clock[j];
 
    for (i[1]=0;i[1]<=3;i[1]++)
    {
        for (i[2]=0;i[2]<=3;i[2]++)
        {
            for (i[3]=0;i[3]<=3;i[3]++)
            {
                for (i[4]=0;i[4]<=3;i[4]++)
                {
                    for (i[5]=0;i[5]<=3;i[5]++)
                    {
                        for (i[6]=0;i[6]<=3;i[6]++)
                        {
                            for (i[7]=0;i[7]<=3;i[7]++)
                            {
                                for (i[8]=0;i[8]<=3;i[8]++)
                                {
                                    for (i[9]=0;i[9]<=3;i[9]++)
                                    {
                                        if (check(i,clock))
                                        {
                                            for (j=1;j<=9;j++) m[j]=i[j];
                                            break;
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
 
    bool flag=true;
    for (j=1;j<=9;j++)
    {
        if (m[j])
        {
            for (int i=0;i<m[j];i++)
            {
                if (!flag) fout<<’ ‘;
                fout<<j;
                if (flag) flag=false;
            }
        }
    }
    fout<<endl;
 
    fin.close();
    fout.close();
 
    return 0;
}
 
bool check(int*a,int*clock) //检验对于每一个钟是否都已达到了12点
{
    int i1,i3,tmp;
    bool flag=true;
 
    for (i1=1;i1<=9;i1++) //对于1到9每一个clock
    {
        tmp=0;
        for (i3=0;i3<9;i3++)
        {
            tmp += a[i3+1]*move[i3][i1-1];
        }
 
        if ((tmp+clock[i1])%12)
        {
            flag=false;
            break;
        }
    }
 
    return flag;
}

1 comment to USACO 1.4.2 The Clocks

Leave a Reply

You can use these HTML tags

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

  

  

  

*