有關於 ACM 的題目 (DEV C ) 緊急!

Question

一個人沿著一數線前進。他每次走的長度（整數）必須是正的，而且比上一步走的長度多1，一樣，或少1。另外請注意：第一步及最後一步的長度一定是1.

請問這個人若要從x走到y，最少需要走幾步。

舉例說明：若x=45, y=50，那麼每步走的長度可以是：1,2,1,1，所以最少需要4步。

Input

輸入的第一列有一個正整數代表以下有幾組測試資料。每組測試資料一列，含有2個整數x,y（0 <= x <= y < 231）。
Output

每組測試資料輸出一列，最少需要走幾步才能從x走到y。
Sample Input

3
45 48
45 49
45 50
Sample Output

3
3
4





是用DEV C 的MS-DOS類型製作.....

Answer 1

本程式印出 從 0 到 d 最少步數的實際走法
以及最少的總步數
其他讀檔案資料部分請自行加入
/* suggested test range d:182 ~ 209 */
#include
#include
void print_step(int , int , int , int );
main()
{
int i, j, k, d, n, top, extra;
printf("Enter distance (2 < d) : ");
scanf("%d", &d);
if (d < 3) return;
printf(" From 0 to %d:\n", d);
n=0;
for(i=1; i <= d/2; i++)
if ((n+2*i) > d) break;
else n += 2*i;
top = i - 1;
extra = d - n;
if (extra == 0)
print_step(top, 0, 0, 0);
else if ((extra >= 2*top-2))
{
if (extra < top+2)
print_step(top, 1, 1, extra-top);
else if (extra % 2 == 0)
print_step(top, 2, 2, extra/2-top);
else
print_step(top, 2, 1, (extra/2 }
else if (extra > top+1)
{
j = extra % 2;
j = sqrt(8*top - 4*(extra-j) - 7)/2 - 0.5;
k = j*j + 3*j + extra - 2*top;
if (k == -1)
print_step(top-j, 2*j+2, 1, k);
else
print_step(top-j, 2*j+2, k, 1);
}
else if (extra > top-2)
print_step(top, 1, 1, extra-top);
else
{
j = sqrt(top-extra-1);
k = j*j + 2*j + extra - top;
if (k == -1)
print_step(top-j, 2*j+1, 1, k);
else
print_step(top-j, 2*j+1, k, 1);
}
return;
}
/* 印出實際的走法 */
void print_step(int top, int cnt, int exc, int flag)
{
int i, j;
for (i = 1, j = 0; i <= top; i++)
{
printf("%4d", i);
if (++j % 10 == 0) printf("\n");
}
for (i = 1; i <= exc; i++)
{
printf("%4d", top+flag);
if (++j % 10 == 0) printf("\n");
}
for (i = 1; i <= cnt-exc; i++)
{
printf("%4d", top);
if (++j % 10 == 0) printf("\n");
}
for (i = top; i >= 1; i--)
{
printf("%4d", i);
if (++j % 10 == 0) printf("\n");
}
printf("\nTotal %d steps\n\n", j);
}
如果有問題, 請來函討論. 不然, 我可能會錯失你再補充的疑點.

Answer 2

//想法...以下數字代表第幾步!
ACM 846 Steps
1
1
2
1
2 4
3
1
2 4
3 6
5
1
2 4
3 6 9
5 8
7
1
2 4
3 6 9
5 8 12 (第12步最少需要6步為1,1,2,2,3,3 =>重排後為 1,2,3,3,2,1 )
7 11 (第11步最少需要6步為 1,1,2,2,3,2 =>重排後為 1,2,2,3,2,1 )
10 (第10步最少需要6步為 1,1,2,2,3,1 => 重排後為 1,1,2,3,2,1 )
//程式解法
//Accepted 0.156 392 C++ 846 - Steps
#include
int main(){
int x,y,i,d,loop;
scanf("%d",&loop);
while(loop--){
scanf("%d %d",&x,&y);
d=y-x;
if(d==0){
printf("0\n");
continue;
}
for(i=0;0<1;i++){
if(d>=i*i-i&&d<=i*i){
printf("%d\n",2*i-1);
break;
}else if( d>i*i && d<=i*i+i ){
printf("%d\n",2*i);
break;
}
}
}
return 0;
}