[Codeforces] Educational Codeforces Round 153 (Rated for Div. 2 (A~C)

 

https://codeforces.com/contest/1860

Dashboard - Educational Codeforces Round 153 (Rated for Div. 2) - Codeforces

버추얼로 참가했습니다

 

A.

#include <bits/stdc++.h>
using namespace std;
#define fastio cin.tie(0)->sync_with_stdio(0)
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
void solve() {
    string str; cin >> str;
    int n = str.size();
    
    if(str == "()") cout << "NO" << '\n';
    else {
        cout << "YES" << '\n';
        string t1 = "", t2 = "";
        for(int i = 0; i < n; i++) {
            if(i % 2 == 0) {
                t1 += '('; t2 += ')';
            } else {
                t1 += ')'; t2 += '(';
            }
        }
        
        if(str == t1 || str == t2) {
            cout << string(n, '(') + string(n, ')') << '\n';
        } else {
            for(int i = 0; i < 2 * n; i++) {
                if(i % 2 == 0) cout << '(';
                else cout << ')';
            }
            cout << '\n';
        }

    }
}
int main() {
    fastio;
    int tc; cin >> tc;
    while(tc--) {
        solve();
    }
    return 0;
}

 

주어진 괄호 문자열이 ()()...,  )()(... 꼴인 경우 ((((())))) 식으로 정답을 만들 수 있고

그렇지 않은 경우엔 ()()()().. 식으로 정답을 만들 수 있다.

 

입력이 ()인 경우에 ()(), (()) 모두 ()를 포함하기 때문에 정답이 없게되어 예외처리를 해주었다.

 

 

 

B.

#include <bits/stdc++.h>
using namespace std;
#define fastio cin.tie(0)->sync_with_stdio(0)
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
void solve() {
    int m, k, a, b;
    cin >> m >> k >> a >> b;
    
    int ans = m;

    int km = max(0, m - min(m / k, b) * k);
    ans = min(ans, km / k + km % k);
    
    km = max(0, km - a);
    ans = min(ans, km / k + km % k);

    if(a >= m % k) {
        a -= m % k;
        m -= m % k; // -> m % k == 0
        km = max(0, m - min(m / k, b) * k);
        ans = min(ans, max(0, (km - (a / k) * k)) / k);
    }
    
    cout << ans << '\n';
}
int main() {
    fastio;
    int tc; cin >> tc;
    while(tc--) {
        solve();
    }
    return 0;
}

 

regular coin은 입력에서 주어지는 코인이고, fancy coin은 무제한으로 사용할 수 있는 코인이다.

코인종류는 1, k가 있다. k는 입력에서 주어진다.

fancy coin을 최대한 적게 사용해서 m을 만들면 된다.

 

정답은 최대 m인데, regular coin은 쓰지 않고 1 fancy coin만 사용했을때의 결과값이다.

 

정답을 구할 수 있는 경우의 수가 여러가지 있다.

 

1 . k regular coin을 다 쓰고 나머지를 k facny coin과  1 fancy coin으로 나눈 값,

2. k regular coin을 다 쓰고 나머지에서 1 regular coin을 빼고 k fancy coin과 1 fancy coin으로 나눈 값,

3. 1 regular coin을 사용해서 m을 k의 배수로 만들 수 있을 때, m을 k의 배수로 만들고 k reagular coin을 다 쓰고 나머지를 1 regular coin으로 k개씩 쓰고 k fancy coin으로만 나눈 값.

 

정답을 최대로 두고 위 값들과 비교하며 최소값을 찾을 수 있다.

 

 

 

C.

#include <bits/stdc++.h>
using namespace std;
#define fastio cin.tie(0)->sync_with_stdio(0)
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
void solve() {
    int n; cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; i++) {
        cin >> a[i];
    }

    vector<int> pos;
    int ans = 0;
    for(int i = 0; i < n; i++) {
        auto it = lower_bound(pos.begin(), pos.end(), a[i]);
        if(it == pos.end()) {
            pos.push_back(a[i]);
            if(pos.size() == 2) ans++;
        } else {
            if(pos.size() >= 2 && it == pos.begin() + 1) ans++;
            *it = a[i];
        }
    }
    cout << ans << '\n';
}
int main() {
    fastio;
    int tc; cin >> tc;
    while(tc--) {
        solve();
    }

    return 0;
}

 

특정 인덱스를 마지막으로 하는 증가하는 부분수열을 찾을 떄, 최대 위치가 두번째일 때만 럭키하다.

 

2 1 5 3 4

{2}

2 -> 불가능

{1}

1 -> 불가능

{2, 5}, {1, 5}

5 -> 가능

{2, 3}, {1, 3}

3 -> 가능

{2, 4}, {1, 4}, {2, 3, 4}, {1, 3, 4}

4->불가능

 

예를들어 4일 때 Alice가 4를 고르고 Bob이 3을 고르면 bob이 이긴다

 

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
  ios::sync_with_stdio(false); cin.tie(0);
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    int ans = 0;
    int mn = n + 1, mnWin = n + 1;
    while (n--) {
      int x;
      cin >> x;
      if (mn < x && x < mnWin) {
      	ans += 1;
      	mnWin = x;
      }
      mn = min(mn, x);
    }
    cout << ans << '\n';
  }
}

에디토리얼 보니까 이게 더 나은듯