小 W, sinh viên khoa Kỹ thuật phần mềm, đang dự thi vẽ kỹ thuật nhưng chỉ mang theo một chiếc thước thẳng đã bị thời gian mài mất vạch chia và một chiếc compa. Không còn cách nào khác, cậu phải nhờ đến bạn, người có khả năng dựng hình học đáng kinh ngạc. Hãy dùng thước thẳng không chia vạch và compa để giúp 小 W hoàn thành bản vẽ vừa nhanh vừa chính xác.

Ta đơn giản hóa bài toán: giả sử 小 W đã có hệ tọa độ và độ dài đơn vị. Cậu cần bạn dựng độ dài $L_0$ bằng thước và compa, tức là thu được điểm $(L_0,0)$.

Bạn có thể dùng ba thao tác sau:

1. $\operatorname{line}(A,B)$: dựng đường thẳng đi qua hai điểm $A$ và $B$;

2. $\operatorname{circle}(O,A,B)$: dựng đường tròn tâm $O$, bán kính bằng khoảng cách $AB$;

3. $\operatorname{intersect}(i,j)$: đánh dấu tất cả giao điểm của hình thứ $i$ và hình thứ $j$; nếu có nhiều giao điểm thì đánh dấu tất cả.

Ban đầu, 小 W cung cấp gốc tọa độ $O(0,0)$, là điểm số $0$. Độ dài đơn vị được cho bởi điểm số $1$ tại $(1,0)$. Ngoài ra còn có trục $x$ (hình số $0$) và trục $y$ (hình số $1$).

Tất cả các điểm và hình mới thu được qua các thao tác sẽ được đánh số tiếp nối.

Giả sử số hiệu hiện tại là $n$, thì điểm tạo ra bởi thao tác $\operatorname{intersect}$ sẽ được đánh số $n+1$.

Nếu hai hình không có giao điểm thì không tạo ra điểm mới.

Nếu có hai giao điểm, điểm có giá trị $x$ nhỏ hơn (nếu bằng nhau thì chọn điểm có $y$ nhỏ hơn) được đánh số $n+1$, còn điểm kia được đánh số $n+2$.

Hãy dựng điểm $(L_0,0)$ và chỉ ra số hiệu của nó. Bạn không cần đạt được giá trị chính xác, nhưng sai lệch so với giá trị chính xác và số thao tác bạn dùng sẽ ảnh hưởng đến điểm số.

Dữ liệu vào

Đây là bài chỉ nộp tệp kết quả. Tất cả dữ liệu vào draw1.in–draw10.in đã có trong thư mục bài thi.

Mỗi dữ liệu vào $x_0$ là một biểu thức tính toán bằng Python. Trong đó, ** là phép lũy thừa; chẳng hạn 3 ** 2 biểu diễn $3^2$, còn 2 ** 0.5 biểu diễn $\sqrt2$.

Để có độ chính xác cao hơn, các số trong biểu thức được chuyển sang kiểu decimal, tức là số thập phân có độ chính xác cao. Ví dụ, Decimal(2) biểu diễn $2$.

Dữ liệu vào bảo đảm giữa số với ký hiệu và giữa hai ký hiệu có một dấu cách.

Kết quả của đoạn mã Python là số cần dựng.

Lưu ý rằng kết quả tính trực tiếp bằng Python là giá trị gần đúng, còn giá trị thực sự được yêu cầu là giá trị chính xác; tức là giá trị dùng để so sánh với kết quả của thí sinh là giá trị chính xác.

Ngoài ra, chúng tôi cung cấp tệp draw.pdf, trình bày biểu thức của mỗi bộ dữ liệu theo cách dễ đọc.

Dữ liệu ra

Với 10 tệp dữ liệu vào draw1.in–draw10.in, bạn cần nộp riêng các tệp kết quả draw1.out–draw10.out tương ứng.

Dòng đầu của tệp kết quả là số nguyên $n$, biểu thị số thao tác. Tiếp theo là $n$ dòng, mỗi dòng một thao tác. Định dạng tương ứng của ba thao tác là:

line: L A B
circle: C O A B
intersect: I i j

Ý nghĩa các tham số giống như trong mô tả bài toán.

Dòng cuối của tệp kết quả chứa một số nguyên là số hiệu của điểm cuối cùng thu được.

Ví dụ

Dữ liệu vào 1

Decimal( 2 ) ** ( Decimal( 1 ) / Decimal( 2 ) )

Dữ liệu ra 1

5
C 0 0 1
I 1 2
C 0 1 3
L 1 3
I 0 3
5

Ghi chú

Năm thao tác trong ví dụ có ý nghĩa như sau:

1. Dựng đường tròn tâm $O$, bán kính bằng độ dài đơn vị; đường tròn này là hình số $2$;

2. Lấy giao điểm của hình số $2$ (đường tròn) với trục $y$; các giao điểm là điểm số $2$ tại $(0,-1)$ và điểm số $3$ tại $(0,1)$;

3. Dựng đường tròn tâm $O$, bán kính bằng khoảng cách giữa điểm số $1$ và điểm số $3$; đường tròn này là hình số $3$;

4. Nối hai điểm $(1,0)$ và $(0,1)$; đường thẳng thu được là hình số $4$.

5. Lấy giao điểm của hình số $3$ (đường tròn) với trục $x$; các giao điểm là điểm số $4$ tại $(-\sqrt2,0)$ và điểm số $5$ tại $(\sqrt2,0)$.

Vì vậy, điểm số $5$ là điểm cuối cùng cần dựng.

Nhiệm vụ con

Với 10 tệp dữ liệu vào draw1.in–draw10.in, chúng tôi cung cấp các tệp tham số chấm điểm tương ứng draw1.ans–draw10.ans.

Mỗi tệp tham số chấm điểm có 10 dòng, mỗi dòng gồm hai số $c_i,x_i$. Nếu hoành độ $x$ của điểm cuối cùng $(x,0)$ thỏa mãn $|x-L_0|\le10^{-x_i}$ và số thao tác sử dụng thỏa mãn $n\le c_i$, bạn có thể được $i$ điểm.

Hệ thống chấm lấy mức điểm cao nhất trong các điều kiện được thỏa mãn. Nếu không thỏa mãn điều kiện nào thì được 0 điểm.

Cách kiểm tra kết quả của bạn

Chúng tôi cung cấp công cụ checker để kiểm tra tệp kết quả của bạn có được chấp nhận hay không. Để sử dụng, trước tiên mở cửa sổ dòng lệnh và chạy lệnh sau để vào thư mục bài thi:

cd draw

Sau đó chạy:

./checker <case_no>

Trong đó, case_no là số hiệu bộ dữ liệu kiểm tra. Ví dụ:

./checker 3

Lệnh này kiểm tra xem draw3.out có được chấp nhận hay không.

Sau khi được gọi, checker sẽ trả về kết quả kiểm tra dựa trên tệp kết quả bạn đưa ra, bao gồm:

1. Thoát bất thường: lỗi không xác định.

2. Invalid parameters for checker.: các tham số truyền cho checker không hợp lệ.

3. Input/Output file does not exist.: tệp dữ liệu vào hoặc tệp kết quả không tồn tại.

4. Output invalid: tệp kết quả có lỗi; có thể kèm thông tin lỗi cụ thể.

5. Correct! Your answer is n. Your score is s.: kết quả được chấp nhận, số thao tác đã dùng là $n$, điểm của bộ dữ liệu này là $s$.

Các chức năng khác

checker còn có thể kiểm tra các tệp dữ liệu vào và kết quả tùy ý. Chạy trong cửa sổ dòng lệnh:

cd draw
./checker <input_file> <output_file> <ans_file>

Trong đó, input_file, output_file và ans_file lần lượt là tên tệp dữ liệu vào, tệp kết quả và tệp tham số chấm điểm.

Ví dụ:

./checker draw3.in draw3.out draw3.ans

Lệnh này kiểm tra xem draw3.out có được chấp nhận hay không.

Dùng tùy chọn -w để xuất tọa độ của từng điểm được tạo ra. Mỗi dòng có định dạng:

id x y

Các giá trị lần lượt là số hiệu điểm, tọa độ $x$ và tọa độ $y$. Cách dùng cụ thể:

./checker -w <input_file> <output_file> <ans_file>

hoặc

./checker -w <case_no>

Ví dụ:

./checker -w draw3.in draw3.out draw3.ans

Dùng tùy chọn -i để đồng thời hiển thị kết quả của thí sinh, giúp thuận tiện khi gỡ lỗi. Cách dùng cụ thể:

./checker -i <input_file> <output_file> <ans_file>

hoặc

./checker -i <case_no>

Ví dụ:

./checker -i draw3.in draw3.out draw3.ans

Dùng -e prec để chỉ định độ chính xác tính toán (số chữ số có nghĩa) của checker. Nếu không dùng tùy chọn này, prec mặc định là 200. Cách dùng cụ thể:

./checker -e <prec> <input_file> <output_file> <ans_file>

hoặc

./checker -e <prec> <case_no>

Ví dụ:

./checker -e 50 draw3.in draw3.out draw3.ans

Có thể dùng đồng thời các tùy chọn -e prec, -w và -i, theo bất kỳ thứ tự nào, chẳng hạn:

./checker -w -i -e 50 draw3.in draw3.out draw3.ans

Ghi chú

Ta có thể dùng Python để lấy giá trị gần đúng của biểu thức. Cụ thể, sau khi chạy Python trong cửa sổ dòng lệnh, nhập:

from math import *
from decimal import *
getcontext().prec = 100

Sau đó sao chép biểu thức (mã Python) trong tệp dữ liệu vào cửa sổ dòng lệnh và nhấn Enter để nhận giá trị gần đúng của biểu thức. (Có thể thay 100 trong đoạn mã trên bằng độ chính xác bạn muốn.)

Lưu ý đặc biệt

Nếu dùng tệp dữ liệu tự tạo để gỡ lỗi, kích thước quá lớn có thể khiến checker gặp lỗi. Khi đó, hãy thử dữ liệu có kích thước nhỏ hơn.

Hãy giữ cẩn thận các tệp dữ liệu vào draw*.in, tệp kết quả của bạn draw*.out và tệp tham số chấm điểm draw*.ans, đồng thời sao lưu kịp thời để tránh vô tình xóa mất.