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

A: bookstack - Book stack
B: eatpizza - Eating a pizza
C: missing - The smallest missing number
D: sleepless - Sleepless nights
E: dominoes - Domino tiling
F: findmax - Find the purest sample
G: onthefarm - On the farm
H: vacuum - Vacuum cleaning

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