#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define SAFE_DELETE(p) { delete (p); (p) = nullptr; } #define SAFE_DELETE_ARRAY(p) { delete[] (p); (p) = nullptr; } using namespace std; namespace ValLib { const int MOD = 1000000007; typedef unsigned long long ull; template class unordered_vmap; template using sptr = typename std::shared_ptr; class vnode; class vegde; class vgraph; class SearchResult; template void fill(vector>& vec, const T& value) { for (vector& t : vec) { fill(t, value); } } template void fill(vector& vec, const T& value) { fill(vec.begin(), vec.end(), value); } template void resize(vector>& vec, int size1, int size2) { vec.resize(size1); for (vector& t : vec) { t.resize(size2); } } template class umap : public std::unordered_map { public: bool containsKey(const Key& key) const; bool containsValue(const Value& val) const; }; template bool umap::containsKey(const Key& key) const { return (this->find(key) != this->end()); } template bool umap::containsValue(const Value& val) const { for(auto itr = this->begin(); itr != this->end(); ++itr) { if (itr->second == val) { return true; } } return false; } class Point { public: inline Point() : x(-1), y(-1) {} inline Point(int _x, int _y) : x(_x), y(_y) {} int x; int y; }; /// /// 素集合データ構造 /// class UnionFind { public: /// /// コンストラクタ /// /// 要素数 UnionFind(int N) { parent.resize(N); for (int i = 0; i < N; ++i) { parent[i] = i; } } /// /// 要素xの根を探索 /// /// 探索する要素番号(0~N-1) /// 要素xの根(0~N-1) int find(int x) { if (parent[x] == x) { return x; } else { parent[x] = find(parent[x]); // 経路圧縮(間接的な要素をrootに直接つなぐ) return parent[x]; } } /// /// 2つの要素の根が同じか /// /// 探索する要素番号1(0~N-1) /// 探索する要素番号2(0~N-1) /// true: 同じ根, false: 異なる根 bool same(int x1, int x2) { return find(x1) == find(x2); } /// /// 2つの要素の根同士を繋ぐ /// /// 要素番号1(0~N-1) /// 要素番号1(0~N-1) void union_elements(int x1, int x2) { int rootX1 = find(x1); int rootX2 = find(x2); parent[rootX2] = rootX1; } private: vector parent; }; class vmath { public: // 約数を全て求める O(√n) static ull calcDivisors(list* divisors, ull n) { divisors->clear(); if (n <= 0ull) { return 0ull; } divisors->push_back(1ull); if (n != 1ull) { divisors->push_back(n); } for (ull i = 2ull; i * i <= n; ++i) { if (n % i == 0ull) { divisors->push_back(i); divisors->push_back(n / i); } } return divisors->size(); } // 約数の個数を返す O(√n) static ull calcDivisorNum(ull n) { if (n <= 0ull) { return 0ull; } ull count = 1ull; // for 1 if (n != 1ull) { ++count; // for n } // for 2~n-1 for (ull i = 2ull; i * i <= n; ++i) { if (n % i == 0ull) { count += 2ull; } } return count; } // 素因数分解 O(√n) static int decompositPrime(list* primes, ull n) { primes->clear(); if (n == 0) { return 0ull; } if (n == 1) { primes->push_back(1); return 1ull; } // 割る数の初期値 ull a = 2ull; // √n ≧ a ( n ≧ a * a ) の間ループ処理 while (n >= a * a) { if (n % a == 0ull) { // a で割り切れたら、a は素因数 primes->push_back(a); // そして、割られる数を a で割る n /= a; } else { // a で割り切れなかったら、 a を 1 増加させる a++; } } primes->push_back(n); return primes->size(); } // 素因数の数を返す O(√n) static ull calcPrimeNum(ull n) { if (n <= 1) { return n; } ull count = 0ull; // 割る数の初期値 ull a = 2ull; // √n ≧ a ( n ≧ a * a ) の間ループ処理 while (n >= a * a) { if (n % a == 0ull) { // a で割り切れたら、a は素因数 ++count; // そして、割られる数を a で割る n /= a; } else { // a で割り切れなかったら、 a を 1 増加させる a++; } } ++count; // for n return count; } // 階乗 static ull fact(ull x) { if (x == 0ull) { return 1ull; } else { return x * fact(x - 1ull); } } // 順列 nPr static ull permutation(int n, int r) { assert(n >= r); //return fact(n) / fact(n - r); ull result = 1; for (ull i = n; i > n - r; --i) { result *= i; } return result; } // 組み合わせ nCr // 先にmakePascalTriangleでパスカルの三角形を作成しておく必要がある static ull combination(int n, int r) { assert(n >= r); assert(n <= mPascalTriangleDepth); return mPascalTriangle[n][r]; } // 重複組合せ nHr = n+r-1Cr // 使いどころ:n人にr個を配るとき、同じ人に何個配っても良い場合とか // 4人に5個の◯を配るときa=2,b=0,c=2,d=1のとき、◯◯||◯◯|◯みたいになる。 // これは◯と|を混ぜた組み合わせで、◯の数がn,棒の数はr-1だから全体でn+r-1 // (n-r)で割ったものが順列n+r-1Prで、それを更にrで割っているからnHr = n+r-1Cr static ull repeatedCombination(int n, int r) { return combination(n + r - 1, r); } // パスカルの三角形。組み合わせの計算に使用するのでこれを先に作成しておく必要がある。 static void makePascalTriangle(int depth) { resize(mPascalTriangle, depth + 1, depth + 1); for (int i = 0; i <= depth; ++i) { mPascalTriangle[i][0] = 1; for (int j = 1; j <= i; ++j) { mPascalTriangle[i][j] = mPascalTriangle[i - 1][j] + mPascalTriangle[i - 1][j - 1]; } } mPascalTriangleDepth = depth; } // xのN桁目の数値を得る static ull getNDigitNumber(ull x, ull n) { return (x / pow(10ull, n - 1ull)) % 10; } // xのN桁目の数値を得る static int getNDigitNumber(int x, int n) { assert(n <= 10); return (x / pow(10, n - 1)) % 10; } // xのN乗を求める(バイナリ法) O(logN) static ull pow(ull x, ull n) { assert(x >= 0ull); assert(n >= 0ull); if (x == 0ull) { if (n == 0ull) { return 1ull; } else { return 0ull; } } ull result = 1ull; ull z = x; while (n > 0ull) { if (n & 1ull) { result *= z; } z *= z; n >>= 1; } return result; } // xのN乗を求める(バイナリ法) O(logN) static int pow(int x, int n) { assert(x >= 0); assert(n >= 0); if (x == 0) { if (n == 0) { return 1; } else { return 0; } } int result = 1; int z = x; while (n > 0) { if (n & 1) { result *= z; } z *= z; n >>= 1; } return result; } private: static int mPascalTriangleDepth; static vector> mPascalTriangle; }; int vmath::mPascalTriangleDepth = 0; vector> vmath::mPascalTriangle; class vmath_mod { public: // 階乗 static ull fact(ull x) { ull result = 1ull; for (ull i = 1ull; i <= x; ++i) { result *= i; result %= MOD; } return result; } // 順列 nPr static ull permutation(int n, int r) { assert(n >= r); //return fact(n) / fact(n - r); ull result = 1; for (ull i = n; i > n - r; --i) { result *= i; result %= MOD; } return result; } // 組み合わせ nCr // 先にmakePascalTriangleでパスカルの三角形を作成しておく必要がある static ull combination(int n, int r) { assert(n >= r); assert(n <= mPascalTriangleDepth); return mPascalTriangle[n][r]; } // 重複組合せ nHr = n+r-1Cr // 使いどころ:n人にr個を配るとき、同じ人に何個配っても良い場合とか // 4人に5個の◯を配るときa=2,b=0,c=2,d=1のとき、◯◯||◯◯|◯みたいになる。 // これは◯と|を混ぜた組み合わせで、◯の数がn,棒の数はr-1だから全体でn+r-1 // (n-r)で割ったものが順列n+r-1Prで、それを更にrで割っているからnHr = n+r-1Cr static ull repeatedCombination(int n, int r) { return combination(n + r - 1, r); } // パスカルの三角形。組み合わせの計算に使用するのでこれを先に作成しておく必要がある。 static void makePascalTriangle(int depth) { resize(mPascalTriangle, depth + 1, depth + 1); for (int i = 0; i <= depth; ++i) { mPascalTriangle[i][0] = 1; for (int j = 1; j <= i; ++j) { mPascalTriangle[i][j] = (mPascalTriangle[i - 1][j] + mPascalTriangle[i - 1][j - 1]) % MOD; } } mPascalTriangleDepth = depth; } // xのN桁目の数値を得る static ull getNDigitNumber(ull x, ull n) { return (x / pow(10ull, n - 1ull)) % 10; } // xのN桁目の数値を得る static int getNDigitNumber(int x, int n) { assert(n <= 10); return (x / pow(10, n - 1)) % 10; } // xのN乗を求める O(n) static ull pow(ull x, ull n) { if (x == 0ull) { if (n == 0ull) { return 1ull; } else { return 0ull; } } ull result = 1ull; for (ull i = 0ull; i < n; ++i) { result *= x; result %= MOD; } return result; } // xのN乗を求める O(n) static int pow(int x, int n) { assert(x >= 0); assert(n >= 0); if (x == 0) { if (n == 0) { return 1; } else { return 0; } } int result = 1; for (int i = 0; i < n; ++i) { result *= x; result %= MOD; } return result; } private: static int mPascalTriangleDepth; static vector> mPascalTriangle; }; int vmath_mod::mPascalTriangleDepth = 0; vector> vmath_mod::mPascalTriangle; class vegde { public: vegde() : mLeft(nullptr), mRight(nullptr) { } vegde(sptr left, sptr right) : vegde() { mLeft = left; mRight = right; } vegde(sptr left, sptr right, int cost) : vegde(left, right) { mCost = cost; } sptr getOpponent(sptr node) const { assert(node == mLeft || node == mRight); return (node == mLeft) ? mLeft : (node == mRight) ? mRight : nullptr; } void set(sptr left, sptr right) { mLeft = left; mRight = right; } const sptr& getLeft() const { return mLeft; } const sptr& getRight() const { return mRight; } int getCost() const { return mCost; } private: sptr mLeft; sptr mRight; int mCost; }; class vnode { public: vnode() : mID(-1) { } vnode(int id) : vnode() { mID = id; } void addEgde(sptr egde) { mEgdeList.push_back(egde); } void removeEgde(int nodeID1, int nodeID2) { auto itrNewEnd = std::remove_if(mEgdeList.begin(), mEgdeList.end(), [=](sptr e)->bool { return (e->getLeft()->getID() == nodeID1 && e->getRight()->getID() == nodeID2); }); mEgdeList.erase(itrNewEnd, mEgdeList.end()); } int getID() const { return mID; } const list>& getEgde() const { return mEgdeList; } private: list> mEgdeList; int mID; }; class AdjacencyMatrix { public: AdjacencyMatrix() { } AdjacencyMatrix(int nodeNum) { resize(mConnectionMap, nodeNum, nodeNum); resize(mCostMap, nodeNum, nodeNum); resize(mMinimumDistMap, nodeNum, nodeNum); resize(mPrevNodeMap, nodeNum, nodeNum); } void addEgde(int nodeID1, int nodeID2, int cost) { mConnectionMap[nodeID1][nodeID2] = true; mConnectionMap[nodeID2][nodeID1] = true; mCostMap[nodeID1][nodeID2] = cost; mCostMap[nodeID2][nodeID1] = cost; } void removeEgde(int nodeID1, int nodeID2) { mConnectionMap[nodeID1][nodeID2] = false; mConnectionMap[nodeID2][nodeID1] = false; mCostMap[nodeID1][nodeID2] = 0; mCostMap[nodeID2][nodeID1] = 0; } void warshallFloyd(int nodeNum) { for (int k = 0; k < nodeNum; ++k) { for (int i = 0; i < nodeNum; ++i) { for (int j = 0; j < nodeNum; ++j) { if (mConnectionMap[i][j]) { mMinimumDistMap[i][j] = mCostMap[i][j]; } else { mMinimumDistMap[i][j] = 99999999; } } } } for (int k = 0; k < nodeNum; ++k) { for (int i = 0; i < nodeNum; ++i) { for (int j = 0; j < nodeNum; ++j) { mMinimumDistMap[i][j] = min(mMinimumDistMap[i][j], mMinimumDistMap[i][k] + mMinimumDistMap[k][j]); } } } //for (int i = 0; i < mNodeNum; ++i) { // for (int j = 0; j < mNodeNum; ++j) { // cerr << mMinimumDistMap[i][j] << ", "; // } // cerr << endl; //} } const vector>& getConnectionMap() const { return mConnectionMap; } const vector>& getCostMap() const { return mCostMap; } const vector>& getMinimumDistMap() const { return mMinimumDistMap; } const vector>& getPrevNodeMap() const { return mPrevNodeMap; } private: vector> mConnectionMap; vector> mCostMap; vector> mMinimumDistMap; vector> mPrevNodeMap; }; // グラフ class vgraph { public: const int INF = 1000000; vgraph(int nodeNum) { mNodeNum = nodeNum; mNodes.resize(nodeNum); for (int i = 0; i < nodeNum; ++i) { mNodes[i] = make_shared(i); } mMinimumDists.resize(mNodeNum); mPrevNodes.resize(mNodeNum); } void addEgde(int nodeID1, int nodeID2) { addEgde(nodeID1, nodeID2, 1); } virtual void addEgde(int nodeID1, int nodeID2, int cost) = 0; virtual void removeEgde(int nodeID1, int nodeID2) = 0; // ベルマンフォード法を使ってある頂点から全ての頂点への最短距離を求める // startからたどり着ける場所に負のループが存在する場合はfalseを返す // ダイクストラ法と違い、負のコストの辺があっても最短距離を計算できる // O(V*E) bool bellmanFord(int start) { vector& dist = mMinimumDists; fill(dist, INF); dist[start] = 0; for (int i = 0; i < mNodeNum; ++i) { bool update = false; for (sptr node : mNodes) { for (sptr egde : node->getEgde()) { int from = egde->getLeft()->getID(); int to = egde->getRight()->getID(); if (dist[from] == INF) { continue; } if (dist[node->getID()] + egde->getCost() < dist[to]) { dist[to] = dist[node->getID()] + egde->getCost(); update = true; if (i == mNodeNum - 1) { //return false; } } } } if (!update) { break; } } return true; } // ダイクストラ法を使ってある頂点から全ての頂点への最短距離を求める // 負のコストの辺があると最短距離を計算できない点に注意する // O(E*logV) void dijkstraSearch(int start) { // Minimum distances for each nodes vector& dpMinDists = mMinimumDists; fill(dpMinDists, INF); // Result of the previous visited node vector& resultPrev = mPrevNodes; fill(resultPrev, -1); // Create a priority_queue for search. typedef pair P; // key: その頂点までの最短距離, value: 頂点の番号 priority_queue, greater

> pq_node; // Mark the current node as visited and enqueue it pq_node.push(P(0, start)); dpMinDists[start] = 0; while (!pq_node.empty()) { P p = pq_node.top(); pq_node.pop(); int nowDist = p.first; int nowNodeID = p.second; if (dpMinDists[nowNodeID] < nowDist) { continue; } for (sptr egde : mNodes[nowNodeID]->getEgde()) { sptr nextNode = egde->getRight(); int nextNodeID = nextNode->getID(); int nextNodeDist = nowDist + egde->getCost(); if (nextNodeDist < dpMinDists[nextNodeID]) { dpMinDists[nextNodeID] = nextNodeDist; resultPrev[nextNodeID] = nowNodeID; pq_node.push(P(nextNodeDist, nextNodeID)); } } } } int calcMaxDepth() const { pair farestNodeData = getFarestNodeID(0); pair farestNodeData2 = getFarestNodeID(farestNodeData.first); return farestNodeData2.second; } int getNodeNum() const { return mNodeNum; } const vector& getMinimumDists() const { return mMinimumDists; } const vector& getPrevNodes() const { return mPrevNodes; } protected: // 引数で受け取ったノードから最も遠いノードのidと距離を返す // グラフにループがあると無限ループになるので注意する(つまり木専用) pair getFarestNodeID(int start) const { queue> q; // nodeID, このノードまでの距離 q.push(make_pair(start, 0)); pair finalNodeData; vector opened(mNodeNum); fill(opened, false); while (!q.empty()) { pair nodeData = q.front(); int nodeID = nodeData.first; int dist = nodeData.second; if (dist > finalNodeData.second) { finalNodeData.second = dist; finalNodeData.first = nodeID; } q.pop(); for (sptr egde : mNodes[nodeID]->getEgde()) { int id = egde->getRight()->getID(); if (opened[id]) { continue; } opened[id] = true; q.push(make_pair(id, dist + egde->getCost())); } } return finalNodeData; } int mNodeNum; bool mUseMaps; vector> mNodes; vector mMinimumDists; vector mPrevNodes; }; // 無向グラフ UnDirected Val Graph. class udvgraph : public vgraph { public: udvgraph(int nodeNum) : vgraph(nodeNum) { } void addEgde(int nodeID1, int nodeID2, int cost) { mNodes[nodeID1]->addEgde(make_shared(mNodes[nodeID1], mNodes[nodeID2], cost)); mNodes[nodeID2]->addEgde(make_shared(mNodes[nodeID2], mNodes[nodeID1], cost)); } void removeEgde(int nodeID1, int nodeID2) { mNodes[nodeID1]->removeEgde(nodeID1, nodeID2); mNodes[nodeID2]->removeEgde(nodeID2, nodeID1); } }; // 隣接行列付きの無向グラフ。ワーシャルフロイドが使える。 UnDirected Val Graph Matrix class udvgraph_m : public udvgraph { public: udvgraph_m(int nodeNum) : udvgraph(nodeNum) { mAdjacencyMatrix = AdjacencyMatrix(nodeNum); } void addEgde(int nodeID1, int nodeID2, int cost) { udvgraph::addEgde(nodeID1, nodeID2, cost); mAdjacencyMatrix.addEgde(nodeID1, nodeID2, cost); } void removeEgde(int nodeID1, int nodeID2) { udvgraph::removeEgde(nodeID1, nodeID2); mAdjacencyMatrix.removeEgde(nodeID1, nodeID2); } void warshallFloyd() { mAdjacencyMatrix.warshallFloyd(mNodeNum); } const vector>& getConnectionMap() const { return mAdjacencyMatrix.getConnectionMap(); } const vector>& getCostMap() const { return mAdjacencyMatrix.getCostMap(); } const vector>& getMinimumDistMap() const { return mAdjacencyMatrix.getMinimumDistMap(); } const vector>& getPrevNodeMap() const { return mAdjacencyMatrix.getPrevNodeMap(); } private: AdjacencyMatrix mAdjacencyMatrix; }; // 無向グラフ Directed Val Graph. class dvgraph : public vgraph { public: dvgraph(int nodeNum) : vgraph(nodeNum) { } void addEgde(int nodeID1, int nodeID2, int cost) { mNodes[nodeID1]->addEgde(make_shared(mNodes[nodeID1], mNodes[nodeID2], cost)); } void removeEgde(int nodeID1, int nodeID2) { mNodes[nodeID1]->removeEgde(nodeID1, nodeID2); } }; // 隣接行列付きの有向グラフ。ワーシャルフロイドが使える。 Directed Val Graph Matrix class dvgraph_m : public dvgraph { public: dvgraph_m(int nodeNum) : dvgraph(nodeNum) { mAdjacencyMatrix = AdjacencyMatrix(nodeNum); } void addEgde(int nodeID1, int nodeID2, int cost) { dvgraph::addEgde(nodeID1, nodeID2, cost); mAdjacencyMatrix.addEgde(nodeID1, nodeID2, cost); } void removeEgde(int nodeID1, int nodeID2) { dvgraph::removeEgde(nodeID1, nodeID2); mAdjacencyMatrix.removeEgde(nodeID1, nodeID2); } void warshallFloyd() { mAdjacencyMatrix.warshallFloyd(mNodeNum); } const vector>& getConnectionMap() const { return mAdjacencyMatrix.getConnectionMap(); } const vector>& getCostMap() const { return mAdjacencyMatrix.getCostMap(); } const vector>& getMinimumDistMap() const { return mAdjacencyMatrix.getMinimumDistMap(); } const vector>& getPrevNodeMap() const { return mAdjacencyMatrix.getPrevNodeMap(); } private: AdjacencyMatrix mAdjacencyMatrix; }; // 立っているビットの数を返す static int bitcount8(unsigned char b8) { // 8 bits 限定アルゴリズムを利用している //c_assert( 8 == (CHAR_BIT * sizeof( b8 )) ); b8 = (unsigned char)( ((b8 & 0xAA) >> 1) + (b8 & 0x55) ); b8 = (unsigned char)( ((b8 & 0xCC) >> 2) + (b8 & 0x33) ); b8 = (unsigned char)( ((b8 & 0xF0) >> 4) + (b8 & 0x0F) ); return b8; } // 立っているビットの数を返す static int bitcount16(unsigned short w16) { // 16 bits 限定アルゴリズムを利用している //c_assert( 16 == (CHAR_BIT * sizeof( w16 )) ); w16 = (unsigned short)( ((w16 & 0xAAAA) >> 1) + (w16 & 0x5555) ); w16 = (unsigned short)( ((w16 & 0xCCCC) >> 2) + (w16 & 0x3333) ); w16 = (unsigned short)( ((w16 & 0xF0F0) >> 4) + (w16 & 0x0F0F) ); w16 = (unsigned short)( ((w16 & 0xFF00) >> 8) + (w16 & 0x00FF) ); return w16; } // 立っているビットの数を返す static int bitcount32(unsigned long dw32) { // 32 bits 限定アルゴリズムを利用している //c_assert( 32 == (CHAR_BIT * sizeof( dw32 )) ); dw32 = ((dw32 & 0xAAAAAAAA) >> 1) + (dw32 & 0x55555555); dw32 = ((dw32 & 0xCCCCCCCC) >> 2) + (dw32 & 0x33333333); dw32 = ((dw32 & 0xF0F0F0F0) >> 4) + (dw32 & 0x0F0F0F0F); dw32 = ((dw32 & 0xFF00FF00) >> 8) + (dw32 & 0x00FF00FF); dw32 = ((dw32 & 0xFFFF0000) >> 16) + (dw32 & 0x0000FFFF); return dw32; } } using namespace ValLib; int main() { vector N(1000); vector K(1000); for (int i = 0; i < 1000; ++i) { cin >> N[i] >> K[i]; } int count = 0; bool lastWin = false; for (int i = 0; i < 1000; ++i) { if (i == 0) { if (N[i] % (K[i] + 1) != 1) { ++count; } } else { if (lastWin) { ++count; } else { } } } cout << count << endl; }