Toy と帽子と ADP BE

主にプログラミングに関わる話をゆるくエモくやっていきます

B. Yet Another Meme Problem (Educational Codeforces Round #80)

Codeforces こどふぉ competitive programming c++

問題

https://codeforces.com/contest/1288/problem/B

問題概要

conc(a, b)を、aとbを連結したものを返す関数として定義する。例えばconc(12,23) = 1223であり、conc(100,11) = 10011である。

2つの正の整数A, Bが与えられるので、1 <= a <= A, 1 <= b <= Bであるa, bの組のうち、a * b + a + b = conc(a, b)を満たすものの個数を答えよ。

考察

式変形をしていきます。

まず関数concは a \times 10^{|b|} + b（|b|はbの文字数とする）と表すことができます。

なので a \times b + a + b = a \times 10^{|b|} + bとなります。

両辺に+ bがあるので取っ払って a \times b + a = a \times 10^{|b|}です。

左辺をaでくくると a \times (b + 1) = a \times 10^{|b|}となり、両辺をaで割ると（aは正数なので大丈夫です） b + 1 = 10^{|b|}となります。

ここで、式を成り立たせるためにaの値は実はなんでもいいことがわかります。また、右辺は10のべき乗であり、bは9, 99, 999のような数のみ取りうることがわかります。

よって答えるべき組み合わせの数は、Aと、B以下ですべての桁が9である数の個数をかけ合わせたものとなります。

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int t;
    cin >> t;
    while (t--) {
        long long a;
        string b;
        cin >> a >> b;
        long long l = b.size();
        for (char c : b) {
            if (c != '9') {
                l--;
                break;
            }
        }
        cout << a * l << endl;
    }
}