ICPC Japan Domestic 2008

ICPC2008年の問題．3時間で5問しか解けなかった…orz．

AOJ 1153-Equal Total Scores

問題概要

(省略)

解法

全てのカードの交換を試してみる．

実装(C++)

#include <vector>
#include <iostream>
using namespace std;

#define REP(i,x) for(int i=0;i<(int)(x);i++)

int main(){
	int n,m;
	for(;cin>>n>>m;){
		if(n==0&&m==0)break;
		vector<int> taro(n);
		int s_t=0;
		REP(i,n){
			cin>>taro[i];
			s_t+=taro[i];
		}
		vector<int> hanako(m);
		int s_h=0;
		REP(i,m){
			cin>>hanako[i];
			s_h+=hanako[i];
		}
		int sum=0x10000000;
		int ri=-2,rj=-2;
		REP(i,n)REP(j,m){
			if(s_t-taro[i]+hanako[j]==s_h-hanako[j]+taro[i]){
				if(sum>taro[i]+hanako[j]){
					ri=i;rj=j;
					sum=taro[i]+hanako[j];
				}
			}
		}
		if(ri==-2){
			cout<<-1<<endl;continue;
		}
		cout<<taro[ri]<<" "<<hanako[rj]<<endl;
	}
	return 0;
}

AOJ 1154-Monday-Saturday Prime Factors

問題概要

(省略)

解法

素数を全て求める．
単純にSqrt(N)までの数で試し割りする方法でも十分間に合う．

実装(C++)

#include <vector>
#include <iostream>
#include <set>
using namespace std;

#define REP(i,x) for(int i=0;i<(int)(x);i++)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();i++)

int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};
int check(int x){
	bool ok=true;
	for(int i=2;i*i<=x;i++){
		if((i%7)!=1&&(i%7)!=6)continue;
		if(x%i==0){
			ok=false;
			break;
		}
	}
	return ok;
}
int main(){
	vector<int> prime;
	for(int i=2;i<=300000;i++){
		if((i%7)!=1&&(i%7)!=6)continue;
		if(check(i)){
			prime.push_back(i);
		}
	}
	int n;
	for(;cin>>n;){
		if(n==1)break;
		set<int> res;
		cout<<n<<":";
		REP(i,prime.size()){
			if(prime[i]>n)break;
			if(n%prime[i]==0){
				//n/=prime[i];
				res.insert(prime[i]);
			}
		}

		FOR(it,res){
			cout<<" "<<(*it);
		}
		cout<<endl;
	}
	return 0;
}

AOJ-