-
Notifications
You must be signed in to change notification settings - Fork 0
/
solution.go
98 lines (89 loc) · 1.79 KB
/
solution.go
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
// A great question, enjoy it a lot.
// Can reduce the question to two small questions:
// 1. How many balls, each column needs to give to its adjacent slots?
// 2. Giving that ^, how to construct the board?
package main
import (
"bufio"
"fmt"
"os"
"strconv"
)
func abs(a int) int {
if a > 0 {
return a
}
return -a
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
func solve(final []int) (int, []string) {
result, sum := []string{}, 0
for _, d := range final {
sum += d
}
if (sum != len(final)) || (final[0] == 0) || (final[len(final)-1] == 0) {
return 0, []string{}
}
transform, extra := make([]int, len(final)), make([]int, len(final))
for i, f := range final {
cap := (extra[i] + 1) - (abs(transform[i]) + f)
if cap > 0 {
transform[i], extra[i+1] = cap, extra[i+1]+cap
}
if cap < 0 {
transform[i+1], extra[i] = cap, extra[i]-cap
}
}
// Borad construction
layer := 1
for _, t := range transform {
layer = max(layer, abs(t)+1)
}
for i := 1; i <= layer; i++ {
line := ""
for _, t := range transform {
if i > abs(t) {
line = line + "."
continue
}
if t > 0 {
line = line + "\\"
continue
}
line = line + "/"
}
result = append(result, line)
}
return layer, result
}
var scanner = bufio.NewScanner(os.Stdin)
func scanNum() int {
scanner.Scan()
num, _ := strconv.Atoi(scanner.Text())
return num
}
func main() {
scanner.Split(bufio.ScanWords)
caseCount := scanNum()
for i := 0; i < caseCount; i++ {
slotCount := scanNum()
final := make([]int, slotCount)
for j := 0; j < slotCount; j++ {
final[j] = scanNum()
}
layer, lines := solve(final)
if layer == 0 {
fmt.Printf("Case #%d: IMPOSSIBLE\n", i+1)
continue
}
fmt.Printf("Case #%d: %d\n", i+1, layer)
for _, l := range lines {
fmt.Println(l)
}
}
}