codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
// BEGIN CUT HERE #include "stdafx.h" // END CUT HERE #include <cstdio> #include <cstdlib> #include <cmath> #include <climits> #include <cfloat> #include <map> #include <utility> #include <set> #include <iostream> #include <memory> #include <string> #include <vector> #include <algorithm> #include <functional> #include <sstream> #include <complex> #include <stack> #include <queue> #include <numeric> using namespace std; typedef long long ll; static const double EPS = 1e-9; int ROUND(double x) { return (int)(x+0.5); } bool ISINT(double x) { return fabs(ROUND(x)-x)<EPS; } bool ISEQUAL(double x,double y) { return fabs(x-y)<EPS; } #define PI (3.14159265358979323846) template<class T> bool INRANGE(T x,T a,T b) { return a<=x&&x<=b; } double SQSUM(double x,double y) { return x*x+y*y; } #define SZ(a) ((int)a.size()) class DonutsOnTheGrid { public: long long calc(int H, int W, int seed, int threshold) { long long result = 0; vector <string> field; int a = seed; for(int y=0;y<H;y++) { string tmp; for(int x=0;x<W;x++) { a = (a * 25173 + 13849) % 65536; if(a>=threshold) { tmp += "."; } else { tmp += "O"; } } field.push_back(tmp); } vector <vector <int> > tate_len(H, vector<int>(W,0)); for(int y=0;y<H;y++) { for(int x=0;x<W;x++) { if(field[y][x]=='O') { if(y>=1) { tate_len[y][x] = tate_len[y-1][x] + 1; } else { tate_len[y][x] = 1; } } } } for(int y1=0;y1<H-2;y1++) { for(int y2=y1+2;y2<H;y2++) { int cnt = -1; bool horyu = false; for(int x=0;x<W;x++) { if(field[y1][x]=='.'||field[y2][x]=='.') { cnt = -1; horyu = false; } else if(y2-y1+1<=tate_len[y2][x]) { if(horyu) { cnt++; horyu = false; } if(x>=1 && y2-y1+1<=tate_len[y2][x-1]) { horyu = true; } else { cnt++; } result += cnt; } } } } #if 0 // 残念な回答 vector <vector <int> > tate_len(H, vector<int>(W,0)); vector <vector <int> > yoko_len(H, vector<int>(W,0)); for(int y=0;y<H;y++) { for(int x=0;x<W;x++) { if(field[y][x]=='O') { if(y>=1) { tate_len[y][x] = tate_len[y-1][x] + 1; } else { tate_len[y][x] = 1; } if(x>=1) { yoko_len[y][x] = yoko_len[y][x-1] + 1; } else { yoko_len[y][x] = 1; } } } } // 長方形の数。右下の頂点の位置でかぞえる vector <vector <ll> > num_rect(H, vector<ll>(W,0)); for(int y=0;y<H;y++) { for(int x=0;x<W;x++) { // 下の辺と右の辺の長さがどちらも3以上 if(yoko_len[y][x]>=3 && tate_len[y][x]>=3) { if(yoko_len[y-tate_len[y][x]+1][x]>=3 && tate_len[y][x-yoko_len[y][x]+1]>=3) { num_rect[y][x] = 1; result += num_rect[y][x]; } } } } #endif return result; } // BEGIN CUT HERE public: void run_test(int Case) { if ((Case == -1) || (Case == 0)) test_case_0(); if ((Case == -1) || (Case == 1)) test_case_1(); if ((Case == -1) || (Case == 2)) test_case_2(); if ((Case == -1) || (Case == 3)) test_case_3(); } private: template <typename T> string print_array(const vector<T> &V) { ostringstream os; os << "{ "; for (typename vector<T>::const_iterator iter = V.begin(); iter != V.end(); ++iter) os << '\"' << *iter << "\","; os << " }"; return os.str(); } void verify_case(int Case, const long long &Expected, const long long &Received) { cerr << "Test Case #" << Case << "..."; if (Expected == Received) cerr << "PASSED" << endl; else { cerr << "FAILED" << endl; cerr << "\tExpected: \"" << Expected << '\"' << endl; cerr << "\tReceived: \"" << Received << '\"' << endl; } } void test_case_0() { int Arg0 = 5; int Arg1 = 5; int Arg2 = 222; int Arg3 = 55555; long long Arg4 = 4LL; verify_case(0, Arg4, calc(Arg0, Arg1, Arg2, Arg3)); } void test_case_1() { int Arg0 = 5; int Arg1 = 6; int Arg2 = 121; int Arg3 = 58000; long long Arg4 = 3LL; verify_case(1, Arg4, calc(Arg0, Arg1, Arg2, Arg3)); } void test_case_2() { int Arg0 = 4; int Arg1 = 5; int Arg2 = 6; int Arg3 = 50000; long long Arg4 = 1LL; verify_case(2, Arg4, calc(Arg0, Arg1, Arg2, Arg3)); } void test_case_3() { int Arg0 = 4; int Arg1 = 4; int Arg2 = 1; int Arg3 = 65536; long long Arg4 = 9LL; verify_case(3, Arg4, calc(Arg0, Arg1, Arg2, Arg3)); } // END CUT HERE }; // BEGIN CUT HERE int main() { DonutsOnTheGrid* ___test = new DonutsOnTheGrid(); ___test->run_test(-1); delete ___test; } // END CUT HERE
Private
[
?
]
Run code
Submit