QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#94501 | #5253. Denormalization | maomao90# | AC ✓ | 609ms | 3916kb | C++17 | 2.1kb | 2023-04-06 14:38:39 | 2023-04-06 14:38:40 |
Judging History
answer
// Hallelujah, praise the one who set me free
// Hallelujah, death has lost its grip on me
// You have broken every chain, There's salvation in your name
// Jesus Christ, my living hope
#include <bits/stdc++.h>
using namespace std;
#define REP(i, s, e) for (int i = (s); i < (e); i++)
#define RREP(i, s, e) for (int i = (s); i >= (e); i--)
template <class T>
inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;}
typedef long long ll;
typedef long double ld;
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> iii;
#define ALL(_a) _a.begin(), _a.end()
#define SZ(_a) (int) _a.size()
#define pb push_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
typedef vector<iii> viii;
#ifndef DEBUG
#define cerr if (0) cerr
#endif
const int INF = 1000000005;
const ll LINF = 1000000000000000005ll;
const int MAXN = 10000;
int n;
ll x[MAXN];
int ans[MAXN];
int main() {
scanf("%d", &n);
ll mx = 0;
REP (i, 0, n) {
scanf(" 0.%lld", &x[i]);
mxto(mx, x[i]);
}
bool same = 1;
REP (i, 1, n) {
if (x[i] != x[i - 1]) {
same = 0;
}
}
if (same) {
REP (i, 0, n) {
printf("1\n");
}
return 0;
}
ld mn = LINF;
int ak = -1;
REP (i, 2, MAXN + 1) {
ld d = (ld) mx / i;
bool pos = 1;
ld error = 0;
REP (j, 0, n) {
ld tx = x[j] / d;
int nx = round(tx);
if (nx <= 0) {
pos = 0;
break;
}
error += abs(nx * d - x[j]);
}
if (!pos) {
continue;
}
if (mnto(mn, error)) {
ak = i;
}
}
ld d = (ld) mx / ak;
REP (j, 0, n) {
ld tx = x[j] / d;
ans[j] = round(tx);
}
int g = 0;
REP (j, 0, n) {
g = __gcd(g, ans[j]);
}
REP (j, 0, n) {
ans[j] /= g;
printf("%d\n", ans[j]);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3752kb
input:
2 0.909840249060 0.414958698174
output:
9665 4408
result:
ok good solution
Test #2:
score: 0
Accepted
time: 2ms
memory: 3568kb
input:
3 0.005731604132 0.696198848562 0.717826101486
output:
75 9110 9393
result:
ok good solution
Test #3:
score: 0
Accepted
time: 0ms
memory: 3588kb
input:
10 0.338936215010 0.390914583549 0.048893426174 0.446152513833 0.137891103101 0.017985796057 0.459132554353 0.201452557127 0.362800863500 0.358493585479
output:
5823 6716 840 7665 2369 309 7888 3461 6233 6159
result:
ok good solution
Test #4:
score: 0
Accepted
time: 8ms
memory: 3572kb
input:
100 0.027828573352 0.034289446708 0.021442608673 0.002752893865 0.091163859407 0.180717182268 0.012097751269 0.101332712254 0.087249881055 0.112643922419 0.016667180541 0.108449036530 0.050488448020 0.104216696303 0.120734059490 0.090096410766 0.066537631979 0.046668105514 0.174836851156 0.084908984...
output:
1486 1831 1145 147 4868 9650 646 5411 4659 6015 890 5791 2696 5565 6447 4811 3553 2492 9336 4534 5302 193 5082 58 1438 4729 3774 542 5876 1641 5574 1443 9374 7710 9570 1413 3054 396 2768 8066 1774 1546 9548 1546 8339 411 3862 3496 3418 8165 4760 7829 4709 8174 8816 4396 7811 8148 2957 1239 1857 4361...
result:
ok good solution
Test #5:
score: 0
Accepted
time: 516ms
memory: 3704kb
input:
10000 0.014153431495 0.006246805276 0.014846752535 0.008905976745 0.012146085543 0.003020528319 0.010107617948 0.005218062088 0.014054879627 0.009239669913 0.008637984822 0.013371932468 0.009493829995 0.005771335736 0.002264963994 0.010799210007 0.015999982294 0.014564928771 0.001206828144 0.0056243...
output:
8186 3613 8587 5151 7025 1747 5846 3018 8129 5344 4996 7734 5491 3338 1310 6246 9254 8424 698 3253 18 6747 6383 7580 1483 2171 4328 7368 2072 8229 3813 8743 9601 5375 9211 4221 6853 8470 8388 929 2604 4103 8579 2768 1138 3754 2139 7163 5876 525 8775 4406 7769 1654 3080 734 3950 4290 6828 4796 4006 4...
result:
ok good solution
Test #6:
score: 0
Accepted
time: 0ms
memory: 3672kb
input:
10000 0.010000000000 0.010000000000 0.010000000000 0.010000000000 0.010000000000 0.010000000000 0.010000000000 0.010000000000 0.010000000000 0.010000000000 0.010000000000 0.010000000000 0.010000000000 0.010000000000 0.010000000000 0.010000000000 0.010000000000 0.010000000000 0.010000000000 0.0100000...
output:
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
result:
ok good solution
Test #7:
score: 0
Accepted
time: 308ms
memory: 3916kb
input:
10000 0.000001731921 0.000003463842 0.000005195763 0.000006927684 0.000008659605 0.000010391525 0.000012123446 0.000013855367 0.000015587288 0.000017319209 0.000019051130 0.000020783051 0.000022514972 0.000024246893 0.000025978814 0.000027710735 0.000029442656 0.000031174576 0.000032906497 0.0000346...
output:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 ...
result:
ok good solution
Test #8:
score: 0
Accepted
time: 2ms
memory: 3600kb
input:
2 0.447213595500 0.894427191000
output:
1 2
result:
ok good solution
Test #9:
score: 0
Accepted
time: 2ms
memory: 3788kb
input:
2 0.707142137409 0.707071423196
output:
10000 9999
result:
ok good solution
Test #10:
score: 0
Accepted
time: 2ms
memory: 3592kb
input:
2 0.000100000000 0.999999995000
output:
1 10000
result:
ok good solution
Test #11:
score: 0
Accepted
time: 306ms
memory: 3672kb
input:
10000 0.000001000050 0.010000500037 0.010000500037 0.010000500037 0.010000500037 0.010000500037 0.010000500037 0.010000500037 0.010000500037 0.010000500037 0.010000500037 0.010000500037 0.010000500037 0.010000500037 0.010000500037 0.010000500037 0.010000500037 0.010000500037 0.010000500037 0.0100005...
output:
1 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 1000...
result:
ok good solution
Test #12:
score: 0
Accepted
time: 609ms
memory: 3740kb
input:
10000 0.009999000100 0.010000000100 0.010000000100 0.010000000100 0.010000000100 0.010000000100 0.010000000100 0.010000000100 0.010000000100 0.010000000100 0.010000000100 0.010000000100 0.010000000100 0.010000000100 0.010000000100 0.010000000100 0.010000000100 0.010000000100 0.010000000100 0.0100000...
output:
9999 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 1...
result:
ok good solution