solution

100519H.cpp

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int n,m,k;
vector<int> outgo[1010];
bool visit[1010];
void search(int now,int dis)
{
	visit[now]=true;
	for(int i=0;i<outgo[now].size();i++)
	{
		int to=outgo[now][i];
		if(visit[to])
			continue;
		if(dis)
			search(to,dis-1);
	}
}
int cnt=0;
void search1(int now)
{
	visit[now]=true;
	cnt++;
	for(int i=0;i<outgo[now].size();i++)
	{
		int to=outgo[now][i];
		if(!visit[to])
			search1(to);
	}
}
int calc(int dis)
{
	int ret=(1<<30);
	int p=dis*2+1;
	for(int i=1;i<=n;i++)
	{
		memset(visit,0,sizeof(visit));
		search(i,dis);
		int ans=1;
		for(int j=1;j<=n;j++)
			if(!visit[j])
			{
				cnt=0;
				search1(j);
				ans+=(cnt+p-1)/p;
			}
		ret=min(ret,ans);
	}
	return ret;
}
int main()
{
	scanf("%d %d %d",&n,&m,&k);
	for(int i=1;i<=m;i++)
	{
		int u,v;
		scanf("%d %d",&u,&v);
		outgo[u].push_back(v);
		outgo[v].push_back(u);
	}
	int l=0,r=n;
	int ans=-1;
	while(l<=r)
	{
		int mid=(l+r)>>1;
		if(calc(mid)<=k)
		{
			r=mid-1;
			ans=mid;
		}
		else
			l=mid+1;
	}
	printf("%d\n",ans);
	return 0;
}

100519I.py

import sys
def ask(x):
	print x
	sys.stdout.flush()
	ans = raw_input()
	if ans == "OK": sys.exit(0)
	return ans

N = input()
x = sum(2**(-i) * (ask(2) == "<") for i in xrange(1,42))
ask(min((abs(x - round(x * P) / P), P) for P in xrange(2,N+1))[1])

100792L.cpp

#include<bits/stdc++.h>
#include<map>
using namespace std;
int n,m,k,l;
map<pair<int,vector<int> >,int> mp;
vector<pair<int,int> >g[1000005];
queue<pair<int,vector<int> > >q;
int bfs()
{
	q.push(make_pair(0,vector<int>(l,0)));
	mp[q.front()]=0;
	pair<int,vector<int> >u,v;
	int cnt;
	while(!q.empty())
	{
		u=q.front();q.pop();
		v=u;cnt=mp[u];
		if(l)for(int i=l-1;i;i--)v.second[i]=v.second[i-1];
		for(int i=0;i<g[u.first].size();i++)
		{
			if(g[u.first][i].second==n)return cnt;
			v.first=g[u.first][i].first;
			if(l)
			{
				v.second[0]=g[u.first][i].second;
				int f=0;
				for(int i=0;i<l;i++)if(v.second[0]==u.second[i]){f=1;break;}
				if(f)continue;
			}
			if(mp.find(v)==mp.end())
			{
				mp[v]=cnt+1;
				q.push(v);
			}
		}
	}
	return -1;
}
int main()
{
	scanf("%d%d%d",&n,&m,&k);
	l=(k*25-1)/1000;
	for(int i=1;i<=m;i++)
	{
		int u,v,t;
		scanf("%d%d%d",&u,&v,&t);
		if(u==1)g[0].push_back(make_pair(i,1));
		for(int j=0;j<t;j++)
		{
			int x;
			scanf("%d",&x);
			g[i].push_back(make_pair(x,v));
		}
	}
	long long ans=bfs();
	if(ans==-1)puts("No chance");else cout<<ans*1000+k*25;
	return 0;
}