Submission #8804908


Source Code Expand

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using VI = vector<ll>;
using VV = vector<VI>;
using VS = vector<string>;
using PII = pair<ll, ll>;

// tourist set
template <typename A, typename B>
string to_string(pair<A, B> p);

template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p);

template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p);

string to_string(const string& s) {
  return '"' + s + '"';
}

string to_string(const char* s) {
  return to_string((string) s);
}

string to_string(bool b) {
  return (b ? "true" : "false");
}

string to_string(vector<bool> v) {
  bool first = true;
  string res = "{";
  for (int i = 0; i < static_cast<int>(v.size()); i++) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(v[i]);
  }
  res += "}";
  return res;
}

template <size_t N>
string to_string(bitset<N> v) {
  string res = "";
  for (size_t i = 0; i < N; i++) {
    res += static_cast<char>('0' + v[i]);
  }
  return res;
}

template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}

template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")";
}

template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
}

void debug_out() { cerr << '\n'; }

template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}

#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif
// tourist set end

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define rep(i,b) FOR(i, 0, b)
#define ALL(v) (v).begin(), (v).end()
#define p(s) cout<<(s)<<'\n'
#define p2(s, t) cout << (s) << " " << (t) << '\n'
#define br() p("")
#define pn(s) cout << (#s) << " " << (s) << '\n'
#define p_yes() p("YES")
#define p_no() p("NO")
#define SZ(x) ((int)(x).size())
#define SORT(A) sort(ALL(A))
#define RSORT(A) sort(ALL(A), greater<ll>())
#define MP make_pair

void no(){p_no(); exit(0);}
void yes(){p_yes(); exit(0);}

const ll mod = 1e9 + 7;
const ll inf = 1e18;
const double PI = acos(-1);

double dp[2][201][101][101];

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll N, D;
    cin >> N >> D;

    ll cur = 0;
    ll next = 1;
    dp[0][0][0][0] = 1;
    rep(i, N){
      memset(dp[next], 0, sizeof(dp[next]));
      // i回目なら、今までに出た2の数は
      ll num2_max = 2*i;
      ll num3_max = i;
      ll num5_max = i;
      
      rep(j, num2_max+1){
        rep(k, num3_max+1){
          rep(l, num5_max+1) if(dp[cur][j][k][l]){
            dp[next][j][k][l] += dp[cur][j][k][l]; // 1
            dp[next][j+1][k][l] += dp[cur][j][k][l]; // 2
            dp[next][j][k+1][l] += dp[cur][j][k][l]; // 3
            dp[next][j+2][k][l] += dp[cur][j][k][l]; // 4
            dp[next][j][k][l+1] += dp[cur][j][k][l]; // 5
            dp[next][j+1][k+1][l] += dp[cur][j][k][l]; // 6
          }
        }
      }
      swap(cur, next);
      // cur == 1
      // next == 0
    }

    ll d = D;
    int two = 0, three = 0, five = 0;
    while(d % 2 == 0) two++, d /= 2;
    while(d % 3 == 0) three++, d /= 3;
    while(d % 5 == 0) five++, d /= 5;

    double sum = 0;
    FOR(i, two, 201){
      FOR(j, three, 101){
        FOR(k, five, 101){
          sum += dp[cur][i][j][k];
        }
      }
    }
    rep(i, N){
      sum /= 6.0;
    }
    cout << setprecision(20);
    p(sum * (d==1));

    return 0;
}

Submission Info

Submission Time
Task D - サイコロ
User peroon
Language C++14 (GCC 5.4.1)
Score 4
Code Size 4456 Byte
Status AC
Exec Time 277 ms
Memory 32256 KB

Judge Result

Set Name All
Score / Max Score 4 / 4
Status
AC × 13
Set Name Test Cases
All 00, 01, 02, 03, 04, 05, 06, 07, 08, 09, 10, 90, 91
Case Name Status Exec Time Memory
00 AC 68 ms 32256 KB
01 AC 198 ms 32256 KB
02 AC 174 ms 32256 KB
03 AC 75 ms 32256 KB
04 AC 72 ms 32256 KB
05 AC 222 ms 32256 KB
06 AC 193 ms 32256 KB
07 AC 177 ms 32256 KB
08 AC 38 ms 32256 KB
09 AC 167 ms 32256 KB
10 AC 277 ms 32256 KB
90 AC 12 ms 32256 KB
91 AC 14 ms 32256 KB