FIND THE COW!

Cô bò Bessie đã trốn thoát và đang trốn ở một đồi núi với những đồng cỏ cao. Nông dân John (FJ), người đang muốn tìm kiếm Bessie, đã quyết định bò trên đồng cỏ bằng tay và đầu gối để tìm ra dấu vết của Bessie. Không may thay, ông ta có một chút vấn đề với việc tìm kiếm Bessie: Dãy cỏ ở trước mặt FJ trông như một chuỗi ngoặc đơn có độ dài N (1≤ N≤ 50,000); ví dụ: )((()())()) FJ biết rằng chân sau của Bessie giống như một cặp dấu mở ngoặc đơn ((, và chân trước của cô ta giống như một cặp dấu đóng ngoặc đơn )). Vị trí của Bessie có thể được diễn tả bởi một cặp x < y , trong đó (( được tìm ở vị trí x, và )) được tìm ở vị trí y. Hãy đếm có bao nhiêu vị trí mà Bessie có thể đang đứng.

Dữ liệu vào: ghi từ tệp COWFIND.INP

+ Dòng 1: Một chuỗi ngoặc đơn có độ dài là N

Dữ liệu ra: ghi vào tệp văn bản COWFIND.OUT một số nguyên cho biết vị trí Bessise đang đứng

Ví dụ:

COWFIND.INP	COWFIND.OUT
)((()())())	4

Giải thích: Các vị trí Bessise có thể đứng là

1. )((()())())

2. )((()())())

3. )((()())())

4. )((()())())

TEST

DÃY SỐ

Steve không tập trung tư tưởng trong giờ toán vì vậy thầy giáo cho thêm bài tập về nhà rèn luyện khả năng tập trung tư tưởng và tính cẩn thận chu đáo.

Nội dung bài tập là cho n xâu chỉ bao gồm các ký tự la tinh thường và chữ số. Đoạn các ký tự số liên tục tạo thành một số nguyên. Ở mỗi đoạn ký tự số liên tục Steve phải trích ra số lớn nhất có thể, sắp xếp các số nhận được từ các xâu đã cho và đưa ra theo thứ tự không giảm, mỗi số được đưa ra dưới dạng không có các số 0 không có nghĩa.

Ví dụ, với n = 1 và xâu là 01a2b3456cde478 dãy số cần đưa ra là 1, 2, 478, 3456.

Yêu cầu: Cho số nguyên n (1 ≤ n ≤ 100) và n xâu, mỗi xâu có độ dài không quá 100. Hãy đưa ra dãy số nhận được đã sắp xếp theo thứ tự không giảm, mỗi số trên một dòng.

Dữ liệu: Vào từ file văn bản NUMBERS.INP:

+ Dòng đầu tiên chứa số nguyên n,

+ Mỗi dòng trong n dòng sau chứa một xâu chỉ gồm các ký tự la tinh thường và số.

Dữ liệu đảm bảo có không quá 500 số được tách ra.

Kết quả: Đưa ra file văn bản NUMBERS.OUT dãy số nhận được đã sắp xếp theo thứ tự không giảm, mỗi số trên một dòng.

Ví dụ:

NUMBERS.INP	NUMBERS.OUT
4 43silos0 zita002 le2sim 231233	0 2 2 43 231233

TEST - CODE

COWS IN A ROW

Nguồn bài: http://www.usaco.org/index.php?page=viewproblem2&cpid=130

Nông dân John (FJ) có N con bò (1 <= N <= 1000) đang xếp hàng thành một đường thẳng. Mỗi con bò được định dạng bằng một số tự nhiên là “mã giống”, mã định dạng của con bò thứ i trong dãy là B(i). FJ suy nghĩ rằng dãy các con bò này sẽ càng ấn tượng hơn nếu như có một nhóm các con bò có cũng mã giống đứng cạnh nhau. Để thực hiện được điều này, FJ quyết định loại bỏ những con bò có mã giống được ông ta chỉ định. Hãy giúp FJ tìm ra độ dài lớn nhất của dãy các con bò có cùng mã giống mà ông ta có thể xếp được bằng cách bỏ các con bò có cùng mã giống mà ông ta chỉ định.

Dữ liệu vào từ tệp: COWROW.INP

+ Dòng 1: Số tự nhiên N

+ Dòng 2..1+N: Dòng thứ i+1 chứa số B(i) là mã giống của i nằm trong khoảng 0..1,000,000

Dữ liệu ra: ghi vào tệp COWROW.OUT  là 1 số nguyên cho biết độ dài lớn nhất của một nhóm các con bò có cùng mã giống mà FJ có thể tạo được.

Ví dụ:

COWROW.INP	COWROW.OUT	Giải thích
9 2 7 3 7 7 3 7 5 7	4	Bằng cách bỏ các con bò có mã giống là 3, dãy các con bò còn lại sẽ là 2, 7, 7, 7, 7, 5, 7. Trong hàng mới, độ dài lớn nhất là 4 của các con bò có mã giống là 7

TEST - CODE

ĐẾM VÙNG

Một khu vườn hình chữ nhật được chia thành MxN ô đơn vị. Các dòng đánh số từ 1 tới M từ trên xuống dưới, các cột đánh số từ 1 đến N từ trái sang phải. Ô nằm ở hàng i, cột j được gọi là ô (i,j). Người ta có đắp K lối đi trên mảnh vườn đó, lối đi thứ i là một dãy các ô liên tiếp nhau theo đường ngang hoặc đường dọc, và được cho bởi 4 số nguyên dương x_i, y_i, z_i và t_i trong đó (x_­i­, y_i) là vị trí của ô đầu, còn (z_i­, t_i) là vị trí của ô cuối của lối đi. Các lối đi chia khu vườn thành các miền. Mỗi miền là một tập tất cả các ô không thuộc các lối đi sao cho hai ô bất kì trong đó có thể đi tới bằng cách di chuyển qua các ô chung cạnh và không phải là ô thuộc lối đi.

Yêu cầu: Hãy xác định số miền S mà các lối đi chia khu vườn.

Dữ liệu: Vào từ file văn bản REGIONS.INP trong đó:

·         Dòng đầu chứa 3 số M, N, K.

·         Dòng thứ i trong K dòng tiếp theo chứa 4 số xác định lối đi thứ i: x_i, y_i, z_i, t_i.

Kết quả: Ghi ra file văn bản REGIONS.OUT số S tìm được.

Ví dụ:

REGIONS.INP	REGIONS.OUT
10 10 2 5 1 5 10 1 5 7 5	3

TEST - CODE

TRÒ CHƠI XÂY NHÀ

Trong các trò chơi, Bi thích nhất chơi trò xây nhà cao tầng. Để thực hiện trò chơi này Bi thường lấy các khối hình vuông có độ cao 1 để chồng lên nhau, Bi muốn xây nhà càng cao càng tốt nên đã sắp những khối hình vuông lớn ở dưới và khối hình vuông nhỏ ở trên. Một hôm, chú của Bi đi công tác về tặng cho Bi rất nhiều khối hình vuông khác, Bi quyết định ngay là xây thêm một tòa nhà nữa, chỉ trong chốc lát Bi đã hoàn thành nhưng rồi Bi nghĩ sẽ gộp hai tòa nhà lại để được một tòa nhà có độ cao bằng tổng của 2 tòa nhà cũ. Nếu phải tháo hết cả hai tòa nhà rồi ghép lại thì rất mất thời gian. Bạn hãy giúp Bi thực hiện công việc đó

Dữ liệu vào: Từ file BUILD.INP

+ Dòng đầu tiên là số nguyên dương N cho biết độ cao của của ngôi nhà thứ nhất (1≤N≤10⁶)

+ N dòng tiếp theo dòng thứ i là một số nguyên dương cho biết kích thước của khối hình vuông thứ i dùng để xây ngôi nhà thứ nhất

+ Dòng thứ N+2 là số nguyên dương M cho biết độ cao của ngôi nhà thứ hai (1≤M≤10⁶)

+ M dòng tiếp theo dòng thứ j là một số nguyên dương cho biết kích thước của khối hình vuông thứ j dùng để xây ngôi nhà thứ 2

Dữ liệu ra: Ghi vào file BUILD.OUT gồm N+M dòng trong đó dòng thứ i cho biết kích thước của khối hình vuông thứ i trong tròng nhà mới

Giới hạn: Các số nguyên dương đều ≤ 10⁹

Ví dụ:

BUILD.INP	BUILD.OUT
2 7 2 3 8 7 4	8 7 7 4 2

TEST - CODE

TỔ ONG

Tổ ong bao gồm nhiều ô giống nhau hình lục bát. Các ô này để ở, chứa mật, sáp, ong non, . . . Ban đầu ong xây một ô. Sau đó xây tiếp các ô kề cạnh với ô ban đầu, làm thành lớp thứ hai, sau đó xây tiếp các ô kề cạnh với ô ở lớp thứ hai, làm thành lớp thứ 3, . . .

Người ta tìm thấy một tổ ong lớn có tới n lớp. Hãy xác định số ô của tổ ong tìm thấy.

Dữ liệu: Vào từ file văn bản BEEHIVE.INP gồm một dòng chứa số nguyên n (1 ≤ n ≤ 10⁹).

Kết quả: Đưa ra file văn bản BEEHIVE.OUT một số nguyên – số lượng ô trong tổ ong.

Ví dụ:

BEEHIVE.INP	BEEHIVE.OUT
4	37

TEST - CODE - SOLUTION

ỐC SÊN

Con ốc sên đang ở gốc của một cái cây cao v mét tính từ gốc. Ốc sên muốn bò lên ngọn cây để ăn những lá non trên đó. Ban ngày ốc sên bò được a mét lên trên, nhưng ban đêm, khi ngủ nó bị trôi xuống dưới b mét.

Yêu cầu: Cho các số nguyên  a và b, v (1 ≤ b < a ≤ v ≤ 10⁹). Hãy xác định số ngày cần thiết để ốc sên lên tới ngọn cây.

Dữ liệu: Vào từ file văn bản SNAIL.INP gồm một dòng chứa 3 số nguyên a, b và v.

Kết quả: Đưa ra file văn bản SNAIL.OUT một số nguyên – kết quả tìm được.

Ví dụ:

SNAIL.INP	SNAIL.OUT
2 1 5	4

TEST - CODE

HÁI NẤM

Trước mặt Mario là một dãy 10 cây nấm xếp thành một hàng dài, mỗi cây nấm có một giá trị riêng, là một số nguyên không vượt quá 100. Mario không cần phải hái hết nấm mà chỉ cần đạt tổng giá trị càng gần 100 càng tốt và chỉ được hái liên tục các cây nấm cạnh nhau. Nếu có hai khả năng gần 100 tương đương nhau (ví dụ 98 và 102) Mario sẽ chọn phương án có giá trị lớn hơn.

Yêu cầu: Cho giá trị các cây nấm theo trình tự từ trái sang phải. Hãy xác định tổng giá trị nấm Mario hái được.

Dữ liệu: Vào từ file văn bản MUSHROOM.INP gồm 10 dòng, mỗi dòng chứa một số nguyên, dòng thứ i xác định giá trị cây nấm i.

Kết quả: Đưa ra file văn bản MUSHROOM.OUT một số nguyên – tổng giá trị nấm Mario hái được.

Ví dụ:

MUSHROOM.INP	MUSHROOM.OUT
1 2 3 5 8 13 21 34 55 79	110

TEST - CODE

KHÁCH SẠN

Ở Hội khỏe Phù Đổng các đoàn đại biểu đến tham dự là rất đông, vì vậy việc bố trí chổ ở cho mỗi đoàn không phải là một chuyện đơn giản.

Đoàn đại biểu của một tỉnh lớn có n người. Khách sạn dành cho đoàn chỉ có 2 loại phòng: phòng 2 người và phòng 3 người. Để tiết kiệm kinh phí trưởng đoàn quyết định thuê càng ít phòng càng tốt và các phòng được thuê phải ở hết chổ.

Hãy xác định số phòng 2 chổ a₂ và số phòng 3 chổ a₃ cần thuê.

Dữ liệu: Vào từ file văn bản HOTEL.INP gồm một dòng chứa số nguyên n (2 ≤ n ≤ 1000).

Kết quả: Đưa ra file văn bản HOTEL.OUT hai số nguyên a₂ và a₃.

Ví dụ:

HOTEL.INP	HOTEL.OUT
7	2 1

TEST - CODE