Cho mảng A[] gồm N số nguyên, gọi K là tích các số trong mảng A[] bạn hãy xác định xem K có phải là số chính phương không ? Nếu nó là số chính phương thì bạn hãy in ra 28tech, đồng thời bạn phải in ra căn bậc hai của K sau khi chia dư căn này cho số 10^9 + 7 (1000000007), ngược lại nếu K không phải là số chính phương thì bạn chỉ cần in ra 29tech.

Đầu vào

• Dòng 1 là N : Số lượng phần tử trong mảng

• Dòng 2 là N số trong mảng A[]

Giới hạn

• 1<=N<=10^3

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

Đầu ra

• In ra 29tech nếu K không phải là số chính phương, ngược lại in ra 28tech và căn bậc hai của K sau khi chia dư căn này cho 10^9 + 7.

Ví dụ :

Input 01

4
2 2 4 9

Output 01

28tech 12

Input 02

3
3 5 5 10

Output 02

29tech

28Tech gọi 2 số x và x + 2 là 2 số nguyên tố sinh đôi nếu cả 2 số này đều là số nguyên tố, bạn hãy giúp 28Tech đếm số lượng cặp số nguyên tố sinh đôi trong khoảng 2 số a, b.

Lưu ý là cặp số (x, y) sẽ được coi là giống cặp số (y, x)

Đầu vào

• Dòng duy nhất chứa 2 số a, b

Giới hạn

• 1≤a≤b≤10^9

• b-a≤10^6

Đầu ra

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

Ví dụ :

Input 01

3 13

Output 01

3

Giải thích test :

Các cặp thỏa mãn là (3, 5), (5, 7) và (11, 13)

Bài này yêu cầu các bạn hãy đếm số lượng số có chính xác 9 ước trong đoạn giữa 2 số [a, b]

Đầu vào

• Dòng đầu chứa T : số bộ test

• Mỗi bộ test chứa 2 số a, b

Giới hạn

• 1≤T≤10^4

• 1≤a≤b≤10^8

Đầu ra

• In ra đáp án của mỗi test trên từng dòng

Ví dụ :

Input 01

2
1 50
1 200

Output 01

1
3

Bài này yêu cầu các bạn hãy tính tổng chữ số của 2^N, ví dụ N = 6 thì 2^6 = 64 ta có tổng các chữ số của nó là 10.

Đầu vào

• Dòng đầu chứa T : số bộ test

• Mỗi bộ test chứa số nguyên N

Giới hạn

• 1≤T≤10^4

• 0≤N≤1000

Đầu ra

• In ra đáp án của mỗi test trên từng dòng

Ví dụ :

Input 01

2
3 
4

Output 01

8
7

Cho mảng A[] gồm N phần tử, gọi X là tích các phần tử trong mảng A[], bạn hãy xác định xem X có bao nhiêu chữ số 0 liên tiếp tính từ chữ số cuối cùng của X.

Ví dụ A = [2, 5, 10, 3, 1, 2], X = 600 sẽ có 2 chữ số 0 tận cùng tính từ cuối

Gợi ý : Tương tự như bài trailing zero, bạn cần phần tích thừa số nguyên tố của từng số trong mảng A[] để đếm số lần xuất hiện của số 2 và 5

Đầu vào

Dòng 1 là N

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

Giới hạn

1<=N,M<=10^6

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

Đầu ra

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

Ví dụ :

Input 01

6
2 5 10 3 1 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

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

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 N đoạn thẳng trên trục tọa độ Ox, mỗi đoạn thẳng bắt đầu từ hoành độ L và kết thúc tại hoành độ R. 2 đoạn thẳng được coi là không giao nhau nếu điểm bắt đầu của đoạn thẳng này lớn hơn hoặc bằng điểm kết thúc của đoạn thẳng trước.

Ví dụ [2, 5] và [5, 10] là 2 đoạn thẳng không giao nhau, trong khi đó [1, 3] và [2, 5] là 2 đoạn thẳng giao nhau.

28Tech cảm thấy khó chịu khi phải nhìn những đoạn thẳng bị giao cắt nhau, bây giờ anh ấy muốn bạn xóa đi 1 số đoạn thẳng ít nhất để tất cả những đoạn thẳng còn lại sẽ không còn giao nhau.

Đầu vào

Dòng 1 là N : số lượng đoạn thẳng

N dòng tiếp theo mỗi dòng là [Li, Ri] tương ướng với điểm bắt đầu và kết thúc của đoạn thẳng thứ i

Giới hạn

1<=N<=10^5

0<=L[i]<R[i]<=10^9</p>

Đầu ra

In ra số lượng đoạn thẳng ít nhất cần loại bỏ để những đoạn thẳng còn lại không bị giao nhau

Ví dụ :

Input 01

5
4 5
2 3
1 4
6 7
5 9

Output 01

2

Giải thích test :

Loại bỏ đi đoạn thẳng [1, 4] và [5, 9] thì 3 đoạn thẳng còn lại sẽ không bị giao nhau

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ệ 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