P10098: 俄罗斯轮盘赌

传统题
2.000s 时间限制
256MB 内存限制
6 提交
1 解决
【题目描述】
【题目描述】
在我们都知道的奥兰多事件之后，萨沙和罗马决定找出谁仍然是球队最大的输家。谢天谢地，玛莎在某个地方找到了一把左轮手枪，它有一个由n个弹孔组成的旋转圆筒，可以装下k颗子弹，现在男孩们有机会一劳永逸地解决这个问题了。
萨沙从n个弹孔选择任意k个，并在那里放置子弹。罗马旋转圆筒，使得n个可能的圆柱体中的每一个位移都是等概率的。然后游戏开始，玩家轮流上场，萨沙开始:他把枪对准自己的头射击。如果扳机前没有子弹，枪筒就会移动一个位置，武器就会交给罗马来做同样的动作。游戏继续，直到有人被击中，幸存者就是赢家。
萨沙不想输，所以他必须为子弹选择空位，这样才能最大限度地减少自己的损失。在所有可能的变体中，他想选择字典上最小的变体，其中空槽在字典上小于带电槽。
更准确地说，能够容纳k个子弹的n个子弹孔的圆柱体可以表示为n个字符的字符串。其中恰好有k个是“X”(带电插槽)，其他的是“.”(不带电插槽)。
让我们来描述一下射击的过程。假设触发器位于字符串的第一个字符(第一个槽)的前面。如果一射击没有杀死任何人，并且圆筒移动了，那么弹孔就会向左移动。所以第一个字符变成最后一个，第二个字符变成第一个，以此类推。但是扳机不会动。它将位于结果字符串的第一个字符的前面。
在所有给出最小损失概率的字符串中，萨沙选择了字典上最小的一个。根据这个条件，他给枪填上了子弹。你得帮萨沙给枪上弹。为此，必须回答位置xi中是否有一个子弹?
【输入】
第一行包含3个整数n、k、p(1≤n≤1018,0≤k≤n,1≤p≤1000)，分别表示圆柱槽数、子弹数和查询次数。然后p行每行包含一个整数xi(1≤xi≤n)的弹槽位号。
请不要使用%lld说明符在c++中读写64位数字。最好使用cin、cout流或%I64d说明符。
【输出】
对于每个查询，如果弹槽为空，则输出“.”，如果弹槽有子弹，则输出“X”。
【输入样例1】
3 1 3
1
2
3
【输出样例1】
X . .
【输入样例2】
6 3 6
1
2
3.
4
5
6
【输出样例2】
.X.X.X
【输入样例3】
5 2 5
1
2
3.
4
5
【输出样例3】
XX…
【请注意】
字典顺序比较在现代编程语言中由<操作符执行。如果存在这样的i(1≤i≤n)，则a字符串在字典序上小于b字符串，并且对于任意j(1≤j<i)， aj=bj。

【样例输入】复制
	

	

	
【样例输出】 复制
	

	
【提示】

	

		After all the events in Orlando we all know, Sasha and Roma decided to find out who is still the team's biggest loser. Thankfully, Masha found somewhere a revolver with a rotating cylinder of n bullet slots able to contain exactly k bullets, now the boys have a chance to resolve the problem once and for all.
	





	
		Sasha selects any k out of n slots he wishes and puts bullets there. Roma spins the cylinder so that every of n possible cylinder's shifts is equiprobable. Then the game starts, the players take turns, Sasha starts: he puts the gun to his head and shoots. If there was no bullet in front of the trigger, the cylinder shifts by one position and the weapon is given to Roma for make the same move. The game continues until someone is shot, the survivor is the winner.
	

	
		Sasha does not want to lose, so he must choose slots for bullets in such a way as to minimize the probability of its own loss. Of all the possible variant he wants to select the lexicographically minimal one, where an empty slot is lexicographically less than a charged one.
	

	
		More formally, the cylinder of n bullet slots able to contain k bullets can be represented as a string of n characters. Exactly k of them are "X" (charged slots) and the others are "." (uncharged slots).
	

	
		Let us describe the process of a shot. Suppose that the trigger is in front of the first character of the string (the first slot). If a shot doesn't kill anyone and the cylinder shifts, then the string shifts left. So the first character becomes the last one, the second character becomes the first one, and so on. But the trigger doesn't move. It will be in front of the first character of the resulting string.
	

	
		Among all the strings that give the minimal probability of loss, Sasha choose the lexicographically minimal one. According to this very string, he charges the gun. You have to help Sasha to charge the gun. For that, each xi query must be answered: is there a bullet in the positions xi?
	





	

		Input
	

	
		The first line contains three integers n, k and p (1≤n≤1018,0≤k≤n,1≤p≤1000) − the number of slots in the cylinder, the number of bullets and the number of queries. Then follow p lines; they are the queries. Each line contains one integer xi (1≤xi≤n) the number of slot to describe.
	

	
		Please do not use the %lld specificator to read or write 64-bit numbers in C++. It is preferred to use cin, cout streams or the %I64d specificator.
	





	

		Output
	

	
		For each query print "." if the slot should be empty and "X" if the slot should be charged.
	





	

		Examples
	

	

		

			

				Input
			


3 1 3
1
2
3


		

		

			

				Output
			


..X

		

		

			

				Input
			


6 3 6
1
2
3
4
5
6


		

		

			

				Output
			


.X.X.X

		

		

			

				Input
			


5 2 5
1
2
3
4
5


		

		

			

				Output
			


...XX

		

	





	

		Note
	

	
		The lexicographical comparison of is performed by the < operator in modern programming languages. The a string is lexicographically less that the b string, if there exists such i (1≤i≤n), that ai<bi, and for any j (1≤j<i) aj=bj.
	


	    









	

	
题目类型~

	 	










咻咻~

提交答案
状态