Một con ếch đang đứng ở chỉ số 0 của mảng A[], giả sử con ếch đang ở chỉ số i của mảng A[] thì ở mỗi lần di chuyển nó có thể nhảy sang phải với số bước nhảy lớn nhất bằng với A[i], mỗi bước nhảy sẽ giúp con ếch di chuyển sang phải 1 vị trí trong mảng A[]. Giả sử A[i] = 5 thì từ chỉ số i con ếch có thể nhảy sang phải tối đa 5 vị trí. Bạn hãy xác định xem con ếch có thể di chuyển tới phần tử cuối cùng trong mảng A[] được hay không?

Ví dụ A[] = [1, 3, 2, 2, 0, 0] thì con ếch có thể di chuyển qua các chỉ số như sau : 0->1-> 3->5

Gợi ý : Ở mỗi vị trí I xem từ đó nhảy xa nhất là bao nhiêu, nếu tại 1 vị trí bất kỳ mà nhảy được tới N - 1 thì có thể kết luận ngay.

Đầ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^3

Đầu ra

In ra 28tech nếu con ếch có thể đến được vị trí cuối cùng, 29tech nếu không thể.

Ví dụ :

Input 01

6
1 3 2 2 0 0

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

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

28Tech đang có một chiến lược mua bitcoin, may mắn là anh ta biết trước giá của bitcoin trong N ngày liên tiếp luôn rồi nhưng không may là anh ta không biết ngày nào mua ngày nào bán để kiếm được lợi nhuận lớn nhất sau N ngày. Ở mỗi ngày anh ta có thể mua, bán hoặc không mua bán gì cả. Tuy nhiên ở mỗi ngày anh ta nếu đang giữ bitcoin mua ở 1 ngày nào trước đó rồi thì anh ta không được mua thêm nữa mà chỉ có thể bán hoặc giữ. Tất nhiên anh ta chỉ có thể bán vào những ngày sau ngày mua.

Bạn hãy giúp 28Tech tìm ra lợi nhuận lớn nhất có thể nhé.

Ví dụ giá bitcoin trong N ngày sẽ là [1, 3, 6, 3, 2, 4, 5, 7, 6, 1] thì anh ta sẽ mua ở ngày 1, bán ở ngày 3 lợi nhuận thu được là 5, tiếp tục mua bitcoin ở ngày thứ 5 và bán ở ngày thứ 8 lợi nhuận thu được là 5. Vậy tổng lợi nhuận lớn nhất thu được là 10. Ngày thứ 9, 10 thấy giá giảm nên sẽ không mua.

Đầu vào

Dòng 1 là N : số ngày

Dòng 2 là N số tương ứng với giá bitcoin trong N ngày

Giới hạn

1<=N<=10^6

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

Đầu ra

In ra lợi nhuận lớn nhất mà 28Tech có thể kiếm được.

Ví dụ :

Input 01

6
1 6 7 9 2 3

Output 01

9

Hiện tại 28Tech đang có N đô la trong ngân hàng, anh ta sẽ cho bạn luôn số tiền này, thật sự rất hào phóng. Tuy nhiên bạn có thể tối đa số tiền bạn lấy về bằng cách hoán đổi 2 chữ số của N đúng 1 lần duy nhất, vậy thì bạn sẽ nhận được số tiền tối đa là bao nhiêu.

Ví dụ 28Tech có 9125 đô la trong ngân hàng thì bạn sẽ hoán đổi số 1 và 5 để có thể lấy về 9521 đô la

Đầu vào

Dòng 1 là N

Giới hạn

N là số nguyên không âm có không quá 1000 chữ số

Đầu ra

In ra số tiền tối đa mà bạn có thể lấy được từ 28Tech

Ví dụ :

Input 01

9125

Output 01

9521