- High and Dry
You are planning a canoe trip through a tidal estuary (a network of waterways subject to tides). You can paddle only by day (sunrise to sunset). A particular difficulty is that many of the places you can consider stopping will only have enough water to float your canoe when the tide is sufficiently high, and getting stuck offshore in the mud for several hours is not your idea of a good time!
You have a list of the available docks, in the order you will encounter them. For each dock you know how many miles it is from your starting point and for how many hours before and after low tide it cannot be reached. You need not stop at each dock, and the main channel of the waterway will always have enough water for you to make progress if you wish to bypass one or more docks. You want to be sure, however, that you put in to an accessible dock by sunset on each day. You also cannot depart from a dock in the morning until enough water is available.
The time of sunrise, sunset, and low tides for each day will change slightly. So successive sunrises will not be exactly 24 hours apart nor sunsets, nor will successive low tides occur exactly 12 hours apart. Over the limited number of days for your trip, we can approximate these changes as a fixed number of minutes per day away from the ideal.
Write a program to prepare itineraries for such trips, indicating at which docks you will stop at end of each day's paddling. Each itinerary should require as few days as possible. Given a choice of itineraries with the same number of days, choose the one in which you make the most progress in the earlier days.
Input consists of a series of trip descriptions. All time inputs will be presented in the form HH:MM:SS, where HH is a two digit integer indicating hours from 00-23, MM is a two-digit integer indicating minutes from 00-59, and SS is a two-digit integer indicating seconds from 00-59.
For each trip description:
Line 1 Maximum number of days for the trip (integer 1-10)
Line 2 Average paddling speed in miles per hour (positive real number)
Time of sunrise on day 1 of the trip (05:00:00-08:00:00)
Time between successive sunrises (23:45:00-24:15:00)
Time of sunset on day 1 (17:00:00-20:00:00)
Time between successive sunsets (23:45:00-24:15:00)
Time of 1st low tide on day 1 (any time)
Time between successive low tides (11:00:00-13:00:00)
Line 6 Number of docks available along the way, not counting your trip starting point but
including your final destination (positive integer)
One line for each dock (including the starting dock at distance 0.0), containing:
Distance of that dock, in miles, from your trip starting point (real)
Number of hours before and after low tide when dock is inaccessible(integer 0-12)
The final dataset is followed by a 0.
For each trip description, print a single line:
NO ITINERARY POSSIBLE
if the trip cannot be completed in the indicated number of days. If the trip can be completed, print a single line containing the numbers of the docks at which you would stop on each day, each number separated from the others by a single space.
2 5 7 9
- 博客 在中国程序员是青春饭吗？
- 博客 程序员请照顾好自己，周末病魔差点一套带走我。
- 博客 Java基础知识面试题（2020最新版）
- 博客 和黑客斗争的 6 天！
- 博客 Intellij IDEA 实用插件安利
- 博客 搜狗输入法也在挑战国人的智商！
- 博客 总结了 150 余个神奇网站，你不来瞅瞅吗？
- 博客 副业收入是我做程序媛的3倍，工作外的B面人生是怎样的？
- 博客 MySQL数据库面试题（2020最新版）
- 博客 如果你是老板，你会不会踢了这样的员工？
- 博客 我入职阿里后，才知道原来简历这么写
- 博客 魂迁光刻，梦绕芯片，中芯国际终获ASML大型光刻机
- 博客 优雅的替换if-else语句
- 博客 离职半年了，老东家又发 offer，回不回？
- 博客 2020阿里全球数学大赛：3万名高手、4道题、2天2夜未交卷
- 博客 为什么你不想学习？只想玩？人是如何一步一步废掉的
- 博客 百度工程师，获利10万，判刑3年！
- 博客 程序员为什么千万不要瞎努力？
- 博客 为什么程序员做外包会被瞧不起？
- 博客 当HR压你价，说你只值7K，你该怎么回答？
- 博客 面试：第十六章：Java中级开发（16k）
- 博客 面试阿里p7，被按在地上摩擦，鬼知道我经历了什么？
- 博客 无代码时代来临，程序员如何保住饭碗？
- 博客 面试了一个 31 岁程序员，让我有所触动，30岁以上的程序员该何去何从？
- 博客 大三实习生，字节跳动面经分享，已拿Offer
- 博客 程序员垃圾简历长什么样？
- 博客 《Oracle Java SE编程自学与面试指南》最佳学习路线图2020年最新版（进大厂必备）
- 博客 字节跳动面试官竟然问了我JDBC？
- 博客 面试官：你连SSO都不懂，就别来面试了
- 博客 实时更新：计算机编程语言排行榜—TIOBE世界编程语言排行榜（2020年6月份最新版）