KUPC2014

オンラインで参加した。
占いが解けなくてつらい。

A:マッサージチェア
6通りしかないしコピペで全通り書いた

#include <cstdio>
#include <algorithm>
using namespace std;

int a[3];
int b[3];

int d(int x, int y, int z){
	int p = abs(x-a[0]);
	int q = abs(y-a[1]);
	int r = abs(z-a[2]);
	return p + q + r;
}
int main(){
	for(int i=0;i<3;i++)
		scanf("%d", a+i);
	for(int i=0;i<3;i++)
		scanf("%d", b+i);
	int D = 10000000;
	D = min(D, d(b[0],b[1],b[2]));
	D = min(D, d(b[0],b[2],b[1]));
	D = min(D, d(b[1],b[0],b[2]));
	D = min(D, d(b[1],b[2],b[0]));
	D = min(D, d(b[2],b[0],b[1]));
	D = min(D, d(b[2],b[1],b[0]));
	printf("%d\n", D);
}

B:数当てゲーム
Submitデバッグしたら、かなりWAしてしまった。エラトステネスの篩っぽくする。

#include <cstdio>
#include <algorithm>
using namespace std;

bool AI(int x){
	char J[2];
	printf("? %d\n",x);
	fflush(stdout);
	scanf("%s", J);
	if(J[0] == 'Y') return true;
	return false;
}
bool n[1002];
int main(){
	fill(n+1,n+1002,true);
	n[1] = true;
	int z = 2;
	for(int q = 0; q < 200; q++){
		if(!AI(z)){
			for(int j=z; j<1001; j+=z){
				n[j] = false;
			}
		}else{
			for(int i = 1; i < 1001; i++){
				if(i % z != 0){
					n[i] = false;
				}
			} 
			z++;
		}
		for(; ; z++){
			if(n[z]) break;
		}
		if(z > 1000) break;
	}
	for(int i = 1000; i>=1; i--){
		if(n[i]){
			printf("! %d\n", i);
			return 0;
		}
	}
}

C:占い
TLE（絶望）

D:ハミング
二つのバイナリ文字列が一致している箇所の個数A、一致していない箇所の個数Bとして、
d1 = a + b
d2 = a + (B - b)
ただし0<=a<=A, 0<=b<=B
を満たすa,bを求めて、(A C a) * (B C b)の和
繰り返し二乗法を使う必要があるかはよく分からなかったけど、ライブラリがあったので貼り付けた。

#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MOD = 1000000007;
char s[2][100010];
int d[2];
int A, B;
ll mod_pow(ll a, ll n){
	ll ret = 1;
	ll t = a;
	while(n){
		if(n&1)
			ret = ret * t % MOD;
		t = t * t % MOD;
		n >>= 1;
	}
	return ret;
}
//nCk mod p
ll mod_comb(ll N, ll K){
	ll nPk = 1 , kfact = 1;
	ll n = N;
	for(ll i = N; i > N - K; i--)
		nPk = nPk * (i % MOD) % MOD;

	kfact = 1;
	for(ll i = 2; i <= K; i++)
		kfact = kfact * i % MOD;

	kfact = mod_pow(kfact, MOD - 2);
	return ((nPk * kfact) % MOD);
}
int main(){
	for(int i=0;i<2;i++){
		char c;
		scanf("%s",&s[i][0]);
		scanf("%d", &d[i]);
		scanf("%c", &c);
	}
	for(int k = 0; s[0][k] != 0; k++){
		if(s[0][k] == s[1][k]){
			A++;
		}else{
			B++;
		}
	}
	ll ans = 0;
	for(int b=0;b<=B;b++){
		int a = (d[0] - b);
		if(0<=a&&a<=A && d[1] == a+(B-b)){
			ans += (mod_comb(A,a) * mod_comb(B,b)) % MOD;
		}	
	}
	printf("%lld\n", ans);
	return 0;
}

E:何しちゃおっかな
何でこのネーミングなんだろう。
自明に敷き詰められないものを除いて、面積が8で割りきれればよい。

#include <cstdio>
#include <algorithm>
using namespace std;

char p[] = "Possible\n";
char im[] = "Impossible\n";
int main(){
	int N, M, C;
	scanf("%d", &C);
	for(int i = 0; i < C; i++){
		scanf("%d %d", &N, &M);
		if(N==2 && M==4 || N==4&&M==2){
			printf("%s",im);
		}else if(N%4==0&&M%4==0){
			printf("%s",p);
		}else{
			if(N==1 || M==1){
				printf("%s",im);
			}else{
				if((N*M)%8==0)
					printf("%s", p);
				else
					printf("%s", im);
			}
		}
	}
}

J:カード
考える気力がなくなったので部分点だけ取った

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

int N, M, P;
int x[100000];
int s[100001];
int main(){
	scanf("%d %d %d", &N, &M, &P);
	for(int i = 0; i < M; i++){
		scanf("%d", x+i);
		s[i+1] = s[i] + x[i];
	}
	int n = 0, w = 0, d = 0;
	for(;;d++){
		w += P;
		int k = distance(s,upper_bound(s,s+M+1,w));
		k--;
		n+=k;
		w-=s[k];
		if(n >= N) break;
	}
	printf("%d\n", d+1);
}

KUPC楽しかったです