질문
우리는 그들의 우주 정거장에서 로봇 군대에 의해 체포됩니다. 우리의 우주선 조종사는 1 층에있는 감옥에 있습니다. 탈출하는 방법은 단 하나 뿐이며 우주선 조종사를 구출하고 있습니다. 그것은 N 레벨에서 1 레벨로 옮겨가는 것을 의미합니다. 그러나 매우 위험하기 때문에 가능한 한 적은 수의 단계로 감옥에 가야합니다.
정황
-
이동하는 방법에는 4 가지가 있습니다.
- N 레벨에서 N-1 레벨로 이동
e.g. from 12 to 11 - 레벨 N에서 레벨 N + 1로 이동
e.g. from 12 to 13 - 레벨 2k에서 레벨 k까지 텔레포트 사용
e.g. from 12 to 6 - 레벨 3k에서 레벨 k까지 텔레포트 사용
e.g. from 12 to 4
- N 레벨에서 N-1 레벨로 이동
-
순간 이동은 일방 통행입니다 (12에서 4까지는 가능하지만 4에서 12까지는 불가능합니다)
- 모든 행동은 한 걸음 내딛습니다
입력
입력은 STDIN 또는 프로그래밍 언어에서 가장 가까운 대안에서 읽어야합니다. 입력은 n여기서 정수로 구성됩니다 1 <= n <= 10^8.
산출
출력은 n레벨 1 로 이동하는 데 필요한 최소 단계 수 여야합니다 .
예
Level Minimum number of steps
1 0
8 3
10 3
267 7
100,000,000 25
가장 짧은 시간 안에 감옥에서 우주선 조종사를 구하고 집으로 돌아 오는 데 도움이되는 프로그램을 코딩하십시오!
가장 짧은 코드가 이길 것입니다!
답변
Pyth, 32 바이트
L?<b3tbhSsmm+h%_Wkbdy/+kbd2tS3yQ
설명:
나는 문제를 조금 변형시켰다. 나는 질문의 4 가지 작업을 대체하는 4 개의 새로운 작업을 정의합니다.
level / 2((level % 2) + 1텔레포트하기 위해 먼저 레벨을 낮추어야 할 수도 있기 때문에 단계로 계산 )(level + 1) / 2((level % 2) + 1단계로 계산 )level / 3((level % 3) + 1단계로 계산 )(level + 1) / 3((-level % 3) + 1단계로 계산 )
이러한 설계 작업은 숫자이면 숫자에 각각 적용 할 수있다 0 mod 2, 1 mod 2, 0 mod 3, 1 mod 3또는 2 mod 3.
왜 이것이 효과가 있는지 쉽게 생각할 수 있습니다. 주요 아이디어는 연속으로 두 번 (아래로 이동) 또는 두 번 (위로 이동)하지 않는 최적의 솔루션이 하나 이상 있다는 것입니다. 증명 : 솔루션이있는 경우 솔루션을 교체하고 솔루션의 길이를 더 작거나 같게 만들 수있는 것보다 두 가지 모션이 연속으로 있습니다. 예를 들어, 다른 모든 경우에 대체 (위로 이동, 위로 이동, 2k에서 k로 텔레포트)하여 (2k에서 k 로의 텔레포트, 위로 이동) 등을 대체 할 수 있습니다.
L?<b3tbhSsmm+h%_Wkbdy/+kbd2tS3yQ
L define a function y(b), which returns:
?<b3 if b < 3:
tb return b-1
else:
m tS3 map each d in [2, 3] to:
m 2 map each k in [0, 1] to:
%_Wkbd (b mod d) if k == 0 else (-b mod d)
h +1, this gives the additional steps
+ y/+kbd + f((b+k)/d) (recursive call)
s combine the two lists
hS and return the minimum element
yQ call y with input number
이 함수 y는 암시 적으로 메모를 사용하므로 런타임이 폭발하지 않습니다.
답변
파이썬, 176 바이트
n=int(1e8);s,f,L=0,input(),[1,0]+[n]*(n-1)
def h(q):
if 0<=q<=n and L[q]>s:L[q]=s+1
while n in L:
for i,v in enumerate(L):
if v==s:map(h,(i-1,i+1,i*2,i*3))
s+=1
print L[f]
무차별 대입; 1 to 100,000,00064 비트 컴퓨터 의 모든 숫자 목록 은 ~ 800Mb의 메모리입니다.
목록 색인은 숫자를 나타내며 값은 허용 된 구조 단계에서 1과의 거리를 나타냅니다.
- “0 단계에 도달 할 수 있음”을 의미하는 list [1] = 0을 설정하십시오.
- 0 단계에 도달 목록의 모든 번호 (예에 대한
1)- 1 단계에서 도달 가능한 숫자 +1, 숫자 -1, 숫자 * 2, 숫자 * 3 설정
- 리스트에있는 모든 수의 어느 한 단계에서 (예를 연결할
0,2,2,3)- 2 단계로 도달 가능한 숫자 +1, 숫자 -1, 숫자 * 2, 숫자 * 3 설정
- … 모든 목록 색인에 도달 할 때까지
런타임은 10 분이 조금 넘습니다. * 아헴 *.
코드 주석
n=int(1e8) # max input limit.
s=0 # tracks moves from 1 to a given number.
f=input() # user input.
L=[1,0]+[n]*(n-1) # A list where 0 can get to room 1 in 1 step,
# 1 can get to itself in 0 steps,
# all other rooms can get to room 1 in
# max-input-limit steps as a huge upper bound.
def helper(q):
if 0<=q<=n: # Don't exceed the list boundaries.
if L[q]>s: # If we've already got to this room in fewer steps
# don't update it with a longer path.
L[q]=s+1 # Can get between rooms 1 and q in steps+1 actions.
while n in L: # until there are no values still at the
# original huge upper bound
for i,v in enumerate(L):
if v==s: # only pick out list items
# rechable in current s steps,
map(helper,(i-1,i+1,i*2,i*3)) # and set the next ones reachable
# in s+1 steps.
s+=1 # Go through the list again to find
# rooms reachable in s+1 steps
print L[f] # show answer to the user.
다른
- PythonWin에서 실행하면 나중에 인터프리터의 목록 L에 액세스 할 수 있습니다.
- 모든 객실은 30 이동 또는 이하의 선장에 대한 경로가 있습니다.
- 한 방만 30 칸 떨어져 있습니다-방 72,559,411-29 개 떨어진 244 개의 방이 있습니다.
- 최대 사례의 경우 런타임 특성이 끔찍할 수 있지만 질문 의견 중 하나는 ” @Geobits 5 분 안에 20000 테스트 사례에 가장 짧은 방법을 찾아야하는 모든 프로그램 “이며 <6 초 안에 1-20,001을 테스트합니다.
답변
파이썬 2 … 1050
잘못 쓰여졌 고 골프가없고 최적화되지 않았습니다.
stdin의 시작 레벨을 읽고 stdout에 최소 단계 수를 인쇄합니다.
def neighbors(l):
yield l+1
yield l-1
if not l%3:yield l/3
if not l%2:yield l/2
def findpath(start, goal):
closedset = set([])
openset = set([start])
came_from = {}
g_score = {}
g_score[start] = 0
f_score = {}
f_score[start] = 1
while len(openset) > 0:
current = min(f_score, key=f_score.get)
if current == goal:
return came_from
else:
openset.discard(current)
del f_score[current]
closedset.add(current)
for neighbor in neighbors(current):
if neighbor in closedset:
continue
tentative_g_score = g_score[current] + 1
if (neighbor not in openset) or (tentative_g_score < g_score[neighbor]):
came_from[neighbor] = current
g_score[neighbor] = tentative_g_score
f_score[neighbor] = tentative_g_score + 1
openset.add(neighbor)
def min_path(n):
path = findpath(n,1)
i,current = 0,1
while current <> n:
i+=1
current = path[current]
return i
print min_path(input())
답변
32 비트 x86 기계 코드, 59 바이트
16 진수로 :
31c9487435405031d231dbb103f7f14a7c070f94c301d008d353e8e3ffffff5b00c3585331d2b102f7f152e8d2ffffff5a00d05a38d076019240c3
기계 언어 자체 에는 표준 입력 개념이 없습니다. 과제는 순수한 계산이므로 입력 매개 변수를 가져 와서 EAX결과를 반환 하는 함수를 작성 했습니다 AL.
코드 뒤의 수학은 @Jakube에 의해 잘 설명되어 있습니다. 한 번의 이동만으로 텔레포트가 산재 된 경로 중에서 만 검색이 수행됩니다. 성능은 입력 범위의 하단에서 초당 약 12000 테스트 케이스이고 상단에서 초당 50 케이스입니다. 메모리 소비는 재귀 수준 당 12 바이트의 스택 공간입니다.
0: 31 c9 xor ecx, ecx
_proc:
2: 48 dec eax
3: 74 35 je _ret ;if (EAX==1) return 0;
5: 40 inc eax ;Restore EAX
6: 50 push eax
7: 31 d2 xor edx, edx ;Prepare EDX for 'div'
9: 31 db xor ebx, ebx
b: b1 03 mov cl, 3
d: f7 f1 div ecx ;EAX=int(EAX/3); EDX=EAX%3
f: 4a dec edx ;EDX is [-1..1]
10: 7c 07 jl _div3 ;EDX<0 (i.e. EAX%3==0)
12: 0f 94 c3 sete bl ;BL=EDX==0?1:0
15: 01 d0 add eax, edx ;If EAX%3==2, we'd go +1 level before teleport
17: 08 d3 or bl, dl ;BL=EAX%3!=0
_div3:
19: 53 push ebx ;Save register before...
1a: e8 e3 ff ff ff call _proc ;...recursive call
1f: 5b pop ebx
20: 00 c3 add bl, al ;BL is now # of steps if taken 3n->n route (adjusted) less one
22: 58 pop eax ;Restore original input parameter's value
23: 53 push ebx
24: 31 d2 xor edx, edx
26: b1 02 mov cl, 2
28: f7 f1 div ecx ;EAX=EAX>>1; EDX=EAX%2
2a: 52 push edx ;Save register before...
2b: e8 d2 ff ff ff call _proc ;...another recursive call
30: 5a pop edx
31: 00 d0 add al, dl ;AL is now # of steps if using 2n->n route (adjusted) less one
33: 5a pop edx
34: 38 d0 cmp al, dl ;Compare two routes
36: 76 01 jbe _nsw
38: 92 xchg eax, edx ;EAX=min(EAX,EDX)
_nsw:
39: 40 inc eax ;Add one for the teleport itself
_ret:
3a: c3 ret