Codeforces #200 Div2

A. Magnets

シミュレーション。

#include <iostream>

using namespace std;

int main()
{
    int n, inp, ans = 0;
    bool plus = false;

    cin >> n >> inp;

    if (inp == 10) 
        plus = true;

    for (int i = 0; i < n - 1; i++) {
        cin >> inp;

        if (plus && inp != 10) {
            ans++;
            plus = false;
        }
        else if (!plus && inp != 1) {
            ans++;
            plus = true;
        }
    }

    cout << ans + 1 << endl;

    return 0;
}

B.Simple Molecules
ノード１、２の辺の本数をo1
ノード２、３の辺の本数をo2
ノード３、１の辺の本数をo3
と置くと、次の連立方程式が成り立つ。
・o1 + o3 = a
・o1 + o2 = b
・o2 + o3 = c

式を変形すると、
・2 * o1 = a + b - c
・2 * o2 = -a + b + c
・2 * o3 = a - b + c

#include <iostream>

using namespace std;

int main()
{
    int a, b, c;

    cin >> a >> b >> c;
    
    int o1, o2, o3;
    bool flag = true;

    if ((a + b - c) % 2 == 0 && (a + b - c) / 2 >= 0)
        o1 = (a + b - c) / 2;
    else
        flag = false;

    if ((-a + b + c) % 2 == 0 && (-a + b + c) / 2 >= 0)
        o2 = (-a + b + c) / 2;
    else
        flag = false;

    if ((a - b + c) % 2 == 0 && (a - b + c) / 2 >= 0)
        o3 = (a - b + c) / 2;
    else
        flag = false;


    if (flag) {
        cout << o1 << " " << o2 << " " << o3 << endl;
    }
    else 
        cout << "Impossible" << endl;
    
    return 0;
}

C. Rational Resistance
・直列接続の場合
R = y/x + 1
= (x + y) / x
・並列接続の場合
R = 1 / (y/x + 1)
= y / (x + y)

解説に、Calkin-Wilf treeという木が紹介されていた。
Calkin-Wilf treeとは、
・木の頂点が正の有理数への全単射となっている
・木の根は１
・頂点a/bの子はa/(a+b)と(a+b)/bの二分木
・すべての正の有理数は木の中のひとつの頂点となる

Calkin-Wilf treeの頂点a/bの高さを求める問題。

・a < bの場合
a'/b'の子はa'/(a'+ b')または(a'+ b')/b'なので、
a/bの親はa/(b - a)となる。

・a > bの場合
a/bの親は(a - b)/bとなる。

・aが１の場合
上のa

#include <iostream>

using namespace std;

typedef long long ll;

int main()
{
    ll a, b;
    ll ans = 0;

    cin >> a >> b;

    while (true) {
        if (a == 1) {
            ans += b;
            break;
        }
        if (b == 1) {
            ans += a;
            break;
        }

        if (a < b) {
            ans += (b / a);
            b = b % a;
        }
        else if (a > b) {
            ans += (a / b);
            a = a % b;
        }
    }
    cout << ans << endl;
    
    return 0;
}

D. Alternating Current

糸がからまった時にこのようにやります。
（後で書く）

#include <iostream>
#include <stack>

using namespace std;

int main()
{
    string inp;
    stack<char> st;

    cin >> inp;

    for (int i = 0; i < inp.size(); i++) {
        if (st.empty() || st.top() !=  inp[i])
            st.push(inp[i]);
        else
            st.pop();
    }
    if (st.empty())
        cout << "Yes" << endl;
    else
        cout << "No" << endl;

    return 0;
}