Problem Solving►UVa

UVa 11384 - Help is needed for Dexter

Contents

  1. 1. Problem
  2. 2. Solution
  3. 3. Code

Problem

題目網址
中文網址

注意:給 N ，表示 1~N。

Solution

直接舉例:(右邊為步驟數)

1 : 1
1 2 : 2
1 2 3 : 2

可以找出規律

1 2 3 4 => 1 2 1 2

讓右邊成為跟左邊一樣的，所以也就是兩個 1 2，1 則為此次使左右兩邊相同。而 1 2 所要完成的步驟，則是兩個 1。
dp[n/2] + 1
可以用遞迴或 DP 去解，但速度較慢。

其中這裡可以發現每次步驟增加都是在 $2^i$ 時，所以我們可以找出 n 是在哪個區間，以求出它的步驟數。 

1 => 1
2 => 2
3 => 2
4 => 3
5 => 3
6 => 3
7 => 3
8 => 4
...

以下提供 3 種作法。

Code

建好區間直接查找

UVa 11384UVa 11384 - Help is needed for Dexter
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<cstdio>

int main()
{
    int dp[30];
    int n = 0, i;
    for (i = 1; i <= 1000000000; i <<= 1)
        dp[n++] = i;

    while (scanf("%d", &n) != EOF)
    {
        for (i = 0; i<30; i++)
            if (dp[i] > n)
                break;

        printf("%d\n", i);
    }

    return 0;
}

每次都乘以二，找出 n 的所在區間

UVa 11384UVa 11384 - Help is needed for Dexter
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<cstdio>

int main()
{
    int n;
    while (scanf("%d", &n) != EOF)
    {
        int ans = 0;
        for (int i = 1; i <= n; i <<= 1,ans++);
        printf("%d\n", ans);
    }

    return 0;
}

DP

UVa 11384UVa 11384 - Help is needed for Dexter
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<cstdio>
#define N (1000000000>>2)

int dp[N + 1];
int main()
{
    for (int i = 1; i <= N; i++)
        dp[i] = dp[i >> 1] + 1;

    int n;
    while (scanf("%d", &n) != EOF)
    {
        if (n <= N)
            printf("%d\n", dp[n]);
        else if (n <= N << 1)
            printf("%d\n", dp[n >> 1] + 1);
        else
            printf("%d\n", dp[n >> 2] + 2);
    }

    return 0;
}