Esta análise detalha as soluções para os problemas do AtCoder Beginner Contest 400 (abc400).

A e B Estes são problemas introdutórios que requerem implementação direta. As soluções podem ser encontradas nos snippets de código abaixo.

Problema A

#include <iostream>

int main() {
    int input_val;
    std::cin >> input_val;
    if (400 % input_val != 0) {
        std::cout << -1 << std::endl;
    } else {
        std::cout << 400 / input_val << std::endl;
    }
    return 0;
}

Problema B

#include <iostream>

int main() {
    long long n, m;
    std::cin >> n >> m;
    long long current_power_of_n = 1;
    long long total_sum = 1;
    for (int i = 0; i < m; ++i) {
        long long term = current_power_of_n * n;
        if (total_sum > 1000000000LL - term) { // Check for overflow before adding
            std::cout << "inf" << std::endl;
            return 0;
        }
        total_sum += term;
        current_power_of_n *= n;
    }
    std::cout << total_sum << std::endl;
    return 0;
}

C Este problema envolve contar números da forma (2^a \cdot b^2 \le N). Uma abordagem eficaz é iterar sobre as potências de 2 ((2^a)) e, para cada potência, usar busca binária para encontrar o maior valer de (b) tal que (2^a \cdot b^2 \le N).

É importante notar que, se um número (b) tiver um fator 2, a forma (2^a \cdot b^2) pode ser representada de maneiras diferentes. Para evitar contagens duplicadas, a contribuição de um (b) encontrado por busca binária é (\lceil b/2 \rceil). Isso ocorre porque se (b = 2k), então (2^a \cdot (2k)^2 = 2^{a+2} \cdot k^2). Ao contar as contribuições de (\lceil b/2 \rceil), garantimos que cada número quadrado perfeito da forma (x^2) seja contado corretamente uma única vez, mesmo que sua representação como (2^a \cdot b^2) possa variar.

Solução para C

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>

// Using __int128 for larger number support if needed, otherwise long long might suffice
using IntType = __int128;

// Helper function to read __int128
IntType read_int128() {
    long long val = 0;
    int sign = 1;
    char c = getchar();
    while (c < '0' || c > '9') {
        if (c == '-') sign = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        val = val * 10 + (c - '0');
        c = getchar();
    }
    return val * sign;
}

// Helper function to print __int128
void write_int128(IntType n) {
    if (n == 0) {
        putchar('0');
        return;
    }
    if (n < 0) {
        putchar('-');
        n = -n;
    }
    char buf[100];
    int i = sizeof(buf) - 1;
    buf[i--] = 0;
    while (n > 0) {
        buf[i--] = (n % 10) + '0';
        n /= 10;
    }
    printf("%s", &buf[i + 1]);
}

int main() {
    IntType n;
    read_int128(n); // Assuming a read function for __int128 is available or implemented

    std::vector<IntType> powers_of_2;
    IntType current_power = 1;
    powers_of_2.push_back(current_power);
    for (int i = 0; i < 63; ++i) { // Up to 2^63 for potential values within 10^18
        if (current_power > n / 2) break; // Prevent overflow
        current_power *= 2;
        powers_of_2.push_back(current_power);
    }

    IntType total_count = 0;
    for (IntType pow2 : powers_of_2) {
        if (pow2 > n) break;
        
        IntType low = 1, high = 3000000000LL; // Sufficiently large upper bound for b (sqrt(10^18))
        IntType max_b = 0;

        while (low <= high) {
            IntType mid = low + (high - low) / 2;
            if (mid == 0) { // Avoid division by zero or unnecessary checks
                 low = mid + 1;
                 continue;
            }
            // Check for overflow before multiplication: n / pow2 / mid < mid
             if (pow2 > n / mid || mid > (n / pow2) / mid ) { // Check if pow2 * mid * mid > n
                high = mid - 1;
            } else {
                max_b = mid;
                low = mid + 1;
            }
        }
        
        // Add the contribution, using ceiling division (max_b + 1) / 2
        if (max_b > 0) {
            total_count += (max_b + 1) / 2;
        }
    }

    write_int128(total_count);
    putchar('\n');

    return 0;
}

D Este problema pode ser resolvido utilizando Busca em Largura (BFS) com um Fila de Prioridade. A chave é adaptar o BFS para considerar os "custos" de atravessar paredes.

Ao realizar a busca, cada estado na fila de prioridade deve conter a posição atual (x, y) e o custo acumulado para chegar a essa posição. A fila de prioridade deve ordenar os estados com base no custo, priorizando os de menor custo.

Inicializamos as distâncias mínimas para cada célula com um valor infinito. Ao explorar de uma célula (x, y) com custo c:

1. Se a célula adjacente (nx, ny) for um caminho livre ('.') e o custo para alcançá-la (c) for menor que a distância mínima já registrada para (nx, ny), atualizamos a distância mínima e adicionamos (nx, ny) à fila de prioridade com custo c.
2. Se a célula adjacente (nx, ny) for uma parede ('#'), consideramos a célula além da parede (nnx, nny). Se o custo para chegar a (nnx, nny) através da parede (c + 1) for menor que a distância mínima já registrada para (nnx, nny), atualizamos a distância mínima e adicionamos (nnx, nny) à fila de prioridade com custo c + 1.

O processo continua até que a célula de destino seja alcançada.

Solução para D

#include <iostream>
#include <vector>
#include <queue>
#include <tuple>

const int INF = 1e9; // Represents infinity

struct State {
    int r, c, cost;

    // Overload operator< for priority queue (min-heap)
    bool operator>(const State& other) const {
        return cost > other.cost;
    }
};

int dr[] = {-1, 1, 0, 0}; // Delta row for neighbors (up, down, left, right)
int dc[] = {0, 0, -1, 1}; // Delta column for neighbors

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    int R, C;
    std::cin >> R >> C;

    std::vector<std::string> grid(R);
    for (int i = 0; i < R; ++i) {
        std::cin >> grid[i];
    }

    int start_r, start_c, end_r, end_c;
    std::cin >> start_r >> start_c >> end_r >> end_c;
    // Adjust to 0-based indexing
    start_r--; start_c--; end_r--; end_c--;

    std::vector<std::vector<int>> min_cost(R, std::vector<int>(C, INF));
    std::priority_queue<State, std::vector<State>, std::greater<State>> pq;

    min_cost[start_r][start_c] = 0;
    pq.push({start_r, start_c, 0});

    while (!pq.empty()) {
        auto [r, c, cost] = pq.top();
        pq.pop();

        if (cost > min_cost[r][c]) {
            continue;
        }
        
        if (r == end_r && c == end_c) {
            std::cout << cost << std::endl;
            return 0;
        }

        // Explore neighbors
        for (int i = 0; i < 4; ++i) {
            int nr = r + dr[i];
            int nc = c + dc[i];

            if (nr >= 0 && nr < R && nc >= 0 && nc < C) {
                if (grid[nr][nc] == '.') { // Free path
                    if (cost < min_cost[nr][nc]) {
                        min_cost[nr][nc] = cost;
                        pq.push({nr, nc, cost});
                    }
                } else { // Wall encountered
                    int nnr = nr + dr[i]; // Cell beyond the wall
                    int nnc = nc + dc[i];

                    if (nnr >= 0 && nnr < R && nnc >= 0 && nnc < C) {
                        if (cost + 1 < min_cost[nnr][nnc]) {
                            min_cost[nnr][nnc] = cost + 1;
                            pq.push({nnr, nnc, cost + 1});
                        }
                    }
                }
            }
        }
    }

    // If the destination is unreachable
    if (min_cost[end_r][end_c] == INF) {
        std::cout << -1 << std::endl;
    } else {
         std::cout << min_cost[end_r][end_c] << std::endl;
    }


    return 0;
}

E Para este problema, a estratégia é primeiro gerar todos os números "possíveis" que podem ser expressos na forma (a^{2x} b^{2y} = (a^x b^y)^2). Isso significa que precisamos encontrar todas as bases que, quando elevadas ao quadrado, resultam em um número menor ou igual a (10^6).

Podemos fazer isso pré-calculando todos os números da forma (p^k) onde (p) é um primo e (p^k \le 10^6). Em seguida, combinamos esses números primos para formar as bases. Uma abordagem é iterar através dos números primos pré-calculados. Para cada número (p^k), geramos todas as suas potências ( (p^k)^m \le 10^6 ).

Depois de ter uma lista de todas as bases (b \le 10^6) tal que (b^2 \le 10^6), podemos combiná-las. A ideia é iterar por todas as bases pré-calculadas (vamos chamá-las de bases). Para cada base_i na lista, iteramos por base_j (onde (j \ge i)) e verificamos se base_i * base_j \le 10^6. Se eles forem coprimos, o produto base_i * base_j é uma nova base válida. Se base_i * base_j for maior que (10^6), podemos parar de verificar para base_i, pois os produtos subsequentes também excederão o limite.

Finalmente, calculamos o quadrado dessas bases combinadas e armazenamos os resultados em um array. Para responder às consultas, usamos busca binária neste array de quadrados.

Solução para E

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <set>

const int MAX_VAL = 1000000;
const int SQRT_MAX_VAL = 1000; // sqrt(10^6)

std::vector<int> primes;
bool is_prime[MAX_VAL + 1];

// Function to precompute primes up to MAX_VAL using a sieve
void sieve() {
    std::fill(is_prime, is_prime + MAX_VAL + 1, true);
    is_prime[0] = is_prime[1] = false;
    for (int p = 2; p * p <= MAX_VAL; ++p) {
        if (is_prime[p]) {
            for (int i = p * p; i <= MAX_VAL; i += p)
                is_prime[i] = false;
        }
    }
    for (int p = 2; p <= MAX_VAL; ++p) {
        if (is_prime[p]) {
            primes.push_back(p);
        }
    }
}

// Function to generate bases
std::vector<long long> generate_bases() {
    sieve();
    std::set<long long> base_set;

    // Add powers of primes
    for (int p : primes) {
        long long current_power = p;
        while (current_power <= MAX_VAL) {
            base_set.insert(current_power);
            if (MAX_VAL / p < current_power) break; // Prevent overflow
            current_power *= p;
        }
    }

    std::vector<long long> bases(base_set.begin(), base_set.end());
    std::vector<long long> final_bases;
    final_bases.push_back(1); // Base case for 1

    for (long long b1 : bases) {
        for (long long b2 : bases) {
            if (b1 > b2) continue; // Ensure b1 <= b2 to avoid duplicates and redundant checks
            if (b1 == 1 && b2 == 1) continue; // Already handled by initial 1

            long long combined_base = b1 * b2;
            if (combined_base > MAX_VAL) {
                if (b1 == 1) break; // If even 1 * b2 exceeds, further b1 will too
                continue; // For b1 > 1, this b2 is too large, try next b2 for same b1
            }

            // Check for coprimality using GCD - this part is tricky and might be simplified
            // A simpler approach might be to ensure that the prime factorization of b1 and b2 are disjoint
            // For this problem's constraints, it might be sufficient to just generate combinations and check the final square value
             if (std::gcd(b1, b2) == 1) { // Only combine if coprime
                 final_bases.push_back(combined_base);
             }
        }
    }
    
    // Alternative approach: Generate all numbers of the form p1^a1 * p2^a2 ... where exponents are even
    // Or, generate all numbers k such that k^2 <= MAX_VAL and then filter based on the problem's specific form.
    // The provided C++ solution seems to directly combine powers of primes. Let's refine that logic.

    std::vector<long long> temp_bases;
    temp_bases.push_back(1);

    for(int p : primes) {
        std::vector<long long> next_bases;
        long long pk = p;
        while(pk <= MAX_VAL) {
            for(long long existing_base : temp_bases) {
                long long prod = existing_base * pk;
                if (prod <= MAX_VAL) {
                     next_bases.push_back(prod);
                } else {
                    break; // Optimization
                }
            }
             if (MAX_VAL / p < pk) break; // Prevent overflow
            pk *= p;
        }
        for(long long nb : next_bases) {
            temp_bases.push_back(nb);
        }
    }
    
    std::sort(temp_bases.begin(), temp_bases.end());
    temp_bases.erase(std::unique(temp_bases.begin(), temp_bases.end()), temp_bases.end());

    std::vector<long long> result_bases;
     for(long long base : temp_bases) {
         if (base * base <= MAX_VAL) {
             result_bases.push_back(base);
         }
     }
     std::sort(result_bases.begin(), result_bases.end());
    return result_bases;

}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    std::vector<long long> bases = generate_bases();
    std::vector<long long> perfect_squares;
    for (long long base : bases) {
        perfect_squares.push_back(base * base);
    }
    // Ensure perfect_squares is sorted and unique (generate_bases should handle this)
    std::sort(perfect_squares.begin(), perfect_squares.end());
    perfect_squares.erase(std::unique(perfect_squares.begin(), perfect_squares.end()), perfect_squares.end());


    int q;
    std::cin >> q;
    while (q--) {
        int x;
        std::cin >> x;
        // Find the count of perfect squares less than or equal to x
        auto it = std::upper_bound(perfect_squares.begin(), perfect_squares.end(), x);
        std::cout << (it - perfect_squares.begin()) << "\n";
    }

    return 0;
}