Codeforces #185, Division 1, A ( Division 2, C ) : The Closest Pair

問題文

http://codeforces.com/contest/312/problem/C

概要

平面上の n 個の点の内、最も近いものの距離を求めるプログラムを書いた。（問題文参照）
このアルゴリズムに於ける tot というカウントが k を超える場合、このプログラムは TLE してしまう。
プログラムを TLE させる入力を作成せよ。
そのような入力が存在しない場合はその旨を表示せよ。

解法

提示されたアルゴリズムは、二点の x 座標の差が暫定の最短距離以上になったときに内側のループを break します。
すべての点が相異なるという制約から、最短距離が 1 未満になることはありません。
従って、x = t となる直線上に点を配置すると一度も break されずにループが回ることになり、最も tot が大きくなる入力となります。
この場合でも tot が k 以下ならば TLE させることはできません。

コード

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )

int main()
{
	cin.tie( 0 );
	ios::sync_with_stdio( false );

	int n, k;
	cin >> n >> k;

	int tot = 0;
	REP( i, 0, n )
	{
		REP( j, i + 1, n )
		{
			tot++;
		}
	}

	if ( tot <= k )
	{
		cout << "no solution" << endl;
		return 0;
	}

	REP( i, 0, n )
	{
		cout << "0 " << i << endl;
	}

	return 0;
}