DÃY CON TĂNG DÀI NHẤT - mã: LIS - Làm với BIT

Link: http://vn.spoj.com/problems/LIS/

(Giống bài LIQ) Cho một dãy gồm N số nguyên (1 ≤ N ≤ 30000). Hãy tìm dãy con tăng dài nhất trong dãy đó. In ra số lượng phần tử của dãy con. Các số trong phạm vi longint.

Input

Dòng đầu tiên gồm số nguyên N.

Dòng thứ hai gồm N số mô tả dãy.

Output

Gồm một số nguyên duy nhất là đáp số của bài toán

Example

Input:

5

2 1 4 3 5

Output:

3

Code tham khảo: LIS (BIT)

Continue Reading

RR - mã: VMRR - SPOJ

Link: http://vn.spoj.com/problems/VMRR/

Có một điều bí mật, mà xưa nay chỉ được lưu truyền giữa các admin VNOI, là RR có những sở thích rất khác người. Không chỉ dừng lại ở việc ngồi ngắm bảng rank của các kỳ thi trên mạng hàng tiếng đồng hồ hay ngồi học thuộc tên của các coder nổi tiếng thế giới, RR còn có sở thích tìm tên mình trong những chuỗi văn bản dài...

Nhiều khi, việc tìm tên mình mất rất nhiều thời gian, thậm chí có thể tốn nhiều ngày mà vẫn đếm nhầm. Các bạn hãy giúp RR giải quyết vấn đề này một cách tổng quát hơn nhé.

Yêu cầu

Cho một xâu S và 2 ký tự X và Y. Đếm xem chuỗi con XY xuất hiện bao nhiêu lần trong S (hai ký tự X và Y không cần liên tiếp nhưng cần xuất hiện đúng thứ tự (X trước Y)).

Input

Dòng 1: Xâu S.

Dòng 2: X và Y.

Output

Gồm 1 số nguyên duy nhất là kết quả của bài toán.

Giới hạn

Xâu S chứa không quá 10⁶ ký tự.

Tất cả các ký tự trong đề bài có mã ASCII từ 32 đến 255.

Chấm bài

Bài của bạn sẽ được chấm trên thang điểm 100. Điểm mà bạn nhận được sẽ tương ứng với % test mà bạn giải đúng.

Trong quá trình thi, bài của bạn sẽ chỉ được chấm với 2 test ví dụ có trong đề bài.

Khi vòng thi kết thúc, bài của bạn sẽ được chấm với bộ test đầy đủ.

Example

Input 1:

R_R_
RR

Output 1: 1

Input 2:

BA
AB

Output 2: 0

Code: VMRR

Solution: VMRR

Continue Reading

QUA CẦU - mã: CROSS12 - SPOJ

Link: http://vn.spoj.com/problems/CROSS12/

    Một nhóm n bạn đi tập văn nghệ về khuya. Cả nhóm chỉ có 1 chiếc đèn pin và phải qua 1 cây cầu gồm m đoạn, các đoạn được đánh số từ 1 đến m kể từ vị trí bờ đang đứng sang bờ kia. Coi vị trí n bạn đang đứng là đoạn thứ 0 và đầu cầu bên kia là vị trí m+1. Cây cầu đã cũ, do đó có một số đoạn của cầu đã hỏng và không thể đi vào được, hơn nữa cầu chỉ chịu được sức nặng của không quá hai người. Để qua cầu an toàn, các bạn phải tổ chức qua cầu theo cách thức sau: mỗi lượt chỉ có 2 người cầm đèn pin để cùng nhau qua cầu và không được đi vào những vị trí đoạn cầu bị hỏng. Sau khi hai người qua đến đầu cầu bên kia thì những người đã qua cầu phải cử 1 người đem đèn pin trở lại đầu cầu bên này để các bạn khác tiếp tục qua cầu ... Mỗi đơn vị thời gian, bạn thứ i có thể bước không quá r_i đoạn, nghĩa là nếu bạn thứ i đang ở đoạn thứ s của cây cầu thì bạn có thể di chuyển vào một trong các đoạn thứ s+1, s+2, ..., s+r_i nếu đoạn đó không bị hỏng. Việc thực hiện một bước đi đòi hỏi 1 đơn vị thời gian. Do đó có thể có người qua cầu nhanh hơn, có người qua cầu chậm hơn. Nếu 2 bạn đi cùng nhau qua cầu thì họ phải di chuyển qua cầu với thời gian của bạn chậm hơn. Vì đã quá khuya nên cả nhóm bàn nhau tìm cách qua cầu sớm nhất có thể được.

Yêu cầu: 

    * Cho biết vị trí các đoạn cầu bị hỏng và khả năng di chuyển của từng bạn (được mô tả bằng các số r₁, r₂, ..., r_n), 

    * Hãy tính khoảng thời gian ngắn nhất để n bạn qua được cầu. Giải thiết rằng luôn có cách để cả nhóm vượt qua cầu.

Ràng buộc: 50% số tests ứng với 50% số điểm của bài có n ≤ 10.

Input

    * Dòng thứ nhất chứa hai số nguyên dương n và m tương ứng là số bạn trong nhóm và số đoạn của cây cầu (n ≤ 10000; m ≤ 100000).

    * Dòng thứ hai chứ n số nguyên dương r₁, r₂, ..., r_n (r_i ≤ 100, i = 1, 2, ..., n).

    * Dòng thứ ba chứa một xâu gồm m ký tự '0' hoặc '1' mô tả trạng thái của cây cầu. Ký tự thứ i của xâu là '0' nếu đoạn cầu thứ i không bị hỏng có thể đi vào được, là '1' nếu đoạn cầu thứ i bị hỏng không thể đi vào được.

    * 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.

Output

    * Ghi ra một số nguyên là khoảng thời gian ngắn nhất để n bạn vượt qua được cây cầu.

Example

Input:

3 5
2 2 4
00100

Output: 8

Solution: CROSS12

Code: CROSS12

Continue Reading

PHÂN TRANG - mã: PTRANG - SPOJ

Link: http://vn.spoj.com/problems/PTRANG/

Văn bản là một dãy gồm N từ đánh số từ 1 đến N. Từ thứ i có độ dài là wi (i=1, 2,... N). Phân trang là một cách xếp lần lượt các từ của văn bản vào dãy các dòng, mỗi dòng có độ dài L, sao cho tổng độ dài của các từ trên cùng một dòng không vượt quá L.Ta gọi hệ số phạt của mỗi dòng trong cách phân trang là hiệu số (L-S), trong đó S là tổng độ dài của các từ xếp trên dòng đó. Hệ số phạt của cách phân trang là giá trị lớn nhất trong số các hệ số phạt của các dòng.Tìm cách phân trang với hệ số phạt nhỏ nhất.

Input

• Dòng 1 chứa 2 số nguyên dương N, L (N<=6000,L<=1000)
• Dòng thứ i trong số N dòng tiếp theo chứa số nguyên dương wi (wi<=L), i=1, 2,.., N

Output

In ra hệ số phạt nhỏ nhất

Ví dụ

Input:

4 5

3

2

2

4

Output:

2

Solution: PTRANG

Code: PTRANG

Continue Reading

SIÊU TRỘM KID VÀ MẬT KHẨU ĐÊM TRUNG THU - mã: C11SUM - SPOJ

Link: http://vn.spoj.com/problems/C11SUM/

Bài toán trên tờ giấy của ông Jirokichi như sau:

Cho một xâu S , S chỉ chứa các số 0 đến 9. 

Tính tổng các DÃY CON LIÊN TIẾP của S mod 10^9+7

Input

Một dòng duy nhất chứa xâu S

Output

Một số duy nhất là kết quả của bài toán.

Giới hạn:

Với length(s) là độ dài của xâu S:

• 50% số test length(S) ≤ 100
• 50% số test còn lại length(s) ≤ 10^6

Input:

737

Output:

864

Giải thích: 7 + 3 + 7 + 73 + 37 + 737 = 864

Code tham khảo: C11SUM

Continue Reading

ĐỔI TIỀN - mã: DTDOI - SPOJ

Link: http://vn.spoj.com/problems/DTDOI/

Bạn được cho một tập hợp các mệnh giá tiền. Tập hợp luôn chứa phần tử mang gía trị 1. Mỗi mệnh giá có vô hạn các đồng tiền mang mệnh giá đó. Cho số tiền S, hãy tìm cách đổi S thành ít đồng tiền nhất, sao cho mỗi đồng tiền có mệnh giá thuộc vào tập hợp đã cho.

Input

Dữ liệu vào gồm 2 dòng:

·               *  Dòng 1: Hai số nguyên dương N (số phần tử của tập hợp mệnh giá tiền) và S (số tiền cần đổi) (1 ≤ N ≤ 100; 1 ≤ S ≤ 10⁹ ).

·               * Dòng 2: N số nguyên dương biểu thị mệnh giá của các phần tử trong tập hợp (giá trị không vượt quá 100).

Output

Dữ liệu ra gồm một số nguyên duy nhất là số đồng tiền ít nhất có thể đổi được.

Example

Input:

2 3

1 2

Output: 2

Code: DTDOI

Thuật toán: DTDOI

Continue Reading

HÌNH CHỮ NHẬT 0-1 (SPOJ) - mã: QBRECT

Link: http://vn.spoj.com/problems/QBRECT/

Cho một bảng kích thước MxN, được chia thành lưới ô vuông đơn vị M dòng N cột ( 1 <= M, N <= 1000 )

Trên các ô của bảng ghi số 0 hoặc 1. Các dòng của bảng được đánh số 1, 2... M theo thứ tự từ trên xuống dưới và các cột của bảng được đánh số 1, 2..., N theo thứ tự từ trái qua phải

Yêu cầu:

Hãy tìm một hình chữ nhật gồm các ô của bảng thoả mãn các điều kiện sau:

1 - Hình chữ nhật đó chỉ gồm các số 1

2 - Cạnh hình chữ nhật song song với cạnh bảng

3 - Diện tích hình chữ nhật là lớn nhất có thể

Input

Dòng 1: Ghi hai số M, N

M dòng tiếp theo, dòng thứ i ghi N số mà số thứ j là số ghi trên ô (i, j) của bảng

Output

Gồm 1 dòng duy nhất ghi diện tích của hình chữ nhật tìm được

Example

Input:

11 13

0 0 0 0 0 1 0 0 0 0 0 0 0

0 0 0 0 1 1 1 0 0 0 0 0 0

0 0 1 1 1 1 1 1 1 0 0 0 0

0 0 1 1 1 1 1 1 1 0 0 0 0

0 1 1 1 1 1 1 1 1 1 0 0 0

1 1 1 1 1 1 1 1 1 1 1 0 0

0 1 1 1 1 1 1 1 1 1 0 0 0

0 0 1 1 1 1 1 1 1 0 0 0 0

0 0 1 1 1 1 1 1 1 0 0 0 0

0 0 0 0 1 1 1 0 0 0 0 1 1

0 0 0 0 0 1 0 0 0 0 0 1 1

Output:

49

===================================

Thuật:

- H[j] là số số 1 liên tiếp ở cột thứ j (với mỗi dòng i ta lại cập nhật H[j], tăng H[j] lên 1 đơn vị nếu A[i,j]=1 ngược lại H[j]=0)

-Duyệt đến dòng thứ i, ta tìm vị trí trái nhất (L[j]) và phải nhất (R[j]) sao cho H[j] là bé nhất (ta dùng thuật toán left-right để tìm L và R ở mỗi dòng i)

- và diện tích hình chữ nhật lớn nhất tính đến dòng i sẽ là H[j] * (R[j]-L[j]+1)....tại mỗi dòng, ta lại cập nhật kết quả max...

====================================

Đây là code: QBRECT.PAS

Continue Reading

HÌNH VUÔNG 01 (SPOJ) - mã: QBSQUARE

Link: http://vn.spoj.com/problems/QBSQUARE/

Cho một bảng kích thước MxN, được chia thành lưới ô vuông đơn vị M dòng N cột ( 1 <= M, N <= 1000 )

Trên các ô của bảng ghi số 0 hoặc 1. Các dòng của bảng được đánh số 1, 2... M theo thứ tự từ trên xuống dưới và các cột của bảng được đánh số 1, 2..., N theo thứ tự từ trái qua phải

Yêu cầu:

Hãy tìm một hình vuông gồm các ô của bảng thoả mãn các điều kiện sau:

1 - Hình vuông là đồng nhất: tức là các ô thuộc hình vuông đó phải ghi các số giống nhau (0 hoặc 1)

2 - Cạnh hình vuông song song với cạnh bảng.

3 - Kích thước hình vuông là lớn nhất có thể

Input

Dòng 1: Ghi hai số m, n

M dòng tiếp theo, dòng thứ i ghi N số mà số thứ j là số ghi trên ô (i, j) của bảng

Output

Gồm 1 dòng duy nhất ghi kích thước cạnh của hình vuông tìm được

Example

Input:

11 13

0 0 0 0 0 1 0 0 0 0 0 0 0

0 0 0 0 1 1 1 0 0 0 0 0 0

0 0 1 1 1 1 1 1 1 0 0 0 0

0 0 1 1 1 1 1 1 1 0 0 0 0

0 1 1 1 1 1 1 1 1 1 0 0 0

1 1 1 1 1 1 1 1 1 1 1 0 0

0 1 1 1 1 1 1 1 1 1 0 0 0

0 0 1 1 1 1 1 1 1 0 0 0 0

0 0 1 1 1 1 1 1 1 0 0 0 0

0 0 0 0 1 1 1 0 0 0 0 1 1

0 0 0 0 0 1 0 0 0 0 0 1 1

Output:

7

========================================

Thuật toán: Quy hoạch động:

- F[i,j] là kích thước của hình vuông tính đến ô (i,j):

F[i,j]=max(F[i-1,j],F[i,j-1],F[i-1,j-1])+1 nếu A[i,j]=Ai-1,j]=A[i,j-1]=A[i-1,j-1] ngược lại F[i,j]=1

- Kết quả của bài toán là max(F[i,j])  (1<=i<=m và 1<=j<=n)

========================================

Code: QBSQUARE

Continue Reading