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;
}