Desafios de Programação no Verão

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

» 04 de fevereiro de 2011

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

Problemas

POS Competidor Resultado Pontuação A B C D E F G H  
1 Eric Destefanis 6 (678) 99 +0   +0 +3 +1 +0 +0 -2  
2 Gabriel Luís Mello Dalalio 6 (708) 97 +1 +0 +0 +0 +0   +1    
3 walter erquinigo 6 (735) 95 +0 +1 +0 +0 +1   +2    
4 Daniel Ribeiro Moreira 5 (537) 93 +0   +0 +2 +0   +0    
5 Jesus Alejandro 5 (633) 91 +0   +0 +1 +1   +0    
6 Thiago Sonego Goulart 5 (654) 89 +0   +0 +1 +2 -4 +3    
7 Cesar Kawakami 5 (729) 87 +0   +3 +1 +0   +1    
8 Cesar Gamboa 5 (761) 85 +1   +0 +0 +1   +2    
9 Guilherme Souza 4 (198) 83 -7 -1 +0 +0 +0   +0    
10 Tiago Madeira 4 (294) 81     +2 +2 +0   +0    
11 daniel soncco 4 (329) 79     +2 +0 +0   +0    
12 Leonardo Marchetti 4 (397) 77     +0 +0 +0   +0    
13 Renato Parente 4 (430) 75 +2   +0 +2 +0        
14 Pablo Pinheiro 4 (432) 73     +0 +0 +0   +1    
15 Gaston Ingaramo 4 (464) 71 +0   +0 +0 +6        
16 Igor R. de Assis 4 (608) 69 +1   +0 +1 +5        
17 Pedro Veras 3 (174) 67     +0 +2 -4   +0    
18 Matias Daniel Tealdi 3 (210) 65 -3   +0 +2 +0        
19 Caique Porto Lira 3 (227) 63     +0 +0 -1   +0    
20 Natan Costa Lima 3 (249) 61     +0 +1 +0   -1    
21 Atol Fortin 3 (314) 59     +2 +1 +2   -11    
22 Leonardo Inácio 3 (317) 57     +0 +0 +0        
23 Arthur 3 (320) 55     +0 +0     +3    
24 Renan Ferraz Pires 3 (331) 53     +0 +0 +1        
25 Luiz Afonso 3 (399) 51     +1 +1 +0   -3    
26 Ricardo Oliveira 3 (422) 49     +0 +0 +5   -3    
27 Eduardo Ribas 3 (531) 47 -1   +9 +1 +0   -7    
28 Felipe Abella 3 (544) 45 -1   +6 +0 +1        
29 Edwin Macelo Guzman Buezo 3 (726) 43     +1 +6 +4        
30 Leonardo Martinez 2 (89) 41 -1   +0 +1     -7    
31 Douglas Santos 2 (111) 39     +0 +0 -3   -1    
32 Vinicius Ruoso 2 (158) 37     +0 +2 -1   -3    
33 Filipe Martins 2 (196) 35     +2 +1 -7        
34 Paulo Costa 2 (220) 33       +0 +0   -5    
35 Phyllipe Cesar 2 (388) 31     +7 +1          
36 Adriana Libório 2 (391) 29       +1     +6    
37 Davi Duarte Pinheiro 2 (455) 27     +2 +5     -2    
38 Nicolas Gumiel 2 (470) 25 -2   +1 +4          
39 Igor Ramos 2 (512) 23     -3 +4     +5    
40 Victor Hugo Paredes Mora 2 (616) 21 -2   +1 +9          
41 Andre Hahn 1 (14) 19     -14 +0          
42 Rafael Brandão 1 (55) 17     -3 +1          
47 Vinicius Flores Zambaldi 1 (173) 7     -3 +3          
47 Alex Alves da Paixão 0 (0) 7       -3          
47 Leonardo Flores Zambaldi 0 (0) 7                  
47 Victor Jatobá 0 (0) 7     -5 -4          
47 Felipe Menezes Machado 0 (0) 7                  
47 Ricardo Hahn 0 (0) 7                  
47 gustavo pacianotto gouveia 0 (0) 7                  
47 Renato Ferreira 0 (0) 7                 </div>

Vídeo: Discussão sobre os problemas

Algumas soluções dos competidores

Book stack (por Gabriel Luís Mello Dalalio)

#include <stdio.h>
#include <algorithm>
using namespace std;
#define LIM 1000100

int k;
int p[LIM], pc;
int f[LIM], ini, fim, dir, fc;

int main(){
	int a;
	scanf("%d",&k);
	pc=0;
	ini=1;
	fim=0;
	dir=1;
	fc=0;
	while( scanf("%d",&a)>0 && a!=0 ){
		//printf("%d %d\n",ini,fim);		
		if( a>0 ){
			fim=(fim+dir+LIM)%LIM;
			f[fim]=a;
			fc++;
			if( fc>k ){
				p[++pc]=f[ini];
				ini=(ini+dir+LIM)%LIM;
				fc--;
			}
		}
		else if( a==-1 ){
			printf("%d\n",f[fim]);
			fim=(fim-dir+LIM)%LIM;
			if( pc>0 ){
				ini=(ini-dir+LIM)%LIM;
				f[ini]=p[pc--];
			}
			else{
				fc--;
			}
		}
		else{
			swap(ini,fim);
			dir*=-1;
		}
	}
	return 0;
}

Eating a pizza (por Gabriel Luís Mello Dalalio)

#include <stdio.h>
#include <string.h>
#include <cmath>
using namespace std;
#define MAXN 110
#define MOD 1000000009

struct point{
	double x, y;
	point(){}
	point( double a, double b ){
		x=a;
		y=b;
	}
	point operator+( point p ){
		return point(x+p.x,y+p.y);
	}
	point operator*( double k ){
		return point(k*x,k*y);
	}
	point operator/( double k ){
		return point(x/k,y/k);
	}
};

point cm[MAXN][MAXN];
long long p[MAXN][MAXN], bin[MAXN][MAXN], resp;
int n;
double d, r, dist, ang;

void calc(){
	int i, j;
	memset(bin,0,sizeof(bin));
	bin[0][0]=1;
	for( i=1 ; i<=n ; i++ ){
		bin[i][0]=1;
		for( j=1 ; j<=n ; j++ ){
			bin[i][j]=(bin[i-1][j]+bin[i-1][j-1])%MOD;
		}
	}
}

int main(){
	int i, j, k;
	scanf("%d %lf %lf",&n,&r,&d);
	calc();
	dist=2.0*r*n*sin(4*atan(1)/n)/(3.0*4.0*atan(1));
	ang=4*atan(1)/n;
	//printf("--> %.2lf %.2lf\n",dist,ang);
	for( i=0; i<n ; i++ ){
		cm[i][i].x=cos(ang*(2*i+1))*dist;
		cm[i][i].y=d+sin(ang*(2*i+1))*dist;
		//printf("%.2lf %.2lf\n",cm[i][i].x,cm[i][i].y);
	} 
	for( k=1 ; k<n ; k++ ){
		for( i=0 ; i<n ; i++ ){
			cm[i][(i+k)%n]=(cm[i][(i+k-1)%n]*(double)k+cm[(i+k)%n][(i+k)%n])/((double)k+1);
		}
	}
	for( i=0 ; i<n ; i++ ){
		if( cm[i][i].y>=0 ){
			p[i][i]=1;
		}
		else{
			p[i][i]=0;
		}
		p[(i+1)%n][i]=1;
	}
	for( k=1 ; k<=n-2 ; k++ ){
		for( i=0 ; i<n ; i++ ){
			p[i][(i+k)%n]=0;			
			if( cm[i][(i+k)%n].y>0 ){	
				for( j=0 ; j<=k ; j++ ){
					p[i][(i+k)%n]+=(((p[i][(i+j-1+n)%n]*p[(i+j+1)%n][(i+k)%n])%MOD)*bin[k][j])%MOD;
					p[i][(i+k)%n]%=MOD;
				}
			}
			//printf("%d %d: %lld\n",i,(i+k)%n,p[i][(i+k)%n]);
		}
	}
	resp=0;
	for( i=0 ; i<n ; i++ ){
		resp+=p[i][(i+n-2)%n]%MOD;
		resp%=MOD;
	}
	printf("%lld\n",resp);
	return 0;
}

The smallest missing number (por Felipe Abella)

#include <iostream>
#include <cstdio>
#include <cstring>
#include <set>

using namespace std;

char str[100010];

int main()
{
  scanf(" %s", str);
  int n = strlen(str);
  set <int> bla;

  for (int i = 0; i < n; i++) {
    int val = 0;
    for (int j = i; j < min(n, i+7); j++) {
      val = 10*val + (str[j]-'0');
      bla.insert(val);
    }
  }

  int last = 0;
  set<int>::iterator it;
  for (it = bla.begin(); it != bla.end(); it++) {
    int v = *it;
    if (v > last+1) {
      printf("%d\n", last+1);
      return 0;
    }
    last = v;
  }
  it = bla.end();
  it--;
  printf("%d\n", (*it)+1);

  return 0;
}

Sleepless nights (por Felipe Abella)

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

int main()
{
  int a, b, c, d;

  scanf("%d:%d %d:%d", &a, &b, &c, &d);

  int e = c-a, f = d-b;

  if (f < 0) {
    f += 60;
    e--;
  }

  if (e < 0)
    e += 12;
  if (e == 0 && f == 0)
    e += 12;

  printf("Misof slept for");
  
  if (e)
    printf(" %d hour%s", e, (e > 1) ? "s" : "");
  if (e && f)
    printf(" and");
  if (f)
    printf(" %d minute%s", f, (f>1) ? "s" : "");

  printf(".\n");

  return 0;
}

Domino tiling (por Felipe Abella)

#include <iostream>
#include <cstdio>
#include <map>
#include <utility>
#include <cassert>
#include <cstring>
#include <stack>

#define INF 1000000000
#define MAXR 2048
#define MAXC 2048
#define MAXN (MAXR*MAXC/*+2*/)

using namespace std;

int nrow, ncol, missy, missx;
char result[MAXR][MAXC];

char getlet(int y, int x)
{
  return 'a' + ((y%5)*5 + (x%5));
}

int go(int y, int x)
{
  if (y == nrow) {
    y = 0;
    x ++;
  }
  if (x == ncol)
    return 1;
  if (result[y][x] != '*' || (y == missy && x == missx))
    return go(y+1, x);

  if (y+1 < nrow && result[y+1][x] == '*' && !(y+1 == missy && x == missx)) {
    result[y][x] = result[y+1][x] = getlet(y, x);
    if (go(y+1, x))
      return 1;
    result[y][x] = result[y+1][x] = '*';
  }
  if (x+1 < ncol && result[y][x+1] == '*' && !(y == missy && x+1 == missx)) {
    result[y][x] = result[y][x+1] = getlet(y, x);
    if (go(y+1, x))
      return 1;
    result[y][x] = result[y][x+1] = '*';
  }

  return 0;
}

struct state {
  int y, x, pos;
  state(int y, int x, int pos): y(y), x(x), pos(pos) {}
};

void run(int& ret, stack<state>& states)
{
  state st = states.top();
  states.pop();

  int y= st.y, x = st.x;

  if (y == nrow) {
    y = 0;
    x ++;
  }
  if (x == ncol) {
    ret = 1;
    return;
  }
  
  if (st.pos == 0)
    goto pos0;
  else if (st.pos == 1)
    goto pos1;
  else if (st.pos == 2)
    goto pos2;
  else if (st.pos == 3)
    goto pos3;

 pos0:
  if (result[y][x] != '*' || (y == missy && x == missx)) {
    states.push(state(y, x, 1));
    states.push(state(y+1, x, 0));
    return;
  pos1:
    //ret = ret;
    return;
  }
  
  if (y+1 < nrow && result[y+1][x] == '*' && !(y+1 == missy && x == missx)) {
    result[y][x] = result[y+1][x] = getlet(y, x);
    states.push(state(y, x, 2));
    states.push(state(y+1, x, 0));
    return;
  pos2:
    if (ret) {
      //ret = 1;
      return;
    }
    result[y][x] = result[y+1][x] = '*';
  }
  if (x+1 < ncol && result[y][x+1] == '*' && !(y == missy && x+1 == missx)) {
    result[y][x] = result[y][x+1] = getlet(y, x);
    states.push(state(y, x, 3));
    states.push(state(y+1, x, 0));
    return;
  pos3:
    if (ret) {
      //ret = 1;
      return;
    }
    result[y][x] = result[y][x+1] = '*';
  }

    ret = 0;

  return;
}

stack <state> states;
int go2(void)
{

  states.push(state(0, 0, 0));

  int ret = -1;
  while (!states.empty()) {
    run(ret, states);
  }
  
  return ret;
}

int main()
{
  scanf("%d %d %d %d", &nrow, &ncol, &missy, &missx);
  missy--, missx --;

  if ((missy+missx)%2 || (nrow*ncol-1)%2) {
    printf("impossible\n");
    return 0;
  }

  for (int y = 0; y < nrow; y++)
    for (int x = 0; x < ncol; x++)
      result[y][x] = '*';

  int x = go2();
  if (!x) {
    //abort();
    printf("impossible\n");
    return 0;
  }

  for (int y = 0; y < nrow; y++) {
    for (int x = 0; x < ncol; x++)
      printf("%c", result[y][x]);
    printf("\n");
  }

  return 0;
}

Find the purest sample (por Filipe Martins)

#pragma comment(linker, "/STACK:16777216")

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cfloat>
#include <climits>
#include <cctype>
#include <cmath>
#include <cassert>
#include <ctime>

#include <iostream>
#include <iomanip>
#include <algorithm>
#include <sstream>
#include <string>
#include <vector>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <complex>
#include <functional>
#include <numeric>

using namespace std;

template<class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cout << *i << " "; cout << endl; }

typedef long long ll;

#define eps 1e-10
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3fLL

#define fr(x,y,z) for(int(x)=(y);(x)<(z);(x)++)
#define cast(x,t) *({stringstream ss;static t __ret;ss<<x,ss>>__ret;&__ret;})

#define dbg(x) cout << #x << " == " << x << endl
#define print(x) cout << x << endl

// var
int n, m, k;
int dp[1<<20];
pair<int,int> op[1<<20];

int read() {
	if(scanf("%d %d %d",&n,&m,&k) != 3) return 0;
	for(int i = 0; i < m; i++) {
		scanf("%d %d",&op[i].first,&op[i].second);
	}
	return 1;
}

void process() {
	memset(dp,0,sizeof(dp));
	for(int i = 0; i < m; i++) {
		dp[ op[i].first ] = min(dp[ op[i].first ], dp[ op[i].second ]);
		dp[ op[i].second ]++;
	}
	
	//pv(dp+1,dp+n+1);
	
	int tot = 0;
	for(int i = 2; i <= n; i++) if(dp[i] <= k) {
		tot += k + 1 - dp[i];
	}
	
	printf("%d\n",tot);
}

int main() {
	// solve
	int t = 1 << 30; //cin >> t;
	while(t-- && read()) {
		process();
		//break;
	}	
	return 0;
}

On the farm (por Gabriel Luís Mello Dalalio)

#include <stdio.h>
#include <algorithm>
using namespace std;

long long h, l , w;
long long ini, fim, i;

int main(){
	int imp;
	scanf("%lld %lld %lld",&h,&l,&w);
	if( (l+w)%4!=0 ){
		printf("impossible\n");
	}
	else{
		ini=max((long long)0,((l+w)/4)-h);
		fim=min(w,(l-w)/2);
		if( fim>ini+100 ){
			fim=ini+100;
		}
		imp=1;
		for( i=ini ; i<=fim && imp==1 ; i++ ){
			if( ((w-i)%2)==0 && ((l-w-2*i)%4)==0 ){
				imp=0;
				printf("%lld %lld %lld %lld\n",i,(i+h-(l+w)/4),(w-i)/2,(l-w-2*i)/4);
			}
		}
		if( imp ){
			printf("impossible\n");
		}
	}
	return 0;
}

Vacuum cleaning (por Eduardo Ribas)

#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>
#include <map>
#include <set>
#include <string>
#include <iostream>
#include <queue>
#include <vector>
#include <cmath>
using namespace std;

int N,M;


char nomesala[16][32];
int sala[16];
int adjacentes[16];

int arestaa[32];
int arestab[32];
int peso[32];

#define two(n) (1<<(n))
double PD[8][two(18)];
int cmp(double a, double b) {
	if(fabs(a-b)<1e-8)
		return 0;
	if(a<b)
		return -1;
	return 1;
}

void sistlinear(int nest,double sist[10][10]) {
	for(int i=0;i<nest-1;i++) {
		//pega a linha com maior valor da coluna i
		if(cmp(sist[i][i],0.0)==0) {
			int q=i;
			for(int j=i+1;j<nest;j++)
				if(sist[j][i] > sist[q][i])
					q=j;
			memcpy(sist[9],sist[i],sizeof(sist[0]));
			memcpy(sist[i],sist[q],sizeof(sist[0]));
			memcpy(sist[q],sist[9],sizeof(sist[0]));
		}

		for(int j=i+1;j<nest;j++) {
			double v=-sist[j][i]/sist[i][i];
			for(int k=i;k<=nest;k++)
				sist[j][k]+=sist[i][k]*v;
		}
	}
	for(int i=nest-1;i>=0;i--) {
		double soma=0;
		for(int j=i+1;j<nest;j++)
			soma+=sist[i][j]*sist[j][nest];
		sist[i][nest]=(sist[i][nest]-soma)/sist[i][i];
	}
}

double calc(int p, int b) {
	double& ans=PD[p][b];
	if(ans!=-1)
		return ans;

	ans=0.0;
	//chegou ao fim
	if(b==two(M)-1) {
		if(adjacentes[p]==1)
			return ans=0.0;
		return ans=-sala[p];
	}

	//pega todas as cidades que foram atingidas
	int bc=two(p);
	for(int i=0;i<M;i++) if(b&two(i))
		bc|=two(arestaa[i])|two(arestab[i]);

	//mapeia estado para variavel do sistema linear
	int nest=0;

	double sist[10][10];
	memset(sist,0,sizeof(sist));

	int qualsist[10];
	for(int i=0;i<N;i++) if(two(i)&bc)
		qualsist[i]=nest++;
	if(nest>=9)
		printf("%d\n",nest);

	for(int i=0;i<nest;i++)
		sist[i][i]=1.0;

	//monta sistema linear
	for(int j=0;j<M;j++) {
		int i=-1;
		int c,b2;
		//aresta a ta dentro
		if(two(arestaa[j]) & bc) {
			i=arestaa[j];
			c=arestab[j];
			b2=b|two(j);

			if(b2!=b) {
				sist[qualsist[i]][nest]+=(1.0/(double)adjacentes[i])  * (calc(c,b2) + peso[j] + sala[c] );
			}
			else {
				sist[qualsist[i]] [ qualsist[c] ] += -(1.0/(double)adjacentes[i]);
				sist[qualsist[i]] [ nest ] += (1.0/(double)adjacentes[i])*(peso[j] + sala[c]);
			}
		}
		if(two(arestab[j]) & bc) {
			i=arestab[j];
			b2=b|two(j);
			c=arestaa[j];
			if(b2!=b) {
				sist[qualsist[i]][nest]+=(1.0/(double)adjacentes[i])  * (calc(c,b2) + peso[j] + sala[c] );
			}
			else {
				sist[qualsist[i]] [ qualsist[c] ] += -(1.0/(double)adjacentes[i]);
				sist[qualsist[i]] [ nest ] += (1.0/(double)adjacentes[i])*(peso[j] + sala[c]);
			}
		}

	}
	sistlinear(nest,sist);
	for(int i=0;i<N;i++) if(two(i) & bc) {
		PD[i][b]=sist[qualsist[i]] [nest];
	}

	return ans=sist[qualsist[p]][nest];
}


int main(void) {
	scanf("%d %d",&N, &M);
	for(int i=0;i<N;i++) {
		scanf("%s %d",nomesala[i],sala+i);
	}
	memset(adjacentes,0,sizeof(adjacentes));
	for(int i=0;i<M;i++) {
		char aux[2][32];
		int q[2];
		scanf("%s %s %d",aux[0],aux[1],peso+i);
		for(int j=0;j<2;j++)
			for(int k=0;k<N;k++)
				if(strcmp(aux[j],nomesala[k])==0)
					q[j]=k;
		arestaa[i]=q[0];
		arestab[i]=q[1];
		adjacentes[q[0]]++;
		adjacentes[q[1]]++;
	}
	for(int i=0;i<N;i++)
		for(int j=0;j<two(M);j++)
			PD[i][j]=-1.0;
	double ans=1e100;
	vector<string> vans;
	for(int i=0;i<N;i++) {
		double v=sala[i]+calc(i,0);
		if(cmp(v,ans)==0) {
			vans.push_back(nomesala[i]);
		}
		else if(v<ans) {
			vans.clear();
			ans=v;
			vans.push_back(nomesala[i]);
		}
	}
	sort(vans.begin(),vans.end());
	for(int i=0;i<(int)vans.size();i++) {
		if(i) printf(" ");
		cout << vans[i];
	}
	printf("\n%.8lf\n",ans);
	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.