fork download
copy 
  1. /*
  2. 	ideone上でケース1000個全部流すと途中で切られてRuntimeErrorになるので、
  3. 	500個ずつくらいに分けて流してね
  4. */
  5.  
  6. import java.io.BufferedReader;
  7. import java.io.IOException;
  8. import java.io.InputStreamReader;
  9. import java.util.ArrayList;
  10. import java.util.List;
  11.  
  12. class Ideone {
  13. 	/**
  14. 	 * s(n) = s(0)*r^n + n*d となる r と d を返す
  15. 	 * @param s 調べる数列。インデックスはゼロから始まり、３つ以上の項があると信じるｗ
  16. 	 * @return  s(0)と r と d を (s(0), r, d) = (0, 1, 2) にパックして返す。nullなら等差・等比数列ではなかった。
  17. 	 */
  18. 	public static int[] getParamOfSeries(Integer[] s) {
  19. 		boolean flag = true;
  20.  
  21. 		// 等差数列か調べる
  22. 		int d = s[1] - s[0];
  23. 		for (int i = 2 ; flag && i < s.length ; i++) {
  24. 			if (d != s[i] - s[i-1]) flag = false;
  25. 		}
  26. 		if (flag) return new int[] {s[0], 1, d}; // 等差数列だった
  27.  
  28. 		// 等比数列か調べる
  29. 		/*try {
  30. 			flag = true;
  31. 			double r = (double) s[1] / (double) s[0];
  32. 			for (int i = 2 ; flag && i < s.length ; i++) {
  33. 				if (r != (double) s[i] / (double) s[i-1]) flag = false;
  34. 			}
  35. 			if (flag) return new int[] {s[0], (int) r, 0}; // 等比数列だった
  36. 		} catch (Exception e) { return null; } // 多分、ゼロ除算エラーなので等比数列ではなかった
  37. 		*/
  38.  
  39. 		return null; // どれでもなかった
  40. 	}
  41.  
  42. 	public static long[] makeSeriesFromParams(int[][] params, int begin, int end) {
  43. 		long[] result = new long[end - begin + 1];
  44. 		int i = 0;
  45. 		for (int n = begin ; n <= end ; n++) {
  46. 			int j = n / params.length,
  47. 				m = n % params.length;
  48. 			result[i++] = (long) (params[m][0]*Math.pow(params[m][1], j) + params[m][2]*j);
  49. 		}
  50. 		return result;
  51. 	}
  52.  
  53. 	public static void main(String[] args) throws IOException {
  54. 		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  55.  
  56. 		String line;
  57. 		while (null != (line = br.readLine())) {
  58. 			// 数列とパラメータの読み取り
  59. 			String[] terms = line.split(" ");
  60. 			int idx = Integer.parseInt(terms[0]);
  61. 			int begin = Integer.parseInt(terms[2])-1,
  62. 				end = Integer.parseInt(terms[3])-1;
  63. 			long expSum = Long.parseLong(terms[4]);
  64. 			String[] os = terms[1].split(",");
  65. 			int[] o = new int[os.length];
  66. 			for (int i = 0 ; i < os.length ; i++) o[i] = Integer.parseInt(os[i]);
  67. 			os = null;
  68. 			int N = o.length / 3; // 循環長の最大
  69.  
  70. 			// 循環の調査
  71. 			int L;
  72. 			int[][] params = null;
  73. 			boolean isFound = false;
  74. 			for (L = 1 ; L <= N ; L++) { // L は循環長
  75. 				boolean flag = true;
  76. 				params = new int[L][3];
  77. 				List<Integer> list = new ArrayList<>();
  78. 				for (int p = 0 ; p < L ; p++) { // p は循環内でのオフセット位置
  79. 					list.clear();
  80. 					for (int i = p ; i < o.length ; i += L) list.add(o[i]);
  81. 					int[] param = getParamOfSeries((Integer[])list.toArray(new Integer[0]));
  82. 					if (null == param) { // この循環長Lにおけるオフセット位置pでは数列が求まらなかった
  83. 						flag = false;
  84. 						break;
  85. 					} else { // 数列が求められた
  86. 						params[p][0] = param[0];
  87. 						params[p][1] = param[1];
  88. 						params[p][2] = param[2];
  89. 					}
  90. 				}
  91. 				if (flag) { // 全てのオフセット位置で数列が求められた
  92. 					isFound = true;
  93. 					break;
  94. 				}
  95. 			}
  96.  
  97. 			if (!isFound) { // 全てが数列となる循環長が見つからなかった
  98. 				System.out.println(idx+" : NOT FOUND!!");
  99. 			} else { // 循環と全数列が見つかった
  100. 				long[] c = makeSeriesFromParams(params, begin, end);
  101. 				long sum = 0;
  102. 				for (long v : c) sum += v;
  103. 				if (sum != expSum) {
  104. 					System.out.println(idx+" : Expecred="+expSum+", Obtained="+sum);
  105. 					for (int l = 0 ; l < params.length ; l++) {
  106. 						System.out.println(" ("+l+") : s(0)="+params[l][0]+", r="+params[l][1]+", d="+params[l][2]);
  107. 					}
  108. 					//for (long v : c) System.out.print(v+",");
  109. 					System.out.println("\n-----------------");
  110. 				}
  111. 			}
  112. 		}
  113. 	}
  114. }
Success #stdin #stdout 0.14s 380608KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
101 : Expecred=2654, Obtained=2655
 (0) : s(0)=82, r=1, d=83

-----------------
104 : Expecred=154, Obtained=155
 (0) : s(0)=37, r=1, d=0
 (1) : s(0)=9, r=1, d=9
 (2) : s(0)=23, r=1, d=0
 (3) : s(0)=34, r=1, d=0
 (4) : s(0)=16, r=1, d=0
 (5) : s(0)=14, r=1, d=0

-----------------
109 : Expecred=6084, Obtained=6085
 (0) : s(0)=60, r=1, d=48
 (1) : s(0)=41, r=1, d=48
 (2) : s(0)=6, r=1, d=48
 (3) : s(0)=37, r=1, d=48

-----------------
416 : Expecred=2636, Obtained=2635
 (0) : s(0)=55, r=1, d=50
 (1) : s(0)=27, r=1, d=50
 (2) : s(0)=5, r=1, d=50
 (3) : s(0)=49, r=1, d=50

-----------------
425 : Expecred=3499, Obtained=3498
 (0) : s(0)=6, r=1, d=0
 (1) : s(0)=48, r=1, d=12

-----------------
436 : Expecred=35452, Obtained=35453
 (0) : s(0)=86, r=1, d=64
 (1) : s(0)=40, r=1, d=64
 (2) : s(0)=25, r=1, d=64

-----------------
https://ideone.com/rvgQIM
codeIQ「中学入試から：数列の和」提出解答……難しかったよ？(ΦωΦ)
language:
Java (HotSpot 12)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!