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;
}