2015
04-13

# Checkers

Little X, Little Y and Little Z are playing checkers when Little Y is annoyed. So he wants to make the chessboard much bigger. Although Little Z insists the original version, Little X stands by Little Y. After they enlarge the chessboard, the chessboard turns to an infinite line.
The chessboard is like the Number Axes now, with each integer point able to hold a checker. At initial status there are three checkers on three different integer points , and through the game there always are three checkers. Every time, they can choose a checker A to jump across a pivot checker B to a new position(but the distance between old A and B equals to new A and B, and there should be no other checkers except B in the range [old A, new A]).
After playing for a while, they wonder whether an given status a,b,c can be transferred to x,y,z. obeying the rules. Since the checkers are considered the same, it is unnecessary for a must jump to x.

The first line is a,b,c.
The second line is x,y,z.
They are all integers in range (-10^9, 10^9) and the two status are valid.

The first line is a,b,c.
The second line is x,y,z.
They are all integers in range (-10^9, 10^9) and the two status are valid.

1 2 3
0 3 5

YES
2

HintThe middle checker jumps to position 0, and the status is 0 1 3
Then , the middle one jumps to 5. 

LCA + 二分（很好的题目，思维难度和编程技巧兼具的一题，但是写起来又不会太麻烦，好题！）

1.一般很容易想到，可以把一个状态看成一个点，那么状态间的转移就可以看做点间的连边，而且应该是无向边，应该两个状态是可以转化的。但是想到这里还不够，如果能想到这个图其实是个二叉树那么就完美了，而且应该说是一个无限深的二叉树，而且每个节点都有两个儿子，不会只有1个

1.对于第1类状态，即 y – x = z – y，相当于二叉树的根

2.对于第2,3类状态，相当于二叉树的非根节点

3.对于y向两边跳跃并产生的新状态，就看做二叉树的节点向其两个儿子移动

1.首先，我们很容易想到，整个图，可能是不连通的，也就是不止一棵二叉树，如果起始和终点状态不在一个树上，也就是树根状态不同的话，那么它们是不可互达的，就输出NO

2.如果两点在一棵树上，那么它们一定可以使它们互达，输出YES，剩下就是怎么找到LCA

1.怎么判断两点在不在一棵树上，方法很简单，就是找到两个状态的树根，然后看看它们是不是相同的

1 3 9  —-》  3 5 9 —–》 5 7 9  ，回到树根

1 3 10 —–》 3 5 ——》5 7 10 ———-》 7 9 10

7 9 10 ———》7 8 9，回到树根

case 1 ：1 3 9 —-》 3 5 9 ， 实际上是1跳到了5的位置，走了1步，但是我们完全可以看做是1和3同时跳到了3和5，一样是用了1步，

case 2 ：1 3 9 —–》 7 9 10 ， 可以看做是1跳到7,3跳到9，每次跳2格，条了3次，然后再从7 9 10 ——》  7 8 9

（上面的部分，属于编程技巧，避开了讨论，其本身并不影响题目的求解，对于case 2 ， 7 9 10 到 7 8 9也是使用相同的办法）

inline void SORT(State &a)  ：对一个状态a的三个点排序保证 x < y < z

State Root(State &a) ：给定一个状态a，算出它的根状态并返回，另外计算出a的深度，更新在a里面

void updata(State &a ,ll delta) ： 给定一个状态a和向上走的步数delta，求出a向上走了delta步后产生的新状态，返回

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
#define ll __int64

struct State
{
ll x,y,z;
ll dep;
};
State S,T;

inline bool cmp_state(State a , State b)
{
if(a.x == b.x && a.y == b.y && a.z == b.z)
return true;
return false;
}

inline ll Abs(ll x)
{
return x > 0LL ? x : -x;
}

inline void SORT(State &a)
{
if(a.y < a.x) swap(a.x , a.y);
if(a.z < a.x) swap(a.x , a.z);
if(a.y > a.z) swap(a.y , a.z);
}

State Root(State &a)
{
State tmp = a;
tmp.dep = 0;
ll dep = 0;
while(Abs(tmp.x - tmp.y) != Abs(tmp.y - tmp.z))
{
ll len = Abs(tmp.x - tmp.y);
ll __len = Abs(tmp.y- tmp.z);
if(__len > len)
{
ll c = (__len - 1)/ len; //巧妙，避开判断
dep += c;
tmp.y += c * len;
tmp.x += c * len;
}
else
{
ll c = (len - 1) / __len;
dep += c;
tmp.y -= c * __len;
tmp.z -= c * __len;
}
//        printf("%d  %d  %d\n",tmp.x , tmp.y , tmp.z);
}
a.dep = dep;
return tmp;
}

void updata(State &a ,ll delta)
{
ll count = 0;
while(count < delta)
{
ll len = Abs(a.x - a.y);
ll __len = Abs(a.y - a.z);
ll k = Abs(count - delta); //还差多少步
if(len < __len)
{
ll c = (__len - 1) / len; //将要移动多少步
ll Min = min(k , c);
a.x += Min * len;
a.y += Min * len;
count += Min;
if(Min == k) break;
}
else
{
ll c = (len - 1) / __len;
ll Min = min(k , c);
a.y -= Min * __len;
a.z -= Min * __len;
count += Min;
if(Min == k) break;
}
}
a.dep -= delta;
}

ll solve()
{
State tS,tT;
ll low = 0 , high = S.dep;
while(low <= high)
{
ll mid = (low + high) >> 1;
ll delta = S.dep - mid;
tS = S; tT = T;
updata(tS , delta); //SORT(tS);
updata(tT , delta); //SORT(tT);
if(!cmp_state(tS , tT))
high = mid - 1;
else
low = mid + 1;
}
return 2 * (S.dep - high);
}

int main()
{
//while(cin >> S.x >> S.y >> S.z >> T.x >> T.y >> T.z)
while( scanf("%I64d%I64d%I64d",&S.x,&S.y,&S.z) != EOF)
{
scanf("%I64d%I64d%I64d",&T.x,&T.y,&T.z);
S.dep = T.dep = 0;
SORT(S); SORT(T);
State RS = Root(S);
State RT = Root(T);

//        printf("%d  %d  %d  %d\n",RS.x , RS.y , RS.z , RS.dep);
//        printf("%d  %d  %d  %d\n",RT.x , RT.y , RT.z , RT.dep);

if(!cmp_state(RS,RT))
{
//cout << "N0" << endl;
printf("NO\n");
continue;
}
ll tmpr = Abs(S.dep - T.dep); //调整的步数记得记录
if(S.dep > T.dep)
updata(S , S.dep - T.dep);
else
updata(T , T.dep - S.dep);

//        printf("%d  %d  %d  %d\n",S.x , S.y , S.z , S.dep);
//        printf("%d  %d  %d  %d\n",T.x , T.y , T.z , T.dep);

ll res = solve();
//cout << "YES" << endl;
//cout << tmpr + res << endl;
printf("YES\n");
printf("%I64d\n",res + tmpr);
}
return 0;
}

1. 你的理解应该是：即使主持人拿走一个箱子对结果没有影响。这样想，主持人拿走的箱子只是没有影响到你初始选择的那个箱子中有奖品的概率，但是改变了其余两个箱子的概率分布。由 1/3,1/3 变成了 0, 2/3

2. #include <cstdio>
#include <algorithm>

struct LWPair{
int l,w;
};

int main() {
//freopen("input.txt","r",stdin);
const int MAXSIZE=5000, MAXVAL=10000;
LWPair sticks[MAXSIZE];
int store[MAXSIZE];
int ncase, nstick, length,width, tmp, time, i,j;
if(scanf("%d",&ncase)!=1) return -1;
while(ncase– && scanf("%d",&nstick)==1) {
for(i=0;i<nstick;++i) scanf("%d%d",&sticks .l,&sticks .w);
std::sort(sticks,sticks+nstick,[](const LWPair &lhs, const LWPair &rhs) { return lhs.l>rhs.l || lhs.l==rhs.l && lhs.w>rhs.w; });
for(time=-1,i=0;i<nstick;++i) {
tmp=sticks .w;
for(j=time;j>=0 && store >=tmp;–j) ; // search from right to left
if(j==time) { store[++time]=tmp; }
else { store[j+1]=tmp; }
}
printf("%dn",time+1);
}
return 0;
}

3. I go through some of your put up and I uncovered a good deal of expertise from it. Many thanks for posting this sort of exciting posts