2019 ICPC TOPC 簡易講評 === ###### tags: `ICPC` `TOPC` `TOPC2019` [題組資源](https://drive.google.com/open?id=1mg3UvMZUE1l3JbuG6fLmLoVS7dn4ztxv) 本次競賽賽題由交通大學退役選手陳昇暉、莊昕宸、黃右萱協助裁判長命題,並由交通大學資工系蔡孟宗教授,以及中正大學、台灣大學、清華大學、交通大學多位退役選手審查、校對、檢驗測資與撰寫解答驗題。因本次賽事並無爭取到任何經費,在此特別感謝他們的辛勞與無私奉獻。 以下為 2019 ICPC Asia Taiwan Online Programming Contest 的競賽主席兼裁判長謝旻錚對此題組的簡易講評。 ## Problem A -- Animal King Election Problem setter: Min-Zheng Shieh 本題預設目標答對率 100% ,最終答對率近 99% 。題目說由九個公民選出下一任國王,候選人只有兩位: Tiger 跟 Lion 。而且題目保證一定都會投有效票:不是給 Tiger 就是給 Lion 。要求算出得票比較多的下一任國王。 做法有很多種,可以直接統計誰票多,就印誰。附贈的範例一行解答則是將九張票做排序,然後輸出中間的那一個,這也能得到答案。 ```kotlin= fun main() = println((1..9).map{readLine()!!}.sorted()[4]) ``` 在檢視答錯的同學程式碼時,發現部分同學不知道字串大小寫可能被視為相異的字串,因此答錯。如果有人未來以目標答對率 100% 命題時,請特別留意字串最好都小寫。 ## Problem B -- Bags Problem setter: Min-Zheng Shieh 本題預設目標答對率 90% ,最終答對率近 94% 。題目說要收 $n$ 個化學廢料,不能把相異的廢料收在同一個袋子,必須要用不同的袋子裝。問需要多少個袋子。其實很單純的,統計相異物品有幾個即可。最簡單的方式如參考解答,直接用個簡單集合類的容器裝,並且印出其中有幾個即可。 ```kotlin= private fun nextLine() = readLine()!! private fun nextInt() = nextLine().toInt() private fun nextToks() = nextLine().split(" ") private fun nextInts() = nextToks().map{it.toInt()} fun main() { val n = nextInt() val cans = HashSet<Int>(nextInts()) println(cans.size) } ``` 這題要做一行解,比較討厭的是那個 $n$ 要讀。 ```kotlin= fun main(){readLine()?.also{println(readLine()!!.split(" ").distinct().size)}} ``` ```python= print(input()[0:0]+'%d'%len(set(input().split()))) ``` 命題時有考量可能隊伍不會使用容器,另法是:「排序後,靠檢查有多少組相鄰兩個數字不同,再加上一就是答案」。 ## Problem C -- Change Making Problem Setter: Min-Zheng Shieh 考量這是個經典題,只要知道原來的題目怎樣 Dynamic Programming 會通過的隊伍,應該能通過。目標答對率設定為 70% ,但最終通過的只有約 60% 。演算法課程很可能會提到 Change making problem ,只要能夠計算最佳解,並依照題面敘述計算 Greedy 解,在有限的範圍內要找出第一個不同處,應該不困難。低年級的同學沒有做出這題,請不要太過沮喪。 ```kotlin= private fun nextLine() = readLine()!! private fun nextInt() = nextLine().toInt() private fun nextToks() = nextLine().split(" ").filter{it!=""} private fun nextInts() = nextToks().map{it.toInt()} fun main() { var dp = ArrayList<Int>(listOf(0)) var g = ArrayList<Int>(listOf(0)) val n = nextInt() val coin = nextInts() if (n != coin.size) throw Exception("input incorrect") for(i in 1..100000) { dp.add( coin.filter{it <= i}.map{dp[i-it]+1}.min() ?: 0 ) g.add( g[i-coin.filter{it <= i}.max()!!]+1 ) if (dp[i] != g[i]) { println(i) return } } println(-1) } ``` ## Problem D -- Disrupting Defense Problem setter: Min-Zheng Shieh 目標答對率設定為 50% ,做法並沒有用到什麼特殊的資料結構。但最終答對率僅約 28% ,出題者還要多學學。先觀察如果相同價值觀(value)的敵人超過半數,則不可能擊敗他們,因為你每次只能打倒兩個價值觀不同的,無法找到夠多跟他們價值觀相異的敵人來打倒他們。但如果相同價值觀的人沒有過半數,則每次選擇一個擁有在當下「人數最多」的價值觀。這種價值觀的敵人,必然有一個跟相異價值觀的人相臨。如果沒有,那根本就通通信仰同一價值,跟原先沒過半的假定矛盾。此時如隨便打倒一個此價值觀的敵人和另外一個人,則必然不會造成剩餘敵人中,具有某一價值觀的人超過半數(此部分證明略過)。因此能夠繼續執行這演算法,直到剩下兩個相異價值觀的敵人。因此最後一口氣打倒他們兩個,就完成攻略了。 時間複雜度:$O(n^2)$。因為 $n$ 次攻擊,每次攻擊先掃一次 $O(n)$ 統計價值觀,再掃一次 $O(n)$ 找最多的那種,最後再掃一次 $O(n)$ 找到該打倒的兩個敵人,並花至多 $O(n)$ 時間維護資料。 ```kotlin= private fun nextLine() = readLine()!! private fun nextInt() = nextLine().toInt() private fun nextToks() = nextLine().split(" ") private fun nextInts() = nextToks().map{it.toInt()} fun main() { val (n,k) = nextInts() val a = nextInts().map{it-1} var cnt = IntArray(k) a.forEach{cnt[it] += 1} if (n/2 < cnt.max()?:0) { println(-1) return } var used = BooleanArray(n) for (rnd in 1..(n/2)) { val m = cnt.max()!! val t = cnt.indexOf(m) val pos = a.mapIndexed{i, x -> if(x==t) i else -1} .filter{it>=0 && !used[it]} for (p in pos) { var q = (p+1) % n while (used[q]) q = (q+1) % n if (a[q] != a[p]) { used[q] = true used[p] = true cnt[t] -= 1 cnt[a[q]] -= 1 println("${p+1} ${q+1}") break } } } } ``` ## Problem E -- Explosion Problem setter: Min-Zheng Shieh 目標答對率 <1% ,最終無人答對。對命題人而言是嘔心瀝血之作了,感謝最後試著解題的隊伍。這題作為難題,會要求隊伍需要具備特定知識:[最小包圓](http://mathworld.wolfram.com/MinimalEnclosingCircle.html)以及[凸包](https://zh.wikipedia.org/wiki/%E5%87%B8%E5%8C%85)或極角排序。但以命題人的感受,這並不是特別難碰到的題材。 題目要炸掉一個半徑為 $r$ 的圓。除了一個選定點外,其餘所有點必須被該圓包覆,由範例測資可以確認摸到邊就算。 首先,先計算所有點的最小包圓。如果其半徑比 $r$ 小,那肯定有解。先直接假想炸在最小包圓的圓心上,然後選一個在最小包圓邊上的點,讓該點「倖免於難」:將圓心沿著該點往最小圓心的方向推,剛剛好推「超過」即可。 如果最小包圓半徑不比 $r$ 小,則需要排除一個點,也就是安全的點,之後重新計算最小包圓,看看是否不大於 $r$ 。如果不大於,那就找到一組解了。先觀察那些點可以做為這個安全點:只有最小包圓邊上的點才可以,不然最小包圓跟原來一樣,你不能炸,不是全滅就是炸完剩下兩個以上。 但問題是最小包圓上的點,可能有很多個,在本題我們選用的測試資料,最小包圓上可能有超過一千個點 (這就是為什麼產生了 Problem I 的原因)。可是其中其實只有至多三個點需要考慮:因為只有至多三個點,拿掉以後最小包圓會變小。 為何是三個?因為把最小包圓邊上的點拿來做凸包 (此時極角座標排序即可得到) ,這是一個圓內接多邊形。對應的圓周角如果不是銳角,拿掉也不影響最小包圓。但圓內接多邊形,至多只有三個角可以是銳角,也就是我們需要檢測的三個。 以下為範例程式碼: ```kotlin= import java.math.BigInteger import java.math.BigDecimal import kotlin.random.Random import kotlin.math.atan2 import java.util.TreeSet private fun nextLine() = readLine()!! private fun nextInt() = nextLine().toInt() private fun nextToks() = nextLine().split(" ") private fun nextInts() = nextToks().map{it.toInt()} data class BigFrac(val num: BigInteger, val den: BigInteger = BigInteger.ONE) typealias Point = Pair<BigFrac, BigFrac> val half = BigFrac(BigInteger.ONE, BigInteger.TWO) fun BigFrac.conanical(): BigFrac { val gcd = num.gcd(den) if (den < BigInteger.ZERO) return BigFrac(-num/gcd, -den/gcd) return BigFrac(num/gcd, den/gcd) } operator fun BigFrac.unaryMinus() = BigFrac(-num, den) operator fun BigFrac.plus(x: BigFrac): BigFrac = BigFrac(num*x.den + den*x.num, den*x.den)//.conanical() operator fun BigFrac.minus(x: BigFrac): BigFrac = BigFrac(num*x.den - den*x.num, den*x.den)//.conanical() operator fun BigFrac.times(x: BigFrac): BigFrac = BigFrac(num*x.num, den*x.den)//.conanical() operator fun BigFrac.div(x: BigFrac): BigFrac = BigFrac(num*x.den, den*x.num)//.conanical() operator fun BigFrac.compareTo(x: BigFrac): Int = (this - x).num.compareTo(BigInteger.ZERO) fun BigFrac.sqrt(scale: Int = 100): BigFrac { val conan = conanical() val (x, rx) = conan.num.sqrtAndRemainder() val (y, ry) = conan.den.sqrtAndRemainder() if (rx == BigInteger.ZERO && ry == BigInteger.ZERO) return BigFrac(x, y) val frac = toBigDecimal(scale*2).sqrt(java.math.MathContext.DECIMAL128) val d = BigInteger.TEN.pow(frac.scale()) val n = (frac * d.toBigDecimal()).toBigInteger() return BigFrac(n, d) } operator fun Point.plus(x: Point): Point = Pair(first + x.first, second + x.second) operator fun Point.minus(x: Point): Point = Pair(first - x.first, second - x.second) // inner product: % operator fun Point.rem(x: Point): BigFrac = first * x.first + second * x.second infix fun Point.dot(x: Point): BigFrac = first * x.first + second * x.second // cross product: * operator fun Point.times(x: Point): BigFrac = first * x.second - second * x.first infix fun Point.cross(x: Point): BigFrac = first * x.second - second * x.first // scalar product: BigFrac * Point operator fun BigFrac.times(x: Point): Point = Pair(this * x.first, this * x.second) // scalar product: Point * BigFrac operator fun Point.times(x: BigFrac): Point = Pair(first * x, second * x) fun Point.mag2(): BigFrac = this dot this fun Point.mag(): BigFrac = mag2().sqrt() fun BigInteger.toBigFrac() = BigFrac(this) fun Int.toBigFrac() = this.toBigInteger().toBigFrac() fun BigFrac.toBigDecimal(scale: Int = 80) = BigDecimal(num, scale) / BigDecimal(den, scale) fun BigFrac.toDouble() = toBigDecimal().toDouble() private fun nextFracs() = nextToks().map{it.toBigInteger().toBigFrac()} fun ext(p: Point, q: Point, r: Point): Point { val (x1, y1) = p val (x2, y2) = q val (x3, y3) = r val m1 = p dot p val m2 = q dot q val m3 = r dot r val num1 = m1 * y2 + m2 * y3 + m3 * y1 - y1 * m2 - y2 * m3 - y3 * m1 val num2 = x1 * m2 + x2 * m3 + x3 * m1 - m1 * x2 - m2 * x3 - m3 * x1 val den = x1 * y2 + x2 * y3 + x3 * y1 - y1 * x2 - y2 * x3 - y3 * x1 return Pair(half * num1 / den, half * num2 / den) } fun center(pts: ArrayList<Point>, pass: Int, n: Int): Point { if (pass == 3) return ext(pts[0], pts[1], pts[2]) if (n == 1) return pts[0] var ret = half * (pts[0] + pts[1]) if (n == 2) return ret var radius = half * (pts[0] - pts[1]) var dist2 = radius dot radius for (i in 2 until n) { val r = pts[i]-ret if (dist2 < r dot r) { pts[pass] = pts[i].also{pts[i] = pts[pass]} ret = center(pts, pass+1, i+1) radius = pts[0] - ret dist2 = radius dot radius } } return ret } fun nextPoints(n: Int): ArrayList<Point> { var fracs: List<List<BigFrac>> = (1..n).map{nextFracs()} return ArrayList<Point>(fracs.map{Point(it[0],it[1])}) } fun BigFrac.toReadable(scale: Int = 10): String = this.toBigDecimal(scale).toPlainString() fun Point.toReadable(scale: Int = 10): String = first.toReadable(scale) + " " + second.toReadable(scale) class PolarCmp(val c: Point): Comparator<Point> { override fun compare(a: Point, b: Point): Int { val da = a - c val db = b - c val angleA = atan2(da.second.toDouble(), da.first.toDouble()) val angleB = atan2(db.second.toDouble(), db.first.toDouble()) return angleA.compareTo(angleB) } } fun solve(pts: ArrayList<Point>, safe: Point, r2: BigFrac): String { var n = pts.size - 1 val pos = pts.indexOf(safe) pts[n] = pts[pos].also{pts[pos] = pts[n]} var nc = center(pts, 0, n) var nr2 = (nc - pts[0]).mag2() if (nr2 > r2) return "-1" return "${safe.first.num} ${safe.second.num}\n" + "${nc.first.toReadable(20)} ${nc.second.toReadable(20)}" } fun main() { val (n, _r) = nextInts() val r = _r.toBigFrac() var pts = nextPoints(n) pts.shuffle() var c = center(pts, 0, pts.size) val radius = c - pts[0] val r2 = radius dot radius var ans = "-1" if (r2 < r * r) { val tune = 16 val epsilon = BigFrac(BigInteger.ONE,BigInteger.TEN.pow(tune)) val one = BigFrac(BigInteger.ONE) c = c + (r/radius.mag()-one+epsilon) * radius ans = "${pts[0].first.num} ${pts[0].second.num}\n" + "${c.first.toReadable(tune*2)} ${c.second.toReadable(tune*2)}" } else { val cand = TreeSet<Point>(PolarCmp(c)) pts.filter{val dx = it - c val x2 = dx dot dx x2 >= r2}.forEach{cand.add(it)} for (p in cand) { val s = cand.higher(p) ?: cand.first() val t = cand.lower(p) ?: cand.last() if (s - p dot t - p > BigInteger.ZERO.toBigFrac()) { // at most 3 points pass this val attemp = solve(pts, p, r*r) if (attemp != "-1") { ans = attemp break } } } } println(ans) } ``` ## Problem F -- Factorization Problem setter: Yu-Hsuan Huang (NCTU_Teumessian) 目標答對率 10% ,主要考量是數論類的題目,台灣少出。最終答對率 5% ,或許大家的工具箱內還沒有這些裝備,要準備與國際隊伍競爭的同學,可以趁機補一下。當初命題者給了我一個完全超過我的數學知識的做法,因此我自己收到題目後先試著自己做做看。呃,給你兩數的積($b_0\cdot b_1$)還有和($b_0+b_1$)要你算出兩數 $b_0,b_1$ 為何?這不就想辦法算出兩數的差($b_0-b_1$)然後跟兩數的和拿來解方程式。因此,先想到的作法是 $\sqrt{(b_0+b_1)^2-4(b_0\cdot b_1)}$ 算出兩數的差,再回頭解 $b_0$ 跟 $b_1$。 因此問題就回到「在餘質數 $p$ 下開根號」了。大抵上這題在手上有 [Tonelli-Shanks](https://en.wikipedia.org/wiki/Tonelli%E2%80%93Shanks_algorithm) 或是 [Cipolla](https://en.wikipedia.org/wiki/Cipolla%27s_algorithm) 這些演算法的隊伍,應該只要數學推一下後就毫無難度,頂多處理一下 $p=2$ 的特例。此外,由於開根號太針對性,我也認真想了一下,比較通用的方法是否能解。為此我們選了算出 $\mathbb{Z}_p^\times$ 的[原根 (primitive root)](https://en.wikipedia.org/wiki/Primitive_root_modulo_n)後,套用[離散對數(Discrete logarithm)](https://en.wikipedia.org/wiki/Discrete_logarithm)演算法,如[Baby-step Giant-step](https://en.wikipedia.org/wiki/Baby-step_giant-step)法來撰寫另解,確保時限內能夠讓此類算法通過。 ## Problem G -- Gifted Bafuko Problem setter: Sheng-Huei Chen (ICPC World Finalist, NCTU_Fox) 目標答對率 5% ,最終答對率約 1% ,意外變成王選試題。方法說穿了很簡單,就是找到一個 Leaf 之後,開始長樹,長不出去就砍掉重練,換一條邊再長一次,頂多三次。因為有唯一解,所以能長出來的只有一棵。 Leaf 如何找呢?由於題目上有限制點數 $n$ 至少 7 且 $G_T$ 所有節點 degree 至多 3,因此如果有一個點在 $G_U$ 的 degree 是 2,則它必然是一個 leaf 。如果都沒有結點 degree 是 $2$ ,那 degree 是 3 的必然是一個 leaf 。 長樹基本上就是修改 DFS,紀錄目前走進點的邊 ($u$,$v$) ,接下來檢查 $v$ 的 $G_U$ 鄰居中,有多少是 $u$ 在 $G_U$ 的鄰居,這些點才能是 $G_T$ 中 $v$ 的鄰居。並且還要是沒拜訪過、也不在 $u$ 在 $G_T$ 中的鄰居。這部分的檢查請大家自己推演一下。但如此我們就可以開始建構整棵樹了。 建構的過程中,如果一次長出超過 2 條邊,那就違背 degree 最多 3 的限制,可以直接停掉不長。如果到最後仍有點沒長出來,則這也不是我們要的答案。 ```kotlin= private fun nextLine() = readLine()!! private fun nextInt() = nextLine().toInt() private fun nextToks() = nextLine().split(" ") private fun nextInts() = nextToks().map{it.toInt()} fun dfs(u: Int, v: Int, adj: ArrayList<IntArray>, ans: Array<ArrayList<Int>>, visited: BooleanArray): Int { var ret = 1 visited[v] = true val cand = adj[v].filter{!visited[it] && u in adj[it] && it !in ans[u]} if (cand.size>2) return -1 ans[v].add(u) ans[v].addAll(cand) ans[v].sort() for (w in cand) ret += dfs(v, w, adj, ans, visited) return ret } fun solve() { val n = nextInt() var adj = ArrayList<IntArray>() var leaf = -1 var cap = 3 var buf = StringBuilder() for (v in 1..n) { adj.add(nextInts().drop(1).map{it-1}.toIntArray()) if (adj.last().size <= cap) { leaf = v-1 cap = adj.last().size } } for (v in adj[leaf]) { var ans = Array<ArrayList<Int>>(n){ArrayList<Int>()} var visited = BooleanArray(n){it==leaf} ans[leaf].add(v) val size = dfs(leaf, v, adj, ans, visited) if (size == n-1) { for (lst in ans) buf.append("${lst.size} ${lst.map{it+1}.joinToString(" ")}\n") break } } print(buf) } fun main() = (1..nextInt()).forEach{solve()} ``` ## Problem H -- Hotel Problem setter: Hsin-Chen Chuang (ICPC World Finalist, NCTU_Fox) 目標答對率 15% ,結果約 7%。有點驚嚇的低答對率。這是一題單點更新、區間查詢線段樹就可以做的題目。線段樹確實對中階以及中階之下的隊伍來說,是一個未必有接觸的題材。但中前段隊伍怎麼可能不會線段樹?因此答對率這麼低,出乎意料。 線段樹是一種資料結構,用來儲存一個序列: $a_1,\cdots,a_n$,而序列元素的資料型態,可以進行具備結合律的運算 $\oplus$,線段樹可提供快速 ($O(\log n)$) 的計算出任一個連續片段 $a_\ell\oplus a_{\ell+1} \oplus \cdots \oplus a_r$ 的值,並且提供快速 ($O(\log n)$) 更新序列中單一元素。在某些特定情況下,也能夠用一些技法達到快速 ($O(\log n)$) 的區間修改操作。常見的例子有,拿來求整數數列的片段最大值、最小值、總和等等,因為這些操作 ($\max$, $\min$, $+$) 都具備結合律。 本題首先要利用高度變化時,不會發生與相鄰高度一樣的保證。將實際上表示的序列改成 $d_i = h_{i+1} - h_i$ 。則原問題變成是在詢問, $d_\ell,\ldots,d_{r-1}$ 中,最長的一段「正負號至多換一次,且先正後負」的最長片段長度。由此我們開始定義一個資料型態 `Seg(size, b, e, ans, ba, ea)` ,其中 size 代表這個資料是對應到多長的序列片段,b代表片段開頭的序列元素,e代表片段結尾的序列元素,ans代表這個片段的最佳解,ba 代表從開頭開始的片段之「正負號至多換一次,且先正後負」最長長度,ea則代表從結尾往前的片段之「正負號至多換一次,且先正後負」最長長度。而這種新資料,我們定義將其相接的操作為 `concat` ,而這個操作是具備有結合律的,更新時沿路重算即可。剩下的事情,我們就交給線段樹了,請參考下述參考程式碼。 ```kotlin= private fun nextLine() = readLine()!! private fun nextToks() = nextLine().split(" ") private fun nextInt() = nextLine().toInt() private fun nextInts() = nextToks().map{it.toInt()} data class Seg(val size: Int = 0, var b: Int = 1, var e: Int = 1, val ans: Int = 1, val ba: Int = 1, val ea: Int = 1) infix fun Seg.concat(x: Seg): Seg { val sz = size + x.size val ok = e > 0 || x.b < 0 var newBA = if (ba == size && ok) ba+x.ba else ba var newEA = if (x.ea == x.size && ok) ea+x.ea else x.ea val best = maxOf(ans, x.ans, if(ok) ea+x.ba else 0) return Seg(sz, b, x.e, best, newBA, newEA) } const val H = 18 var t = Array<ArrayList<Seg>>(H){ArrayList<Seg>()} fun update(pos: Int, d: Int) { if (pos < 0 || pos >= t[0].size) return t[0][pos].b += d t[0][pos].e += d for (h in 1 until H) { val q = pos shr h if (q >= t[h].size) break t[h][q] = t[h-1][2*q] concat t[h-1][2*q+1] } } fun query(h: Int, L: Int, R: Int): Seg { if (L==R-1) return t[0][L] val ls = L.shr(h-1) val rs = (R-1).shr(h-1) if (ls==rs) return query(h-1, L, R) if (R==L+1.shl(h)) return t[h][L.shr(h)] val M = rs.shl(h-1) return query(h-1, L, M) concat query(h-1, M, R) } fun query(L: Int, R: Int): Int { if (L==R) return 1 if (L+1==R) return 2 return query(H-1, L, R).ans + 1 } fun solve() { val n = nextInt() var seq = nextInts() var buf = ArrayList<String>() for (x in t) x.clear() for (i in 1 until n) t[0].add(Seg(1, seq[i]-seq[i-1], seq[i]-seq[i-1])) for (i in 1 until H) for (j in 0 until t[i-1].size-1 step 2) t[i].add(t[i-1][j] concat t[i-1][j+1]) val q = nextInt() for (i in 1..q) { val (op, L, R) = nextInts() if (op == 1) { update(L-1,R) update(L,-R) } else buf.add("${query(L,R)}") } println(buf.joinToString("\n")) } fun main() = (1..nextInt()).forEach{solve()} ``` ## Problem I -- Integral Points Problem setter: Min-Zheng Shieh 目標答對率 30% ,最終答對率約 16% 。這一題是 Problem E 準備測試資料過程時的副產品。事前很難估難度,因為出題者也不知道怎樣做才能及時做完,只想藉機宣揚本地打表這項技法,畢竟月球表面可以放很多東西。能夠成為答案的半徑,應該多能寫成 $k(n^2+m^2)$ 這種形式,請參考[畢氏三元數](https://en.wikipedia.org/wiki/Pythagorean_triple),找一些很多組$k$, $m$ 跟 $n$ 產生出重複的來試,然後暴力檢查有多少個 Integral Points。我希望當初驗題的吳宗達可以提供他的想法,因為他寫了一個沒有在本地作業的程式碼並在時限內通過。 範例程式是事前先找出一個 $r$ ,然後認真的把圓上所有整數點給找出來,再印出答案。 ```kotlin= fun main() { val n = readLine()!!.toInt() val r = 5928325L val r2 = r*r var squares = ArrayList<Long>() var output = HashSet<Pair<Long,Long>>() for (i in 0L..r) { val q = i*i val p = r2 - q squares.add(q) val j = squares.binarySearch(p).toLong() if (j >= 0) { output.add(Pair(i, j)) output.add(Pair(j, i)) output.add(Pair(-i, j)) output.add(Pair(-j, i)) output.add(Pair(i, -j)) output.add(Pair(j, -i)) output.add(Pair(-i, -j)) output.add(Pair(-j, -i)) } if (output.size >= n) break } println(r) output.take(n).forEach{println("${it.first} ${it.second}")} } ```