Regional da Maratona de Programação 2020

Aconteceu no dia 14 de Novembro de forma remota a etapa da regional da Maratona de Programação. O resultado completo pode ser conferido aqui. Em 2020 a sede Goiânia teve 24 times de 6 instituições de todo o estado, ambos realizaram a prova de forma remota. As 10 melhores equipes podem ser vistas na imagem abaixo.

Top 10 - Regional Maratona de Programação 2020 - Sede Goiânia

As equipes “Monkeys” do INF-UFG e BalloonField da PUC-Goiás se classificaram para a fase nacional da maratona que acontecerá nos dias 11 a 13 de março de 2021 online. Boa sorte!

A prova esse ano veio de uma forma diferente já que seria realizada de forma remota, questões que não exirgiam muito código e mais raciocínio e com um nível interessante. As dicas de soluções dos juizes podem ser encontradas aqui. Além disso, algumas explicações mais elaboradas e exemplos de implementação podem ser encontradas abaixo.

Problema	Dificuldade	Técnica relacionada
A - Álbum de Figurinhas	médio	programação dinâmica + matemática
B - Batalha Naval	balão++	implementação
C - Concatenando Times	difícil	strings
D - Dança da Divisibilidade	difícil	algebra, exponeciação de matriz, recorrência linear
E - Empresa de Festas	médio	grafos, dfs, lca
F - Fastminton	fácil	adhoc
G - Game Show!	fácil	programação dinâmica
H - Hangar do SBC	fácil/médio	adhoc, miscellaneous
I - Interatividade	médio	programação dinâmica, dfs
J - Juntando Dados	difícil	geometria, algebra
K - Ká entre Nós	médio/difícil	algebra, gauss
L - Lavaspar	fácil	adhoc
M - Metralhadora	fácil	persistent segment tree, sweep line, binary search
N - Números Multiplicados	fácil/médio	crivo, matemática
O - Ônibus Venusiano	difícil	geometria, line sweep

A - Álbum de Figurinhas

	#include <bits/stdc++.h>

	using namespace std;

	const int N = int(1e6) + 10;
	double dp[N];

	int main(){
	int n, a, b;

	scanf("%d %d %d", &n, &a, &b);

	// printf("%.6lf\n", solve(n, a, b));

	// return 0;
	if(a != 0){
	for(int i = 1 ; i < a ; i++){
	dp[i] = 1.0;
	}

	double pref = 0.0;

	for(int i = a ; i <= n ; i++){
	int t = b - a + 1;

	pref += dp[i - a];

	if(i - b - 1 >= 0){
	pref -= dp[i - b - 1];
	}

	double val =1.0 + (pref / double(t));

	dp[i] = val;
	}
	}else{
	double pref = 0.0;

	for(int i = 1 ; i <= n ; i++){
	int t = b - a + 1;

	if(i){
	pref += dp[i - 1];
	}

	if(i - b - 1 >= 0){
	pref -= dp[i - b - 1];
	}

	dp[i] = ((double(t) + pref) / t) / (1.0 - double(1.0 / t));
	}
	}

	printf("%.7lf\n", dp[n]);

	return 0;
	}

view raw a.cpp hosted with ❤ by GitHub

B - Batalha Naval

	#include <bits/stdc++.h>

	using namespace std;

	int cnt[100][100];

	int main(){
	int n;

	scanf("%d", &n);

	bool ok = true;

	for(int i = 0 ; i < n ; i++){
	int d, l, r, c;

	scanf("%d %d %d %d", &d, &l, &r, &c);

	if(d){
	while(l){
	if(r > 10 \|\| c > 10){
	ok = false;
	break;
	}

	if(cnt[r][c] > 0){
	ok = false;
	break;
	}

	cnt[r][c]++;
	r++;
	l--;
	}
	}else{
	while(l){
	if(r > 10 \|\| c > 10){
	ok = false;
	break;
	}

	if(cnt[r][c] > 0){
	ok = false;
	break;
	}

	cnt[r][c]++;
	c++;
	l--;
	}
	}

	if(!ok){
	break;
	}
	}

	if(ok){
	printf("Y\n");
	}else{
	printf("N\n");
	}

	return 0;
	}

view raw b.cpp hosted with ❤ by GitHub

C - Concatenando Times

Em breve

D - Dança da Divisibilidade

Em breve

E - Empresa de Festas

Em breve

F - Fastminton

Em breve

G - Game Show!

Em breve

H - Hangar do SBC

Em breve

I - Interatividade

Em breve

J - Juntando Dados

Em breve

K - Ká entre Nós

Em breve

L - Lavaspar

Em breve

M - Metralhadora

Em breve

N - Números Multiplicados

	#include <bits/stdc++.h>

	using namespace std;

	typedef unsigned long long ll;
	typedef pair< int, int > pii;

	const int N = 31622776 + 10;
	const int M = int(2e3) +100;
	int lp[N+1];
	vector< ll > primes;
	vector< pii > adj[N];
	ll sum[M];
	ll a[M];
	ll ans[M];

	void sieve(){
	for (int i=2; i< N; ++i) {
	if (lp[i] == 0) {
	lp[i] = i;
	primes.push_back (i);
	}
	for (int j=0; j<(int)primes.size() && primes[j]<=lp[i] && i*primes[j]<=N; ++j)
	lp[i * primes[j]] = primes[j];
	}
	}

	int main(){
	sieve();
	// printf("%lu\n", primes.size());

	int m, n, k;

	scanf("%d %d %d", &m, &n, &k);

	for(int i = 1 ; i <= n ; i++){
	scanf("%lld", &a[i]);
	}

	for(int i = 0 ; i < k ; i++){
	int l, r, d;

	scanf("%d %d %d", &l, &r, &d);
	if(sum[l] == 0)
	sum[l] += a[r];

	adj[r].push_back({l, d});
	}

	int j = 0;
	int i = 1;

	while(j < primes.size()){
	while(i <= m && j < primes.size()){
	if(sum[i] % primes[j] == 0LL){
	ans[i] = primes[j];
	break;
	}

	j++;
	}

	i++;
	j++;
	}

	for(int i = 1 ; i <= n ; i++){
	int pt = -1;
	// printf("%lu\n", adj[i].size());

	for(auto u: adj[i]){
	// printf("%d %d\n", i, u.first);
	if(ans[u.first]){
	// printf("entrei %d %d\n", i, u.first);

	while(u.second){
	a[i] /= ans[u.first];
	u.second--;
	}
	}else{
	pt = u.first;
	}
	}

	// printf("%lld\n", a[i]);

	if(pt != -1){
	ans[pt] = a[i];
	}
	}

	for(int i = 1 ; i <= m ; i++){
	assert(ans[i] != 0);
	printf("%lld ", ans[i]);
	}

	printf("\n");

	return 0;
	}

view raw n.cpp hosted with ❤ by GitHub

O - Ônibus Venusiano

Em breve

Edit this post on GitHub