网易互娱雷火校园招聘试卷-游戏研发工程师（第一批）

本题需要让你模拟一下在Windows系统里窗口和鼠标点击的操作，具体如下：
1.屏幕分辨率为3840*2160，左上角坐标为(0, 0)， 右下角坐标为(3839, 2159)
2.窗口是一个矩形的形状，由左上角坐标(X, Y)，和宽高(W, H)，四个数字来定位。左上角坐标为(X, Y)、右下角坐标为(X+W, Y+H)，其中左上角坐标一定会在屏幕范围内，其他一些部分可能会超过屏幕范围。
3.窗口的点击和遮挡规则同Windows，但是不考虑关闭窗口、最大化、最小化和强制置顶的情况。即
    3.1 如果发生重叠的话，后面打开的窗口会显示在前面打开的窗口上面
    3.2 当鼠标发生一次点击的时候，需要判断点击到了哪个窗口，如果同个坐标有多个窗口，算点击到最上层的那个
    3.3 当一个窗口被点击的时候，会浮动到最上层

输入描述： 每个测试输入包含1个测试用例
第一行为2个整数N, M。其中N表示打开的窗口数目，M表示鼠标点击的数目。其中0<N,M<1000
接下来N行，每一行四个整数 Xi Yi Wi Hi，分别表示第i个窗口（窗口Id为i，从1开始计数）的左上角坐标以及宽高，初始时窗口是按输入的顺序依次打开。其中 0<=Xi<3840, 0<=Yi<2160, 0<Wi<3840, 0<Hi<2160
再接下来有M行，每一行两个整数 Xj Yj，分别表示接下来发生的鼠标点击坐标。其中 0 <=Xj<3840, 0<=Yj<2160输入样例： 2 4 100 100 100 100 10 10 150 150 105 105 180 180 105 105 1 1 输出描述： 对于每次鼠标点击，输出本次点击到的窗口Id。如果没有点击到窗口，输出-1输出样例 2 1 1 -1

The Stern-Brocot tree is an infinite complete binary tree in which the vertices correspond one-for-one to the positive rational numbers, whose values are ordered from the left to the right as in a search tree.



Figure 1 shows a part of the Stern-Brocot tree, which has the first 4 rows. Each node in the tree is marked in a red cycle. The value in the node is the mediant of the left and right fractions. The mediant of two fractions A/B and C/D is defined as (A+C)/(B+D).
To construct the Stern-Brocot tree, we first define the left fraction of the root node is 0/1, and the right fraction of the root node is 1/0. So the value in the root node is the mediant of 0/1 and 1/0, which is (0+1)/(1+0)=1/1. Then the value of root node becomes the right fraction of the left child, and the left fraction of the right child. For example, the 1st node in row2 has 0/1 as its left fraction and 1/1(which is the value of its parent node) as its right fraction. So the value of the 1st node in row2 is (0+1)/(1+1)=1/2. For the same reason, the value of the 2nd node in row2 is (1+1)/(1+0)=2/1. This construction progress goes on infinitly. As a result, every positive rational number can be found on the Stern-Brocot tree, and can be found only once.

Given a rational number in form of P/Q, find the position of P/Q in the Stern-Brocot Tree.

输入描述： Input consists of two integers, P and Q (1<=P,Q<=1000), which represent the rational number P/Q. We promise P and Q are relatively prime.输入样例： 5 3 输出描述： Output consists of two integers, R and C.
R indicates the row index of P/Q in the Stern-Brocot Tree, C indicates the index of P/Q in the row.
Both R and C are base 1.
We promise the position of P/Q is always in the first 12 rows of the Stern-Brocot tree, which means R<=12.输出样例 4 6

在网游中，聊天功能是一项非常重要的功能，加上玩家可以打出游戏内置的一些表情图片，因此需要实现一个图文混排系统，如上图所示。

玩家在聊天框输入的是一段utf-8编码的文字，且只会包含中文、英文、中英文的标点符号和空格（不会出现换行、回车和制表符）。按照网易游戏的传统，井号(#)是作为一个转义字符，支持下面几种转义行为：

1. #加一个数字来表示内置的表情图片，为了简化问题，我们这里只支持20个表情图片，从0开始计数，并且数字是按最长匹配原则去匹配，比如 #0 表示0号表情图片、#1 表示1号表情图片 、#19表示19号表情图片、#20则表示2号表情图片后面加数字0。需要注意的是#00表示的是0号表情图片加后面数字0。

2. #r 表示换行，遇到以后会自动切换到下一行开始排版。

3. ## 表示显示出#这个符号

4.如果玩家不按规则输入错误的转义，则按照玩家的输入原样显示，比如#a、#、#,、#啊

 

上图所示的玩家输入为：“Hello world#大家好#r欢迎大家参加网易雷火校园招聘#1祝大家取得好成绩”

 

排版的时候需要像上图一样，将文字从起始位置开始，依次显示在聊天窗口里，一些显示规则如下所示：

1.聊天窗口的宽度固定为W像素，起始坐标为左上角，坐标为(0, 0)，右上角坐标为(W-1, 0)，坐标向右向下增长。任何文字和表情必须显示在窗口内，不能超出窗口。但是高度可以无限向下延伸。

2.显示的字体均为等宽字体，英文（包括英文标点符号和空格）的字体宽度统一为XE，高度统一为YE。中文（包括中文的标点符号）的字体宽度统一为XC，高度统一为YC。

3.每个表情图片的宽高是独立的，0号表情图片的宽度为 X0，高度Y0，依次类推，19号表情图片的宽度为X19，高度为Y19。

4.字符（中英文以及标点符号、空格等，下同）与字符之间、字符与表情之间、表情与表情之间都需要额外保留一个PX像素的字间距。每一行第一个字符左边，以及最后一个字符右边不需要保留字间距。

5.当下一个字符或者表情无法在本行W宽度的像素内完整显示的话，则会强行换到下一行首开始显示。遇到#r的时候也会自动换到下一行开始显示下一个字符或表情。

6.在一行里出现高度不同的中英文以及表情的时候，需要将其底部对齐。

7.当一行里没有任何字符或表情，直接被#r换行的时候，这一行的高度算英文字体的高度。

8.每一行里高度最高的字符或表情，需要同上一行的的底部保留PY像素的行间距。第一行上面与最后一行下面不需要保留行间距。

9.最后一个字符或表情显示显示以后，它的右下角坐标则为结束坐标。也就是本题需要求解的问题。输入保证最后不会以#r结尾。

输入描述： 每个测试输入包含1个测试用例

第一行为7个正整数W, XE, YE, XC, YC, PX, PY

第二行为40个正整数X0,
Y0, X1, Y1…X19, Y19

第三行为长度不超过10000的十六进制编码过的玩家输入，即玩家输入的utf-8编码的数据每个字节的数字转成大写的十六进制表示，不足两位的话前面补0（同C里printf的%X格式化），然后不同字节的十六进制编码表示依次拼接起来。

比如Hello的十六进制编码表示为48656C6C6F。

前两行的各个数字含义如上文描述，其中50&ltW&lt10000，0<其他&lt50。输入样例： 60 2 4 3 4 1 3 7 6 7 6 7 6 7 6 7 6 7 6 7 6 7 6 7 6 7 6 7 6 7 6 7 6 7 6 7 6 7 6 7 6 7 6 7 6 7 6 48656C6C6F20776F726C6423E5A4A7E5AEB6E5A5BD2372E6ACA2E8BF8EE5A4A7E5AEB6E58F82E58AA0E7BD91E69893E99BB7E781ABE6A0A1E59BADE68B9BE881982331E7A59DE5A4A7E5AEB6E58F96E5BE97E5A5BDE68890E7BBA9 输出描述： 输出用空格隔开的两个数字，表示结束坐标输出样例 38 19

游戏规则如下
- 在棋盘上有N个数字（A1~AN）从左到右排列成一行
- A，B两个玩家轮流进行游戏，第一回合A玩家行动，第二回合B玩家行动，依次行动直到游戏结束
- 每回合玩家可以选择拿走棋盘上最左边或者最右边的一个数字，其余的都不能拿
- 拿走的数字依次从左到右排列在自己面前
- 棋盘上所有数字被拿走后游戏结束
- 最优策略的说明：在任意局面下，玩家如果取左边的数字或者取右边的数字，最终最优得分都一样，那么只能取左边的数字

当所有数字都被拿走后，A,B两个玩家面前都各有一个数列。
假设A玩家面前数字从左到右为 X1,X2,X3...XM，则他的最终得分Sa计算方式如下（B玩家的得分计算Sb也类似，不赘述）：
Sa = abs(X1-0) + abs(X2-X1) + abs(X3-X2) + ... + abs(XM - X(M-1))


请计算在以上的规则下，如果两个玩家都想拿到尽量多的分数，用最优策略进行游戏，计算两个人的最终得分。

输入描述： 第一行一个数字 N, 一半的测试用例 (0 < N <= 50)，一半的测试用例 (0 < N <= 1000)
第二行N个数字 Ai ( 0 <= Ai <= 50)输入样例： 4 1 2 3 4 输出描述： 用空格隔开的两个整数Sa和Sb输出样例 7 4

钱老板家的电子保险柜被一个神秘的安保函数y=f(x)保护，每次试图开锁时，系统都会调用安保函数代码输入一个(0,1)之间的浮点数x，如果安保函数能输出正确的y数值则可以打开保险柜，否则就会报警。黑客小军想办法获取到了一份这个安保函数的测试程序，但这个程序并不能在钱老板家的系统上直接运行，必须要重新编码一份新的代码才能使用，请帮助小军实现这个安保函数代码！
你可以在以下的URL下载这份测试程序的可执行文件，压缩包里包含windows、linux和macos三个平台下的可执行程序：
http://59.111.13.242/leihuo_2019_guess.zip

输入描述： 一个(0,1)的浮点数，精确到小数点后6位输入样例： 0.268044 输出描述： 一个浮点数，精确到小数点后6位输出样例 2.681916