MC521 - Relatório I
Júlio da Silva Telles
12 de Julho de 2026
1 F - P06 (AtCoder - abc251_d)
O problema F descreve uma situação em que dado um inteiro w tal que 1 ≤ w ≤ 106 e
necessario encontrar uma familia de elementos descrita como W =P{wi ∈ Z}i∈I com 1 ≤
|I| ≤ 300, tal que ∀n ∈ Z ∩ (1, w), ∃A ⊆ I t.q. 1 ≤ |A| ≤ 3 e n = a∈A wa .
1.1 Solução
Como w não pode ser maior que 106 e não existe limitações adicionais ao problema
podemos apenas formar uma solução para 106 que será viavel para todos os possiveis
valores de w. Tendo isso em mente dividimos o a familia em tres secções de 100 elementos
cada, descritos como:
W1 = {i · 1000 | i ∈ Z, 1 ≤ i ≤ 100}
W2 = {i · 1001 | i ∈ Z, 1 ≤ i ≤ 100}
W3 = {i · 1002 | i ∈ Z, 1 ≤ i ≤ 100}
Assim para qualquer inteiro 1 ≤ w ≤ 106 temos 3 casos:
a) se 1 ≤ w ≤ 102 , para todo w podemos formá-lo utilizando apenas um elemento do
conjunto W1 .
b) se 102 < w ≤ 104 , podemos formar w somando exatamente dois elementos: um
pertencente a W1 representando as duas primeiras casas decimais e outro a repre-
sentando as ultimas duas W2 .
c) se 104 < w ≤ 106 , podemos formar w somando exatamente três elementos distintos:
um de W1 , um de W2 e um de W3 com o terceiro representando as duas ultimas
casas decimais expandindo do ultimo caso.
Desse modo, e necessário apenas que para todo w a resposta seja a união entre W1 ,
W2 e W3 .
2 G - P07 (AtCoder - abc249_d)
O problema nos da uma sequência de inteiros A = (A1 ,. . . ,AN ) de tamanho N, e pede
como resposta o numero de triplas de indices (i,j,k) que satisfaçam as seguintes condições:
• 1 ≤ i,j,k ≤ N
1
• Ai
Aj
= Ak
• 1 ≤ N ≤ 2 × 105
• 1 ≤ Ai ≤ 2 × 105 (1 ≤ i ≤ N )
2.1 Solução
Vamos resolver esse problema usando combinatoria, para isto primeiro precisamos rear-
ranjar todos os Ai da sequencia em um Heat-map de tamanho K = 2 × 105 + 1 assim
podemos guardar o numero de ocorrencias de cada numero da sequencia e teremos uma
variavel max que guarda qual é o maior numero da sequencia, ademais devemos mani-
pular a expressão AAji = Ak para Ai = Aj × Ak para facilitar o trabalho de encontrar as
triplas. Tendo esse Heat-map que, relaciona o indice do Array com o numero de ocorren-
cias daquele índice na sequência, podemos encontrar para todo inteiro i nessa sêquencia
o numero de triplas de indices que o envolvem e satisfazem as condições estabelecidas,
utilizando um for sobre todos os indices a partir do i escolhido até que i × j seja maior
que max + 1, multiplicando as ocorrencias dos indices i,j e i × j (que nessa contrução são
os numeros dos indices correspondentes a j, k, i respectivamente)
1 for ( int i = 1; i < max + 1; i ++) {
2 for ( int j = i ; j * i < max + 1; j ++) {
3 /* O if abaixo verifica se os indices sao distintos
4 e multiplicando a resposta por 2 , contando a possivel
5 permutacao de indices na multiplicacao da tripla */
6 if ( i != j ) res += ( o [ i ] * o [ j ] * o [ i * j ]) * 2;
7 else res += o [ i ] * o [ j ] * o [ i * j ];
8 }
9 }
2.2 Análise de Complexidade
Seja N = max. O laço externo itera sobre a variável i de 1 até N . Para cada valor de i,
o laço interno itera sobre a variável j começando de i enquanto a condição i × j ≤ N for
verdadeira. Isso implica que, para um dado i, o laço interno executa no máximo Ni vezes.
Para determinar o número total de iterações, devemos somar as execuções do laço
interno para todos os possíveis valores do laço externo:
N N
X N X 1
=N
i=1
i i=1
i
Sabemos que o somatório i=1 i representa a série harmônica, cuja soma diverge
PN 1
logaritmicamente. Podemos aproximá-la da seguinte forma:
N
X 1
≈ log N
i=1
i
Substituindo essa aproximação na nossa equação original, concluímos que o número
de operações é proporcional a:
2
N log N
Portanto, a complexidade de tempo do algoritmo é limitada por O(N log N ), tornando
a execução viável para a densidade de dados apresentados pelo problema.