Codeforces Round #454 Div. 2 A

题目:A. Masha and Bears
A family consisting of father bear, mother bear and son bear owns three cars. Father bear can climb into the largest car and he likes it. Also, mother bear can climb into the middle car and she likes it. Moreover, son bear can climb into the smallest car and he likes it. It's known that the largest car is strictly larger than the middle car, and the middle car is strictly larger than the smallest car.
Masha came to test these cars. She could climb into all cars, but she liked only the smallest car.
It's known that a character with size a can climb into some car with size b if and only if a ≤ b, he or she likes it if and only if he can climb into this car and 2a ≥ b.
You are given sizes of bears and Masha. Find out some possible integer non-negative sizes of cars.
Input
You are given four integers V1, V2, V3, Vm(1 ≤ Vi ≤ 100) — sizes of father bear, mother bear, son bear and Masha, respectively. It's guaranteed that V1 > V2 > V3.
Output
Output three integers — sizes of father bear's car, mother bear's car and son bear's car, respectively.
If there are multiple possible solutions, print any.
If there is no solution, print "-1" (without quotes).

样例:
Examples
Input
50 30 10 10
Output
50
30
10
Input
100 50 10 21
Output
-1

提示:
In first test case all conditions for cars' sizes are satisfied.
In second test case there is no answer, because Masha should be able to climb into smallest car (so size of smallest car in not less than 21), but son bear should like it, so maximum possible size of it is 20.

大体意思:这个题的大体意思就是,3个熊都能爬到一辆车中,父亲爬最大的,母亲爬中等的,小熊爬最小的,并且每个熊都喜欢他们所爬的这辆车。a为熊的体积,b为车的体积。而且他们喜欢一辆车的条件是他们能爬上这辆车即b>=a,而且还要满足2a>=b。这样才可以,但是并没有说只喜欢自己爬上的这辆车。masha则是都可以爬上车,但是只喜欢小车。然后依次输入三个熊的体积和masha的体积,看能否有合适的三辆车存在,如果存在则输出,不存在则输出-1;

思路:当时做的时候先分析了这题的类型,这题为是非问题,所以判断条件的寻找就显得非常重要,这里当初先把三只熊的三辆车的范围通过数学中数轴画出来,然后再把masha的车的范围也在数轴上标出,因为masha能够进入所以车,也就是说masha的体积比最小的车还小,但又因为masha还有喜欢小车,所以masha车的范围要和小熊的车的范围有交集才能保证有解,而且题目中还说只能喜欢小车,所以说masha的车的范围与母熊即中等的车有交集,但不可以覆盖,即中等车的范围有比masha的车的最大范围还大的,这样才可以有解;接下来是输出问题,大车只需要满足父熊的范围就可以,所以随便哪个都可以。小车则要满足masha和小熊都可以才行,即小车只要是大于两者之间最大的体积,小于两者之间两倍的最小的就可以。中等车要满足母熊且要保证两倍的masha是小于中等车的体积就可以;

过程中学到的新技巧:就是通过数学数轴的方法,将题目内的数值范围转换在数学中的交集问题;

代码:

include<stdio.h>

int main()
{

   int a,b,c,x,t;
   scanf("%d%d%d%d",&a,&b,&c,&x);
   if(x<b&&x<=2*c&&2*x>=c)
   {
       t=x>c?x:c;
       printf("%d\n",a>(2*b+1)?a:(2*b+1));
       printf("%d\n",b>(t*2+1)?b:(t*2+1));
       printf("%d\n",t);
   }
   else
       printf("-1\n");
   return 0;

}

评论

暂无评论