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

VOI2011 NÂNG CẤP MẠNG

Nguồn: http://vn.spoj.com/problems/UPGRANET/

Một hệ thống gồm n máy tính đánh số từ 1 đến n được kết nối thành một mạng bởi m đoạn cáp mạng đánh số từ 1 đến m. Đoạn cáp mạng thứ i có thông lượng w_i kết nối hai máy u_i, v_icho phép truyền dữ liệu theo cả hai chiều giữa hai máy này.

Một dãy các máy x₁, x₂, …, x_p trong đó giữa hai máy x_j và x_j+1 (j = 1, 2, …, p-1) có đoạn cáp nối được gọi là một đường truyền tin từ máy x₁ tới máy x_p. Thông lượng của đường truyền tin được xác định như là thông lượng nhỏ nhất trong số các thông lượng của các đoạn cáp mạng trên đường truyền. Giả thiết là mạng được kết nối sao cho có đường truyền tin giữa hai máy bất kì và giữa hai máy có không quá một đoạn cáp mạng nối chúng.

Người ta muốn nâng cấp mạng bằng cách tăng thông lượng của một số đoạn cáp nối trong mạng. Để tăng thông lượng của mỗi đoạn cáp mạng thêm một lượng d (d > 0) ta phải trả một chi phí đúng bằng d. Việc nâng cấp mạng phải đảm bảo là sau khi hoàn tất, thông lượng của mỗi đoạn cáp mạng i đều bằng thông lượng của đường truyền tin có thông lượng lớn nhất từ máy u_i tới máy v_i.

Yêu cầu: Tìm phương án nâng cấp các đoạn cáp mạng sao cho tổng chi phí nâng cấp là nhỏ nhất.

Dữ liệu vào: Từ tệp văn bản UPGRANET.INP

·         Dòng thứ nhất: Chứa hai số nguyên dương n, m (n, m <= 10^5).

·         Dòng thứ i trong số m dòng tiếp theo chứa ba số nguyên dương u_i, v_i, w_i (w_i <= 10^6),
i = 1, 2, …, m.

Các số trên cùng một dòng được ghi cách nhau ít nhất một dấu cách.

Kết quả: ghi ra tệp văn bản UPGRANET.OUT một số nguyên duy nhất là tổng chi phí nâng cấp theo phương án tìm được.

Ví dụ:

UPGRANET.INP	UPGRANET.OUT
6 7 1 2 6 1 3 5 2 4 3 3 4 9 4 5 4 4 6 8 5 6 7	5

Giới hạn: 50% số test tương ứng với 50% số điểm có N<=100;

SOLUTION  - CODE

LỊCH MỚI

Các nhà bác học xứ Byteland tranh luận với nhau rất nhiều về cách xây dựng lịch phù hợp với hành tinh của mình, trong đó quan trọng nhất là xác định năm nhuận. Ở đại hội lần thứ XII có một phương pháp xác định năm nhuận hoàn toàn mới được mọi người hết sức chú ý.

Theo cách tính này, số năm được xét dưới dạng nhị phân (không có các số 0 không có nghĩa ở đầu) .Các số giống nhau đứng liên tiếp tạo thành một nhóm. Nếu số chứa đúng 3 nhóm thì đó là năm nhuận. Ví dụ các năm 9 = 1001₂ và 13 = 1101₂ là năm nhuận, còn 7 = 111₂ – không phải là nhuận. Năm được đánh số từ 1 trở đi một cách liên tiếp.

Người ta muốn kiểm nghiệm độ chính xác của lịch này và tính số lượng năm nhuận trong khoảng thời gian từ a đến b (kể cả a và b).

Hãy xác định số năm nhuận trong khoảng đã cho.

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

Kết quả: Đưa ra file văn bản CALENDAR.OUT một số nguyên – số năm nhuận.

Ví dụ:

CALENDAR.INP	CALENDAR.OUT
19 30	5

SOLUTION - TEST - CODE

NƯỚC ĐỌNG

Nguồn: http://vn.spoj.com/problems/V11WATER/

Năm 2011, tình trạng ngập lụt trong thành phố trở lên nghiêm trọng hơn. Vì vậy, mọi người quyết định xây dựng hệ thống mái che cho toàn thành phố.

Mái che có bề rộng là N, được chia làm N phần có độ dài như nhau. Độ cao của mỗi phần là h1, h2, ..., hn. Khi trời mưa, một phần nước sẽ đọng lại trên mái và một phần sẽ thoát ra ngoài theo hai bên trái và phải của mái che. Do đó, thành phố sẽ không phải chịu cảnh mưa lụt như trước.

Nhằm mục đích bảo trì mái che, bạn cần viết chương trình tính lượng nước lớn nhất có thể đọng lại trên mái che.

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

+ Dòng đầu ghi số N. (1 <= N <= 100000)

+ Dòng sau ghi N số tự nhiên h1, h2, ..., hn. (1 <= hi <= 100000)

Gồm một số duy nhất thể hiện lượng nước tìm được.

Dữ liệu ra: ghi vào tệp V11WATER.OUT

+ Môt số duy nhất thể hiện số lượng nước tìm được

Ví dụ:

V11WATER.INP	V11WATER.OUT
5 1 3 1 2 3	3

 SOLUTION - CODE

CÂY

Nguồn: http://vn.spoj.com/problems/VOTREE/

Cho cây gồm N đỉnh, có gốc ở đỉnh 1. (N ≤ 70,000). Bạn cần trả lời Q truy vấn, mỗi truy vấn gồm 2 số u, v. Bạn cần tìm đỉnh xa gốc nhất, mà là tổ tiên của tất cả các đỉnh u, u+1, ..., v.

Dữ liệu vào: VOTREE.INP

+ Dòng 1: Số nguyên dương N và Q.

+ N-1 dòng tiếp theo, mỗi dòng chứa 2 số nguyên dương u và v, thể hiện có 1 cạnh nối giữa 2 đỉnh u và v. (u ≠ v, 1 ≤ u, v ≤ N).

 +Q dòng tiếp theo, mỗi dòng gồm 2 số nguyên dương u và v (1 ≤ u ≤ v ≤ N), thể hiện 1 truy vấn.

Dữ liệu ra: Ghi vào tệp văn bản VOTREE.OUT

Với mỗi truy vấn, in ra 1 dòng duy nhất là đáp số của truy vấn.

Giới hạn:

+ Trong 30% số test, 1 ≤ N, Q ≤ 1000.

+ Trong tất cả các test, 1 ≤ N, Q ≤ 70,000.

+ Thời gian chạy: 1s. Thời gian chạy cho test ví dụ: 0.5s

Ví dụ:

VOTREE.INP	VOTREE.OUT
5 3 1 2 2 3 3 4 3 5 2 5 1 3 4 5	2 1 3

SOLUTION - CODE