[U]3.2.3 Spinning Wheelsシミュレーション
最も简単な方法で过ごした、裸のシミュレーションの问题.
時間の複雑さを見積もってみると、シミュレーションはできることに気づき、思い切ってシミュレーションしたが、シミュレーションがうまくいかず、遅すぎた.bitsetクラスをマスターして、空間を節約したほうがいいです.boolで8位を落とす360ビットのbit setで直接判断できるので、毎回スキャンする必要はありません...
コードは断固として醜い:
時間の複雑さを見積もってみると、シミュレーションはできることに気づき、思い切ってシミュレーションしたが、シミュレーションがうまくいかず、遅すぎた.bitsetクラスをマスターして、空間を節約したほうがいいです.boolで8位を落とす360ビットのbit setで直接判断できるので、毎回スキャンする必要はありません...
コードは断固として醜い:
/*
ID:bysen
LANG:C++
PROG:spin
*/
#include<stdio.h>
using namespace std;
struct node
{
int s,e,len;
}wheel[6][6];
int v[6];
int w[6];
int gcd( int a,int b )
{
if( b==0 )return a;
else return gcd( b,a%b );
}
int max( int a,int b ){ return a>b?a:b; }
int min( int a,int b ){ return a<b?a:b; }
bool flag[360];
bool whe[360];
void input()
{
for( int i=1;i<6;i++ )
{
scanf( "%d %d",&v[i],&w[i] );
v[i]%=360;
for( int j=1;j<=w[i];j++ )
{
scanf( "%d %d",&wheel[i][j].s,&wheel[i][j].len );
wheel[i][j].s%=360;
wheel[i][j].e=wheel[i][j].s+wheel[i][j].len;
}
}
}
int main()
{
freopen( "spin.in","r",stdin );
freopen( "spin.out","w",stdout );
input();
int T=0;
for( int i=1;i<=5;i++ )
T=max( T,360*v[i]/gcd(360,v[i]) );
int cnt=0;
while( cnt<T )
{
for( int i=0;i<360;i++ )
flag[i]=true;
node b;
for( int i=1;i<6;i++ )
{
for( int k=0;k<360;k++ )
whe[k]=false;
for( int j=1;j<=w[i];j++ )
{
b=wheel[i][j];
b.s=(wheel[i][j].s+v[i]*cnt)%360;
b.e=b.s+b.len;
for( int k=b.s;k<=b.e;k++ )
whe[k%360]=true;
}
for( int k=0;k<360;k++ )
if( whe[k]==false )
flag[k]=false;
}
for( int i=0;i<360;i++ )
if( flag[i]==true )
{
printf( "%d
",cnt );
return 0;
}
cnt++;
}
printf( "none
" );
return 0;
}