codeforces 218 div.2

本文从WordPress迁移而来, 查看全部WordPress迁移文章

A.

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
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <utility>
#include <iterator>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
using namespace std;
#define LL long long
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))
#define N 110

int matrix[N][N],row,col,n,K;

int main(){
	while(cin >> n >> K){
		for(int i = 0; i < n/K; i++)
			for(int j = 0; j < K; j++)
				cin >> matrix[i][j];
		int ans = 0;
		for(int j = 0; j < K; j++){
			int one = 0 , two = 0;
			for(int i = 0; i < n/K; i++){
				if(matrix[i][j] == 1) one++;
				else two++;
			}
			if(one < two) ans += one;
			else ans += two;
		}
		cout << ans << endl;
	}
	return 0;
}

B.

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
60
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <utility>
#include <iterator>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
using namespace std;
#define LL long long
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))

int A,B,f[3] = {2,3,5};

int gcd(int a,int b){
	return b == 0 ? a : gcd(b,a%b);
}

int solve(){
	int a = A , b = B;
	for(int i = 0; i < 3; i++){
		while(a % f[i] == 0)
			a /= f[i];
	}
	for(int i = 0; i < 3; i++){
		while(b % f[i] == 0)
			b /= f[i];
	}
	if(a != b) return -1;
	A /= a; B /= b;
	int g = gcd(A,B);
	A /= g; B /= g;
	int ans = 0;
	a = A; b = B;
	for(int i = 0; i < 3; i++){
		while(a % f[i] == 0){
			a /= f[i]; ans++;
		}
	}
	for(int i = 0; i < 3; i++){
		while(b % f[i] == 0){
			b /= f[i]; ans++;
		}
	}
	return ans;
}

int main(){
	while(cin >> A >> B){
		if(A == B) puts("0");
		else printf("%d\n",solve());
	}
	return 0;
}

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <utility>
#include <iterator>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
using namespace std;
#define LL long long
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))
#define N 110
#define INF 0x3f3f3f3f

int need[3],num[3],cost[3],now[3];
LL money;

LL solve(){
	LL c = 0LL;
	for(int i = 0; i < 3; i++){
		if(need[i] == 0) continue;
		c += cost[i] * (need[i] - num[i]); 
	}
	if(money < c) return 0LL;
	money -= c;
	c = 0LL;
	for(int i = 0 ; i < 3; i++){
		c += need[i] * cost[i];
	}
	LL NUM = money / c;
	return NUM+1;
}

int main(){
	char str[N];
	while(cin >> str){
		cl(need,0);
		for(int i = 0; str[i]; i++){
			if(str[i] == 'B') need[0]++;
			else if(str[i] == 'S') need[1]++;
			else need[2]++;
		}

		for(int i = 0 ; i < 3; i++)
			scanf("%d",&num[i]);
		for(int i = 0 ; i < 3; i++)
			scanf("%d",&cost[i]);
		scanf("%I64d",&money);

		LL ans = 0LL;
		while(true){
			for(int i = 0; i < 3; i++){
				if(need[i] != 0) now[i] = num[i] / need[i];
				else now[i] = INF;
			}
			int m = min(now[0] , min(now[1],now[2]) );
			ans += (LL)m;
			for(int i = 0; i < 3; i++)
				num[i] -= m*need[i];

			bool mark = true;
			for(int i = 0; i < 3; i++){
				if(need[i] == 0) continue;
				if(num[i] > need[i]) mark = false;
			}
			if(mark) break;

			LL c = 0;
			for(int i = 0; i < 3; i++){
				if(need[i] && num[i] < need[i]){
					c += cost[i] * (need[i] - num[i]);
					num[i] = need[i];
				}
			}
			if(c > money) { money = 0LL; break; }
			money -= c;
		}
		if(money == 0LL)
			cout << ans << endl;
		else{
			ans += solve();
			cout << ans << endl;
		}
	}
	return 0;
}

D.

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
60
61
62
63
64
65
66
67
68
69
70
71
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <utility>
#include <iterator>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
using namespace std;
#define LL long long
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))
#define N 200010
         
int n,pre[N],__next[N],fp[N]; //
LL cap[N],re[N];

void solve(int pos,LL x){
	int P = pre[pos];
	while(true){
		if(pos == n+1) break;
		if(re[pos] == 0LL){
			pos = __next[pre[pos]];	
		}
		if(re[pos] >= x){
			re[pos] -= x; break;
		}
		x -= re[pos];
		re[pos] = 0LL;
		int tmp_next = __next[pos];
		__next[ pre[pos] ] = tmp_next;
		pre[ tmp_next ] = pre[pos];
		pre[pos] = P;
		pos = tmp_next;
	}
}

int main(){
	while(scanf("%d",&n)!=EOF){
		for(int i = 1; i <= n; i++){
			scanf("%I64d",&cap[i]);
			re[i] = cap[i];
			pre[i] = i-1;
			__next[i] = i+1;
			fp[i] = -1;
		}
		pre[0] = 0; __next[0] = 1;
		pre[n+1] = n; __next[n+1] = n+1;
		int Q;
		scanf("%d",&Q);
		while(Q--){
			int op,pos;
			LL x;
			scanf("%d",&op);
			if(op == 1){
				scanf("%d%I64d",&pos,&x);
				solve(pos,x);
			}
			else{
				scanf("%d",&pos);
				printf("%d\n",cap[pos] - re[pos]);
			}
		}
	}
	return 0;
}