A. Erasing Zeroes
Problem - A - Codeforces
codeforces.com
길이
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
#include <bits/stdc++.h>
using namespace std;
int main(void) {
int t; cin >> t;
while (t--) {
string s; cin >> s;
int cnt = 0;
int prv = -1;
for (int i = 0; i < s.size(); i++) {
if (s[i] == '1') {
cnt += (prv == -1 ? 0 : i - prv - 1);
prv = i;
}
}
cout << cnt << '\n';
}
return 0;
}
|
cs |
B. National Project
Problem - B - Codeforces
codeforces.com
길이
해당 지방은 날씨가 좋은
날씨가 좋은 날 수리한 구간은 퀄리티가 좋고, 날씨가 나쁜 날 수리한 구간은 퀄리티가 나쁘다.
날마다 도로를 한 unit만큼 수리할지, 그냥 쉴지 선택할 수 있다.
전체 도로의 절반 이상이 퀄리티 좋은 상태로 수리가 끝나려면 최소 며칠이 필요한지 구해야 한다.
반드시 퀄리티 좋아야 하는 구간의 길이
날씨 좋은 날이
답은
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
int main(void) {
int t; cin >> t;
while (t--) {
ll n, g, b;
cin >> n >> g >> b;
ll h = (n + 1) / 2;
ll q = h / g;
ll r = h % g;
ll cnt = h + b * max(0ll, (r ? q : q-1));
cout << max(n, cnt) << '\n';
}
return 0;
}
|
cs |
C. Perfect Keyboard
키보드는
패스워드가 문자열
위 조건을 만족하는 키보드 조합을 구하는 문제이다.
그래프로 모델링하여 생각할 수 있다.
키보드 구성이 불가능한 케이스
1) 어떤 정점에 연결된 간선이 3개 이상인 경우
2) 사이클이 존재하는 경우
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
|
#include <bits/stdc++.h>
using namespace std;
vector<bool> visited(26);
vector<set<int> > adj;
bool dfs1(int u, int p) {
bool ret = false;
visited[u] = true;
for (int v: adj[u]) {
if (v == p) continue;
if (!visited[v]) ret = ret || dfs1(v, u);
else return true;
}
return ret;
}
void dfs2(int u) {
cout << (char)('a'+u);
visited[u] = true;
for (int v: adj[u]) {
if (!visited[v]) {
dfs2(v);
}
}
}
int main(void) {
int t; cin >> t;
while (t--) {
string s; cin >> s;
adj.clear(); adj.resize(26);
for (int i = 1; i < s.size(); i++) {
int a = s[i-1] - 'a';
int b = s[i] - 'a';
adj[a].insert(b);
adj[b].insert(a);
}
bool flag = false;
visited.assign(26, false);
for (int i = 0; i < 26; i++) {
if (!visited[i]) {
flag = dfs1(i, i);
if (flag) break;
}
if (adj[i].size() >= 3) {
flag = true;
break;
}
}
if (flag) {
cout << "NO\n";
}
else {
cout << "YES\n";
visited.assign(26, false);
for (int i = 0; i < 26; i++) {
if (!visited[i] && adj[i].size() == 1) dfs2(i);
}
for (int i = 0; i < 26; i++) {
if (!visited[i]) cout << (char)('a'+i);
}
cout << '\n';
}
}
return 0;
}
|
cs |
D. Fill The Bag
Problem - D - Codeforces
codeforces.com
사이즈가
박스의 사이즈는 모두
가방을 박스로 빈틈없이 채울 때 필요한 최소 division 횟수를 구하는 문제이다.
우선 박스들의 크기 합이
모든 박스를 크기
binary representation of
1)
남은
2)
남은
3)
남은 박스들 중 가장 작은 박스의 사이즈를
해당 박스를 쪼개서
이때 필요한 division 횟수는
이 과정에서 만들어지는 박스들을 통해
ex)
이후
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
|
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
int log2(ll a) {
int ret = 0;
while (a > 1) {
ret++;
a /= 2;
}
return ret;
}
int main(void) {
int t; cin >> t;
while (t--) {
ll n, m, sum = 0;
cin >> n >> m;
vector<int> box(65);
while (m--) {
ll a; cin >> a;
sum += a;
box[log2(a)]++;
}
if (n > sum) {
cout << -1 << '\n';
continue;
}
ll ans = 0;
for (int i = 0; i < 64; i++) {
if (n & (1LL << i)) {
if (box[i]) {
box[i]--;
}
else {
while (!box[i]) i++, ans++;
box[i]--; i--;
continue;
}
}
box[i+1] += box[i] / 2;
}
cout << ans << '\n';
}
return 0;
}
|
cs |
'Codeforces' 카테고리의 다른 글
Codeforces #763 (0) | 2022.01.02 |
---|---|
Codeforces Educational #120 (0) | 2022.01.02 |
Codeforces Global #18 (0) | 2021.12.26 |
Codeforces #619 (0) | 2021.12.23 |
Codeforces #728 (0) | 2021.07.17 |