2015 Open Silver Problem 1 Bessie Goes Moo

Official Problem Statement

Bessie Goes Moo

Problem

In the problem, "Bessie Goes Moo", the task is to count the number of distinct strings that Bessie the cow can create. Bessie has a vocabulary of six different sounds, denoted as 'A', 'B', 'C', 'D', 'E', 'F'. Each sound has a certain length, and Bessie can only make a certain number of sounds per day. However, once she uses a sound, she can decide to elongate it by doubling its length at no extra cost.

The task is to determine how many different sounds Bessie can make given these conditions.

Input Format

The input starts with seven integers: N, A, B, C, D, E, F.

   N (1 <= N <= 100,000): the maximum length of any sound that Bessie can make in one day.
   A-F (1 <= A-F <= N): the initial lengths of each of the six sounds that Bessie can make.

Output Format

Print the number of distinct sound sequences Bessie can create, modulo 1,000,000,009.

Solution

To solve this problem, dynamic programming can be used. The main idea is to keep track of the number of ways to make a sound of each length for each sound Bessie can make.

A 2D dp array is created where dp[i][j] represents the number of ways to make a sound of length j using sounds A through i. The dp array is filled iteratively, where for each sound, it counts the number of ways to make a sound of each length from 1 to N.

Then, to account for the ability to elongate a sound by doubling its length, the dp array is updated by adding the number of ways to make a sound of length j using sounds A through i-1, doubled, to dp[i][j].

Finally, to find the total number of distinct sound sequences Bessie can make, the dp array is summed up for each sound at every length, and this sum is printed as the answer.

The complexity of this solution is O(N) for each of the 6 sounds, thus O(6N) in total, which is feasible within the given problem constraints.

Code

C++

#include <iostream>
#include <cstdio>

using namespace std;

// Array to store the number of each letter and its possible remainders
long long letterCounts[256][7];

int main() {
  // Redirect input and output streams to files
  freopen("bgm.in", "r", stdin);
  freopen("bgm.out", "w", stdout);

  // Read the number of entries
  int N;
  cin >> N;

  // For each entry, read the letter and its value, then increment the count for the respective remainder
  for (int i = 0; i < N; i++) {
    char letter;
    int val;
    cin >> letter >> val;
    letterCounts[letter][(val % 7 + 7) % 7]++;
  }

  // Result variable to store the total number of good sequences
  long long result = 0;

  // For each possible remainder (0-6) of the seven letters B, E, S, I, G, O, M
  // Check if their combination forms a good sequence (remainder is 0), and if so, increment the result
  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 += letterCounts['B'][B] * letterCounts['E'][E] * letterCounts['S'][S] * letterCounts['I'][I] *
                            letterCounts['G'][G] * letterCounts['O'][O] * letterCounts['M'][M];
                }
              }

  // Print the total number of good sequences
  cout << result << endl;

  return 0;
}

Java

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        // Initialize reader and writer
        BufferedReader br = new BufferedReader(new FileReader("bgm.in"));
        PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter("bgm.out")));

        // Initialize letterCounts array
        long[][] letterCounts = new long[256][7];

        // Read N from input
        int N = Integer.parseInt(br.readLine());

        // Populate letterCounts array
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            char letter = st.nextToken().charAt(0);
            int val = Integer.parseInt(st.nextToken());
            letterCounts[letter][(val % 7 + 7) % 7]++;
        }

        // Initialize result
        long result = 0;

        // Iterate over each possible remainder for each letter
        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 += letterCounts['B'][B] * letterCounts['E'][E] * letterCounts['S'][S] *
                                                  letterCounts['I'][I] * letterCounts['G'][G] * letterCounts['O'][O] *
                                                  letterCounts['M'][M];
                                    }
                                }

        // Write result to output
        pw.println(result);
        pw.close();
    }
}

Python

with open("bgm.in") as f:
    N = int(f.readline())
    counts = {ch: [0]*7 for ch in 'BESIGOM'}
    for _ in range(N):
        letter, val = f.readline().split()
        val = int(val)
        counts[letter][(val % 7 + 7) % 7] += 1

result = 0
for B in range(7):
    for E in range(7):
        for S in range(7):
            for I in range(7):
                for G in range(7):
                    for O in range(7):
                        for M in range(7):
                            if (((B + E + S + S + I + E) * (G + O + E + S) * (M + O + O)) % 7 == 0):
                                result += (counts['B'][B] * counts['E'][E] * counts['S'][S] * 
                                           counts['I'][I] * counts['G'][G] * counts['O'][O] * counts['M'][M])

with open("bgm.out", "w") as f:
    f.write(str(result))