Cho mảng A[] gồm N phần tử, 28tech muốn bạn kiểm tra xem liệu có thể lật ngược 1 dãy con liên tiếp bất kỳ trong mảng 1 lần duy nhất để tạo thành mảng tăng dần hay không?

Ví dụ A = [1, 2, 5, 4, 3, 7, 8 ,9] bạn có thể lật ngược lại đoạn [2, 5, 4] để tạo thành mảng [1, 2, 3, 4, 5, 7, 8, 9]

Gợi ý : Tìm left là chỉ số bắt đầu của dãy còn cần lật (a[left] > a[left + 1]) và chỉ số right là chỉ số cuối cùng của dãy con cần lật (a[right] < a[right - 1]). Nếu left ko tồn tại tức mảng đã tăng dần rồi, còn nếu left và right tồn tại thì lật ngược đoạn đó là và kiểm tra xem sau khi lật thì mảng có tăng dần không?

Đầu vào

Dòng 1 là N : các phần tử trong mảng

Dòng 2 là N số trong mảng

Giới hạn

1<=N<=10^6

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

Đầu ra

In ra 28tech nếu có thể lật ngược mảng con để tạo thành mảng tăng dần, ngược lại in ra 29tech

Ví dụ :

Input 01

5
1 4 3 2 5

Output 01

28tech

Input 02

5
1 4 2 3 5

Output 02

29tech

Tiếp tục câu chuyện về chiều cao tại Vương Quốc 28Tech, hôm nay Quốc Vương tại 28Tech muốn N cư dân của mình xếp thành 1 hàng dài và đánh số cho họ từ 1 tới N. Quốc Vương sẽ yêu cầu mỗi người tìm ra vị trí của người đứng trước gần họ nhất mà có chiều cao thấp hơn họ. Tất nhiên sẽ có những người không thể tìm được người thấp hơn mình. Nhiệm vụ của bạn rất đơn giản, hãy tìm vị trí của người đứng trước gần nhất của mọi cư dân trong Vương Quốc thịnh vượng này.

Đầu vào

• Dòng 1 là N số lượng cư dân

• Dòng 2 là chiều cao của cư dân thứ 1 tới thứ N

Giới hạn

1<=N<=10^6

Chiều cao của cư dân thuộc đoạn [1, 999999999]

Đầu ra

In ra vị trí của người thấp hơn gần nhất với mỗi cư dân trong Vương Quốc, nếu không thể tìm được vị trí hợp lý này thì in ra 0.

Ví dụ :

Input 01

6
1 3 7 2 4 6

Output 01

0 1 2 1 4 5

Tại Vương Quốc 28Tech có N cư dân, mỗi cư dân có một chiều cao . Vì yêu thích sự công bằng nên Quốc Vương của 28Tech muốn tất cả mọi người đều có phải có cùng chiều cao với nhau để tránh tình trạng body shaming giữa các cư dân.

Bây giờ Quốc Vương sẽ đi tìm 1 người bất kỳ mà ông ta thích trong N người đó và chọn làm hạt giống, người này và những người có cùng chiều cao với hạt giống kia thực sự may mắn bởi vì Quốc Vương có một ý tưởng thực sự rất đáng sợ. Ông ta sẽ cắt bớt chân của những người cao hơn người hạt giống hoặc kéo chân những người thấp hơn người hạt giống sao cho tất cả mọi người có cùng chiều cao với người hạt giống. Tuy nhiên ý tưởng của Quốc Vương bị phản đối bởi cư dân trong Vương Quốc của mình thành ra Quốc Vương phải đi tìm một hạt giống sao cho việc cắt bớt chân và kéo dài chân gây ít đau đớn nhất. Quốc Vương nhờ bạn tìm giúp hạt giống này !

Biết rằng khi chiều cao của 1 dân cư là X cao(thấp) hơn người hạt giống có chiều cao là Y thì sự đau đớn khi cắt (kéo dài) chân sẽ là |X - Y| (Đây là ý nghĩa của giá trị tuyệt đối).

Bạn hãy xác định xem với hạt giống tối ưu thì tổng sự đau đớn của mọi dân cư trong Vương Quốc 28Tech sẽ là bao nhiêu để tất cả mọi người có cùng chiều cao với người hạt giống đó.

Đầu vào

• Dòng 1 là N : số lượng dân cư

• Dòng 2 gồm N số là chiều cao của các cư dân

Giới hạn

• Vương Quốc có không quá 1 triệu cư dân

• Chiều cao của cư dân thuộc đoạn [1, 999999999]

Đầu ra

• In ra tổng số đau đớn của mọi cư dân được coi là phương án tối ưu

Ví dụ :

Input 01

5
3 9 10 1 8

Output 01

15

28Tech định tổ chức một kỳ thi Hackathon, kỳ thi này sẽ gồm N cuộc thi nhỏ diễn ra lần lượt. Mỗi cuộc thi sẽ chứa 1 số problem cụ thể, Hackathon sẽ diễn ra trong H giờ liên tiếp. Mỗi giờ bạn có thể quyết định mình sẽ giải được K problem.

Nếu cuộc thi nào mà bạn đã giải hết các problem của cuộc thi đó thì bạn không thể dành thời gian thừa để làm các problem trong các cuộc thi khác.

Nhiệm vụ của bạn là xác định giá trị nhỏ nhất của K để đảm bảo được mình sẽ hoàn thành tất cả problem trong các cuộc thi kịp thời gian.

Đầu vào

Dòng 1 là N và H

Dòng 2 là N số tương ứng với số problem trong các cuộc thi nhỏ của Hackathon

Giới hạn

1<=N<=2.10^5

N<=H<=10^9

Các problem trong các cuộc thi là số nguyên dương không vượt quá 10^6

Đầu ra

In ra giá trị nhỏ nhất của K tìm được

Ví dụ :

Input 01

5 8
5 5 4 2 2

Output 01

3

Giải thích test :

Các cuộc thi mất lần lượt 2, 2, 2, 1, 1 giờ để hoàn thành

Lớp cấu trúc dữ liệu và giải thuật của 28Tech có N bạn tham gia với chiều cao khác nhau đôi một, ban đầu N bạn này được xếp vào 1 hàng ngang với thứ tự ngẫu nhiên.

Tuy nhiên thì 28Tech muốn rằng các bạn này cần phải xếp thành 1 hàng theo chiều cao tăng dần, để đạt được điều này thì cần phải hoán đổi vị trí 1 số bạn trong hàng.

Nhiệm vụ của bạn là hãy giúp 28Tech đếm xem cần tối thiểu bao nhiêu hoán đổi vị trí các bạn học viên để hàng người tăng dần về chiều cao.

Đầu vào

Dòng 1 là N : số lượng học viên lớp CTDL & GT

Dòng 2 gồm N số khác nhau tương ứng với chiều cao của các bạn trong lớp

Giới hạn

1<=N<=2.10^5

Chiều cao là số nguyên dương 32bit

Đầu ra

In ra số hoán đổi tối thiểu để sắp tăng dần chiều cao của các bạn học viên

Ví dụ :

Input 01

5
1 5 4 3 2

Output 01

2

Cho mảng A[] có N phần tử, mảng B[] có M phần tử. Gọi a là những phần tử thuộc mảng A[], b là những phần tử thuộc mảng B[], nhiệm vụ của bạn là hãy đếm số cặp (a, b) thỏa mãn a^b > b^a.

Ví dụ A = [3, 9, 7, 2] và B = [2, 5] thì có những cặp thỏa mãn là (3, 2), (3, 5), (2, 5)

Gợi ý : a^b > b^a nếu a < b, ví dụ a = 2, và b = 5 thì 2^5 = 32 > 5^2 = 25. Có 1 vài ngoại lại là cặp (a, b) = (3, 2) thì lại ngược lại và cặp (2, 4) thì bằng nhau cần loại bỏ khi đếm và chú ý khi a = 0, a = 1 là những trường hợp đặc biệt.

Vậy đối với mỗi phần tử trong mảng A[] bạn cần đếm xem trong mảng B[] có bao nhiêu phần tử lớn hơn nó.

Đầu vào

Dòng 1 là N và M

Dòng 2 gồm N số trong mảng A[]

Dòng 3 gồm M số trong mảng B[]

Giới hạn

1<=N,M<=2.10^5

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

Đầu ra

In ra đáp án của bài toán

Ví dụ :

Input 01

4 2
3 9 7 2
2 5

Output 01

3