/* -*- coding: utf-8 -*- * * 249.cc: No.249 N言っちゃダメゲーム (2) - yukicoder */ #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; /* constant */ const int TN = 1000; /* typedef */ typedef long long ll; /* global variables */ bool fws[TN]; ll dp[TN + 1][2]; /* subroutines */ /* main */ int main() { for (int i = 0; i < TN; i++) { ll ni, ki; cin >> ni >> ki; fws[i] = ((ni - 1) % (ki + 1) != 0); } dp[TN][0] = dp[TN][1] = 0; for (int i = TN - 1; i >= 0; i--) { ll dmin, dmax; if (dp[i + 1][0] <= dp[i + 1][1]) dmin = dp[i + 1][0], dmax = dp[i + 1][1]; else dmin = dp[i + 1][1], dmax = dp[i + 1][0]; ll dw = dmin + 1, dl = dmax; if (fws[i]) { dp[i][0] = dw, dp[i][1] = dl; } else { dp[i][0] = dw, dp[i][1] = dl; } } printf("%lld\n", dp[0][0]); return 0; }