結果
問題 | No.23 技の選択 |
ユーザー | hamray |
提出日時 | 2020-03-05 20:33:36 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 2 ms / 5,000 ms |
コード長 | 8,344 bytes |
コンパイル時間 | 1,388 ms |
コンパイル使用メモリ | 164,464 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-10-14 02:07:33 |
合計ジャッジ時間 | 2,189 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 33 |
ソースコード
#include <bits/stdc++.h>//typedef//-------------------------#include <bits/stdc++.h>const double pi = 3.141592653589793238462643383279;using namespace std;//conversion//------------------------------------------inline int toInt(string s) { int v; istringstream sin(s); sin >> v; return v; }template<class T> inline string toString(T x) { ostringstream sout; sout << x; return sout.str(); }inline int readInt() { int x; scanf("%d", &x); return x; }//typedef//------------------------------------------typedef vector<int> VI;typedef vector<VI> VVI;typedef vector<string> VS;typedef pair<int, int> PII;typedef pair<long long, long long> PLL;typedef pair<int, PII> TIII;typedef long long LL;typedef unsigned long long ULL;typedef vector<LL> VLL;typedef vector<VLL> VVLL;//container util//------------------------------------------#define ALL(a) (a).begin(),(a).end()#define RALL(a) (a).rbegin(), (a).rend()#define PB push_back#define MP make_pair#define SZ(a) int((a).size())#define SQ(a) ((a)*(a))#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)#define EXIST(s,e) ((s).find(e)!=(s).end())#define SORT(c) sort((c).begin(),(c).end())//repetition//------------------------------------------#define FOR(i,s,n) for(int i=s;i<(int)n;++i)#define REP(i,n) FOR(i,0,n)#define MOD 1000000007#define rep(i, a, b) for(int i = a; i < (b); ++i)#define trav(a, x) for(auto& a : x)#define all(x) x.begin(), x.end()#define sz(x) (int)(x).size()typedef long long ll;typedef pair<int, int> pii;typedef vector<int> vi;const double EPS = 1E-8;#define chmin(x,y) x=min(x,y)#define chmax(x,y) x=max(x,y)class UnionFind {public:vector <int> par;vector <int> siz;UnionFind(int sz_): par(sz_), siz(sz_, 1) {for (ll i = 0; i < sz_; ++i) par[i] = i;}void init(int sz_) {par.resize(sz_);siz.assign(sz_, 1LL);for (ll i = 0; i < sz_; ++i) par[i] = i;}int root(int x) {while (par[x] != x) {x = par[x] = par[par[x]];}return x;}bool merge(int x, int y) {x = root(x);y = root(y);if (x == y) return false;if (siz[x] < siz[y]) swap(x, y);siz[x] += siz[y];par[y] = x;return true;}bool issame(int x, int y) {return root(x) == root(y);}int size(int x) {return siz[root(x)];}};class WeightedUnionFind{public:vector <int> par;vector <int> siz;vector <ll> diff_weight; /* 頂点間の重みの差 */WeightedUnionFind(int sz_): par(sz_), siz(sz_, 1LL), diff_weight(sz_, 0LL){for(int i=0; i<sz_; i++) par[i] = i;}void init(int sz_){par.resize(sz_);siz.assign(sz_, 1LL);diff_weight.resize(sz_);for(int i=0; i<sz_; i++) par[i] = i, diff_weight[i] = 0;}int root(int x){if(par[x] == x){return x;}else{int r = root(par[x]);diff_weight[x] += diff_weight[par[x]];return par[x] = r;}}ll weight(ll x){root(x);return diff_weight[x];}bool issame(int x, int y){return root(x) == root(y);}bool merge(int x, int y, ll w){w += weight(x); w -= weight(y);x = root(x); y = root(y);if(x == y) return false;if (siz[x] < siz[y]) swap(x, y), w = -w;siz[x] += siz[y];par[y] = x;diff_weight[y] = w;return true;}ll diff(int x, int y){return weight(y) - weight(x);}};ll modPow(ll x, ll n, ll mod = MOD){if(n <= 0) return 1;ll res = 1;while(n){if(n&1) res = (res * x)%mod;res %= mod;x = x * x %mod;n >>= 1;}return res;}#define SIEVE_SIZE 500000+10bool sieve[SIEVE_SIZE];void makeSieve(){for(int i=0; i<SIEVE_SIZE; ++i) sieve[i] = true;sieve[0] = sieve[1] = false;for(int i=2; i*i<SIEVE_SIZE; ++i) if(sieve[i]) for(int j=2; i*j<SIEVE_SIZE; ++j) sieve[i*j] = false;}bool isprime(ll n){if(n == 0 || n == 1) return false;for(ll i=2; i*i<=n; ++i) if(n%i==0) return false;return true;}const int MAX = 2000010;long long fac[MAX], finv[MAX], inv[MAX];// テーブルを作る前処理void COMinit() {fac[0] = fac[1] = 1;finv[0] = finv[1] = 1;inv[1] = 1;for (int i = 2; i < MAX; i++){fac[i] = fac[i - 1] * i % MOD;inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;finv[i] = finv[i - 1] * inv[i] % MOD;}}// 二項係数計算long long COM(int n, int k){if (n < k) return 0;if (n < 0 || k < 0) return 0;return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;}long long extGCD(long long a, long long b, long long &x, long long &y) {if (b == 0) {x = 1;y = 0;return a;}long long d = extGCD(b, a%b, y, x);y -= a/b * x;return d;}// 負の数にも対応した mod (a = -11 とかでも OK)inline long long mod(long long a, long long m) {return (a % m + m) % m;}// 逆元計算 (ここでは a と m が互いに素であることが必要)long long modinv(long long a, long long m) {long long x, y;extGCD(a, m, x, y);return mod(x, m); // 気持ち的には x % m だが、x が負かもしれないので}ll GCD(ll a, ll b){if(b == 0) return a;return GCD(b, a%b);}template< typename Monoid, typename OperatorMonoid = Monoid >struct LazySegmentTree{using F = function< Monoid(Monoid, Monoid) >;using G = function< Monoid(Monoid, OperatorMonoid) >;using H = function< OperatorMonoid(OperatorMonoid, OperatorMonoid) >;using P = function< OperatorMonoid(OperatorMonoid, int) >;int sz;vector< Monoid > data;vector< OperatorMonoid > lazy;const F f;const G g;const H h;const P p;const Monoid M1;const OperatorMonoid OM0;LazySegmentTree(int n, const F f, const G g, const H h, const P p,const Monoid &M1, const OperatorMonoid OM0): f(f), g(g), h(h), p(p), M1(M1), OM0(OM0){sz = 1;while(sz < n) sz <<= 1;data.assign(2 * sz, M1);lazy.assign(2 * sz, OM0);}void set(int k, const Monoid &x){data[k + sz] = x;}void build(){for(int k = sz - 1; k > 0; k--) {data[k] = f(data[2 * k + 0], data[2 * k + 1]);data[k] %= MOD;}}void propagate(int k, int len){if(lazy[k] != OM0) {if(k < sz) {lazy[2 * k + 0] = h(lazy[2 * k + 0], lazy[k]);lazy[2 * k + 1] = h(lazy[2 * k + 1], lazy[k]);}data[k] = g(data[k], p(lazy[k], len));lazy[k] = OM0;}}Monoid update(int a, int b, const OperatorMonoid &x, int k, int l, int r){propagate(k, r - l);if(r <= a || b <= l) {return data[k];} else if(a <= l && r <= b) {lazy[k] = h(lazy[k], x);propagate(k, r - l);return data[k];} else {return data[k] = f(update(a, b, x, 2 * k + 0, l, (l + r) >> 1),update(a, b, x, 2 * k + 1, (l + r) >> 1, r));}}Monoid update(int a, int b, const OperatorMonoid &x){return update(a, b, x, 1, 0, sz);}Monoid query(int a, int b, int k, int l, int r){propagate(k, r - l);if(r <= a || b <= l) {return M1;} else if(a <= l && r <= b) {return data[k];} else {return f(query(a, b, 2 * k + 0, l, (l + r) >> 1),query(a, b, 2 * k + 1, (l + r) >> 1, r));}}Monoid query(int a, int b){return query(a, b, 1, 0, sz);}Monoid operator[](const int &k){return query(k, k + 1);}};double dp[20010];int main() {cin.tie(0);ios::sync_with_stdio(false);cout << fixed << setprecision(15);ll H, A, D; cin >> H >> A >> D;for(int i=0; i<20010; i++){dp[i] = 100000.0;}dp[0] = 0.0;for(int i=0; i<20010; i++){if(i-A>=0){dp[i] = min(dp[i], dp[i-A]+1.0);}if(i-D>=0){dp[i] = min(dp[i], dp[i-D]+1.5);}}double ans = 100000.0;for(int i=H; i<=20000; i++){ans = min(ans, dp[i]);}cout << ans << endl;return 0;}