编程介的小学生 2019-06-10 13:27 采纳率: 20.5%
浏览 106

确定最后一个海盗与最后一个项目越过木板之前需要多长时间,怎么使用C语言的程序编写代码设计解决

Problem Description
A bunch of pirates have successfully conquered a commercial vessel. The ship itself is too badly damaged, so the entire shipload needs to be transferred to the pirate ship.
The pirates have anchored a plank to both ships, which the pirates can use to go from one ship to the other, but it can only support one pirate at a time.
Each pirate executes the following routine:
1. Walk across the plank from the pirate ship to the commercial ship
2. Pick up an item from the cargo hold and return to the plank
3. Cross the plank back to the pirate ship with the item
4. Put the item in the cargo hold and return to the plank
Each of these four steps takes a given amount of time for each pirate. Every pirate will repeat these steps until the number of pirates on the commercial ship equals the number of items there (i.e. there's nothing more for the pirate to collect).
If a pirate gets to the plank and it's in use by another pirate, he will wait at his side of the plank. When the plank is vacated and there are pirates on both sides of the plank, the pirates on the side of the commercial vessel (carrying some item) will get to go first. At both sides of the plank, the pirates queue up, i.e. the first one to get there will be the first one to cross. Should two or more pirates arrive at the same side of the plank at the exact same time, the pirate who was slowest (i.e. the one who has taken the most time to and from the cargo hold on this ship) gets to go first.Can you determine how long it takes before the last pirate has crossed the plank with the last item?

Input
The first line of the input contains a single number: the number of test cases to follow. Each test case has the following format:
1.One line with two integers N and P, satisfying 1 <= N <= 100,000 and 1 <= P <= 1,000: the number of items on the commercial vessel and the number of pirates, respectively.
2.P lines, each with 4 integers t1 through t4, satisfying 1 <= ti <= 1,000: the time in seconds it takes this pirate to complete each step (as listed above).
At the start, all pirates are queued up at the plank on the pirate ship in the order given in the input (the first pirate is the first to cross over).

Output
For every test case in the input, the output should contain one integer on a single line: the time in seconds between the time the first pirate starts crossing the plank and the time the last pirate has crossed the plank carrying the last item.

Sample Input
3
3 3
10 3 10 3
10 3 10 3
10 3 10 3
3 2
10 10 10 10
1 9 1 8
3 2
3 2 3 6
4 2 5 5

Sample Output
63
50
24

  • 写回答

0条回答 默认 最新

    报告相同问题?

    悬赏问题

    • ¥15 【提问】基于Invest的水源涵养
    • ¥20 微信网友居然可以通过vx号找到我绑的手机号
    • ¥15 spring后端vue前端
    • ¥15 寻一个支付宝扫码远程授权登录的软件助手app
    • ¥15 解riccati方程组
    • ¥15 display:none;样式在嵌套结构中的已设置了display样式的元素上不起作用?
    • ¥15 使用rabbitMQ 消息队列作为url源进行多线程爬取时,总有几个url没有处理的问题。
    • ¥15 Ubuntu在安装序列比对软件STAR时出现报错如何解决
    • ¥50 树莓派安卓APK系统签名
    • ¥65 汇编语言除法溢出问题