USACO 2016 January Contest, Silver Problem 2. Subsequences Summing to Sevens

Category: 計算機國際競賽 Date: 2017年11月10日下午4:25

原題下載

USACO2016-JAN-S2

答案

(Analysis by Nick Wu)

In this problem, we have a list of numbers. We want to find a sublist of numbers where the sum of the numbers is divisible by 7.

Define a prefix of a list to be the first K numbers of the list. Note that any sublist of numbers can be obtained by taking some prefix of the original list and removing a smaller prefix of the list. Note furthermore that if you take the sums of the two prefixes, they have the same remainder when divided by 7.

Therefore, for every prefix, we can compute the sum of the numbers in the prefix modulo 7, and keep track of the shortest and longest prefixes that when summed are equivalent to? $x$ ?modulo 7 for? $0 < x < 7$ . The answer is then the maximum difference between the lengths of the shortest and longest prefixes over all? $x$ .

Here is my Java code demonstrating this.

import java.io.*;
import java.util.*;
public class div7 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new FileReader("div7.in"));
		PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter("div7.out")));
		
		int n = Integer.parseInt(br.readLine());
		int[] first = new int[7];
		int[] last = new int[7];
		Arrays.fill(first, Integer.MAX_VALUE);
		first[0] = 0;
		int currPref = 0;
		for(int i = 1; i <= n; i++) {
			currPref += Integer.parseInt(br.readLine());
			currPref %= 7;
			first[currPref] = Math.min(first[currPref], i);
			last[currPref] = i;
		}
		int ret = 0;
		for(int i = 0; i < 7; i++) {
			if(first[i] <= n) {
				ret = Math.max(ret, last[i] - first[i]);
			}
		}
		pw.println(ret);
		pw.close();
	}
}

以上就是關于【USACO 2016 January Contest, Silver Problem 2. Subsequences Summing to Sevens】的解答，如需了解學校/賽事/課程動態(tài)，可至翰林教育官網(wǎng)獲取更多信息。

往期文章閱讀推薦：

2026 NOAI國際AI奧賽中國站即將開考！賽事地址&日程已出！

2027 USAAIO美國AI奧賽啟動報名！MIT/谷歌/Jane Street集體站臺！