A. Minimum Binary Number
처음 문제를 봤을 때 operation을 1번이나 제한적으로 쓸 수 있다고 생각해서 A 부터 엄청 어려운 게 나왔구나 했는데 계속 사용이 가능했다. 보면 나올 수 있는 최소의 값은 0의 개수를 세어주고 그 뒤에 1을 붙이거나, input이 1 0 인 예외를 처리해주면 통과되었다.
#include <iostream>
#include <string>
using namespace std;
char arr[1001];
int main(void) {
int n;
cin >> n;
string s;
cin >> s;
if (n == 1 && s[0] == '0') {
cout << '0' << endl;
return 0;
}
int cnt = 0;
for (int i = 0; i < n; ++i) {
if (s[i] == '0') {
cnt++;
}
}
cout << '1';
for (int i = 0; i < cnt; ++i) {
cout << '0';
}
return 0;
}
B. Lara Croft and the New Game
처음 문제를 봤을 때 x좌표와 y좌표를 k,n,m에 대해서 나타낼 수 있을 걸 알았지만 교육적인 목적에서 직접 경로를 탐색하는 코드를 짜보았다. 무슨 생각인 진 모르겠지만 k가 10^9보다 작다고 생각해서 시간초과는 안 날 것이라 생각했는데 짜놓고 제출하고 시간초과가 나서 생각해보니 최악의 경우 INT32_MAX-1까지 가능했다. 20억번이므로 대략 20초가 걸리므로 당연히 시간초과
그래도 구현한 코드를 올려보면
#include <iostream>
#include <string>
using namespace std;
int c;
int x = 1, y = 1;
bool inturrupt() {
if (x == 1 && y == 2) {
cout << x << ' ' << y << endl;
return 1;
}
if (c == 0) {
cout << x << ' ' << y << endl;
return 1;
}
c--;
return false;
};
void print() {
cout << x << ' ' << y << endl;
}
int main(void) {
int a, b;
cin >> a >> b >> c;
a--;
b--;
//print();
if (inturrupt()) {
return 0;
}
for (int i = 1; i <= a; ++i) {
x++;
if (inturrupt()) {
return 0;
}
//print();
}
for (int i = 1; i <= b; ++i) {
y++;
if (inturrupt()) {
return 0;
}
//print();
}
while (c != 0) {
x--;
if (inturrupt()) {
return 0;
}
//print();
for (int i = 1; i <= b - 1; ++i) {
y--;
if (inturrupt()) {
return 0;
}
// print();
}
x--;
if (inturrupt()) {
return 0;
}
//print();
for (int i = 1; i <= b - 1; ++i) {
y++;
if (inturrupt()) {
return 0;
}
// print();
}
}
return 0;
}
inturrupt 함수는 한번 x나 y를 바꾸는 연산을 한 다음에 실행시켜 줘서 k가 0이 되면 x,y를 출력하고 끝내도록 만들었다. 코드는 엄청 복잡했다.
#include <iostream>
#include <string>
using namespace std;
int c;
int x = 1, y = 1;
int main(void) {
int n, m;
cin >> n >> m >> c;
if (c < n) {
cout << 1 + c << ' ' << 1 << endl;
return 0;
}
if (c < n + m - 1) {
cout << n << ' ' << (c - (n - 1)) + 1 << endl;
return 0;
}
if (n*m - 1 == c) {
cout << 1 << ' ' << 2 << endl;
return 0;
}
c -= (m + n - 2);
int temp = n - 1 - ((c-1) / (m - 1));
int temp2;
if (temp % 2 == 0) {
temp2 = 1 + (c-1) % (m - 1);
}
else {
temp2 = m - 1 - (c-1) % (m - 1);
}
cout << temp << ' ' << temp2 + 1 << endl;
return 0;
}
x와 y를 n,m,k에 대한 식으로 나타내서 짠 코드. 여기서
Note that k doesn't fit into 32-bit integer type!
이런 문구가 있는 걸 간과했다. long long 으로 작성하면 accept를 받을 수 있었다.
C. Nested Segments
뻔한 문제 같은데 도저히 풀 방법이 생각나지 않았다. Contest 가 끝나고 나서 코드를 확인해 보니
좌표를 묶어서 first 크기대로 정렬을 한다. first가 같으면 second가 작은 순으로 정렬한다.
본래 순서의 index를 가지고 있어야 하므로 index배열을 따로 만들고 index배열을 정렬시키면서 정럴시키는 cmp 함수안의 조건은 pair값을 사용한다.
정렬이 끝나면 첫번째 값은 무조건 다음값에 포함되므로 생각하지 않고 second 값만 비교한다.
#include <iostream>
#include <algorithm>
using namespace std;
int u[300001];
pair<int, int> in[300001];
int main(void)
{
int n;
cin >> n;
for (int i = 1; i <= n; ++i) {
u[i] = i;
cin >> in[i].first >> in[i].second;
}
sort(u + 1, u + n + 1, [](int a, int b) {
if (in[a].first != in[b].first) {
return in[a].first < in[b].first;
}
else {
return in[a].second > in[b].second;
}
});
int temp = u[1];
for (int i = 2; i <= n; ++i) {
if (in[temp].second >= in[u[i]].second) {
cout << u[i] << ' ' << temp << endl;
return 0;
}
else {
temp = u[i];
}
}
cout << -1 << ' ' << -1 << endl;
return 0;
}