BỐC SỎI

Trong trò chơi bốc sỏi, ta có n viên sỏi được xếp thành một hàng ngang. Mỗi viên sỏi có một màu, có thể là Đỏ, Vàng hoặc Xanh. Nhiệm vụ của bạn là xác định số lượng tối thiểu các viên sỏi cần bốc ra để không còn hai viên sỏi liên tiếp có cùng màu.

Dữ liệu vào

Tệp văn bản BOCSOI.INP gồm:

• Dòng đầu tiên chứa một số nguyên n ~(1 \leq n \leq 50)~, là số lượng các viên sỏi.
• Dòng thứ hai chứa một xâu có n ký tự. Mỗi ký tự thuộc tập {D, V, X}, biểu thị màu của các viên sỏi:
  • D: Đỏ,
  • V: Vàng,
  • X: Xanh.

Dữ liệu ra

Tệp văn bản BOCSOI.OUT gồm:

• Một số nguyên duy nhất, là số lượng tối thiểu các viên sỏi cần bốc ra.

Ví dụ

MÃ SỐ

Bờm thường xuyên tham gia các cuộc thi lập trình trên mạng. Vì đạt được thành tích cao nên Bờm được ban tổ chức gửi tặng một phần mềm diệt virus, đồng thời nhà sản xuất phần mềm diệt virus cung cấp cho Bờm một dãy ký tự có độ dài không quá 1000 ký tự (dãy ký tự này chỉ bao gồm các chữ cái thường, chữ cái số).

Để cài đặt được phần mềm diệt virus đó, Bờm phải nhập mã số Serial của phần mềm để đăng ký bản quyền. Mã số Serial ở đây là một dãy số gồm các số chưa được xuất hiện trong dãy ký tự mà nhà sản xuất đã cung cấp nằm trong đoạn từ 0 đến 9, và có giá trị nhỏ nhất đến ký tự số có giá trị lớn nhất có trong dãy ký tự đó.

Yêu cầu

Hãy giúp Bờm tìm dãy số Serial đó. Nếu không tồn tại dãy số nào trong dãy ký tự đã cho thì ghi ra màn hình -1 để biết không tồn tại mã số Serial.

Dữ liệu vào

Tệp văn bản SERIAL.INP gồm:

• Một dãy ký tự mà nhà sản xuất cấp cho Bờm.

Kết quả

Ghi ra file văn bản SERIAL.OUT gồm:

• Kết quả của dãy số Serial cần tìm, giữa các số cách nhau 1 dấu cách.

Ví dụ

Đếm số đôi tất

Mô tả bài toán

Bé Hải Dương có ~n~ chiếc tất, chiếc tất thứ ~i~ có màu là ~c_i~. Bé Hải Dương muốn biết bé có thể ghép được bao nhiêu đôi tất để cho các bạn cùng lớp mỗi người một đôi, biết rằng hai chiếc tất có thể ghép thành một đôi nếu chúng có cùng màu.

Input

Dữ liệu đầu vào được cung cấp như sau:

• Dòng đầu tiên chứa số nguyên ~n~: số tất mà bé Hải Dương có (~1 \leq n \leq 10^6~).
• Dòng thứ hai chứa ~n~ số nguyên ~c_i~ (~1 \leq c_i \leq 10^6~): màu của từng chiếc tất.

Output

Dữ liệu đầu ra là một số nguyên duy nhất: số lượng đôi tất mà bé Hải Dương có thể ghép được.

Ví dụ

Input:

9
10 20 20 10 10 30 50 10 20

Output:

3

Bài 4. Dãy con có tổng lớn nhất

Cho dãy số nguyên ~a_1, a_2, \dots, a_N~. Một dãy con liên tiếp có dạng ~a_i, a_{i+1}, \dots, a_j~ với ~1 \leq i \leq j \leq N~, tổng của dãy con liên tiếp ~a_i, a_{i+1}, \dots, a_j~ là ~a_i + a_{i+1} + \dots + a_j~.

Yêu cầu: Cho dãy số nguyên ~a_1, a_2, \dots, a_N~, tìm dãy con liên tiếp có tổng lớn nhất.

Dữ liệu:

Vào từ tệp văn bản TONGMAX.INP gồm:

• Dòng 1: ghi số nguyên dương ~N~.
• Dòng 2: ghi lần lượt các số nguyên ~a_1, a_2, \dots, a_N~ (~|a_i| \leq 10^6~, với ~i = 1 \dots N~).

Kết quả: ghi ra tệp văn bản TONGMAX.OUT gồm một số duy nhất là tổng của dãy con tìm được.

Ví dụ:

Dữ liệu đầu vào (TONGMAX.INP):

6
3 8 -2 4 5 -1

Dữ liệu đầu ra (TONGMAX.OUT):

18

Giới hạn:

• Subtask 1: Có 40% số điểm với ~N \leq 100~
• Subtask 2: Có 40% số điểm với ~N \leq 1000~
• Subtask 3: Có 20% số điểm với ~N \leq 10^6~