BOI 2011 - Ngày 2

Hội Cứu Thế Giới triệu tập \(N\) thành viên đến một đại hội khẩn cấp để thống nhất kế hoạch cứu thế giới. Trong mỗi cuộc họp tại đại hội, những người tham dự đi đến quyết định chung theo quy trình sau:

1. Mỗi người có một đề xuất và dành \(P\) phút trình bày đề xuất đó cho những người còn lại.
2. Sau khi tất cả đã trình bày, họ bỏ phiếu chọn đề xuất tốt nhất; việc bỏ phiếu mất \(V\) phút.

Chẳng hạn, nếu trình bày một đề xuất mất một phút (\(P=1\)) và bỏ phiếu cũng mất một phút (\(V=1\)), cuộc họp có 100 người sẽ đi đến quyết định sau 101 phút.

Để đẩy nhanh quá trình, các thành viên quyết định chia thành nhiều nhóm và làm việc đồng thời. Mỗi nhóm chọn đề xuất tốt nhất trong nhóm theo quy trình trên. Sau đó, đại diện các nhóm họp với nhau và chọn kế hoạch cuối cùng trong số những đề xuất đã thắng ở từng nhóm.

Ví dụ, nếu 100 người chia thành hai nhóm có lần lượt 40 và 60 người, với \(P=V=1\), quá trình có thể diễn ra như sau:

• Nhóm lớn cần 61 phút để chọn đề xuất tốt nhất.
• Nhóm nhỏ cần 41 phút, rồi phải đợi nhóm lớn hoàn thành.
• Sau đó, hai đại diện gặp nhau, dành 2 phút trình bày và 1 phút bỏ phiếu.

Tổng thời gian là \(61+2+1=64\) phút.

Các nhóm còn có thể chia tiếp thành những nhóm nhỏ hơn; đôi khi chia thành nhiều hơn hai nhóm cũng có lợi. Đặc biệt, nhóm chỉ có một người quyết định ngay lập tức, vì người đó không cần trình bày đề xuất cho chính mình.

Cho thời gian trình bày \(P\) và thời gian bỏ phiếu \(V\), hãy tính thời gian ít nhất để \(N\) thành viên đi đến quyết định chung, khi họ tổ chức các nhóm và cuộc họp một cách tối ưu.

Dữ liệu vào

Dòng duy nhất chứa ba số nguyên \(N\), \(P\) và \(V\): số thành viên, thời gian trình bày một đề xuất và thời gian bỏ phiếu. Thời gian được tính bằng phút.

Dữ liệu ra

In một số nguyên \(M\), là số phút ít nhất để đại hội đi đến quyết định chung.

Ràng buộc

• \(1 \le N \le 10^{15}\).
• \(1 \le P,V \le 1\,000\).

Phân nhóm

• Trong các bộ dữ liệu có tổng cộng 40 điểm, \(1 \le N \le 5\,000\).
• Trong các bộ dữ liệu có tổng cộng 70 điểm, \(1 \le N \le 50\,000\); số điểm này bao gồm 40 điểm ở trên.
• 30 điểm còn lại không có ràng buộc bổ sung.

Ví dụ

9 1 1

8

6 1 2

8

6 2 1

12

Các thí sinh của Cuộc thi Lập trình Thế giới đã nộp \(N\) tệp lời giải \(f_1,\ldots,f_N\) lên hệ thống chấm. Trước khi công nhận kết quả cuối cùng, ban giám khảo muốn loại trừ mọi khả năng đạo văn. Họ có một chương trình nhận hai tệp và so sánh để xác định liệu chúng có quá giống nhau hay không.

Tuy nhiên, số tệp khá lớn nên so sánh mọi cặp sẽ mất quá nhiều thời gian. Mặt khác, có thể nhanh chóng bỏ qua nhiều cặp vì kích thước của hai tệp chênh lệch quá nhiều.

Cụ thể, ban giám khảo quyết định bỏ qua mọi cặp mà kích thước tệp nhỏ hơn chưa đạt 90% kích thước tệp lớn hơn. Do đó, chỉ cần kiểm tra những cặp tệp khác nhau \((f_i,f_j)\) thỏa mãn

Mỗi cặp tệp chỉ được tính một lần. Hãy viết chương trình tính số cặp phải kiểm tra.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên \(N\), là số tệp lời giải đã nộp.

Dòng thứ hai chứa \(N\) số nguyên \(\operatorname{size}(f_1),\ldots,\operatorname{size}(f_N)\), lần lượt là kích thước của từng tệp.

Dữ liệu ra

In một số nguyên duy nhất: số cặp tệp cần kiểm tra.

Ràng buộc

• \(1 \le N \le 100\,000\).
• \(1 \le \operatorname{size}(f_i) \le 100\,000\,000\).

Phân nhóm

• Trong các bộ dữ liệu có tổng cộng 50 điểm, \(1 \le N \le 2\,000\).
• 50 điểm còn lại không có ràng buộc bổ sung.

Ví dụ

2
2 1

0

5
1 1 1 1 1

10

Một đa giác đơn có \(N\) đỉnh được vẽ trên một lưới ô vuông vô hạn. Trong đa giác này, chỉ hai cạnh kề nhau mới tiếp xúc tại đỉnh chung; mọi cặp cạnh khác không cắt nhau và cũng không tiếp xúc. Tất cả các đỉnh nằm tại các điểm lưới, tức là có tọa độ nguyên.

Hãy tính tổng độ dài các đoạn thuộc những đường lưới nằm hoàn toàn bên trong đa giác, không tính phần nằm trên biên. Những đoạn cần tính được tô đậm trong các hình ví dụ.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên \(N\), là số đỉnh của đa giác.

Mỗi dòng trong \(N\) dòng tiếp theo chứa hai số nguyên \(x\) và \(y\), là tọa độ một đỉnh. Các đỉnh được cho theo chiều kim đồng hồ hoặc ngược chiều kim đồng hồ. Mọi đỉnh đều phân biệt, nhưng có thể có hơn hai đỉnh liên tiếp cùng nằm trên một đường thẳng.

Dữ liệu ra

In một số thập phân duy nhất: tổng độ dài các đoạn thuộc đường lưới nằm hoàn toàn bên trong đa giác.

Gọi kết quả bạn in là \(L\) và đáp án là \(R\). Kết quả được chấp nhận nếu thỏa mãn ít nhất một trong hai điều kiện:

• Sai số tương đối:

  \[ |L-R|\le R\cdot10^{-6}. \]

• Sai số tuyệt đối:

  \[ |L-R|\le10^{-6}. \]

Ràng buộc

• \(3 \le N \le 100\,000\).
• \(-500\,000\,000 \le x,y \le 500\,000\,000\).

Phân nhóm

• Trong các bộ dữ liệu có tổng cộng 50 điểm, tất cả các cạnh của đa giác nằm trên các đường lưới.
• 50 điểm còn lại không có ràng buộc bổ sung.

Ví dụ

3
5 1
2 4
1 1

10.0

5
0 0
-2 2
-2 -1
2 -2
2 0

12.5

Cho \(T\) là một cây có gốc, tức một đồ thị vô hướng liên thông không có chu trình, và \(S\) là một bản sao hoàn toàn giống \(T\).

Lấy hợp của \(T\) và \(S\), rồi gộp từng cặp đỉnh lá tương ứng của hai cây thành một đỉnh; tuyệt đối không gộp hai gốc. Ta gọi đồ thị thu được là một đồ thị phản chiếu cây.

Hãy viết chương trình xác định xem một đồ thị vô hướng liên thông cho trước có phải là đồ thị phản chiếu cây hay không.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên \(N\) và \(M\), là số đỉnh và số cạnh của đồ thị \(G\). Các đỉnh được đánh số từ \(1\) đến \(N\).

Mỗi dòng trong \(M\) dòng tiếp theo chứa hai số nguyên \(x\) và \(y\), mô tả một cạnh, với \(x\ne y\) và \(1\le x,y\le N\). Giữa mỗi cặp đỉnh có nhiều nhất một cạnh.

Dữ liệu ra

In YES nếu \(G\) là đồ thị phản chiếu cây; ngược lại, in NO.

Ràng buộc

• \(3 \le N,M \le 100\,000\).
• Đồ thị vô hướng và liên thông.

Phân nhóm

• Trong các bộ dữ liệu có tổng cộng 30 điểm, \(3 \le N,M \le 300\).
• Trong các bộ dữ liệu có tổng cộng 60 điểm, \(3 \le N,M \le 3\,500\); số điểm này bao gồm 30 điểm ở trên.
• 40 điểm còn lại không có ràng buộc bổ sung.

Ví dụ

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

NO

6 6
1 2
2 3
2 4
3 5
4 5
5 6

YES

22 28
13 8
8 1
1 22
1 12
1 14
13 18
13 4
4 20
20 7
13 15
15 3
15 9
9 16
9 19
22 5
12 5
14 5
5 11
11 6
18 6
7 10
10 17
17 6
3 21
21 6
16 2
19 2
2 21

YES