AtCoder Beginner Contest 182 解题报告

abc182_c To 3

AtCoder Beginner Contest 182 的第三题,签到题。

题目链接:C – To 3

题意翻译

  • 给你一个没有一位为 \( 0 \) 的正整数 \( n \);
  • 设 \( k \) 是 \( n \) 的位数,要求你删去 \( 0 \sim k-1 \) 个数位使得新数是 \( 3 \) 的倍数;
  • 输出最少需要删除多少位数,无解输出 \( -1 \);
  • 数据范围:\( 1 \leq n \leq 10 ^ {18} \)。

题解

解法很显然,分类讨论即可。

#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 ll read(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;
}

ll n;
int cnt[3];

int main(void)
{
    n = read();
    reg int tmp = n % 3; //n 与 3 的倍数间的差距
    while (n)
    {
        ++cnt[(n % 10) % 3]; //记录每一位的余数对应的个数
        n /= 10;
    }
    reg int sum = cnt[0] + cnt[1] + cnt[2]; //总位数
    if (!tmp)
        puts("0"); //3 的倍数无需修改
    else if (tmp == 1)
        if (cnt[1] > 0 && sum > 1) //删 1 个 1
            puts("1");
        else if (cnt[2] > 1 && sum > 2) //删 2 个 2
            puts("2");
        else //无解
            puts("-1");
    else if (cnt[2] > 0 && sum > 1) //删 1 个 2
        puts("1");
    else if (cnt[1] > 1 && sum > 2) //删 2 个 1
        puts("2");
    else //无解
        puts("-1");
    return 0;
}
Pages: 1 2 3 4 5 6 7 8