A問題
最終カットから1つずつ遡っていく。
package main
import (
"bufio"
"os"
"strings"
"strconv"
"fmt"
)
func main() {
reader:=bufio.NewReader(os.Stdin)
line,_:=reader.ReadString('\n')
T,_:=strconv.Atoi(strings.TrimSpace(line))
for i:=0;i<T;i++ {
line,_=reader.ReadString('\n')
ss := strings.Split(strings.TrimSpace(line), " ")
// M,_:=strconv.Atoi64(ss[0])
C,_:=strconv.Atoi(ss[1])
W,_:=strconv.Atoi64(ss[2])
ans := W
A := make([]int64, C, C)
B := make([]int64, C, C)
for j:=0;j<C;j++ {
line,_=reader.ReadString('\n')
ab := strings.Split(strings.TrimSpace(line), " ")
a,_:=strconv.Atoi64(ab[0])
b,_:=strconv.Atoi64(ab[1])
A[j], B[j] = a, b
}
for j:=C-1;j>=0;j-- {
if ans <= B[j] {
ans = A[j] + ans - 1
} else if ans - B[j] < A[j] {
ans = ans - B[j]
}
}
fmt.Printf("Case #%d: %d\n", i+1, ans)
}
}
B問題
最終日から貪欲法。
sortパッケージを使うときに、
sort.Interfaceに適合するように型を作らないといけないのが
面倒。
package main
import (
"bufio"
"os"
"strings"
"strconv"
"fmt"
"sort"
)
type Coffee struct {
c, t int64
s int
}
type Coffees []Coffee
func (c Coffees) Len() int {
return len(c)
}
func (c Coffees) Less(i, j int) bool {
return c[i].s < c[j].s
}
func (c Coffees) Swap(i, j int) {
c[i], c[j] = c[j], c[i]
}
type Int64Slice []int64
func (p Int64Slice) Len() int { return len(p) }
func (p Int64Slice) Less(i, j int) bool { return p[i] < p[j] }
func (p Int64Slice) Swap(i, j int) { p[i], p[j] = p[j], p[i] }
func main() {
reader:=bufio.NewReader(os.Stdin)
line,_:=reader.ReadString('\n')
T,_:=strconv.Atoi(strings.TrimSpace(line))
for i:=0;i<T;i++ {
line,_=reader.ReadString('\n')
ss := strings.Split(strings.TrimSpace(line), " ")
N,_:=strconv.Atoi(ss[0])
//K,_:=strconv.Atoi64(ss[1])
ans := uint64(0)
coffee := make([]Coffee, N, N)
ts := make([]int64, N+2, N+2)
for j:=0;j<N;j++ {
line,_=reader.ReadString('\n')
s1 := strings.Split(strings.TrimSpace(line), " ")
a1,_:=strconv.Atoi64(s1[0])
a2,_:=strconv.Atoi64(s1[1])
a3,_:=strconv.Atoi(s1[2])
coffee[j] = Coffee{a1,a2,a3}
ts[j] = a2
}
ts[N] = 0
ts[N+1] = 0
sort.Sort(Int64Slice(ts))
sort.Sort(Coffees(coffee))
for j:=N;j>=0;j-- {
t := ts[j+1]-ts[j]
for k:=N-1;k>=0;k-- {
if t == 0 { break }
if coffee[k].t >= ts[j+1] {
n := coffee[k].c
if n > t {
n = t
}
coffee[k].c -= n
t -= n
ans += uint64(n) * uint64(coffee[k].s)
//fmt.Printf("ans:%d t:%d %d n:%d k:%d coffee:%v", ans, ts[j+1], ts[j], n, k, coffee[k])
}
}
}
fmt.Printf("Case #%d: %d\n", i+1, ans)
}
}
C問題
試行錯誤の末。
2^n-1の時は特別なケース。
package main
import (
"bufio"
"os"
"strings"
"strconv"
"fmt"
)
func main() {
reader:=bufio.NewReader(os.Stdin)
line,_:=reader.ReadString('\n')
T,_:=strconv.Atoi(strings.TrimSpace(line))
for i:=0;i<T;i++ {
line,_=reader.ReadString('\n')
N,_:=strconv.Atoui64(strings.TrimSpace(line))
fmt.Printf("Case #%d: %d\n", i+1, keta2(N))
}
}
func keta2(i uint64) int {
ret := 0
b := false
for i != uint64(0) {
if i & 1 == uint64(1) {
if b {
ret++
}
} else {
b = true
}
ret++
i = i >> 1
}
if b { ret-- }
return ret
}
