結果

問題 No.3 ビットすごろく
コンテスト
ユーザー jj
提出日時 2016-07-23 08:01:04
言語 Fortran
(gFortran 14.2.0)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 1,862 bytes
コンパイル時間 1,393 ms
コンパイル使用メモリ 32,896 KB
実行使用メモリ 6,940 KB
最終ジャッジ日時 2024-07-01 08:02:17
合計ジャッジ時間 10,725 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 32 WA * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

! partialy check
logical function is_reachable(n)
  implicit none
  integer::i, n

  if (n.eq.1) then
     is_reachable = .true.
     return
  end if

  do i=max(1,n-(31-LEADZ(10000))), n
     if (n.eq.POPCNT(i)+i) then
        is_reachable = .true.
        return
     end if
  end do
end function is_reachable

integer function get_least_step(need_step, temp, N, reach_num)
  implicit none
  integer,allocatable::need_step(:),temp(:)
  integer::num,pcnt,size,step,reach_num,i,j,N, pos
  logical::is_updated

  need_step(1)=1
  do i=1,N
     is_updated = .false.
     do pos=1,N
        pcnt = POPCNT(pos)
        step = need_step(pos)

        if(pos+pcnt.le.N) then
           need_step(pos+pcnt) = MIN(step+1, need_step(pos+pcnt))
           is_updated = .true.
        end if
        if(pos-pcnt.gt.1) then
           need_step(pos-pcnt) = MIN(step+1, need_step(pos-pcnt))
           is_updated = .true.
        end if
     end do
     if (is_updated.eqv..false.) then
        exit
     endif
  end do

  get_least_step = need_step(N)
end function get_least_step

program main
  implicit none
  interface
     logical function is_reachable(N)
       integer::N
     end function is_reachable
     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

  if(N.eq.1) then
     print '(a)',"1"
     return
  else if(is_reachable(N).eqv..false.) 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)

  if (least_step.eq.N) then
     print '(a)',"-1"
  else
     print '(i0)',least_step
  end if
end program main
0