情報オリンピック第5回模擬試験1, 2

模擬試験の問題はJOIにはありません。ので、手元で一応確認したものの間違ってる可能性も。
オーダーとか何それって感じ。

情報オリンピック第5回模擬試験1

JOI 2006 模擬試験１問題・データ

1. Triangle Types

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
	int x = 0, y = 0, z = 0;
	vector<int> t(3);
	while(~scanf("%d %d %d\n", &t[0], &t[1], &t[2])){
		sort(t.begin(), t.end());
		if((t[1] + t[0]) > t[2]){
			if(t[2] * t[2] < t[0] * t[0] + t[1] * t[1]){
				x++;
			}else if((t[2] * t[2]) == (t[0] * t[0] + t[1] * t[1])){
				y++;
			}else if(t[2] * t[2] > t[0] * t[0] + t[1] * t[1]){
				z++;
			}
		}else{
			break;
		}
	}
	printf("%d %d %d %d\n", x + y + z, y, x, z);
	return 0;
}

簡単なのだが、三角形以外が出てきた所でやめろ、などがいやらしい問題。

2. Common Divisors

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
	int n;
	scanf("%d\n", &n);
	vector<int> v(n);
	for(int i = 0; i < n; i++)
		scanf("%d", &v[i]);
	sort(v.begin(), v.end());
	for(int i = 1; i <= v[0]; i++){
		bool f = 1;
		for(int j = 0; j < v.size(); j++){
			if(v[j] % i) f = 0;
		}
		if(f) printf("%d\n", i);
	}
	return 0;
}

3. Two Number Cards

順列を数として見て小さい順に並べる、の意味が分からない。
考えつく範囲の全ての解釈を試したけれどもダメだった。
おそらくどれかが正解でかつどれかにバグがあったんだと思う。

4. Nearest Two Points

ベタに解くとこうなるのだが、これはオーダー破滅である。
なんか解説には工夫すれば計算機幾何学の知識がなくても解けるよとかいうナメた事が書いてあるが、僕の脳味噌ではそんな物思いつきませんでした。本当にありがとうございました。

#include <cstdio>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
inline int po(int x){
	return x * x;
}
int main()
{
	int n;
	scanf("%d\n", &n);
	vector<pair<int, int> > v;
	for(int i = 0; i < n; i++){
		int x, y;
		scanf("%d %d\n", &x, &y);
		v.push_back(make_pair(x, y));
	}
	int minimum = INT_MAX;
	for(int i = 0; i < n; i++){
		for(int j = i + 1; j < n; j++){
			const pair<int, int> a =  v[i], b = v[j];
			const int c = po(a.first - b.first) + po(a.second - b.second);
			minimum = min(minimum, c);
		}
	}
	printf("%d\n", minimum);
	return 0;
}

5. Palindrome

そもそも自分の解法だとオーダー破滅な事は分かっていたけれども、なんかそれよりも、テストケース3で誤答を出す。当然のように5では終わらない。ぬ？

#include <cstdio>
#include <vector>
using namespace std;
class prime {
private:
	vector<bool> tbl;
public:
	inline bool is_prime(long long x){
		return tbl[x];
	}

	void maketable(long long x){
		tbl = vector<bool>(x + 1, true);
		tbl[0] = tbl[1] = false;
		for(long long i = 2; i <= x; i++){
			if(tbl[i] == false) continue;
			for(long long j = i + i; j <= x; j += i){
				tbl[j] = false;
			}
		}
		return;
	}
};
inline long long p(int x, int n){
	long long y = x;
	if(!n) return 1;
	while(--n) y *= x;
	return y;
}

inline long long makeparlin(long long x){
	long long y = 0;
	do {
		y *= 10;
		y += x % 10;
	} while(x /= 10);
	return y;
}

int main()
{
	int n, c;
	scanf("%d %d\n", &n, &c);
	prime pr;
	int m = 2 * n + (c < 0 ? 0 : 1);
	pr.maketable(p(10, m));
	long long dst = (p(10, n) - 1) * p(10, (c < 0 ? n : n + 1)) +
		(c < 0 ? 0 : c)  * p(10, n) + (p(10, n) - 1);
	for(long long i = p(10, n) - 1; 0 <= i; i--){
		long long cur = i * p(10, (c < 0 ? n : n + 1)) +
			(c < 0 ? 0 : c)  * p(10, n) + makeparlin(i);
		if(pr.is_prime(cur)){
			dst = cur;
			break;
		}
	}
	printf("%lld\n", dst);
	
	return 0;
}

情報オリンピック第5回模擬試験2

JOI 2006 模擬試験２問題・データ

1. Tunnel

他はあってるのにテストケース2限定で誤答する。ん？

#include <cstdio>
#include <vector>
using namespace std;
int main()
{
	int n, m;
	scanf("%d\n%d\n", &n, &m);
	vector<int> in(n + 1), out(n + 1);
	for(int i = 1; i <= n; i++)
		scanf("%d %d\n", &in[i], &out[i]);
	int cur = m;
	int maximum = 0;
	for(int i = 1; i <= n; i++){
		cur += in[i];
		cur -= out[i];
		maximum = max(maximum, cur);
	}
	printf("%d\n", maximum);
	return 0;
}

2. Simple Calculator

#include <iostream>
#include <sstream>
using namespace std;
inline int calc(int l, char c, int r){
	switch(c){
	case '+': return l + r;
	case '-': return l - r;
	case '*': return l * r;
	case '/': return l / r;
	}
}
int main()
{
	string s;
	int l = 0, r = 0;
	char c = 0;
	while(cin>>s){
		switch(s[0]){
		case '+':
		case '-':
		case '*':
		case '/':
			c = s[0];
			break;
		case '=':
			cout<<l<<endl;
		default:
			stringstream ss(s);
			if(!c){
				ss>>l;
			}else{
				ss>>r;
				l = calc(l, c, r);
				c = 0;
			}
			break;
		}

	}
	return 0;
}

3. Production

#include <cstdio>
#include <map>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
class strange_greater {
public:
	bool operator () (const pair<string, int>& p, const pair<string, int>& q) const {
		const string s = p.first, t = q.first;
		if(s.size() < t.size()){
			return true;
		}else if(s.size() > t.size()){
			return false;
		}else{
			return s < t;
		}
	}
};

int main()
{
	int n;
	scanf("%d\n", &n);
	map<string, int> m;
	for(int i = 0; i < n; i++){
		char c[6];
		int l;
		scanf("%s %d\n", c, &l);
		string s(c);
		m[s] += l;
	}
	vector<pair<string, int> > v;
	strange_greater sg;
	for(map<string, int>::iterator it = m.begin(); it != m.end(); it++)
		v.push_back(make_pair((*it).first, (*it).second));
	sort(v.begin(), v.end(), sg);
	for(int i = 0; i < v.size(); i++)
		printf("%s %d\n", v[i].first.c_str(), v[i].second);
	return 0;
}

ライブラリ問題かと思ったら、

順序：文字の長さの小さい順に，同じ長さのときは，前から比べて最初に異なる文字のアルファベット順とする．

ここだけが異常にいやらしい問題。

4. Available areas

解説見たけどよく分からなかった。この解法だとオーダーで死にます。

#include <cstdio>

int main()
{
	int N;
	scanf("%d\n", &N);
	int cnt = 0;
	for(int i = 0; i < N; i++){
		int n;
		scanf("%d\n", &n);
		bool f = false;
		for(int y = 1; y < n; y++){
			int x = (n - y) / (2 * y + 1);
			if((2 * x * y + x + y) == n){
				f = true;
				break;
			}
		}
		if(!f){
			cnt++;
		}
	}
	printf("%d\n", cnt);
	return 0;
}

5. Beads

解いていないが解き方が分かりそうという事もない。

情報オリンピック 第5回模擬試験1