A. Shortest Path with Obstacle
https://codeforces.com/contest/1547/problem/A
Problem - A - Codeforces
codeforces.com
A, B, F의 위치가 주어졌을 때 A->B로 가는 최단 거리를 구하는 문제이다.
F가 거슬리는 경우를 생각해보자.
A, B, F가 한 줄 위에 같이 존재하면서 F가 A, B사이에 있는 경우에만 A->B로 가는 경로에서 F를 우회하기 위해 2번의 움직임이 더 필요하다.
그 외에 경우는 A->B 최단거리인 \(|Ax - Bx| + |Ay - By|\)가 답이 된다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 2147483647;
const int MAX_N = 1e+5 + 1;
const int MOD = 1e5;
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
void solve() {
int Ax, Ay, Bx, By, Fx, Fy;
cin >> Ax >> Ay >> Bx >> By >> Fx >> Fy;
if (
((Ax == Bx && Bx == Fx) && ((Ay <= Fy && Fy <= By) || (By <= Fy && Fy <= Ay)))
||
((Ay == By && By == Fy) && ((Ax <= Fx && Fx <= Bx) || (Bx <= Fx && Fx <= Ax)))
) {
cout << abs(Ax - Bx) + abs(Ay - By) + 2 << '\n';
}
else {
cout << abs(Ax - Bx) + abs(Ay - By) << '\n';
}
return;
}
int main() {
ios::ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int T;
cin >> T;
while (T--) {
solve();
}
return 0;
}B. Alphabetical Strings
https://codeforces.com/contest/1547/problem/B
Problem - B - Codeforces
codeforces.com
a만 들어있는 string을 str이라고 하자. alphabetical이란, b부터 z까지 알파벳의 순서대로 str의 앞 or 뒤에 삽입했을 때 나오는 string을 일컫는다. 입력받은 string이 alphabetical인지 판별하는 게 목표인 문제이다.
입력받은 string안에 들어있는 알파벳들의 위치를 기억하자.
이 위치를 기반으로 어떤 알파벳을 삽입하는 상황일 때 이전 알파벳의 위치를 보고 앞으로 삽입할지, 뒤로 삽입할지 판단할 수 있다. 따라서 a만 들어있는 string을 만들고 b부터 순서대로 삽입할 때 이전 알파벳의 위치가 삽입해야되는 알파벳의 위치보다 앞에 있으면 뒤에 삽입, 그렇지 않으면 앞에 삽입해준다.
마지막으로 위 과정을 거쳐 나온 string이 입력받은 string과 같은지 확인해주면 된다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 2147483647;
const int MAX_N = 1e+5 + 1;
const int MOD = 1e5;
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
int alp[26] = { 0, };
void solve() {
memset(alp, -1, sizeof(alp)); //-1로 초기화
string str;
cin >> str;
for (int i = 0; i < str.size(); ++i) {
if (alp[str[i] - 'a'] == -1) { // 알파벳이 처음 등장
alp[str[i] - 'a'] = i;
}
else if (alp[str[i] - 'a'] >= 0) { // 같은 알파벳이 두번 이상 등장
cout << "NO\n";
return;
}
}
string ans = "a";
for (int i = 1; i < 26; ++i) {
if (alp[i] == -1) break; // 입력받은 string에 없는 알파벳이 나오면 break
int prev = alp[i - 1];
int cur = alp[i];
if (prev > cur) ans = (char)('a' + i) + ans;
else ans += (char) ('a' + i);
}
if (ans == str) cout << "YES\n";
else cout << "NO\n";
return;
}
int main() {
ios::ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int T;
cin >> T;
while (T--) {
solve();
}
return 0;
}C. Pair Programming
https://codeforces.com/contest/1547/problem/C
Problem - C - Codeforces
codeforces.com
문제를 처음에 잘못 읽어 여러번의 WA를 받은 문제이다. 문제의 조건과 내용은 항상 정확하게 읽어야한다는 것을 다시 한번 상기시키는 문제였다.
Monocarp와 Polycarp 중 한명이 매초마다 (file 마지막에 한줄을 더 추가) or (이미 있는 라인 하나를 수정)을 한다.
현재 파일에 적혀있는 라인의 개수와, Monocarp와 Polycarp가 각각 하는 Action들의 순서와 내용이 주어졌을 때, 가능한 Action의 순서를 출력해주어야 한다.
Monocarp와 Polycarp 중 한명이라도 다음에 하는 Action이 라인을 추가하는 것이라면 greedy하게 라인을 추가해주자. 만약, 둘 다 라인을 바꿔주는 Action이라면 바꿔야하는 라인이 현재 쓰여있는 라인인지 확인해주면 된다. 마지막으로 한명이 먼저 Action을 다 끝냈을 때도 고려해주자.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 2147483647;
const int MAX_N = 1e+5 + 1;
const int MOD = 1e5;
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
int a[101] = { 0, };
int b[101] = { 0, };
void solve() {
int k, n, m;
cin >> k >> n >> m;
for (int i = 1; i <= n; ++i) cin >> a[i];
for (int i = 1; i <= m; ++i) cin >> b[i];
vector<int> ans;
int ai = 1, bi = 1;
for (int i = 1; i <= n + m; ++i) {
if (ai <= n && bi <= m) { // 두명 다 할 일이 남아있을 때
if (a[ai] == 0) { // 라인 추가
ans.push_back(0);
k++;
ai++;
}
else if (b[bi] == 0) { // 라인 추가
ans.push_back(0);
k++;
bi++;
}
else {
if (a[ai] <= k) {
ans.push_back(a[ai++]);
}
else if (b[bi] <= k) {
ans.push_back(b[bi++]);
}
else { // 둘 다 바꿀 수 있는 라인이 없는 경우
cout << -1 << '\n';
return;
}
}
}
else if(ai <= n){ // b의 Action이 끝난 경우
if (a[ai] == 0) {
ans.push_back(0);
k++;
ai++;
}
else if (a[ai] <= k) {
ans.push_back(a[ai++]);
}
else {
cout << -1 << '\n';
return;
}
}
else if (bi <= m) { // a의 Action이 끝난 경우
if (b[bi] == 0) {
ans.push_back(0);
k++;
bi++;
}
else if (b[bi] <= k) {
ans.push_back(b[bi++]);
}
else {
cout << -1 << '\n';
return;
}
}
}
for (int num : ans) cout << num << ' ';
cout << '\n';
return;
}
int main() {
ios::ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int T;
cin >> T;
while (T--) {
solve();
}
return 0;
}D. Co-growing Sequence
추가 예정
E. Air Conditioners
추가 예정
'codeforce' 카테고리의 다른 글
| Round #728 (0) | 2021.06.26 |
|---|---|
| Round #727 (0) | 2021.06.25 |
| Round #725 (Div. 3) (0) | 2021.06.14 |
| Round #707 (Div. 2) (0) | 2021.05.25 |
| Round #706 (Div. 2) (0) | 2021.05.24 |