A - Johnny and Ancient Computer
Problem - A - Codeforces
codeforces.com
수 \(a,b\)가 주어진다.
\(a\)에 다음과 같은 연산을 해서 \(b\)로 만들 수 있는지, 가능하면 최소 몇번의 연산으로 가능한지 알아내야 한다.
1. 2를 곱한다
2. 4를 곱한다
3. 8을 곱한다
4. 2로 나눠 떨어진다면, 2로 나눈다
5. 4로 나눠 떨어진다면, 4로 나눈다
6. 8로 나눠 떨어진다면, 8로 나눈다
먼저 큰 수가 작은 수로 나눠 떨어지지 않는다면, 불가능하다.
나눠 떨어진다면, 큰 수를 작은 수로 나눈 값을 \(x\)라고 하자.
\(x\)가 2의 거듭제곱꼴이 아니라면 불가능하다.
2의 거듭제곱 꼴이라면, \(x = 2^n\)이라고 했을 때,
\(\lceil \frac n3 \rceil\)이 답이다.
|
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
|
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int t; cin >> t;
while (t--)
{
ll a, b; cin >> a >> b;
if (a > b) swap(a, b);
if (b % a)
{
cout << "-1\n";
continue;
}
ll res = b / a;
if (res & (res - 1))
{
cout << "-1\n";
continue;
}
for (int i = 0; i <= 60; i++)
{
if (res == (1ll << i))
{
cout << (i + 2) / 3 << '\n';
break;
}
}
}
}
|
B - Johnny and His Hobbies
Problem - B - Codeforces
codeforces.com
양수의 집합 \(s\)가 주어진다.
\(s\)의 모든 원소를 어떤 양수 \(k\)와 bitwise XOR해서 나온 수들의 집합 \(S\)가 있을 때,
\(s\)와 \(S\)가 같아질 수 있는지 여부를 판별하고, 가능하다면 가장 작은 양수 \(k\)를 알아내야 한다.
\(1 \le k \lt 1024\)에 해당하는 모든 \(k\)에 대해 \(S\)를 직접 만든 다음, 두 집합이 같은지 판별하면 된다.
|
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
|
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
int n;
int cnt[1024];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int t; cin >> t;
while (t--)
{
memset(cnt, 0, sizeof cnt);
cin >> n;
for (int i = 0; i < n; i++)
{
int s; cin >> s;
cnt[s]++;
}
bool hasAns = false;
for (int i = 1; i < 1024; i++)
{
bool flag = true;
int ccnt[1024];
memcpy(ccnt, cnt, sizeof cnt);
for (int j = 0; j < 1024; j++)
{
if (ccnt[i ^ j] != ccnt[j])
{
flag = false;
break;
}
}
if (flag)
{
hasAns = true;
cout << i << '\n';
break;
}
}
if (!hasAns) cout << "-1\n";
}
}
|
C - Johnny and Another Rating Drop
Problem - C - Codeforces
codeforces.com
정수 \(n\)이 주어진다.
0부터 \(n\)까지 모든 수를 차례대로 이진법으로 나열했을 때, 이웃하는 두 숫자의 자릿수가 다른 부분의 개수의 합을 구해야 한다.
가장 작은 순으로 \(n\)번째 자릿수는 수가 \(k-1\) 에서 \(k\)로 바뀔 때, \(k\)가 \(2^{n-1}\)로 나눠 떨어지면 바뀜을 알 수 있다.
따라서 답은 \(\lfloor \frac {n}{2^0} \rfloor + \lfloor \frac {n}{2^1} \rfloor + \cdots + \lfloor \frac {n}{2^{60}} \rfloor \) 다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int t; cin >> t;
while (t--)
{
ll n; cin >> n;
ll ans = 0;
for (int i = 0; i <= 60; i++)
ans += n / (1ll << i);
cout << ans << '\n';
}
}
|
A - Johnny and Contribution
Problem - A - Codeforces
codeforces.com
\(n\)개의 정점과 \(m\)개의 간선으로 이루어진 그래프가 있다.
이 그래프의 각 정점마다 수를 써넣을 수 있는데, 이 정점에 연결된 다른 정점에 쓰여있지 않은 수 중에 가장 작은 수를 쓸 수 있다.
어떤 정점부터 수를 쓰는지는 원하는대로 정할 수 있다고 할 때, 각 정점에 입력으로 주어지는 수를 쓸 수 있는지 여부를 알아내고, 가능하다면 그 순서를 출력해야 한다.
관찰을 잘 해보면, 작은 숫자부터 쓰면 무조건 최적임을 알 수 있다.
\(1 \le k \le n\)에 대해 차례대로, 입력으로 \(k\)가 주어진 모든 정점에 대해 \(k\)를 쓸 수 있는지 확인하자.
\(k\)를 쓸 수 있기 위해서는 \(1\)부터 \(k-1\)까지의 수가 쓰여진 정점과 연결되어 있어야 하고, \(k\)가 쓰여진 수가 연결되어있지 않아야 한다.
후자는 쉽게 알 수 있고, 전자는 각 정점에 해당하는 배열을 만든다음, 각 단계에서 처리한 정점과 연결되어있는 정점에 1을 더했을 때, 배열에 \(k-1\)이 저장되어 있는지 확인함으로써 알 수 있다.
|
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
|
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
int n, m;
vector <int> graph[500001];
vector <int> idx[500001];
int cnt[500001];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> m;
for (int i = 0; i < m; i++)
{
int a, b; cin >> a >> b;
graph[a].push_back(b);
graph[b].push_back(a);
}
for (int i = 0; i < n; i++)
{
int d; cin >> d;
idx[d].push_back(i + 1);
}
for (int i = 1; i <= n; i++)
{
set <int> plus;
for (int v : idx[i])
{
if (plus.find(v) != plus.end())
{
cout << -1;
return 0;
}
if (cnt[v] != i - 1)
{
cout << -1;
return 0;
}
for (int nv : graph[v])
plus.insert(nv);
}
for (int p : plus)
{
cnt[p]++;
}
}
for (int i = 1; i <= n; i++)
{
for (int v : idx[i]) cout << v << ' ';
}
}
|
B - Johnny and Grandmaster
Problem - B - Codeforces
codeforces.com
수 \(p\)가 주어진다.
\(n\)개의 수 \(p^{k_i}\)에 대해, 수를 두 개의 묶음으로 나눴을 때, 두 묶음에 있는 수들의 합의 차이를 최소화 해야 한다.
우선 \(p\)가 1이라면, 답은 \(n\)을 2로 나눈 나머지이다.
\(p\)진수를 저장할 수 있는 구조체를 하나 만들자.
여러가지 방법이 있을 수 있는데, 본인은 map을 사용해서 \({n, a} = a \times p^n\)을 저장하는 식으로 구현했다.
이 구조체에는 현재 두 묶음의 차이가 저장될 것이다.
차이를 최소화하기 위해서는 큰 수부터 나눠 나가는것이 유리하므로, 배열 \(k\)를 내림차순 정렬한 다음 차례대로 살펴보자.
현재 구조체에 저장된 수가 없다면 (0 이라면), \(p^{k_i}\)를 더한다.
그렇지 않다면, \(p^{k_i}\)를 빼면 된다.
빼는 과정에서 받아내림이 필요할 수 있다.
\(p^a\)에서 \(p^b\)를 뺄 때, \([b,a-1]\)구간의 모든 자릿수에 대해 연산하면 시간이 부족하므로,
\(p^a\)의 계수에서 1을 빼고, \(p^b\)의 계수에 \(p^{a-b}\)를 더해주는 식으로 구현하면 빠르게 해결할 수 있다.
\(p^{a-b}\)가 long long의 표현 범위를 넘어가는 것이 또 문제가 될 수 있는데, 적당한 INF를 더해주는 식으로 처리한 다음 마지막에 해당하는 값을 따로 더해주면 된다.
|
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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
|
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
const ll MOD = 1e9 + 7;
const ll INF = 987654321987654321;
ll mpow(ll n, ll a)
{
if (a == 0) return 1;
ll res = mpow(n, a / 2);
res = res * res % MOD;
if (a % 2) res = res * n % MOD;
return res;
}
ll n, p;
ll k[1000001];
map <ll, ll> dif;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int t; cin >> t;
while (t--)
{
dif.clear();
cin >> n >> p;
for (int i = 0; i < n; i++)
{
cin >> k[i];
}
if (p == 1)
{
cout << n % 2 << '\n';
continue;
}
sort(k, k + n);
vector <ll> add;
for (int i = n - 1; i >= 0; i--)
{
if (dif.empty())
{
dif[k[i]] = 1;
continue;
}
auto it = dif.lower_bound(k[i]);
if (it->first != k[i])
{
ll tmp = 1;
bool flag = false;
for (int j = it->first - 1; j >= k[i]; j--)
{
tmp *= p;
if (tmp > n)
{
flag = true;
break;
}
}
if (flag)
{
dif[k[i]] = INF;
ll res = (mpow(p, it->first) - mpow(p, k[i]) + MOD) % MOD;
add.push_back(res);
}
else
{
dif[k[i]] = tmp - 1;
}
}
if (it->second != INF)
{
if (--it->second == 0)
{
dif.erase(it);
}
}
else
{
add.push_back(MOD - mpow(p, it->first));
}
}
ll ans = 0;
for (auto it : dif)
{
if (it.second == INF) continue;
ans += mpow(p, it.first) * it.second % MOD;
ans %= MOD;
}
for (ll x : add)
{
ans += x;
ans %= MOD;
}
cout << ans << '\n';
}
}
|
C - Johnny and Megan's Necklace
Problem - C - Codeforces
codeforces.com
\(n\)개의 목걸이 파츠가 있다.
파츠는 2개의 부분으로 이루어져 있고, 각각 정수가 쓰여져 있다.
이 목걸이 파츠를 원형으로 이어 하나의 목걸이를 만드려고 한다.
목걸이 파츠를 서로 이은 부분의 아름다움은 이어진 부분에 쓰여진 두 정수를 XOR한 값이 \(2^k\)로 나누어 떨어진다고 할 때, \(k\)의 최대값이다. 만약 두 수가 같다면, 20이다.
최종적으로 만들어진 목걸이의 아름다움은, 이어진 부분의 아름다움의 최소값이다.
목걸이의 아름다움을 최대화 했을 때의 값과, 그 때 파츠를 잇는 방법을 알아내야 한다.
먼저 \(k\)가 답이 되기 위해서는 각 정수를 \(2^k\)로 나누었을 때, 나머지가 같은 부분 끼리 이어서 하나의 목걸이가 될 수 있어야 한다.
이것을 각 파츠가 정점이고 나머지가 같은 부분끼리 간선이 있는 그래프로 생각해보면, 이 그래프에 오일러 회로가 존재하는지 여부를 판별하는 문제로 생각할 수 있다.
오일러 회로를 만들거나 존재 여부를 판별하는 시간은 일반적인 그래프 탐색과 시간복잡도가 같으므로, 이를 모든 \(0 \le k \le 20\)에 대해 회로를 만들 수 있는지 확인해서 가능한 \(k\)의 최대값을 구하면 된다.
|
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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
|
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
int n;
int pearl[1000001];
vector <int> idx[1 << 20];
int last[1 << 20];
int prv[1000001];
int nxt[1000001];
int cache[500001];
int ans;
bool DFS(int v, int rt)
{
cache[v / 2] = 1;
int v2 = (v / 2 * 2) + 1 - v % 2;
bool isFirst = true;
int cidx = pearl[v] % (1 << ans);
bool isConnected = false;
for (int &i = last[cidx]; i < idx[cidx].size(); i++)
{
int nv = idx[cidx][i];
int nv2 = (nv / 2 * 2) + 1 - nv % 2;
if (cache[nv / 2]) continue;
if (isFirst)
{
isFirst = false;
nxt[v] = nv;
prv[nv] = v;
if (!DFS(nv2, rt)) return false;
isConnected = true;
}
else
{
int new_rt = nxt[v];
nxt[v] = nv;
prv[nv] = v;
if (!DFS(nv2, new_rt)) return false;
isConnected = true;
}
}
if (!isConnected)
{
if (pearl[v] % (1 << ans) == pearl[rt] % (1 << ans))
{
nxt[v] = rt;
prv[rt] = v;
return true;
}
}
return isConnected;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n;
for (int i = 0; i < n; i++)
cin >> pearl[i * 2] >> pearl[i * 2 + 1];
for (ans = 20; ans > 0; ans--)
{
for (int i = 0; i < (1 << ans); i++) idx[i].clear();
memset(last, 0, sizeof last);
memset(prv, -1, sizeof prv);
memset(nxt, -1, sizeof nxt);
memset(cache, 0, sizeof cache);
for (int i = 0; i < n; i++)
{
int t1 = pearl[i * 2] % (1 << ans);
int t2 = pearl[i * 2 + 1] % (1 << ans);
idx[t1].push_back(2 * i);
idx[t2].push_back(2 * i + 1);
}
if (!DFS(1, 0)) continue;
bool flag = false;
for (int i = 0; i < n; i++) if (!cache[i]) flag = true;
if (flag) continue;
cout << ans << '\n';
int v = 0;
for (int i = 0; i < n; i++)
{
int v2 = (v / 2 * 2) + 1 - v % 2;
cout << v + 1 << ' ' << v2 + 1 << ' ';
v = nxt[v2];
}
return 0;
}
cout << "0\n";
for (int i = 1; i <= 2 * n; i++) cout << i << ' ';
}
|
D - Johnny and James
Problem - D - Codeforces
codeforces.com
추가 예정
E - James and the Chase
Problem - E - Codeforces
codeforces.com
추가 예정
F - Johnny and New Toy
Problem - F - Codeforces
codeforces.com
추가 예정
'문제 풀이 > Codeforces' 카테고리의 다른 글
| Codeforces Round #650 (Div. 3) (0) | 2020.06.17 |
|---|---|
| Codeforces Round #648 (Div. 2) (0) | 2020.06.08 |
| Codeforces Round #646 (Div. 2) (0) | 2020.06.01 |
| Educational Codeforces Round 88 (0) | 2020.05.30 |
| Codeforces Round #645 (Div. 2) (0) | 2020.05.27 |
