D를 DP로 접근했는데 아직 왜 틀린지 모르겠습니다.
하하하하하ㅏ하하하하하흐헝허어허엏어ㅠㅠㅠㅠ
저것만 풀었어도 기뻤을 텐데…
A. Divisibility Problem
알고리즘
- 수학
A % B 만큼 A를 증가하게 되면 B로 나누어 떨어집니다.
그럴때 그 차이가 정답입니다.
#include <bits/stdc++.h>
#define FIO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define FOR(a,b,c) for(int a = (b); a <= (c); a++)
#define RFOR(a,b,c) for(int a = (b); a >= (c); a--)
#define all(x) (x).begin(), (x).end()
#define vi vector <int>
#define vvi vector <vi>
#define ll long long
#define vll vector <ll>
#define vvl vector <vll>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define eb emplace_back
#define ep emplace
#define fs first
#define sd second
#define mod 998244353
#define EPS 1e-9
using namespace std;
int main() {
FIO;
int t; cin >> t; while (t--) {
int a, b; cin >> a >> b;
int x = a % b;
cout << (x ? b - x : 0) << '\n';
}
return 0;
}
B. K-th Beautiful String
알고리즘
- 완전 탐색
- 구현
모든 문자열을 구하려고 하면 당연히 시간초과가 납니다.
사전순일때 K번째 값을 구하는 것이므로 더 짧은 시간에 구할 수 있습니다.
첫번째 등장하는 b의 위치에 따라서 순서의 범위가 정해집니다.
만약 뒤에서 두 번째에 등장하면 1~1(aabb)이고, 세 번째에 등장하면 2~3(abab, abba)입니다.
이런식으로 첫번째 위치를 먼저 원하는 K번째 값이 범위안에 들어오도록 합니다.
범위는 1~X-1의 합으로 구할 수 있습니다.
그 다음에 두 번째 등장하는 b의 위치를 K에 맞춰서 배치하면 됩니다.
#include <bits/stdc++.h>
#define FIO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define FOR(a,b,c) for(int a = (b); a <= (c); a++)
#define RFOR(a,b,c) for(int a = (b); a >= (c); a--)
#define all(x) (x).begin(), (x).end()
#define vi vector <int>
#define vvi vector <vi>
#define ll long long
#define vll vector <ll>
#define vvl vector <vll>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define eb emplace_back
#define ep emplace
#define fs first
#define sd second
#define mod 998244353
#define EPS 1e-9
using namespace std;
int main() {
FIO;
int t; cin >> t; while (t--) {
int a, b; cin >> a >> b;
string ans;
FOR(i, 0, a - 1) ans += 'a';
int sum = 0;
FOR(i, 1, a) {
sum += i;
if (sum >= b) {
ans[a - i - 1] = ans[a - 1 - (b - (sum - i + 1))] = 'b';
break;
}
}
cout << ans << '\n';
}
return 0;
}
C. Ternary XOR
알고리즘
- 그리디
0은 0과 0, 2는 1과 1을 분배합니다.
1이 어디에 할 지 고민되는데 처음 1을 분배한 곳에 다음 1부터는 다른 곳에 분배를 해줍니다.
그래야 둘 중 최댓값이 최소가 될 수 있습니다.
ex) 2101211 -> 1100100, 1001111
#include <bits/stdc++.h>
#define FIO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define FOR(a,b,c) for(int a = (b); a <= (c); a++)
#define RFOR(a,b,c) for(int a = (b); a >= (c); a--)
#define all(x) (x).begin(), (x).end()
#define vi vector <int>
#define vvi vector <vi>
#define ll long long
#define vll vector <ll>
#define vvl vector <vll>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define eb emplace_back
#define ep emplace
#define fs first
#define sd second
#define mod 998244353
#define EPS 1e-9
using namespace std;
int main() {
//FIO;
int t; cin >> t; while (t--) {
int n; cin >> n;
int arr[50005] = {}, x[50005], f = 0;
FOR(i, 1, n) {
scanf("%1d", &x[i]);
if (!f && x[i] == 1) {
f = 1;
arr[i] = 1;
}
else if(!f) arr[i] = x[i] / 2;
}
FOR(i, 1, n) cout << arr[i];
cout << '\n';
FOR(i, 1, n) cout << x[i] - arr[i];
cout << '\n';
}
return 0;
}