某岛

… : "…アッカリ~ン . .. . " .. .
August 12, 2019

Google Code Jam 2019 World Finals

Google Code Jam 2019 World Finals

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

Board Meeting

Brief Description

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

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

Idea

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

Sorting Permutation Unit

Brief Description

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

(k <= 30, n <= 50, s = 450)
(Small: p = 20)
(Large: p = 5)

Won’t Sum

Juggle Stuggle Part

Brief Description

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

Idea

Go To Considered Helpful

Brief Description

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

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