No.413 +5,000,000pts

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : / 解いたユーザー数 44
作問者 : yuppe19 🐱yuppe19 🐱 / テスター : 37zigen37zigen

2 ProblemId : 1175 / 出題時の順位表

問題文

プログラミングコンテストで、こんな問題が出題されました。
与えられた正整数 $d$ に対し、$t^{2} + t \le d$ を満たす最大の整数 $t$ を求めよ。
・$1 \le d \le 10^{18}$

コンテストに出場したあなたは、他の参加者の64ビット C++11/gcc4.8.5(yukicoderで動作するC++11)で書かれた、こんな答案を見つけました。
(32ビット環境では意図した動作が起こらないようです)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll calc(ll d) {
  return (ll)((-1 + sqrt(1 + 4*d)) / 2.0);
}

int main() {
  ll d; cin >> d;
  ll t = calc(d);
  cout << t << endl;
  return 0;
}

あなたは、このコードはうまくチャレンジすれば成功する(失敗するテストケースを見つけること)と思いました。
チャレンジに成功するテストケースを 10 万件生成してください。
※10 万 $= 10^{5} = 100000$

入力

この問題に入力はありません。

出力

チャレンジに成功する $d$ の値を一件一行で 10 万件出力し、最後に改行してください。
ジャッジは、
・1 件目から 10 万件目までを見ます。10 万件に満たない場合の動作は未定義です。
・10 万件の中に「$d$ の値に重複がある場合」、「$d$ が適切な範囲に無いものを含んでいる場合」、「失敗するチャレンジが含まれている場合」は、 いずれも不正解(WA)を返します。

出力サンプル

次のようなフォーマットで数値を出力してください。
19980604
19980727
19980904
19980930
19981114
19981123
.
.
.
20000507
20010625
ここで出力されている値は、あくまで出力イメージを明確にする用途で使われており、正しい答えであるとは限りません。
全部で 10 万行、出力してください。

提出ページヘ