시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
10 초 256 MB 1 1 1 100.000%

문제

You must design an algorithm for an ancient computer whose memory is just an array of 10240 bits. The memory is initialized to zero, after which you may write and read a single bit at a time.

You must implement two operations on this computer:

  • remember(a): a is an integer between 0 and 4095
    • The implementation of this operation may call:
      • bit_set(address): address is an integer between 1 and 10240
        • The memory bit at position address will be set to 1
  • compare(b): b is an integer between 0 and 4095
    • if b < a, it should return -1
    • if b = a, it should return 0 if b > a, it should return 1
    • The implementation of this operation may call:
      • bit_get(address)
        • Returns the memory bit at position address: 1 if it was set through bit_set() during the remember(a) operation, and 0 otherwise.

Implement remember() and compare() to minimize the total number of memory accesses (bit_set() and bit_get()) in the worst-case for all possible values of a and b.

Your solution will be evaluated exhaustively:

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

제한

  • You may be disqualified for any attempt to interact with the memory of our grading code.
  • If your solution does not obey the protocol defined above (e.g. calling bit_set() during compare() or with an invalid address), you will receive zero points.

구현

Your source file must begin with:

#include "cmp.h"

The prototypes for the memory-access functions are:

void bit_set(int addr);
int bit_get (int addr);

You must implement the functions:

void remember(int value);
int compare(int value);

The file cmp.h will provide the function main(), and you must not define another such function. All global names (for variables and functions) except bit_set() and bit_get() will begin with the prefix boi. So you may avoid compilation errors by not naming your functions and variables with this prefix.

We have provided a sample implementation for cmp.h in the file public-cmp.h for convenience which you may edit as you please. The implementation is different from the version of cmp.h used for grading but the interface to your program remains the same.

To compile all code simply compile your source file and make sure that cmp.h is in the same directory.

첨부

제출할 수 있는 언어

C++17, C++14, C++20, C++14 (Clang), C++17 (Clang), C++20 (Clang)

채점 및 기타 정보

  • 100점 이상을 획득해야 를 받는다.
  • 예제는 채점하지 않는다.