Round #920 Div. 3 - 4sol
https://codeforces.com/contest/1921
Dashboard - Codeforces Round 920 (Div. 3) - Codeforces
codeforces.com
A. Square
좌표 4개가 주어지고, 해당 좌표가 만드는 사각형의 넓이를 구하는 문제이다.
주어진 문제는 축에 평행하다는 조건이 있었는데,
이를 못보고 CCW 알고리즘을 이용하여 문제를 해결했다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
#include <iostream>
#include <cmath>
using namespace std;
int main(){
int t, x, y;
cin >> t;
while(t--){
pair<int,int>dp[4];
for(int i=0; i<4; i++){
cin >> x >> y;
dp[i]={x,y};
}
cout << (abs(dp[0].first * dp[1].second + dp[1].first * dp[2].second + dp[2].first * dp[0].second - dp[1].first * dp[0].second - dp[2].first * dp[1].second - dp[0].first * dp[2].second)
+ abs(dp[0].first * dp[1].second + dp[1].first * dp[3].second + dp[3].first * dp[0].second - dp[1].first * dp[0].second - dp[3].first * dp[1].second - dp[0].first * dp[3].second)) / 2 << "\n";
}
}
|
cs |
B. Arranging Cats
처음 상태의 박스 n개의 상태가 주어지는데, 1이면 고양이가 앉아있는 상태, 0이면 고양이가 없는 상태이다.
이후 다시 박스 n개의 상태가 주어지는데, 이 때 가능한 경우는 고양이를 옮기거나, 고양이가 추가되거나, 고양이가 사라지거나 세가지 경우의 수 중 하나이다.
그러므로 가장 적은 변화를 야기시키는 경우를 구하면 된다.
먼저 고양이가 있던 자리 그대로 존재하거나, 없던 자리 그대로 존재하지 않는다면 비교할 필요가 없고,
있었는데 없어진다면 어디로 옮겼거나 사라진 것이므로 무조건 변화가 한 번은 존재한다.
마찬가지로 없었는데 생겼다면 어디로 옮겼거나 생긴 것이므로 변화가 한 번은 존재한다.
다만 옮긴 것이라면 당연히 없어진 곳과 생긴곳이 한 번의 변화이므로 두 번 세지않게 조심해야한다.
s1 = 고양이 O -> 고양이 X 의 개수
c1 = 고양이 X -> 고양이 O 의 개수
라고 변수를 선언하면
s1의 변화와 c1의 변화는 상호적으로 일어나야한다.
s1이 존재하고, 현재 고양이가 X -> O인 상태라면 당연히 고양이를 옮긴 것이므로 카운트하지 않지만, (s1을 증가시킬 때 카운트를 올려주었으므로, 만약 다시 올린다면 중복의 문제가 발생한다.)
s1이 존재하지 않은 상황이라면 고양이가 생겼거나 옮긴 변화이므로 카운트를 증가시켜야한다.
c1의 경우도 마찬가지이다.
|
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 <iostream>
using namespace std;
int main(){
int t, n;
cin >> t;
string s, c;
while(t--){
cin >> n >> s >> c;
int s1=0, c1=0, ans=0;
for(int i=0; i<n; i++){
if(s[i]!=c[i]){
if(s[i]=='1'){
if(c1) c1--;
else ans++, s1++;
}
else {
if(s1) s1--;
else ans++, c1++;
}
}
}
cout << ans << "\n";
}
}
|
cs |
C. Sending Messages
휴대폰을 이용하여 정해진 시간에 문자를 보내야하는데, 배터리가 관건이다.
가만히 있으면 초당 a만큼의 배터리가 닳고, 전원을 꺼놓으면 배터리가 닳지 않으나 끄는데 필요한 에너지로 인해 배터리가 소모된다.
최종적으로 정해진 시간에 휴대폰이 켜져있는지 구하는 문제이다.
그래서 문자를 보낸 시간과 다음 문자를 보낼 시간 사이 걸리는 시간 X 초당 닳는 배터리 a와 전원을 끄는데 드는 배터리를 비교하며 초기 배터리에서 빼주면된다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
#include <iostream>
using namespace std;
int main(){
long long x, t, n, f, a, b;
cin >> t;
while(t--){
cin >> n >> f >> a >> b;
int m=0, ti;
bool check=true;
while(n--){
cin >> x;
m=x-m;
ti=min(b, a*m);
if(f-ti<=0) check=false;
f-=ti;
m=x;
}
check? cout << "YES\n" : cout << "NO\n";
}
}
|
cs |
D. Very Different Array
길이 n짜리 배열 a, 길이 m짜리 배열 b가 주어진다.
배열을 잘 조합해 a[i] - b[i]의 합이 최대가 되도록 하는 문제이다.
단순무식하게 오름차순, 내림차순 정렬을 한 후 비교하는 것이 아니라,
상황에 맞게 원소를 나열해야한다.
그래서 생각한 것은 n <= m 의 조건에 따라
m개의 원소를 가진 배열 b를 먼저 오름차순 정렬해주고,
이후 a 배열을 비교하는 방법이다.
가령
b[6] ={ 1, 2, 3, 3, 5, 7}
a[4] = {6, 4, 2, 1}이라고 한다면
| i | 0 | 1 | 2 | 3 | 4 | 5 |
| b | 1 | 2 | 3 | 3 | 5 | 7 |
| a(처음부터) | 6 | 4 | 2 | 1 | ||
| a(마지막부터) | 6 | 4 | 2 | 1 |
이렇게 비교하여 어느 b배열의 원소와 a[i]의 원소의 차이가 큰지 비교하면 된다.
여기서는
b[3] - a[3] < b[5] - a[3] ==> 6
b[2] - a[2] < b[4] - a[2] ==> 3
b[1] - a[1] > b[3] - a[1] ==> 2
b[0] - a[0] > b[2] - a[0] ==> 5
이므로 답은 16이 된다.
이를 일반화시키면,
ans += max(b[m-i-1] - a[i], b[n-i-1] - a[i]) 가 된다.
|
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 <iostream>
#include <algorithm>
using namespace std;
int main(){
int x, t, n, m;
long long ans;
cin >> t;
while(t--){
cin >> n >> m;
ans=0;
int* a=new int[n];
int* b=new int[m];
for(int i=0; i<n; i++) cin >> a[i];
for(int j=0; j<m; j++) cin >> b[j];
sort(a, a+n);
sort(b, b+m);
for(int i=0; i<n; i++){
ans+=max(abs(b[m-i-1]-a[i]), abs(b[n-i-1]-a[i]));
}
delete[] a;
delete[] b;
cout << ans << "\n";
}
}
|
cs |