うにゅーん、って感じだ

だいたいのコンテストサイトで橙か赤か黄です、よく C#を書きます。

TOJ Extra Problems Contest #1

これはなに

大学で学部 2 年生向けの C 言語の実習授業の TA をしていて、そこで普通の課題だと物足りないプロ向けに extra 問題を作って置いといたやつです(もちろん、成績には反映されない本当にただのおまけです)(一部改題しています)。
ジャッジシステムは学内からしかアクセスできないので、ジャッジは公開していません。

難易度はどれも ABC-D 前後だと思います。
答えが知りたい方は @rian_tkb とかいう人が twitter で解法を呟いていたりするので探していただいても良いですし、近いうちに解説記事も書くと思います。
半分くらい手で写しているので、間違っていそうなところがあったら教えてください。

twitter.com

ちなみに、受講生は以下の言語縛りで解いて(解かされて)いました。

  • C89 に 1行コメント(// ... )と long long型 を足したもの(GCC 拡張は使用不可)



A - Counting Triangles

実行時間制限 : 1 sec

問題文

入力された正整数 {X} に対して、以下の 2 つの値を半角スペース区切りで出力してください。

  • 全ての辺の長さが正整数かつ一番長い辺の長さが {X} であるような三角形の個数
  • 全ての辺の長さが正整数かつ互いに異なり、一番長い辺の長さが {X} であるような三角形の個数

ただし、回転させたり反転させたりすることで同じ三角形となるものは重複して数えないものとします。

入力

X

制約

  • {1 \le X \le 2 \times 10^9}

出力

  • 入力された整数に対応する 2 つの値を半角スペース区切りで出力してください。

入出力例

入力例 1:

1

出力例 1:

1 0

入力例 2:

5

出力例 2:

9 2

入力例 3:

987654321

出力例 3:

243865264941319921 243865263459838440



B - Contiguous Sum

実行時間制限 : 1 sec

問題文

正整数 {N} に対し、和が {N} になる連続した {1} 以上 {N} 未満の整数の組合せを全て出力してください。

入力

T
(case_1)
(case_2)
:
(case_T)

  • 入力は {T} 個のケースからなり、各ケースでは整数 {N} が与えられます。

制約

  • {1 \le T \le 1{,}000}
  • 各ケースに対し、
    • {2 \le N \le 10^8}

出力

  • 各ケースの答えを改行で区切って出力してください。
    • それぞれの解は、{\displaystyle \sum_{k=l}^{r}k = N} なる {(l, r)} に対し、 l-r という形で出力してください。
      • 解が複数ある場合は、 {l} の小さい順に出力してください。
      • 解が存在しない場合は何も出力しないでください。

入出力例

入力例 1:

3
27
8
9

出力例 1:

2-7
8-10
13-14
2-4
4-5

入力例 2:

1
99999999

出力例 2:

309-14145
592-14154
4999-14999
5002-15000
6539-15580
9877-17249
10224-17450
11669-18334
18347-23164
19859-24379
28337-31669
31672-34685
39319-41784
40307-42715
43894-46115
54097-55914
61464-63069
65604-67110
75447-76760
80487-81719
89454-90564
109557-110465
121244-122065
124132-124934
151879-152535
164714-165319
228092-228529
243104-243514
329882-330184
364827-365100
456512-456730
494949-495150
504952-505149
684859-685004
729859-729995
990049-990149
1010052-1010150
1369827-1369899
1515119-1515184
3030287-3030319
4545444-4545465
5555547-5555564
9090904-9090914
11111107-11111115
16666664-16666669
33333332-33333334
49999999-50000000



C - Dividing Combination

実行時間制限 : 1 sec

問題文

{{}_N \mathrm{C}_K} が整数 {P \ (P \ge 2)} で何回割れるかを求めてください。
より正確には、{P^X \mid {}_N \mathrm{C}_K \ \land \ P^{X + 1} \nmid {}_N \mathrm{C}_K} を満たすような非負整数 {X} を求めてください。

入力

T
(case_1)
(case_2)
:
(case_T)

  • 入力は {T} 個のケースからなり、各ケースでは整数 {N, K, P} がこの順に半角スペース区切りで与えられます。

制約

  • {1 \le T \le 2{,}000}
  • 各ケースに対し、
    • {0 \le K \le N \le 10^9}
    • {2 \le P \le 10^9}

出力

  • 各ケースの答えを改行で区切って出力してください。

入出力例

入力例 1:

6
5 3 5
5 3 10
18 4 6
0 0 2
1000000000 1000000 24
1000000000 500000000 998244353

出力例 1:

1
1
2
0
3
1



D - Palindromic Numbers

実行時間制限 : 1 sec

問題文

{L} 以上 {R} 以下の整数のうち、十進法における回文数であるような整数の個数を求めてください。

入力

T
(case_1)
(case_2)
:
(case_T)

  • 入力は {T} 個のケースからなり、各ケースでは整数 {L, R} がこの順に半角スペース区切りで与えられます。

制約

  • {1 \le T \le 10{,}000}
  • 各ケースに対し、
    • {0 \le L \le R \le 10^{16}}

出力

  • 各ケースの答えを改行で区切って出力してください。

入出力例

入力例 1:

6
0 100
101 101
12345 67890
1234333 1234999
99999999 9999999999999999
0 10000000000000000

出力例 1:

19
1
555
0
199980001
199999999