Codeforces 626C Block Towers(二分)

C. Block Towers

time limit per test:2 seconds

memory limit per test:256 megabytes

input:standard input

output:standard output

Students in a class are making towers of blocks. Each student makes a (non-zero) tower by stacking pieces lengthwise on top of each other. n of the students use pieces made of two blocks and m of the students use pieces made of three blocks.

The students don’t want to use too many blocks, but they also want to be unique, so no two students’ towers may contain the same number of blocks. Find the minimum height necessary for the tallest of the students' towers.

Input

The first line of the input contains two space-separated integers n and m (0 ≤ n, m ≤ 1 000 000, n + m > 0) — the number of students using two-block pieces and the number of students using three-block pieces, respectively.

Output

Print a single integer, denoting the minimum possible height of the tallest tower.

Examples

Input

1 3

Output

9

Input

3 2

Output

8

Input

5 0

Output

10

Note

In the first case, the student using two-block pieces can make a tower of height 4, and the students using three-block pieces can make towers of height 3, 6, and 9 blocks. The tallest tower has a height of 9 blocks.

In the second case, the students can make towers of heights 2, 4, and 8 with two-block pieces and towers of heights 3 and 6 with three-block pieces, for a maximum height of 8 blocks.

题目链接：http://codeforces.com/contest/626/problem/C

分析：

题意：

你需要找n个2的倍数，m个3的倍数，要求所有数都不一样

你的目的是使得其中最大的数最小，然后问你这个数是多少呢？

(0 ≤ n, m ≤ 1 000 000, n + m > 0)

那么我们怎么做呢？

我们首先第一步，认识到这个答案是具有单调性的！

如果T这个值是符合答案的，那么存在To>T,To显然也是符合答案的。

因为To范围内的数显然比T多，而且To完全可以和T选取一模一样的数出来。

反之，如果T是不符合答案的，如果To<T，显然To也是不符合答案的。

然后我们就可以开始二分答案咯。

我们把问题转换为，给你T，问你T范围内，是否能够分离出n个2的倍数，和m个3的倍数，并且这些数都是不一样的呢？

我们可以知道，T范围内，是2的倍数的数有T/2个，是3的倍数的有T/3个，即是2又是3的倍数的数，有T/6个，那么只要(max(0,n-(T/2-T/6))+max(m-(T/3-T/6),0))<=T/6就好了！

我们就二分答案，不断check就好了。

我们首先找到答案的下界，l = 0，以及答案的上界r = 3*1000000。

然后我们不断check((l+r)/2)，如果(l+r)/2是符合答案的，那么根据单调性，显然[(l+r)/2,+∞)这个范围，都是符合答案的，那么我们令r = mid。如果(l+r)/2不符合答案，同理，根据单调性，(-∞,(l+r)/2]都是不符合答案的，我们就令l=mid。

然后这样不断的进行check，直到l > r的时候，这样我们就能找到那个不符合和符合的分界线了~

这条分界线，显然就是答案咯。

喵，每一次check的时候，时间复杂度是O(1)，我最多check logn次，所以二分的总时间复杂度是O(logn)的，完全可以接受。

附上小图：（丑图一张）

下面给出AC代码：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int n,m;
 4 bool check(int x)
 5 {
 6     int num1=x/2;
 7     int num2=x/3;
 8     int num3=x/6;
 9     if(num1<n)
10         return false;
11     if(num2<m)
12         return false;
13     if(min(num3,num1-n)<m-(num2-num3))
14         return false;
15     return true;
16 }
17 int main()
18 {
19     scanf("%d%d",&n,&m);
20     int l=0,r=1e7,ans=0;
21     while(l<=r)
22     {
23         int mid=(l+r)/2;
24         if(check(mid))
25         {
26             ans=mid;
27             r=mid-1;
28         }
29         else l=mid+1;
30     }
31     cout<<ans<<endl;
32     return 0;
33 }