Trong một liên hoan phim, n bộ phim sẽ được chiếu. Bạn biết thời gian bắt dầu và kết thúc của mỗi bộ phim. Số lượng phim tối đa bạn có thế xem toàn bộ là bao nhiều? Biết rằng nếu thời gian kết thúc của bộ phim trước bằng hoặc nhỏ hơn thời gian bắt đầu của bộ phim sau thì bạn có thể xem cả 2 phim này.

Định dạng đầu vào: Dòng nhập đầu tiên có số nguyên n là số lượng phim. Sau đó, có n dòng mô tả các bộ phim. Mỗi dòng có hai số nguyên a và b là thời gian bắt đầu và kết thúc của một bộ phim.

Ràng buộc: 1 < n, m <= 2.10^5; 1 ≤ a, b ≤ 10^9

Định dạng đầu ra: In một số nguyên là số lượng phim tối đa.

Input:

3
3 5
4 6
2 4

Output:

2

Bạn được cho biết thời gian đến và đi của n khách hàng trong một nhà hàng. Số lượng khách hàng có mặt tại cửa hàng ở 1 thời điểm nhiều nhất là bao nhiêu?

Định dạng đầu vào: Dòng nhập dầu tiên có số nguyên n là số lượng khách hàng. Sau đó, có n dòng mô tả khách hàng. Mỗi dòng có hai số nguyên a và b là thời gian đến và đi của một khách hàng. Bạn có thể cho răng tất cả thời gian đến và đi là khác nhau.

Ràng buộc: 1 <= n, m ≤ 2.10^5; 1 ≤ a, b ≤ 10^9

Định dạng đầu ra: In một số nguyên là số lượng khách hàng tối đa.

Input:

3
5 8
2 4
3 9

Output:

2

Có n vé xem hòa nhạc có sẵn, mỗi vé có một mức giá nhất định. Sau đó, m khách hàng lần lượt đến. Mỗi khách hàng thông báo mức giá tối đa mà họ sản sàng trả cho một vé và sau đó họ sẽ nhận được một vé với mức giá gần nhất có thế sao cho không vượt quá mức giá tối đa.

Định dạng đầu vào: Dòng đầu tiên chứa các số nguyên n và m: số lượng vé và số lượng khách hàng. Dòng tiếp theo ghi n số nguyên h1, h2,.., hn là giá của từng vé. Dòng cuối cùng chứa m số nguyên t1, 2,.., tm: giá tối đa cho mỗi khách hàng theo thứ tự họ đến.

Ràng buộc: 1 <= n, m ≤ 2.10^5; 1 <= ti, hi <= 10^9

Định dạng đầu ra: In cho mỗi khách hàng giá mà họ sẽ trả cho vé của họ. Sau đó, vé không thể được mua lại lần nữa. Nếu khách hàng không lấy được vé nào, hãy in -1.

Input:

5 3
5 3 7 8 5
4 8 3

Output:

3
8
-1

Cho dãy A đã sắp xếp tăng dần. Với mỗi truy vấn X, tìm số nhỏ nhất trong dãy A mà lớn hơn hẳn X (lớn hơn chặt).

Dữ liệu vào:

Dòng 1: N và Q.

Dòng 2: Dãy A.

Q dòng tiếp theo: Mỗi dòng là số X.

Dữ liệu ra:

Giá trị tìm được hoặc "Khong".

Ràng buộc:

1 <= N, Q <= 10^5

Ví dụ:

Input:

5 2 
1 4 5 5 9 
5 
9

Output:

9 
Khong

Cho dãy A đã sắp xếp tăng dần. Với mỗi truy vấn X, hãy tìm số nhỏ nhất trong dãy A mà có giá trị lớn hơn hoặc bằng X. Nếu không có số nào thỏa mãn, in ra "Khong".

Dữ liệu vào:

Dòng 1: N và Q.

Dòng 2: Dãy A.

Q dòng tiếp theo: Mỗi dòng là một số X.

Dữ liệu ra:

Giá trị tìm được hoặc "Khong".

Ràng buộc:

1 <= N, Q <= 10^5

Ví dụ:

Input:

5 2 
1 4 5 8 9 
6 
10

Output:

8 
Khong

Cho dãy A đã sắp xếp tăng dần. Hãy đếm xem số X xuất hiện bao nhiêu lần trong dãy.

Dữ liệu vào:

Dòng 1: N và X.

Dòng 2: N số nguyên dãy A.

Dữ liệu ra:

Số lần xuất hiện của X.

Ràng buộc:

1 <= N <= 10^5

|A[i]|, |X| <= 10^9

Ví dụ:

Input:

7 2 
1 1 2 2 2 3 4

Output:

3

Cho một mảng A nguyên gồm N phần tử đã sắp xếp tăng dần, hãy tìm chỉ số của phần tử xuất hiện đầu tiên trong mảng, ví dụ mảng 1, 3, 4, 5, 5, 5, 6, 7. Nếu tìm số 5 thì số 5 xuất hiện đầu tiên sẽ có chỉ số 3, chỉ số này được in ra. Nếu không tìm thấy thì in ra -1

Ràng buộc: ~0 < N \leq 10^6~, ~-10^6 < A[i] \leq 10^6~

Input 01:

8 5
1 3 4 5 5 5 6 7

Output 01:

3

Input 02:

7 -3
-3 -3 -1 4 5 6 7

Output 02:

0

Input 03:

6 10
1 3 4 5 6 7

Output 03:

-1

Một buổi tối nọ, HCN tổ chức một bữa tiệc ở quán cà phê của mình.

Có n người xuất hiện, người thứ i có chiều cao h;. Những bữa tiệc thì không thế thiếu đi những hoạt động vui vẻ nên HCN quyết định ghép các cặp hai người cho một trò chơi team-building của mình. Vì không muốn để cho các cặp đôi trông quá chênh lệch về chiều cao, HCN đã đưa ra yêu cầu:

Người thứ i và người thứ j (i ‡ j) có thể ghép cặp được với nhau nếu 90% * hj ≤ hi ≤ hj. Hai cách ghép cặp (i, j) và cặp (j, i) được coi là một.

Với số lượng người tham dự nhỏ HCN có thể dễ dàng tính ra được số cách ghép các cặp khác nhau, nhưng do đã lỡ tay mời quá nhiều người nên việc tính toán của HCN trở nên khó khăn hơn. Hãy giúp HCN làm công việc này nhé.

Đầu vào:

• Dòng đầu tiên chứa số nguyên dương n - Số người ở bữa tiệc (1 ≤ n ≤ 10^5).

• Dòng tiếp theo chứa n số nguyên dương h1, h2, h3, ..., hn tương ứng với chiều cao từng người (hi ≤ 10^9).

Đầu ra:

In ra số cách chọn các cặp khác nhau.

Input:

6
100 89 90 101 91 99

Output:

11

Cho dãy số A và số nguyên K.

Hãy tìm số lượng số chẵn nhiều nhất có thể có trong một đoạn con liên tiếp độ dài K.

Input:

• Dòng 1: N, K.

• Dòng 2: N số nguyên A[i].

Output:

• Số lượng số chẵn nhiều nhất trong cửa sổ K.

Ví dụ 1:

Input:

7 3
1 2 4 5 6 8 1

Output:

3

Ví dụ 2:

Input:

5 2
1 3 5 7 9

Output:

0

Cho dãy số nguyên A gồm N phần tử và số nguyên K.

Hãy tìm giá trị tổng nhỏ nhất của K phần tử liên tiếp trong dãy.

Input:

• Dòng 1: N, K (1 <= K <= N <= 10^5).

• Dòng 2: N số nguyên A[i] (|A[i]| <= 10^9).

Output:

• Tổng nhỏ nhất tìm được.

Ví dụ 1:

Input:

6 3
10 2 5 1 8 9

Output:

8

Ví dụ 2:

Input:

5 2
10 20 30 40 50

Output:

30

Cho một chuỗi ký tự S chỉ gồm các chữ cái tiếng Anh thường và hoa, chữ số và ký tự đặc biệt. Hãy tìm độ dài của chuỗi con liên tiếp dài nhất mà trong đó không có ký tự nào bị lặp lại.

Input:

• Một dòng duy nhất chứa chuỗi S (độ dài 1 ≤ len(S) ≤ 10^5).

Output:

• In ra một số nguyên là độ dài lớn nhất tìm được.

Gợi ý thuật toán: Sử dụng kỹ thuật Hai con trở (Two Pointers) hoặc Cửa sổ trượt co giãn.

• Dùng 2 biến (L (trái) và R (phải).

• Di chuyển R sang phải. Dùng một mảng đếm (hoặc Map) để kiểm tra ký tự S[R] đã xuất hiện trong đoạn [L, R] chưa.

• Nếu đã xuất hiện, tăng L lên để loại bỏ ký tự trùng lặp đó.

• Cập nhật độ dài max ans = max(ans, R - L + 1).

Ví dụ:

Test 1:

Input:

abcabcbb

Output:

3

Test 2:

Input:

pwwkew

Output:

3

Cho dãy số nguyên A có N phần tử và số nguyên K. Hãy tìm giá trị trung bình cộng lớn nhất của K phần tử liên tiếp trong dãy. Giá trị trung bình của đoạn từ i đến i + K - 1 được tính bằng: (Ai + Ai+1 + ... + Ai+K-1)/K.

Input:

• Dòng đầu tiên chứa N và K (1 ≤ K ≤ N ≤ 10^5).

• Dòng thứ hai chứa N số nguyên A; (-10^4 ≤ Ai ≤ 10^4).

Output:

• In ra giá trị trung bình lớn nhất. Kết quả có thể là số thực (hệ thống chấm chấp nhận sai số 10^-5).

• Lưu ý khi code: Với C++, dùng fixed và setprecision(5) để in.

Gợi ý thuật toán: Về mặt toán học, vì K là hằng số dương, nên để Trung bình lớn nhất thì Tổng của K phần tử phải lớn nhất. Ta tìm tổng lớn nhất của cửa sổ K phần tử (Sliding Window), sau đó lấy tổng đó chia cho K (ép kiểu sang số thực).

Vi dụ:

Test 1:

Input:

4 4
1 12 -5 -6

Output:

0.50000

Test 1:

Input:

6 3
1 12 -5 -6 50 3

Output:

15.66667

Cho mảng AI gồm N phần tử và số X. Nhiệm vụ của bạn là tìm cặp phần tử A[i] - A[j] = X. Nếu tồn tại A[i] - A[j] = X đưa ra 1, ngược lại đưa ra -1.

Đầu vào: Dòng thứ nhất là cặp số N, X; Dòng tiếp theo là N số Ali) là các phần tử của mảng A.

Ràng buộc: 1≤ N ≤10^5; 1≤ X, A[i] ≤10^5.

Input:

5 4
8 4 3 1 7

Output:

1

Trong lớp học có n bạn nam và m bạn nữ. Các bạn nam có chiều cao là a1, a2, ..., an. Các bạn nữ có chiều cao là b1, b2, .., bm. Nhân dịp lễ tổng kết cuối năm, cả lớp dự định tổ chức buổi khiêu vũ nhưng có điều kiện là trong một đôi khiêu vũ bất kỳ, bạn nam phải cao hơn bạn nữ. Và mỗi bạn không tham gia quá 1 đôi khiêu vũ. Hãy tính số lượng cặp đôi nhiều nhất thỏả mãn yêu cầu trên.

Đầu vào: gồm 3 dòng

• Dòng thứ nhất là hai số n, m mỗi số cách nhau một khoảng trắng.

• Dòng thứ hai gồm n số nguyên a1, a2, .., an là chiều cao các bạn nam.

• Dòng thứ ba gồm m số nguyên b1, b2, .... bm là chiều cao các bạn nữ.

Ràng buộc: 1 <= n,m <= 10^5; 1 <= a[i],b[i] <=10^6

Input:

5 5
2668 2956 20933 21199 24224
11521 13084 19573 25628 28958

Output:

3

Để tiếp tục nâng cao trải nghiệm cho người dùng, nhà mạng HNOJ tiếp tục xây dựng dịch vụ kiểm tra số dư tài khoản chỉ với một nút gửi. Bạn vừa gửi yêu cầu kiểm tra tài khoản và nhận được thông báo, hãy tính số tin nhắn bạn còn có thể gửi được với số dư hiện tại, với chi phí cho mỗi tin nhắn cơ sở vẫn giữ là 3 dogecoin.

Input:

Gồm một xâu có dạng: So du tai khoan: (x) dogecoin

Với x là số dư hiện tại của người dùng (x nguyên dương, |x| ≤ 3000).

Output: In ra số lượng tin nhắn cơ sở bạn có thể gửi được với số dư x.

Sample Test

Input:

So du tai khoan: 200 dogecoin

Output:

66

Cho một xâu kí tự S chỉ bao gồm chữ số và chữ cái, hãy tính tổng chữ số xuất hiện trong xâu

Nhập vào 1 dòng duy nhất chứa xâu S

Ràng buộc: ~1 \leq len(S) \leq 10000~

Input:

315abSA9172WSbn2d0

Output:

30

Giải thích: Tổng các số xuất hiện trong xâu = 3 +1 +5 +9 +1 +7 +2 +2 + 0 = 30

Cho xâu kí tự S bao gồm chữ cái và chữ số, thực hiện tách riêng chữ số và chữ cái của S.

In ra dòng 1 in ra những chữ số xuất hiện trong S theo thứ tự xuất hiện, dòng 2 in ra những chữ cái xuất hiện trong S theo thứ tự xuất hiện.

Ràng buộc: ~1 \leq len(S) \leq 10000~

Input:

I68c8SASicab6AiI9i

Output:

68869
IcSASicabAiIi

Trường đại học ABC tổ chức cấp email cho sinh viên mới nhập học. Email và mật khấu sẽ được cấp dựa trên tên của sinh viên và ngày sinh của sinh viên đó. Bạn hãy viết chương trình để cấp tài khoản theo yêu cầu như sau, tên email được tạo bằng cách lấy tên của sinh viên và ghép với các chữ cái đầu tiên của họ và tên đệm tất các ký tự trong email đều ở dạng in thường, ví dụ sinh viên có tên "Nguyen Van Long" sẽ được cấp email "longnv@xyz.edu.vn".

Mật khẩu sẽ dựa trên ngày sinh của sinh viên đó, bằng cách ghép ngày tháng năm lại với nhau, ví dụ sinh viên sinh ngày 27/04/2002 sẽ có mật khẩu là 2742002. Ngoài ra sẽ có những trường hợp sinh viên bị trùng tên email, ví dụ, sinh viên "Nguyen Van Long" sẽ được cấp email "longnv@xyz.edu.vn", sinh viên tên "Ngo Van Long" cũng sẽ được cấp email "longnv@xyz.edu.vn", vì thế nhà trường quy định, theo thứ tự tên trong danh sách, nếu email được cấp của sinh viên hiện tại đã được cấp cho một sinh viên trước đó thì thêm số thứ tự vào tên email.

Ràng buộc:

~1 \leq N ≤ 5000~

Dòng thông tin của sinh viên không quá 1000 kí tự, dữ liệu đảm bảo thông tin cuối cùng trong dòng là ngày sinh của sinh viên.

In ra ra email và mật khẩu được cấp của mỗi sinh viên trên 2 dòng. Chú ý các sinh viên email bị trùng tên sẽ được thêm số thứ tự vào sau.

Input:

4
Nguyen quang Truong 24/12/2005
Le   van   Tho 06/07/2005
ngo quan Truong 12/3/2005
le van   Sen 02/4/2005

Output:

truongnq@xyz.edu.vn
24122005
tholv@xyz.edu.vn
672005
truongnq2@xyz.edu.vn
1232005
senlv@xyz.edu.vn
242005

Cho một xâu là tên người chỉ bao gồm các kí tự là chữ cái và dấu cách, giữa các từ trong câu có thế tồn tại nhiều dầu cách hãy chuẩn hóa tên người theo 2 mẫu được yêu cầu trước. Xem output để rõ hơn về cách chuẩn hóa.

Ràng buộc: Xâu kí tự tên người có không quá 1000 kÍ tự

Dòng đầu tiên in ra theo mẫu chuẩn hóa 1. Dòng thứ 2 in ra theo mẫu chuẩn hóa 2.

Input:

le Thi   huyen Thanh

Output:

Le Thi Huyen, THANH
THANH, Le Thi Huyen

Cho 2 xâu kí tự S1 và S2 chỉ bao gồm chữ cái in hoa và in thường, hãy tìm các kí tự xuất hiện trong xâu S1 mà không xuất hiện trong xâu S2 và các kí tự chỉ xuất hiện trong xâu S2 mà không xuất hiện trong xâu S1. Các ký tự được in ra theo thứ tự từ điển và chỉ liệt kê mỗi ký tự một lần.

Ràng buộc: ~1 \leq len(S1) ≤ 100000; 1 \leq len(S2) ≤ 100000~

Dòng đầu tiên in ra các ký tự chi xuất hiện trong S1 mà không xuất hiện trong S2. Dòng thứ 2 in ra các ký tự chỉ xuất hiện trong S2 mà không xuất hiện trong S1.

Input:

hoccongnghe
laptrinh

Output:

cego
ailprt