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)