結果

問題 No.3 ビットすごろく
ユーザー jjjj
提出日時 2016-07-23 07:38:23
言語 Fortran
(gFortran 13.2.0)
結果
WA  
実行時間 -
コード長 2,938 bytes
コンパイル時間 223 ms
コンパイル使用メモリ 34,048 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-11-06 14:43:56
合計ジャッジ時間 1,190 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 1 ms
5,248 KB
testcase_03 AC 1 ms
5,248 KB
testcase_04 AC 1 ms
5,248 KB
testcase_05 AC 1 ms
5,248 KB
testcase_06 AC 1 ms
5,248 KB
testcase_07 AC 1 ms
5,248 KB
testcase_08 AC 1 ms
5,248 KB
testcase_09 AC 2 ms
5,248 KB
testcase_10 AC 2 ms
5,248 KB
testcase_11 AC 2 ms
5,248 KB
testcase_12 AC 2 ms
5,248 KB
testcase_13 AC 2 ms
5,248 KB
testcase_14 AC 1 ms
5,248 KB
testcase_15 AC 1 ms
5,248 KB
testcase_16 AC 2 ms
5,248 KB
testcase_17 AC 1 ms
5,248 KB
testcase_18 AC 1 ms
5,248 KB
testcase_19 AC 2 ms
5,248 KB
testcase_20 AC 2 ms
5,248 KB
testcase_21 WA -
testcase_22 AC 1 ms
5,248 KB
testcase_23 AC 1 ms
5,248 KB
testcase_24 AC 2 ms
5,248 KB
testcase_25 AC 1 ms
5,248 KB
testcase_26 WA -
testcase_27 AC 1 ms
5,248 KB
testcase_28 AC 2 ms
5,248 KB
testcase_29 AC 1 ms
5,248 KB
testcase_30 AC 1 ms
5,248 KB
testcase_31 AC 1 ms
5,248 KB
testcase_32 AC 1 ms
5,248 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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)
  if (least_step.eq.N) then
     print '(a)',"-1"
  else
     print '(i0)',least_step
  end if
end program main
0