存档

‘算法’ 分类的存档

ZJU OJ 2001

2012年8月26日 没有评论
#include <iostream>
#include <string>
#include <algorithm>
#include <sstream>
using namespace std;
 
int str_to_int(string num_str){
	int result = 0, base = 1;
	for (int i=num_str.size()-1;i>=0;--i){
		result += (num_str[i] - '0')*base;
		base *= 10;
	}
	return result;
}
 
int main(int argc, char *argv[]){
	int n;
	cin >> n;
	for (int i=0;i<n;++i){
		string sa,sb;
		cin >> sa >> sb;
		reverse(sa.begin(), sa.end());
		reverse(sb.begin(), sb.end());
		int tmp = str_to_int(sa) + str_to_int(sb);
		ostringstream o;
		if (o << tmp){
			string s = o.str();
			reverse(s.begin(), s.end());
			cout << str_to_int(s) << endl;
		}
	}
	return 0;
}
分类: OJ, 算法 标签: , , , ,

ZJU OJ 2932

2012年8月26日 没有评论
#include <iostream>
#include <map>
#include <string>
using namespace std;
 
int main(){
	map<char, string> m;
	m.insert(make_pair(' ',"%20"));
	m.insert(make_pair('!',"%21"));
	m.insert(make_pair('$',"%24"));
	m.insert(make_pair('%',"%25"));
	m.insert(make_pair('(',"%28"));
	m.insert(make_pair(')',"%29"));
	m.insert(make_pair('*',"%2a"));
 
	string s;
	char line[80];
	while (cin.getline(line,80)){
		if (line[0] == '#')
			break;
		s = line;
		for (int i=0;i<s.size();i++){
			if (m.find(s[i]) == m.end()){
				cout << s[i];
			}
			else{
				cout << m[s[i]];
			}
		}
		cout << endl;
	}
	return 0;
}
分类: OJ, 算法 标签: , , , ,

ZJU OJ 1251

2012年8月25日 没有评论
#include <iostream>
#include <vector>
using namespace std;
 
int main(){
  int n, c=0;
  while (cin >> n){
	if (n == 0)
		break;
	int sum = 0;
	c++;
	vector<int> v;
	for (int i=0;i < n;++i){
		int d;
		cin >> d;
		v.push_back(d);
		sum += d;
	}
	int avg = sum / n;
	sum = 0;// now it's number of moves
	for (int i=0;i < v.size();++i){
		if (v[i] > avg)
			sum += v[i] - avg;
	}
	cout << "Set #" << c << endl;
	cout << "The minimum number of moves is " << sum << "." << endl;
	cout << endl;
  }
  return 0;
}
分类: OJ, 算法 标签: , , , ,

ZJU OJ 1115

2012年8月25日 没有评论

模九算digital root

不要用long long,字符串处理

#include <iostream>
#include <string>
using namespace std;
 
int main(){
    string s;
    while(cin >> s){
		if (s == "0")
			break;
        int n = 0;
        for(int i = 0;i != s.size();i++)
            n += s[i] - '0';
        n %= 9;
        if(n == 0) n=9;
        cout << n << endl;
    }
    return 0;
}
分类: OJ, 算法 标签: , , , , ,

ZJU OJ 2947

2012年8月23日 没有评论
#include <iostream>
#include <string>
using namespace std;
 
int main(){
	int n,p,q;
	cin >> n;
	string s,sa,sb;
	for (int i=0;i<n;++i){
		cin >> p;
		for (int i=0;i<p;++i){
			cin >> s;
			sa += s[0];
		}
		cin >> q;
		for (int i=0;i<q;++i){
			cin >> s;
			sb += s[0];
		}
		if (sa.compare(sb))
			cout << "DIFFERENT" << endl;
		else
			cout << "SAME" << endl;
		sa = "";
		sb = "";
	}
}
分类: OJ, 算法 标签:

上海交通大学08年研究生机试题B

2009年9月23日 没有评论

题目
Problem B. Simple Sorting
Input file: Standard Input
Output file: Standard Output
Time Limit: 1 Second

You are given an unsorted array of integer numbers. Your task is to sort this array and kill possible duplicated elements occurring in it.

Input
The first line of the input contains an integer number N representing the quantity of numbers in this array(1≤N≤1000). Next N lines contain N integer numbers(one number per each line) of the original array.

Output
Output file should contain at most N numbers sorted in ascending order. Every number in the output file should occur only once.

Sample input and output
Standard Input Standard Output
6 3
8 7
8 8
7
3
7
7

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <iostream>
#include <fstream>
using namespace std;
#define MAX_LEN 1000
 
int number_of_inputs;
int inputs[MAX_LEN];
 
void get_inputs()
{
	int i;
	cin >> number_of_inputs;
	for (i=0;i<number_of_inputs;++i)
	{
		cin >> inputs[i];
	}
}
 
void qsort(int left,int right)
{
	int i = left;
	int j = right;
	int pivot_index = (i + j) / 2;
	int pivot = inputs[pivot_index];
	while (i <= j)
	{
		while (inputs[i] < pivot)
			++i;
		while (inputs[j] > pivot)
			--j;
		if (i <= j)
		{
			int temp = inputs[i];
			inputs[i++] = inputs[j];
			inputs[j--] = temp;
		}
	}
	if (i > left)
		qsort(left,j);
	if (j < right)
		qsort(i,right);
}
int main()
{
	get_inputs();
 
	qsort(0,number_of_inputs-1);
	ofstream output_file;
	output_file.open("output.txt");
	for (int i =0;i<number_of_inputs-1;++i)
	{
		if (inputs[i] != inputs[i+1])
			output_file << inputs[i] << endl;
	}
	if (i == number_of_inputs -1)
		output_file << inputs[i] << endl;
	output_file.close();
	return 0;
}
分类: 算法 标签: , ,

上海交通大学08年研究生机试题A

2009年9月23日 没有评论

这两天在准备保送到交大软院,由于要考机试,这两天狂练C++中,把自己的代码贴出来吧,不能再懒了,再懒博客就要荒废了。

题目:
Problem A. Prime Number
Input file: Standard Input Page 1 of 2
Output file: Standard Output
Time Limit: 1 Second
Output the k-th prime number.

Input
k≤10000

Output
The k-th prime number.

Sample input and output
Standard Input Standard Output
3 5
7 17

C++代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
#include <cmath>
using namespace std;
 
int isPrime(int n)
{
	int i,flag = 1;
	for (i=2;i<=sqrt(n);++i)
	{
		if (n % i == 0)
		{
			flag = 0;
			break;
		}
	}
	return flag;
}
 
int main()
{
	int i = 1,n = 2,k,result;
	cin >> k;
	while(i <= k)
	{
		result = n++;
		if (isPrime(result))
			++i;
	}
	cout << result;
}
分类: 算法 标签: , ,