| 题目名称 | 575. 猴子和香蕉 |
|---|---|
| 输入输出 | monkeys.in/out |
| 难度等级 | ★★☆ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 14 |
| 题目来源 |
 cqw
于2011-07-26加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：1， 提交：23， 通过率：4.35% | ||||
 confoo |
100 | 1.442 s | 15.55 MiB | C++ |
 KZNS |
92 | 2.303 s | 0.31 MiB | C++ |
|
confoo |
92 | 3.253 s | 15.55 MiB | C++ |
|
confoo |
85 | 1.705 s | 15.55 MiB | C++ |
 老虎小飞 |
64 | 0.014 s | 57.34 MiB | Pascal |
 农场主 |
64 | 3.795 s | 0.31 MiB | C++ |
|
农场主 |
64 | 3.962 s | 0.31 MiB | C++ |
|
农场主 |
64 | 4.011 s | 0.31 MiB | C++ |
|
confoo |
64 | 7.002 s | 38.43 MiB | C++ |
 王者自由 |
57 | 0.009 s | 0.27 MiB | C++ |
| 本题关联比赛 | |||
| 20110727 | |||
| 20120418x | |||
| 关于 猴子和香蕉 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
让常数优化成为一种习惯 —— wys
前排提醒，a和a-1互质 | ||||
【问题描述】
你听说过猴子分香蕉的故事吗?这个题目有些不一样.有N只猴子住在一个岛屿上,一天他们发现了很多香蕉,于是他们决定把这些香蕉分成各自的,他们应该怎么做?
吵闹了很长时间,他们制定了如下规则:他们定出了C条选择,每个选择包含两个整数x,y,我们假设开始有B串香蕉,每只猴子从老的到小的,随机进行一个选择获得他自已的香蕉.如果他选了第i个选择(1≤i≤C),他可以先得到yi串香蕉,然后,他把剩余的分成xi堆,每堆是相同的.最后他再获得一堆香蕉.他总共获得了yi和一堆香蕉.每只猴子都这样做.当最后一只猴子选择时,他们发现所有的香蕉都分完了.
现在我知道他们的计划.但我不知道哪只猴子作了什么选择,也不知道猴子和香蕉的开始数量.如果有B0串香蕉能满足这个分配过程,B0被认为是一个可能的答案.
这是你的工作,我将给你一个数K,你应该输出第K小的可能的答案.
【输入格式】
输入文件第一行是两个正整数Nm(Nm≤100)和C(C≤20)，表示猴子的最大数量和他们的选择数．下面每行包含两个整数xi(2≤xi≤100)和yi(0≤yi≤100)，含义如题所述．下面一行包含一个整数K (1≤K≤1,000,000),是I号请求．
【输出格式】
输出仅一行包含一个整数B，是一个与输入需求一致的答案．如果K是一个比所有答案大的数,则输出“-1” .
注意:已知香蕉总数不会超过10^9．
【输入样例】
输入文件名：monkeys.in
2 2
2 4
3 2
3
2 4
3 2
3
输出文件名：monkeys.out
5
输入文件名：monkeys.in
2 2
2 4
3 2
6
2 4
3 2
6
输出文件名：monkeys.out
-1