QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#726227 | #6423. Fireworks | maspy | TL | 177ms | 4136kb | C++23 | 13.6kb | 2024-11-08 22:27:11 | 2024-11-08 22:27:12 |
Judging History
answer
#line 1 "/home/maspy/compro/library/my_template.hpp"
#if defined(LOCAL)
#include <my_template_compiled.hpp>
#else
// https://codeforces.com/blog/entry/96344
#pragma GCC optimize("Ofast,unroll-loops")
// いまの CF だとこれ入れると動かない?
// #pragma GCC target("avx2,popcnt")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using u8 = uint8_t;
using u16 = uint16_t;
using u32 = uint32_t;
using u64 = uint64_t;
using i128 = __int128;
using u128 = unsigned __int128;
using f128 = __float128;
template <class T>
constexpr T infty = 0;
template <>
constexpr int infty<int> = 1'010'000'000;
template <>
constexpr ll infty<ll> = 2'020'000'000'000'000'000;
template <>
constexpr u32 infty<u32> = infty<int>;
template <>
constexpr u64 infty<u64> = infty<ll>;
template <>
constexpr i128 infty<i128> = i128(infty<ll>) * 2'000'000'000'000'000'000;
template <>
constexpr double infty<double> = infty<ll>;
template <>
constexpr long double infty<long double> = infty<ll>;
using pi = pair<ll, ll>;
using vi = vector<ll>;
template <class T>
using vc = vector<T>;
template <class T>
using vvc = vector<vc<T>>;
template <class T>
using vvvc = vector<vvc<T>>;
template <class T>
using vvvvc = vector<vvvc<T>>;
template <class T>
using vvvvvc = vector<vvvvc<T>>;
template <class T>
using pq = priority_queue<T>;
template <class T>
using pqg = priority_queue<T, vector<T>, greater<T>>;
#define vv(type, name, h, ...) vector<vector<type>> name(h, vector<type>(__VA_ARGS__))
#define vvv(type, name, h, w, ...) vector<vector<vector<type>>> name(h, vector<vector<type>>(w, vector<type>(__VA_ARGS__)))
#define vvvv(type, name, a, b, c, ...) \
vector<vector<vector<vector<type>>>> name(a, vector<vector<vector<type>>>(b, vector<vector<type>>(c, vector<type>(__VA_ARGS__))))
// https://trap.jp/post/1224/
#define FOR1(a) for (ll _ = 0; _ < ll(a); ++_)
#define FOR2(i, a) for (ll i = 0; i < ll(a); ++i)
#define FOR3(i, a, b) for (ll i = a; i < ll(b); ++i)
#define FOR4(i, a, b, c) for (ll i = a; i < ll(b); i += (c))
#define FOR1_R(a) for (ll i = (a)-1; i >= ll(0); --i)
#define FOR2_R(i, a) for (ll i = (a)-1; i >= ll(0); --i)
#define FOR3_R(i, a, b) for (ll i = (b)-1; i >= ll(a); --i)
#define overload4(a, b, c, d, e, ...) e
#define overload3(a, b, c, d, ...) d
#define FOR(...) overload4(__VA_ARGS__, FOR4, FOR3, FOR2, FOR1)(__VA_ARGS__)
#define FOR_R(...) overload3(__VA_ARGS__, FOR3_R, FOR2_R, FOR1_R)(__VA_ARGS__)
#define FOR_subset(t, s) for (ll t = (s); t >= 0; t = (t == 0 ? -1 : (t - 1) & (s)))
#define all(x) x.begin(), x.end()
#define len(x) ll(x.size())
#define elif else if
#define eb emplace_back
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define stoi stoll
int popcnt(int x) { return __builtin_popcount(x); }
int popcnt(u32 x) { return __builtin_popcount(x); }
int popcnt(ll x) { return __builtin_popcountll(x); }
int popcnt(u64 x) { return __builtin_popcountll(x); }
int popcnt_sgn(int x) { return (__builtin_parity(x) & 1 ? -1 : 1); }
int popcnt_sgn(u32 x) { return (__builtin_parity(x) & 1 ? -1 : 1); }
int popcnt_sgn(ll x) { return (__builtin_parity(x) & 1 ? -1 : 1); }
int popcnt_sgn(u64 x) { return (__builtin_parity(x) & 1 ? -1 : 1); }
// (0, 1, 2, 3, 4) -> (-1, 0, 1, 1, 2)
int topbit(int x) { return (x == 0 ? -1 : 31 - __builtin_clz(x)); }
int topbit(u32 x) { return (x == 0 ? -1 : 31 - __builtin_clz(x)); }
int topbit(ll x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); }
int topbit(u64 x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); }
// (0, 1, 2, 3, 4) -> (-1, 0, 1, 0, 2)
int lowbit(int x) { return (x == 0 ? -1 : __builtin_ctz(x)); }
int lowbit(u32 x) { return (x == 0 ? -1 : __builtin_ctz(x)); }
int lowbit(ll x) { return (x == 0 ? -1 : __builtin_ctzll(x)); }
int lowbit(u64 x) { return (x == 0 ? -1 : __builtin_ctzll(x)); }
template <typename T>
T floor(T a, T b) {
return a / b - (a % b && (a ^ b) < 0);
}
template <typename T>
T ceil(T x, T y) {
return floor(x + y - 1, y);
}
template <typename T>
T bmod(T x, T y) {
return x - y * floor(x, y);
}
template <typename T>
pair<T, T> divmod(T x, T y) {
T q = floor(x, y);
return {q, x - q * y};
}
template <typename T, typename U>
T SUM(const vector<U> &A) {
T sm = 0;
for (auto &&a: A) sm += a;
return sm;
}
#define MIN(v) *min_element(all(v))
#define MAX(v) *max_element(all(v))
#define LB(c, x) distance((c).begin(), lower_bound(all(c), (x)))
#define UB(c, x) distance((c).begin(), upper_bound(all(c), (x)))
#define UNIQUE(x) sort(all(x)), x.erase(unique(all(x)), x.end()), x.shrink_to_fit()
template <typename T>
T POP(deque<T> &que) {
T a = que.front();
que.pop_front();
return a;
}
template <typename T>
T POP(pq<T> &que) {
T a = que.top();
que.pop();
return a;
}
template <typename T>
T POP(pqg<T> &que) {
T a = que.top();
que.pop();
return a;
}
template <typename T>
T POP(vc<T> &que) {
T a = que.back();
que.pop_back();
return a;
}
template <typename F>
ll binary_search(F check, ll ok, ll ng, bool check_ok = true) {
if (check_ok) assert(check(ok));
while (abs(ok - ng) > 1) {
auto x = (ng + ok) / 2;
(check(x) ? ok : ng) = x;
}
return ok;
}
template <typename F>
double binary_search_real(F check, double ok, double ng, int iter = 100) {
FOR(iter) {
double x = (ok + ng) / 2;
(check(x) ? ok : ng) = x;
}
return (ok + ng) / 2;
}
template <class T, class S>
inline bool chmax(T &a, const S &b) {
return (a < b ? a = b, 1 : 0);
}
template <class T, class S>
inline bool chmin(T &a, const S &b) {
return (a > b ? a = b, 1 : 0);
}
// ? は -1
vc<int> s_to_vi(const string &S, char first_char) {
vc<int> A(S.size());
FOR(i, S.size()) { A[i] = (S[i] != '?' ? S[i] - first_char : -1); }
return A;
}
template <typename T, typename U>
vector<T> cumsum(vector<U> &A, int off = 1) {
int N = A.size();
vector<T> B(N + 1);
FOR(i, N) { B[i + 1] = B[i] + A[i]; }
if (off == 0) B.erase(B.begin());
return B;
}
// stable sort
template <typename T>
vector<int> argsort(const vector<T> &A) {
vector<int> ids(len(A));
iota(all(ids), 0);
sort(all(ids), [&](int i, int j) { return (A[i] == A[j] ? i < j : A[i] < A[j]); });
return ids;
}
// A[I[0]], A[I[1]], ...
template <typename T>
vc<T> rearrange(const vc<T> &A, const vc<int> &I) {
vc<T> B(len(I));
FOR(i, len(I)) B[i] = A[I[i]];
return B;
}
template <typename T, typename... Vectors>
void concat(vc<T> &first, const Vectors &... others) {
vc<T> &res = first;
(res.insert(res.end(), others.begin(), others.end()), ...);
}
#endif
#line 1 "/home/maspy/compro/library/other/io.hpp"
#define FASTIO
#include <unistd.h>
// https://judge.yosupo.jp/submission/21623
namespace fastio {
static constexpr uint32_t SZ = 1 << 17;
char ibuf[SZ];
char obuf[SZ];
char out[100];
// pointer of ibuf, obuf
uint32_t pil = 0, pir = 0, por = 0;
struct Pre {
char num[10000][4];
constexpr Pre() : num() {
for (int i = 0; i < 10000; i++) {
int n = i;
for (int j = 3; j >= 0; j--) {
num[i][j] = n % 10 | '0';
n /= 10;
}
}
}
} constexpr pre;
inline void load() {
memcpy(ibuf, ibuf + pil, pir - pil);
pir = pir - pil + fread(ibuf + pir - pil, 1, SZ - pir + pil, stdin);
pil = 0;
if (pir < SZ) ibuf[pir++] = '\n';
}
inline void flush() {
fwrite(obuf, 1, por, stdout);
por = 0;
}
void rd(char &c) {
do {
if (pil + 1 > pir) load();
c = ibuf[pil++];
} while (isspace(c));
}
void rd(string &x) {
x.clear();
char c;
do {
if (pil + 1 > pir) load();
c = ibuf[pil++];
} while (isspace(c));
do {
x += c;
if (pil == pir) load();
c = ibuf[pil++];
} while (!isspace(c));
}
template <typename T>
void rd_real(T &x) {
string s;
rd(s);
x = stod(s);
}
template <typename T>
void rd_integer(T &x) {
if (pil + 100 > pir) load();
char c;
do
c = ibuf[pil++];
while (c < '-');
bool minus = 0;
if constexpr (is_signed<T>::value || is_same_v<T, i128>) {
if (c == '-') { minus = 1, c = ibuf[pil++]; }
}
x = 0;
while ('0' <= c) { x = x * 10 + (c & 15), c = ibuf[pil++]; }
if constexpr (is_signed<T>::value || is_same_v<T, i128>) {
if (minus) x = -x;
}
}
void rd(int &x) { rd_integer(x); }
void rd(ll &x) { rd_integer(x); }
void rd(i128 &x) { rd_integer(x); }
void rd(u32 &x) { rd_integer(x); }
void rd(u64 &x) { rd_integer(x); }
void rd(u128 &x) { rd_integer(x); }
void rd(double &x) { rd_real(x); }
void rd(long double &x) { rd_real(x); }
void rd(f128 &x) { rd_real(x); }
template <class T, class U>
void rd(pair<T, U> &p) {
return rd(p.first), rd(p.second);
}
template <size_t N = 0, typename T>
void rd_tuple(T &t) {
if constexpr (N < std::tuple_size<T>::value) {
auto &x = std::get<N>(t);
rd(x);
rd_tuple<N + 1>(t);
}
}
template <class... T>
void rd(tuple<T...> &tpl) {
rd_tuple(tpl);
}
template <size_t N = 0, typename T>
void rd(array<T, N> &x) {
for (auto &d: x) rd(d);
}
template <class T>
void rd(vc<T> &x) {
for (auto &d: x) rd(d);
}
void read() {}
template <class H, class... T>
void read(H &h, T &... t) {
rd(h), read(t...);
}
void wt(const char c) {
if (por == SZ) flush();
obuf[por++] = c;
}
void wt(const string s) {
for (char c: s) wt(c);
}
void wt(const char *s) {
size_t len = strlen(s);
for (size_t i = 0; i < len; i++) wt(s[i]);
}
template <typename T>
void wt_integer(T x) {
if (por > SZ - 100) flush();
if (x < 0) { obuf[por++] = '-', x = -x; }
int outi;
for (outi = 96; x >= 10000; outi -= 4) {
memcpy(out + outi, pre.num[x % 10000], 4);
x /= 10000;
}
if (x >= 1000) {
memcpy(obuf + por, pre.num[x], 4);
por += 4;
} else if (x >= 100) {
memcpy(obuf + por, pre.num[x] + 1, 3);
por += 3;
} else if (x >= 10) {
int q = (x * 103) >> 10;
obuf[por] = q | '0';
obuf[por + 1] = (x - q * 10) | '0';
por += 2;
} else
obuf[por++] = x | '0';
memcpy(obuf + por, out + outi + 4, 96 - outi);
por += 96 - outi;
}
template <typename T>
void wt_real(T x) {
ostringstream oss;
oss << fixed << setprecision(15) << double(x);
string s = oss.str();
wt(s);
}
void wt(int x) { wt_integer(x); }
void wt(ll x) { wt_integer(x); }
void wt(i128 x) { wt_integer(x); }
void wt(u32 x) { wt_integer(x); }
void wt(u64 x) { wt_integer(x); }
void wt(u128 x) { wt_integer(x); }
void wt(double x) { wt_real(x); }
void wt(long double x) { wt_real(x); }
void wt(f128 x) { wt_real(x); }
template <class T, class U>
void wt(const pair<T, U> val) {
wt(val.first);
wt(' ');
wt(val.second);
}
template <size_t N = 0, typename T>
void wt_tuple(const T t) {
if constexpr (N < std::tuple_size<T>::value) {
if constexpr (N > 0) { wt(' '); }
const auto x = std::get<N>(t);
wt(x);
wt_tuple<N + 1>(t);
}
}
template <class... T>
void wt(tuple<T...> tpl) {
wt_tuple(tpl);
}
template <class T, size_t S>
void wt(const array<T, S> val) {
auto n = val.size();
for (size_t i = 0; i < n; i++) {
if (i) wt(' ');
wt(val[i]);
}
}
template <class T>
void wt(const vector<T> val) {
auto n = val.size();
for (size_t i = 0; i < n; i++) {
if (i) wt(' ');
wt(val[i]);
}
}
void print() { wt('\n'); }
template <class Head, class... Tail>
void print(Head &&head, Tail &&... tail) {
wt(head);
if (sizeof...(Tail)) wt(' ');
print(forward<Tail>(tail)...);
}
// gcc expansion. called automaticall after main.
void __attribute__((destructor)) _d() { flush(); }
} // namespace fastio
using fastio::read;
using fastio::print;
using fastio::flush;
#if defined(LOCAL)
#define SHOW(...) SHOW_IMPL(__VA_ARGS__, SHOW6, SHOW5, SHOW4, SHOW3, SHOW2, SHOW1)(__VA_ARGS__)
#define SHOW_IMPL(_1, _2, _3, _4, _5, _6, NAME, ...) NAME
#define SHOW1(x) print(#x, "=", (x)), flush()
#define SHOW2(x, y) print(#x, "=", (x), #y, "=", (y)), flush()
#define SHOW3(x, y, z) print(#x, "=", (x), #y, "=", (y), #z, "=", (z)), flush()
#define SHOW4(x, y, z, w) print(#x, "=", (x), #y, "=", (y), #z, "=", (z), #w, "=", (w)), flush()
#define SHOW5(x, y, z, w, v) print(#x, "=", (x), #y, "=", (y), #z, "=", (z), #w, "=", (w), #v, "=", (v)), flush()
#define SHOW6(x, y, z, w, v, u) print(#x, "=", (x), #y, "=", (y), #z, "=", (z), #w, "=", (w), #v, "=", (v), #u, "=", (u)), flush()
#else
#define SHOW(...)
#endif
#define INT(...) \
int __VA_ARGS__; \
read(__VA_ARGS__)
#define LL(...) \
ll __VA_ARGS__; \
read(__VA_ARGS__)
#define U32(...) \
u32 __VA_ARGS__; \
read(__VA_ARGS__)
#define U64(...) \
u64 __VA_ARGS__; \
read(__VA_ARGS__)
#define STR(...) \
string __VA_ARGS__; \
read(__VA_ARGS__)
#define CHAR(...) \
char __VA_ARGS__; \
read(__VA_ARGS__)
#define DBL(...) \
double __VA_ARGS__; \
read(__VA_ARGS__)
#define VEC(type, name, size) \
vector<type> name(size); \
read(name)
#define VV(type, name, h, w) \
vector<vector<type>> name(h, vector<type>(w)); \
read(name)
void YES(bool t = 1) { print(t ? "YES" : "NO"); }
void NO(bool t = 1) { YES(!t); }
void Yes(bool t = 1) { print(t ? "Yes" : "No"); }
void No(bool t = 1) { Yes(!t); }
void yes(bool t = 1) { print(t ? "yes" : "no"); }
void no(bool t = 1) { yes(!t); }
#line 3 "main.cpp"
using Re = long double;
void solve() {
LL(N, M, P);
Re p = P / 10000.0;
Re ANS = infty<Re>;
Re pw = 1.0;
FOR(k, 1, 100000) {
pw *= 1 - p;
chmin(ANS, (N * k + M) / (1 - pw));
}
print(ANS);
}
signed main() {
INT(T);
FOR(T) solve();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3792kb
input:
3 1 1 5000 1 1 1 1 2 10000
output:
4.000000000000000 10141.585289113576437 3.000000000000000
result:
ok 3 numbers
Test #2:
score: 0
Accepted
time: 177ms
memory: 3832kb
input:
20 10 27 2855 79 59 6888 65 72 7725 78 50 2888 31 21 5759 41 58 6619 47 27 3881 35 55 5095 77 7 6028 17 89 1792 84 60 8604 58 44 4923 88 27 3824 54 63 1482 19 42 5366 93 76 97 100 99 8660 96 36 4343 90 56 9515 24 44 9922
output:
89.729805650548002 200.348432055749100 177.346278317152098 416.839877800354600 90.293453724604959 149.569421362743611 190.672507085802636 164.601521115576929 139.349701393497014 275.133110248423009 167.364016736401652 207.190737355271182 300.732217573221760 589.058848950519405 101.877028212448849 10...
result:
ok 20 numbers
Test #3:
score: 0
Accepted
time: 3ms
memory: 4124kb
input:
10 954269343 987322500 9806 916720797 981711601 9728 902477101 957414437 9250 967013471 988735825 9674 985383693 926528961 9411 970653208 917703218 9331 998423148 911924940 9283 986159007 902133513 9759 953796828 947934512 9959 995334734 931874197 9944
output:
1980003919.029165744781494 1951513567.023026227951050 2010693554.594594478607178 2021655257.390944719314575 2031572260.121134757995605 2023744964.098167419433594 2057899480.771302461624146 1934924193.052566766738892 1909560538.206647157669067 1938062078.640386104583740
result:
ok 10 numbers
Test #4:
score: 0
Accepted
time: 3ms
memory: 3824kb
input:
10 933722894 72 9673 975866948 5 9424 910984544 95 9682 994597175 6 9351 972675086 51 9712 952759975 51 9114 956482031 85 9478 921988922 72 9017 950640658 36 9893 965297247 78 9342
output:
965287879.665046930313110 1035512471.349745273590088 940905431.728981614112854 1063626543.685167312622070 1001518880.766062498092651 1045380761.465876579284668 1009160282.760075926780701 1022500825.108129024505615 960922565.450318336486816 1033287652.536929965019226
result:
ok 10 numbers
Test #5:
score: 0
Accepted
time: 3ms
memory: 4032kb
input:
10 910088095 81 316 970640211 35 537 908853334 41 89 932269507 8 457 953224740 22 113 959834859 69 34 924852390 63 115 952730384 97 382 917634328 91 20 937287266 32 654
output:
28800258734.177211761474609 18075237355.679698944091797 102118356741.573028564453125 20399770568.927787780761719 84356173628.318572998046875 282304390588.235290527343750 80421952434.782608032226562 24940588507.853401184082031 458817209500.000000000000000 14331610061.162078857421875
result:
ok 10 numbers
Test #6:
score: 0
Accepted
time: 3ms
memory: 3988kb
input:
10 968675373 962412132 104 923494255 934310785 381 922721350 957856460 282 978335370 917228676 825 951116860 942542480 359 999013758 972493824 676 930242700 964474169 342 968944030 984608304 520 965837594 909045242 369 990484700 925952624 479
output:
106669104052.294281005859375 31076848077.761108398437500 40771434362.895141601562500 16579259543.363533020019531 33660076568.701946258544922 20209258011.501918792724609 34581380127.395103454589844 24798113234.332958221435547 33145494087.728286743164062 26925682159.120101928710938
result:
ok 10 numbers
Test #7:
score: 0
Accepted
time: 1ms
memory: 4136kb
input:
10 22 972733171 975 22 973609752 512 55 987399854 126 49 967364929 642 23 948126474 513 25 962813818 421 93 933323422 113 58 950364131 647 82 991906690 682 31 957667404 402
output:
972736672.681293487548828 973616306.986935973167419 987457697.396779298782349 967376069.315485358238220 948133283.101613879203796 962822722.647579073905945 933426898.317728161811829 950377057.363343119621277 991923706.585391640663147 957678776.965345382690430
result:
ok 10 numbers
Test #8:
score: 0
Accepted
time: 3ms
memory: 3988kb
input:
10 47 972371220 9743 65 949941115 9400 86 921812690 9736 11 927065494 9182 71 923766617 9378 63 941828720 9029 96 917539847 9084 88 952051332 9499 91 958386812 9427 64 950375055 9887
output:
972371465.901790261268616 949941549.320472955703735 921813131.821226119995117 927065583.858390092849731 923767096.493965983390808 941829231.442622780799866 917540568.647066354751587 952051875.055215239524841 958387391.921013832092285 950375326.495618939399719
result:
ok 10 numbers
Test #9:
score: 0
Accepted
time: 3ms
memory: 3832kb
input:
10 98 46 9403 99 89 9661 80 62 9450 25 20 9283 68 74 9328 54 14 9286 4 80 9574 35 61 9420 77 47 9943 22 9 9358
output:
153.142614059342748 194.596832626022149 150.264550264550252 48.475708283959925 152.229845626072034 73.228516045660129 87.737622728222263 101.910828025477699 124.710851855576777 33.126736482154307
result:
ok 10 numbers
Test #10:
score: 0
Accepted
time: 3ms
memory: 3924kb
input:
10 89 77 65 53 41 913 47 67 488 89 13 267 20 60 427 58 72 690 23 60 677 43 38 775 52 68 343 83 61 805
output:
15149.283838238592580 795.195959678696227 1340.262610317280632 3590.647504732402012 734.463107824569988 1204.044041798925264 568.432537046958487 761.453449761660181 1986.669558374136159 1378.158448339147753
result:
ok 10 numbers
Test #11:
score: 0
Accepted
time: 6ms
memory: 3996kb
input:
20 5 1000000000 4 3 999999979 5 5 1000000000 2 2 999999999 4 3 999999983 1 3 999999984 1 3 999999987 3 3 999999974 1 2 999999998 1 1 999999981 2 4 999999971 4 3 999999992 1 5 999999973 4 4 999999984 4 3 999999972 4 2 999999994 4 2 999999980 5 4 999999970 5 2 999999980 2 4 999999983 4
output:
1000153595.966846108436584 1000078103.937718987464905 1000289896.621388435363770 1000066017.486277937889099 1000345377.445976734161377 1000345378.446022152900696 1000125100.235101819038391 1000345368.445568323135376 1000245388.908319711685181 1000066005.589947700500488 1000125078.477628946304321 100...
result:
ok 20 numbers
Test #12:
score: -100
Time Limit Exceeded
input:
10000 15 999999991 6 16 999999975 2 12 999999978 9 7 999999993 4 19 999999980 5 20 999999977 5 13 999999995 10 11 999999979 6 19 999999995 5 6 999999982 10 15 999999978 1 2 999999974 5 12 999999980 4 18 999999997 1 12 999999992 10 20 999999970 6 2 999999999 2 13 999999984 1 16 999999984 2 16 9999999...