USACO 2018 - Tháng 2 - Hạng Bạch Kim

Một trong những công việc đồng áng mà bác nông dân John ghét nhất là vận chuyển những lượng lớn phân bò. Để đơn giản hóa quá trình này, ông nghĩ ra một ý tưởng thú vị: thay vì chở phân giữa hai điểm bằng chiếc xe kéo phía sau máy kéo, tại sao không bắn nó qua không trung bằng một chiếc ná bắn phân khổng lồ? (quả thật, liệu có chuyện gì có thể xảy ra chứ...)

Trang trại của bác nông dân John nằm dọc theo một con đường thẳng rất dài, nên mỗi vị trí trong trang trại có thể được mô tả đơn giản bằng vị trí của nó trên con đường này (tương ứng với một điểm trên trục số). Bác nông dân John xây \(N\) chiếc ná (\(1 \leq N \leq 10^5\)), trong đó chiếc ná thứ \(i\) được mô tả bởi ba số nguyên \(x_i\), \(y_i\) và \(t_i\), cho biết chiếc ná này có thể bắn phân từ vị trí \(x_i\) đến vị trí \(y_i\) chỉ trong tổng cộng \(t_i\) đơn vị thời gian.

Bác nông dân John có \(M\) đống phân cần vận chuyển (\(1 \leq M \leq 10^5\)). Đống thứ \(j\) cần được chuyển từ vị trí \(a_j\) đến vị trí \(b_j\). Chở phân bằng máy kéo trên quãng đường \(d\) mất \(d\) đơn vị thời gian. Bác nông dân John hy vọng giảm được thời gian này bằng cách cho phép sử dụng tối đa một lần bất kỳ chiếc ná nào khi vận chuyển mỗi đống phân. Thời gian bác nông dân John di chuyển máy kéo mà không chở phân không được tính.

Với mỗi trong số \(M\) đống phân, hãy giúp bác nông dân John xác định thời gian vận chuyển nhỏ nhất có thể, biết rằng ông có thể dùng tối đa một chiếc ná trong quá trình vận chuyển.

Dữ liệu vào

Dòng đầu tiên chứa \(N\) và \(M\). Mỗi dòng trong \(N\) dòng tiếp theo mô tả một chiếc ná bằng các số nguyên \(x_i\), \(y_i\) và \(t_i\) (\(0 \leq x_i, y_i, t_i \leq 10^9\)). \(M\) dòng cuối mô tả các đống phân cần vận chuyển bằng các số nguyên \(a_j\) và \(b_j\).

Dữ liệu ra

In ra \(M\) dòng, mỗi dòng ứng với một đống phân và cho biết thời gian nhỏ nhất cần để vận chuyển đống phân đó.

Ví dụ

2 3
0 10 1
13 8 2
1 12
5 2
20 7

4
3
10

Nguồn

USACO 2018 February Contest, Platinum — Slingshot

Tác giả bài toán: Brian Dean.

Bác nông dân John nhận thấy đàn bò của mình có xu hướng tranh cãi nếu chúng bị nhốt quá gần nhau, vì vậy ông muốn mở một loạt chuồng bò mới để giúp chúng giãn ra.

Mỗi khi xây một chuồng bò mới, bác nông dân John nối nó với nhiều nhất một chuồng đã có bằng một lối đi hai chiều. Để bảo đảm đàn bò được phân tán đủ xa nhau, đôi khi ông muốn xác định khoảng cách từ một chuồng nhất định đến chuồng xa nhất có thể đi tới từ đó (khoảng cách giữa hai chuồng là số lối đi phải đi qua để từ chuồng này đến chuồng kia).

Bác nông dân John sẽ đưa ra tổng cộng \(Q\) truy vấn (\(1 \leq Q \leq 10^5\)), mỗi truy vấn thuộc loại “xây” hoặc “khoảng cách”. Với truy vấn xây, bác nông dân John xây một chuồng và nối nó với nhiều nhất một chuồng đã được xây trước đó. Với truy vấn khoảng cách, ông hỏi khoảng cách từ một chuồng nhất định đến chuồng xa nhất có thể đi tới từ đó qua một chuỗi các lối đi. Bảo đảm rằng chuồng được truy vấn đã được xây. Hãy giúp bác nông dân John trả lời tất cả các truy vấn này.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên \(Q\). Mỗi dòng trong \(Q\) dòng tiếp theo chứa một truy vấn. Mỗi truy vấn có dạng B p hoặc Q k, lần lượt yêu cầu xây một chuồng và nối nó với chuồng \(p\), hoặc cho biết khoảng cách xa nhất như đã định nghĩa từ chuồng \(k\). Nếu \(p = -1\) thì chuồng mới sẽ không được nối với chuồng nào khác. Nếu không, \(p\) là chỉ số của một chuồng đã được xây. Chỉ số các chuồng bắt đầu từ \(1\), nên chuồng được xây đầu tiên là chuồng \(1\), chuồng thứ hai là chuồng \(2\), và cứ tiếp tục như vậy.

Dữ liệu ra

In ra một dòng cho mỗi truy vấn khoảng cách. Lưu ý rằng một chuồng không nối với bất kỳ chuồng nào khác có khoảng cách xa nhất bằng \(0\).

Ví dụ

7
B -1
Q 1
B 1
B 2
Q 3
B 2
Q 2

0
2
1

  (1)
    \
     (2)---(4)
    /
  (3)

Nguồn

USACO 2018 February Contest, Platinum — New Barns

Tác giả bài toán: Anson Hu.

Chán cuộc sống nông trại, đàn bò đã bán hết mọi tài sản trần thế và gia nhập đoàn của một gánh xiếc lưu động. Cho đến nay, đàn bò chỉ được giao những tiết mục dễ dàng: tung hứng đuốc, đi dây, cưỡi xe một bánh — không có gì mà một cô bò khéo móng lại không xử lý được. Tuy nhiên, người quản lý gánh xiếc muốn tạo ra một tiết mục kịch tính hơn nhiều cho buổi diễn tiếp theo.

Sân khấu cho tiết mục mới gồm \(N\) bục được xếp thành một vòng tròn. Trên mỗi bục, từ \(1\) đến \(N\) cô bò phải xếp thành một chồng, cô nọ đứng trên cô kia. Khi người quản lý ra hiệu, tất cả các chồng phải đồng thời đổ theo chiều kim đồng hồ: cô bò dưới cùng trong một chồng không di chuyển, cô bò phía trên cô ấy di chuyển một bục theo chiều kim đồng hồ, cô bò tiếp theo di chuyển hai bục theo chiều kim đồng hồ, và cứ tiếp tục như vậy. Vì là những vận động viên thể dục điêu luyện, đàn bò biết rằng chúng sẽ không gặp khó khăn với khía cạnh kỹ thuật của tiết mục này. Các chồng bò khác nhau sẽ không “cản trở” nhau khi đổ, nên mọi cô bò đều sẽ đáp xuống bục dự định. Tất cả các cô bò đáp xuống cùng một bục tạo thành một chồng mới và chồng này không đổ tiếp.

Người quản lý cho rằng tiết mục sẽ đặc biệt kịch tính nếu sau khi các chồng đổ, chồng mới trên mỗi bục chứa đúng bằng số bò trong chồng ban đầu trên bục đó. Ta gọi một cấu hình kích thước các chồng là “kỳ diệu” nếu nó thỏa mãn điều kiện này. Hãy giúp đàn bò tính số cấu hình kỳ diệu. Vì số này có thể rất lớn, hãy tính phần dư của nó khi chia cho \(10^9 + 7\).

Hai cấu hình được xem là khác nhau nếu tồn tại bất kỳ bục nào mà hai cấu hình gán số bò khác nhau.

Dữ liệu vào

Dữ liệu vào gồm một số nguyên duy nhất \(N\) (\(1 \leq N \leq 10^{12}\)).

Dữ liệu ra

In ra một số nguyên duy nhất là số cấu hình kỳ diệu modulo \(10^9 + 7\).

Ví dụ

4

6

Nguồn

USACO 2018 February Contest, Platinum — Cow Gymnasts

Tác giả bài toán: Dhruv Rohatgi.