USACO 3.2 Spinning Wheels

最多转360秒,各个轮子就复位了。所以在360秒内,每过一秒检测一下是否可以透过光即可。
用一个数组记录能透过0-359的轮子的个数,当在某一度轮子的个数达到了5,则说明光可以透过,输出即可。
否则说明是不可能有光透过。

#include <iostream>
#include 
<fstream>

using namespace std;

ifstream in(
"spin.in");
ofstream out(
"spin.out");

struct wedge{
    
int start;
    
int extent;
};

int speed[5];
wedge wedges[
5][5];
int wedge_num[5];

void onesecond()
{
   
for(int i=0;i<5;++i){
       
for(int j=0;j<wedge_num[i];++j){
           wedges[i][j].start
+=speed[i];
           wedges[i][j].start
%=360;
       }
   } 
}

bool isok()
{
    
int tmp[360];

    memset(tmp,
0,sizeof(tmp));

    
for(int i=0;i<5;++i){
        
for(int j=0;j<wedge_num[i];++j){
            
for(int k=0;k<=wedges[i][j].extent;++k)
                tmp[(wedges[i][j].start
+k)%360]++;
        }
    }

    
for(int i=0;i<360;++i)
        
if(tmp[i]==5)
            
return true;

    
return false;
}

void solve()
{
    
for(int i=0;i<5;++i){
        
in>>speed[i];
        
in>>wedge_num[i];
        
for(int j=0;j<wedge_num[i];++j){
            
in>>wedges[i][j].start>>wedges[i][j].extent;
        }
    }

    
if(isok()){
        
out<<0<<endl;
        
return;
    }

    
for(int i=1;i<=360;++i){
        onesecond();
        
if(isok()){
            
out<<i<<endl;
            
return;
        }
    }
    
out<<"none"<<endl;
}

int main(int argc,char *argv[])
{
    solve(); 
    
return 0;
}

posted on 2009-07-04 20:49 YZY 阅读(499) 评论(0)  编辑 收藏 引用 所属分类: AlgorithmUSACO


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


导航

<2009年6月>
31123456
78910111213
14151617181920
21222324252627
2829301234
567891011

统计

常用链接

留言簿(2)

随笔分类

随笔档案

搜索

积分与排名

最新评论

阅读排行榜