A Contest dedicated to Renat Mullakhanov (rem)

なんかRenat Mullakhanovさんという人が亡くなったらしいのでそれの追悼コンテストらしい
正直TopCoderとかCodeforcesとかはコンテストの時間が夜中過ぎて出れないので、
夕方からやってるUVaのコンテストに最近出てます。

1時間遅れぐらいで参加して5問といて25位でした。
解いた問題はH,A,J,E,C(解いた順)

H - A Change in Thermal Unit

現在の温度が摂氏、温度の変化量が華氏で与えられるので変化した後の温度を摂氏で答える問題。
やるだけ

#include <iostream>
#include <cstdio>
using namespace std;

double func(int c,int f) {
    double ff = (double)c*9/5 + 32 + f;
    return ((double)ff*5-32*5)/9;
}

int main() {
    int n,c,f,tc;
    cin>>n;

    for(tc = 1; tc <= n; ++tc) {
        cin>>c>>f;
        printf("Case %d: %.2f\n", tc, func(c,f));
    }
}

A - Story of Tomisu Ghost

整数nとtが与えられるので、n!がt個以上末尾に0が続くような最も大きい基数bを求める問題。
b進数でn!の末尾に0が続く個数は、b^kがn!を割り切るような最大のkとなるのでn!%b^t == 0となるような最大のbを求めればいい。
で、これはn!を素因数分解したあとに、素因数の指数がt以上になるようなやつを適当にあつめてくればいいのでそんな感じでやった。

#include <iostream>
#include <cstdio>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;

typedef long long ll;

vector<int> pl;
bool isp[100001] = {};

vector<pair<int,int> > factorize(int n)
{
    vector<pair<int,int> > ret;
    for(int i=0; i<pl.size(); ++i) {
        if(pl[i] > n) break;
        int div = 0;
        ll p = pl[i];
        while(p <= n) {
            div += n/p;
            p *= pl[i];
        }
        ret.push_back(make_pair(pl[i], div));
    }
    return ret;
}

int main()
{
    int t,n,b;
    cin>>t;

    for(int i=4; i<100001; i+=2) isp[i] = true;
    for(int i=3; i*i<100001; i+=2)
        if(!isp[i])
            for(int j=2; i*j<100001; ++j)
                isp[i*j] = true;

    pl.push_back(2);
    for(int i=3; i<100001; i+=2)
        if(!isp[i]) pl.push_back(i);

    for(int tc=1; tc<=t; ++tc) {
        cin>>n>>b;
        printf("Case %d: ", tc);
        vector<pair<int,int> > fact = factorize(n);
        sort(fact.begin(), fact.end());
        reverse(fact.begin(), fact.end());
        vector<int> pp;
        for(int i=0; i<fact.size(); ++i) {
            if(fact[i].second >= b) pp.push_back(i);
        }

        if(pp.empty()) {
            printf("-1\n");
            continue;
        }

        ll ans = 1;
        for(int i=0; i<pp.size(); ++i) {
            for(int j=0; j<(fact[pp[i]].second/b); ++j) {
                ans *= fact[pp[i]].first;
                ans %= 10000019;
            }
        }
        ans %= 10000019;
        printf("%lld\n", ans);
    }
}

J - Save from Radiation

n個の水が入ったボトルと1個の毒水が入ったボトルがあるので、それを何匹かのラットに飲ませてどれが毒水の入ったボトルなのか見分けたい。
ラットの数の最小値を求める問題。
n+1個のものからある1個を区別するので、n+1を2進数で表したときの桁数とかなんかなーと適当に考えたら通った。

#include <iostream>
using namespace std;

typedef long long ll;

int main()
{
    int t;
    ll n;
    cin>>t;
    for(int tc=1; tc<=t; ++tc) {
        cin>>n;
        cout<<"Case "<<tc<<": ";
        if(n == 1) {
            cout<<1<<endl;
            continue;
        }
        ll ans = 1,nt = 1;
        while(nt < n+1) {
            ans++;
            nt *= 2;
        }
        cout<<ans-1<<endl;
    }
}

E - Corrupted Friendship

n人の人がいて、最初0番の人がn枚カードを持っている。
カードを持っている人は手元に1枚のこして残りのn-1枚をまだカードを持っていない友達に渡す。このときカードを渡すことをinviteするという。
カードを渡せる友達がいなければ自分にカードを渡した人に余りを返す。
ということを全員にカードが行き渡るまで繰り返す。
inviteした記録が与えられるので"互いに友達でない"人のペアの数を求める問題。
カードを渡すことを辺とみなすと木になって、ある節点の下についてる部分木どうしは友達関係にないので、それぞれの節点に対して適当に組合せの計算をすればいい。

#include <cstdio>
#include <vector>
#include <set>
#include <cstring>
using namespace std;

typedef long long ll;

vector<int> child[100000];
int csum[100000];

ll func1(int x) {
    if(child[x].empty()) {
        csum[x] = 0;
        return 0;
    }
    ll sum = 0;
    for(int i=0; i<child[x].size(); ++i)
        sum += func1(child[x][i]);

    csum[x] = sum + child[x].size();
    return csum[x];
}

ll func(int x) {
    if(child[x].empty()) return 0;
    if(child[x].size() == 1) return func(child[x][0]);

    ll ans = 0;
    for(int i=0; i<child[x].size(); ++i)
        ans += csum[child[x][i]]+1;

    ll ret = 0;
    for(int i=0; i<child[x].size(); ++i) {
        ans -= csum[child[x][i]]+1;
        ret += (csum[child[x][i]]+1) * ans;
    }

    for(int i=0; i<child[x].size(); ++i) ret += func(child[x][i]);
    return ret;
}

int main()
{
    int t,n,x,y;
    scanf("%d", &t);

    for(int tc=1; tc<=t; ++tc) {
        printf("Case %d: ", tc);
        scanf("%d", &n);

        for(int i=0; i<n; ++i) child[i].clear(), csum[i] = 0;

        for(int i=0; i<n-1; ++i) {
            scanf("%d %d", &x, &y);
            x--,y--;
            child[x].push_back(y);
        }

        func1(0);

//        for(int i=0; i<n; ++i) printf("%d : %d\n", i, csum[i]);
        printf("%d ", n-1);
        printf("%lld\n", func(0));
    }
}

C - Hamming Base

解いてる人は多かったんだけど、問題が読めなくてなかなか分からなかった問題。
N進数M桁の数字がN個与えられるので,任意のペアの各桁が全て違うようにしたい。
許される操作は各桁を1増やすか1減らすか。
操作の最小回数を求める問題。
各桁は独立に考えていいかつ数字がN個与えられるので各桁には0からN-1が1回ずつ現れる。
ので、各桁について0から順にgreedyに埋めていくといいっぽい。

#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;

typedef long long ll;
int ip[2000][10];
int cnt[2000], used[2000];

int main()
{
    int t,n,m;
    scanf("%d", &t);
    for(int tc=1; tc<=t; ++tc) {
        printf("Case %d: ", tc);
        scanf("%d %d", &n, &m);
        for(int i=0; i<n; ++i)
            for(int j=0; j<m; ++j)
                scanf("%d", &ip[i][j]);

        ll ans = 0;
        for(int i=0; i<m; ++i) {
            memset(cnt, 0, sizeof(cnt));
            memset(used, 1, sizeof(used));
            for(int j=0; j<n; ++j) cnt[ip[j][i]]++;
            int ptr = 0,now = 0,uu = 0;
            while(ptr < n) {
                while(cnt[now] == 0) now++;
                while(used[ptr] == 1) ptr++;
                ans += abs(now-ptr);
                uu++;
                if(uu == n) break;
//                printf("%d %d\n", now, ptr);
                used[ptr] = 1;
                cnt[now]--;
            }
        }

        printf("%lld\n", ans);
    }
}