Upsolving Maratona regional ICPC 2019
Hora de alguém movimentar esse site aqui pra fazer valer a pena (manter site é caro demais para ninguem utilizar).
Me chamo João Vitor Fröhlich (joaovitor01) e estarei realizando aqui um upsolving das questões que caíram na maratona regional de 2019.
Vou estar disponibilizando também um código que solucione a questão, lembrando que o código não corresponde à melhor solução, além de que é no mínimo interessante a produção do próprio código, ou seja, olhe o código somente se você não foi capaz de programar a própria solução (ou pra comparar também).
Cada problema terá um link para o problema na plataforma Uri Online Judge.
Dito isso, aproveite a leitura
Aquecimento
Problema A
Teleférico
Solução disponivel na própria prova.
Problema B
O problema se baseia em dado um valor $N$, descobrir qual a menor quantidade de $k$ fatorias são necessários tal que $N = a! + b! + ... + z!$, sendo ${a,b,...,z}$ inteiros positivos menores que $k$.
Um valor $N$ pode ser descrito da forma $N = a! + b! + c!$ Sabemos que:
$$\frac{N}{c!} = \frac{a!}{c!} + \frac{b!}{c!} + \frac{c!}{c!}$$
$$\frac{N}{c!} = \frac{a!}{c!} + \frac{b!}{c!} + 1$$
Se considerarmos como sendo divisão inteira temos
$$\frac{N}{c!} = 0 + 0 + 1$$
Isso nos mostra que se $c!$ pertencer a soma, $\frac{N}{c!} == 1$.
Então para minimizar $k$, precisamos adotar uma estratégia greedy começando por pegar os maiores valores até zerar $N$.
Por fim, realizamos uma operação modular em $N$ para retirar o fatorial da soma. Com a finalidade de otimizar a consulta do fatorial, utilizamos a técnica de programação dinâmica.
Solução em Python3
def fats(x):
ans = 1
for i in range(2,x+1):
ans *= i
return ans
fat = [fats(i) for i in range(1,10)]
n = int(input())
ans = 0
for i in range(8,-1,-1):
ans += n//fat[i]
n %= fat[i]
print(ans)
Problema C
Este problema consiste em descobrir $B$ tal que $M = (A+B) / 2$
Sabemos $M$ e $A$, então isolando $B$ obtemos:
$$B = 2*M - A$$
Solução em Python3
A = int(input())
M = int(input())
B = 2*M - A
print(B)
Prova Principal
Problema A
O problema consiste em encontrar um caminho entre o canto inferior esquerdo e o canto superior direito de um retângulo, evitando passar pela área dos sensores de presença, que possuem um raio r e um par de coordenadas (x,y).
Para esse problema é interessante perceber as seguintes propriedades:
-
É possível passar entre dois círculos se e somente se eles não se interseccionam
-
Um círculo impede a passagem da sala se:
- As extremidades do círculo interseccionam as delimitantes do retângulo superior e inferior
- As extremidades do círculo interseccionam as delimitantes do retângulo esquerda e direita
- As extremidades do círculo interseccionam as delimitantes do retângulo esquerda e inferior
- As extremidades do círculo interseccionam as delimitantes do retângulo direita e superior
Note que ao aplicar a primeira propriedade, é possível gerar um conjunto de circunferências de forma que as extremidades desse conjunto serão dadas pelas:
- Extremidade mais a esquerda de todos os círculos do conjunto;
- Extremidade mais a direita de todos os círculos do conjunto;
- Extremidade mais superior de todos os círculos do conjunto;
- Extremidade mais inferior de todos os círculos do conjunto.
Assim, para solucionarmos o problema, basta armazenamos os conjuntos de circunferências em vetores e, em seguida, testarmos se um conjunto de circunferências é capaz de impedir a passagem. Retornamos "N" caso um ou mais conjunto são capazes de impedir a passagem pela sala, ou retornamos "S" caso contrário.
Solução em C++
#include <bits/stdc++.h>
using namespace std;
struct point{
int x, y;
point () { x = y = 0; }
point(int _x, int _y) : x(_x), y(_y) {}
};
double dist (point p1, point p2){
return hypot(p1.x-p2.x, p1.y-p2.y);
}
struct circle{
point c;
int r;
int idx;
circle () { c = point(); r = 0; idx = 0; }
circle(point _c, int _r, int _idx) : c(_c), r(_r), idx(_idx) {}
};
bool inter(circle c1, circle c2){
return dist(c1.c, c2.c) <= c1.r+c2.r;
}
#define pb push_back
int main(int argc, char const *argv[]) {
int n,m,k;
int x,y,r;
cin >> n >> m >> k;
vector <circle> c;
vector<vector <circle> > circles;
for (int i = 0; i < k; i++){
cin >> x >> y >> r;
c.pb(circle(point(x,y),r,-1));
}
for (int i = 0; i < k; i++){
for (int j = 0; j < k; j++){
if (i == j) continue;
if (inter(c[i],c[j])){
if (c[i].idx != -1 || c[j].idx != -1){
if (c[i].idx == c[j].idx) continue;
else if (c[i].idx == -1 || c[j].idx == -1){
int idx;
if (c[i].idx == -1) {
idx = c[j].idx;
circles[idx].pb(c[i]);
c[i].idx = idx;
} else {
idx = c[i].idx;
circles[idx].pb(c[j]);
c[j].idx = idx;
}
} else {
int idx1 = c[i].idx, idx2 = c[j].idx;
for (int i = 0; i < circles[idx2].size(); i++){
circles[idx1].pb(circles[idx2][i]);
circles[idx2][i].idx = idx1;
}
circles[idx2] = vector<circle> ();
}
} else {
int idx = circles.size();
c[i].idx = idx;
c[j].idx = idx;
circles.pb(vector<circle> ({c[i],c[j]}));
}
}
}
if (c[i].idx == -1){
circles.pb(vector<circle> ({c[i]}));
}
}
for (int i = 0; i < circles.size(); i++) {
int minX = n+1, maxX = 0, minY = m+1, maxY = 0;
for (int j = 0; j < circles[i].size(); j++){
circle caux = circles[i][j];
minX = min(minX, caux.c.x-caux.r);
maxX = max(maxX, caux.c.x+caux.r);
minY = min(minY, caux.c.y-caux.r);
maxY = max(maxY, caux.c.y+caux.r);
}
if ((minX <= 0 && (maxX >= n || minY <= 0)) || (maxY >= m && (minY <= 0 || maxX >= n))){
cout << "N" << endl;
return 0;
}
}
cout << "S" << endl;
return 0;
}
Problema B
Para esse problema, nos é dado um vetor de entrada V, com N elementos, e é requerido que encontremos dentro desse vetor um valor que seja maior que o primeiro valor do vetor.
Podemos solucionar esse problema sem a necessidade de um vetor, testando os valores inseridos na entrada, otimizando o tempo gasto para rodar o algoritmo.
Para isso, basta lermos o valor de N, o primeiro valor de V, e então para i = 2; i <= N, lemos os valores restantes e comparamos com o primeiro valor, gerando o resultado final a partir de uma variável booleana.
Solução em C++
#include <bits/stdc++.h>
using namespace std;
int main(int argc, char const *argv[]) {
int n, x, foo;
cin >> n;
cin >> foo;
bool v = true;
for (int i = 1; i < n; i++){
cin >> x;
if (x > foo){
v = false;
}
}
if (v) cout << "S" << endl;
else cout << "N" << endl;
return 0;
}
Problema D
Nesse problema precisamos encontrar o maior número de mafiosos em uma hierarquia podendo saber os crimes de apenas K pessoas.
Note que como o topo da hierarquia sempre pertence ao nó 1, podemos facilmente modelar esse problema utilizando uma árvore, onde cada elemento possui um nó pai e uma profundidade. Após a entrada de dados, precisamos encontrar a profundidade de todos os nós. Para isso, rodamos um DFS a partir do nó raiz da árvore.
Em seguida, com a profundidade de cada nó, precisamos encontrar quantas pessoas podem ser presas a partir de uma folha. Para isso, rodamos um DFS com DP em todos os nós, começando com os nós de menor profundidade e subindo a árvore, denotando para cada nó, o tamanho do caminho até a parte mais baixa da árvore. Perceba que caso um nó tenha 2 ou mais filhos, é interessante manter o nó cujo caminho seja maior. Os outros nós armazenaremos em um fila de prioridade.
Quando terminarmos de percorrer todos os nós, temos como resultado o tamanho do maior caminho até a parte mais baixa da árvore, enquanto os outros caminhos estarão armazenados de forma decrescente. Feito isso, basta agora pegar da fila K-1 elementos e somá-los com o resultado que ja tinhamos. Esse é o resultado que deve ser imprimido.
Solução em C++
#include <bits/stdc++.h>
using namespace std;
vector<vector<int> > adjList;
vector<pair<int, int> > r;
vector<int> parent;
vector<int> vis;
priority_queue<int> pq;
void busca_rank(int o){
for (int i = 0; i < adjList[o].size(); i++){
int idx = adjList[o][i];
r[idx].first = r[o].first-1;
busca_rank(idx);
}
}
int dfs(int o){
if (vis[o] != -1) return vis[o];
int m = 0;
for (int i = 0; i < adjList[o].size(); i++){
int tam = dfs(adjList[o][i]);
if (tam > m){
if (m != 0) pq.push(m);
m = tam;
} else pq.push(tam);
}
vis[o] = m+1;
return vis[o];
}
int main(int argc, char const *argv[]) {
int n, k, x;
cin >> n >> k;
adjList.resize(n);
vis.push_back(-1);
r.push_back(make_pair(n,0));
parent.push_back(-1);
for (int i = 1; i < n; i++){
vis.push_back(-1);
r.push_back(make_pair(n,i));
cin >> x;
x--;
parent.push_back(x);
adjList[x].push_back(i);
}
busca_rank(0);
sort(r.begin(), r.end());
int res;
for (int i = 0; i < n; i++){
res = dfs(r[i].second);
}
for (int i = 0; i < k-1; i++){
res += pq.top();
pq.pop();
}
cout << res << endl;
return 0;
}
Problema H
Nesse problema nos é fornecido o comprimento de uma volta (N) e o número de voltas (V) que serão percorridas, e precisamos fornecer a distância de cada 10% do trajeto até 90%.
A primeira coisa que precisamos fazer é encontrarmos a distância total do percurso $dt = N*V$.
Após isso, basta fazer uma iteração de 1 a 9, imprimindo o resultado da operação:
$$\sum_{i=1}^{9} \frac{dt}{0.1*i}$$
Solução em C++
#include <bits/stdc++.h>
using namespace std;
int main(){
int a,b,c;
cin >> a >> b;
c = a*b;
printf("%d",(int)(ceil(c*0.1)));
for (int i = 2; i < 10; i++){
printf(" %d", (int)(ceil(c*(i/10.0))));
}
cout << endl;
return 0;
}
Problema J
O problema consiste basicamente em simular o jogo até chegar em uma condição de vitória,e como o problema possui constantes pequenas, somos capazes de executar a simulação em pouco tempo.
Para facilitar o código transformamos as cartas em números de 0 a 12, inserindo a quantidade de cartas que aparecem para cada jogador em uma matriz de dimensões Nx13.
Indiquei também a posição e o status do coringa em um vetor de N posições.
Deve-se atentar ao fato de que pode-se ter um estado vencedor antes de começar a simulação.
No final apenas imprimimos o valor correspondente ao jogador vencedor.
Solução em C++
#include <bits/stdc++.h>
using namespace std;
#define NT 0
#define MANTER 1
#define PASSAR 2
int transformaChar(char c){
if (c == 'A') return 0;
else if (c == 'D') return 9;
else if (c == 'Q') return 10;
else if (c == 'J') return 11;
else if (c == 'K') return 12;
else return ((int)c)-49;
}
int main(int argc, char const *argv[]) {
int n,k, vencedor = 0;
char jogo[4];
cin >> n >> k;
int coringa[n];
int jogos[n][13];
for (int i = 0; i < n; i++){
for (int j = 0; j < 13; j++){
jogos[i][j] = 0;
}
cin >> jogo;
if (i == k-1) coringa[i] = MANTER;
else coringa[i] = NT;
for (int j = 0; j < 4; j++){
jogos[i][transformaChar(jogo[j])]++;
}
if (jogos[i][transformaChar(jogo[0])] == 4 && vencedor == 0 && coringa[i] == NT){
vencedor = i+1;
}
}
int jogador = k-1, proximoJogador;
bool passou;
while (vencedor == 0){
passou = false;
int cartasDuplas[2] = {-1,-1};
if (jogador != n-1){
proximoJogador = jogador+1;
} else {
proximoJogador = 0;
}
if (coringa[jogador] == PASSAR){
for (int i = 0; i < 13; i++){
if (jogos[jogador][i] == 4) vencedor = jogador+1;
}
coringa[proximoJogador] = MANTER;
coringa[jogador] = NT;
jogador = proximoJogador;
continue;
} else if (coringa[jogador] == MANTER){
coringa[jogador] = PASSAR;
}
for (int i = 0; i < 13; i++){
if (jogos[jogador][i] == 1){
if (passou) continue;
jogos[proximoJogador][i]++;
jogos[jogador][i]--;
passou = true;
} else if (jogos[jogador][i] == 2){
if (passou) continue;
if (cartasDuplas[0] == -1) cartasDuplas[0] = i;
else cartasDuplas[1] = i;
} else if (jogos[jogador][i] == 3) {
cartasDuplas[1] = i;
} else if (jogos[jogador][i] == 4){
if (coringa[jogador] == NT){
vencedor = jogador+1;
} else {
jogos[proximoJogador][i]++;
jogos[jogador][i]--;
}
break;
}
}
if (cartasDuplas[0] != -1 && cartasDuplas[1] != -1 && !passou){
jogos[proximoJogador][cartasDuplas[0]]++;
jogos[jogador][cartasDuplas[0]]--;
}
jogador = proximoJogador;
}
cout << vencedor << endl;
return 0;
}
Problema M
Maratona Brasileira de Comedores de Pipoca
O problema consiste em encontrar um número [1,C] de subsequencias, onde a subsequencia que possua a maior soma tenha a soma de valor minimo.
São fornecidos os dados de quantidade elementos da sequencia principal $N$, a quantidade máxima de subsequencias $C$ e quantas pipocas serão consumidas por segundo $T$. Também serão fornecidos $N$ valores, onde cada valor $p_{i}$ representa a quantidade de pipocas por elemento.
Para resolvermos esse problema, iremos inicialmente testar um valor $x = 2^{\log_2 \frac{M}{T}}$, onde $M$ representa o elemento com maior quantidade de pipocas. Esse valor $x$ representa o valor máximo da soma de uma subsequência. Note que $x = 2^{a}$, $a \in \mathbb{N}$, com isso denotaremos uma variável $aux = 2^{a-1}$.
Após obtermos $x$, encontraremos a quantidade de subsequências necessárias para obedecer ao valor $x$, que denotaremos $contador$.
Realizaremos agora uma implementação na forma de uma busca binária:
- Caso $contador \leq C$, calcularemos $x = \frac{x-a}{2}$ e armazenamos $x$ como resposta temporaria $R$.
- Caso contrário, utilizaremos duas abordagens diferentes:
- Caso ainda não tenha acontecido $contador \leq C$, $aux = x$ e $x = x*2$
- Caso contrario, denotaremos $aux_2 = \frac{x-a}{2}$ e atribuiremos $aux = x$ e $x = x+aux_2$
Quando encerrarmos a busca binária basta imprimir o valor de $R$
Solução em C++
#include <bits/stdc++.h>
using namespace std;
int main(int argc, char const *argv[]) {
int n,c,t,x,m=0,mi,aux=1,ret;
bool v = false;
cin >> n >> c >> t;
int s[n];
for (int i = 0; i < n; i++){
cin >> s[i];
m = max(m,s[i]);
}
x = pow(2,(int) ceil(log2(m/t)));
mi = x/2;
while (aux != 0){
int sa = 0;
int cont = 0;
for (int i = 0; i < n; i++){
if (ceil(s[i]*1.0/t) > x || cont == c){
cont = c+1;
break;
}
if (ceil((double)(sa + s[i])/(t*1.0)) <= x){
sa += s[i];
} else {
cont++;
sa = s[i];
}
}
cont++;
aux = (x-mi)/2;
if (cont <= c){
ret = x;
v = true;
x -= aux;
} else if (v){
mi = x;
x += aux;
} else {
aux = 1;
mi = x;
x = x*2;
}
}
cout << ret << endl;
return 0;
}