Desafios de Programação no Verão

Desafios de Programação no Verão de 2011 - Prova 14 - Individual

» 01 de fevereiro de 2011

Hora de início: 2011-02-01 09:10:00 -0200   Hora de término: 2011-02-01 13:10:00 -0200

Problemas

POS Competidor Resultado Pontuação A B C D E F G H  
1 walter erquinigo 7 (840) 99 +1 +0 +0 +0   +2 +1 +0  
2 Cesar Kawakami 6 (659) 97   +0 +1 +0   +3 +0 +0  
3 Guilherme Souza 6 (663) 95 -4 +0 +5 +0   +1 +0 +1  
4 Eric Destefanis 6 (743) 93 -4 +0 +1 +3   +1 +0 +1  
5 Thiago Sonego Goulart 6 (750) 91   +0 +4 +1   +0 +0 +0  
6 Eduardo Ribas 5 (423) 89   +0 -8 +0   +0 +0 +0  
7 Gabriel Luís Mello Dalalio 5 (469) 87     +1 +0   +1 +0 +0  
8 Felipe Abella 5 (585) 85   +1 -3 +0   +0 +0 +0  
9 Luiz Afonso 5 (603) 83   -1 +0 +0   +0 +0 +0  
10 Tiago Madeira 5 (665) 81     +5 +0   +1 +0 +1  
11 Gaston Ingaramo 5 (707) 79   +0 -2 +2   +0 +1 +3  
12 Filipe Martins 5 (793) 77   +0 +1 +1     +2 +2  
13 Atol Fortin 5 (937) 75   +2   +0   +0 +3 +4  
14 Andre Hahn 4 (332) 73   -3   +0   +0 +1 +0  
15 Leonardo Marchetti 4 (347) 71 -3     +0   +1 +0 +0  
16 Pedro Veras 4 (366) 69     -2 +0   +0 +2 +0  
17 Renato Parente 4 (394) 67   -1 -1 +0   +0 +0 +1  
18 Jesus Alejandro 4 (428) 65   +1   +1     +0 +0  
19 Felipe Menezes Machado 4 (488) 63       +0   +0 +3 +0  
20 Daniel Ribeiro Moreira 4 (500) 61   -3 +1 +0   +0 -3 +1  
21 Paulo Costa 4 (636) 59   -1   +3 -2 +0 +2 +1  
22 Leonardo Inácio 4 (639) 57       +2   +0 +2 +0  
23 daniel soncco 4 (642) 55 +0     +1 +2     +0  
24 Leonardo Martinez 3 (259) 53       +0     +0 +0  
25 Natan Costa Lima 3 (304) 51       +0   -1 +2 +1  
26 Phyllipe Cesar 3 (321) 49       +0   -4 +2 +0  
27 Matias Daniel Tealdi 3 (330) 47       +1   -1 +0 +0  
28 Igor Ramos 3 (399) 45       +1     +4 +1  
29 Davi Duarte Pinheiro 3 (413) 43       +0     +2 +2  
30 Cesar Gamboa 3 (427) 41 -3     +0     +1 +2  
31 Igor R. de Assis 3 (432) 39       +2   -2 +3 +2  
32 Arthur 3 (435) 37   -4   +0     +1 +4  
33 Vinicius Ruoso 3 (459) 35       +0     +3 +1  
34 Pablo Pinheiro 3 (556) 33       +3     +2 +2  
35 Ricardo Oliveira 2 (85) 31       +0   -3 -4 +0  
36 Adriana Libório 2 (122) 29       +0     -5 +0  
37 Renan Ferraz Pires 2 (154) 27       +1     -6 +0  
38 Rafael Brandão 2 (160) 25   -2   +2       +0  
39 Edwin Macelo Guzman Buezo 2 (239) 23       +1       +0  
40 Caique Porto Lira 2 (471) 21       +5     -1 +2  
41 Douglas Santos 1 (30) 19       -3   -1   +0  
46 Vinicius Flores Zambaldi 1 (84) 9             -7 +0  
46 gustavo pacianotto gouveia 0 (0) 9                  
46 Ricardo Hahn 0 (0) 9                  
46 Leonardo Flores Zambaldi 0 (0) 9                  
46 Alex Alves da Paixão 0 (0) 9               -4  
46 Nicolas Gumiel 0 (0) 9       -5          
46 Victor Hugo Paredes Mora 0 (0) 9       -3          
46 Victor Jatobá 0 (0) 9       -1       -3  
46 Renato Ferreira 0 (0) 9                 </div>

Vídeo: Discussão sobre os problemas

Algumas soluções dos competidores

A cycle of divisors (por Thiago Sonego Goulart)

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <utility>
#include <vector>

using namespace std;

#define MAX 10000000

long long primes[700000];
int nprimes;
char isprime[MAX+1];

void sieve() {
	memset(isprime,-1,sizeof(isprime));
	isprime[0] = isprime[1] = 0;
	isprime[2] = nprimes = 1;
	primes[0] = 2;
	for (int i=4; i <= MAX; i+=2) {
		isprime[i] = 0;
	}
	for (int i=3; i <= MAX; i+=2) {
		if (isprime[i] == -1) {
			isprime[i] = 1;
			primes[nprimes++] = i;
			for (int j=2*i; j <= MAX; j+=i) {
				isprime[j] = 0;
			}
		}
	}
}

long long gcd(long long a, long long b) {
	return b ? gcd(b,a%b) : a;
}

set <long long> specials;

vector < pair<long long,int> > factorize(long long n) {
	vector < pair<long long,int> > fact;
	for (int i=0; i < nprimes && primes[i]*primes[i] <= n; i++) {
		int q = 0;
		while (n%primes[i] == 0) {
			n /= primes[i];
			q++;
		}
		if (q) fact.push_back(make_pair(primes[i],q));
	}
	if (n != 1) {
		fact.push_back(make_pair(n,1));
	}
	return fact;
}

struct Number {
	long long n;
	vector < pair<long long,int> > fact;
	bool special;
	Number(long long a) {
		n = a;
		fact = factorize(n);
		special = (specials.find(n) != specials.end());
	}
	bool operator <(const Number &N) const {
		
		if (special) {
			return fact[0].first < N.fact[0].first;
		}
		
		if (N.special) {
			return fact[0].first <= N.fact[0].first;
		}
		
		int i;
		for (i=0; i < fact.size() && i < N.fact.size(); i++) {
			if (fact[i].first != N.fact[i].first) {
				return fact[i].first < N.fact[i].first;
			}
		}
		return fact.size() < N.fact.size();
	}
};

int main() {
	long long n;
	
	sieve();
	
	while (scanf("%lld",&n) == 1) {
		vector <Number> divs;
		Number N(n);
		
		if (N.fact.size() == 1 && N.fact[0].second == 1) {
			printf("%lld\n",n);
			continue;
		}
		
		specials.clear();
		
		vector < pair<long long,int> > fac = factorize(n);
		
		for (int i=1; i < fac.size(); i++) {
			specials.insert(fac[i].first * fac[i-1].first);
		}
		
		for (long long i=2; i*i <= n; i++) {
			if (n % i == 0) {
				divs.push_back(Number(i));
				if (i*i != n) {
					divs.push_back(Number(n/i));
				}
			}
		}
		//if (divs.size() > 1) printf("%d %d %d %d\n",divs.size() == 0,divs.size() == 2,divs[0].fact.size() == 1,divs[1].fact.size() == 1);
		if (divs.size() == 0 || (divs.size() == 2 && divs[0].fact.size() == 1 && divs[1].fact.size() == 1 && gcd(divs[0].n,divs[1].n) == 1)) {
			puts("0");
			continue;
		}
		
		sort(divs.begin(),divs.end());
		
		divs.push_back(N);
		
		for (int i=0; i < divs.size(); i++) {
			if (i) printf(" ");
			printf("%lld",divs[i].n);
		}
		puts("");
	}
	
	
    return 0;
}

Grid game (por Felipe Abella)

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <map>
#include <cstring>
#define MAXN 126

using namespace std;
typedef long long lint;

int origmatrix[2+2*MAXN][2+2*MAXN], matrix[2+2*MAXN][2+2*MAXN];
int caps[2+2*MAXN][2+2*MAXN];
int mark[2+2*MAXN], prev[2+2*MAXN];
int mindist[2+2*MAXN];

int main()
{
  int ntest;

  scanf("%d", &ntest);

  for (int t = 0; t < ntest; t++) {
    int n;

    scanf("%d", &n);

    memset(matrix, 0, sizeof(matrix));
    memset(origmatrix, 0, sizeof(origmatrix));
    for (int y = 0; y < n; y++)
      for (int x = 0; x < n; x++) {
	scanf("%d", &origmatrix[y+2][n+x+2]);
	origmatrix[n+x+2][y+2] = -origmatrix[y+2][n+x+2];
      }

    for (int y = 0; y < n; y++)
      for (int x = 0; x < n; x++) {
	matrix[y+2][n+x+2] = origmatrix[y+2][n+x+2] + 1024;
	matrix[n+x+2][y+2] = -(origmatrix[y+2][n+x+2] + 1024);
      }

    int nnode = 2*n+2;

    memset(caps, 0, sizeof(caps));
    for (int y = 0; y < n; y++)
      for (int x = 0; x < n; x++)
	caps[2+y][2+n+x] = 1;

    for (int y = 0; y < n; y++) {
      caps[0][2+y] = 1;
      caps[2+n+y][1] = 1;
    }

    int result = 0;

    while (1) {
      memset(prev,-1, sizeof(prev));
      memset(mark, 0, sizeof(mark));
      for (int i = 0; i < nnode; i++)
	mindist[i] = 500000;
      mindist[0] = 0;
      prev[0] = -2;

      int current = 0;
      do {
	mark[current] = 1;
	for (int i = 0; i < nnode; i++)
	  if (caps[current][i] > 0 && mindist[i] > mindist[current] + matrix[current][i]) {
	    prev[i] = current;
	    mindist[i] = mindist[current] + matrix[current][i];
	  }

	current = -1;
	for (int i = 0; i < nnode; i++)
	  if (!mark[i] && (current == -1 || mindist[i] < mindist[current]))
	    current = i;
      } while (current != -1);

      if (prev[1] == -1)
	break;

      int v = 1, u = prev[v];
      while (u != -2) {
	caps[u][v] --;
	caps[v][u] ++;
	result += origmatrix[u][v];

	v = u;
	u = prev[v];
      }

      for (int i = 0; i < nnode; i++)
	for (int j = 0; j < nnode; j++)
	  matrix[i][j] += mindist[i] - mindist[j];
	  
    }
    printf("%d\n", result);
  }

  return 0;
}

Power of an Integer (por Gabriel Luís Mello Dalalio)

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define INF 1000000000000000100LL
#define LIM 70

long long a, b;
long long p[LIM], phi[LIM];

long double eleva( long long base, int expo ){
	long double ret;
	if( expo==0 ){
		return 1;
	}
	else{
		ret=eleva(base,expo/2);
		ret*=ret;
		if( expo%2==1 ){
			ret*=base;
		}
		return min(ret,(long double)INF);
	}
}

long long busc( long long k, int expo ){
	long long ini, fim, meio;
	ini=0;
	fim=b;
	while( ini<fim ){
		meio=(ini+fim+1)/2;
		if( eleva(meio,expo)>k ){
			fim=meio-1;
		}
		else{
			ini=meio;		
		}
	}
	return ini;
}

unsigned long long int resp[100];

void soma( long long k ){
	int i;
	resp[0]+=k;
	for( i=0 ; resp[i]>=10 ; i++ ){
		resp[i+1]+=resp[i]/10;
		resp[i]%=10;
	}
}

int main(){
	int t, i, j;
	memset(p,0,sizeof(p));
	for( i=1 ; i<LIM ; i++ ){
		phi[i]=i;
	}
	for( i=2 ; i<LIM ; i++ ){
		if( p[i]==0 ){
			for( j=i ; j<LIM ; j+=i ){
				phi[j]/=i;
				phi[j]*=i-1;
			}
			for( j=2*i ; j<LIM ; j+=i ){
				p[j]=1;
			}
		}
	}
	for( scanf("%d",&t) ; t>0 ; t-- ){
		scanf("%lld %lld",&a,&b);
		a--;		
		memset(resp,0,sizeof(resp));
		for( i=1 ; i<LIM ; i++ ){
			soma(phi[i]*(busc(b,i)-busc(a,i)));
		}
		for( i=99 ; resp[i]==0 ; i-- );
		for( ; i>=0 ; i-- ){
			printf("%d",resp[i]);
		}
		printf("\n");
	}
	return 0;
}

Inversions… inverted! (por Felipe Abella)

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <map>
#include <cassert>

using namespace std;
typedef long long lint;

int ret[100010];

void print(int n)
{
  printf("%d", ret[0]+1);
  for (int i = 1; i < n; i++)
    printf(" %d", ret[i]+1);
  printf("\n");
}
	
int main()
{
  lint n, k;

  scanf("%lld %lld", &n, &k);

  if (k > n*(n-1LL)/2LL) {
    printf("impossible\n");
    return 0;
  }

  for (int i = 0; i < n; i++)
    ret[i] = i;

  if (k == 0) {
    print(n);
    return 0;
  }

  int j = n-1;
  while (j > 0 && k >= j) {
    k -= j;
    j--;
  }
  
  vector <int> ret2;
  for (int x = n-1; x > j; x--)
    ret2.push_back(x);
  for (int x = 0; x < j; x++)
    ret2.push_back(x);
  ret2.insert(ret2.begin()+(n-1)-k, j);

  for (int i = 0; i < n; i++)
    ret[i] = ret2[i];

  print(n);

  return 0;
}

Root of a matrix (por daniel soncco)

#include <iostream>
#include <vector>
#include <cstring>
#include <iomanip>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <cmath>
#include <algorithm>
#include <cstdio>
#include <stack>
#include <sstream>

typedef long long ll;
#define f(i,x,y) for(int i = x; i<y; i++ )
#define fd(i,x,y) for(int i = x; i>=y; i-- )
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define oo (1<<30)
#define eps (1e-9)
#define clr(A,x) memset( A,x,sizeof(A) )
#define CLR(A) f(i,0,n) A[i].clear()
#define vint vector<int>
#define poner push_back

using namespace std;

int n,k;
double A[100][100];

int main(){
	f(i,0,100)f(j,0,100) A[i][j] = 0;
	cin >> n >> k;
	double pi = acos(-1);
//	printf( "%.10f\n",  pi );
	double teta = 2*pi/k;
	bool ok = 1;
	double x,y,z,w;
	if( k!=4 ) x=w=cos(teta), y = sin(teta), z = -sin(teta);
	else x = 2,w=-2, y = sqrt(5), z = -sqrt(5);
	
	if( (n&1)==0 ){
		
		f(i,0,n/2){
			A[2*i][2*i]  = x;
			A[2*i+1][2*i+1] = w;
			A[2*i][2*i+1] = y;
			A[2*i+1][2*i] = z;
		}
	}else if( (k&1)==0 ){
		f(i,0,n/2){
			A[2*i][2*i]  = x;
			A[2*i+1][2*i+1] = w;
			A[2*i][2*i+1] = y;
			A[2*i+1][2*i] = z;
		}
		A[n-1][n-1] = -1;
	}else{
		f(i,0,n/2 - 1){
			A[2*i+3][2*i+3]  = x;
			A[2*i+1+3][2*i+1+3] = w;
			A[2*i+3][2*i+1+3] = y;
			A[2*i+1+3][2*i+3] = z;
		}
		double alfa = 2*pi/3;
		A[0][0] = cos(teta);
		A[0][1] = cos(alfa) * sin(teta); A[1][0] = -A[0][1];
		A[0][2] = sin(alfa) * sin(teta); A[2][0] = -A[0][2];
		A[1][1] = sin(alfa)*sin(alfa) + cos(alfa)*cos(alfa)*cos(teta);
		A[1][2] = A[2][1] = sin(alfa)*cos(alfa)*(cos(teta)-1);
		A[2][2] = sin(alfa)*sin(alfa)*cos(teta) + cos(alfa)*cos(alfa);
	}
	if( ok==0 ) puts( "Presiel som sedem chotarov, ale taku maticu som nestretol." );
	else{
		f(i,0,n)f(j,0,n){
			if( j ) printf(" ");
			printf( "%.10f", A[i][j] );
			if( j==n-1) printf( "\n" );
		}
	}
}

This sentence is false. (por Felipe Abella)

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <map>
#include <cstring>

#define MAXN 10010

using namespace std;
typedef long long lint;

int ok;
int mark[2*MAXN], myleft , myright;
vector <int> adj[2*MAXN];

void dfs(int v, int col)
{
  if (mark[v]) {
    if (col != mark[v])
      ok = 0;
    return;
  }

  mark[v] = col;
  if ((v&1)==0) {
    if ((col == 2))
      myleft++;
    else
      myright ++;
  }

  for (int i = 0; i < adj[v].size(); i++)
    dfs(adj[v][i], col^1);
}


void make_edge(int a, int b)
{
  adj[a].push_back(b);
  adj[b].push_back(a);
}

char line[1024];
int main()
{
  int n;
  
  while (scanf("%d ", &n), n) {
    for (int i = 0; i < 2*n; i++)
      adj[i].clear();

    for (int i = 0; i < n; i++) {
      int s;
      char t;

      fgets(line, 1024, stdin);
      sscanf(line, "Sentence %d is %c", &s, &t);
      s--;

      make_edge(2*i, 2*i+1);

      int no1 = 2*i, no2=2*s;
      if (t == 't') {
	make_edge(no1, no2^1);
	make_edge(no1^1, no2);
      } else
	make_edge(no1, no2);
    }

    int result = 0;
    ok = 1;
    memset(mark, 0, sizeof(mark));
    for (int i = 0; i < 2*n; i++)
      if (!mark[i]) {
	myleft = 0, myright = 0;
	dfs(i, 3);
	result += max(myleft, myright);
      }

    if (!ok)
      printf("Inconsistent\n");
    else
      printf("%d\n", result);
  }
  
  return 0;
}

School (por Felipe Abella)

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <map>

#define P 1000000009LL
#define MAXP 15485934

using namespace std;
typedef long long lint;

int isprime[MAXP];
vector <int> primes, primesum;

int main()
{
  isprime[0] = isprime[1] = 0;
  fill(isprime+2, isprime+MAXP, 1);
  for (int i = 2; i < MAXP; i++)
    if (isprime[i]) {
      if (i < 3940) {
	for (int j = i*i; j < MAXP; j += i)
	  isprime[j] = 0;
      }
      primes.push_back(i%P);
    }

  primesum.reserve(primes.size());
  lint s = 0;
  for (int i = 0; i < primes.size(); i++) {
    s += primes[i];
    s %= P;
    primesum.push_back(s);
  }

  int _n, m;
  lint result = 0;

  scanf("%d %d", &_n, &m);

  lint n = _n;

  for (lint i = 0; i < n; i++) {
    result = (result + ((lint)primes[i]) * ((((2 * (i+1) * (n-i))%P)-1+P)%P))%P;
  }

  for (int i = 0; i < m; i++) {
    lint r, s;
    scanf("%lld %lld", &r, &s);
    r--, s--;
    if (r > s)
      swap(r, s);
    result = (result - primesum[s] + P)%P;
    if (r-1 >= 0)
      result = (result + primesum[r-1])%P;
  }

  printf("%lld\n", result);

  return 0;
}

Square count (por Felipe Abella)

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;

typedef long long lint;

int list1[2000], list2[2000];

int main()
{
  int h, v;
  map <int, lint> many;

  scanf("%d %d", &h, &v);

  for (int i = 0; i < h; i++)
    scanf("%d", &list1[i]);
  for (int i = 0; i < v; i++)
    scanf("%d", &list2[i]);

  for (int i = 0; i < h; i++)  
    for (int j = i+1; j < h; j++)
      many[list1[j]-list1[i]] ++;

  lint ret = 0;
  for (int i = 0; i+1 < v; i++)
    for (int j = i+1; j < v; j++)
      ret += (lint)many[list2[j]-list2[i]];
  
  printf("%lld\n", ret);

  return 0;
}

blog comments powered by Disqus
Licença Creative Commons
Esta obra foi licenciada com uma Licença
Creative Commons - Atribuição - Uso Não-Comercial - Obras Derivadas Proibidas 3.0 Não Adaptada.