結果

問題 No.3 ビットすごろく
ユーザー jjjj
提出日時 2016-07-23 08:01:04
言語 Fortran
(gFortran 13.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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 1 ms
5,376 KB
testcase_02 AC 1 ms
5,376 KB
testcase_03 AC 39 ms
5,376 KB
testcase_04 AC 5 ms
5,376 KB
testcase_05 AC 193 ms
5,376 KB
testcase_06 AC 48 ms
5,376 KB
testcase_07 AC 17 ms
5,376 KB
testcase_08 AC 121 ms
5,376 KB
testcase_09 AC 324 ms
5,376 KB
testcase_10 AC 459 ms
5,376 KB
testcase_11 AC 271 ms
5,376 KB
testcase_12 AC 180 ms
5,376 KB
testcase_13 AC 28 ms
5,376 KB
testcase_14 AC 429 ms
5,376 KB
testcase_15 AC 662 ms
5,376 KB
testcase_16 AC 571 ms
5,376 KB
testcase_17 AC 643 ms
5,376 KB
testcase_18 AC 21 ms
5,376 KB
testcase_19 AC 681 ms
5,376 KB
testcase_20 AC 3 ms
5,376 KB
testcase_21 WA -
testcase_22 AC 441 ms
5,376 KB
testcase_23 AC 679 ms
5,376 KB
testcase_24 AC 678 ms
5,376 KB
testcase_25 AC 660 ms
5,376 KB
testcase_26 AC 1 ms
5,376 KB
testcase_27 AC 33 ms
5,376 KB
testcase_28 AC 545 ms
5,376 KB
testcase_29 AC 278 ms
5,376 KB
testcase_30 AC 1 ms
5,376 KB
testcase_31 AC 1 ms
5,376 KB
testcase_32 AC 237 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

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