Home » 国际竞赛 » Details

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

Category: 国际竞赛, 计算机国际竞赛 Date: 2017年12月8日下午3:45

原题下载

USACO2015OPEN-S1

答案

(Analysis by Nick Wu)

There are $500^{7}$ 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 $7^{7}$ 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;
}

以上就是关于【USACO 2015 US Open, Silver Problem 1. Bessie Goes Moo】的解答，如需了解学校/赛事/课程动态，可至翰林教育官网获取更多信息。

往期文章阅读推荐：

美国AI奥赛首次新增低龄组！2027 USAAIO报名中，2月正式开考！

不考编程实操？2026 CAICP人工智能能力认证首轮11月22日开考，备考指南速递！