图森未来2020校招笔试卷（三）
时长:120分钟 总分:100分
261浏览 0人已完成答题
题型介绍
| 题型 | 填空题 |
|---|---|
| 数量 | 3 |
1.
公司扩招
又到了一年一度的校招季，图森未来的老员工阿伟自然是非常关心今年公司的新生力量涌入。
经过一番调查，阿伟发现，每年公司新入职的员工数量都和前两年入职的员工数量有关。假设第 i 年公司有 Fi 个人新入职，那么有 Fi = Fi-22 + k * Fi-1。
忙碌的阿伟希望你帮他写一个程序来算一算某一年公司会有多少个人新入职。由于最终答案可能非常大，所以只需要告诉阿伟最终答案对100003（105+3）取模之后的结果就可以了。
提示：图森未来成立于2015年，我们可以认为2014年新入职的员工数是0，2015年新入职的员工数是1。
输入描述： 输入只有一行，包含2个正整数y和k。其中y表示阿伟想要询问的年份，k为题面式子中的系数。
对于 80% 的数据，我们保证 2015 <= y <= 9999，1 <= k <= 10；
对于剩下 20% 的数据，我们保证 2015 <= y <= 10^9999，1 <= k <= 100。输入样例： 2017 2 输出描述： 输出只有一个整数，即当年新入职的员工数量。输出样例 5
经过一番调查，阿伟发现，每年公司新入职的员工数量都和前两年入职的员工数量有关。假设第 i 年公司有 Fi 个人新入职，那么有 Fi = Fi-22 + k * Fi-1。
忙碌的阿伟希望你帮他写一个程序来算一算某一年公司会有多少个人新入职。由于最终答案可能非常大，所以只需要告诉阿伟最终答案对100003（105+3）取模之后的结果就可以了。
提示：图森未来成立于2015年，我们可以认为2014年新入职的员工数是0，2015年新入职的员工数是1。
输入描述： 输入只有一行，包含2个正整数y和k。其中y表示阿伟想要询问的年份，k为题面式子中的系数。
对于 80% 的数据，我们保证 2015 <= y <= 9999，1 <= k <= 10；
对于剩下 20% 的数据，我们保证 2015 <= y <= 10^9999，1 <= k <= 100。输入样例： 2017 2 输出描述： 输出只有一个整数，即当年新入职的员工数量。输出样例 5
2.
快递机器人
图森未来的员工阿伟最新研发了一款快递机器人，他投放了一台机器人在公司办公室中进行试运营。
公司的座位分布比较工整，可以看成一个四分之一平面上的网格图，即所有坐标轴上第一象限中的整点都是一个工位，上下左右相邻的工位间有一条长为1的边。由于阿伟资历比较深，所以坐在了公司的(1, 1)点上。
机器人每天都会从阿伟的座位出发，去n个同事的工位上收快递。每1秒中，机器人可以向x轴正方向，x轴负方向，或者y轴正方向移动1个单位（由于某些技术原因，暂时不允许向y轴负方向移动，同时也不允许移动到公司外，即不允许移动到x坐标小于等于0的位置）。例如，如果当前时刻机器人所在的坐标为(x, y)，下一秒机器人可能可以到达的位置为(x + 1, y)，(x - 1, y)或者(x, y + 1)。当机器人到达某个同事所在的工位时，就会获得要收取的快递，收快递的动作不需要消耗时间。一旦机器人收完所有快递，他就可以立即传送回仓库，把同事们的快递发送出去。
现在阿伟告诉了你今天需要去收快递的所有同事的工位坐标，他希望你可以写一个程序帮他计算一下收完所有快递最少所需要花费的总时间。
输入描述： 输入的第1行包含1个正整数n，表示当天要收货的同事数量。
接下来的n行，每行有两个正整数x和y，表示坐在(x, y)处的同事今天有快递需要收取。保证n个坐标两两不同。
对于 30% 的数据，1 <= n <= 8，1 <= x, y <= 1000；
对于另外 30% 的数据，1 <= n <= 1000，1 <= x, y <= 106，并且保证没有任何超过8个同事位置的y坐标相同。
对于另外 40% 的数据，1 <= n <= 105，1 <= x, y <= 109；输入样例： 2 3 3 2 2 输出描述： 输出只包含一个正整数，为当天收货所需要花费的最少总时间。输出样例 4
公司的座位分布比较工整，可以看成一个四分之一平面上的网格图，即所有坐标轴上第一象限中的整点都是一个工位，上下左右相邻的工位间有一条长为1的边。由于阿伟资历比较深，所以坐在了公司的(1, 1)点上。
机器人每天都会从阿伟的座位出发，去n个同事的工位上收快递。每1秒中，机器人可以向x轴正方向，x轴负方向，或者y轴正方向移动1个单位（由于某些技术原因，暂时不允许向y轴负方向移动，同时也不允许移动到公司外，即不允许移动到x坐标小于等于0的位置）。例如，如果当前时刻机器人所在的坐标为(x, y)，下一秒机器人可能可以到达的位置为(x + 1, y)，(x - 1, y)或者(x, y + 1)。当机器人到达某个同事所在的工位时，就会获得要收取的快递，收快递的动作不需要消耗时间。一旦机器人收完所有快递，他就可以立即传送回仓库，把同事们的快递发送出去。
现在阿伟告诉了你今天需要去收快递的所有同事的工位坐标，他希望你可以写一个程序帮他计算一下收完所有快递最少所需要花费的总时间。
输入描述： 输入的第1行包含1个正整数n，表示当天要收货的同事数量。
接下来的n行，每行有两个正整数x和y，表示坐在(x, y)处的同事今天有快递需要收取。保证n个坐标两两不同。
对于 30% 的数据，1 <= n <= 8，1 <= x, y <= 1000；
对于另外 30% 的数据，1 <= n <= 1000，1 <= x, y <= 106，并且保证没有任何超过8个同事位置的y坐标相同。
对于另外 40% 的数据，1 <= n <= 105，1 <= x, y <= 109；输入样例： 2 3 3 2 2 输出描述： 输出只包含一个正整数，为当天收货所需要花费的最少总时间。输出样例 4
3.
另一个快递机器人
图森未来的员工阿伟最新研发了一款快递机器人，他投放了一台机器人在自己的小区中进行试运营。
这个小区中共有n幢楼，每幢都有一个编号；同时每幢楼都有k层，每层有一个层号。房间号则是层号加上包含前导0的两位数字拼接而成，例如：第3层的2号房间，房间号为302；第15层的58号房间，房间号为1558；第123层的4号房间，房间号为12304。
同时，因为业主的要求，小区每幢楼的层号都会跳过包含"4"和"13"的数字，因为它们不吉利。例如，4、13、49、133和134都是不吉利的数字，而123则不是不吉利的数字，因为里面没有包含连续的"13"。被跳过的数字不会有对应的层数，例如第3层的上一层是第5层，而第12层的上一层是第15层。
机器人每天会为m个住户寄送快递，住户的房间由楼号b和一个房间号r表示。快递机器人只能通过一些特定的路线在某些楼的1层之间移动，或者通过电梯在同一幢楼的不同楼层之间移动。m个住户的送货顺序是确定的并会提前给出，快递机器人只会按照顺序依次为这m个住户送货。
为了了解快递机器人的工作效率，阿伟希望知道快递机器人每天送货的预计时间。为了简化问题，他认为只有在同一幢楼的不同楼层之间移动以及不同楼的1层之间移动才会花时间。等待电梯、在同一楼层之间送货以及出发前装货的时间都可以忽略，且快递机器人的容量足以装下所有快递，而机器人和电梯的移动速度也不会因为快递的数量发生改变。
简而言之，我们只需要计算如下两种时间花费：
- 从某幢楼的1层移动到另一幢楼的1层：某些楼之间是可以直接移动的，阿伟会提前给出这些楼之间移动的时间花费。注意因为一些交通规则的原因，从a到b花费的时间和从b到a花费的时间不一定是一样的，也可能出现a可以移动到b但是b不能移动到a的情况。另外，从a移动到c花费的时间也不一定等于从a移动到b再从b移动到c的时间。
- 从某幢楼的x层移动到同一幢楼的y层：假设x层和y层之间相隔k层，那么这次移动的时间花费就是k。但是注意因为有一些层号是不存在的，所以k不一定等于|y-x|（||代表绝对值）。例如，3层和5层之间因为不存在4层所以只相隔1层，从3层移动到5层的时间花费是1而不是2。同理，因为39层和50层之间都是包含4的楼层，所以从50层移动到39层的时间花费也是1。
请注意，按照以上规则，如果当前在a楼的x层，要移动到b楼的y层，且a!=b，x!=1，y!=1，那么要经历三个步骤：
- 从a楼x层移动到a楼1层；
- 从a楼1层移动到b楼1层（有可能会经过其它楼的1层）；
- 从b楼1层移动到b楼y层。
现在阿伟会按照顺序给出某天需要送货的所有住户的楼号和房间号，以及全部可以移动的楼号和在它们之间移动分别所花费的时间。机器人每天会从1号楼的1层出发，并在所有货物送完之后回到1号楼的1层结束。阿伟希望你可以写一个程序帮他计算一下这一天送货（包括回到1号楼的1层）最少所需要花费的总时间。如果无法依次到达需要送货的所有住户，输出-1。
输入描述： 输入的第1行包含三个正整数n、t和m，分别为小区内楼的数量、可以移动的路径数量以及当天要送货的住户数量。
接下来的t行（第2行到第t+1行）每行包含三个正整数x、y、d，用空格分隔，表示从x号楼的1层移动到y号楼的一层所花费的时间为d，楼号为[1, n]内的正整数。
接下来的m行（第t+2到t+m+1行）每行包含两个正整数b和r，分别表示题目描绘中的楼号b和房间号r，其中房间号是按照题目描述中的方式拼接而成的。输入样例： 2 2 2 1 2 10 2 1 100 2 1501 2 314 输出描述： 输出包含一个整数，为当天送货所需要花费的最少总时间。若当天因为无法在某两个楼之间移动而完不成送货任务，则输出-1。输出样例 132
这个小区中共有n幢楼，每幢都有一个编号；同时每幢楼都有k层，每层有一个层号。房间号则是层号加上包含前导0的两位数字拼接而成，例如：第3层的2号房间，房间号为302；第15层的58号房间，房间号为1558；第123层的4号房间，房间号为12304。
同时，因为业主的要求，小区每幢楼的层号都会跳过包含"4"和"13"的数字，因为它们不吉利。例如，4、13、49、133和134都是不吉利的数字，而123则不是不吉利的数字，因为里面没有包含连续的"13"。被跳过的数字不会有对应的层数，例如第3层的上一层是第5层，而第12层的上一层是第15层。
机器人每天会为m个住户寄送快递，住户的房间由楼号b和一个房间号r表示。快递机器人只能通过一些特定的路线在某些楼的1层之间移动，或者通过电梯在同一幢楼的不同楼层之间移动。m个住户的送货顺序是确定的并会提前给出，快递机器人只会按照顺序依次为这m个住户送货。
为了了解快递机器人的工作效率，阿伟希望知道快递机器人每天送货的预计时间。为了简化问题，他认为只有在同一幢楼的不同楼层之间移动以及不同楼的1层之间移动才会花时间。等待电梯、在同一楼层之间送货以及出发前装货的时间都可以忽略，且快递机器人的容量足以装下所有快递，而机器人和电梯的移动速度也不会因为快递的数量发生改变。
简而言之，我们只需要计算如下两种时间花费：
- 从某幢楼的1层移动到另一幢楼的1层：某些楼之间是可以直接移动的，阿伟会提前给出这些楼之间移动的时间花费。注意因为一些交通规则的原因，从a到b花费的时间和从b到a花费的时间不一定是一样的，也可能出现a可以移动到b但是b不能移动到a的情况。另外，从a移动到c花费的时间也不一定等于从a移动到b再从b移动到c的时间。
- 从某幢楼的x层移动到同一幢楼的y层：假设x层和y层之间相隔k层，那么这次移动的时间花费就是k。但是注意因为有一些层号是不存在的，所以k不一定等于|y-x|（||代表绝对值）。例如，3层和5层之间因为不存在4层所以只相隔1层，从3层移动到5层的时间花费是1而不是2。同理，因为39层和50层之间都是包含4的楼层，所以从50层移动到39层的时间花费也是1。
请注意，按照以上规则，如果当前在a楼的x层，要移动到b楼的y层，且a!=b，x!=1，y!=1，那么要经历三个步骤：
- 从a楼x层移动到a楼1层；
- 从a楼1层移动到b楼1层（有可能会经过其它楼的1层）；
- 从b楼1层移动到b楼y层。
现在阿伟会按照顺序给出某天需要送货的所有住户的楼号和房间号，以及全部可以移动的楼号和在它们之间移动分别所花费的时间。机器人每天会从1号楼的1层出发，并在所有货物送完之后回到1号楼的1层结束。阿伟希望你可以写一个程序帮他计算一下这一天送货（包括回到1号楼的1层）最少所需要花费的总时间。如果无法依次到达需要送货的所有住户，输出-1。
输入描述： 输入的第1行包含三个正整数n、t和m，分别为小区内楼的数量、可以移动的路径数量以及当天要送货的住户数量。
接下来的t行（第2行到第t+1行）每行包含三个正整数x、y、d，用空格分隔，表示从x号楼的1层移动到y号楼的一层所花费的时间为d，楼号为[1, n]内的正整数。
接下来的m行（第t+2到t+m+1行）每行包含两个正整数b和r，分别表示题目描绘中的楼号b和房间号r，其中房间号是按照题目描述中的方式拼接而成的。输入样例： 2 2 2 1 2 10 2 1 100 2 1501 2 314 输出描述： 输出包含一个整数，为当天送货所需要花费的最少总时间。若当天因为无法在某两个楼之间移动而完不成送货任务，则输出-1。输出样例 132
