USACO 2012 - Tháng 12 - Hạng Vàng

Cuộc sống ở trang trại thật khắc nghiệt, và khi cuộc sống khắc nghiệt thì ta phải trở nên cứng rắn. Những con bò đã lập thành các băng nhóm (được đánh số thuận tiện từ \(1\) đến \(M\)). Các băng nhóm đã chung sống hòa bình trong một thời gian, nhưng giờ mọi chuyện thực sự đang vượt khỏi tầm kiểm soát!

Những con bò đang tranh giành quyền kiểm soát một cánh đồng cỏ rộng lớn. Cuộc xung đột này diễn ra trong một chuỗi các phút. Mỗi phút, một con bò đi vào cánh đồng. Nếu cánh đồng đang trống, băng nhóm của con bò mới được xem là giành quyền kiểm soát cánh đồng. Nếu cánh đồng đã do băng nhóm của con bò mới kiểm soát thì nó chỉ việc bắt đầu gặm cỏ. Nếu không, một con bò đang gặm cỏ thuộc băng nhóm kiểm soát sẽ đối đầu với con bò mới.

Những cuộc đối đầu giữa hai con bò bắt đầu bằng một hồi tranh cãi và chắc chắn kết thúc khi cả hai nhận ra rằng chúng giống nhau nhiều hơn là khác nhau biết bao. Nhận ra sai lầm của mình, hai con bò rời khỏi băng nhóm và cánh đồng, rồi đến quán rượu của FJ uống một ly sữa đậu nành lạnh. Nếu sau cuộc đối đầu này cánh đồng không còn con bò nào thì không băng nhóm nào kiểm soát cánh đồng.

Bessie hiểu những cuộc đối đầu này sẽ diễn ra như thế nào. Cô biết số lượng bò trong mỗi băng nhóm. Bessie rất muốn băng nhóm của mình kiểm soát cánh đồng sau khi cuộc xung đột kết thúc và tất cả bò hoặc ở trên cánh đồng hoặc ở quán rượu của FJ. Hãy giúp Bessie xác định liệu cuối cùng băng nhóm của cô, được đánh số \(1\), có thể kiểm soát cánh đồng hay không.

Nếu có thể, Bessie muốn biết số lượng lớn nhất bò thuộc băng nhóm của cô có thể còn ở trên cánh đồng khi kết thúc. Hãy in số này và thứ tự từ điển nhỏ nhất của các con bò để đạt được số bò đó từ băng nhóm của Bessie khi kết thúc. Một thứ tự \(X\) được xem là đứng trước \(Y\) theo thứ tự từ điển nếu tồn tại một \(k\) sao cho \(X[k] < Y[k]\) và \(X[i] = Y[i]\) với mọi \(i < k\).

Dữ liệu vào

• Dòng đầu tiên chứa \(N\) (\(1 \le N \le 100\)) và \(M\) (\(1 \le M \le N\)), cách nhau bởi dấu cách. Tổng số bò trong tất cả các băng nhóm là \(N\). Tổng số băng nhóm là \(M\).
• \(M\) dòng tiếp theo: dòng thứ \(1+i\) cho biết số thành viên trong băng nhóm \(i\). Mỗi băng nhóm có ít nhất \(1\) thành viên.

Dữ liệu ra

• Dòng đầu tiên in YES nếu băng nhóm của Bessie có thể kiểm soát cánh đồng sau cuộc xung đột. Nếu không, in NO trên một dòng.
• Nếu băng nhóm của Bessie có thể kiểm soát cánh đồng sau cuộc xung đột, dòng thứ hai in số lượng lớn nhất bò có thể còn ở trên cánh đồng.
• Nếu có thể, trong \(N\) dòng tiếp theo, dòng thứ \(i+2\) in chỉ số băng nhóm của con bò xuất hiện ở phút thứ \(i\) trong thứ tự từ điển nhỏ nhất mà vẫn để lại số lượng bò lớn nhất trên cánh đồng sau cuộc xung đột.

Ví dụ

5 3
2
1
2

YES
1
1
3
2
3
1

Nguồn

USACO 2012 December Contest, Gold — Problem 1: Gangs of Instanbull/Cowstantinople

Tác giả đề: Mark Gordon, 2012.

Bessie lại chơi với các xâu. Cô phát hiện rằng bằng cách thay đổi thứ tự bảng chữ cái, cô có thể khiến một số xâu đứng trước tất cả các xâu khác theo thứ tự từ điển.

Chẳng hạn, với các xâu "omm", "moo", "mom" và "ommnom", Bessie nhận thấy cô có thể khiến "mom" xuất hiện đầu tiên bằng bảng chữ cái tiêu chuẩn và có thể khiến "omm" xuất hiện đầu tiên bằng bảng chữ cái "abcdefghijklonmpqrstuvwxyz". Tuy nhiên, Bessie không tìm ra cách nào để khiến "moo" hoặc "ommnom" xuất hiện đầu tiên.

Hãy giúp Bessie xác định những xâu nào trong dữ liệu vào có thể đứng đầu theo thứ tự từ điển bằng cách sắp xếp lại thứ tự bảng chữ cái. Để xác định xâu \(X\) có đứng trước xâu \(Y\) theo thứ tự từ điển hay không, hãy tìm vị trí đầu tiên \(j\) mà hai ký tự tương ứng khác nhau. Nếu không có vị trí như vậy thì \(X\) đứng trước \(Y\) theo thứ tự từ điển khi \(X\) ngắn hơn \(Y\). Nếu có, \(X\) đứng trước \(Y\) theo thứ tự từ điển khi \(X[j]\) xuất hiện trước \(Y[j]\) trong bảng chữ cái.

Dữ liệu vào

• Dòng đầu tiên chứa một số nguyên \(N\) (\(1 \le N \le 30\,000\)), là số lượng xâu mà Bessie đang xét.
• \(N\) dòng tiếp theo, mỗi dòng chứa một xâu không rỗng. Tổng số ký tự trong tất cả các xâu không vượt quá \(300\,000\). Mọi ký tự trong dữ liệu vào đều là chữ cái thường từ a đến z. Dữ liệu vào không chứa hai xâu trùng nhau.

Dữ liệu ra

• Dòng đầu tiên chứa số nguyên \(K\), là số lượng xâu có thể đứng đầu theo thứ tự từ điển.
• \(K\) dòng tiếp theo: dòng thứ \(1+i\) chứa xâu thứ \(i\) trong số các xâu có thể đứng đầu theo thứ tự từ điển. Các xâu phải được in theo đúng thứ tự xuất hiện trong dữ liệu vào.

Ví dụ

4
omm
moo
mom
ommnom

2
omm
mom

Nguồn

USACO 2012 December Contest, Gold — Problem 2: First!

Tác giả đề: Mark Gordon, 2012.

Đã tới giờ cho uống nước ở nông trại của nông dân John (FJ), nhưng các con bò lại đang bỏ chạy!

FJ muốn tập trung chúng lại, và ông ta cần sự giúp đỡ của bạn. Nông trại của FJ là một dãy gồm có \(N\) \((1 \leq N \leq 200000)\) bãi cỏ được đánh số từ \(1 \ldots N\) và được nối bằn \(N-1\) con đường hai chiều. Chuồng bò nằm ở bãi cỏ thứ nhất, và từ bãi thứ nhất, ta có thể đi đến tất cả các bãi cỏ còn lại. Những con bò của FJ đang ở bãi cỏ của chúng vào sáng nay, nhưng không ai biết chúng đã đi đâu cho tới bây giờ. FJ biết rằng những con bò chỉ muốn chạy xa khỏi nhà chứa, nhưng cũng cũng rất lười nên không thể chạy một đoạn đường có độ dài lớn hơn \(L\) (theo hướng xa nhà chuồng). Với mỗi bãi cỏ, FJ muốn biết có bao nhiêu bãi cỏ mà những con bò bắt đầu tại bãi cỏ đó có thể dừng chân.

Lưu ý: Số dạng 64 bit (trong Pascal là int64, trong C/C++ là long long, và trong Java là long) cần dùng để lưu các khoảng cách.

Input

• Dòng đầu tiên ghi hai số nguyên \(N, L\) \((1 \leq N \leq 200000, \ 1 \leq L \leq 10^{18})\)
• \(N-1\) dòng tiếp theo, dòng thứ \(i\) ghi hai số \(p_i,l_i\) với \(p_i\) là bãi cỏ đầu tiên trên đường đi ngắn nhất từ \(i+1\) đến nhà chứa, \(l_i\) là khoảng cách con đường đó \((1 \leq p_i < i+1, \ 1 \leq l_i \leq 10^{12})\)

Output

• gồm \(N\) dòng, dòng thứ là số lượng bãi cỏ có thể đi tới được từ bằng cách rời xa nhà chứa (bãi cỏ 1) với độ dài không quá \(L\).

Example

4 5
1 4
2 3
1 5

3
2
1
1