JOI 2022 - Open Contest - Bộ đề bài - LQDOJ: Le Quy Don Online Judge

#	Bài tập	Điểm	Thời gian:	Giới hạn bộ nhớ
1	JOI 2022 - Seesaw	100 (p)	2.0s	1G
2	JOI 2022 - Giraffes	100 (p)	7.0s	1G
3	JOI 2022 - School Road	100 (p)	2.0s	1G

1. JOI 2022 - Seesaw

Điểm: 100 (p) Thời gian: 2.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Một thanh thẳng dài \(10^9\) được đặt theo chiều từ trái sang phải. Có thể bỏ qua khối lượng của thanh. Trên thanh gắn \(N\) quả cân, mỗi quả có khối lượng bằng \(1\), tại các vị trí đôi một khác nhau. Quả cân thứ \(i\) \((1 \le i \le N)\) ở vị trí \(A_i\), nghĩa là cách đầu trái của thanh một khoảng \(A_i\).

Ban đầu, bạn có một chiếc hộp rộng \(w\). Bạn đặt thanh lên hộp để hộp đỡ đoạn từ vị trí \(l\) đến vị trí \(r\), kể cả hai đầu, với \(0 \le l < r \le 10^9\) và \(r=l+w\). Sau đó, không được thay đổi \(l\) và \(r\).

Tiếp theo, mỗi lần bạn tháo quả cân ngoài cùng bên trái hoặc ngoài cùng bên phải còn gắn trên thanh. Bạn thực hiện thao tác này \(N-1\) lần. Trong toàn bộ quá trình, kể cả trạng thái ban đầu và trạng thái cuối cùng, trọng tâm của các quả cân còn trên thanh phải nằm trong đoạn \([l,r]\). Nếu còn \(m\) quả cân ở các vị trí \(b_1,b_2,\ldots,b_m\), vị trí trọng tâm là

\[ \frac{b_1+b_2+\cdots+b_m}{m}. \]

Cho số quả cân \(N\) và các vị trí \(A_1,A_2,\ldots,A_N\), hãy tính chiều rộng nhỏ nhất có thể của hộp.

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
A_1 A_2 ... A_N

Dữ liệu ra

In một dòng chứa chiều rộng nhỏ nhất \(w\). Kết quả được chấp nhận nếu sai số tuyệt đối hoặc sai số tương đối không vượt quá \(10^{-9}\).

Kết quả phải có một trong hai dạng sau:

Số nguyên, ví dụ 123, 0, -2022.
Một số nguyên, tiếp theo là dấu chấm, rồi một dãy chữ số từ 0 đến 9, không có dấu phân cách hoặc khoảng trắng ở giữa. Không giới hạn số chữ số sau dấu chấm. Ví dụ 123.4, -123.00, 0.00288.

Ràng buộc

\(2 \le N \le 200\,000\).
\(0 \le A_1 < A_2 < \cdots < A_N \le 10^9\).

Chấm điểm

\(1\) điểm: \(N \le 20\)
\(33\) điểm: \(N \le 100\)
\(33\) điểm: \(N \le 2\,000\)
\(33\) điểm: Không có giới hạn bổ sung.

Ví dụ

Ví dụ 1

Input

3
1 2 4

Output

0.8333333333

Giải thích

Chọn \(w=\frac56\), \(l=\frac32\), \(r=\frac73\) và thực hiện như sau:

Ban đầu, trọng tâm ở \(\frac73\).
Lần đầu, tháo quả cân ngoài cùng bên phải, ở vị trí \(4\). Trọng tâm trở thành \(\frac32\).
Lần thứ hai, tháo quả cân ngoài cùng bên trái, ở vị trí \(1\). Trọng tâm trở thành \(2\).

Trọng tâm luôn nằm trong đoạn \([l,r]\). Không thể chọn hộp hẹp hơn \(\frac56\), nên in biểu diễn thập phân của \(\frac56\). Ví dụ này thỏa mãn mọi nhóm.

Ví dụ 2

Input

6
1 2 5 6 8 9

Output

1.166666667

Giải thích

Ví dụ này thỏa mãn mọi nhóm.

Nguồn

JOI Open Contest 2022, JCIOI. Bản dịch tiếng Việt theo CC BY-SA 4.0.

2. JOI 2022 - Giraffes

Điểm: 100 (p) Thời gian: 7.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Vườn thú IOI nổi tiếng với hươu cao cổ. Có \(N\) con hươu cao cổ, được đánh số từ \(1\) đến \(N\) theo thứ tự chiều cao tăng dần; chiều cao của chúng đôi một khác nhau. Có \(N\) chuồng xếp thành một hàng, đánh số từ \(1\) đến \(N\) từ trái sang phải. Mỗi chuồng có đúng một con hươu. Con hươu \(P_i\) sống trong chuồng \(i\).

Ông APIO, giám đốc vườn thú, lo lắng vì những đánh giá thấp với lý do "hươu cao cổ lên ảnh không đẹp". Cụ thể, khi chụp ảnh, khách chọn hai số nguyên \(l,r\) \((1 \le l \le r \le N)\) rồi chụp các con hươu trong các chuồng \(l,l+1,\ldots,r\). Bức ảnh không đẹp nếu đồng thời thỏa mãn hai điều kiện:

Có một con hươu trong ảnh cao hơn cả hai con ở hai đầu ảnh; tức là tồn tại \(k\) với \(l<k<r\) sao cho \(P_l<P_k>P_r\).
Có một con hươu trong ảnh thấp hơn cả hai con ở hai đầu ảnh; tức là tồn tại \(k\) với \(l<k<r\) sao cho \(P_l>P_k<P_r\).

Ông APIO muốn sắp xếp lại các con hươu sao cho ảnh không bị xấu với bất kỳ cách chọn \(l,r\) nào. Vì chuyển hươu giữa các chuồng rất vất vả, ông muốn số con hươu phải chuyển là nhỏ nhất. Sau khi sắp xếp, mỗi chuồng vẫn phải có đúng một con hươu.

Cho vị trí hiện tại của các con hươu, hãy tính số con ít nhất phải chuyển. Vì cách sắp xếp hiện tại do ông APIO chọn ngẫu nhiên, có thể giả sử các giá trị \(P_i\) được sinh ngẫu nhiên như mô tả ở mục Cách sinh dữ liệu.

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
P_1 P_2 ... P_N

Dữ liệu ra

In một dòng chứa số con hươu ít nhất phải chuyển.

Ràng buộc

\(1 \le N \le 8\,000\).
\(1 \le P_i \le N\) \((1 \le i \le N)\).
\(P_i \ne P_j\) \((1 \le i<j \le N)\).
Các giá trị \(P_i\) được sinh ngẫu nhiên theo cách dưới đây.

Chấm điểm

\(10\) điểm: \(N \le 7\)
\(22\) điểm: \(N \le 13\)
\(27\) điểm: \(N \le 300\)
\(41\) điểm: Không có giới hạn bổ sung.

Cách sinh dữ liệu

Không kể các ví dụ, có \(10\) bộ dữ liệu thỏa mãn cả bốn nhóm; \(10\) bộ chỉ thỏa mãn các nhóm \(2,3,4\); \(10\) bộ chỉ thỏa mãn các nhóm \(3,4\); và \(10\) bộ chỉ thỏa mãn nhóm \(4\). Tính cả ví dụ, có tổng cộng \(44\) bộ dữ liệu dùng để chấm. Cả \(44\) bộ đều được sinh như sau:

Chọn \(N\) thỏa mãn giới hạn của nhóm tương ứng.
Chọn ngẫu nhiên đều một hoán vị \((P_1,P_2,\ldots,P_N)\) trong \(N!=1\times2\times\cdots\times N\) hoán vị hợp lệ. Mọi hoán vị có xác suất được chọn như nhau.

Ví dụ

Ví dụ 1

Input

6
5 4 6 1 3 2

Output

Giải thích

Thứ tự từ trái sang phải là \(5,4,6,1,3,2\). Ảnh ứng với \(l=2,r=5\) không đẹp: con trong chuồng \(3\) cao hơn cả hai con trong chuồng \(2\) và \(5\), còn con trong chuồng \(4\) thấp hơn cả hai con đó.

Chuyển con hươu \(1\) từ chuồng \(4\) sang chuồng \(1\) và con hươu \(5\) từ chuồng \(1\) sang chuồng \(4\) thì mọi ảnh đều không bị xấu. Cần chuyển \(2\) con và đây là số nhỏ nhất. Ví dụ thỏa mãn mọi nhóm.

Ví dụ 2

Input

4
4 1 3 2

Output

Giải thích

Với thứ tự \(4,1,3,2\), mọi ảnh đều không bị xấu, nên không cần chuyển con nào. Ví dụ thỏa mãn mọi nhóm.

Ví dụ 3

Input

7
3 1 6 7 4 2 5

Output

Giải thích

Có thể sắp thành \(3,5,6,7,4,2,1\). Khi đó mọi ảnh đều không bị xấu. Cần chuyển \(2\) con và đây là số nhỏ nhất. Ví dụ thỏa mãn mọi nhóm.

Ví dụ 4

Input

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

Output

Giải thích

Ví dụ này thỏa mãn các nhóm \(2,3,4\).

Nguồn

JOI Open Contest 2022, JCIOI. Bản dịch tiếng Việt theo CC BY-SA 4.0.

3. JOI 2022 - School Road

Điểm: 100 (p) Thời gian: 2.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Đất nước Hải Ly có \(N\) thành phố, đánh số từ \(1\) đến \(N\), và \(M\) con đường, đánh số từ \(1\) đến \(M\). Đường \(i\) nối hai chiều giữa thành phố \(A_i\) và \(B_i\), có độ dài \(C_i\). Có thể đi từ bất kỳ thành phố nào đến bất kỳ thành phố nào khác qua một số con đường.

Hải ly Bitaro sống ở thành phố \(1\) và học ở thành phố \(N\). Cậu thường đến trường theo một lộ trình cố định có độ dài \(L\), trong đó \(L\) là khoảng cách ngắn nhất từ thành phố \(1\) đến thành phố \(N\).

Hôm nay trời đẹp, Bitaro muốn đi đường vòng về nhà: từ thành phố \(N\) về thành phố \(1\) theo một lộ trình dài hơn \(L\). Vì dễ chán, cậu không muốn ghé cùng một thành phố nhiều lần. Do đó, trên đường về, cậu không được ghé một thành phố quá một lần và không được quay ngược lại giữa đường.

Cho thông tin về các thành phố và con đường, hãy xác định có tồn tại đường vòng từ trường về nhà thỏa mãn yêu cầu hay không.

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
A_1 B_1 C_1
A_2 B_2 C_2
...
A_M B_M C_M

Dữ liệu ra

In 1 nếu tồn tại lộ trình từ trường về nhà dài hơn \(L\) mà không ghé thành phố nào quá một lần. Nếu không, in 0.

Ràng buộc

\(2 \le N \le 100\,000\).
\(1 \le M \le 200\,000\).
\(1 \le A_i<B_i \le N\) \((1 \le i \le M)\).
\(1 \le C_i \le 10^9\) \((1 \le i \le M)\).
Có thể đi từ bất kỳ thành phố nào đến bất kỳ thành phố nào khác qua một số con đường.

Chấm điểm

\(7\) điểm: \(M \le 40\)
\(15\) điểm: \(N \le 18\)
\(23\) điểm: \(M-N \le 13\)
\(35\) điểm: Với ba thành phố đôi một khác nhau \(a,b,c\) bất kỳ, tồn tại một lộ trình từ \(a\) đến \(c\) không đi qua \(b\).
\(20\) điểm: Không có giới hạn bổ sung.

Ví dụ

Ví dụ 1

Input

Output

Giải thích

Khoảng cách ngắn nhất từ nhà ở thành phố \(1\) đến trường ở thành phố \(4\) là \(5\). Có hai lộ trình về nhà không lặp thành phố:

Đi các đường \(3 \to 1\), qua các thành phố \(4 \to 2 \to 1\), dài \(5\).
Đi các đường \(4 \to 2\), qua các thành phố \(4 \to 3 \to 1\), dài \(5\).

Không có lộ trình dài hơn \(5\), nên in 0. Ví dụ thỏa mãn mọi nhóm.

Ví dụ 2

Input

Output

Giải thích

Khoảng cách ngắn nhất vẫn là \(5\). Hai lộ trình không lặp thành phố là:

Đi các đường \(3 \to 1\), qua các thành phố \(4 \to 2 \to 1\), dài \(5\).
Đi các đường \(4 \to 2\), qua các thành phố \(4 \to 3 \to 1\), dài \(6\).

Có lộ trình dài hơn \(5\), nên in 1. Ví dụ thỏa mãn mọi nhóm.

Ví dụ 3

Input

Output

Giải thích

Ví dụ này thỏa mãn các nhóm \(1,2,3,5\).

Ví dụ 4

Input

Output

Giải thích

Ví dụ này thỏa mãn mọi nhóm.

Ví dụ 5

Input

12 17
2 4 656247308
4 6 106088453
1 5 754343261
9 12 497827261
3 8 759830309
3 4 61084725
1 6 324702188
3 6 415317430
7 12 846175092
5 8 278621369
1 10 891247646
10 12 755236904
6 8 511967203
5 6 597197970
1 7 800309458
7 9 348347831
10 11 134217757

Output

Giải thích

Ví dụ này thỏa mãn các nhóm \(1,2,3,5\).

Nguồn

JOI Open Contest 2022, JCIOI. Bản dịch tiếng Việt theo CC BY-SA 4.0.