結果

問題 No.3 ビットすごろく
ユーザー jjjj
提出日時 2016-07-23 08:01:04
言語 Fortran
(gFortran 13.2.0)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 1,862 bytes
コンパイル時間 243 ms
コンパイル使用メモリ 27,700 KB
実行使用メモリ 4,504 KB
最終ジャッジ日時 2023-09-14 00:04:52
合計ジャッジ時間 8,037 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,376 KB
testcase_01 AC 1 ms
4,376 KB
testcase_02 AC 1 ms
4,380 KB
testcase_03 AC 29 ms
4,380 KB
testcase_04 AC 4 ms
4,376 KB
testcase_05 AC 141 ms
4,376 KB
testcase_06 AC 35 ms
4,376 KB
testcase_07 AC 12 ms
4,380 KB
testcase_08 AC 88 ms
4,380 KB
testcase_09 AC 238 ms
4,376 KB
testcase_10 AC 338 ms
4,380 KB
testcase_11 AC 198 ms
4,376 KB
testcase_12 AC 133 ms
4,380 KB
testcase_13 AC 21 ms
4,376 KB
testcase_14 AC 318 ms
4,380 KB
testcase_15 AC 494 ms
4,380 KB
testcase_16 AC 428 ms
4,376 KB
testcase_17 AC 477 ms
4,380 KB
testcase_18 AC 16 ms
4,380 KB
testcase_19 AC 502 ms
4,380 KB
testcase_20 AC 3 ms
4,376 KB
testcase_21 WA -
testcase_22 AC 323 ms
4,380 KB
testcase_23 AC 502 ms
4,380 KB
testcase_24 AC 505 ms
4,376 KB
testcase_25 AC 494 ms
4,380 KB
testcase_26 AC 1 ms
4,376 KB
testcase_27 AC 25 ms
4,376 KB
testcase_28 AC 409 ms
4,380 KB
testcase_29 AC 205 ms
4,376 KB
testcase_30 AC 1 ms
4,380 KB
testcase_31 AC 1 ms
4,380 KB
testcase_32 AC 174 ms
4,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