// すべての組み合わせを計算するとO(2^N)となってしまう // 動的計画法を使うことで、計算量がO(10_000*n)になる // 例えば、N=100の場合、 2^100=1267650600228229401496703205376 vs 10_000*100=1_000_000 package main import "fmt" func scan() (N int, W []int) { fmt.Scan(&N) for i := 0; i < N; i++ { var w int fmt.Scan(&w) W = append(W, w) } return } func printMultipleDemSlice(s [][]int) { for i := 0; i < len(s); i++ { if i == 0 { fmt.Print(" ") for j := 0; j < len(s[i]); j++ { fmt.Printf("%v ", j) } fmt.Print("\n") } fmt.Printf("%v ", i) for j := 0; j < len(s[i]); j++ { fmt.Printf("%v ", s[i][j]) } fmt.Print("\n") } fmt.Print("\n") } func main() { N, W := scan() // N, W := 3, []int{1, 2, 3} // N, W := 15, []int{62, 8, 90, 2, 24, 62, 38, 64, 76, 60, 30, 76, 80, 74, 72} var sum int for _, w := range W { sum += w } var expectedWeight int if sum%2 != 0 { // 割り切れない場合は水平にならない fmt.Print("impossible") return } else { expectedWeight = sum / 2 } // dp[i][j]とし、左からi番目までにjという重さが成立するかリストを作る dp := make([][]int, N+1) for i := 0; i < N+1; i++ { dp[i] = make([]int, sum+1) } dp[0][0] = 1 // printMultipleDemSlice(dp) for i, w := range W { for j := 0; j < sum+1; j++ { if dp[i][j] == 1 { dp[i+1][j] = 1 dp[i+1][j+w] = 1 } } // printMultipleDemSlice(dp) } if dp[N][expectedWeight] == 1 { fmt.Print("possible") } else { fmt.Print("impossible") } }