Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-03-20SRM368, SRM369 (Practice)

SRM 369 AbsSequence

|  SRM 369 AbsSequence - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 369 AbsSequence - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=8178


  • 方針を検討
    • 少し実験してみると、3つ組で考えたとき規則性があることに気づく
    • コーナーケースに注意してシミュレーションする
  • (a, b, c) で aが最大かつcが最小になるまで回す
    • min(a, b) / (c * 2) で規則が変わる瞬間が分かる
    • (min(a, b) / (c * 2)) * 3 が回すターン数を超えていたらその周期の中に答えはある
import java.util.ArrayList;
import java.util.List;

public class AbsSequence {
	
	public class Stat {
		long turn;
		long a, b;
		Stat(long t, long x, long y) {
			turn = t;
			a = x;
			b = y;
		}
	}
	
	public void processOne(long[] a) {
		long n = Math.abs(a[1] - a[2]);
		a[0] = a[1];
		a[1] = a[2];
		a[2] = n;
	}
	

	public String[] getElements(String first, String second, String[] indices) {
		
		long a0 = Long.valueOf(first);
		long a1 = Long.valueOf(second);
		
		long[] f3 = new long[]{a0, a1, Math.abs(a0 - a1)};
		int len = indices.length;
		String[] ans = new String[len];
		for (int i = 0 ; i < len ; i++) {
			ans[i] = "";
			long wanttoknow = Long.valueOf(indices[i]);
			
			long[] g3 = f3.clone();
			
			
			long res = -1;
			while (wanttoknow >= 3) {
				long min = Math.min(g3[0], Math.min(g3[1], g3[2]));
				long max = Math.max(g3[0], Math.max(g3[1], g3[2]));
				if (min == g3[2] && max == g3[0]) {
					if (min == 0) {
						if (wanttoknow % 3 == 2) {
							res = 0;
						} else {
							res = g3[1];
						}
						break;
					} else {
						long secondmin = Math.min(g3[1], g3[0]);
						long canrep = Math.min(secondmin / (min * 2), wanttoknow / 3);
						if (canrep >= 1) {
							long willproc = canrep * 3;
							wanttoknow -= willproc;
							g3[0] -= min * 2 * canrep;
							g3[1] -= min * 2 * canrep;
						} else {
							processOne(g3);
							wanttoknow--;
						}
					}
				} else {
					processOne(g3);
					wanttoknow--;
				}
			}
			if (res == -1) {
				ans[i] = String.valueOf(g3[(int)wanttoknow]);
			} else {
				ans[i] = String.valueOf(res);
			}
		}
		return ans;
	}
}