Dual Problem: Date Occurrence and Binary String Entropy

Problem A: Date Occurrence

You are given a fixed array of 100 digits. The array is (with 0‐indexing) as follows:

5 6 8 6 9 1 6 1 2 4 9 1 9 8 2 3 6 4 7 7 5 9 5 0 3 8 7 5 8 1 5 8 6 1 8 3 0 3 7 9 2 7 0 5 8 8 5 7 0 9 9 1 9 4 4 6 8 6 3 3 8 5 1 6 3 4 6 7 0 7 8 2 7 6 8 9 5 6 5 6 1 4 0 1 0 0 9 4 8 0 9 1 2 8 5 0 2 5 3 3

A subsequence is obtained by selecting some indices in increasing order. We are interested in finding subsequences of length 8 that, when concatenated in order, form a date string in the format yyyymmdd. In addition, the following conditions must be met:

1. The first 4 digits must be exactly 2023 (i.e. the year is fixed to 2023).
2. The following 2 digits represent the month (with a leading zero if needed) and must be between 01 and 12.
3. The last 2 digits represent the day (with a leading zero if needed) and must be a valid day of the corresponding month in 2023 (taking into account the different lengths of months, and note that 2023 is not a leap year).

Your task is to count how many distinct valid dates (i.e. distinct 2023mmdd strings) can be obtained as a subsequence from the given array. For the same date found in multiple ways, count it only once.

---

Problem B: 01-String Entropy

For a binary string S of length n where S = x₁x₂…x_n (each x_i is either 0 or 1), the Shannon entropy is defined as:

$$H(S) = -\Big( x \log_{2}\Big(\frac{x}{n}\Big) + (n - x) \log_{2}\Big(\frac{n - x}{n}\Big) \Big), $$

where x is the number of 0's in the string and therefore n - x is the number of 1's. Note that \log_2 denotes the logarithm base 2. For example, for S = 100, one may compute the entropy accordingly.

Now consider a binary string of length 23333333 whose entropy is given as $$11625907.5798,$$

and in which the number of 0's is less than the number of 1's. Your task is to determine how many 0's appear in this binary string. (Output the answer as an integer.)

---

Input Format of the Combined Problem: The input consists of a single integer T. If T = 1, solve Problem A; if T = 2, solve Problem B.

inputFormat

The input consists of a single integer. Enter 1 to get the answer for the Date Occurrence problem (Problem A) and 2 to get the answer for the Binary String Entropy problem (Problem B).

outputFormat

Output a single integer which is the answer to the chosen problem.

sample

1

4