前往
大廳
主題

ZeroJudge - a364: 2. 神秘的進位問題 解題心得

Not In My Back Yard | 2021-09-26 00:00:13 | 巴幣 0 | 人氣 240

題目連結:


題目大意:
有一個特別的進位制:
每個正整數 N 可以表為 abc 三個數字相連(沒有空白隔開),其中 a > b > c ≧ 0 且 N = C(a, 3) + C(b, 2) + C(c, 1),又其中 C(n, k) 代表著二項式係數即 n 個物品取 k 個出來的方法數,而當 n < k 時 C(n, k) 之值定義為 0。

不過我們可以看到以上的進位制會使一些整數有多種表示法。這邊只考慮字典序最小的表示法,即 a 、 b 之值要盡可能地小。



現在輸入第一列給定一正整數 m(1 ≦ m ≦ 10),代表有 m 筆測試資料,每筆佔一列。每列給定一正整數 N(0 ≦ N ≦ 500),試問 N 於上面提及的進位制中之表示法為何?



範例輸入:
輸入範例 1:
4
0
1
2
200

輸入範例 2:
3
18
19
20


範例輸出:
輸出範例 1:
210
310
320
1187

輸出範例 2:
542
543
610


解題思維:
就是單純地窮舉即可,而因為 a 、 b 要盡可能地小因此我們只能從 a = 2 開始窮舉,即對每個 a 值窮舉 b = 1 ~ a - 1 之間的所有數字,再對每個 b 值窮舉 c = 0 ~ b - 1 之間的所有數字。

然後計算每個數組 (a, b, c) 的 C(a, 3) + C(b, 2) + C(c, 1) 值是否恰好為 N,也就是判斷
a(a - 1)(a - 2) ÷ 6 + b(b - 1) ÷ 2 + c
是否為 N。

如果是就直接輸出 a 、 b 、 c 此時的值即可。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

相關創作

更多創作