夢追い人

"It takes a dreamer to make a dream come true."―Vincent Willem van Gogh

1003~1005

とりあえずCodeChef中だけど、またTLEに引っかかってる上明日UAPCなのでUAPCの過去問を。

1003を通せない…一応助言求める感じで…

1003

携帯の数字入力での入力が与えられるから、それを英字入力に変換しよう。という問題。
サンプル通ってるからもしかしたら問題文の条件見逃してるかもしれないけどとりあえず次のコードでWA

/*sample->AC system test->WA*/

#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <string>
#include <algorithm>
using namespace std;

const string p[9] = {"\',.!?","abcABC","defDEF","ghiGHI","jklJKL","mnoMNO","pqrsPQRS","tuvTUV","wxyzWXYZ"};

int parse(char t) {
	switch(t) {
		case '1':
			return 1;
		case '2':
			return 2;
		case '3':
			return 3;
		case '4':
			return 4;
		case '5':
			return 5;
		case '6':
			return 6;
		case '7':
			return 7;
		case '8':
			return 8;
		case '9':
			return 9;
	}
}

int ad(int c, int n) {
	int t = c%p[n-1].length()-1;
	if (t==-1) t=p[n-1].length()-1;
}

int main() {
	string in;
	while (cin >> in) {
		int c=0, n=0;
		string res="";
		for (int i=0; i<in.length();i++) {
			if (in[i]=='0'&&n!=0) {
				res += p[n-1][ad(c,n)];
				c=0;
				n=0;
			} else if (in[i]=='0'&&n==0) {
				res += " ";
			} else if (c==0) {
				n = parse(in[i]);
				c++;
			} else if (parse(in[i])!=n) {
				res += p[n-1][ad(c,n)];
				c=1;
				n=parse(in[i]);
			} else {
				c++;
			}
		}
		res += p[n-1][ad(c,n)];
		cout << res << endl;
	}
}

1004

上限Nの中で

1  2  ... N
N N-1 ... 1

と並べた縦の二数が両方共素数になるペア数を数える問題。
サンプルの入力N=1の出力をずっと"1"だと見間違えててずっと問題文の理解に苦しんでたw

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
typedef vector<bool> vb;

vb makeTable() {
	vb p(10001, true);
	p[1]=false;
	for(int i=4;i<=10000;i+=2)p[i]=false;
	for(int i=3;i<=10000;i+=2){
		if(p[i]){
			for(int j=i*2;j<=10000;j+=i)p[j]=false;
		}
	}
	return p;
}

int main() {
	vb table = makeTable();
	int N;
	while (cin >> N) {
		int cnt=0;
		for(int i=1;i<=N;i++){
			if(table[i]&&table[N-i+1]) cnt++;
		}
		cout << cnt << endl;
	}
}

1005

n*n人のクラスの座席で横並びの中で一番背の低い時に手を上げ、縦並びの中で一番背が高いときに手を上げたとき、どちらとも手を挙げる生徒の身長は?というもの。
身長は整数で与えられ、n<=100より全探索でおk(というより全探索でO(n*n)だからほとんど問題ない…)。答えが必ず一つになることにも注意。

#include <cstdio>
#include <cmath>
#include <vector>
using namespace std;
typedef vector<int> vi;

int main() {
	int n;
	while (scanf("%d", &n)&&n!=0) {
		vi stu(n*n);
		for (int i=0; i<n*n; i++) scanf("%d", &stu[i]);
		vi row(n,1000000), col(n,0);
		for (int i=0; i<n; i++) {
			for (int j=i*n; j<(i+1)*n; j++) row[i] = min(row[i], stu[j]);
		}
		for (int i=0; i<n; i++) {
			for (int j=i; j<n*n; j+=n) col[i] = max(col[i], stu[j]); 
		}
		int res = 0;
		for (int i=0; i<n; i++) {
			for (int j=0; j<n; j++) {
				if (row[i]==col[j]) res = row[i];
			}
		}
		printf("%d\n",res);
	}
}

実はコレの正答率が30%ぐらいになっているんだけど、全探索で求められる問題がなぜこうなった…と思ったり。

英語に飽きたのであとは他のAOJ解いていようと思いやす。