QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#470012 | #8008. Fortune Wheel | Fffoooo | WA | 107ms | 58700kb | C++14 | 2.2kb | 2024-07-10 09:39:36 | 2024-07-10 09:39:36 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int mian(); int main() { return mian(); }
/*
有一个长为 $n$ 的环,给定 $k_i$,每个点可以从 $i\to i+k_i\mod n$ 。也可以随机一个 $[0,n)$ 的值并到达此地方
求最优策略下到达点 $0$ 的期望步数
$m\le10^5, K\le 500$
$time:1s$,$memory:512MB$
先得到最优策略。那么一定是先随机后走路径。因为一次随机可以直接使得之前走的路径全部报废(对于每个点都是公平随机)
那么一定是随机到某个位置优秀人后停止。对于走步数,那么优秀的标准就应该是最短路
于是先预处理出每个点到目标节点的最短路。对于优秀的标准,枚举标准值 $x$。假设有 $i$ 个值的 $dis\le x$
那么每一次跳到这些点的概率为 $\dfrac{i}{n}$,又因为每一次的概率相同,所以期望的步数就是 $\dfrac{n}{i}$
因为并没有规定跳到的是哪一个点,所以这 $i$ 个点都有可能且相等。于是之后的期望就是 $\sum \dfrac{1}{i}dis_j$
把所有的值全部求出后取最小值即可
*/
#define ll long long
const int N = 1e5 + 15, K = 555;
const ll inf = 1e13;
int n, X, m;
vector<int> eg[N];
void add(const int u, const int v) { eg[u].push_back(v); }
struct frac {
ll fi, se;
frac(ll x = 0, ll y = 1) { const ll gcd = __gcd(x, y); fi = x / gcd; se = y / gcd; }
friend bool operator < (const frac a, const frac b) {
return a.fi * b.se < a.se * b.fi;
}
}ans;
int dis[N];
void MSP() {
memset(dis, -1, sizeof dis);
queue<int> q;
q.push(0); dis[0] = 0;
while(!q.empty()) {
const int u = q.front(); q.pop();
for(auto v : eg[u]) {
if(dis[v] != -1) continue;
dis[v] = dis[u] + 1;
q.push(v);
}
}
}
int mian() {
scanf("%d%d%d", &n, &X, &m);
for(int i = 1, ki; i <= m; ++i) {
scanf("%d", &ki);
for(int j = 0; j < n; ++j) add( (j + ki) % n, j );
}
MSP();
for(int i = 0; i < n; i++) {
if(dis[i] == -1)dis[i] = 1e9;
}
frac ans(dis[X], 1);
sort(dis, dis + n);
ll sum = 0;
for(int x = 0, i = 0; x <= n; ++x) {
while(i<n && dis[i] <= x) sum += dis[i], i++;
i--;
frac ant(n + sum, i + 1);
ans = min( ans, ant );
}
printf("%lld %lld", ans.fi, ans.se);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 6500kb
input:
6 3 2 2 4
output:
8 3
result:
ok 2 number(s): "8 3"
Test #2:
score: 0
Accepted
time: 1ms
memory: 6588kb
input:
5 4 1 1
output:
1 1
result:
ok 2 number(s): "1 1"
Test #3:
score: 0
Accepted
time: 107ms
memory: 58700kb
input:
99999 65238 100 64714 45675 36156 13116 93455 22785 10977 60219 14981 25839 83709 80404 41400 12469 31530 65521 35436 20326 96792 50699 27522 98233 26187 12509 90992 72693 83919 74145 80892 68422 38333 33497 89154 88403 77492 4570 3908 59194 3482 89871 96330 45114 5555 73987 95832 476 949 74649 2084...
output:
3 1
result:
ok 2 number(s): "3 1"
Test #4:
score: -100
Wrong Answer
time: 0ms
memory: 7104kb
input:
10000 23 7 9594 8998 9330 6851 1662 6719 583
output:
42754 4805
result:
wrong answer 1st numbers differ - expected: '42726', found: '42754'