結果

問題 No.3 ビットすごろく
コンテスト
ユーザー jj
提出日時 2016-07-23 07:35:52
言語 Fortran
(gFortran 14.2.0)
結果
WA  
実行時間 -
コード長 2,867 bytes
コンパイル時間 205 ms
コンパイル使用メモリ 33,792 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-11-06 14:43:54
合計ジャッジ時間 1,189 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 28 WA * 5
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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)  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
        end if
        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
0