본문 바로가기
알고리즘/Codeforces

Educational Codeforces Round 98 (Rated for Div. 2) ACD

by 유시은 2020. 11. 20.
import sys
input = sys.stdin.readline
 
for TEST in range(int(input())):
    n, m = map(int, input().split())
    p, q = min(n, m), max(n, m)
    q -= p
    print(n+m+max(0, q-1))

 

A - Robot Program

 

로봇이 멈추지 않고 최선의 방법으로 가는 방법은 긴 쪽으로 두 칸, 짧은 쪽으로 한 칸 움직이는 것이다.

 

따라서 위와 같은 방법으로 최대한 멀리 간 다음 두 칸 움직이고 한 칸 쉬는 것이 최선(중 하나)이다.

 

 

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
 
int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int TEST; cin >> TEST; while (TEST--) {
		string s; cin >> s;
		int aopen = 0, bopen = 0, res = 0;
		for (char c : s) {
			if (c == '(') aopen++;
			if (c == '[') bopen++;
			if (c == ')') {
				if (aopen) {
					aopen--;
					res += 1;
				}
			}
			if (c == ']') {
				if (bopen) {
					bopen--;
					res += 1;
				}
			}
		}
		cout << res << "\n";
	}
}

 

C - Two Brackets

 

그냥 괄호 쌍이 최대 몇 개 맞는지 셌다.

 

이게 왜 C번인지, 틀렸다면 왜 이런 코드가 통과되게 했는지 궁금하다.

 

 

#include <bits/stdc++.h> 
using namespace std;
typedef long long ll;
const ll MOD = 998244353;
 
ll fibo[200001];
 
ll magic(ll p, ll q) {
    long long ex;
    ex = MOD - 2;
 
    while (ex) {
        if (ex & 1) {
            p = (p * q) % MOD;
        }
        q = (q * q) % MOD;
        ex /= 2;
    }
    return p;
}
ll fastpow(int a, int b, int c) {
    long long ret = 1;
    while (b) {
        if (b % 2) (ret *= a) %= c;
        a = (ll)a * a % c;
        b /= 2;
    }
    return ret;
}
 
int main() {
    fibo[0] = 0;
    fibo[1] = 1;
    for (int i = 2; i <= 200000; ++i) {
        fibo[i] = (fibo[i - 1] + fibo[i - 2]) % MOD;
    }
    int n; cin >> n;
 
    cout << magic(fibo[n], fastpow(2, n, MOD));
    return 0;
}

 

D - Radio Towers

 

예제만 보고 유추해서 풀어서 잘 모르겠다.

태그

,

댓글0