USACO chapter 1 section 1.4 clocks

USER: tianbing tianbing [tbbd4261]
TASK: clocks
LANG: C++
Compiling...
Compile: OK
Executing...
Test 1: TEST OK [0.054 secs, 2932 KB]
Test 2: TEST OK [0.043 secs, 2932 KB]
Test 3: TEST OK [0.043 secs, 2932 KB]
Test 4: TEST OK [0.054 secs, 2932 KB]
Test 5: TEST OK [0.043 secs, 2932 KB]
Test 6: TEST OK [0.043 secs, 2932 KB]
Test 7: TEST OK [0.032 secs, 2932 KB]
Test 8: TEST OK [0.032 secs, 2932 KB]
Test 9: TEST OK [0.054 secs, 2932 KB]
All tests OK.

Your program ('clocks') produced all correct answers! This is your submission #3 for this problem. Congratulations!

Here are the test data inputs:

------- test 1 -------
9 9 12
6 6 6
6 3 6
------- test 2 -------
12 9 12
9 9 9
12 9 12
------- test 3 -------
6 9 3
3 3 9
12 12 12
------- test 4 -------
9 3 9
9 9 9
9 9 9
------- test 5 -------
6 12 12
12 12 12
12 12 12
------- test 6 -------
3 12 9
6 6 6
12 12 12
------- test 7 -------
12 3 3
3 6 6
12 3 6
------- test 8 -------
12 3 9
9 12 12
3 6 9
------- test 9 -------
9 12 9
12 3 12
9 12 9
Keep up the good work!

Thanks for your submission!
题意:给你九个表的初始状态,每个表只可能是3,6,9,12,然后下面有9个操作,每个操作分把几个表的指针顺时针移动90度
  要求给你一个初始状态,让你给出一种方案(移动操作的组合)使移动后所有的表的指针都指向12
提交了三次,第一次compile error 没有包含string.h,下文用到了memset,低级错误;
第二次对于test无法通过。
题解:用数组a[1……9 ]分别纪录每个表移到12需要移动的次数,接受数据时a[i]=(12-a[i])/3;即可。
             9重循环暴力所有情况,用cnt[1……9]记录1……9个表的移动次数,如果可以使所有表都指向12的话就保存起来。
           要注意的是:每个操作不超过四次,因为四次又回到初始的状态没有意义,表移动的次数可以超过四次,比如test 3就让A表移动了6次,而a[1]==2,也就是第i个表 移动的次数cnt[i]/4==a[i]才可,这也就是我test 3 错的原因。
          最后如果有多个结果的话,是输出使所有表移动次数的和最小的那个

  1 /*
  2 ID:tbbd4261
  3 PROG:clocks
  4 LANG:C++
  5 */
  6 
  7 #include<iostream>
  8 #include<fstream>
  9 #include<cstring>
 10 #include<vector>
 11 using namespace std;
 12 int a[10];        //需要移动的次数 
 13 int cnt[10]={0};
 14 void f1(int i)
 15 {
 16 cnt[1]+=i; cnt[2]+=i; cnt[4]+=i; cnt[5]+=i;
 17 }
 18 
 19 void f2(int i)
 20 {
 21 cnt[1]+=i; cnt[2]+=i; cnt[3]+=i; 
 22 }
 23 
 24 void f3(int i)
 25 {
 26 cnt[2]+=i; cnt[3]+=i; cnt[5]+=i; cnt[6]+=i;
 27 }
 28 
 29 void f4(int i)
 30 {
 31 cnt[1]+=i; cnt[4]+=i; cnt[7]+=i;
 32 }
 33 
 34 void f5(int i)
 35 {
 36 cnt[2]+=i; cnt[4]+=i; cnt[5]+=i; cnt[6]+=i;cnt[8]+=i;
 37 }
 38 
 39 void f6(int i)
 40 {
 41 cnt[3]+=i; cnt[6]+=i; cnt[9]+=i;
 42 }
 43 
 44 void f7(int i)
 45 {
 46 cnt[4]+=i; cnt[5]+=i; cnt[7]+=i; cnt[8]+=i;
 47 }
 48 
 49 void f8(int i)
 50 {
 51      cnt[7]+=i; cnt[8]+=i; cnt[9]+=i;
 52 }
 53 
 54 void f9(int i)
 55 {
 56 cnt[5]+=i; cnt[6]+=i; cnt[8]+=i; cnt[9]+=i;
 57 }
 58 
 59 int check()
 60 {
 61 bool is_ans=1
 62  for(int i=1; i<=9; i++)
 63  {
 64    if(cnt[i]%4!=a[i])is_ans=0;//原写成cnt[i]!=a[i],这样就没有操作的组合符合条件
 65  }    
 66  if(is_ans)return 1;
 67  else return 0;
 68 }
 69 vector<vector< int > >vec; 
 70  
 71 void push(int i1,int i2,int i3,int i4,int i5,int i6,int i7,int i8,int i9,int &min)
 72 {
 73      vector<int>tem;
 74      for(int i=1;i<=i1&&i1!=0;i++)tem.push_back(1);
 75      for(int i=1;i<=i2&&i2!=0;i++)tem.push_back(2);
 76      for(int i=1;i<=i3&&i3!=0;i++)tem.push_back(3);
 77      for(int i=1;i<=i4&&i4!=0;i++)tem.push_back(4);
 78      for(int i=1;i<=i5&&i5!=0;i++)tem.push_back(5);
 79      for(int i=1;i<=i6&&i6!=0;i++)tem.push_back(6);
 80      for(int i=1;i<=i7&&i7!=0;i++)tem.push_back(7);
 81      for(int i=1;i<=i8&&i8!=0;i++)tem.push_back(8);
 82      for(int i=1;i<=i9&&i9!=0;i++)tem.push_back(9);
 83      vec.push_back(tem);
 84      //int sum=tem.size();
 85      //if(sum<min){ min=sum; vec.clear(); vec.push_back(tem); }
 86      //else if(sum==min)vec.push_back(tem);
 87 }
 88 
 89 int main()
 90 {
 91     ifstream cin("clocks.in");
 92     ofstream cout("clocks.out");  
 93     int min=10000
 94     for(int i=1; i<=9; i++)
 95       { cin>>a[i]; a[i]=(12-a[i])/3; }
 96     for(int i1=0; i1<4; i1++)
 97     for(int i2=0; i2<4; i2++)
 98     for(int i3=0; i3<4; i3++)
 99     for(int i4=0; i4<4; i4++)
100     for(int i5=0; i5<4; i5++)
101     for(int i6=0; i6<4; i6++)
102     for(int i7=0; i7<4; i7++)
103     for(int i8=0; i8<4; i8++)
104     for(int i9=0; i9<4; i9++)
105     {
106      f1(i1); f2(i2); f3(i3); f4(i4); f5(i5); f6(i6); f7(i7);  f8(i8); f9(i9);
107      int v=check();
108      if(v==1)
109        push(i1,i2,i3,i4,i5,i6,i7,i8,i9,min);
110      memset(cnt,0,sizeof cnt);
111     }
112     
113     int mov[10]={0,4,3,4,3,5,3,4,3,4};
114     vector<int> temp; int m=10000;
115       
116      for(int i=0; i<vec.size(); i++)
117       {
118         int sum=0;   
119         for(int j=0; j<vec[i].size();j++)
120           sum+=mov[vec[i][j]];
121         if(sum<m)
122         { m=sum; temp=vec[i]; }
123       }
124       cout<<temp[0];
125       for(int i=1; i<temp.size(); i++)
126       cout<<' '<<temp[i];
127       cout<<endl;
128   
129    //system("pause");
130     return 0;
131 }
132 

posted on 2010-06-03 10:09 田兵 阅读(1465) 评论(0)  编辑 收藏 引用 所属分类: USACO


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2010年6月>
303112345
6789101112
13141516171819
20212223242526
27282930123
45678910

导航

统计

常用链接

留言簿(2)

随笔分类(65)

随笔档案(65)

文章档案(2)

ACM

搜索

积分与排名

最新随笔

最新评论

阅读排行榜