USACO 2014 - US Open - Hạng Đồng

Những cô bò của Farmer John đang đi du lịch bằng ô tô! Đồng hồ đo quãng đường trên xe hiển thị một giá trị nguyên, bắt đầu ở \(X\) dặm (\(100 \le X \le 10^{16}\)) khi chuyến đi bắt đầu và kết thúc ở \(Y\) dặm (\(X \le Y \le 10^{16}\)) khi chuyến đi kết thúc. Mỗi khi đồng hồ hiển thị một số "thú vị" (kể cả tại thời điểm bắt đầu và kết thúc chuyến đi), những cô bò sẽ rống lên. Một số được gọi là "thú vị" nếu, khi xét tất cả các chữ số của nó ngoại trừ các số \(0\) vô nghĩa ở đầu, mọi chữ số đều giống nhau ngoại trừ đúng một chữ số khác biệt. Ví dụ, các số \(33323\) và \(110\) là thú vị, còn các số \(9779\) và \(55555\) thì không.

Hãy giúp Farmer John đếm số lần những cô bò sẽ rống trong chuyến đi.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên \(X\) và \(Y\), cách nhau bởi một dấu cách.

Ràng buộc

• \(100 \le X \le Y \le 10^{16}\).
• Để lưu một số lớn tới \(10^{16}\), bạn cần dùng kiểu số nguyên 64 bit, chẳng hạn như long long trong C/C++.

Phân nhóm

• Trong một nửa số test, \(X \le Y \le 10^6\).

Dữ liệu ra

• In ra một số nguyên duy nhất là số lần những cô bò sẽ rống trong chuyến đi.

Ví dụ

110 133

13

Nguồn

USACO 2014 US Open, Bronze — Problem 1: Odometer

Tác giả đề: Brian Dean, 2014.

\(N\) con bò của Farmer John (\(1 \le N \le 100\,000\)) đang đứng tại nhiều vị trí khác nhau dọc theo một hàng rào dài một chiều. Con bò thứ \(i\) đứng tại vị trí \(x_i\) (một số nguyên trong đoạn từ \(0\) đến \(1\,000\,000\,000\)) và thuộc giống \(b_i\) (G nếu là giống Guernsey hoặc H nếu là giống Holstein). Không có hai con bò nào đứng cùng một vị trí.

Farmer John muốn chụp ảnh một đoạn liên tiếp gồm các con bò để mang đến hội chợ hạt, nhưng ông muốn tất cả các giống xuất hiện trong ảnh được đại diện một cách công bằng. Vì vậy, với những giống có mặt trong ảnh, ông muốn số bò của mỗi giống đều bằng nhau. Chẳng hạn, một bức ảnh chỉ có bò Holstein là hợp lệ; một bức ảnh có \(27\) bò Holstein và \(27\) bò Guernsey cũng hợp lệ; nhưng một bức ảnh có \(10\) bò Holstein và \(9\) bò Guernsey thì không hợp lệ.

Hãy giúp Farmer John chụp một bức ảnh công bằng bằng cách tìm kích thước lớn nhất của một bức ảnh thỏa mãn các điều kiện trên. Kích thước của bức ảnh là hiệu giữa vị trí lớn nhất và vị trí nhỏ nhất của các con bò trong ảnh. Farmer John có thể chỉ chụp một con bò; khi đó bức ảnh có kích thước bằng \(0\).

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên \(N\).
• \(N\) dòng tiếp theo, dòng thứ \(i\) chứa \(x_i\) và \(b_i\).

Ràng buộc

• \(1 \le N \le 100\,000\).
• \(0 \le x_i \le 1\,000\,000\,000\).
• \(b_i\) là G hoặc H.
• Không có hai con bò nào đứng cùng một vị trí.

Dữ liệu ra

• In ra một số nguyên duy nhất là kích thước lớn nhất của một bức ảnh công bằng.

Ví dụ

6
4 G
10 H
7 G
16 G
1 G
3 H

7

Nguồn

USACO 2014 US Open, Bronze — Problem 2: Fair Photography

Tác giả đề: Brian Dean, 2014.

Farmer John có \(N\) đồng cỏ (\(1 \le N \le 50\,000\)), được đánh số thuận tiện từ \(1\) đến \(N\), nối với nhau bằng \(M\) lối đi hai chiều (\(1 \le M \le 100\,000\)). Lối đi thứ \(i\) nối đồng cỏ \(A_i\) (\(1 \le A_i \le N\)) với đồng cỏ \(B_i\) (\(1 \le B_i \le N\)), trong đó \(A_i \ne B_i\). Có thể có hai lối đi nối cùng một cặp đồng cỏ.

Bessie quyết định trang trí các đồng cỏ nhân dịp sinh nhật Farmer John. Cô muốn đặt tại mỗi đồng cỏ một tấm biển lớn mang chữ F hoặc chữ J. Tuy nhiên, để Farmer John không bị nhầm lẫn, cô muốn bảo đảm rằng hai đồng cỏ được trang trí bằng hai chữ khác nhau nếu chúng được nối trực tiếp bởi một lối đi.

Công ty làm biển đòi Bessie trả nhiều tiền hơn cho biển chữ F so với biển chữ J, vì vậy Bessie muốn dùng nhiều biển chữ J nhất có thể. Hãy xác định số lượng biển chữ J lớn nhất, hoặc in ra \(-1\) nếu không tồn tại cách bố trí biển hợp lệ.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(M\).
• \(M\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(A_i\) và \(B_i\), cho biết có một lối đi hai chiều nối \(A_i\) với \(B_i\).

Ràng buộc

• \(1 \le N \le 50\,000\).
• \(1 \le M \le 100\,000\).
• \(1 \le A_i,B_i \le N\) và \(A_i \ne B_i\).
• Có thể có hai lối đi nối cùng một cặp đồng cỏ.

Dữ liệu ra

• In ra số lượng biển chữ J lớn nhất mà Bessie có thể dùng. Nếu không có cách bố trí biển hợp lệ, in ra \(-1\).

Ví dụ

4 4
1 2
2 3
3 4
4 1

2

Nguồn

USACO 2014 US Open, Bronze — Problem 3: Decorating the Pastures

Tác giả đề: Kalki Seksaria, 2014.