コンテンツにスキップ

DOJ Beginner Contest 11 B - Even Roasting

サイト
DOJ
コンテスト
DOJ Beginner Contest 11
問題
B - Even Roasting

一列に並んだ NN 枚の肉があり、焼き加減はすべて 00 です。1 回の操作では、左か右の端を選び、火力 PP(1≤P≤1091 \le P \le 10^9)を決めます。選んだ側から dd 番目の肉の焼き加減が max⁡(0,P−d+1)\max(0, P - d + 1) 増えます。

すべての肉の焼き加減を同じ正の整数にするための最小の操作回数と、その操作を出力する問題です。

左から火力 11 で 1 回焼けば、焼き加減が 11 になります。答えは 11 回です。

1 回の操作では足りません。端から 1 番目の肉は PP、2 番目の肉は P−1P - 1 増えるので、この 2 枚の焼き加減が必ず異なります。

2 回なら作れます。左から火力 NN で焼くと、焼き加減は左から N,N−1,…,1N, N - 1, \dots, 1 増えます。右から火力 NN で焼くと、左から 1,2,…,N1, 2, \dots, N 増えます。合わせると、どの肉も N+1N + 1 になります。

Python
for _ in range(int(input())):
N = int(input())
if N == 1:
print(1)
print(1, 1)
else:
print(2)
print(1, N)
print(2, N)