USACO 2015 US Open, Silver Problem 1. Bessie Goes Moo

原題下載

USACO2015OPEN-S1

答案

(Analysis by Nick Wu)

There are?5007?different combinations to check, which is far too many.

However, just like with the bronze version of this problem, where we were only concerned about the parity of the answer, we are only concerned with the result of the product mod 7, so we only care about the values of the variables mod 7. This gives us?77?different combinations to check, which will run in time.

Here is Mark Gordon's code.

#include <iostream>
#include <cstdio>

using namespace std;

long long num[256][7];

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

  int N;
  cin >> N;

  for (int i = 0; i < N; i++) {
    char letter;
    int val;
    cin >> letter >> val;
    num[letter][(val % 7 + 7) % 7]++;
  }

  long long result = 0;

  /* Try every possible residue mod 7 for the variables. */
  for(int B = 0; B < 7; B++)
  for(int E = 0; E < 7; E++)
  for(int S = 0; S < 7; S++)
  for(int I = 0; I < 7; I++)
  for(int G = 0; G < 7; G++)
  for(int O = 0; O < 7; O++)
  for(int M = 0; M < 7; M++) {
    if (((B + E + S + S + I + E) * (G + O + E + S) * (M + O + O)) % 7 == 0) {
      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;
}

以上就是關(guān)于【USACO 2015 US Open, Silver Problem 1. Bessie Goes Moo】的解答，如需了解學(xué)校/賽事/課程動態(tài)，可至翰林教育官網(wǎng)獲取更多信息。

往期文章閱讀推薦：

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

2026理工科競賽“大洗牌”：線上考試終結(jié)、報(bào)名門檻收緊、晉級規(guī)則重塑...你準(zhǔn)備好了嗎？