Official

C - Slot Strategy Editorial by en_translator


First, let us fix the common digit that Takahashi will obtain. For example, suppose that he wants 0’s.

For \(j=0,1,\ldots,9\), let \(count(0,j)\) be the number of integers \(i\) such that the \(j\)-th character of \(S_i\) is 0, for \(i=1,2,\ldots,N\).

Here, if there exists \(j\) such that \(count(0,j)\geq 1\) and \(t<10\times (count(0,j)-1)+j\), then it is impossible to stop all reels to have 0 in a row during the first \(t\) seconds, because, in order to stop all the reals whose \(j\)-th character is 0 when it is showing 0, you must repeat \(count(0,j)\) times pressing buttons at the times of distinct non-negative integers \(t'\) such that \(t'\bmod{10}=j\).
Conversely, it can be achieved during the first \(\displaystyle\max_{j=0,1,\ldots,9} (10\times (count(0,j)-1)+j)\) seconds by, for each time \(t'\), checking if there is a rotating reel whose \(((t'\bmod{10})+1)\)-th character is 0 and stopping it if such a reel exists.

Same applies for 1, 2, \(\ldots\) , 9, and the desired value is the minimum value of them.

Therefore, the answer can be found as

\[ \displaystyle\min_{k=0,1,\ldots,9}\left( \max_{j=0,1,\ldots,9} (10\times (count(k,j)-1)+j)\right) \]

where \(count(k,j)\) denotes the number of integers \(i\) such that the \(j\)-th character of \(S_i\) is 0, for \(i=1,2,\ldots,N\).

Note that, since we need at most \((10N-1)\) seconds to line up the same specific digit, we may fix the digit to obtain and do the simulation without exceeding the time limit.

Sample code in C++:

#include <bits/stdc++.h>
using namespace std;

int main(void) {
	int n;
	string s[100];
	int cnt[10][10];
	int ans, mx;
	for (int i = 0; i < 10; i++) {
		for (int j = 0; j < 10; j++)cnt[i][j] = 0;
	}

	cin >> n;
	for (int i = 0; i < n; i++)cin >> s[i];

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < 10; j++) {
			cnt[(s[i][j] - '0')][j]++;
		}
	}

	ans = 1000;
	for (int i = 0; i < 10; i++) {
		mx = 0;
		for (int j = 0; j < 10; j++) {
			mx = max(mx, 10 * (cnt[i][j] - 1) + j);
		}
		ans = min(ans, mx);
	}

	cout << ans << endl;

	return 0;
}

Sample code in Python:

n=int(input())
s=[]
for i in range(n):
	s.append(input())

cnt=[[0 for j in range(10)]for i in range(10)]
for i in range(n):
	for j in range(10):
		cnt[int(s[i][j])][j]= cnt[int(s[i][j])][j]+1

mx=[0 for i in range(10)]
for i in range(10):
	for j in range(10):
		mx[i]=max(mx[i], 10 * (cnt[i][j] - 1) + j)

print(min(mx))

posted:
last update: