トップページに戻る
次の競技プログラミングの問題へ
前の競技プログラミングの問題へ
No.149 碁石の移動
■■■問題■■■
中身が見えない袋Aと袋Bがある。
袋Aと袋Bにはそれぞれ碁石が入っている。
袋Aには白い碁石がAw個、黒い碁石がAb個入っている。
袋Bには白い碁石がBw個、黒い碁石がBb個入っている。
最初に袋A個から色を見ずにC個の碁石を取り出し袋Bに移す。
次に、袋Bからまた色を見ずにD個の碁石を取り出し袋Aに移す。
最後に袋Aに入っている白い碁石の数を数えるとき、
可能性としてありうる最多の白い碁石の数はいくつか？
■■■入力■■■
Aw Ab
Bw Bb
C D
0 <= Aw,Ab <= 10万
0 <= Bw,Bb <= 10万
0 <= C <= 20万
0 <= D <= 40万
C,Dはかならず碁石を取れる個数が与えられる。
■■■出力■■■
移動を行った後に、考えられる袋Aの中の最多の白い碁石の数を1行で出力せよ。
最後に改行を忘れずに。
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("2 1");
WillReturn.Add("1 2");
WillReturn.Add("2 3");
//3
//袋Aには白い碁石が2個、黒い碁石が1個入っている。
//袋Bには白い碁石が1個、黒い碁石が2個入っている。
//例えば、袋Aから袋Bに移した2個の碁石が共に白い碁石であり、
//次に、袋Bから袋Aに移した3個の碁石がすべて白い碁石であれば、
//最終的に袋Aには最多で3個の白い碁石がある。
}
else if (InputPattern == "Input2") {
WillReturn.Add("2 0");
WillReturn.Add("0 3");
WillReturn.Add("2 1");
//1
//最初に袋Aから袋Bに移した2個の碁石はかならず白い碁石である。
//次に、袋Bから袋Aに移した1個の碁石が白い碁石であれば、
//最終的に袋Aには最多で1個の白い碁石がある。
}
else if (InputPattern == "Input3") {
WillReturn.Add("3 0");
WillReturn.Add("2 3");
WillReturn.Add("0 5");
//5
//最初に、袋Aから袋Bに0個碁石を移す。(つまり碁石の数は動かない。)
//次に、袋Bから袋Aに移した5個の碁石が白い碁石が2個、黒い碁石が3個であるので、
//最終的に袋Aには最多で5個の白い碁石がある。
}
else if (InputPattern == "Input4") {
WillReturn.Add("43682 82641");
WillReturn.Add("54647 3647");
WillReturn.Add("92674 64591");
//98240
}
else {
string wkStr;
while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
}
return WillReturn;
}
static void Main()
{
List<string> InputList = GetInputList();
int[] wkArr = { };
Action<int> SplitAct = (pIndY) =>
wkArr = InputList[pIndY].Split(' ').Select(X => int.Parse(X)).ToArray();
int ACntWhite, ACntBlack;
int BCntWhite, BCntBlack;
int TakeCntFromA, TakeCntFromB;
SplitAct(0); ACntWhite = wkArr[0]; ACntBlack = wkArr[1];
SplitAct(1); BCntWhite = wkArr[0]; BCntBlack = wkArr[1];
SplitAct(2); TakeCntFromA = wkArr[0]; TakeCntFromB = wkArr[1];
Action DebugPrintAct = () =>
{
Console.WriteLine(new string('■', 20));
Console.WriteLine("袋Aの白={0}、黒={1}。袋Bの白={2}、黒={3}",
ACntWhite, ACntBlack, BCntWhite, BCntBlack);
};
DebugPrintAct();
//Aの袋からBの袋への移動
if (TakeCntFromA <= ACntBlack) {
ACntBlack -= TakeCntFromA;
BCntBlack += TakeCntFromA;
}
else {
int FirstMoveCnt = ACntBlack;
ACntBlack = 0;
BCntBlack += FirstMoveCnt;
int SecondMoveCnt = TakeCntFromA - FirstMoveCnt;
ACntWhite -= SecondMoveCnt;
BCntWhite += SecondMoveCnt;
}
DebugPrintAct();
//Bの袋からAの袋への移動
if (TakeCntFromB <= BCntWhite) {
BCntWhite -= TakeCntFromB;
ACntWhite += TakeCntFromB;
}
else {
int FirstMoveCnt = BCntWhite;
BCntWhite = 0;
ACntWhite += FirstMoveCnt;
int SecondMoveCnt = TakeCntFromB - FirstMoveCnt;
BCntBlack -= SecondMoveCnt;
ACntBlack += SecondMoveCnt;
}
DebugPrintAct();
Console.WriteLine(ACntWhite);
}
}
デバッグ情報付の実行結果
■■■■■■■■■■■■■■■■■■■■
袋Aの白=2、黒=1。袋Bの白=1、黒=2
■■■■■■■■■■■■■■■■■■■■
袋Aの白=1、黒=0。袋Bの白=2、黒=3
■■■■■■■■■■■■■■■■■■■■
袋Aの白=3、黒=1。袋Bの白=0、黒=2
3
解説