SRM 478 :: DIV2

補完計画実行中

250pt

Taro has prepared delicious kiwi fruit juice. He poured it into N bottles numbered from 0 to N-1. The capacity of the i-th bottle is capacities[i] liters, and he poured bottles[i] liters of kiwi juice into this bottle.
Now he wants to redistribute juice in the bottles. In order to do this, he will perform M operations numbered from 0 to M-1 in the order in which he will perform them. For the i-th operation, he will pour kiwi juice from bottle fromId[i] to bottle toId[i]. He will stop pouring when bottle fromId[i] becomes empty or bottle toId[i] becomes full, whichever happens earlier.
Return an int[] that contains exactly N elements and whose i-th element is the amount of kiwi juice in the i-th bottle after all pouring operations are finished.
俺得英単語memo
prepare 準備する
pour 注ぐ
redistribute 再分配する

struct KiwiJuiceEasy{
    
vector <int> thePouring(vector <int> cap, vector <int> bot,
    vector <int> from, vector <int> to)
    {
        rep(i,from.size()){
            int t = bot[from[i]] + bot[to[i]];
            if( t>=cap[to[i]] ){
                bot[to[i]] = cap[to[i]];
                bot[from[i]] = t-cap[to[i]];
            }
            else{
                bot[to[i]] = t;
                bot[from[i]] = 0;
            }
        }
        return bot;
    
    }
    
};

500pt

Rabbits often feel hungry, so when they go out to eat carrots, they jump as quickly as possible.
Initially, rabbit Hanako stands at position init. From position x, she can jump to either position 4*x+3 or 8*x+7 in a single jump. She can jump at most 100,000 times because she gets tired by jumping.
Carrots are planted at position x if and only if x is divisible by 1,000,000,007 (i.e. carrots are planted at position 0, position 1,000,000,007, position 2,000,000,014, and so on). Return the minimal number of jumps required to reach a carrot. If it's impossible to reach a carrot using at most 100,000 jumps, return -1.
俺得英単語memo
if and only 場合のみ

struct CarrotJumping{
    int theJump(int init){
        set<ll> st;
        queue<ll> q;
        ll mod = 1000000007;
        
        st.insert((ll)init);
        q.push((ll)init);
        for(int i=0; i<100000; i++){
            queue<ll> tmp;
            for(;!q.empty();){
                ll n = q.front();
                ll a = (4*n%mod + 3)%mod;
                ll b = (8*n%mod + 7)%mod;
                if( a%mod==0 || b%mod==0 ) return i+1;
                
                if( st.find(a) == st.end() )st.insert(a),tmp.push(a);
                if( st.find(b) == st.end() )st.insert(b),tmp.push(b);
                
                //printf("%lld %lld\n",a,b);
                q.pop();
            }
            q = tmp;
        }
        
        return -1;
    }
};