Home » 国际竞赛 » Details

USACO 2021 February Contest, Gold Problem 3. Count the Cows

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

USACO 2021 February Contest, Gold Problem 3. Count the Cows

As is typical, Farmer John's cows have spread themselves out along his largest pasture, which can be regarded as a large 2D grid of square "cells" (picture a huge chessboard).

The pattern of cows across the pasture is quite fascinating. For every cell $(x, y)$ with $x \geq 0$ and $y \geq 0$ , there exists a cow at $(x, y)$ if for all integers $k \geq 0$ , the remainders when $⌊ \frac{x}{3^{k}} ⌋$ and $⌊ \frac{y}{3^{k}} ⌋$ are divided by three have the same parity. In other words, both of these remainders are odd (equal to $1$ ), or both of them are even (equal to $0$ or $2$ ). For example, the cells satisfying $0 \leq x, y < 9$ that contain cows are denoted by ones in the diagram below.

        x
    012345678

  0 101000101
  1 010000010
  2 101000101
  3 000101000
y 4 000010000
  5 000101000
  6 101000101
  7 010000010
  8 101000101

FJ is curious how many cows are present in certain regions of his pasture. He asks $Q$ queries, each consisting of three integers $x_{i}, y_{i}, d_{i}$ . For each query, FJ wants to know how many cows lie in the cells along the diagonal range from $(x_{i}, y_{i})$ to $(x_{i} + d_{i}, y_{i} + d_{i})$ (endpoints inclusive).

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

The first line contains $Q$ ( $1 \leq Q \leq 10^{4}$ ), the number of queries.The next $Q$ lines each contain three integers $d_{i}$ , $x_{i}$ , and $y_{i}$ ( $0 \leq x_{i}, y_{i}, d_{i} \leq 10^{18}$ ).

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

$Q$ lines, one for each query.

SAMPLE INPUT:

8
10 0 0
10 0 1
9 0 2
8 0 2
0 1 7
1 1 7
2 1 7
1000000000000000000 1000000000000000000 1000000000000000000

SAMPLE OUTPUT:

11
0
4
3
1
2
2
1000000000000000001

SCORING:

Test case 2 satisfies $d_{i} \leq 100$ for each query.
Test cases 3-6 satisfy $x + d = 3^{30} - 1$ and $y = 0$ for each query.
Test cases 7-12 satisfy no additional constraints.

Problem credits: Benjamin Qi

USACO 2021 February Contest, Gold Problem 3. Count the Cows 题解(翰林国际教育提供，仅供参考)

题解请注册或登录查看

[/hide]

(Analysis by Benjamin Qi)

Looking at the diagram provided in the sample case, the locations of the cows is essentially an X where each of the five squares that form the X are recursively replaced by Xes.

Subtask 2: Define $f (k, d i f)$ to be the number of cows $(x, y)$ in the square $[0, 3^{k}) \times [0, 3^{k})$ such that $x - y = d i f$ . We can do this in $O (k)$ time by reducing to $k - 1$ , as $gen_full$ does in the code below. Assume $d i f \geq 0$ .

Case 1: $d i f < 3^{k - 1}$

The diagram below displays the relevant positions for $k = 2, d i f = 2$ . In this case, $f (k, d i f) = 3 \cdot f (k - 1, d i f)$ .

        x
    012345678

  0 10*000101
  1 010.00010
  2 1010.0101
  3 00010*000
y 4 000010.00
  5 0001010.0
  6 10100010*
  7 010000010
  8 101000101

Case 2: $d i f \geq 3^{k - 1}$

The diagram below displays the relevant positions for $k = 2, d i f = 6$ . In this case, $f (k, d i f) = f (k - 1, d i f - 2 \cdot 3^{k - 1})$ .

        x
    012345678

  0 101000*01
  1 0100000*0
  2 10100010*
  3 000101000
y 4 000010000
  5 000101000
  6 101000101
  7 010000010
  8 101000101

Full solution: We use the same idea of reducing from $3^{k}$ to $3^{k - 1}$ . For the details, see $rec$ in the code below.

#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
 
vector<ll> po3 = [](){
	vector<ll> res{1};
	for (int i = 1; i < 40; ++i) 
		res.push_back(3*res.back());
	return res;
}();

ll full[40];
void gen_full(int k, ll dif) { 
	// count # of cows (x,y) in [0,3^k) x [0,3^k)
	// such that x-y=dif
	dif = abs(dif);
	if (k == 0) {
		full[k] = (dif == 0);
		return;
	}
	if (dif >= po3[k-1]) {
		gen_full(k-1,dif-2*po3[k-1]);
		full[k] = full[k-1];
	} else {
		gen_full(k-1,dif);
		full[k] = 3*full[k-1];
	}
}
 
ll rec(ll x, ll y, int k) {
	x %= po3[k], y %= po3[k];
	// count # of cows in [0,3^k) x [0,3^k)
	// on the segment from (x-min(x,y),y-min(x,y)) to (x,y)
	if (k == 0) return 1;
	if (x < y) swap(x,y);
	if (x-y >= po3[k-1]) {
		if (x < 2*po3[k-1]) return 0;
		if (y < po3[k-1]) return rec(x,y,k-1);
		if (y >= po3[k-1]) return full[k-1];
	}
	if (x < po3[k-1]) return rec(x,y,k-1);
	if (y < po3[k-1]) return full[k-1];
	if (x < 2*po3[k-1]) return full[k-1]+rec(x,y,k-1);
	if (y < 2*po3[k-1]) return 2*full[k-1];
	return 2*full[k-1]+rec(x,y,k-1);
}
ll diag(ll x, ll y) {
	if (x < 0 || y < 0) return 0;
	gen_full(39,x-y);
	return rec(x,y,39);
}
 
int main() {
	int Q; cin >> Q;
	while (Q--) {
		ll d,x,y; cin >> d >> x >> y;
		cout << diag(x+d,y+d)-diag(x-1,y-1) << "\n";
	}
}

Alternatively, we can ignore the diagram and do dynamic programming on the base-3 digits directly to count the number of $k \in [0, d]$ such that $(x + k, y + k)$ contains a cow. We determine the digits of $k$ from least significant to most significant. If we've determined the first $i$ digits so far, we should keep track of the following information:

whether $k < d % 3^{i}$ (0), $k = d % 3^{i}$ (1), or $k > d % 3^{i}$ (2) in $c m p$ .
whether $x % 3^{i} + k \geq 3^{i}$ in $x c$
whether $y % 3^{i} + k \geq 3^{i}$ in $y c$

#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;

#define F0R(i,a) for (int i = 0; i < a; ++i)
 
int main() {
	vector<ll> po3{1};
	for (int i = 1; i < 40; ++i) 
		po3.push_back(3*po3.back());
	array<array<array<ll,2>,2>,3> dp, DP;
	int Q; cin >> Q;
	while (Q--) {
		ll d,x,y; cin >> d >> x >> y;
		dp = {}; dp[1][0][0] = 1;
		F0R(i,39) {
			DP = {};
			int dd = d/po3[i]%3, xd = x/po3[i]%3, yd = y/po3[i]%3;
			F0R(cmp,3) F0R(xc,2) F0R(yc,2) F0R(j,3) {
				int XD = (xd+xc+j)%3, XC = (xd+xc+j)/3;
				int YD = (yd+yc+j)%3, YC = (yd+yc+j)/3;
				int CMP = cmp;
				if (j > dd) CMP = 2;
				if (j < dd) CMP = 0;
				if (XD%2 == YD%2)
					DP[CMP][XC][YC] += dp[cmp][xc][yc];
			}
			swap(dp,DP);
		}
		cout << dp[0][0][0]+dp[1][0][0] << "\n";
	}
}

Danny Mittal's code:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class LargestPasture {
 
    public static void main(String[] args) throws IOException {
        long[] pow3 = new long[39];
        pow3[0] = 1;
        for (int e = 1; e <= 38; e++) {
            pow3[e] = 3L * pow3[e - 1];
        }
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder out = new StringBuilder();
        int n = Integer.parseInt(in.readLine());
        for (int j = 1; j <= n; j++) {
            StringTokenizer tokenizer = new StringTokenizer(in.readLine());
            long d = Long.parseLong(tokenizer.nextToken());
            long x = Long.parseLong(tokenizer.nextToken());
            long y = Long.parseLong(tokenizer.nextToken());
            long[][][][][] dp = new long[3][2][3][2][40];
            for (int a = 0; a < 2; a++) {
                for (int c = 0; c < 2; c++) {
                    dp[a][0][c][0][0] = 1;
                }
            }
            for (int e = 0; e <= 38; e++) {
                int lim = (int) ((d / pow3[e]) % 3L);
                int xDigit = (int) ((x / pow3[e]) % 3L);
                int yDigit = (int) ((y / pow3[e]) % 3L);
                for (int h = 0; h < 2; h++) {
                    for (int digit = 0; digit < 3; digit++) {
                        for (int k = 0; k < 2; k++) {
                            int hNext = (xDigit + digit + h) / 3;
                            int xNewDigit = (xDigit + digit + h) % 3;
                            int kNext = (yDigit + digit + k) / 3;
                            int yNewDigit = (yDigit + digit + k) % 3;
                            int compare;
                            if (digit < lim) {
                                compare = 0;
                            } else if (digit == lim) {
                                compare = 1;
                            } else {
                                compare = 2;
                            }
                            if (xNewDigit % 2 == yNewDigit % 2) {
                                for (int a = 0; a < 2; a++) {
                                    for (int c = 0; c < 2; c++) {
                                        dp[a][hNext][c][kNext][e + 1] += dp[a == 1 ? compare : 0][h][c == 1 ? compare : 0][k][e];
                                    }
                                }
                            }
                        }
                    }
                }
            }
            out.append(dp[1][0][1][0][39]).append('\n');
        }
        System.out.print(out);
    }
}

[/hide]