没有合适的资源?快使用搜索试试~ 我知道了~
温馨提示
试读
16页
2017 CCPC Final Contest Onsite Round, Sunday, December 3rd, 2017 Problem A. Dogs and Cages Jerry likes dogs. He has N dogs numbered 0, 1, . . . , N − 1. He also has N cages numbered 0, 1, . . . , N − 1. Everyday he takes all his dogs out and walks them outside. When he is back home, as dogs can’t recognize the numbers, each dog just randomly selects a cage and enters it. Each cage can hold only one dog. One day, Jerry noticed that some dogs were in the cage with the same number of themselves while others were not. Jerry would like to know what’s the expected number of dogs that are NOT in the cage with the same number of themselves.
资源推荐
资源详情
资源评论
2017 CCPC Final Contest
Onsite Round, Sunday, December 3rd, 2017
Problem A. Dogs and Cages
Jerry likes dogs. He has N dogs numbered 0, 1, . . . , N −1. He also has N cages numbered 0, 1, . . . , N −1.
Everyday he takes all his dogs out and walks them outside. When he is back home, as dogs can’t recognize
the numbers, each dog just randomly selects a cage and enters it. Each cage can hold only one dog.
One day, Jerry noticed that some dogs were in the cage with the same number of themselves while others
were not. Jerry would like to know what’s the expected number of dogs that are NOT in the cage with
the same number of themselves.
Input
The first line of the input gives the number of test cases, T . T test cases follow.
Each test case contains only one number N, indicating the number of dogs and cages.
Output
For each test case, output one line containing “Case #x: y”, where x is the test case number (starting
from 1) and y is the expected number of dogs that are NOT in the cage with the same number of itself.
y will be considered correct if it is within an absolute or relative error of 10
−6
of the correct answer.
Limits
• 1 ≤ T ≤ 10
5
.
• 1 ≤ N ≤ 10
5
.
Example
standard input standard output
2
1
2
Case #1: 0.0000000000
Case #2: 1.0000000000
Note
In the first test case, the only dog will enter the only cage. So the answer is 0.
In the second test case, if the first dog enters the cage of the same number, both dogs are in the cage of
the same number, the number of mismatch is 0. If both dogs are not in the cage with the same number
of itself, the number of mismatch is 2. So the expected number is
0+2
2
= 1.
Page 1 of 16
2017 CCPC Final Contest
Onsite Round, Sunday, December 3rd, 2017
Problem B. Same Digit
Little Mono is a smart child, he can do complex arithmetical operations quickly. But he only knows one
digit D(1 ≤ D ≤ 9). He would like to use the only digit he knows to make expressions to represent integer
numbers.
A valid expression can be generated like this:
1. Any number consists of only digit D are valid expressions. E.g. if D = 1, then 1, 11, 111, ... are all
valid expressions.
2. If A and B are valid expressions, then (A) + (B) is a valid expression.
3. If A and B are valid expressions, then (A) − (B) is a valid expression.
4. If A and B are valid expressions, then (A) ∗ (B) is a valid expression.
5. If A and B are valid expressions, then (A)/(B) is a valid expression. (/ here produces exact value,
not integer division)
6. If A and B are valid expressions, then (A)
(B)
is a valid expression.
7. If A is valid expression, then
p
(A) is a valid expression.
8. If A is valid expression, then (A)! is a valid expression.(! here means factorial, and expression A
must produce a non-negative integer)
Now Little Mono would like to know the minimal number of Ds he needs to use in order to represent
integer N .
Input
The first line of the input gives the number of test cases, T . T test cases follow.
Each test case contains one line consists of 2 integers D, N, indicating the digit Little Mono knows and
the integer Little Mono would like to represent.
Output
For each test case, output one line containing “Case #x: y”, where x is the test case number (starting
from 1) and y is the minimal number of Ds Little Mono has to use.
Limits
• 1 ≤ T ≤ 100.
• 1 ≤ D ≤ 9.
• 1 ≤ N ≤ 2000.
Example
standard input standard output
3
1 10
4 64
5 1252
Case #1: 3
Case #2: 2
Case #3: 6
Page 2 of 16
2017 CCPC Final Contest
Onsite Round, Sunday, December 3rd, 2017
Note
In the first test case, Little Mono can use 3 1s as 11 − 1 to represent 10.
In the second test case, Little Mono can use 2 4s as
q
p
√
4
(4!)
to represent 64.
Page 3 of 16
2017 CCPC Final Contest
Onsite Round, Sunday, December 3rd, 2017
Problem C. Rich Game
One day, God Sheep would like to play badminton but he can’t find an opponent. So he request Mr.
Panda to play with him. He said: “Each time I win one point, I’ll pay you X dollars. For each time I lose
one point, you should give me Y dollars back.”
God Sheep is going to play K sets of badminton games. For each set, anyone who wins at least 11 points
and leads by at least 2 points will win this set. In other words, normally anyone who wins 11 points first
will win the set. In case of deuce (E.g. 10 points to 10 points), it’s necessary to lead by 2 points to win
the set.
Mr. Panda is really good at badminton so he could make each point win or lose at his will. But he has
no money at the beginning. He need to earn money by losing points and using the money to win points.
Mr. Panda cannot owe God Sheep money as god never borrowed money. What’s the maximal number of
sets can Mr. Panda win if he plays cleverly?
Input
The first line of the input gives the number of test cases, T . T test cases follow.
Each test case contains 3 numbers in one line, X, Y , K, the number of dollars earned by losing a point,
the number of dollars paid by winning a point, the number of sets God Sheep is going to play.
Output
For each test case, output one line containing “Case #x: y”, where x is the test case number (starting
from 1) and y is the maximal number of sets Mr. Panda could win.
Limits
• 1 ≤ T ≤ 10
5
.
• 1 ≤ X, Y, K ≤ 1000.
Example
standard input standard output
2
10 10 1
10 10 2
Case #1: 0
Case #2: 1
Note
In the first test case, Mr. Panda don’t have enough money to win the only set, so he must lose the only
set.
In the second test case, Mr. Panda can lose the first set by 0:11 and he can earn 110 dollars. Then winning
the second set by 11:0 and spend 110 dollars.
Page 4 of 16
剩余15页未读,继续阅读
资源评论
No_Name42
- 粉丝: 0
- 资源: 2
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功