Submission #8587942


Source Code Expand

Copy
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
//#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }
//---------------------------------------------------------------------------------------------------
/*---------------------------------------------------------------------------------------------------
            ∧_∧
      ∧_∧  (´<_` )  Welcome to My Coding Space!
     ( ´_ゝ`) /  ⌒i     @hamayanhamayan
    /   \     | |
    /   / ̄ ̄ ̄ ̄/  |
  __(__ニつ/     _/ .| .|____
     \/____/ (u ⊃
---------------------------------------------------------------------------------------------------*/














int M;
int D[201010]; ll C[201010];
//---------------------------------------------------------------------------------------------------
void _main() {
	cin >> M;
	rep(i, 0, M) cin >> D[i] >> C[i];

	int cur = 0;
	ll ans = 0;
	rep(_, 0, M) {
		int d = D[_];
		ll c = C[_];

		if (c < 30) {
			rep(i, 0, c) {
				cur += d;
				ans++;
				if (10 <= cur) {
					cur = (cur / 10) + (cur % 10);
					ans++;
				}
			}
		}
		else {
			int idx = 0;

			map<int, int> loop;
			map<int, ll> need;
			loop[cur] = 0;
			need[cur] = ans;

			cur += d;
			ans++;
			if (10 <= cur) {
				cur = (cur / 10) + (cur % 10);
				ans++;
			}
			idx++;

			while (!loop.count(cur)) {
				loop[cur] = idx;
				need[cur] = ans;

				cur += d;
				ans++;
				if (10 <= cur) {
					cur = (cur / 10) + (cur % 10);
					ans++;
				}
				idx++;
			}

			ll ansd = ans - need[cur];
			int loopp = idx - loop[cur];

			c -= idx;

			ans += c / loopp * ansd;
			c %= loopp;
			rep(i, 0, c) {
				cur += d;
				ans++;
				if (10 <= cur) {
					cur = (cur / 10) + (cur % 10);
					ans++;
				}
			}
		}
	}
	cout << ans-1 << endl;
}





Submission Info

Submission Time
Task D - Digit Sum Replace
User hamayanhamayan
Language C++14 (GCC 5.4.1)
Score 500
Code Size 2456 Byte
Status AC
Exec Time 185 ms
Memory 2560 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 500 / 500
Status
AC × 2
AC × 20
Set Name Test Cases
Sample 00-sample-01.txt, 00-sample-02.txt
All 00-sample-01.txt, 00-sample-02.txt, 01-corner-01.txt, 01-corner-02.txt, 01-corner-03.txt, 02-random-01.txt, 02-random-02.txt, 02-random-03.txt, 02-random-04.txt, 02-random-05.txt, 02-random-06.txt, 02-random-07.txt, 02-random-08.txt, 02-random-09.txt, 02-random-10.txt, 02-random-11.txt, 03-max-01.txt, 03-max-02.txt, 04-min-01.txt, 04-min-02.txt
Case Name Status Exec Time Memory
00-sample-01.txt AC 1 ms 256 KB
00-sample-02.txt AC 1 ms 256 KB
01-corner-01.txt AC 1 ms 256 KB
01-corner-02.txt AC 1 ms 256 KB
01-corner-03.txt AC 1 ms 256 KB
02-random-01.txt AC 1 ms 256 KB
02-random-02.txt AC 1 ms 256 KB
02-random-03.txt AC 1 ms 256 KB
02-random-04.txt AC 1 ms 256 KB
02-random-05.txt AC 1 ms 256 KB
02-random-06.txt AC 180 ms 2560 KB
02-random-07.txt AC 182 ms 2560 KB
02-random-08.txt AC 185 ms 2560 KB
02-random-09.txt AC 176 ms 2560 KB
02-random-10.txt AC 185 ms 2560 KB
02-random-11.txt AC 180 ms 2560 KB
03-max-01.txt AC 106 ms 1920 KB
03-max-02.txt AC 1 ms 256 KB
04-min-01.txt AC 112 ms 2048 KB
04-min-02.txt AC 1 ms 256 KB