Codeforces Round #699 (Div.2) A, B

Codeforces Round #699 (Div.2)

---

 A. Space Navigation 

   Problem   

Problem - A - Codeforces

   Code   

#include <iostream>
#include <vector>
#include <string>
 
using namespace std;
 
int tc;
vector<string> ans;
 
int main() {
    cin >> tc;
 
    while (tc--) {
        int px = 0, py = 0;
        string input;
 
        cin >> px >> py;
        cin >> input;
 
        bool up = false;
        bool down = false;
        bool right = false;
        bool left = false;
 
        bool yOk = false;
        bool xOk = false;
 
        if (py >= 0) {
            up = true;
            if (!py) yOk = true;
        }
        else down = true;
 
        if (px >= 0) {
            right = true;
            if (!px) xOk = true;
        }
        else left = true;
 
        int U = 0;
        int D = 0;
        int R = 0;
        int L = 0;
 
        for (int i = 0; i < input.size(); i++) {
            if (up && input[i] == 'U') {
                U++;
                if (U == py) yOk = true;
            }
            else if (down && input[i] == 'D') {
                D--;
                if (D == py) yOk = true;
            }
            else if (right && input[i] == 'R') {
                R++;
                if (R == px) xOk = true;
            }
            else if (left && input[i] == 'L') { // L
                L--;
                if (L == px) xOk = true;
            }
 
            if (xOk && yOk) {
                // x, y 둘 다 가능해짐을 확인이 되면
                ans.push_back("YES");
                break;
            }
            if (i == input.size() - 1)
                // 마지막 이동이지만 아직
                // xOk && yOk 가 만족되지 않을 경우
                ans.push_back("NO");
        }
    }
 
    for (auto elem : ans) cout << elem << '\n';
}

---

B. New Colony

   Problem   

Problem - B - Codeforces

   Code   

#include <iostream>
#include <vector>
 
using namespace std;
 
int tc;
vector<int> ans;
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
    cin >> tc;
 
    while (tc--) {
        int n, k;
        cin >> n >> k;
 
        vector<int> h(n + 1);
 
        for (int i = 1; i <= n; i++) cin >> h[i];
 
        int cur = 1;
 
        for (int i = 1; i <= k; i++) {
            int cur = 1;
 
            if (k >= 9981) {
                ans.push_back(-1);
                break;
            }
 
            while (cur < n && h[cur] >= h[cur + 1])
                cur++; // 돌 계속 굴러감
 
            if (cur == n) {
                ans.push_back(-1);
                break;
            }
            else {h[cur]++;
 
            if (i == k)
                ans.push_back(cur);
        }
    }
 
    for (auto elem : ans) cout << elem << '\n';
}

   Note   

  돌의 개수가 최대 10억개이지만 산의 개수와 높이가 제일 최악의 경우로 1번째 산부터 99번째 산까지 높이가 1, 100번째 산의 높이가 100이어도 boulder는 99*99 인 9,981개가 쓰인다. 즉, k가 9,981 이상인 경우엔 산들의 개수와 모양이 어떠한들 모두 "-1"을 출력할 수 있게 된다. 게다가 시간은 2secs per test 이므로 Brute force 로 풀 수 있다.

최악의 경우