Home » 国际竞赛 » Details

USACO 2021 February Contest, Gold Problem 1. Stone Game

Category: 国际竞赛, 计算机国际竞赛 Date: 2022年7月4日下午4:54

USACO 2021 February Contest, Gold Problem 1. Stone Game

Bessie and Elsie are playing a game with? $N$ ?( $1 \leq N \leq 10^{5}$ ) piles of stones, where the? $i$ -th pile has? $a_{i}$ ?stones for each? $1 \leq i \leq N$ ?( $1 \leq a_{i} \leq 10^{6}$ ). The two cows alternate turns, with Bessie going first.

First, Bessie chooses some positive integer? $s_{1}$ ?and removes? $s_{1}$ ?stones from some pile with at least? $s_{1}$ ?stones.
Then Elsie chooses some positive integer? $s_{2}$ ?such that? $s_{1}$ ?divides? $s_{2}$ ?and removes? $s_{2}$ ?stones from some pile with at least? $s_{2}$ ?stones.
Then Bessie chooses some positive integer? $s_{3}$ ?such that? $s_{2}$ ?divides? $s_{3}$ ?and removes? $s_{3}$ ?stones from some pile with at least? $s_{3}$ ?stones and so on.
In general,? $s_{i}$ , the number of stones removed on turn? $i$ , must divide? $s_{i + 1}$ .

The first cow who is unable to remove stones on her turn loses.

Compute the number of ways Bessie can remove stones on her first turn in order to guarantee a win (meaning that there exists a strategy such that Bessie wins regardless of what choices Elsie makes). Two ways of removing stones are considered to be different if they remove a different number of stones or they remove stones from different piles.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains? $N$ .The second line contains? $N$ ?space-separated integers? $a_{1}, \dots, a_{N}$ .

OUTPUT FORMAT (print output to the terminal / stdout):

Print the number of ways Bessie can remove stones on her first turn in order to guarantee a win.Note that the large size of integers involved in this problem may require the use of 64-bit integer data types (e.g., a "long long" in C/C++).

SAMPLE INPUT:

1
7

SAMPLE OUTPUT:

Bessie wins if she removes? $4$ ,? $5$ ,? $6$ , or? $7$ ?stones from the only pile. Then the game terminates immediately.

SAMPLE INPUT:

6
3 2 3 2 3 1

SAMPLE OUTPUT:

Bessie wins if she removes? $2$ ?or? $3$ ?stones from any pile. Then the two players will alternate turns removing the same number of stones, with Bessie making the last move.

SCORING:

Test cases 3-5 satisfy? $N = 2$ .
Test cases 6-10 satisfy? $N, a_{i} \leq 100$ .
Test cases 11-20 satisfy no additional constraints.

Problem credits: Benjamin Qi

?USACO 2021 February Contest, Gold Problem 1. Stone Game 题解(翰林国际教育提供，仅供参考)

题解请注册或登录查看

[/hide]

(Analysis by Benjamin Qi)

We can think of a valid move in the game as follows:

Dividing all of the pile sizes by some positive integer.
Subtracting one from some pile with a positive size.

We claim that a state in the game is losing for the first player iff for each? $x \geq 1$ , the number of piles of size? $x$ ?is even. In this case, the second player can win by simply mirroring the moves of the first player.

In all other states, let? $x$ ?the maximum pile size such that the number of piles of size exactly? $x$ ?is odd. Then the first player wins if she removes that pile.

Now suppose that Bessie removes? $x$ ?stones from some pile on her first turn. Then we need to count the number of integers among the sequence? $S_{x} = [⌊ \frac{a_{1}}{x} ⌋, ⌊ \frac{a_{2}}{x} ⌋, ⌊ \frac{a_{3}}{x} ⌋, \dots, ⌊ \frac{a_{n}}{x} ⌋]$ ?such that when decreased by one, every positive integer in the sequence occurs an even number of times (ignoring zero).

So Bessie wins if she picks? $t > 0$ ?such that

$t$ ?occurs an odd number of times in? $S_{x}$
If? $t > 1$ ,? $t - 1$ ?occurs an odd number of times in? $S_{x}$
No other positive integer occurs an odd number of times in? $S_{x}$ .

For each? $x$ ?and? $t$ , the number of occurrences of? $t$ ?in? $S_{x}$ ?is equal to the number of integers in the input sequence that are in the range? $[x t, x (t + 1) - 1]$ . For a fixed? $x$ , we can compute this quantity for all relevant? $t$ ?in? $O (\frac{max a_{i}}{x})$ ?time using prefix sums. After this, it's just a matter of checking which numbers appear an odd number of times in? $S_{x}$ ?and updating the answer accordingly.

Time Complexity:? $O (N + (max a_{i}) \log (max a_{i}))$ .

#include <bits/stdc++.h>
using namespace std;
 
int main() {
	int N; cin >> N;
	vector<int> A(N); 
	int mx = 0;
	for (int& t: A) {
		cin >> t;
		mx = max(mx,t);
	}
 
	vector<int> cum(mx+1); for (int t: A) ++cum[t];
	for (int i = 1; i <= mx; ++i) cum[i] += cum[i-1];
	auto getCum = [&](int ind) { // number of elements of A <= ind
		if (ind > mx) return cum.back();
		return cum[ind];
	};
 
	long long ans = 0;
	for (int x = 1; x <= mx; ++x) {
		vector<int> counts{0};
		for (int t = 1; x*t <= mx; ++t)
			counts.push_back(getCum(x*(t+1)-1)-getCum(x*t-1));
		vector<int> odd; 
		for (int t = 1; t < counts.size(); ++t) 
			if (counts[t]&1) odd.push_back(t);
		if (odd == vector<int>{1} || (odd.size() == 2 && odd[0]+1 == odd[1]))
			ans += counts[odd.back()];
	}
	cout << ans << "\n";
}

Danny Mittal's Code (somewhat different):

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class StoneGame {
 
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(in.readLine());
        Integer[] piles = new Integer[n + 1];
        StringTokenizer tokenizer = new StringTokenizer(in.readLine());
        for (int j = 0; j < n; j++) {
            piles[j] = Integer.parseInt(tokenizer.nextToken());
        }
        piles[n] = 0;
        Arrays.sort(piles);
        int[] diffSums = new int[1000001];
        int[] indexSums = new int[1000001];
        for (int j = n; j >= 1; j -= 2) {
            diffSums[piles[j]]++;
            diffSums[piles[j - 1]]--;
            indexSums[piles[j]] += j;
            indexSums[piles[j - 1]] -= j;
        }
        long answer = 0;
        for (int k = 1000000; k > 0; k--) {
            diffSums[k - 1] += diffSums[k];
            indexSums[k - 1] += indexSums[k];
            int diff = 0;
            int index = 0;
            for (int m = k; m <= 1000000; m += k) {
                diff += diffSums[m];
                index += indexSums[m];
            }
            if (diff == 1) {
                int upper = n;
                int lower = index;
                while (upper > lower) {
                    int mid = (upper + lower + 1) / 2;
                    if (piles[mid] / k == piles[index] / k) {
                        lower = mid;
                    } else {
                        upper = mid - 1;
                    }
                }
                answer += upper - index + 1;
            }
        }
        System.out.println(answer);
    }
}

[/hide]