Educational Codeforces Round 78 (Rated for Div. 2)

1278B - 6

B. A and B  time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output

You are given two integers aa and bb. You can perform a sequence of operations: during the first operation you choose one of these numbers and increase it by 11; during the second operation you choose one of these numbers and increase it by 22, and so on. You choose the number of these operations yourself.

For example, if a=1a=1 and b=3b=3, you can perform the following sequence of three operations:

1. add 11 to aa, then a=2a=2 and b=3b=3;
2. add 22 to bb, then a=2a=2 and b=5b=5;
3. add 33 to aa, then a=5a=5 and b=5b=5.

Calculate the minimum number of operations required to make aa and bb equal.

Input

The first line contains one integer tt (1≤t≤1001≤t≤100) — the number of test cases.

The only line of each test case contains two integers aa and bb (1≤a,b≤1091≤a,b≤109).

Output

For each test case print one integer — the minimum numbers of operations required to make aa and bb equal.

input

3
1 3
11 11
30 20

　　output

3
0
4

　　

Note

First test case considered in the statement.

In the second test case integers aa and bb are already equal, so you don't need to perform any operations.

In the third test case you have to apply the first, the second, the third and the fourth operation to bb (bb turns into 20+1+2+3+4=3020+1+2+3+4=30).

题意：给你两个数a和b，你每次可以选择一个数并给它加上n，操作后n++,重复多次，最后要使a==b,要你求出最少次数n。

刚开始我以为是暴力模拟题，就用自以为对的方式模拟了，居然WA。我就放弃了，赛后居然是打表找规律？！

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
int main(void)
{
	int t;
	ll a,b;
	scanf("%d",&t);
	//printf("%lld\n",ss);
	while(t--)
	{
		scanf("%lld %lld",&a,&b);
		//直接模拟
		ll n=0ll;
		ll sn=0;
		while(a!=b)
		{
			n++;//操作 
			if(a>b)
			swap(a,b);//a小b大
			sn=b-a;
			//差==n 
			if(n<=sn)
			a+=n;
			else
			b+=n;
			
		}
		//printf("a:%d b:%d\n",a,b);
		printf("%lld\n",n);
	}
	return 0;
}

　　我发现比如，输入a=1 b=15时，输出为12，即当a+36=47,b+32=47。正确答案应为7,即a+21=22,b+7=22。故错误。

至于为什么会错，我还不知道。

下面是打表找规律的，不是我找的，还不太懂

AC代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
ll sum[1000000+5];
int main(void)
{
	int t;
	ll a,b;
	scanf("%d",&t);
	for(int i=1;i<=1000000;i++)
	sum[i]=sum[i-1]+i;
	while(t--)
	{
		scanf("%lld %lld",&a,&b);
		ll n=0ll;
		ll sn=0;
		if(a!=b)
		for(int i=1;i<=1000000;i++){
			sn=abs(a-b);
			if(sum[i]>=sn&&(sum[i]-sn)%2==0)
			{
				n=i;
				break;
			}
		}
		printf("%lld\n",n);
	}
	return 0;
}