# almost beta-ishoku of # https://yukicoder.me/submissions/374293 by nadare $N=<>; @DP = (999)x($N+1); $DP[0] = 0; $r=int sqrt$N; for$i(0..$N-$r*$r){ for$j(1..sqrt$N-$i){ $f=$j*$j; $DP[$i+$f]=$DP[$i]+$j if $DP[$i+$f]>$DP[$i]+$j; } } for(0,1){ $DP[$N]=$DP[$N-$r*$r]+$r if $DP[$N]>$DP[$N-$r*$r]+$r; --$r; } $x = $N; $j=1; while($x){ $f=$j*$j; if($DP[$x] == $DP[$x-$f] + $j){ $y=$j; if($j%2){ print"01"x($j/2),0; }else{ push@E,$j; } $x -= $f; }else{ ++$j; } } while($e=pop@E){ print"01"x($e/2); if($e=shift@E){ print"10"x($e/2); } }