2017年09月23日普级组 看电影 Time Limit:10000MSMemory Limit:256000K Total Submit:23 Accepted:18 Case Time Limit:1000MS 【2017年09月23日普级组 看电影】Description 听说NOIP2016大家都考得不错,于是CCF奖励省常中了 K 张变形金刚5的电影票奖励OI队的同学去看电影。可是省常中OI队的同学们共有 N(N K)人。于是机智的你想到了一个公平公正的方法决定哪K人去看电影。 N个人排成一圈,按顺时针顺序标号为1 - N,每次随机一个还存活的人的编号,将这个人踢出。继续上述操作,直到剩下K个人。 但这样显然太无聊了,于是小S又想出一个牛逼的方法。 N个人排成一圈,按顺时针顺序标号为1 - N,每次随机一个1 - N的编号,假设随机到的编号是X,如果编号为X人还未踢出,则将这个人踢出,否则看编号为X % N + 1(即顺时针顺序下一个编号)的人是否存活,如果还未踢出则将他踢出,否则继续看编号(X + 1)% N + 1的人,如果已被踢出看顺时针的下一个…………,以此类推,直到踢出一个人为止。重复上述操作,直到剩下K个人。 已知小S的编号是Id,问按照小S的方法来他有多少的概率可以不被踢出,成功得到看电影的机会。 Input 第一行包括三个正整数,N,K,Id() Output 一行一个最简分数,表示小S可以看到电影的概率。 (如果概率为1或0,请输出1/1或0/1) Sample Input 2 1 2 Sample Output 1/2 Hint 一共两个人,筛选经过1轮,第1轮每个人被踢出的概率都是等概率的,所以答案是 1/2。 【数据规模】 所有测试数据范围和特点如下 Source |
var
n,k,d:longint;
procedure fi(a,b:longint);
begin
if a mod b=0 then begin d:=b; exit; end;
fi(b,a mod b);
end;
begin
assign(input,'movie.in'); reset(input);
assign(output,'movie.out'); rewrite(output);
read(n,k,d);
if k=0 then begin write('0/1'); close(input); close(output); halt; end;
fi(n,k);
n:=n div d;
k:=k div d;
write(k,'/',n);
close(input);
close(output);
end.
推荐阅读
- 练习|vue+element实现手机号验证码注册
- Python|python:while打印正三角形
- 牛客练习赛25 因数个数和
- Python|Python练习实例——星号三角形
- python输出棱形及对称三角
- 2.任何一个自然数m的立方均可写成m个连续奇数之和
- 练习|如何对解压缩版的Tomcat进行启动
- Java多线程练习(三个线程顺序打印A,B,C)