AtCoder Beginner Contest 182 解题报告

abc182_f Valid payments

AtCoder Beginner Contest 182 的第六题,还算是有点思维难度。

题目链接:F – Valid payments

题意翻译

  • 在 A 国,有 \( n \) 种面额的货币 \( a _ 1 , a _ 2 , \cdots , a _ n \);
  • 其中 \( a _ 1 = 1 \),且货币的面值满足:\( \forall i , 1 \leq i < n \),\( a _ i < a _ { i + 1 } \) 且 \( a _ i \mid a _ { i + 1 } \);
  • 现在你有 \( y \) 元钱,去购买一个价值为 \( x \) 的商品,售货员将会给你找 \( y-x \) 元钱;
  • A 国的售货员都有一种奇怪的癖好,他们绝对不会找给你与你持有的货币面额相同的货币;
  • 给你 \( x \),求可能的 \( y \);
  • 数据范围:\( 1 \leq n \leq 50 \),\( 1 = a _ 1 < a _ 2 < \cdots < a _ n \leq 10 ^ {15} \),\( a _ i \mid a _ { i + 1 } \),\( 1 \leq x \leq 10 ^ {15} \)。

题解

枚举即可。

#include <bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++)
static char buf[100000], *p1 = buf, *p2 = buf;
inline int read(void)
{
    reg bool f = false;
    reg char ch = getchar();
    reg int res = 0;
    while (!isdigit(ch))
        f |= (ch == '-'), ch = getchar();
    while (isdigit(ch))
        res = 10 * res + (ch ^ '0'), ch = getchar();
    return f ? -res : res;
}
inline ll readll(void)
{
    reg bool f = false;
    reg char ch = getchar();
    reg ll res = 0;
    while (!isdigit(ch))
        f |= (ch == '-'), ch = getchar();
    while (isdigit(ch))
        res = 10ll * res + (ch ^ '0'), ch = getchar();
    return f ? -res : res;
}

const int MAXN = 50 + 5;

int n;
ll x;
ll a[MAXN];
map<ll, ll> f, g;

int main(void)
{
    n = read(), x = readll();
    for (reg int i = 1; i <= n; ++i)
        a[n - i + 1] = readll();
    ll x0 = x / a[1] * a[1];
    f[x0] = 1;
    if (x0 != x)
        f[x0 + a[1]] = 1;
    for (reg int i = 2; i <= n; ++i)
    {
        g.clear();
        reg ll Max = a[i - 1] / a[i];
        for (auto it : f)
        {
            reg ll d = x - it.first, m = d / a[i];
            ll y = it.first + m * a[i];
            if (abs(m) < Max)
                g[y] += it.second;
            if (y != x && abs(m) + 1 < Max)
                g[y + a[i] * (d / abs(d))] += it.second;
        }
        swap(f, g);
    }
    printf("%lld\n", f[x]);
    return 0;
}
Pages: 1 2 3 4 5 6 7 8