結果
| 問題 |
No.2934 Digit Sum
|
| コンテスト | |
| ユーザー |
 Pedro Vinicius
|
| 提出日時 | 2024-10-23 13:04:22 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 10,208 bytes |
| コンパイル時間 | 6,266 ms |
| コンパイル使用メモリ | 285,068 KB |
| 実行使用メモリ | 13,636 KB |
| 最終ジャッジ日時 | 2024-10-23 13:04:32 |
| 合計ジャッジ時間 | 9,865 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 7 TLE * 1 -- * 17 |
ソースコード
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define all(x) x.begin(), x.end()
using namespace __gnu_pbds; using namespace std;
template<class T> using ordered_set = tree<T, null_type , less<T> , rb_tree_tag , tree_order_statistics_node_update>; template<class T> using ordered_multiset = tree<T, null_type , less_equal<T> , rb_tree_tag , tree_order_statistics_node_update>; typedef long long ll; typedef pair<int, int> ii; typedef tuple<int, int, int> iii; typedef tuple<int, int, int, int> iiii; typedef vector<int> vi;
const ll oo = 1987654321987654321;
template<class It> void db(It b, It e) { for (auto it = b; it != e; it++) cout << *it << ' '; cout<< endl; } template<typename A> istream& operator>>(istream& fin, vector<A>& v) { for (auto it = v.begin(); it != v.end(); ++it) fin >> *it; return fin; } template<typename A, typename B> istream& operator>>(istream& fin, pair<A, B>& p){ fin >> p.first >> p.second; return fin; } template<typename T> void chmin(T &a, T b){ a = min(a, b); } template<typename T> void chmax(T &a, T b){ a = max(a, b); } template <typename T, typename S> ostream& operator<<(ostream& os, const pair<T, S>& v) { os << "(" << v.first << "," << v.second << ")"; return os; }
// Big Integer
//
// Complexidades: (para n digitos)
// Soma, subtracao, comparacao - O(n)
// Multiplicacao - O(n log(n))
// Divisao, resto - O(n^2)
struct bint {
static const int BASE = 1e9;
vector<int> v;
bool neg;
bint() : neg(0) {}
bint(int val) : bint() { *this = val; }
bint(long long val) : bint() { *this = val; }
void trim() {
while (v.size() and v.back() == 0) v.pop_back();
if (!v.size()) neg = 0;
}
// converter de/para string | cin/cout
bint(const char* s) : bint() { from_string(string(s)); }
bint(const string& s) : bint() { from_string(s); }
void from_string(const string& s) {
v.clear(), neg = 0;
int ini = 0;
while (ini < s.size() and (s[ini] == '-' or s[ini] == '+' or s[ini] == '0'))
if (s[ini++] == '-') neg = 1;
for (int i = s.size()-1; i >= ini; i -= 9) {
int at = 0;
for (int j = max(ini, i - 8); j <= i; j++) at = 10*at + (s[j]-'0');
v.push_back(at);
}
if (!v.size()) neg = 0;
}
string to_string() const {
if (!v.size()) return "0";
string ret;
if (neg) ret += '-';
for (int i = v.size()-1; i >= 0; i--) {
string at = ::to_string(v[i]);
int add = 9 - at.size();
if (i+1 < v.size()) for (int j = 0; j < add; j++) ret += '0';
ret += at;
}
return ret;
}
friend istream& operator>>(istream& in, bint& val) {
string s; in >> s;
val = s;
return in;
}
friend ostream& operator<<(ostream& out, const bint& val) {
string s = val.to_string();
out << s;
return out;
}
// operators
friend bint abs(bint val) {
val.neg = 0;
return val;
}
friend bint operator-(bint val) {
if (val != 0) val.neg ^= 1;
return val;
}
bint& operator=(const bint& val) { v = val.v, neg = val.neg; return *this; }
bint& operator=(long long val) {
v.clear(), neg = 0;
if (val < 0) neg = 1, val *= -1;
for (; val; val /= BASE) v.push_back(val % BASE);
return *this;
}
int cmp(const bint& r) const { // menor: -1 | igual: 0 | maior: 1
if (neg != r.neg) return neg ? -1 : 1;
if (v.size() != r.v.size()) {
int ret = v.size() < r.v.size() ? -1 : 1;
return neg ? -ret : ret;
}
for (int i = int(v.size())-1; i >= 0; i--) {
if (v[i] != r.v[i]) {
int ret = v[i] < r.v[i] ? -1 : 1;
return neg ? -ret : ret;
}
}
return 0;
}
friend bool operator<(const bint& l, const bint& r) { return l.cmp(r) == -1; }
friend bool operator>(const bint& l, const bint& r) { return l.cmp(r) == 1; }
friend bool operator<=(const bint& l, const bint& r) { return l.cmp(r) <= 0; }
friend bool operator>=(const bint& l, const bint& r) { return l.cmp(r) >= 0; }
friend bool operator==(const bint& l, const bint& r) { return l.cmp(r) == 0; }
friend bool operator!=(const bint& l, const bint& r) { return l.cmp(r) != 0; }
bint& operator +=(const bint& r) {
if (!r.v.size()) return *this;
if (neg != r.neg) return *this -= -r;
for (int i = 0, c = 0; i < r.v.size() or c; i++) {
if (i == v.size()) v.push_back(0);
v[i] += c + (i < r.v.size() ? r.v[i] : 0);
if ((c = v[i] >= BASE)) v[i] -= BASE;
}
return *this;
}
friend bint operator+(bint a, const bint& b) { return a += b; }
bint& operator -=(const bint& r) {
if (!r.v.size()) return *this;
if (neg != r.neg) return *this += -r;
if ((!neg and *this < r) or (neg and r < *this)) {
*this = r - *this;
neg ^= 1;
return *this;
}
for (int i = 0, c = 0; i < r.v.size() or c; i++) {
v[i] -= c + (i < r.v.size() ? r.v[i] : 0);
if ((c = v[i] < 0)) v[i] += BASE;
}
trim();
return *this;
}
friend bint operator-(bint a, const bint& b) { return a -= b; }
// operators de * / %
bint& operator *=(int val) {
if (val < 0) val *= -1, neg ^= 1;
for (int i = 0, c = 0; i < v.size() or c; i++) {
if (i == v.size()) v.push_back(0);
long long at = (long long) v[i] * val + c;
v[i] = at % BASE;
c = at / BASE;
}
trim();
return *this;
}
friend bint operator *(bint a, int b) { return a *= b; }
friend bint operator *(int a, bint b) { return b *= a; }
using cplx = complex<double>;
void fft(vector<cplx>& a, bool f, int N, vector<int>& rev) const {
for (int i = 0; i < N; i++) if (i < rev[i]) swap(a[i], a[rev[i]]);
vector<cplx> roots(N);
for (int n = 2; n <= N; n *= 2) {
const static double PI = acos(-1);
for (int i = 0; i < n/2; i++) {
double alpha = (2*PI*i)/n;
if (f) alpha = -alpha;
roots[i] = cplx(cos(alpha), sin(alpha));
}
for (int pos = 0; pos < N; pos += n)
for (int l = pos, r = pos+n/2, m = 0; m < n/2; l++, r++, m++) {
auto t = roots[m]*a[r];
a[r] = a[l] - t;
a[l] = a[l] + t;
}
}
if (!f) return;
auto invN = cplx(1)/cplx(N);
for (int i = 0; i < N; i++) a[i] *= invN;
}
vector<long long> convolution(const vector<int>& a, const vector<int>& b) const {
vector<cplx> l(a.begin(), a.end()), r(b.begin(), b.end());
int ln = l.size(), rn = r.size(), N = ln+rn+1, n = 1, log_n = 0;
while (n <= N) n <<= 1, log_n++;
vector<int> rev(n);
for (int i = 0; i < n; i++) {
rev[i] = 0;
for (int j = 0; j < log_n; j++) if (i>>j&1)
rev[i] |= 1 << (log_n-1-j);
}
l.resize(n), r.resize(n);
fft(l, false, n, rev), fft(r, false, n, rev);
for (int i = 0; i < n; i++) l[i] *= r[i];
fft(l, true, n, rev);
vector<long long> ret;
for (auto& i : l) ret.push_back(round(i.real()));
return ret;
}
vector<int> convert_base(const vector<int>& a, int from, int to) const {
static vector<long long> pot(10, 1);
if (pot[1] == 1) for (int i = 1; i < 10; i++) pot[i] = 10*pot[i-1];
vector<int> ret;
long long at = 0;
int digits = 0;
for (int i : a) {
at += i * pot[digits];
digits += from;
while (digits >= to) {
ret.push_back(at % pot[to]);
at /= pot[to];
digits -= to;
}
}
ret.push_back(at);
while (ret.size() and ret.back() == 0) ret.pop_back();
return ret;
}
bint operator*(const bint& r) const { // O(n log(n))
bint ret;
ret.neg = neg ^ r.neg;
auto conv = convolution(convert_base(v, 9, 4), convert_base(r.v, 9, 4));
long long c = 0;
for (auto i : conv) {
long long at = i+c;
ret.v.push_back(at % 10000);
c = at / 10000;
}
for (; c; c /= 10000) ret.v.push_back(c%10000);
ret.v = convert_base(ret.v, 4, 9);
if (!ret.v.size()) ret.neg = 0;
return ret;
}
bint& operator*=(const bint& r) { return *this = *this * r; };
bint& operator/=(int val) {
if (val < 0) neg ^= 1, val *= -1;
for (int i = int(v.size())-1, c = 0; i >= 0; i--) {
long long at = v[i] + c * (long long) BASE;
v[i] = at / val;
c = at % val;
}
trim();
return *this;
}
friend bint operator/(bint a, int b) { return a /= b; }
int operator %=(int val) {
if (val < 0) val *= -1;
long long at = 0;
for (int i = int(v.size())-1; i >= 0; i--)
at = (BASE * at + v[i]) % val;
if (neg) at *= -1;
return at;
}
friend int operator%(bint a, int b) { return a %= b; }
friend pair<bint, bint> divmod(const bint& a_, const bint& b_) { // O(n^2)
if (a_ == 0) return {0, 0};
int norm = BASE / (b_.v.back() + 1);
bint a = abs(a_) * norm;
bint b = abs(b_) * norm;
bint q, r;
for (int i = a.v.size() - 1; i >= 0; i--) {
r *= BASE, r += a.v[i];
long long upper = b.v.size() < r.v.size() ? r.v[b.v.size()] : 0;
int lower = b.v.size() - 1 < r.v.size() ? r.v[b.v.size() - 1] : 0;
int d = (upper * BASE + lower) / b.v.back();
r -= b*d;
while (r < 0) r += b, d--; // roda O(1) vezes
q.v.push_back(d);
}
reverse(q.v.begin(), q.v.end());
q.neg = a_.neg ^ b_.neg;
r.neg = a_.neg;
q.trim(), r.trim();
return {q, r / norm};
}
bint operator/(const bint& val) { return divmod(*this, val).first; }
bint& operator/=(const bint& val) { return *this = *this / val; }
bint operator%(const bint& val) { return divmod(*this, val).second; }
bint& operator%=(const bint& val) { return *this = *this % val; }
};
ll memo[35][2][35 * 9 + 5];
vi num2v(bint n) {
vi retval;
if (n == 0) retval.push_back(0);
while (n > 0) {
retval.push_back(n % 10);
n /= 10;
}
reverse(all(retval));
return retval;
}
ll n;
ll dp(vi &digitos, int i = 0, bool empatado = true, int x = 0) {
if (i == digitos.size()) {
return 1;
}
ll &ans = memo[i][empatado][x];
if (ans != -1) return ans;
ans = 0;
int r = empatado ? digitos[i] : 9;
for (int val = 0; val <= r; val++) {
bool new_empatado = empatado && val == r;
if (x + val <= n){
ans += dp(digitos, i + 1, new_empatado, x + val);
}
}
return ans;
}
signed main(){
cin.tie(0)->sync_with_stdio(0);
ll k;
cin >> n >> k;
++k;
chmin(n, (ll)300);
auto good = [&](bint x){
vi digitos = num2v(x);
memset(memo, -1, sizeof(memo));
return dp(digitos) >= k;
};
bint l = 0;
bint r = 1;
while (!good(r)) r *= 2;
while (r - l > 1){
bint mid = l + (r - l)/2;
if (good(mid)) r = mid;
else l = mid;
}
cout << r << "\n";
}