コード掃き溜め

明日は忙しいですよ。

なんてったってクリスマス・イブですからね(｀・ω・´)

+11:00~12:30 TopCoderSRM526.5
+14:00~19:00 Xmas Contest 2011
+21:00~23:00 Codeforces Beta Round #99 (Div.2)

AOJ 0556

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
void outp(int s) {
	if (s%3==1) printf("1\n");
	else if (s%3==2) printf("2\n");
	else printf("3\n");
}
int main() {
	int n, k;
	scanf("%d%d",&n,&k);
	for (int i=0; i<k; i++) {
		int a, b; scanf("%d%d",&a,&b);
		int x1=b, x2=abs(n-b)+1, y1=a, y2=abs(n-a)+1;
		if (x1>x2) swap(x1,x2);
		if (y1>y2) swap(y1,y2);
		if (x1<=a&&a<=x2) outp(x1);
		else if (y1<=b&&b<=y2) outp(y1);
	}
}

VKPC A

#include <cstdio>
int main() {
	int a, b, m;
	scanf("%d%d%d",&a,&b,&m);
	int div = b / a;
	int res = 0;
	while (div%m==0) {
		div /= m;
		res++;
	}
	printf("%d\n",res);
}

VKPC B

#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
#include <set>
using namespace std;
int main() {
	set<string> need;
	int m, n;
	scanf("%d",&m);
	for (int i=0; i<m; i++) {
		string temp; cin >> temp;
		need.insert(temp);
	}
	scanf("%d",&n);
	int much=0;
	for (int i=0; i<n; i++) {
		string key, info; cin >> key >> info;
		string sub = key.substr(0,key.length()-1);
		if (need.find(sub)!=need.end()) much++;
	}
	if (much==need.size()) printf("yes\n");
	else printf("no\n");
}

VKPC C

#include <cstdio>
#include <climits>
#include <algorithm>
using namespace std;
int dfs(int i, int m, int n, int sum, int cnt, int umb[]) {
	if (sum==n) return cnt;
	if (i==m) return INT_MAX;
	return min(dfs(i+1,m,n,sum+umb[i],cnt+1,umb),dfs(i+1,m,n,sum,cnt,umb));
}
int main() {
	int m, n;
	scanf("%d%d",&m,&n);
	int umb[m];
	for (int i=0; i<m; i++) scanf("%d",&umb[i]);
	sort(umb, umb+m);
	int res = dfs(0,m,n,0,0,umb);
	if (res==INT_MAX) printf("NA\n");
	else printf("%d\n", res);
}

AOJ 0538

#include <iostream>
using namespace std;
typedef long long ll;
ll comb(int a, int b) {
	if (a<b) return 0;
	return a-b+1;
}
int main() {
	int n, m;
	string str;
	while (cin>>n&&n!=0) {
		cin>>m>>str;
		ll res=0;
		int cnt=0;
		for (int i=0; i<m-1; i++) {
			if (str[i]=='I') {
				if (str[i+1]=='O'&&str[i+2]=='I') cnt++;
				else {
					res += comb(cnt,n);
					cnt=0;
				}
			}
		}
		if (str[m-3]=='I'&&str[m-2]&&'O'&&str[m-1]=='I') {
			res += comb(cnt,n);
		} else if (str[m-3]=='O') {
			res += comb(cnt,n);
		}
		cout << res << endl;
	}
}

AOJ 0546

#include <iostream>
#include <cstdio>
#include <set>
#include <vector>
using namespace std;
int main() {
	int n, k;
	while (scanf("%d%d",&n,&k)) {
		if (n==0&&k==0) break;
		vector<string> str(n);
		for (int i=0; i<n; i++) cin>>str[i];
		set<string> res;
		if (k==2) {
			for (int i=0; i<n; i++)
				for (int j=0; j<n; j++)
					if (i!=j) res.insert(str[i]+str[j]);
		}
		if (k==3) {
			for (int i=0; i<n; i++)
				for (int j=0; j<n; j++)
					for (int k=0; k<n; k++)
						if (i!=j&&i!=k&&j!=k) res.insert(str[i]+str[j]+str[k]);
		}
		if (k==4) {
			for (int i=0; i<n; i++)
				for (int j=0; j<n; j++)
					for (int k=0; k<n; k++)
						for (int l=0; l<n; l++)
							if (i!=j&&i!=k&&i!=l&&
								j!=k&&j!=l&&k!=l) res.insert(str[i]+str[j]+str[k]+str[l]);
		}
		printf("%d\n",res.size());
	}
}

PKU 3174

#include <cstdio>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;
struct cood {
	int x, y;
};
int main() {
	int n; scanf("%d",&n);
	cood cows[n];
	for (int i=0; i<n; i++) scanf("%d%d",&cows[i].x,&cows[i].y);
	vector<pair<int,pair<int, int> > > res;
	for (int i=0; i<n; i++) for (int j=i+1; j<n; j++) for (int k=j+1; k<n; k++) {
		double px=cows[k].x-cows[i].x, qx=cows[j].x-cows[i].x;
		double py=cows[k].y-cows[i].y, qy=cows[j].y-cows[i].y;
		if (px*qy==qx*py) {
				res.push_back(make_pair(i+1,make_pair(j+1,k+1)));
		}
	}
	sort(res.begin(), res.end());
	printf("%d\n",res.size());
	for (int i=0; i<res.size(); i++) {
		printf("%d %d %d\n",res[i].first,res[i].second.first,res[i].second.second);
	}
}

PKU 3193

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct Trie {
	int value;
	Trie *next[0x100];
	Trie() { fill(next, next+0x100, (Trie*)0); }
};
void insert(char *t, Trie *r) {
	for (int i = 0; t[i]; ++i) {
		char c = t[i];
		if (!r->next[c]) r->next[c] = new Trie;
		r = r->next[c];
	}
}
bool find(char *t, Trie *r) {
	for (int i=0; i<strlen(t)-1; ++i) {
		char c = t[i];
		if (!r->next[c]) {
			return false;
		}
		r = r->next[c];
	}
	return true;
}
int main() {
	int m, n; scanf("%d%d\n",&m,&n);
	Trie tr;
	for (int i=0; i<m; i++) {
		char in[100];
		fgets(in,100,stdin);
		in[strlen(in)-1]=0;
		insert(in,&tr);
	}
	int res=0;
	for (int i=0; i<n; i++) {
		char in[100];
		fgets(in,100,stdin);
		in[strlen(in)]=0;
		if (find(in,&tr)) res++;
	}
	printf("%d\n",res);
}