cmp

메모리가 10240비트 배열 하나뿐인 고대 컴퓨터를 위한 알고리즘을 설계해야 한다. 메모리는 0으로 초기화되며, 이후 한 번에 한 비트씩 쓰고 읽을 수 있다.

이 컴퓨터에서 두 가지 연산을 구현해야 한다.

• remember(a): a는 0과 4095 사이의 정수

  • 이 연산의 구현은 다음을 호출할 수 있다.
    • bit_set(address): address는 1과 10240 사이의 정수
      • address 위치의 메모리 비트가 1로 설정된다.

• compare(b): b는 0과 4095 사이의 정수

  • b < a이면 -1을 반환해야 한다.
  • b = a이면 0을 반환해야 한다.
  • b > a이면 1을 반환해야 한다.
  • 이 연산의 구현은 다음을 호출할 수 있다.
    • bit_get(address)
      • address 위치의 메모리 비트를 반환한다. remember(a) 연산 중 bit_set()으로 설정되었다면 1, 그렇지 않으면 0이다.

가능한 모든 a와 b 값에 대해 최악의 경우 메모리 접근(bit_set()과 bit_get() 호출) 횟수의 합이 최소가 되도록 remember()와 compare()를 구현하라.

채점은 다음과 같이 전수 검사로 이루어진다.

define AllMemory = array [0..4095][1..10240] of bits
set AllMemory to zeros
for a = 0..4095:
        define bit_set(address): AllMemory[a][address] = 1 
        remember(a)
let maxA= the maximum number of bit_set() calls executed for any a
for (a,b) ∈ {0..4095}×{0..4095} in random order (i.e. all valid pairs (a,b) are considered, in some random order)
        define bit_get(address): return AllMemory[a][address]
        answer =compare(b)
        if answer for comparing a and b is incorrect : your score = 0; exit
let maxB = the maximum number of bit_get() calls executed for any (a,b) pair
T=maxA + maxB
If (T>20): your score = 0; exit
else your score = 1 + 9 * (21– T); exit

• 채점 코드의 메모리와 상호작용하려는 시도가 있으면 실격될 수 있다.
• 위에서 정의한 프로토콜을 지키지 않으면(예: compare() 중 bit_set() 호출 또는 잘못된 주소 사용) 0점을 받는다.