提出 #169742


ソースコード 拡げる

Copy
#include <iostream>
#include <iomanip>  // setw
#include <algorithm> // sort next_permutation count __gcd reverse etc.
#include <set>
#include <list>
#include <map>
#include <memory>
#include <numeric> // accumulate
#include <functional>
#include <utility>
#include <iterator>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <fstream> // freopen
#include <cstdio> // scanf printf
#include <cstdlib> // abs exit atof atoi
#include <string> // memset
#include <cstring>
#include <cmath> // fabs
#include <cctype> // tolower toupper
#include <sstream> // stringstream
#include <bitset>

#define reb(i,b,n) for(int i=(int)(b); i<(int)(n); i++)
#define rep(i,n) reb(i,0,n)
#define rer(i,n) for(int i=1; i<=n; i++)
#define rrep(i,n) for(int i = n-1; i >= 0; i--)
#define rreb(i,n,b) for(int i = n; i >= b; i--)
#define resz(i,v) rep(i,sz(v))
#define let(v, x) __typeof(x) v = (x)
#define each(it,v) for(let(it, (v).begin()); it!=(v).end(); it++)
#define reach(it,v) for(let(it, (v).rbegin());i!=(v).rend();i++)
#define priArr(table, n) rep(i,n){cout<<table[i]<<' ';}cout<<'\n';
#define priAr2(table,W,H) rep(y,H){rep(x,W)cout<<table[y][x]<<' ';cout<<'\n';}
#define vall(x) (x).begin(), (x).end()
#define rvall(x) (x).rbegin(), (x).rend()
#define vsort(v) sort(vall(v))
#define rvsort(v) sort(rvall(v))
#define len(array) (sizeof (array) / sizeof *(array))
#define aall(x) x, x+len(x)
#define asort(x) sort(aall(x))
#define rasort(a, type) sort(aall(a), greater<type>())
#define afill(a, v) fill(aall(a), v)
#define afill2(a, v, type) fill((type *)a, (type *)(a + len(a)), v)
#define sz(x) (int)(x).size()
#define mp(a, b) make_pair(a, b)
#define fi first
#define se second
#define pb push_back
#define _USE_MATH_DEFINES

using std::stringstream;
using namespace std;

typedef long long ll; typedef unsigned long long ull;
typedef pair <int, int> P; typedef pair <int, P> PP;
typedef vector<int> vi;typedef vector<vi> vvi;typedef vector<string> vs;
typedef vector<ll> vl; typedef vector<P > vP; typedef vector<char> vc;
typedef long double ld;

const static int INF = 0x3f3f3f3f;
const static ll INFL = 0x3f3f3f3f3f3f3f3fLL;
const static double EPS = 1e-9;
const static ll MOD = 1000000007LL;

inline int toInt(std::string s) {int v; std::istringstream sin(s);sin>>v;return v;}
template<class T> inline std::string toString(T x) {std::ostringstream sout;sout<<x;return sout.str();}
template<class F, class T> inline void convert(const F &f, T &t){stringstream ss;ss<<f;ss>>t;}
template<class T> inline T sqr(T x) {return x*x;}

int dx[] = {1,0,-1,0}, dy[] = {0,1,0,-1};
/* --------------------------------------------------------------- */

int factorial(int n)
{
    if (n > 2) n *= factorial(n - 1);
    return n;
}

int main(int argc, char *argv[])
{
//    ios::sync_with_stdio(false);n
//    cin.tie(0); // off the synchronous of cin and cout
    int n;
    cin >> n;
    vP p;

    vector<pair<int, bool> > num;
    rep(i, n) {
        int t;
        cin >> t;
        num.pb(mp(t, true));
        bool f=false;
        rep(j, sz(p)) {
            if (p[j].fi == t) {
                p[j].se++;
                f = true;
            }
        }
        if (!f) p.pb(mp(t, 1));
    }
    int k=0;
    double omote=0;
    vi t;
    rep(i, sz(num)) {
        t.pb(0);
    }
    do{
        rep(i, sz(num)) {
            num[i].se = true;
        }

        bool f=false;
        rep(i, sz(num)) {
            if (num[i].fi != t[i]) {
                f=true;
                break;
            }
        }
        if (!f) break;
        rep(i, sz(num)) {
            t[i]=num[i].fi;
        }

        // rep(i, sz(num)) {
        //     cout << num[i].fi << ' ';
            
        // }cout << '\n';


        rep(i, n) {
            reb(j, i+1, n) {
                if (num[j].fi % num[i].fi == 0) {
                    if (num[j].se) num[j].se = false;
                    else num[j].se = true;
                }
            }
        }
        rep(i, n) {
            if (num[i].se) omote++;
        }
        k++;
    } while(next_permutation(vall(num)));
    // cout << k << endl;



    // if (n > 9) {
    //     cout << 0 << endl;
    //     return 0;
    // }cout << omote << endl;
    double bunbo, bunsi;
    bunbo = (double)factorial(n);
    bunsi = omote;
    rep(i, sz(p)) {
        bunbo /= factorial(p[i].se);
        // bunsi /= p[i].se;
    }

    // cout << bunbo <<' '<< bunsi << endl;
    cout << fixed << setprecision(12);
    // cout << omote / (double)factorial(n) << endl;
    cout << bunsi / k << endl;

    return 0;
}

提出情報

提出日時
問題 C - コイン
ユーザ emacs
言語 C++ (G++ 4.6.4)
得点 0
コード長 4742 Byte
結果 WA
実行時間 2035 ms
メモリ 940 KB

ジャッジ結果

セット名 Sample Subtask1 Subtask2
得点 / 配点 0 / 0 0 / 99 0 / 1
結果
AC × 2
WA × 1
AC × 10
WA × 8
TLE × 2
AC × 12
WA × 10
TLE × 18
セット名 テストケース
Sample sample_01.txt, sample_02.txt, sample_03.txt
Subtask1 subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_20.txt
Subtask2 subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_20.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt, subtask2_13.txt, subtask2_14.txt, subtask2_15.txt, subtask2_16.txt, subtask2_17.txt, subtask2_18.txt, subtask2_19.txt, subtask2_20.txt
ケース名 結果 実行時間 メモリ
sample_01.txt AC 21 ms 792 KB
sample_02.txt AC 20 ms 748 KB
sample_03.txt WA 22 ms 676 KB
subtask1_01.txt AC 21 ms 928 KB
subtask1_02.txt AC 22 ms 704 KB
subtask1_03.txt WA 21 ms 928 KB
subtask1_04.txt AC 33 ms 804 KB
subtask1_05.txt WA 33 ms 804 KB
subtask1_06.txt AC 23 ms 928 KB
subtask1_07.txt AC 30 ms 804 KB
subtask1_08.txt WA 20 ms 928 KB
subtask1_09.txt WA 20 ms 920 KB
subtask1_10.txt AC 32 ms 808 KB
subtask1_11.txt WA 21 ms 752 KB
subtask1_12.txt AC 30 ms 792 KB
subtask1_13.txt AC 19 ms 796 KB
subtask1_14.txt AC 20 ms 796 KB
subtask1_15.txt TLE 2028 ms 884 KB
subtask1_16.txt AC 21 ms 804 KB
subtask1_17.txt WA 22 ms 804 KB
subtask1_18.txt TLE 2029 ms 804 KB
subtask1_19.txt WA 30 ms 796 KB
subtask1_20.txt WA 32 ms 796 KB
subtask2_01.txt AC 1514 ms 788 KB
subtask2_02.txt AC 21 ms 928 KB
subtask2_03.txt WA 20 ms 796 KB
subtask2_04.txt WA 20 ms 800 KB
subtask2_05.txt TLE 2029 ms 808 KB
subtask2_06.txt TLE 2028 ms 800 KB
subtask2_07.txt TLE 2034 ms 800 KB
subtask2_08.txt TLE 2031 ms 804 KB
subtask2_09.txt TLE 2028 ms 804 KB
subtask2_10.txt TLE 2028 ms 800 KB
subtask2_11.txt TLE 2028 ms 884 KB
subtask2_12.txt TLE 2035 ms 796 KB
subtask2_13.txt TLE 2028 ms 916 KB
subtask2_14.txt TLE 2035 ms 940 KB
subtask2_15.txt TLE 2028 ms 924 KB
subtask2_16.txt TLE 2029 ms 800 KB
subtask2_17.txt TLE 2029 ms 924 KB
subtask2_18.txt TLE 2028 ms 884 KB
subtask2_19.txt TLE 2028 ms 920 KB
subtask2_20.txt TLE 2029 ms 800 KB