import java.lang.Math.sqrt import java.lang.StringBuilder fun main(args: Array) { var n = readLine()!!.toInt() var list = getList(n)!!.sortedWith(Comparator { a, b -> com(a,b) }) var prevChar = '0' val ans = StringBuilder() list!!.forEach { val ret = getWord(prevChar == '0', it) ans.append(ret) prevChar = ret.last() } println(ans.toString()) } fun com(a:Int, b:Int):Int { if(a % 2 == 1) { if(b % 2 == 1) { return a.compareTo(b) } else { return -1 } } else { if(b % 2 == 0) { return b.compareTo(a) } else { return 1 } } } val map = mutableMapOf>() fun getList(num:Int):Array? { if(num == 1) { return arrayOf(1) } if(num == 0) { return arrayOf() } map[num]?.let { return it } val lastIndex = sqrt(num.toDouble()).toInt() val list = mutableListOf>() var len = num var minList = Array(0, {0}) (1..lastIndex).reversed().forEach { val ret = getList(num - it * it) val idx = it ret?.let { if(it.size < len) { val list = mutableListOf(idx) list.addAll(it) len = it.size minList = list.toTypedArray() } } } if(minList.isEmpty()) { return null } map[num] = minList return minList } fun getWord(prevZero:Boolean, num:Int):String { if(prevZero) { return (1..num).map { (it - 1) % 2 }.joinToString("") } else { return (1..num).map { it % 2 }.joinToString("") } }