結果
問題 | No.220 世界のなんとか2 |
ユーザー | medo_program05 |
提出日時 | 2020-02-12 01:14:02 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 1,000 ms |
コード長 | 1,200 bytes |
コンパイル時間 | 1,956 ms |
コンパイル使用メモリ | 168,656 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-10-01 14:36:02 |
合計ジャッジ時間 | 2,595 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 19 |
ソースコード
/*yukicoder No.220 世界のなんとか2*/ #include <bits/stdc++.h> using namespace std; typedef long long ll; int main(){ int p; cin >> p; vector<int> n(p+1); n[0] = 1; for(int i = 1; i <= p; i++) n[i] = 0; ll dp[25][2][2][3] = {0}; dp[0][0][0][0] = 1; // i digits // j less ? // k have 3 ? x == 3 -> true // r mod 3<--> (remainder + x) % 3 for(int i = 0; i <= p; i++){ for(int j = 0; j < 2; j++){ for(int k = 0; k < 2; k++){ for(int r = 0; r < 3; r++){ for(int x = 0; x <= (j?9:n[i]); x++){ dp[i+1][j || x < n[i]][k || x == 3][(r+x) % 3] += dp[i][j][k][r]; } } } } } //(have 3 + mod 3 - have3 && mod3) ll ans = 0; for(int i = 0; i < 2; i++){ for(int j = 0; j < 2; j++){ ans += dp[p+1][i][j][0]; } } ans -= (dp[p+1][0][1][0]+dp[p+1][1][1][0]); for(int i = 0; i < 2; i++){ for(int j = 0; j < 3; j++){ ans += dp[p+1][i][1][j]; } } //cout << dp[p+1][0][1][0]+dp[p+1][1][1][0]; cout << ans-1 << endl; return 0; }