AOJ2406 Al dente

問題リンク Al dente

• 解法

1番目の砂時計から順番に[T-E, T+E]の区間のどこかを図れるかを調べます。
T+Eが3000弱なので単純なループでも余裕ですが、
T-E <= x * k
となるような最小のkを
k = (T-E-1)/x + 1
として求めて、
T-E <= x*k <= T+E
となっているかを調べるとO(1)でチェックでき、オシャレです。

• ソース

import java.util.Scanner;

//Al dente
public class AOJ2406 {

	void run(){
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt(), T = sc.nextInt(), E = sc.nextInt();
		int[] a = new int[n+1];
		for(int i=1;i<=n;i++)a[i]=sc.nextInt();
		int res = -1;
		for(int i=1;i<=n&&res==-1;i++){
			int k = (T-E-1)/a[i]+1;
			if(T-E<=a[i]*k&&a[i]*k<=T+E)res=i;
		}
		System.out.println(res);
	}
	
	public static void main(String[] args) {
		new AOJ2406().run();
	}
}