Bài gọi hàm (Signature Grader)

Wiki › Hướng dẫn ra đề

huunguyen · Last updated 17, Tháng 4, 2026, 2:54

Signature grader là gì?

Trong bài signature grader, thí sinh không viết chương trình hoàn chỉnh (không có main(), không đọc input, không in output). Thay vào đó, thí sinh chỉ cài đặt một hoặc vài hàm theo prototype đã cho. Hệ thống sẽ biên dịch code thí sinh cùng với handler (chương trình chính) rồi chạy.

Ví dụ: Bài yêu cầu cài đặt int query(int l, int r) để trả lời truy vấn min trên đoạn. Thí sinh chỉ viết hàm đó — handler lo việc đọc input và gọi hàm.

Khi nào dùng signature grader?

Cấu trúc dữ liệu: Thí sinh cài đặt init() và query() cho segment tree, sparse table, ...
Bài có nhiều thao tác: insert(), delete(), find() — đề bài tập trung vào thuật toán, không phải I/O.
Ẩn cách sinh truy vấn: Handler có thể sinh truy vấn online (phụ thuộc đáp án trước).
Giới hạn ngôn ngữ: Khi bài cần hiệu năng cao và chỉ muốn hỗ trợ C/C++ (và tùy chọn Python, Java).

Kiến trúc

┌─────────────────────────────────────────────┐
│  Biên dịch cùng nhau (C++):                 │
│                                              │
│  ┌───────────┐    #include    ┌────────────┐ │
│  │ handler.cpp│ ◄──────────── │  header.h  │ │
│  │ (main)     │               └────────────┘ │
│  └─────┬─────┘                      ▲        │
│        │ gọi hàm             #include│        │
│        ▼                             │        │
│  ┌────────────┐                      │        │
│  │ solution.cpp│ ─────────────────────┘        │
│  │ (thí sinh)  │                               │
│  └────────────┘                               │
└─────────────────────────────────────────────┘

Gồm 3 file:

File	Vai trò	Ai viết
`header.h`	Khai báo prototype hàm	Problem setter
`handler.cpp`	Chương trình chính: đọc input, gọi hàm thí sinh, in output	Problem setter
`solution.cpp`	Cài đặt các hàm	Thí sinh

Cấu hình trên CTOJ

Khi tạo bài:

grader = "signature"
custom_grader_source = mã nguồn handler.cpp
custom_header_source = mã nguồn header.h
signature_grader_languages = danh sách ngôn ngữ hỗ trợ (ví dụ: ["CPP", "PY3", "JAVA"])

Viết header.h

Header khai báo prototype của các hàm thí sinh cần cài đặt:

#ifndef _HEADER_H
#define _HEADER_H

// Thí sinh cần cài đặt hai hàm sau:
void init(int n, int arr[]);
int query(int l, int r);

#endif

Lưu ý:

Dùng include guard (#ifndef).
Chỉ khai báo prototype, không định nghĩa.
Giữ đơn giản — không include thêm thư viện nếu không cần.

Viết handler.cpp

Handler là chương trình chính: đọc input, gọi hàm thí sinh, in output.

#include "header.h"
#include <cstdio>

static int _arr[200001];

int main() {
    int n, q;
    scanf("%d %d", &n, &q);
    for (int i = 0; i < n; i++) scanf("%d", &_arr[i]);

    init(n, _arr);

    while (q--) {
        int l, r;
        scanf("%d %d", &l, &r);
        printf("%d\n", query(l, r));
    }

    return 0;
}

Lưu ý:

Include header.h để dùng các hàm thí sinh.
Dùng biến static hoặc namespace riêng để tránh xung đột tên với code thí sinh.
Handler lo toàn bộ I/O — thí sinh không cần biết format input.

Viết handler.py (cho Python)

Nếu hỗ trợ Python, cần thêm handler Python:

import sys
from solution import init, query

input = sys.stdin.readline

n, q = map(int, input().split())
arr = list(map(int, input().split()))

init(n, arr)

for _ in range(q):
    l, r = map(int, input().split())
    print(query(l, r))

Lưu ý: Handler Python import từ module solution — CTOJ sẽ lưu code thí sinh dưới tên solution.py.

Ví dụ: Lời giải thí sinh

C++ (nộp trên CTOJ)

#include "header.h"
#include <algorithm>
using namespace std;

static int sp[18][200001];
static int LOG[200002];

void init(int n, int arr[]) {
    LOG[1] = 0;
    for (int i = 2; i <= n; i++) LOG[i] = LOG[i / 2] + 1;
    for (int i = 0; i < n; i++) sp[0][i] = arr[i];
    for (int k = 1; (1 << k) <= n; k++)
        for (int i = 0; i + (1 << k) <= n; i++)
            sp[k][i] = min(sp[k-1][i], sp[k-1][i + (1 << (k-1))]);
}

int query(int l, int r) {
    int k = LOG[r - l + 1];
    return min(sp[k][l], sp[k][r - (1 << k) + 1]);
}

Thí sinh chỉ nộp phần này. Không cần main(), không cần scanf/printf.

Python (nộp trên CTOJ)

import math

_sp = []
_log = []

def init(n, arr):
    global _sp, _log
    max_k = max(1, int(math.log2(n)) + 1) if n > 0 else 1
    _sp = [arr[:]] + [[0]*n for _ in range(max_k)]
    for k in range(1, max_k + 1):
        for i in range(n - (1 << k) + 1):
            _sp[k][i] = min(_sp[k-1][i], _sp[k-1][i + (1 << (k-1))])
    _log = [0] * (n + 1)
    for i in range(2, n + 1):
        _log[i] = _log[i // 2] + 1

def query(l, r):
    k = _log[r - l + 1]
    return min(_sp[k][l], _sp[k][r - (1 << k) + 1])

Viết đề bài signature

Đề bài cần mô tả rõ:

Đây là bài signature grader — thí sinh chỉ viết hàm.
Prototype hàm cho mỗi ngôn ngữ hỗ trợ.
Mô tả chi tiết từng hàm: tham số, giá trị trả về, khi nào được gọi, thứ tự gọi.
Ngôn ngữ hỗ trợ (thường C/C++, Python, Java).

Ví dụ:

## Hàm cần cài đặt

Đây là bài toán **signature grader**. Bạn chỉ cần cài đặt hai hàm sau.

**Ngôn ngữ hỗ trợ:** C/C++, Python, và Java.

### C++

\```cpp
void init(int n, int arr[]);
int query(int l, int r);

Python

```python def init(n: int, arr: list[int]) -> None: ... def query(l: int, r: int) -> int: ... ```

Mô tả

init(n, arr): Được gọi một lần. Khởi tạo cấu trúc dữ liệu.
query(l, r): Được gọi $q$ lần. Trả về min trong đoạn $[l, r]$ .


## Cấu trúc file trong problem package

problems/<problem-name>/ tests/ handler.cpp # Handler C++ (main) handler.py # Handler Python (nếu hỗ trợ PY3) header.h # Khai báo prototype 01.in / 01.out ... solutions/ solution.cpp # Lời giải mẫu (chỉ có hàm, không có main)</problem-name>


## Bài mẫu trên CTOJ

- [RMQ Signature](https://oj.chuyentin.pro/problem/rmqsig) — bài signature grader mẫu: thí sinh cài đặt `init()` và `query()` cho bài toán RMQ (Range Minimum Query).

## So sánh các loại grader

| | Standard | Interactive | Signature |
|---|---------|-------------|-----------|
| Thí sinh viết | Chương trình đầy đủ | Chương trình đầy đủ | Chỉ hàm |
| I/O | stdin → stdout | stdin ↔ stdout (hỏi đáp) | Không (handler lo) |
| Giao tiếp | Không | Pipe hai chiều với interactor | Gọi hàm trực tiếp |
| Ngôn ngữ | Tất cả | Tất cả | C/C++, Python, Java |
| Config `grader` | `"standard"` | `"interactive"` | `"signature"` |
| File đặc biệt | Không | `interactor.cpp` | `handler.cpp` + `header.h` |

## Lưu ý

### Tránh xung đột tên

Handler và code thí sinh được biên dịch chung. Dùng `static` hoặc prefix cho biến trong handler:

```cpp
// handler.cpp — tốt
static int _arr[200001];  // static, không xung đột

// handler.cpp — xấu
int arr[200001];  // có thể trùng với biến thí sinh

Test output

File .out chứa output mong đợi từ handler (sau khi gọi hàm thí sinh với đáp án đúng). Hệ thống so sánh stdout của handler với .out — giống bài standard.

Kết hợp với custom checker

Signature grader có thể kết hợp với custom checker nếu bài có nhiều đáp án đúng. Thiết lập thêm checker = "bridged" và custom_checker_source.

Bình luận

Không có bình luận tại thời điểm này.