公式

C - Security 2 解説 by en_translator


Let \(N\) denote the length of \(S\).

The length of \(t\) increases by one by pressing button A, and remains intact by pressing B. Thus, button A must be pressed \(N\) times.

The following operations do not modify \(t\), so we may assume that these operations are not performed.

  • Press button B before pressing button A for the first time.
  • Press button B \(10\) times in row.

For each \(1 \leq i \leq N\), after pressing button A for the \(i\)-th time before pressing it next time, suppose that button \(B\) is pressed \(b_i\) times. By the discussion above, we may assume that \(0 \leq b_i \leq 9\).

Then, the \(j\)-th character of \(S_j\) ends up being \(S_j\) if and only if \((b_j + \dots + b_N) \bmod 10 = S_j\).

For \(j=N\), we obviously know \(b_N = S_j\), so we consider \(j<N\). By applying the equation above for the \((j+1)\)-th character, we obtain \((b_{j+1} + \dots + b_N) \bmod 10 = S_{j+1}\). Subtracting this form the equation above, we obtain \(b_j \equiv S_{j} - S_{j+1}\ \pmod{10}\). Such an integer \(b_i\) with \(0 \leq b_i \leq 9\) is uniquely determined as \((10 + S_{j} - S_{j+1}) \bmod 10\).

Hence, the answer is the sum of \(b_j\) over \(1 \leq j \leq N\), plus \(N\).

The following is sample code in C++.

#include <iostream>
#include <string>
#include <vector>
using std::cin;
using std::cout;
using std::cerr;
using std::endl;
using std::string;


int main(void){
	string s;
	cin >> s;

	int sum = 0;
	int n = s.size();
	for (int i = n-1; i >= 0; i--) {
		int v = s[i] - '0';
		int u = ((i < n-1) ? (s[i+1] - '0') : 0);
		int b = (10 + v - u) % 10;
		sum += b;
	}

	int ans = sum + n;
	cout << ans << "\n";

	return 0;
}

投稿日時:
最終更新: