Find Divisible [ Educational Codeforces Round 57 (Div. 2) A ]

codeforces.com

問題

範囲 L,R (1<=L<=R<=998244353) が与えられる。
L,R の範囲内にあるような x,y (x!=y) で、y を x で割り切ることができるものを出力せよ。
なお、そのような x,y が存在することは保証されている。

考察

x!=y であるような x,y の存在が保証されているので、範囲には少なくとも 2 個の数字が含まれます。
L=10, R=10 のような入力は来ないということですね。

次に、問題を読み換えることを考えます。

・y を x で割り切ることができる

ではなく、

・y/x をしたときに 1以上の商 が得られるかどうか

と考えます。

得られる商のうち、最も小さいものは 1 です。しかし、商として 1 を得るためには y と x が同じ数でなければならず、問題の x!=y という条件に当てはまらないので、商が 1 となるように x,y を選ぶことはできません。となれば、問題で指定されているような x,y は、y/x の商が少なくとも 2 以上になるような x,y ということになります。

次に、商が 2 のときを考えます。商として 2 を得るためには、x=k のとき y=2k である必要があります。これならば x!=y となるように x,y を選ぶことができるので、選択肢に入ります。仮に、商が 2 となるように x,y を選べることが保証されているならば、範囲の右端である R は少なくとも L の2倍でなければなりません。式で表すと L=k のとき少なくとも R>=2k である必要があるということです。

次に、商が 3 のときを考えます。x=k のとき y=3k、かつ、L=k のとき R>=3k です。L=k, R>=3k という範囲には、L=k, R>=2k が含まれています。商として 3 を得られるような範囲のときには、必ず商として 2 を得られる、ということです。このことは商が 4 であっても 100 であっても同様です。

これらのことから、与えられる範囲 L,R は L=k のとき R>=2k 、すなわち、y/x の商が 2 になるような x,y が存在するような範囲であることが保証されています。ただし、商が 3 以上の場合については、必ずしも保証されていません。

よって、x=L, y=2L を出力すればよいです。このとき、2L が範囲内であることは R>=2k によって保障されています。

コード

void solve (FastScanner in, PrintWriter out) {
	
	int n = in.nextInt();
	
	for (int i=0; i<n; i++) {
		int L = in.nextInt(), R = in.nextInt();
		out.println(L+" "+2*L);
	}

}