ARC050-B 花束

■■■問題■■■

高橋君は赤い花をR本、青い花をB本持っています。
高橋君は次の2種類の花束を作ることができます。

●x本の赤い花と1本の青い花からなる花束
●1本の赤い花とy本の青い花からなる花束

高橋君が作ることのできる花束の個数の最大値を求めてください。
すべての花を使い切る必要はありません。

■■■入力■■■

R B
x y

●1 <= R，B <= 10の18乗
●2 <= x，y <= 10億

■■■出力■■■

高橋君が作ることのできる花束の個数の最大値を出力せよ。

C#のソース

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static string InputPattern = "Input1";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("5 5");
            WillReturn.Add("3 4");
            //2
            //「3本の赤い花と1本の青い花からなる花束」を1個と、
            //「1本の赤い花と4本の青い花からなる花束」を1個作ればよいです。
            //このとき、赤い花が1本余ります。
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("10 20");
            WillReturn.Add("2 2");
            //10
            //「1本の赤い花と2本の青い花からなる花束」を10個作ればよいです
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("1 1");
            WillReturn.Add("2 2");
            //0
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("10000000000 10000000000");
            WillReturn.Add("4 3");
            //4545454545
            //入力値および出力値は32bit整数型に収まらない場合があります
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static long mR;
    static long mB;
    static long mX;
    static long mY;

    static void Main()
    {
        List<string> InputList = GetInputList();

        long[] wkArr = { };
        Action<string> SplitAct = pStr =>
            wkArr = pStr.Split(' ').Select(A => long.Parse(A)).ToArray();

        SplitAct(InputList[0]);
        mR = wkArr[0]; mB = wkArr[1];

        SplitAct(InputList[1]);
        mX = wkArr[0]; mY = wkArr[1];

        Console.WriteLine(ExecNibunHou());
    }

    //2分法で最大で何個の花束を作れるかを調べる
    static long ExecNibunHou()
    {
        long L = 0;
        long R = Math.Min(mR, mB) + 1;

        while (L + 1 < R) {
            long Mid = (L + R) / 2;

            bool CanCreate = DeriveCanCreate(Mid);
            if (CanCreate) L = Mid;
            else R = Mid;
        }
        return L;
    }

    //K個の花束を作れるかを返す
    static bool DeriveCanCreate(long pK)
    {
        long RestR = mR, RestB = mB;

        //両方の花束で共通使用する赤1本と青1本を、先に分配する
        RestR -= pK;
        RestB -= pK;

        long CanCreateCnt = 0;

        //残った赤色のバラで作れる花束
        CanCreateCnt += RestR / (mX - 1);

        //残った青色のバラで作れる花束
        CanCreateCnt += RestB / (mY - 1);

        return pK <= CanCreateCnt;
    }
}

解説

K個の花束が作成可能かの判定は、
両方の花束で共通使用する赤1本と青1本を、先に分配すれば、
貪欲法を使うことができます。

類題

ABC063-D Widespread