Tiếp nối với bài bộ ba tam giác lúc trước thì 28Tech muốn bạn kiểm tra xem một mảng số nguyên A[] có tồn tại bộ ba A[i], A[j], A[k] với i < j < k và A[i] < A[j] < A[k] hay không ? Nếu có thì hãy in ra 28tech, ngược lại in ra 29tech

Gợi ý : Đối với mỗi chỉ số I bạn cần xác định xem đứng trước I có giá trị nào nhỏ hơn nó và có giá trị nào đứng sau I có giá trị lớn hơn nó hay không. Nếu có thì sẽ tồn tại cặp 3 số đề bài yêu cầu. Dùng 2 mảng, 1 mảng để lưu xem mỗi chỉ số I trong mảng có giá trị nhỏ hơn đứng trước không, 1 mảng để lưu xem mỗi giá trị I trong mảng có giá trị lớn hơn đứng sau hay không. Duyệt mọi chỉ số từ 0 tới N - 1 và kiểm tra đồng thời giá trị của 2 mảng này là có kết quả.

Đầu vào

Dòng 1 là N : số lượng phần tử trong mảng A[]

Dòng 2 là các phần tử trong mảng A[]

Giới hạn

1<=N<=10^6

0<=A[i]<=10^9

Đầu ra

In ra 28tech nếu có thể tìm được bộ 3 lớn dần, 29tech nếu không thể.

Ví dụ :

Input 01

5
1 0 0 3 4

Output 01

28tech

3 cạnh a, b, c có thể hình thành một tam giác nếu 3 cạnh này đều là số nguyên dương và thỏa mãn bất đẳng thức tam giác tức là tổng 2 cạnh luôn lớn hơn cạnh còn lại. Cho một mảng số nguyên A[] gồm N phần tử, bạn hãy xác định xem trong mảng A[] có bao nhiêu bộ số A[i], A[j], A[k] có thể tạo thành 3 cạnh của một tam giác.

Ví dụ A[] = [1, 6, 7, 9, 2] thì có thể tạo thành các bộ 3 số (6, 7, 9), (2, 6, 7)

Gợi ý : Sort mảng tăng dần, khi đó sẽ xét từ cuối mảng về gọi là A[i] và coi A[i] là số lớn nhất trong bộ 3 số, dùng 2 biến left = 0, right = i - 1 để xét 2 số còn lại. Nếu A[left] + A[right] > A[i] thì tất cả những số từ left + 1 tới right - 1 có thể kết hợp với left, right, I để tạo thành bộ 3 thỏa mãn. Khi đó có thể giảm right đi để lựa bộ khác, nếu A[left] + A[right] <= A[i] thì bắt buộc phải tăng left lên để tổng của 2 số còn lại lớn hơn.

Đầu vào

Dòng 1 là N : số lượng phần tử trong mảng A[]

Dòng 2 là các phần tử trong mảng A[]

Giới hạn

1<=N<=10^4

-10^3<=A[i]<=10^3

Đầu ra

In ra số bộ 3 thỏa mãn

Ví dụ :

Input 01

5
1 6 7 9 2

Output 01

2

Cho mảng A[] gồm N phần tử, bạn hãy xác định số nguyên dương nhỏ nhất chưa xuất hiện trong mảng A[].

Đầu vào

Dòng 1 là N : số lượng phần tử trong mảng A[]

Dòng 2 là N số của mảng A[]

Giới hạn

1<=N<=10^6

0<=A[i]<=10^6

Đầu ra

In ra kết quả của bài toán

Ví dụ :

Input 01

6
1 2 3 7 8 10

Output 01

4

Cửa hàng 28Toys có N đồ chơi được gán giá cho mỗi trò chơi được mô tả bằng mảng price[], trong đó price[i] đô la là giá của đồ chơi thứ i. Tèo là một học sinh lớp 6 mới mượn được mẹ K đô la, Tèo muốn sử dụng số tiền này một cách tối ưu bằng cách chọn số lượng đồ chơi lớn nhất có thể mua bằng K đô la. Bạn hãy giúp Tèo tìm số lượng đồ chơi tối đa mà Tèo có thể mua

Ví dụ price = [3, 10, 2, 1, 9, 20, 8] và K = 16 thì Tèo có thể mua tối đa 4 đồ vật là [3, 2, 1, 9]

Gợi ý : Sắp xếp tăng dần để lựa những đồ vật rẻ nhất và chọn ra những số đầu tiên có tổng <= K

Đầu vào

Dòng 1 là N và K : số lượng đồ chơi và số tiền của Tèo

Dòng 2 gồm N số trong mảng price[] là giá triền các đồ chơi từ 1 tới N

Giới hạn

1<=N<=2.10^5

1<=K<=2.10^14

0<=A[i]<=10^9

Đầu ra

In ra số đồ chơi tối đa Tèo có thể mua

Ví dụ :

Input 01

7 16
3 10 2 1 9 20 8

Output 01

4

Tại lớp học của 28Tech có N bạn học sinh tham gia, 28Tech muốn chọn ra K bạn trong N bạn này để thành lập nhóm làm contest. Tuy nhiên 28Tech muốn độ chênh lệch trình độ của các bạn trong nhóm là nhỏ nhất có thể. Trong đó độ chênh lệch trình độ của nhóm bằng hiệu của bạn có trình độ lớn nhất và nhỏ nhất trong nhóm. Mỗi bạn tham gia lớp học tại 28Tech có trình độ tương đương với điểm số được cho trong mảng A[], A[i] là trình độ của bạn học sinh thứ i. Bây giờ bạn hãy tìm ra độ chênh lệch nhỏ nhất về trình độ của 1 nhóm làm contest.

Ví dụ A = [3, 9, 10, 20, 14, 7] và K = 3 thì sẽ chọn nhóm [7, 9, 10] có độ chênh lệch tối ưu là 3.

Gợi ý : Sắp xếp rồi xét các cửa sổ cỡ K

Đầu vào

Dòng 1 là N : số lượng học sinh và K

Dòng 2 gồm N số trong mảng A[] là trình độ của các bạn từ 1 tới N

Giới hạn

1<=N<=10^6

0<=A[i]<=10^6

Đầu ra

In ra kết quả tối ưu tìm được

Ví dụ :

Input 01

6 3
3 9 10 20 14 7

Output 01

3