Chipmunk Theo and Equality (CF R 1099 Div.2 - C)

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

---

아이디어

어떤 수 x에 대하여 주어진 연산을 하면서 나타는 수열을 x의 경로라고합시다. 모든 자연수 x에 대하여 경로의 마지막은 1 2 1 2 의 반복입니다.

 

a1와 a2의 경로중 가장 처음으로 겹치는 부분을 생각해봅시다. 그리고 그 겹치는 지점과 a3와의 처음으로 겹치는 지점, 그 겹치는 지점과 a4와 처음으로 겹치는 지점, ... 이런식으로 해주면 마지막에는 어떤 수가 남습니다. 만약 이 수가 1 또는 2라면 1과 2가 모두 후보가 될 수 있습니다. 만약 이 수가 1과 2가 아니라면 그 수가 정답값이 됩니다. 이제 모든 수에서 그 정답값으로 가는데에 걸리는 비용을 모두 더해주면 됩니다.

---

소스코드

#include <iostream>
#include <set>
#define ll long long
using namespace std;

ll arr[101010]={0};

ll Count(ll N,ll now)
{
    ll res=0;
    for (ll i=1;i<=N;i++)
    {
        ll temp=arr[i];

        while (temp!=now)
        {
            res++;
            if (temp%2==1) temp++;
            else temp/=2;
        }
    }
    return res;
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll T;

    cin>>T;
    while (T--)
    {
        ll N,i;

        cin>>N;

        ll now=0;
        for (i=1;i<=N;i++)
        {
            cin>>arr[i];

            if (i==1) now=arr[i];
            else
            {
                set <ll> st;
                ll temp=arr[i];
                while (st.find(temp)==st.end())
                {
                    st.insert(temp);
                    if (temp%2==1) temp++;
                    else temp/=2;
                }

                while (st.find(now)==st.end())
                {
                    if (now%2==1) now++;
                    else now/=2;
                }
            }
        }

        ll res=0;
        if (now>2) res=Count(N,now);
        else res=min(Count(N,1),Count(N,2));

        cout<<res<<"\n";
    }
}