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】的解答，如需了解学校/赛事/课程动态，可至翰林教育官网获取更多信息。

往期文章阅读推荐：

2026 NOAI国际AI奥赛中国站即将开考！赛事地址&日程已出！

2027 USAAIO美国AI奥赛启动报名！MIT/谷歌/Jane Street集体站台！