Dữ liệu đầu vào từ form đăng ký khóa học bị lỗi đánh máy nghiêm trọng. Các họ tên bị dư thừa rất nhiều dấu cách ở đầu, cuối và giữa các từ. Hơn nữa, chữ hoa chữ thường bị lộn xộn. Bạn hãy viết một đoạn script chuẩn hóa lại xâu họ tên sao cho: không có dấu cách thừa, chữ cái đầu tiên của mỗi từ phải viết hoa, và tất cả các chữ cái còn lại viết thường.

Input: Một dòng chứa xâu S là họ tên chưa chuẩn hóa (Độ dài <= 10^5).

Output: Xâu S sau khi đã chuẩn hóa.

Ví dụ:

Input:

nGuyen   VaN   a

Output:

Nguyen Van A

Một lô hàng nhập khẩu gồm có 2N + 1 linh kiện điện tử. Theo hóa đơn, sẽ có đúng N cặp linh kiện hoàn toàn giống nhau (được đánh cùng mã số), và chỉ có duy nhất 1 linh kiện cao cấp bị lẻ không có cặp. Hãy viết thuật toán có độ phức tạp thời gian O(N) và dùng bộ nhớ O(1) để tìm ra mã số của linh kiện lẻ loi đó trong nháy mắt.

Input:

Dòng 1: Số nguyên dương N (1 <= N <= 10^6). (Lưu ý số lượng phần tử mảng là 2N + 1)

Dòng 2: 2*N + 1 số nguyên là mã số của các linh kiện (Mã số <= 10^9).

Output: Mã số của linh kiện lẻ.

Ví dụ:

Input:

2
4 1 2 1 2

Output:

4

Dọc theo một tuyến đường cao tốc thẳng tắp có N trạm thu phí tại các tọa độ X_i. Công ty viễn thông cần lắp đặt các trạm phát sóng Wifi dọc theo tuyến đường. Biết rằng mỗi trạm Wifi có bán kính phủ sóng là R (tức là có thể phủ sóng trong đoạn [V - R, V + R] nếu đặt ở tọa độ V). Tìm số lượng trạm Wifi ít nhất cần lắp đặt để tất cả N trạm thu phí đều có mạng.

Input:

Dòng 1: Hai số nguyên N và R (1 <= N <= 10^5, 0 <= R <= 10^9).

Dòng 2: N số nguyên Xi là tọa độ của các trạm thu phí (0 <= Xi <= 10^9).

Output: Số lượng trạm Wifi tối thiểu.

Ví dụ:

Input:

5 2
1 4 5 10 12

Output:

3

Điện tâm đồ trả về một mảng N chỉ số đo. Bác sĩ cần phân tích một "dãy con nhịp tim" (không nhất thiết liên tiếp) thỏa mãn tính chất Zig-zag: Các phần tử đan xen nhau giữa tăng và giảm. Nói cách khác, nếu phần tử thứ hai lớn hơn phần tử thứ nhất, thì phần tử thứ ba phải nhỏ hơn phần tử thứ hai, thứ tư lớn hơn thứ ba, v.v... và ngược lại. Hãy tìm độ dài của dãy con Zig-zag dài nhất.

Input:

Dòng 1: Số nguyên N (1 <= N <= 10^5).

Dòng 2: N số nguyên Ai (|Ai| <= 10^9).

Output: Độ dài dãy con Zig-zag lớn nhất.

Ví dụ:

Input:

7
1 7 4 9 2 5 3

Output:

7

(Giải thích: Toàn bộ dãy đã cho có tính chất Zig-zag: 1<7, 7>4, 4<9, 9>2, 2<5, 5>3).

Bạn được cung cấp một chuỗi s. Mỗi ký tự là 0 hoặc 1. Bạn muốn tất cả các số 1 trong chuỗi tạo thành một phân đoạn liền kề. Ví dụ: nếu chuỗi là 0, 1, 00111 hoặc 01111100, thì tất cả 1 đều tạo thành một phân đoạn liền kề và nếu chuỗi là 0101, 100001 hoặc 11111111111101 thì điều kiện này không được đáp ứng. Bạn có thể xóa một số 0 (có thể không cần xóa) khỏi chuỗi. Số 0 tối thiểu mà bạn phải xóa là bao nhiêu?

Đầu vào: Dòng đầu tiên chứa một số nguyên t (1≤t≤100) - số lượng trường hợp kiểm tra. Sau đó t dòng tiếp theo, mỗi dòng đại diện cho một trường hợp thử nghiệm. Mỗi dòng chứa một chuỗi s (1≤ | s |<=100); mỗi ký tự của s là 0 hoặc 1.

Đầu ra: In số nguyên t, trong đó số nguyên thứ i là câu trả lời cho mẫu thử thứ i (số tối thiểu là 0 mà bạn phải xóa khỏi s).

Input:

3
010011
0
1111000

Output:

2
0
0