torus711 のアレ

主に競技プログラミングの問題について書きます.PC 以外だと数式が表示されないかもしれないです

Codeforces #232, Division 2, B : On Corruption and Numbers

概要

次のようなクエリ ( n, l, r ) を t ( ≦ 1,000 ) 個処理せよ

  • クエリ ( n, l, r ) := n を [ l, r ] に含まれる整数の和として表現できるかどうか判定し、"Yes" / "No" で示せ

解法

 n, l, r の値がかなり大きくなり得るので、ある程度効率的な方法を考える必要があります。
 [ l, r ] に含まれる整数 k 個の和は区間 [ kl, kr ] に収まります。逆に [ kl, kr ] 内に n を含むような k が存在すれば、クエリの答えは "Yes" であると分かります。そのような k が存在するとすれば、そのときの k は n を r で切り上げ整数除算した結果と一致します。そうして求まった k について、条件式

  • k * l <= n && n <= k * r

を評価した結果が、クエリの答えとなります。

コード

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

bool solve( const int n, const int l, const int r )
{
	const int k = ( n + r - 1 ) / r;
	return k * l <= n && n <= k * r;
}

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

	int t;
	cin >> t;

	REP( i, 0, t )
	{
		int n, l, r;
		cin >> n >> l >> r;
		cout << ( solve( n, l, r ) ? "Yes" : "No" ) << endl;
	}

	return 0;
}