integer function get_reach_num(n) implicit none integer::i, n, reach_num get_reach_num = 0 if (n.eq.1) then get_reach_num = 1 return end if do i=max(1,n-(31-LEADZ(10000))), n if (n.eq.POPCNT(i)+i) then get_reach_num = get_reach_num + 1 end if end do end function get_reach_num module stack integer::top integer,allocatable::contents(:) contains subroutine construct(N) integer::N allocate(contents(N)) top = 0 end subroutine construct end module stack logical function is_empty() use stack is_empty = top.eq.0 end function is_empty integer function pop() use stack pop = contents(top) top = top - 1 end function pop integer function get_size() use stack get_size = top end function get_size subroutine push(n) use stack integer::n top = top + 1 contents(top) = n end subroutine push integer function get_least_step(need_step, temp, N, reach_num) use stack implicit none interface integer function pop() end function pop integer function get_size() end function get_size logical function is_empty() end function is_empty end interface integer,allocatable::need_step(:),temp(:) integer::num,popcount,size,step,reach_num,i,j,N, pos call construct(N) call push(1) need_step(1)=1 do i=1,N size = get_size() do j=1, size temp(j) = pop() end do do j=1, size pos = temp(j) popcount = POPCNT(pos) step = need_step(pos) if(pos+popcount.eq.N .and. reach_num.eq.1) then get_least_step = step+1 return end if if(pos+popcount.le.N) then if (need_step(pos+popcount) .gt. step+1) then need_step(pos+popcount) = step + 1 call push(pos+popcount) end if else if(pos-popcount.gt.1) then if (need_step(pos-popcount) .gt. step+1) then need_step(pos-popcount) = step + 1 call push(pos-popcount) end if end if end do if(is_empty().eqv..true.) then exit end if end do get_least_step = need_step(N) end function get_least_step program main implicit none interface integer function get_reach_num(n) integer::n end function get_reach_num integer function get_least_step(need_step, temp,N, reach_num) integer,allocatable::need_step(:),temp(:) integer::N,reach_num end function get_least_step end interface integer::N, least_step, reach_num integer,allocatable::need_step(:),temp(:) read *,N reach_num = get_reach_num(N) if(reach_num.eq.0) then print '(a)',"-1" return endif allocate(need_step(N)) allocate(temp(N)) need_step=N temp=0 least_step = get_least_step(need_step,temp,N, reach_num) print '(i0)',least_step end program main