Submission #1756160
Source Code Expand
#include <bits/stdc++.h>
typedef long long int ll;
#define FOR(i, a, b) for (ll i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define EREP(i, n) for (int i = (n - 1); i >= 0; --i)
#define mod 1000000007
#define INF 93193111451418101
#define MIN -93193111451418101
//#define INF 931931114518101
using namespace std;
typedef pair<ll, ll> P;
template <typename T> void fill_all(T &arr, const T &v) { arr = v; }
template <typename T, typename ARR> void fill_all(ARR &arr, const T &v) {
for (auto &i : arr) {
fill_all(i, v);
}
}
#define yo 100001
//------------------変数-----------------------//
ll d, n, m;
map<P, ll> dp;
string str[100];
//-------------------関数----------------------//
ll mintime = INF;
ll DP(ll L, ll num, ll kaisuu) {
if (num == n) {
mintime = min(mintime, kaisuu);
return 0;
}
if ((n - num) % L) {
return INF;
}
if (kaisuu > mintime) {
return INF;
}
if (dp[P(L, num)]) {
return dp[P(L, num)];
}
ll cnt = INF;
for (ll i = 39; i >= 0; i--) {
if (to_string(L).size() + str[i].size() < 18) {
ll izryt = L * stoll(str[i]);
if (num + izryt <= n && izryt != L) {
cnt = min(cnt, DP(izryt, num + izryt, kaisuu + 1) + 1);
}
if (num + izryt <= n && izryt != L) {
cnt = min(cnt, DP(izryt, num, kaisuu));
}
}
}
cnt = min(cnt, n - num);
return dp[P(L, num)] = cnt;
}
int main() {
cin >> n;
str[0] = '1';
str[1].push_back('2');
str[2].push_back('5');
FOR(i, 3, 40) {
auto a = stoll(str[i - 2]) % 10;
if (a == 5) {
str[i] = str[i - 2] + "2";
} else {
str[i] = str[i - 2] + "5";
}
}
cout << DP(1, 0, 0) << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
A - 通勤 |
User |
keidaroo |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
1764 Byte |
Status |
WA |
Exec Time |
53 ms |
Memory |
768 KB |
Judge Result
Set Name |
Sample |
Subtask0 |
All |
Score / Max Score |
0 / 0 |
0 / 30 |
0 / 50 |
Status |
|
|
|
Set Name |
Test Cases |
Sample |
sample0.txt, sample1.txt, sample2.txt, sample3.txt |
Subtask0 |
sample0.txt, sample1.txt, sample2.txt, sample3.txt, subtask0_0.txt, subtask0_1.txt, subtask0_10.txt, subtask0_11.txt, subtask0_12.txt, subtask0_13.txt, subtask0_14.txt, subtask0_15.txt, subtask0_2.txt, subtask0_3.txt, subtask0_4.txt, subtask0_5.txt, subtask0_6.txt, subtask0_7.txt, subtask0_8.txt, subtask0_9.txt |
All |
sample0.txt, sample1.txt, sample2.txt, sample3.txt, subtask0_0.txt, subtask0_1.txt, subtask0_10.txt, subtask0_11.txt, subtask0_12.txt, subtask0_13.txt, subtask0_14.txt, subtask0_15.txt, subtask0_2.txt, subtask0_3.txt, subtask0_4.txt, subtask0_5.txt, subtask0_6.txt, subtask0_7.txt, subtask0_8.txt, subtask0_9.txt, subtask1_0.txt, subtask1_1.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_2.txt, subtask1_3.txt, subtask1_4.txt, subtask1_5.txt, subtask1_6.txt, subtask1_7.txt, subtask1_8.txt, subtask1_9.txt |
Case Name |
Status |
Exec Time |
Memory |
sample0.txt |
WA |
2 ms |
256 KB |
sample1.txt |
AC |
1 ms |
256 KB |
sample2.txt |
AC |
2 ms |
256 KB |
sample3.txt |
WA |
2 ms |
256 KB |
subtask0_0.txt |
AC |
2 ms |
256 KB |
subtask0_1.txt |
WA |
2 ms |
256 KB |
subtask0_10.txt |
AC |
1 ms |
256 KB |
subtask0_11.txt |
AC |
1 ms |
256 KB |
subtask0_12.txt |
AC |
1 ms |
256 KB |
subtask0_13.txt |
AC |
1 ms |
256 KB |
subtask0_14.txt |
AC |
2 ms |
256 KB |
subtask0_15.txt |
AC |
1 ms |
256 KB |
subtask0_2.txt |
AC |
2 ms |
256 KB |
subtask0_3.txt |
WA |
2 ms |
256 KB |
subtask0_4.txt |
WA |
2 ms |
256 KB |
subtask0_5.txt |
WA |
2 ms |
256 KB |
subtask0_6.txt |
WA |
1 ms |
256 KB |
subtask0_7.txt |
WA |
1 ms |
256 KB |
subtask0_8.txt |
WA |
1 ms |
256 KB |
subtask0_9.txt |
WA |
1 ms |
256 KB |
subtask1_0.txt |
WA |
6 ms |
256 KB |
subtask1_1.txt |
WA |
9 ms |
384 KB |
subtask1_10.txt |
AC |
2 ms |
256 KB |
subtask1_11.txt |
AC |
2 ms |
256 KB |
subtask1_12.txt |
AC |
2 ms |
256 KB |
subtask1_13.txt |
AC |
2 ms |
256 KB |
subtask1_14.txt |
WA |
1 ms |
256 KB |
subtask1_15.txt |
WA |
53 ms |
768 KB |
subtask1_2.txt |
WA |
13 ms |
384 KB |
subtask1_3.txt |
WA |
13 ms |
384 KB |
subtask1_4.txt |
WA |
11 ms |
384 KB |
subtask1_5.txt |
WA |
1 ms |
256 KB |
subtask1_6.txt |
WA |
1 ms |
256 KB |
subtask1_7.txt |
WA |
1 ms |
256 KB |
subtask1_8.txt |
WA |
1 ms |
256 KB |
subtask1_9.txt |
WA |
2 ms |
256 KB |