x 배열에서 y배열로 변환 가능여부 문제
할 수 있는 행동으로는 돌을 가져가거나 돌을 옮기는 것이 가능하다.
x배열의 합이 y의 배열보다 크거나 같으면 yes를 출력하면 되는 문제
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i];
c += a[i];
}
for (int i = 0; i < n; i++) {
cin >> b[i];
d += b[i];
}
if (c < d) cout << "No";
else cout << "Yes";
| cs |
B. And
문제는 a배열에서 x를 &연산하여 a 배열에서 서로 다른 두 위치의 수를 같게 만드는데 드는 최소 &연산의 횟수이다. 만들지 못한다면 -1을 출력한다.
there should be at least two distinct indices i ≠ j such that ai = aj
풀이는 a배열에 같은 수가 두 개 이상 존재한다면 0을 출력한다.
&한번으로 같은 수가 된다면 1을 출력한다.
& 두번으로 같은 수가 된다면 2를 출력한다.
나머지는 -1을 출력한다.
&연산은 한번 밖에 못쓰기 때문에 여러번 쓴다고 바뀌지 않는다.
int n, x, a[100005], b[100005],c[100005],d,res;
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> n >> x;
for (int i = 0; i < n; i++) {
cin >> a[i];
c[a[i]]++;
if (c[a[i]] > 1) {
cout << "0";
return 0;
}
}
for (int i = 0; i < n; i++) {
c[a[i]]--;
d = x&a[i];
b[d]++;
if (c[d] == 1) {
cout << "1";
return 0;
}
else if (b[d] > 1) {
res = 2;
}
c[a[i]]++;
}
if (res == 2) cout << res;
else cout << "-1";
return 0;
}
| cs |
수의 범위가 10만이기 때문에 배열 참조가 가능하다.
C. Photo of The Sky
문제는 2*n만큼의 좌표가 주어지는데 x인지 y인지 주어지지 않는다.
모든 x와 y를 적절히 조합하여 만든 좌표를 모두 포함하는 최소의 사각형의 넓이를 구하는 문제이다.
가장 작은 사각형을 구하기 위해 가장 작은 넓이를 구해야 한다.
그렇기 때문에 모든 좌표를 sort하여 순서대로 n개 만큼의 수를 선택하여 넓이를 구하면 된다. 풀어서 설명하자면 정렬된 연속된 n개의 수를 선택하는 것이 한 변의 최소 후보가 될 수 있다. 모든 길이의 경우를 전부 탐색하여 최솟값을 출력한다.
int n, x,p,q;
ll a[200005],res=2e18;
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> n;
for (int i = 0; i < n + n; i++) {
cin >> a[i];
}
sort(a, a + n + n);
p = 1, q = n;
res = (a[n + n - 1] - a[n])*(a[n-1] - a[0]);
while (q < n + n-1&&res!=0) {
ll t= (a[n + n - 1] - a[0])*(a[q] - a[p]);
res = min(t, res);
p++, q++;
}
cout << res;
return 0;
}
| cs |
댓글 없음:
댓글 쓰기