USACO 2015 US Open, Bronze Problem 2. Bessie Gets Even

原題下載

USACO2015OPEN-B2

答案

(Analysis by Nick Wu)

In a pure brute-force solution, we would try every possible combination of assignments of variables to values. There are 7 variables, with at most 20 values per variable, for a total of?207207?combinations. This is over one billion combinations to check, which is too many to check.

One approach you can try is to count the number of ways you can force the expression to be odd. When checking if a combination is odd, you can immediately note a couple things - for example, M must be odd. Also, if you recursively assign values to variables and you see that one of the three terms in the product is even, you can stop all combinations for variables that you haven't yet inspected.

There is a much faster approach though that removes the dependency on checking different combinations. Since you want to check if the product is even or odd, the important thing to know for each variable is how many even values that variable can take on, and how many odd values that variable can take on. Once you've done that, you can assign to each variable a parity and see if with those parities, the product is even. If so, you can count how many combinations there are with those parities, and then sum the parities.

With this approach, there are only?27=12827=128?combinations of parities to check, which is guaranteed to work quickly enough.

Here is Mark Gordon's code:

#include <iostream>
#include <cstdio>

using namespace std;

int num[256][2];

bool is_even(int x) {
  return x % 2 == 0;
}

int main() {
  freopen("geteven.in", "r", stdin);
  freopen("geteven.out", "w", stdout);

  int N;
  cin >> N;

  for (int i = 0; i < N; i++) {
    char letter;
    int val;
    cin >> letter >> val;

    if (is_even(val)) {
      num[letter][0]++;
    } else {
      num[letter][1]++;
    }
  }

  int result = 0;

  /* Try every possible way that the variables could be even or odd. */
  for(int B = 0; B < 2; B++)
  for(int E = 0; E < 2; E++)
  for(int S = 0; S < 2; S++)
  for(int I = 0; I < 2; I++)
  for(int G = 0; G < 2; G++)
  for(int O = 0; O < 2; O++)
  for(int M = 0; M < 2; M++) {
    if (is_even((B + E + S + S + I + E) * (G + O + E + S) * (M + O + O))) {
      /* If the expression is even then add the number of variable assignments
       * that have the variables odd/even.
       */
      result += num['B'][B] * num['E'][E] * num['S'][S] * num['I'][I] *
                num['G'][G] * num['O'][O] * num['M'][M];
    }
  }
  cout << result << endl;

  return 0;
}

以上就是關于【USACO 2015 US Open, Bronze Problem 2. Bessie Gets Even】的解答，如需了解學校/賽事/課程動態，可至翰林教育官網獲取更多信息。

往期文章閱讀推薦：

NOAI、UKOAI、USAAIO三大AI奧賽新賽季全面啟動：留學申請的“核武器”來了！

2026理工科競賽“大洗牌”：線上考試終結、報名門檻收緊、晉級規則重塑...你準備好了嗎？