#P17760. 「奶龙OI」Round 3 - 生存大师
「奶龙OI」Round 3 - 生存大师
题目描述
矿道可以看成从入口向内依次排列的 个方块。第 个方块的种类为 :
- 表示石头;
- 表示钻石矿。
你有一把耐久度为 的石镐和一把耐久度为 的铁镐:
- 石镐只能挖掘石头;
- 铁镐既可以挖掘石头,也可以挖掘钻石矿;
- 每挖掘一个方块,所使用的镐的耐久度恰好减少 ;
- 耐久度为 的镐不能继续使用。
你必须从矿道入口开始,按照 的顺序逐格挖掘,不能跳过尚未挖掘的方块。
请问你最多能够挖掘多少个方块?
输入格式
第一行输入一个整数 ,表示测试用例的数量。
接下来依次输入 组测试用例。对于每组测试用例:
- 第一行输入三个整数 ,分别表示矿道长度、石镐耐久度和铁镐耐久度;
- 第二行输入 个整数 ,表示每个方块的种类。
输出格式
对于每组测试用例,输出一行一个整数,表示最多能够挖掘的方块数。
4
5 3 1
1 2 1 1 2
6 2 3
1 1 2 1 2 1
3 0 2
2 1 1
4 10 10
2 2 1 2
4
5
2
4
提示
【样例 #1 解释】
对于第一组测试用例,可以依次使用石镐、铁镐、石镐、石镐挖掘前四个方块。此时铁镐已经损坏,无法挖掘第五个钻石矿,因此答案为 。
对于第二组测试用例,两把镐的总耐久度为 ,并且铁镐足以挖掘前五个方块中的两个钻石矿,因此答案为 。
对于第三组测试用例,只能使用铁镐。挖掘前两个方块后铁镐损坏,因此答案为 。
【数据范围与约定】
本题采用捆绑测试。
对于全部数据,保证:
- ;
- ;
- ;
- ;
- 单个输入文件中所有测试用例的 之和满足 。
的限制对每组测试用例分别成立,不对它们求和。
| 子任务 | 特殊限制 | 分值 |
|---|---|---|
| 无特殊限制 |