QHHOJ SC 2024 - Premier - Round #3 - QHHOJ

QHHOJ SC 2024 - Premier - Round #3

Chia cắt

Giới hạn thời gian: 1.0s / Giới hạn bộ nhớ: 256M

Điểm: 1000

Trên một đường tròn ta chấm ngẫu nhiên ~x~ điểm, sau đó lần lượt nối các cặp hai điểm lại bằng các đoạn thẳng. Khi đó, hình tròn sẽ bị chia ra thành nhiều miền khác nhau.

Hỏi số lượng miền tối đa có thể thu được là bao nhiêu?

Input

Dòng 1: số nguyên dương ~T~ (~1 \le T \le 1000~)
Dòng 2: ~T~ số nguyên dương ~x_1, x_2, \cdots, x_n~

Output

In ra 1 dòng gồm ~T~ số nguyên dương ~y_i~ cách nhau bởi dấu cách, mỗi số nguyên dương ~y_i~ là số miền tối đa tạo trên hình tròn khi nối các cặp hai điểm trong ~x_i~ điểm ngẫu nhiên trên đường tròn.

Ví dụ

Sample Input

5
1 2 3 4 5

Sample Output

1 2 4 8 16

Giải thích

~x_i = 4 \implies y_i = 8~

Subtasks

Subtask 1 (10%): ~a_i \le 5~
Subtask 2 (25%): ~a_i \le 50~
Subtask 3 (30%): ~a_i \le 500~
Subtask 4 (35%): ~a_i \le 50000~

Canh lề trái

Nộp bài

Giới hạn thời gian: 1.0s / Giới hạn bộ nhớ: 256M

Điểm: 1500

edit.exe là một chương trình máy tính trên hệ điều hành MS-DOS nhằm tạo mới hoặc thay đổi các tệp văn bản *.TXT. Vì thực hiện trên giao diện cửa sổ console, không có đồ hoạ phức tạp như các chương trình ngày nay (Notepad, MS Word,…) nên việc tạo kiểu cho văn bản là rất hạn chế trên phần mềm này. Trong bài toán này, nhiệm vụ của bạn là thực hiện thao tác "căn lề trái" (left-align) cho một văn bản trong cửa sổ console có độ dài ~W~ tuỳ ý.

Cho một đoạn văn bản ~T~ gồm ~n~ ký tự ASCII (bao gồm 26 chữ cái Latin thường, 26 chữ cái Latin hoa, 10 chữ số thập phân, dấu phẩy, dấu chấm và dấu khoảng trắng). Hãy in ra đoạn văn bản đã tạo kiểu "căn lề trái", tức là thay thế một số ký tự khoảng trắng bằng ký tự xuống dòng '\n', sao cho đảm bảo:

Trên mỗi dòng, ký tự đầu tiên và ký tự cuối cùng không phải là ký tự khoảng trắng;
Mỗi dòng có tối đa ~W~ ký tự (không kể ký tự xuống dòng);
Số lượng dòng sử dụng là ít nhất;
Nếu có nhiều hơn một phương án, có thể in ra một phương án bất kỳ.

Chú thích.

Một từ là tập hợp các ký tự Latin được bao quanh bởi ký tự khoảng trắng ' '.
Một đoạn văn bản được gọi là chuẩn khi và chỉ khi:
- Không tồn tại hai ký tự khoảng trắng ' ' liên tiếp nhau;
- Liền sau một dấu phẩy , bất kỳ là một ký tự khoảng trắng ' ' hoặc xuống hàng '\n';
- Liền sau một dấu chấm . bất kỳ là một ký tự khoảng trắng ' ' hoặc xuống hàng '\n' (trừ dấu chấm kết đoạn);
- Mở đầu một hàng không phải là một dấu câu;
- Kết thúc một hàng không phải là ký tự khoảng trắng ' '.

Input

Dòng ~1~: chứa số nguyên dương ~W~, biểu thị độ dài cửa sổ ~W~;
Dòng ~2~: chứa toàn bộ văn bản ~T~ trên một dòng. Dữ liệu đảm bảo ~T~ là một văn bản chuẩn.

Output

Dòng ~1~: In ra số nguyên dương ~M~ là số dòng của văn bản sau khi canh lề;
Dòng ~2~ đến ~M+1~: In ra văn bản ~P~ sau khi canh lề. Kết quả phải đảm bảo ~P~ là một văn bản chuẩn.

Ví dụ

Sample Input

98
Artificial intelligence, a nebulous construct of algorithms and data, has precipitated a paradigm shift in contemporary society. Its capacity for rapid learning and adaptation has engendered both awe and trepidation. As these sentient systems proliferate, so too do the ethical quandaries associated with their development and deployment. While the potential benefits, from accelerated medical research to optimized energy consumption, are undeniably profound, the specter of unintended consequences looms large.

Sample Output

6
Artificial intelligence, a nebulous
construct of algorithms and data, has precipitated a paradigm shift in contemporary society.
Its capacity for rapid learning and adaptation has engendered both awe and trepidation. As these
sentient systems proliferate, so too do the ethical quandaries associated with their development
and deployment. While the potential benefits, from accelerated medical research to optimized
energy consumption, are undeniably profound, the specter of unintended consequences looms large.

=======================================[Ruler, DO NOT PRINT]=======================================
         1         2         3         4         5         6         7         8         9       9
12345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678
===================================================================================================

Chú thích:

Đoạn văn sau khi canh lề có ~6~ dòng.

Cách tính điểm

Có tất cả ~16~ testcase, mỗi testcase được sinh bởi chatbot Gemini (Google) sử dụng truy vấn sau:

Generate some random English text in one long paragraph containing around [1000 - 10000] characters, AI-themed, using [simple/complex] words

Với mỗi testcase, giả sử phương án canh lề của bạn sử dụng ~M~ dòng, phương án canh lề của giám khảo sử dụng ~M_0~ dòng. Khi đó,

Bạn được ~5\%~ điểm nếu ~M > 2 M_0~;
Bạn được ~25\%~ điểm nếu ~1.5\cdot M_0 < M \le 2 M_0~;
Bạn được ~50\%~ điểm nếu ~M_0 < M \le 1.5\cdot M_0~;
Bạn được ~100\%~ điểm nếu ~M \le M_0~.

Giới hạn

~100 \le |T| \le 10^4~
~50 \le W \le 200~
Độ dài mỗi từ không vượt quá ~20~.

Canh lề trái 2

Nộp bài

Giới hạn thời gian: 1.0s / Giới hạn bộ nhớ: 256M

Điểm: 2000

Trên mỗi dòng, ký tự đầu tiên và ký tự cuối cùng không phải là ký tự khoảng trắng;
Mỗi dòng có tối đa ~W~ ký tự (không kể ký tự xuống dòng);
Số lượng dòng sử dụng là ít nhất;
Nếu có nhiều hơn một phương án, chọn phương án có chênh lệch độ dài giữa dòng dài nhất và dòng ngắn nhất là ít nhất;
Nếu có nhiều hơn một phương án, có thể in ra một phương án bất kỳ.

Chú thích.

Một từ là tập hợp các ký tự Latin được bao quanh bởi ký tự khoảng trắng ' '.
Một đoạn văn bản được gọi là chuẩn khi và chỉ khi:
- Không tồn tại hai ký tự khoảng trắng ' ' liên tiếp nhau;
- Liền sau một dấu phẩy , bất kỳ là một ký tự khoảng trắng ' ' hoặc xuống hàng '\n';
- Liền sau một dấu chấm . bất kỳ là một ký tự khoảng trắng ' ' hoặc xuống hàng '\n' (trừ dấu chấm kết đoạn);
- Mở đầu một hàng không phải là một dấu câu;
- Kết thúc một hàng không phải là ký tự khoảng trắng ' '.

Input

Dòng ~1~: chứa số nguyên dương ~W~, biểu thị độ dài cửa sổ ~W~;
Dòng ~2~: chứa toàn bộ văn bản ~T~ trên một dòng. Dữ liệu đảm bảo ~T~ là một văn bản chuẩn.

Output

Dòng ~1~: In ra số nguyên dương ~M~ là số dòng của văn bản sau khi canh lề;
Dòng ~2~ đến ~M+1~: In ra văn bản ~P~ sau khi canh lề. Kết quả phải đảm bảo ~P~ là một văn bản chuẩn.

Ví dụ

Sample Input

98
Artificial intelligence, a nebulous construct of algorithms and data, has precipitated a paradigm shift in contemporary society. Its capacity for rapid learning and adaptation has engendered both awe and trepidation. As these sentient systems proliferate, so too do the ethical quandaries associated with their development and deployment. While the potential benefits, from accelerated medical research to optimized energy consumption, are undeniably profound, the specter of unintended consequences looms large.

Sample Output

6
Artificial intelligence, a nebulous construct of algorithms and data, has precipitated
a paradigm shift in contemporary society. Its capacity for rapid learning and adaptation
has engendered both awe and trepidation. As these sentient systems proliferate,
so too do the ethical quandaries associated with their development and deployment.
While the potential benefits, from accelerated medical research to optimized
energy consumption, are undeniably profound, the specter of unintended consequences looms large.

=======================================[Ruler, DO NOT PRINT]=======================================
         1         2         3         4         5         6         7         8         9       9
12345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678
===================================================================================================

Chú thích:

Đoạn văn sau khi canh lề có ~6~ dòng.

Cách tính điểm

Có tất cả ~16~ testcase, mỗi testcase được sinh bởi chatbot Gemini (Google) sử dụng truy vấn sau:

Generate some random English text in one long paragraph containing around [1000 - 10000] characters, AI-themed, using [simple/complex] words

Với mỗi testcase, giả sử:

Phương án canh lề của bạn sử dụng ~M~ dòng, phương án canh lề của giám khảo sử dụng ~M_0~ dòng;
Chênh lệch giữa dòng dài nhất và dòng ngắn nhất trong phương án của bạn là ~\sigma~, trong phương án của giám kháo là ~\sigma_0~;

Khi đó,

Bạn được ~35\%~ điểm nếu ~M = M_0~ và ~\sigma_0 + 2 < \sigma \le \sigma_0 + 8~;
Bạn được ~75\%~ điểm nếu ~M = M_0~ và ~\sigma_0 < \sigma \le \sigma_0 + 2~;
Bạn được ~100\%~ điểm nếu ~M < M_0~ hoặc (~M = M_0~ và ~\sigma \le \sigma_0~).

Giới hạn

~100 \le |T| \le 10^4~
~50 \le W \le 200~
Độ dài mỗi từ không vượt quá ~20~.

Quả nặng thứ 101

Nộp bài

Giới hạn thời gian: 1.5s / Giới hạn bộ nhớ: 256M

Điểm: 2750

Một chiếc cân đĩa đang lệch về phía bên trái bởi một quả nặng có khối lượng là ~x~, quả nặng này gọi là quả nặng thứ 101. Bạn được cho 100 quả nặng khác ~w_1,w_2,⋯,w_{100},~ trong đó:

~w_1=1~ (g)
~w_2=2~ (g)
~w_i=w_{i-1}+w_{i-2}, \forall i \in [3,100]~

Hãy sử dụng các quả nặng trên để đưa chiếc cân đĩa cân bằng trở lại. Nếu có nhiều phương án, hãy in ra phương án sử dụng ít quả nặng nhất.

Input

Dữ liệu vào gồm hai số nguyên dương ~L~ và ~R~ (~L \le R~, ~R-L \le 100~). Bạn sẽ giải bài toán với mọi số nguyên dương ~x~ trong đoạn ~[L,R]~.

Output

Xuất ra ~R-L+1~ nhóm dòng, mỗi nhóm gồm 3 dòng:

Dòng ~1~: Một số nguyên dương ~k~ (~k \ge 1~) là số quả nặng cần dùng (bao gồm quả nặng ban đầu).
Dòng ~2~: Một số nguyên dương ~k_0~ (~k_0 \ge 1~), kế tiếp là ~k_0~ số nguyên dương mô tả các quả nặng ở đĩa cân bên trái. Các quả nặng được in ra theo thứ tự giảm dần về khối lượng, và bắt buộc phải có quả cân thứ 101.
Dòng ~3~: Một số nguyên dương ~k_1~ (~k_1\ge 1~, ~k_0+k_1=k~), kế tiếp là ~k_1~ số nguyên dương mô tả các quả nặng ở đĩa cân bên phải. Các quả nặng được in ra theo thứ tự giảm dần về khối lượng.

Ví dụ

Sample Input

25 27

Sample Output

Giải thích

~25 + 8 + 1 = 34~
~26 = 21 + 5~
~27 + 8 = 34 + 1~

Subtasks

Subtask 1 (20%): ~1 \le L \le R \le 5^1~
Subtask 2 (20%): ~1 \le L \le R \le 5^2~
Subtask 3 (20%): ~1 \le L \le R \le 5^4~
Subtask 4 (20%): ~1 \le L \le R \le 5^8~
Subtask 5 (20%): ~1 \le L \le R \le 5^{16}~

Định vị

Nộp bài

Giới hạn thời gian: 1.0s / Giới hạn bộ nhớ: 256M

Điểm: 3250

Trên biển có ba ngọn hải đăng không thẳng hàng. Ta coi mặt biển như một mặt phẳng toạ độ, ba ngọn hải đăng lần lượt nhận toạ độ ~\mathbf p_1 = (x_1,y_1)~, ~\mathbf p_2 = (x_2,y_2)~, ~\mathbf p_3 = (x_3,y_3)~. Trên mặt phẳng này tồn tại điểm duy nhất cách đều cả ba ngọn hải đăng (theo nghĩa Euclid), ta gọi điểm duy nhất đó là vị trí trung tâm.

Trên tay bạn là một radar, có nhiệm vụ trả về ngọn hải đăng gần nhất với một vị trí ~\mathbf p = (x,y)~ bất kỳ được chỉ định. Chỉ sử dụng chiếc radar đó, bạn hãy xác định vị trí trung tâm của ba ngọn hải đăng trên. Đáp án của bạn coi như hợp lệ nếu toạ độ mà bạn đưa ra đủ gần với toạ độ thực của vị trí trung tâm (mô tả chi tiết ở mục Cách tính điểm).

Tương tác

Đây là bài toán tương tác. Bạn sẽ không biết bất cứ thông tin gì ngoài giới hạn của các toạ độ.

Gửi truy vấn

Bạn sẽ gửi vào luồng xuất chuẩn stdout câu hỏi có dạng

@ x y

Trong đó, ~x~ là hoành độ, ~y~ là tung độ của điểm truy vấn ~(0 \le |x|, |y| \le 10^{20})~.

Lưu ý:

Sau mỗi truy vấn, cần flush stdout bằng câu lệnh cout << flush; hoặc các câu lệnh tương đương.
Thí sinh không được gửi quá ~10^6~ truy vấn.

Nhận kết quả truy vấn

Bạn sẽ đọc từ luồng nhập chuẩn stdin câu trả lời có dạng

Trong đó, ~r = 1, 2, 3~ là số hiệu của ngọn hải đăng gần điểm truy vấn nhất. Nếu có nhiều hơn một ngọn hải đăng có cùng khoảng cách ngắn nhất, ~r~ sẽ nhận ngẫu nhiên một trong các giá trị hợp lệ.

Gửi câu trả lời

Bạn sẽ gửi vào luồng xuất chuẩn stdout câu trả lời có dạng

! x y

Trong đó, ~x~ là hoành độ, ~y~ là tung độ của điểm truy vấn ~(0 \le |x|, |y| \le 10^{20})~.

Lưu ý:

Sau lệnh trả lời, cần flush stdout bằng câu lệnh cout << flush; hoặc các câu lệnh tương đương.

Cách tính điểm

Kỳ thực, tác giả cũng không biết vị trí trung tâm ấy nằm ở đâu, do đó cách tính điểm của bài này sẽ dựa trên tiêu chí “cách đều” của toạ độ đáp án so với toạ độ của ba ngọn hải đăng. Cụ thể, gọi

$$ \delta_1 = \| \mathbf p_1 - \mathbf p \| = \sqrt{(x_1-x)^2 + (y_1-y)^2} $$ $$ \delta_2 = \| \mathbf p_2 - \mathbf p \| = \sqrt{(x_2-x)^2 + (y_2-y)^2} $$ $$ \delta_3 = \| \mathbf p_3 - \mathbf p \| = \sqrt{(x_3-x)^2 + (y_3-y)^2} $$

Khi đó, chỉ số “cách đều” được tính bằng công thức

$$ \boxed{\Delta = \max\{ \delta_1, \delta_2, \delta_3 \} - \min\{ \delta_1, \delta_2, \delta_3 \}} $$

Giả sử một test có giá trị ~T~ điểm, khi đó điểm số của thí sinh là ~\max\{0; 1 - \Delta\} \times T~, làm tròn đến hai chữ số thập phân gần nhất.

Ví dụ

~\Delta = 1.441 - 1.438 < 0.01~. Thí sinh được ~100\%~ số điểm.

Giới hạn

~0 \le |x_1|,|y_1|,|x_3|,|y_3|,|x_3|,|y_3| \le 100~

Subtask

Gọi ~\alpha~ là góc lớn nhất trong tam giác tạo bởi ba ngọn hải đăng.

Subtask 1 (50%): ~\alpha = 90^\circ~
Subtask 2 (25%): ~60^\circ \le \alpha < 90^\circ~
Subtask 3 (25%): ~90^\circ < \alpha \le 135^\circ~

Lời giải ví dụ

#include <bits/stdc++.h>
using namespace std;

int ASK(long double x, long double y) {
    cout << "@ " << x << " " << y << endl << flush;
    int r; cin >> r;
    return r;
}

void ANSWER(long double x, long double y) {
    cout << "! " << x << " " << y << endl << flush;
    exit(0);
}

int main(void) {
    int nearest_to_centre = ASK(0, 0);
    ANSWER(0, 0);

    return 0;
}