Google Code Jam 2019 World Finals

今年的 Code Jam 结束了，一不留神 Tourist 又^6 夺冠了。。。
先来看一下 Final 的题目吧。

• 题目
• 直播

Board Meeting

• Livestream

Brief Description

交互题。给定一个无限大的棋盘，上面摆放了至多 n 个国王。准备阶段，你可以进行询问至多 r 次，每次询问一个坐标，系统返回所有国王距离这个坐标的距离和。之后，询问阶段角色互换，系统会向你询问至多 r 次，每次询问一个坐标，你需要返回所有国王距离这个坐标的距离和。

（每个国王的坐标绝对值不超过 m，询问的坐标绝对值不超过 10m)
（n <= 10, m = 1e6，r = 1000）
（小数据中，n = 1）

Idea

先考虑一个点的情况？回忆航海里的三角测量以及 GPS 里的三点定位？
对于大数据，有办法可以得到每个点的坐标吗？需要得到每个点坐标吗？

Sorting Permutation Unit

• Livestream

Brief Description

你需要将 k 段长度为 n 的数组按照非递减顺序排序。排序的方法是使用你自己构造的置换。你可以至多构造 p 组置换，每次排序可以使用这些置换不超过 s 次。

（k <= 30, n <= 50, s = 450）
（Small: p = 20）
（Large: p = 5）

Won’t Sum

• Livestream

Juggle Stuggle Part

Brief Description

平面内给出 n 条线段，称这组线段是相融的，如果他们两两相交。
– Part 1: 给定 2n 个点，构造一组相融的连线方式，数据保证一定有解。
– Part 2: 给定 n 条线段，判断它们是否相融。

Idea

• 3Blue1Brown, This problem seems hard, then it doesn’t, but it really is
• HDU 4660. Mathematical Olympiad
• Livestream

Go To Considered Helpful

• Livestream

Brief Description

给定一个 r*c 的迷宫，要求构造一个长度最短的带 Goto 的指令序列，可以从起点走到终点。

(Small: r,c <= 10)
(Large: r,c <= 100)

Posted by xiaodao
Category: 日常