Problem Links:
uva00846,Problem:
Steps
One steps through integer points of the straight line. The length of
a step must be nonnegative and can be by one bigger than, equal to, or
by one smaller than the length of the previous step.
Steps |
What is the minimum number of steps in order to get from x to y? The length of the first and the last step must be 1.
Input and Output
Input consists of a line containing n, the number of test cases. For each test case, a line follows with two integers: 0

Sample Input
3 45 48 45 49 45 50
Sample Output
3 3 4
Miguel Revilla 2002-06-15
Solution:
Source Code:
//Wed Mar 30 15:42:25 CDT 2011#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
using namespace std;
int solve(int x, int y)
{
if (y - x == 0) return 0;
int k = sqrt(1.0 * (y - x));
if (k * k == y - x) // odd steps;
{
return 2 * k - 1;
}
else if ((1 + k) * k < y - x) //even steps + one more, which is less then k.
{
return 2 * k + 1;
}
else //even steps;
return 2 * k;
}
int main(int argc, char* argv[])
{
//freopen("input.in", "r", stdin);
//freopen("output.out", "w", stdout);
int n;
cin >> n;
while (n--)
{
int x, y;
cin >> x >> y;
cout << solve(x, y) << endl;
}
//fclose(stdin);
//fclose(stdout);
return 0;
}
No comments :
Post a Comment