ntua_compilers/dana/programs/linemarket.dana at 8426feaebe28c652fbd5d240f5d09c0fb65ed0ac · strange-program/ntua_compilers · GitHub

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
(* linemarket.dana
 *
 * Input:
 * 6     <-- stores
 * 3     <-- N (number of intervals)
 * 10    <-- s (start of interval 1)
 * 12    <-- f (end of interval 1)
 * 0     <-- s (start of interval 2)
 * 4     <-- f (end of interval 2)
 * 5     <-- s (start of interval 3)
 * 8     <-- f (end of interval 3)
 *
 * Output:
 * 2
 *)
def main
    var stores size s f N tail is int
    var MAX_STORES MAX_PLACES is int
    var i is int
    var arr is int[32767]

    def swap: x y as ref int
        var t is int
        t := x
        x := y
        y := t

    def bsort: n as int, x as int[]
        var changed is byte
        var i_bsort is int

        loop:
            changed := false
            i_bsort := 0
            loop:
                if i_bsort < n-1:
                    if x[i_bsort] > x[i_bsort+1]:
                        swap: x[i_bsort], x[i_bsort+1]
                        changed := true
                    i_bsort := i_bsort + 1
                else: break
            if not changed: break

    def possible_store is byte: current_arr as int[], mid spaces stores_to_place as int
        var last_position placed_stores i_ps is int
        var j is int
        var position is int
        last_position := -32768
        placed_stores := 0
        i_ps := 0
        loop:
            if i_ps >= (spaces/2): break
            else:
                j := 2*i_ps
                if (last_position + mid) > current_arr[j]: position := last_position + mid
                else: position := current_arr[j]
                loop:
                    if position > current_arr[j + 1]: break
                    else:
                        placed_stores := placed_stores + 1
                        last_position := position
                        position := position + mid
                        if placed_stores >= stores_to_place: return: true
                i_ps := i_ps + 1
        return: false

    def largest_minimum_distance is int: lmd_arr as int[], spaces num_stores as int
        var distance is int
        var result left right is int

        bsort: spaces, lmd_arr
        result := 0
        left := 0
        if spaces > 0 : right := lmd_arr[spaces - 1] - lmd_arr[0]
        else: right := 0


        loop:
            if left > right: break
            else:
                if left > right : distance := left
                else: distance := (left + right) / 2

                if distance <= 0 : distance := 1

                if possible_store(lmd_arr, distance, spaces, num_stores) = true:
                    result := distance
                    left := distance + 1
                else:
                    right := distance - 1
        return: result

    tail := 0
    MAX_STORES := 32767
    MAX_PLACES := 32767

    stores := readInteger()
    N := readInteger()


    if stores > MAX_STORES or stores < 1:
        writeString: "Wrong starting input, let\'s try again!\n"
        stores := readInteger()

    if N > MAX_PLACES or N < 1:
        writeString: "Wrong starting input, let\'s try again!\n"
        N := readInteger()

    i := 0

    loop:
        if i >= N: break
        else:
            s := readInteger()
            f := readInteger()

            arr[i*2] := s
            arr[i*2 + 1] := f
            tail := tail + 2
            i := i + 1

    writeInteger: largest_minimum_distance(arr, tail, stores)
    writeString: "\n"