Submission #6197848


Source Code Expand

Copy
#include <bits/stdc++.h>

#define x first
#define y second
#define y1 Y1
#define y2 Y2
#define mp make_pair
#define pb push_back
#define DEBUG(x) cout << #x << " = " << x << endl;

using namespace std;

typedef long long LL;
typedef pair <int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T> inline T read ()
{
	T sum = 0, fl = 1; char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
	for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
	return sum * fl;
}

inline void proc_status ()
{
	ifstream t ("/proc/self/status");
	cerr << string (istreambuf_iterator <char> (t), istreambuf_iterator <char> ()) << endl;
}

const int Maxn = 3e7 + 100;
const int Mod = 1e9 + 7;

int N = 1e7, M = 3e7;
int S, Len[Maxn], ans;

inline void Add (int &a, int b) { if ((a += b) >= Mod) a -= Mod; }

inline int Pow (int a, int b)
{
	int ans = 1;
	for (int i = b; i; i >>= 1, a = (LL) a * a % Mod) if (i & 1) ans = (LL) ans * a % Mod;
	return ans;
}

inline void Calc1 ()
{
	int r = 0, sum = 0;
	for (int l = 1; l < N; ++l)
	{
		while (sum < S) sum += Len[++r];
		if (sum == S) ++ans;
		sum -= Len[l];
	}
}

inline void Calc2 ()
{
	for (int i = 1; i <= S / 8; ++i)
		if (!(S % i)) Add (ans, ((LL) Pow (10, S / i - 1) * 9 % Mod - i + 1 + Mod) % Mod);
		else Add (ans, 1);
}

inline void Solve ()
{
	for (int i = 1; i <= M; ++i) Len[i] = Len[i / 10] + 1;

	Calc1 ();
	Calc2 ();
	cout << ans << endl;
}

inline void Input ()
{
	S = read<int>();
}

int main()
{

#ifdef hk_cnyali
	freopen("F.in", "r", stdin);
	freopen("F.out", "w", stdout);
#endif

	Input ();
	Solve ();

	return 0;
}

Submission Info

Submission Time
Task F - Number of Digits
User zjmsb
Language C++14 (GCC 5.4.1)
Score 900
Code Size 1865 Byte
Status
Exec Time 150 ms
Memory 117376 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample-01.txt, sample-02.txt, sample-03.txt, sample-04.txt, sample-05.txt
All 900 / 900 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, 37.txt, 38.txt, 39.txt, 40.txt, 41.txt, 42.txt, 43.txt, 44.txt, 45.txt, 46.txt, 47.txt, 48.txt, 49.txt, 50.txt, 51.txt, 52.txt, 53.txt, 54.txt, 55.txt, 56.txt, 57.txt, 58.txt, 59.txt, 60.txt, sample-01.txt, sample-02.txt, sample-03.txt, sample-04.txt, sample-05.txt
Case Name Status Exec Time Memory
01.txt 83 ms 117376 KB
02.txt 80 ms 117376 KB
03.txt 80 ms 117376 KB
04.txt 80 ms 117376 KB
05.txt 83 ms 117376 KB
06.txt 130 ms 117376 KB
07.txt 85 ms 117376 KB
08.txt 129 ms 117376 KB
09.txt 81 ms 117376 KB
10.txt 124 ms 117376 KB
11.txt 91 ms 117376 KB
12.txt 89 ms 117376 KB
13.txt 124 ms 117376 KB
14.txt 110 ms 117376 KB
15.txt 128 ms 117376 KB
16.txt 86 ms 117376 KB
17.txt 84 ms 117376 KB
18.txt 84 ms 117376 KB
19.txt 84 ms 117376 KB
20.txt 84 ms 117376 KB
21.txt 86 ms 117376 KB
22.txt 84 ms 117376 KB
23.txt 116 ms 117376 KB
24.txt 116 ms 117376 KB
25.txt 116 ms 117376 KB
26.txt 98 ms 117376 KB
27.txt 105 ms 117376 KB
28.txt 121 ms 117376 KB
29.txt 128 ms 117376 KB
30.txt 117 ms 117376 KB
31.txt 97 ms 117376 KB
32.txt 128 ms 117376 KB
33.txt 96 ms 117376 KB
34.txt 134 ms 117376 KB
35.txt 116 ms 117376 KB
36.txt 122 ms 117376 KB
37.txt 132 ms 117376 KB
38.txt 103 ms 117376 KB
39.txt 134 ms 117376 KB
40.txt 104 ms 117376 KB
41.txt 80 ms 117376 KB
42.txt 116 ms 117376 KB
43.txt 116 ms 117376 KB
44.txt 116 ms 117376 KB
45.txt 80 ms 117376 KB
46.txt 84 ms 117376 KB
47.txt 116 ms 117376 KB
48.txt 80 ms 117376 KB
49.txt 84 ms 117376 KB
50.txt 116 ms 117376 KB
51.txt 80 ms 117376 KB
52.txt 80 ms 117376 KB
53.txt 83 ms 117376 KB
54.txt 85 ms 117376 KB
55.txt 121 ms 117376 KB
56.txt 134 ms 117376 KB
57.txt 134 ms 117376 KB
58.txt 150 ms 117376 KB
59.txt 134 ms 117376 KB
60.txt 106 ms 117376 KB
sample-01.txt 80 ms 117376 KB
sample-02.txt 80 ms 117376 KB
sample-03.txt 80 ms 117376 KB
sample-04.txt 80 ms 117376 KB
sample-05.txt 80 ms 117376 KB