THÀNH PHẦN LIÊN THÔNG MẠNH

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

Cho đồ thị G(V,E) có hướng n (1<=n<=10^4)  đỉnh m (1<=m<=10^5) cung, Hãy đếm số thành phần liên thông mạnh của G.

Dữ liệu vào:

+Dòng đầu tiên là n,m.

+M dòng tiếp theo mô tả một cung của G.

Dữ liệu ra:

Gồm một dòng duy nhất là số TPLT mạnh.                  

Ví dụ:

Input	Output		Input	Output
3 2 1 2 2 3	3		3 3 1 2 2 3 3 1	1

OPTCUT

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

Bạn cần chặt một thanh gỗ ra thành n đoạn, mỗi đoạn có độ dài a_i. Các đoạn được chặt phải có độ dài theo đúng thứ tự a₁, a₂, ..., a_n từ trái sang phải.

Tại mỗi bước, bạn có thể chặt một nhát chia một thanh gỗ làm hai, và chi phí cho nhát chặt này bằng độ dài của thanh gỗ trước khi chặt.

Thứ tự chặt khác nhau sẽ cho ra tổng chi phí khác nhau khi chặt thanh gỗ thành n đoạn yêu cầu.

Ví dụ bạn cần chặt một thanh gỗ độ dài 20 ra thành 4 đoạn độ dài 3, 5, 2 và 10 theo thứ tự.

Khi chặt từ trái sang phải:

20 chặt thành 3 và 17, chi phí 20.

17 chặt thành 5 và 12, chi phí 17.

12 chặt thành 2 và 10, chi phí 12.

Tổng chi phí: 49

Khi chặt từ phải sang trái:

20 chặt thành 10 và 10, chi phí 20.

10 chặt thành 8 và 2, chi phí 10.

8 chặt thành 3 và 5, chi phí 8.

Tổng chi phí: 38

Bạn hãy tìm cách chặt có tổng chi phí nhỏ nhất.

Dữ liệu vào:

+ Dòng 1: n (1 ≤ n ≤ 2000)

+ Dòng 2: n số nguyên dương a₁, a₂, ..., a_n, biết rằng độ dài của thanh gỗ a₁+a₂+...+a_n ≤ 500000

Dữ liệu ra: Một số nguyên duy nhất là chi phí nhỏ nhất tìm được.

Ví dụ:

INPUT	OUTPUT
4 3 5 2 10	37

Treats for the Cows

Nguồn: http://www.spoj.com/problems/TRT/

FJ muốn bán N miếng bánh làm từ sữa các con bò. (1≤N≤2000). FJ bãn mỗi ngày một miếng bánh và muốn nhận được số tiền lớn nhất từ việc bán những cái bánh đó trong một khoảng thời gian có hạn. Mỗi miếng bánh có giá trị cao nhờ nhiều nguyên nhân:

+ các miếng bánh được xếp trong một băng dài được đánh số từ 1 đến N. Mỗi ngày FJ có thể lấy 1 miếng bánh ở đầu này hoặc đầu kia của băng đó.

+ Cũng giống như rượu và  pho-mat, các miếng bánh có tuổi thọ càng cao thì càng có giá trị.

+ Giá trị của miếng bánh cũng không cố định. Miếng bánh thứ i có giá trị V_i (1≤V_i≤1000) nếu như miếng bánh đó được bán vào ngày 1.

+ Mỗi chiếc bánh có giá trị phụ thuộc vào tuổi của nó. Mỗi miếng bánh sẽ nhận được a*V_i giá trị với chiếc bánh thứ i có a tuổi.

Yêu cầu: Cho các giá trị V_i. Hãy tìm giá trị lớn nhất Fj có thể nhận được từ việc bán những chiếc bánh.

Chiếc bánh đầu tiên có tuổi là 1, các miếng bánh được bán sau sẽ có tuổi nhiều hơn miếng bánh bán trước là 1.

Dữ liệu vào:

+ Dòng đầu tiên là số nguyên dương N

+ N dòng sau, dòng thứ i là số nguyên V_i

Dữ liệu ra: Một số nguyên duy nhất là giá trị lớn nhất mà FJ thu được

Ví dụ:

INPUT	OUTPUT
5 1 3 1 5 2	43

NKCABLE

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

Các học sinh khi đến thực tập trong phòng máy tính thường hay chơi trò chơi điện tử trên mạng. Để ngăn ngừa, người trực phòng máy đã ngắt tất cả các máy tính ra khỏi mạng và xếp chúng thành một dãy trên một cái bàn dài và gắn chặt máy xuống mặt bàn rồi đánh số thứ tự các máy từ 1 đến N theo chiều từ trái sang phải. Các học sinh tinh nghịch không chịu thua, họ đã quyết định tìm cách nối các máy trên bàn bởi các đoạn dây nối sao cho mỗi máy được nối với ít nhất một máy khác. Để tiến hành công việc này, họ đã đo khoảng cách giữa hai máy liên tiếp. Bạn hãy giúp các học sinh này tìm cách nối mạng thoả mãn yêu cầu đặt ra sao cho tổng độ dài cáp nối phải sử dụng là ít nhất.

Dữ liệu vào:

Dòng đầu tiên chứa số lượng máy N (1 ≤ N ≤ 25000).

Dòng thứ i trong số N-1 dòng tiếp theo chứa các khoảng cách từ máy i đến máy i+1 (i=1,2,...,N-1). Giả thiết rằng khoảng cách từ máy 1 đến máy N không vượt quá 10⁶.

Kết quả ra:

Ghi ra độ dài của cáp nối cần sử dụng.

Ví dụ

Input:

6

2

2

3

2

2

Output

7

CHIA ĐOẠN SỐ NGUYÊN

Steve có nhiệm vụ chuẩn bị một đề đơn giản cho kỳ thi lập trình. Steve có ý định sẽ ra một đề không những rất dễ mà còn nhàm chán nữa: Cho danh sách các số nguyên không âm, yêu cầu tính tổng của chúng.

Đúng là không nên đùa với lửa. Sự nhàm chán của đề tác động vào ngay chính Steve khi anh chuẩn bị dữ liệu. Anh phạm một sai lầm thô thiển – quên đưa các dấu cách giữa các số. Steve nhanh chóng nhận ra sai lầm khi xem lại dữ liệu vào. Thay vì danh sách có các số nguyên trong file thì chỉ chứa một xâu các ký tự số.

Steve nảy ra ý nghĩa sửa lại đề thành một bài có nội dung hấp dẫn hơn và không tầm thường: Tổng lớn nhất có thể nhận được là bao nhiêu nếu ta chia xâu này thành các số không chứa các số 0 không có nghĩa và mỗi số có thể biểu diễn ở dạng  32 bít có dấu.

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

+ Dòng đầu tiên chứa số nguyên T – số test (1≤T≤500)

+ Mỗi dòng trong T dòng tiếp theo chứa một xâu các ký tự số độ dài không quá 200.

Kết quả: Đưa ra tệp văn bản PART.OUT kết quả mỗi test đưa ra trên một dòng dưới dạng số nguyên.

Ví dụ:

PART.INP	PART.OUT
8 6 123 2345346457567421363564564 6356413244123153456574254563325236 2353576857 235235 357588978089089 2456876895436346568	6 123 2671002524 2739216082 353576859 235235 978446677 978932301

ROUTE

Cho lưới ô vuông A kích thước m´n, các hàng được đánh số từ 1 đến m từ trên xuống dưới, các cột được đánh số từ trái sang phải, từ 1 đến n. Mỗi ô của lưới chứa một số nguyên có giá trị tuyệt đối không vượt quá 10⁹.

Từ một ô có thể đi sang ô kề cạnh bên phải hoặc xuống dưới. Xét các đường đi theo quy tắc trên từ ô trên trái xuống ô dưới phải. Tổng các số trên những ô đã đi qua là giá trị của đường đi.

Hãy xác định giá trị lớn nhất có thể đạt được.

Dữ liệu: Vào từ file route.inp, dòng đầu tiên chứa 2 số nguyên m và n (2 £ m, n £ 1000), mỗi dòng trong m dòng sau chứa n số nguyên xác định một dòng của bảng.

Kết quả: Đưa ra file route.out một số nguyên – giá trị max tìm được.

Ví dụ:

ROUTE.INP	ROUTE.OUT
5 6 2 6 8 1 – 5 9 9 1 7 3 6 4 -2 0 5 1 8 -6 1 4 0 3 0 4 9 -2 4 5 -4 2	46

LÁT GẠCH

Nguồn: spoj

Cho một hình chữ nhật kích thước 2xN (1<=N<=100). Hãy đếm số cách lát các viên gạch nhỏ kích thước 1x2 và 2x1 vào hình trên sao cho không có phần nào của các viên gạch nhỏ thừa ra ngoài, cũng không có vùng diện tích nào của hình chữ nhật không được lát.

Dữ liệu vào:

Gồm nhiều test, dòng đầu ghi số lượng test T ( T<=100 ).
T dòng sau mỗi dòng ghi một số N.

Dữ liệu ra:

Ghi ra T dòng là số cách lát tương ứng.

Example

Input:

3

1

2

3

Output:

1

2

3