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
- 3Blue1Brown, This problem seems hard, then it doesn’t, but it really is
- HDU 4660. Mathematical Olympiad
- Livestream
Go To Considered Helpful
Brief Description
給定一個 r*c 的迷宮,要求構造一個長度最短的帶 Goto 的指令序列,可以從起點走到終點。
(Small: r,c <= 10)
(Large: r,c <= 100)