QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#470012#8008. Fortune WheelFffooooWA 107ms58700kbC++142.2kb2024-07-10 09:39:362024-07-10 09:39:36

Judging History

你现在查看的是最新测评结果

  • [2024-07-30 15:38:33]
  • hack成功,自动添加数据
  • (/hack/759)
  • [2024-07-10 09:39:36]
  • 评测
  • 测评结果:WA
  • 用时:107ms
  • 内存:58700kb
  • [2024-07-10 09:39:36]
  • 提交

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'