メモ

自分に向けて書いたメモを取り扱っています.

SRM 550 EasyConversionMachine

問題概要

サンプルセット見れば分かる.
kが与えられる.k回文字列oから1文字変化させることができる.k回でその操作を行った時文字列fと等価になれば,"POSSIBLE".
ならなければ"IMPOSSIBLE"

方針

まずoがfと等価になるときの最小限の変化させた数cを求める.
そして, k-cが負になった時は確実にIMPOSSIBLEになる.
また、k-cが偶数の時は同じ操作を2回行うことができるのでPOSSILBE
奇数の時は, 必ず1文字違う文字になるのでIMPOSSIBLE

class EasyConversionMachine
{
    public:
        string isItPossible(string o, string f, int k)
        {
            for(int i = 0; i < o.size(); i++)
            {
                if(o[i] != f[i])
                    k--;
            }

            return (k < 0 ? "IMPOSSIBLE" : (k % 2 == 0 ? "POSSIBLE" : "IMPOSSIBLE"));
        }
};