ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • Codeforces Round #763 (Div. 2) 풀이
    백준 2022. 7. 6. 02:25

    A. https://codeforces.com/contest/1623/problem/A

     

    Problem - A - Codeforces

     

    codeforces.com

    단순구현입니다. 그냥 훅 돌면서 하면 됩니다.

    https://codeforces.com/contest/1623/problem/B

     

    Problem - B - Codeforces

     

    codeforces.com

    맨  마지막의 Alice's picked range 의 length는 1임이 자명하고,

    맨 처음의 Alice's picked range의 length는 n임이 자명합니다.

    Alice's picked range의 length를  내림차순으로 정렬하면서,

    역순으로 맨 마지막부터 Bob's picked number을 추적해서 하나씩 구해내 리턴합니다.

     

    https://codeforces.com/contest/1623/problem/C

     

    Problem - C - Codeforces

     

    codeforces.com

    이분 탐색으로, 최소  힙의 최대값을 k라고 둡시다.

    역순으로 돌아가면,

    그리디하게 k개만 남기고 나머지는  몽땅 이전거로 넘기는 것이 최선입니다.

    이렇게 역순으로 분배하고 나중에 살펴보았을 때, 모든 힙이 k개 이상의 스톤이 나오면 true를 리턴하도록

    이분탐색을 반복합니다.

     

    https://codeforces.com/contest/1623/problem/D

     

    Problem - D - Codeforces

     

    codeforces.com

    로봇이 청소하는 타이밍은 주기로 구할 수  있습니다. 그 주기는 8은 넘지 않을 것 같아요.

    이제 그 주기를 바탕으로 기하 기대값을 구해야되는데..

    수학을 못해서 뇌정지.

     

    일단 주기까지 구한 코드만 남겨놓기로.

     

    #include <vector>
    #include <cmath>
    #include <algorithm>
    #include <climits>
    #include <set>
    #include <map>
    #include <string>
    #include <queue>
    #include <iostream>
    #include <iomanip>
    #include <unordered_set>
    #include <string>
    
    #include <cmath>
    #include <iostream>
    #include <vector>
    #include <algorithm>
    #include <sstream>
    #include <queue>
    #include <stack>
    #include <bitset>
    
    using namespace std;
    
    using ld = long double;
    using ll = long long;
    using pldld = pair<ld,ld>;
    using edge = pair<ld, pair<ll, ll>>;
    using pll = pair<ll, ll>;
    
    ll gcd(ll a, ll b) {
        if (b==0) {
            return a;
        }
        return gcd(b, a % b);
    }
    
    
    
    int main() {
    
    #ifdef DEBUG
        freopen("../input.txt", "r", stdin);
    #endif
    
    #ifndef DEBUG
        ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    #endif
    
        ll t;
        cin >> t;
        while  (t--)  {
            ll n, m, r_b, c_b, r_d, c_d;
            ll  p;
            cin >> n >> m >> r_b  >> c_b >> r_d >> c_d;
            cin >> p;
            r_b --; c_b--;
            r_d--;
            c_d--;
            ll time = 0;
    
            ll d_x = 1;
            ll d_y = 1;
    
            vector<pair<ll, ll>> locations;
            vector<pair<ll, ll>> dis;
            vector<ll> times;
            ll period;
            ll period_start_index;
            bool is_finihed = true;
            while (is_finihed ) {
                if (r_b == r_d || c_b == c_d) {
                    for (ll i=0; i<locations.size(); i++) {
                        if (locations[i] == make_pair(r_b, c_b) &&
                        dis[i] == make_pair(d_x, d_y))  {
                            period = time - times[i];
                            period_start_index = i;
                            is_finihed = false;
                            break;
                        }
                    }
                    if (!is_finihed) {
                        break;
                    }
                    locations.push_back({r_b, c_b});
                    dis.push_back({d_x, d_y});
                    times.push_back(time);
    
                }
    
                ll next_x = r_b + d_x;
                ll next_y = c_b + d_y;
    
                if (! (0 <= next_x &&next_x < n)) {
                    d_x = - d_x;
                    next_x = r_b + d_x;
                }
                if (! (0 <= next_y && next_y < m)) {
                    d_y = - d_y;
                    next_y = c_b + d_y;
                }
                time++;
                r_b = next_x;
                c_b = next_y;
    //            cout << r_b << ' ' << c_b << '\n';
            }
            cout << period << '\n';
        }
    
        return 0;
    }
Designed by Tistory.