JOI 2021 - Tuyển chọn mùa xuân - Ngày 1

Đây là bài chỉ nộp kết quả (Output Only).

Bitaro sẽ tham gia một cuộc thi bay nhào lộn. Máy bay của cậu giữ nguyên độ cao và bay qua các điểm kiểm tra. Ta biểu diễn khu vực bay bằng một mặt phẳng tọa độ. Có \(N\) điểm kiểm tra, đánh số từ \(1\) đến \(N\); điểm \(i\) có tọa độ \((X_i,Y_i)\).

Máy bay phải đi qua mỗi điểm kiểm tra đúng một lần theo cách sau:

1. Bitaro chọn một điểm kiểm tra làm điểm xuất phát.
2. Lặp lại \(N-1\) lần: chọn một điểm kiểm tra chưa được chọn, rồi bay thẳng từ điểm hiện tại tới điểm đó.
3. Khi đến điểm kiểm tra cuối cùng, chuyến bay kết thúc.

Trong bước \(2\), điểm xuất phát được coi là đã chọn. Máy bay phải bay thẳng giữa hai điểm kiểm tra liên tiếp; không được bay theo đường cong hoặc đổi hướng giữa chừng.

Lộ trình là một đường gấp khúc. Máy bay đổi hướng không quá \(N-2\) lần. Nếu góc của đường gấp khúc tại một điểm kiểm tra nhỏ, máy bay phải đổi hướng nhiều tại đó, làm tăng nguy cơ gặp sự cố. Vì vậy, Bitaro muốn góc nhỏ nhất tại \(N-2\) điểm kiểm tra, không kể điểm đầu và điểm cuối, lớn nhất có thể.

Cho tọa độ các điểm kiểm tra, hãy tìm thứ tự đi qua chúng sao cho góc nhỏ nhất của đường gấp khúc lớn nhất có thể.

Dữ liệu vào

Mỗi tệp đầu vào có dạng sau; tất cả các giá trị đều là số nguyên. \(Z_0\) là tham số dùng bởi trình chấm.

N Z_0
X_1 Y_1
...
X_N Y_N

Dữ liệu ra

Kết quả gồm \(N\) dòng. Dòng thứ \(k\) chứa số nguyên \(P_k\) \((1 \le P_k \le N)\), là điểm kiểm tra thứ \(k\) trong lộ trình. Điểm xuất phát là \(P_1\).

Nộp bài

Nộp các tệp kết quả output_01.txt, output_02.txt, ..., output_06.txt tương ứng với các tệp đầu vào input_01.txt, input_02.txt, ..., input_06.txt.

Ràng buộc

• \(3 \le N \le 1\,000\).
• \(\sqrt{X_i^2+Y_i^2} \le 10\,000\,000\) \((1 \le i \le N)\).
• \((X_i,Y_i) \ne (X_j,Y_j)\) \((1 \le i<j \le N)\).
• \(1 \le Z_0 \le 179\).

Thư viện

Tệp aerobatics.h trong gói phát cho thí sinh chứa hàm tính góc tạo bởi ba điểm:

double GetAngle(int xa, int ya, int xb, int yb, int xc, int yc);

Hàm trả về góc \(BAC\) theo đơn vị độ, với sai số đủ nhỏ. Chú ý thứ tự tham số:

• xa, ya là hoành độ và tung độ của điểm \(A\), tức đỉnh của góc.
• xb, yb là hoành độ và tung độ của điểm \(B\).
• xc, yc là hoành độ và tung độ của điểm \(C\).
• Nếu \(A\) trùng \(B\) hoặc \(A\) trùng \(C\), hành vi của hàm không được xác định.

Bạn có thể sử dụng và sửa đổi hàm GetAngle trong chương trình tạo lời giải của mình. Hàm được cung cấp giống hàm mà trình chấm sử dụng. Đây là thư viện hỗ trợ tạo kết quả, không phải hàm mà thí sinh cần cài đặt để nộp mã nguồn.

Chấm điểm

Mỗi tệp kết quả không hợp lệ được \(0\) điểm. Chẳng hạn, nếu dãy \(P_1,P_2,\ldots,P_N\) không phải là hoán vị của \(1,2,\ldots,N\), hoặc sai định dạng, tệp đó được \(0\) điểm.

Với kết quả hợp lệ, gọi \(Z\) là góc nhỏ nhất, tính bằng độ, tại \(N-2\) điểm trung gian của lộ trình, và \(S\) là điểm tối đa của tệp tương ứng. Điểm nhận được là:

• \(S\) nếu \(Z \ge Z_0\).
• \(S\times\dfrac{f(Z/180)}{f(Z_0/180)}\) nếu \(Z<Z_0\).

Trong đó, với \(0 \le \alpha \le 1\),

Điểm của bài là tổng điểm của sáu tệp, sau đó làm tròn đến số nguyên gần nhất.

Ví dụ

7 90
3 1
2 5
0 2
-1 6
-3 1
-1 -4
4 -2

5
3
1
7
6
4
2

Nguồn

JOI 2021 Spring Training Camp, Contest 1, JCIOI. Bản dịch tiếng Việt và hình trích từ đề chính thức theo CC BY-SA 4.0.

Vương quốc JOI được biểu diễn bằng mặt phẳng tọa độ \(xy\). Có \(N\) ngôi nhà, đánh số từ \(1\) đến \(N\). Nhà \(i\) có tọa độ \((X_i,Y_i)\); các nhà ở những vị trí đôi một khác nhau. Mỗi nhà có một người dân sinh sống. Người sống trong nhà \(i\) được gọi là người dân \(i\).

Một kỳ nghỉ dài bắt đầu. Tại thời điểm \(0\), tất cả mọi người rời nhà để đi du lịch. Mỗi người chọn một hướng cố định trong bốn hướng đông, tây, nam, bắc ngay từ đầu, rồi di chuyển như sau:

• Chọn đông: đi theo chiều dương trục \(x\) với vận tốc \(1\). Tại thời điểm \(t \ge 0\), người \(i\) ở \((X_i+t,Y_i)\).
• Chọn tây: đi theo chiều âm trục \(x\) với vận tốc \(1\). Tại thời điểm \(t \ge 0\), người \(i\) ở \((X_i-t,Y_i)\).
• Chọn nam: đi theo chiều âm trục \(y\) với vận tốc \(1\). Tại thời điểm \(t \ge 0\), người \(i\) ở \((X_i,Y_i-t)\).
• Chọn bắc: đi theo chiều dương trục \(y\) với vận tốc \(1\). Tại thời điểm \(t \ge 0\), người \(i\) ở \((X_i,Y_i+t)\).

Không may, tại thời điểm \(0\), người dân \(1\) mắc căn bệnh truyền nhiễm mới được phát hiện mang tên sốt IOI. Ban đầu không có ai khác mắc bệnh. Bệnh lây theo quy tắc sau: nếu tại một thời điểm, hai người \(a,b\) có cùng tọa độ, người \(a\) đã mắc bệnh còn người \(b\) chưa mắc, thì người \(b\) cũng mắc bệnh ngay lúc đó.

Bệnh không lây bằng bất kỳ cách nào khác. Đây là bệnh không thể chữa khỏi, nên người đã mắc bệnh sẽ không hồi phục.

Là một bộ trưởng, bạn cần ước tính tình huống xấu nhất. Cho số nhà và tọa độ từng nhà, hãy tính số người mắc bệnh lớn nhất có thể tại thời điểm \(10^{100}\), xét tất cả các cách chọn hướng của mọi người.

Dữ liệu vào

Đọc từ đầu vào chuẩn, tất cả các giá trị đều là số nguyên:

N
X_1 Y_1
...
X_N Y_N

Dữ liệu ra

In một dòng chứa số người mắc bệnh lớn nhất có thể tại thời điểm \(10^{100}\).

Ràng buộc

• \(1 \le N \le 100\,000\).
• \(0 \le X_i,Y_i \le 500\,000\,000\) \((1 \le i \le N)\).
• \((X_i,Y_i) \ne (X_j,Y_j)\) \((1 \le i<j \le N)\).

Chấm điểm

Trong bảng dưới, "hoành độ và tung độ đôi một khác nhau" nghĩa là \(X_i\ne X_j\) và \(Y_i\ne Y_j\) với mọi \(1\le i<j\le N\).

1. \(5\) điểm: \(N\le7\); hoành độ và tung độ đôi một khác nhau.
2. \(8\) điểm: \(N\le15\); hoành độ và tung độ đôi một khác nhau.
3. \(6\) điểm: \(N\le100\); hoành độ và tung độ đôi một khác nhau; \(X_1=Y_1=0\).
4. \(6\) điểm: \(N\le100\); hoành độ và tung độ đôi một khác nhau.
5. \(12\) điểm: \(N\le3\,000\).
6. \(32\) điểm: Hoành độ và tung độ đôi một khác nhau.
7. \(31\) điểm: Không có giới hạn bổ sung.

Ví dụ

2
0 0
4 3

1

3
1 2
2 1
4 3

3

2
20 20
20 21

2

15
5 6
2 9
12 0
4 11
3 12
6 5
0 8
9 10
11 13
8 7
13 2
1 1
7 14
10 4
14 3

9

30
275810186 246609547
122805872 99671769
243507947 220373844
281305347 252104708
237805644 214671541
172469077 149334974
222589229 229887956
160653451 208404690
241378966 211098219
144302355 224755786
186392385 163258282
199129390 169928751
294937491 265736852
196096122 172962019
314342944 285142305
202720470 166337671
157037485 133903382
263858979 240724876
210720220 181519581
296402036 267201397
186021287 183036854
195081930 173976211
328293029 299092390
261195361 238061258
323595085 294394446
299933764 270733125
240976723 128081418
188501753 165367650
277832422 248631783
119896220 96762117

11

Nguồn

JOI 2021 Spring Training Camp, Contest 1, JCIOI. Bản dịch tiếng Việt và hình trích từ đề chính thức theo CC BY-SA 4.0.

Trung tâm IOI là một cơ sở huấn luyện có chỗ ở và khu ẩm thực phục vụ các đoàn đông người. Khu ẩm thực có \(N\) cửa hàng xếp thành một hàng, đánh số từ \(1\) đến \(N\). Trước mỗi cửa hàng có một hàng đợi cho khách.

Hôm nay có \(M\) đoàn lưu trú tại trung tâm, đánh số từ \(1\) đến \(M\). Thành viên các đoàn xếp hàng theo một cách khá lạ để trò chuyện với nhau. Đôi khi cửa hàng tặng món tráng miệng miễn phí cho một khách trong hàng. JOI-kun làm việc tại đây, có nhiệm vụ ghi lại đoàn của từng người nhận quà.

Trước khi mở cửa, các hàng đợi đều trống. Trong ngày xảy ra \(Q\) sự kiện theo thứ tự. Sự kiện thứ \(i\) thuộc một trong ba loại:

• Vào hàng (Join): Với mỗi cửa hàng có số từ \(L_i\) đến \(R_i\), kể cả hai đầu, có \(K_i\) khách thuộc đoàn \(C_i\) vào cuối hàng đợi.
• Rời hàng (Leave): Với mỗi cửa hàng có số từ \(L_i\) đến \(R_i\), nếu có ít nhất \(K_i\) khách trong hàng thì \(K_i\) người đầu hàng rời đi; nếu không thì tất cả khách trong hàng rời đi.
• Phục vụ (Service): Nếu hàng của cửa hàng \(A_i\) có ít nhất \(B_i\) khách, cửa hàng tặng món tráng miệng cho người thứ \(B_i\) tính từ đầu hàng. Nếu không thì nhân viên cửa hàng ăn món đó.

JOI-kun làm mất bản ghi các đoàn của những người nhận quà. Cậu muốn khôi phục nó từ thông tin về \(Q\) sự kiện. Với mỗi sự kiện Phục vụ, hãy xác định có khách nhận quà hay không; nếu có, hãy tìm số hiệu đoàn của người đó.

Dữ liệu vào

Đọc từ đầu vào chuẩn, tất cả các giá trị đều là số nguyên:

N M Q
(Sự kiện 1)
...
(Sự kiện Q)

Mỗi dòng sự kiện bắt đầu bằng số nguyên \(T_i\):

• 1 L_i R_i C_i K_i: Vào hàng. Thêm \(K_i\) người thuộc đoàn \(C_i\) vào cuối hàng của mỗi cửa hàng từ \(L_i\) đến \(R_i\).
• 2 L_i R_i K_i: Rời hàng. Cho \(K_i\) người đầu hàng rời đi ở mỗi cửa hàng từ \(L_i\) đến \(R_i\), hoặc cho tất cả rời đi nếu hàng có ít hơn \(K_i\) người.
• 3 A_i B_i: Phục vụ. Tặng quà cho người thứ \(B_i\) trong hàng của cửa hàng \(A_i\) nếu người đó tồn tại; nếu không thì nhân viên ăn quà.

Dữ liệu ra

Với mỗi sự kiện có \(T_i=3\), theo đúng thứ tự xảy ra, in một dòng chứa số hiệu đoàn của người nhận quà; in 0 nếu nhân viên cửa hàng ăn món tráng miệng.

Ràng buộc

• \(1 \le N,M,Q \le 250\,000\).
• \(T_i\) thuộc \(\{1,2,3\}\).
• Nếu \(T_i=1\): \(1 \le L_i \le R_i \le N\), \(1 \le C_i \le M\), \(1 \le K_i \le 10^9\).
• Nếu \(T_i=2\): \(1 \le L_i \le R_i \le N\), \(1 \le K_i \le 10^9\).
• Nếu \(T_i=3\): \(1 \le A_i \le N\), \(1 \le B_i \le 10^{15}\).
• Có ít nhất một sự kiện với \(T_i=3\).

Chấm điểm

1. \(2\) điểm: \(N,Q\le2\,000\); \(K_i=1\) với mọi sự kiện Vào hàng hoặc Rời hàng.
2. \(5\) điểm: \(N,Q\le2\,000\).
3. \(7\) điểm: \(N,Q\le65\,000\); \(R_i-L_i\le10\) và \(K_i=1\) với mọi sự kiện Vào hàng.
4. \(21\) điểm: \(M=1\).
5. \(15\) điểm: \(N,Q\le65\,000\); \(K_i=1\) với mọi sự kiện Vào hàng hoặc Rời hàng.
6. \(13\) điểm: \(N,Q\le65\,000\); chỉ có sự kiện Vào hàng và Phục vụ.
7. \(26\) điểm: \(N,Q\le65\,000\).
8. \(11\) điểm: Không có giới hạn bổ sung.

Ví dụ

3 5 7
1 2 3 5 2
1 1 2 2 4
3 2 3
2 1 3 3
3 1 2
1 2 3 4 2
3 3 2

2
0
4

3 4 7
1 1 2 1 1
1 1 3 4 1
2 2 3 1
2 1 3 1
1 1 2 2 1
3 1 1
3 3 2

4
0

183326 218318 22
1 106761 160918 151683 574906362
3 68709 1
1 29240 156379 22166 957318472
1 14054 181502 82845 97183925
2 112033 122908 587808357
2 57819 160939 215041262
3 36674 524274467
1 35854 69866 32334 322730299
1 1384 7230 115069 454256926
1 44192 158235 8750 84192710
3 54457 1077490708
2 10592 110384 979714505
2 44594 79244 311724477
3 160965 97183926
1 88748 101697 39148 373927458
3 41166 58039001
1 91501 137591 205480 958877326
2 77775 169655 135756956
1 12497 57047 60918 15666764
1 47839 51716 144688 732270998
3 114514 774994894
3 48645 169986425

0
22166
32334
0
82845
8750
60918

Nguồn

JOI 2021 Spring Training Camp, Contest 1, JCIOI. Bản dịch tiếng Việt theo CC BY-SA 4.0.