UVa-10273, ZOJ-1236 : Eat or not to Eat?
問題概要
牛がN(<1000)匹いる。各牛は毎日ある量の牛乳を出す。量はある周期T(<=10)にしたがって変化する。毎日、最も牛乳を出した量が最も少ない牛がユニークにいたらその牛は取り除かれる。繰り返した時に残る牛の数を求める問題。
解法
愚直にシミュレーションする。LCM(1..10)=2520日経っても取り除かれなかったらもう終了してよい。どの辺にグラフの要素があるのかは謎。
acceptされたコード
計算量不明。
#include <cstdio> #include <algorithm> using namespace std; const int TERM = 2520; const int MAX_N = 1000; const int MAX_T = 10; const int INF = 1<<29; int live[TERM]; int ts[MAX_N]; int product[MAX_N]; bool is_live[MAX_N]; int Ms[MAX_N][MAX_T]; int N; int read_int(){ int x; scanf("%d", &x); return x; } void init(){ N = read_int(); fill(live, live+TERM, -1); fill(is_live, is_live+N, true); for(int i=0; i<N; i++){ ts[i] = read_int(); for(int j=0; j<ts[i]; j++){ Ms[i][j] = read_int(); } } } void solve(){ int cur = N, last_day = 0; for(int loop=0; ; loop++){ for(int day=0; day<TERM; day++){ if(live[day] == cur){ printf("%d %d\n", cur, last_day); return ; } else{ live[day] = cur; } fill(product, product+N, INF); for(int i=0; i<N; i++)if(is_live[i]){ product[i] = Ms[i][day%ts[i]]; } int *p, *q; int tmp; p = min_element(product, product+N); if(*p == INF){ printf("%d %d\n", cur, last_day); return ; } tmp = *p; *p = INF; q = min_element(product, product+N); if(*q != tmp){ is_live[p-product] = false; cur--; last_day = loop * TERM + day + 1; } } } } int main(){ for(int T = read_int(); T--; ){ init(); solve(); } return 0; }