C - Slot Strategy 解説 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))
投稿日時:
最終更新: