Submission #17506684


Source Code Expand

Copy
/*
//DP D ナップサック問題

template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

const long long INF = 1LL << 60;

// 入力
int N;
long long W, weight[110], value[110]; // 品物の個数は 100 個なので少し余裕持たせてサイズ 110 に

// DPテーブル
long long dp[110][100100] = {0};

int main() {
  cin >> N >> W;
  for(int i=0;i<N;i++){
    cin >> weight[i] >> value[i];
  }
  
  // DPループ
  for(int i=0;i<N;i++){
    for(int sum_w = 0;sum_w <=W;sum_w++){
      
      //i番目の品物を選ぶ場合
      if(sum_w - weight[i] >= 0){
        chmax(dp[i+1][sum_w],dp[i][sum_w - weight[i]] + value[i]);
      }
      
      //i番目の品物を選ばない場合
      chmax(dp[i+1][sum_w], dp[i][sum_w]);
    }
  }
  
  //最適値の出力
  cout << dp[N][W] << endl;
  
}
*/
/*
//DP  C - 柱柱柱柱柱など
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

const long long INF = 1LL << 60;

// 入力
int N;
long long h[100010];

// DP テーブル
long long dp[100010];

int main() {
    int N; cin >> N;
    for (int i = 0; i < N; ++i) cin >> h[i];

    // 初期化 (最小化問題なので INF に初期化)
    for (int i = 0; i < 100010; ++i) dp[i] = INF;

    // 初期条件
    dp[0] = 0;

    // ループ
    for (int i = 1; i < N; ++i) {
        chmin(dp[i], dp[i - 1] + abs(h[i] - h[i - 1]));
        if (i > 1) chmin(dp[i], dp[i - 2] + abs(h[i] - h[i - 2]));
    }

    // 答え
    cout << dp[N-1] << endl;
}
*/

/*
ABC026 高橋君の給料 DFS
int dfs(int n,vector<vector<int>> G){
  int mi = 1000000000;
  int ma = 0;
  int w,v;
  for(int i=0;i<G[n].size();i++){
    v = G[n][i];
    if(G[v].size() == 0)w = 1;
    else w = dfs(v,G);
    
    mi = min(mi,w);
    ma = max(ma,w);
  }
  return mi + ma + 1;
}
int main() {
  int n;
  cin >> n;
  Graph G(n+1);
  for(int i=2;i<=n;i++){
    int a;
    cin >> a;
    G[a].push_back(i);
  }
  int ans = dfs(1,G);
  cout << ans << endl;
}
*/
//素因数分解
//ABC169-D - Div Game
/*
int main() {
  ll n;
  cin >> n;
  vector<pair<ll,ll> > res;
  for(ll i = 2;i*i <= n;i++){
    if(n % i !=0) continue;
    ll ex = 0;// 指数
    
    //割れる限り割り続ける
    while(n % i ==0){
      ex++;
      n /=i;
    }
    
    //その結果をpush
    res.push_back({i,ex});
  }
  
  //最後に残った数について
  if(n !=1) res.push_back({n,1});
  
//    cout << n << ":";
//    for (auto p : res) {
//        for (int i = 0; i < p.second; ++i) cout << " " << p.first;
//    }
//   cout << endl;
  
  ll times = 0;
    for (auto p : res) {
      int count = 1;
      int cnt = 0;
       while(p.second > cnt){
//         cout << p.second << endl;
         p.second -=count;
         count++;
         cnt ++;
       }
      times += cnt;
    }
  cout << times << endl;
}
*/
  //ABC146 //二分探索
/*int main() {
  ll a,b,x;
  cin >> a >> b >> x;
  ll left = 0;
  ll right = 1000000001;
  while(right - left > 1){
    ll mid = (left + right ) /2;
    if(a * mid + b * ketasuu(mid) > x) right = mid;
    else left = mid;
//    cout << left << " " << right  << endl;
  }
  cout << left << endl;
}
*/

//ABC_128_B// pair型の中にpair型
/*int main() {
  int n;
  cin >> n;
  vector<pair<pair<string,int>,int>> a(n);
  for(int i=0;i<n;i++){
    string s;
    cin >> s;
    int num;
    cin >> num;
    num = num * -1;

    a.at(i).first.first  = s;
    a.at(i).first.second = num;
    a.at(i).second 		 = i;
  }
  sort(a.begin(), a.end());
  for(int i=0;i<n;i++){
    cout <<   a.at(i).second +1 << endl;
  }
}
*/
//ABC_058_Cのように
// s.at(j) == a のとき
//cout << s.at(j)-'0' - 49 << endl;
//とすると、「0」を出力してくれる。 →もっといいほかの方法はないの?

//全bit探索を入れよう!!
/*ABC_167_C skill up などを参考に…
//https://qiita.com/hareku/items/3d08511eab56a481c7db
int main() {
    int n = 3;

    // {0, 1, ..., n-1} の部分集合の全探索
    for (int bit = 0; bit < (1<<n); ++bit) {
        vector<int> S;
        for (int i = 0; i < n; ++i) {
            if (bit & (1<<i)) { // 列挙に i が含まれるか
                S.push_back(i);
            }
        }

        cout << bit << ": {";
        for (int i = 0; i < (int)S.size(); ++i) {
            cout << S[i] << " ";
        }
        cout << "}" << endl;
    }
}
*/
//next_permutation(順列列挙)
/*https://note.com/memenekokaburi/n/nf0201d6002cd
//https://scrapbox.io/ganariya/AtCoderGrandContest022_A%E5%95%8F%E9%A1%8C300%E7%82%B9%E3%80%8CDiverse_Word%E3%80%8D_(copy)
//https://atcoder.jp/contests/agc022/tasks/agc022_a
ABC_150_Cなど。
int main() {
  int n;
  cin >> n ;
   vector<int>array = {};
   for(int i=0;i<n;i++){
    array.push_back(i);
   }
  do{
        for(int i=0; i<n; i++){
            cout << array.at(i);
            if(i!=n-1)cout<<" ";
        }
        cout<<endl;
    }while(next_permutation(array.begin(),array.end()));
    return 0;
}
*/

//ABC126_Cのように関数でdouble型で返ってきてほしい場合はdouble kan_halfのようにかく
/*
//ABC_041_C// pair型
int main() {
  int n;
  cin >> n;
  vector<pair<int,int>>a(n);
  for(int i=0;i<n;i++){
    int num;
    cin >> num;
    a.at(i).first  = num;
    a.at(i).second = i;
  }
  sort(a.begin(), a.end());
  reverse(a.begin(),a.end());
  for(int i=0;i<n;i++){
    cout << a.at(i).second + 1<< endl;
  }
}
*/
/*ABC_068_C //boolの配列を使って
bool s[200050] = {};
bool t[200050] = {};
int main() {
	ll n, m; cin >> n >> m;
	for (int i = 0; i < m; i++){
		ll a, b; cin >> a >> b;
		if (a == 1) {
			t[b] = true;
		}
		if (b == n) {
			s[a] = true;
		}
	}
	for (int i = 0; i < 200050; i++){
		if (s[i] && t[i]) {
			cout << "POSSIBLE" << endl;
			return 0;
		}
	}
	cout << "IMPOSSIBLE" << endl;
	return 0;
}
*/

//int32	4	signed, signed int, int	-2,147,483,648 ~ 2,147,483,647 = 2*10^9
//再帰関数 ABC_029_C
/*
void f(int rest , string s){
  if(rest == 0){
    cout << s << endl;
  }
  else{
    for(char moji = 'a' ;moji <='c' ; moji++){
      f(rest-1,s+moji);
    } 
  }
}
 
int main() {
  int n;
  cin >> n;
  f(n, "");
}
*/
  //連想配列 ARC_081_Cの解答 //ABC073でも復習できます。
/*
int main() {
  ll n;
  cin >> n;
  vector<ll>a(n);
  rep(i,n) cin>>a.at(i);
  map<ll,ll>mp;
  rep(i,n){
    mp[a.at(i)]++;
  }
  ll one  = 0;
  ll two = 0;
  for(auto p:mp){
//    cout << p.first << " " << p.second << endl;
    if(p.second >= 2){
      if(one <= p.first){
        two = one;
        one = p.first;
      }
    }
    if(p.second >= 4){
      if(one <= p.first){
        two = p.first;
        one = p.first;
      }
    }
  }
//  cout << one << endl;
//  cout << two << endl;
//  cout << endl;
  cout << one * two << endl;
}
*/

//関数
/*
ll gcd(ll a, ll b){
   if (a%b == 0){
       return(b);
   }
   else{
       return(gcd(b, a%b));
   }
}

ll lcm(ll a, ll b){
//   return a * b / gcd(a, b);
     return a / gcd(a, b)* b;
}

int kan_hyaku(int n){
  int kurai = 0;
  for(int i=0;i<3;i++){
    kurai = n%10;
    n /=10;
  }
  return kurai;
}
int kan_ju(int n){
  int kurai = 0;
  for(int i=0;i<2;i++){
    kurai = n%10;
    n /=10;
  }
  return kurai;
}
int kan_ichi(int n){
  int kurai = 0;
  for(int i=0;i<1;i++){
    kurai = n%10;
    n /=10;
  }
  return kurai;
}

ll keta(ll n){
  ll wa = 1;
  while(n>0){
    wa *=10;
    n--;
  }
  return wa;
}

double kan_half(int n){
  double wa = 1;
  while(n>0){
//    cout << "TEST"<<endl;
    wa *= 0.5;
//    cout << wa << endl;
    n--;
  }
  return wa;
}

ll facctorialMethod(ll k){
    ll sum = 1;
    for (ll i = 1; i <= k; ++i)
    {
        sum = sum%1000000007 * i%1000000007;
    }
    return sum;
}

int zorocheck(string s){
  int count = 0;
  rep(i,s.size()){
    if(s.at(i) == s.at(0)) count++;
  }
  if(count ==s.size()){
    return 1;
  }
  else{
    return 0;
  }
}

int sannobekijou(int n){
  int wa = 1;
  while(n>0){
    n--;
    wa *=3;
  }
  return wa;
}
ll ketasuu(ll k){
  ll wa = 0;
  while(k > 0){
    k /=10;
    wa++;
  }
  return wa;
}
ll beki(ll f,ll num){
  ll wa = 1;
  while(num > 0){
    wa *= f;
    num--;
//    cout << wa << endl;
  }
  return wa;
}
ll fibona(ll num){
  vector<ll>c(3);
  c.at(0) = 1;
  c.at(1) = 2;
  c.at(2) = 3;
  if(num == 1){
    return c.at(0);
  }
  else if(num == 2){
    return c.at(1);
  }
  else if(num == 3){
    return c.at(2);
  }
  else{
    for(ll i = 3; i < num;i++){
//      cout << " tes " << endl;
      ll tmp;
      tmp = c.at(1) + c.at(2);
      tmp %= 1000000007;
      c.at(0) = c.at(1);
      c.at(1) = c.at(2);
      c.at(2) = tmp;
    }
    return c.at(2);
  }
}
*/

//桁数を指定して出力する方法
//#include <iomanip>//これをincludeしておかないといけない
//cout << fixed << setprecision(20)<< ans << endl;

//  s.at(0) = toupper(s.at(0));//小文字なら大文字へ//大文字の場合はそのまま
//  s.at(i) = tolower(s.at(i));//大文字なら小文字へ//小文字の場合はそのまま
//getline(cin, s); //空白文字を含むものをまとめて入力できる。
//s配列に格納した単語を、辞書順にソートする
//  sort(s.begin(), s.end());
//  string t = "keyence";//で文字列を格納できる
//s.empty() //emptyなら1を出力 入っていれば0を出力
/*//ABC018-B 部分的にreverseをかける解法
int main() {
  string s; cin >> s;
  int n; cin >> n;
  vector<int>a(n); vector<int>b(n);
  rep(i,n) cin>>a.at(i)>>b.at(i);
  rep(i,n)a.at(i)--;  rep(i,n)b.at(i)--;
  string t;
  rep(i,n){
    t = s;
    for(int k=0;k<=b.at(i)-a.at(i);k++){
      t.at(a.at(i)+k) = s.at(b.at(i)-k);
    }
    s = t;
  }
  cout << s << endl;
}
*///ABC018-B
//  cout << char(i+48) << endl;//なぜかaは47と得る時がある。+48で出力もaにできる。
//  cout << char(97) << endl;//アスキーコードでaを出力
// sort(b.begin(), b.end());//bという配列を小さい方からソート
// reverse(b.begin(), b.end());//bという配列をリターン
/*01 02 03 12 13 23 と6回見ていくパターン 
for(int i=0;i<n-1;i++){
  for(int j=i+1;j<n;j++){
    }
  }
*/
//vector<vector<int>> a(3, vector<int>(4));//int型の2次元配列(3×4要素の)の宣言
//10のi乗pow(10, i);//ただしdouble型のため注意
/*string s; stringでの文字列を数字型に変える方法
  cin >> s;
  rep(i,s.size()-2) {
  int a= (s.at(i)-'0')*100 + (s.at(i+1)-'0')*10+ s.at(i+2) -'0';
*/
/*
  int n;
  cin >> n;
  vector<int>a(n);
  rep(i,n) cin >> a.at(i); 
*/
//cout << fixed << setprecision(10)<< ans << endl;
//数字から文字列に変換  a.at(0) = std::to_string(111);
#include <bits/stdc++.h>
#include <iomanip>//これをincludeしておかないといけない
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
using Graph = vector<vector<int>>;
typedef long long ll;
typedef long double lld;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define PI 3.14159265359
#define MOD 1000000007
/*
  ll n;
  cin >> n;
  vector<ll>a(n);
  rep(i,n) cin >> a.at(i);
*/

template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

const long long INF = 1LL << 60;

//            2    3   5
double dp[110][100][50][50];
//double dp[2][100][50][50];
ll N,D;
signed main(){
    cin>>N>>D;
    int c2=0,c3=0,c5=0;
    while(D%2==0){D/=2;c2++;}
    while(D%3==0){D/=3;c3++;}
    while(D%5==0){D/=5;c5++;}

    if(D!=1){
        printf("%.10lf",0);
        return 0;
    }


    dp[0][0][0][0]=1;

    for(int i=0;i<N;i++){
        for(int pc2=0;pc2<=c2;pc2++)for(int pc3=0;pc3<=c3;pc3++)for(int pc5=0;pc5<=c5;pc5++){
            for(int j=1;j<=6;j++){
                int nc2=min(c2,(j==2||j==6?pc2+1:(j==4?pc2+2:pc2)));
                int nc3=min(c3,(j%3==0?pc3+1:pc3));
                int nc5=min(c5,(j%5==0?pc5+1:pc5));
                dp[i+1][nc2][nc3][nc5]+=dp[i][pc2][pc3][pc5]/6.0;
//                dp[(i+1)&1][nc2][nc3][nc5]+=dp[i&1][pc2][pc3][pc5]/6.0;
            }
//            dp[i&1][pc2][pc3][pc5]=0;
        }
    }

    printf("%.10lf\n",dp[N][c2][c3][c5]);
//    printf("%.10lf\n",dp[N&1][c2][c3][c5]);
    return 0;
}

Submission Info

Submission Time
Task D - サイコロ
User oroninehn
Language C++ (GCC 9.2.1)
Score 4
Code Size 13290 Byte
Status
Exec Time 36 ms
Memory 23092 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:602:22: warning: format ‘%lf’ expects argument of type ‘double’, but argument 2 has type ‘int’ [-Wformat=]
  602 |         printf("%.10lf",0);
      |                 ~~~~~^  ~
      |                      |  |
      |                      |  int
      |                      double
      |                 %.10d

Judge Result

Set Name All
Score / Max Score 4 / 4
Status
× 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 6 ms 3668 KB
01 16 ms 9644 KB
02 10 ms 6120 KB
03 8 ms 5588 KB
04 8 ms 6516 KB
05 17 ms 11728 KB
06 36 ms 23092 KB
07 27 ms 22584 KB
08 8 ms 7784 KB
09 27 ms 15384 KB
10 2 ms 3508 KB
90 2 ms 3524 KB
91 1 ms 3672 KB