Problem Solving►UVa

UVa 394 - Mapmaker

Contents

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

Problem

題目網址

基本上就是在算記憶體的位置。

Solution

題目有點難讀懂R…

可以跟著公式算，也可以自己推一下算法，基本上就跟算多維矩陣一樣的概念。

C[i]: 第 i 維每單位位移時的 byte 差
C[0] 跟題目公式不同

e.g. [d1,d2,d3]
[x,5,x] - [x,4,x] = C[i] //該維的單位位移量
[x,x,1] - [x,x,0] = element size of data(bytes)

1
2
3
4
5
6
7
8
9
10
11
12
e.g.
TWO 2000 4 3 1 4 0 5 5 10
TWO base = 2000 size = 4 D = 3
D0=(1, 4), D1=(0, 5), D2=(5, 10)
Di = (Di_L, Di_U)
    
C[2] = size = 4
C[1] = C[2] * (10-5+1) = 24
C[0] = C[1] * (5-0+1) = 144

TWO[3, 3, 9] = base + (3-D0_L)*C[0] + (3-D1_L)*C[1] + (9-D2_L)*C[2]
= 2000 + (3-1)*144 + (3-0)*24 + (9-5)*4 = 2376
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
1 14
ONE       1500 2 2 0 3 1 5
ONE       0 1
ONE       0 2
ONE       0 3
ONE       0 4
ONE       0 5
ONE       1 1
ONE       1 2
ONE       1 3
ONE       1 4
ONE       1 5
ONE       2 1
ONE       2 2
ONE       2 3
ONE       2 4

ONE[0, 1] = 1500
ONE[0, 2] = 1502
ONE[0, 3] = 1504
ONE[0, 4] = 1506
ONE[0, 5] = 1508
ONE[1, 1] = 1510
ONE[1, 2] = 1512
ONE[1, 3] = 1514
ONE[1, 4] = 1516
ONE[1, 5] = 1518
ONE[2, 1] = 1520
ONE[2, 2] = 1522
ONE[2, 3] = 1524
ONE[2, 4] = 1526

Code

UVa 394
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <cstdio>
#include <unordered_map>
#include <string>
using std::string;

int main()
{
    struct data
    {
        int base, size, D;
        int L[10], R[10]; //(L[i], R[i]): lower_bound and upper bound

        int C[10];

        data() {}
        data(int _base, int _size, int _D) : base(_base), size(_size), D(_D)
        {
            for (int i = 0; i < D; ++i)
                scanf("%d%d", &L[i], &R[i]);

            C[D - 1] = size; //last dim.
            for (int i = D - 2; i >= 0; --i)
                C[i] = C[i + 1] * (R[i + 1] - L[i + 1] + 1);
        }
    };

    std::unordered_map<string, data> M;

    int N, R;
    char name[15];
    scanf("%d%d", &N, &R);
    for (int i = 0; i < N; ++i)
    {
        int base, size, d;
        getchar();
        scanf("%s%d%d%d", name, &base, &size, &d);
        M[string(name)] = (data){base, size, d};
    }

    for (int i = 0; i < R; ++i)
    {
        getchar();
        scanf("%s", name);
        printf("%s[", name);
        data &d = M[string(name)];

        int addr = d.base, tmp;
        for (int i = 0; i < d.D; ++i)
        {
            scanf("%d", &tmp);
            addr += (tmp - d.L[i]) * d.C[i];

            if (i)
                printf(", %d", tmp);
            else
                printf("%d", tmp);
        }

        printf("] = %d\n", addr);
    }

    return 0;
}