torus711 のアレ

主に競技プログラミングの問題について書きます

Codeforces #151, A : Buggy Sorting

概要

誤りを含むソートアルゴリズムが提示される。
配列サイズ n が与えられるので、正しくソートできないテストケースを出力せよ。
そのようなケースが存在しない場合は -1 を出力せよ。

解法

提示されたアルゴリズムバブルソートです。
バブルソートでは、末尾方向から要素が確定していくので、ループの終了位置を一つずつ短くすることができます。
ところが、提示されたアルゴリズムは先頭方向から短くしているため、先頭要素は一度しか比較・交換されません。
素数が 2 以下ならば正しくソートされますが、それ以外の場合は降順ソートされた列を与えられると正しくソートされません。

コード

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

	int n;
	cin >> n;

	if ( n < 3 )
	{
		cout << -1 << endl;
	}
	else
	{
		for ( int i = n; 0 < i; i-- )
		{
			if ( i != n )
			{
				cout << ' ';
			}
			cout << i;
		}
		cout << endl;
	}

	return 0;
}