Official

B - 11/11 Editorial by en_translator


There are two approaches to solve this problem.

  1. For each date in a year, determine if it has a repdigit date.
  2. For each possible repdigit date, determine if it exists.

We describe each approach.

1. Determine if each date has a repdigit date

A year in AtCoder kingdom has \(\displaystyle\sum _ {i=1} ^ ND _ i=D _ 1+D _ 2+\cdots+D _ N\) days, from day \(1\) of month \(1\) through day \(D_N\) of day \(1\).

The problem can be solved by enumerating these dates and count how many of them are repdigit dates.

One can determine if a date is a repdigit date by, for instance, convert the month and day value to strings and check if their concatenation consists of only one character.

The following is sample code.

N = int(input())
D = [*map(int, input().split())]

ans = 0
for i, d in enumerate(D):
    month_str = str(i + 1)
    for x in range(d):
        day_str = str(x + 1)
        if len(set(month_str + day_str)) == 1:
            ans += 1
            
print(ans)
#include <iostream>
#include <vector>
#include <set>

using namespace std;

int main() {
    int N;
    cin >> N;
    vector<int> D(N);
    for (auto &&d : D)
        cin >> d;

    int ans = 0;
    for (int m = 1; m <= N; ++m) {
        string month = to_string(m);
        for (int d = 1; d <= D[m - 1]; ++d) {
            string date = month + to_string(d);
            if (size(set<char>(date.begin(), date.end())) == 1)
                ++ans;
        }
    }
    cout << ans << endl;

    return 0;
}

2. Check if each repdigit date actually exists

Under the constraints of this problem, there are \(36\) candidates of repdigit dates: day \(1\) of month \(1\), day \(11\) of month \(1\), day \(2\) of month \(2\), day \(22\) of month \(2\), \(\ldots\), day \(8\) of month \(88\), day \(88\) of month \(88\), day \(9\) of month \(99\), and day \(99\) of month \(99\).

The problem can be solved by determine whether each of them actually exists in AtCoder kingdom’s calendar.

One can determine if day \(i\) of month \(j\) exists by checking if month \(i\) exists and it has at least \(j\) days.

The following is sample code.

N = int(input())
D = [*map(int, input().split())]

ans = 0
for i in range(1, 10):
    # day i of month i
    if i <= N and i <= D[i - 1]:
        ans += 1
    # day 11i of month i
    if i <= N and 11 * i <= D[i - 1]:
        ans += 1
    # day i of month 11i
    if 11 * i <= N and i <= D[11 * i - 1]:
        ans += 1
    # day 11i of month 11i
    if 11 * i <= N and 11 * i <= D[11 * i - 1]:
        ans += 1
            
print(ans)
#include <iostream>
#include <vector>
#include <utility>

using namespace std;

int main() {
    int N;
    cin >> N;
    vector<int> D(N);
    for(auto&& d : D)cin >> d;

    vector<pair<int, int>> zorome; // possible rep-digit dates
    for(int i = 1; i <= 9; ++i){
        zorome.emplace_back(i, i);
        zorome.emplace_back(i, i * 11);
        zorome.emplace_back(i * 11, i);
        zorome.emplace_back(i * 11, i * 11);
    }

    int ans{};
    for(const auto& [month, day] : zorome)
        if(month <= N && day <= D[month - 1])
            ++ans;

    cout << ans << endl;
    
    return 0;
}

posted:
last update: