#1574. 长安三万里
长安三万里
题目背景
安史之乱爆发,神州大地一片狼藉。作为守军,你担负着保卫长安的使命,历史的篇章将由你来书写。
题目描述
你初始有 x 名士兵,叛军有 y 名士兵(题目保证 y > x > y/2)。长安面前仅剩 n 个县城可守,郭子仪的部队需要 m 个月才能到达。
每月你必须选择以下两个行动之一:
·坚守:叛军当月发起进攻,你的士兵数量变为原来的1/3,叛 军数量变为原来的1/2(均向下取整);无县城损失,时间推 进 1 个月。
·撤退:放弃 1 个县城,叛军占领后下个月不会进攻;时间推 进 1 个月。
失败条件(满足任意一条即判定失败)
·可守县城数变为 0;
·你的士兵数 < 叛军士兵数的一半(x < y/2);
·未撑满 m 个月就触发上述任一条件。
胜利条件 ·撑满 m 个月且未触发任何失败条件。
输入格式
一行输入四个正整数:x y n m(分别代表你的初始兵力、叛军初始兵力、可守县城数、郭子仪抵达所需月数)。
输出格式
如果存在某种策略使得你胜利,那么输出YES,否则输出NO。
样例
100 150 3 4
YES
样例解释
以下是一种可行的策略。 第一个月:撤退。 第二个月:由于上个月选择撤退,所以这个月敌人不会进攻,无事发生。 第三个月:坚守,我军剩余50人,敌军剩余75人。 第四个月:撤退。 第五个月:援军到达,你胜利。