Day_3_Spiral_Memory

Day 3: Spiral Memory

Part 1

Translation

당신은 무한 2차원 격자에 놓인 새롭고 실험적인 메모리를 우연히 보았다.

격자의 각 사각형은 1로 표시된 곳으로부터 나선형으로 위치하고 나선형으로 뻗어나갈 때 1씩 증가한다. 예를 들어, 처음 몇 개의 사각형들은 다음과 같이 위치한다:

17  16  15  14  13
18   5   4   3  12
19   6   1   2  11
20   7   8   9  10
21  22  23 --> ...

이는 공간-효율적인데(어떤 사각형도 넘어가지 않는다), 요청된 데이터는 상하좌우로 움직이는 프로그램에 의해 반드시 사각형 1 (해당 메모리 시스템의 유일한 접근 포트 장소)로 넘겨줘야 한다. 이는 항상 최단 경로를 취한다: 데이터의 위치와 사각형 1의 맨하탄 거리.

예시:

• 사각형 1의 데이터는 접근 포트에 있기 때문에, 0 번 옮겨진다.
• 사각형 12의 데이터는 하, 좌, 좌로서, 3 번 옮겨진다.
• 사각형 23의 데이터는 상, 상으로서, 2 번 옮겨진다.
• 사각형 1024의 데이터는 31 번 옮겨진다.

주어진 사각형 위치로부터 접근 포트까지 데이터를 몇 번 옮겨야 하는가?

Solution

• 입력 : 특정 사각형 위치
• 처리 : 주어진 사각형 위치와 사각형 1의 맨하탄 거리를 계산한다.
• 출력 : 주어진 사각형 위치와 사각형 1의 맨하탄 거리.
• source

Part 2

Translation

해당 시스템의 스트레스 테스트로서, 프로그램은 모든 격자를 초기화하고 사각형 1에 값 1을 저장한다. 그리고, 위에 나온 할당 순서대로, 대각선을 포함한 모든 인접한 사각형들의 값을 저장한다.

따라서, 초기 사각형들의 값은 다음과 같이 정해진다:

• 사각형 1은 값 1로 시작한다.
• 사각형 2는 오직 값 1이 채워진 사각형 하나와 인접하므로, 따라서 똑같이 1을 저장한다.
• 사각형 3은 사각형 1과 사각형 2 둘다 이웃이므로 그들의 값의 합인 2를 저장한다.
• 사각형 4는 이전에 언급한 사각형 1, 사각형 2, 사각형 3과 이웃이므로 그들의 값의 합인 4를 저장한다.
• 사각형 5는 사각형 1과 사각형 4 이웃이므로 그들의 값의 합인 5을 저장한다.

사각형에 한번 기록을 하면, 그 값은 바뀌지 않는다. 그러므로, 초기 사각형은 다음과 같이 값을 가진다:

147  142  133  122   59
304    5    4    2   57
330   10    1    1   54
351   11   23   25   26
362  747  806--->   ...

당신의 퍼즐 입력보다 더 크게 나온 최초의 값은 무엇인가?

Solution

• 입력 : 임계값 289326
• 처리 : 임계값보다 더 크게 나온 최초의 값을 구한다.
• 출력 : 임계값보다 더 크게 나온 최초의 값.
• source