結果

問題 No.688 E869120 and Constructing Array 2
コンテスト
ユーザー tsuchinaga
提出日時 2019-03-16 05:39:19
言語 Go
(1.23.4)
結果
AC  
実行時間 2 ms / 1,000 ms
コード長 996 bytes
コンパイル時間 11,074 ms
コンパイル使用メモリ 225,224 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-01 22:20:59
合計ジャッジ時間 11,882 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 10
権限があれば一括ダウンロードができます

ソースコード

diff # 

package main

import (
	"fmt"
	"math"
	"strings"
)

func main() {
	var k int
	_, _ = fmt.Scan(&k)

	if k == 0 {
		fmt.Println(1)
		fmt.Println("0")
		return
	}

	// 合計が2となる組み合わせは、n1から2個、n0から0～n0個取るだけある
	// n1が増えるたびに組み合わせはn1-1だけ増える。n1が5なら、4 + 3 + 2 + 1の10通り
	// n0の組み合わせは2^n0通り。n0が5なら2^5の32通り
	// n1とn0の合計は30以下でないといけない

	n1, n0 := 2, -1 // 1の数, 0の数
	n1p := 0        // n1を使った組み合わせの数
	for {
		if n1 > 30 {
			break
		}
		n1p += n1 - 1

		if k%n1p == 0 {
			for i := 0; n1+i <= 30; i++ {
				p := n1p * int(math.Pow(2, float64(i)))
				if p == k {
					n0 = i
					break
				}
				if p > k {
					break
				}
			}

			if n0 != -1 {
				break
			}
		}

		n1++
	}

	ans := ""
	ans += strings.Repeat("1 ", n1)
	ans += strings.Repeat("0 ", n0)
	fmt.Println(n1 + n0)
	fmt.Println(strings.Trim(ans, " "))
}
0