Con ốc sên đang ở gốc một cái cây cao v mét tính từ gốc. Ốc sên muốn bò lên ngọn cây để ăn những lá non trên đó. Ban ngày ốc sên bò được a mét lên trên, nhưng ban đêm khi ngủ nó bị trôi xuống b mét.

Yêu cầu: Cho các số nguyên ~a~, ~b~, ~v~, ~(1 <= b < a <= v <= 10^9)~. Hãy xác định số ngày cần thiết để ốc sên lên tới ngọn cây.

Ví dụ:

        INPUT               OUTPUT

        2 1 5                4

Tìm một số nguyên dương ~k~ nhỏ nhất sao cho tích các chữ số của ~k~ bằng ~n~ (~k~, ~n~ là 2 số nguyên dương).

Ví dụ:

        INPUT               OUTPUT

        72                  89

Số Palidrom là số đối xứng, nghĩa là đọc từ trái sang phải hay từ phải sang trái ta đều được 1 số.

Ví dụ: ~11~, ~121~, ~1331~, ….

Nhập ~2~ số nguyên dương ~m~, ~n~. Liệt kê dãy số vừa là số nguyên tố vừa là số Palidrom trong đoạn ~[m, n]~.

                INPUT                            OUTPUT

                100 200                          101 131 151 181 191

Đọc số nguyên dương n và dãy số ~a_1, a_2, …. a_n~.

Dòng thứ nhất ghi ~n~, dòng thứ hai ghi dãy số, mỗi phần tử cách nhau một dấu cách.

Ví dụ:

            INPUT                           OUTPUT

            6                               6
            11 21 15 17 13 19               11 21 15 17 13 19

Sử dụng hàm sắp xếp sort trong thư viện có sẵn để thực hiện việc sắp xếp tăng hoặc sắp xếp giảm.

Ví dụ:

                INPUT                       OUTPUT

                6                           11 13 15 17 19 21
                11 21 15 17 13 19           21 19 17 15 13 11

Tính tổng và tính trung bình cộng các phần tử của một dãy số.

Yêu cầu:

• dòng thứ nhất ghi tổng
• dòng thứ hai ghi giá trị trung bình cộng.

Ví dụ:

        INPUT                   OUTPUT

        6                       96
        11 21 15 17 13 19       16

Đếm xem có bao nhiêu phần tử có giá trị lớn hơn hoặc bằng trung bình cộng của dãy số, liệt kê các phần tử này.

Ví dụ:

        INPUT                       OUTPUT

        6                           21 17 19
        11 21 15 17 13 19           3 16

Tìm các vị trí ~i~ (nếu có) chia dãy số thành 2 phần có tổng bằng nhau. Nếu không có ghi ra ~-1~.

Ví dụ: ~n = 6;~ 1 3 4 2 7 3 → i = 4

giải thích: 1 + 3 + 4 + 2 = 7 + 3

Tìm giá trị lớn nhất và giá trị nhỏ nhất của dãy số.

            INPUT                       OUTPUT

            6                           10
            12 15 11 17 19 10           19

Tìm các vị trí phần tử đạt giá trị nhỏ nhất của dãy số.

Ví dụ:

INPUT                       OUTPUT

6                           2 5
12 10 11 17 10 11

Tìm giá trị nhỏ nhì (nếu có) của dãy số và đưa ra các vị trí đạt giá trị đó. Nếu không có thì ghi ra -1.

Ví dụ:

            INPUT                   OUTPUT

            6                       4
            1 3 4 2 7 3

Tìm giá trị lớn thứ k của dãy số. Nhập vào số lượng phần tử n và vị trí lớn thứ k (1 dòng), dòng thứ 2 là dãy số. Yêu cầu: Ghi ra vị trí lớn thứ k trong dãy số.

Ví dụ:

INPUT                           OUTPUT

6 3                             20
27 13 24 19 17 20                    

Tìm dãy 3 phần tử liên tiếp có tổng lớn nhất trong một dãy số có n phần tử (n > 3). Đưa tổng ra màn hình.

Ví dụ:

            INPUT                           OUTPUT

            6                               13
            1 3 4 2 7 3            

Nhập vào giá trị x. Tìm vị trí x (nếu có) trong dãy số có n phần tử và đếm số lượng phần tử có giá trị bằng x. Nếu không có ghi ra -1.

Ví dụ:

            INPUT                       OUTPUT

            6 2                         2 3 6
            1 3 3 5 7 3                 3

Cho số n, tìm số Fibonacci thứ n và hiển thị dãy sô.

Ví dụ:

                INPUT                       OUTPUT

                30                          832040
                                            1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040 

Liệt kê các dãy con liên tiếp không giảm (có nhiều hơn 1 phần tử) của dãy ban đầu, mỗi dãy trên 1 dòng.

Ví dụ:

            INPUT                       OUTPUT

            6                           3 4 6
            3 4 6 2 7 3                 2 7

Tìm số cặp ~(i, j)~ sao cho ~a_i + a_j = k~. Nếu không có ghi ra -1.

Giải thích: ~n = 6;~ dãy ~1 3 4 2 7 3; k = 4 → res = 2~

                    INPUT                           OUTPUT
                    6 4                             2
                    1 3 4 2 7 3 

Xóa phần tử thứ ~k~ của mảng ~a~ có ~n~ phần tử. Đưa ra số phần tử còn lại và mảng ~a~ sau khi xóa.

Ví dụ:

                INPUT                   OUTPUT

                6 4                     5
                5 7 3 4 6 9             5 7 3 6 9   

Xóa tất cả các phần tử chia hết cho ~k~ trong mảng ~a~ có ~n~ phần tử. Đưa ra số phần tử còn lại và mảng ~a~ sau khi xóa.

Ví dụ:

            INPUT               OUTPUT

            6 2                 3
            3 6 5 4 7 2         3 5 7   

Xóa các phần tử giống nhau trong dãy số, chỉ giữ lại những phần tử đại điện mỗi số. Sau khi xóa, đưa dãy số ra màn hình.

Ví dụ:

                INPUT                           OUTPUT

                6                               4
                3 6 5 3 7 3                     3 6 5 7

Chèn ~x~ vào phần tử thứ ~k~ của dãy số ~a~ có ~n~ phần tử. Đưa ra số phần tử và dãy số ~a~ sau khi chèn.

Ví dụ:

            INPUT                   OUTPUT

            6 4 8                   7
            4 6 5 9 3 7             4 6 5 8 9 3 7

Đếm số lần xuất hiện của mỗi phần tử trong dãy số.

Ví dụ:

            INPUT                   OUTPUT

            6                       3 2
            3 5 3 6 5 7             5 2
                                    6 1
                                    7 1

Nhập vào 1 mảng gồm n phần từ. Đảo ngược dãy số. Đưa dãy số đảo ngược ra màn hình.

Ví dụ:

                INPUT                       OUTPUT

                6                           6
                3 5 3 6 5 7                 7 5 6 3 5 3

Tìm dãy con liên tiếp không giảm dài nhất của 1 dãy số.

Yêu cầu: in ra số phần tử và dãy con liên tiếp dài nhất.

Ví dụ:

                INPUT                   OUTPUT

                6                       3
                3 2 5 7 4 6             2 5 7   

Tìm dãy con liên tiếp không giảm có tổng lớn nhất. Kết quả ghi ra tổng và liệt kê dãy các phần tử có tổng lớn nhất.

Ví dụ:

            INPUT                   OUTPUT

            6                       14
            3 2 5 7 4 6             2 5 7

Tìm dãy con bằng nhau liên tiếp trong 1 dãy số. Yêu cầu: liệt kê các phần tử của dãy con bằng nhau.

Ví dụ:

                INPUT                           OUTPUT

                6                               2 2 2
                2 2 2 7 4 4                     4 4

Tìm dãy con bằng nhau liên tiếp dài nhất trong 1 dãy số.

Yêu cầu: ghi ra tổng số phần tử và liệt kê các phần tử của dãy con bằng nhau.

Ví dụ:

                INPUT                           OUTPUT

                10                              4
                2 2 1 1 1 1 3 4 4 4             1 1 1 1   

Liệt kê các số chính phương có trong dãy số a. Nếu không có ghi số -1.

Ví dụ:

                    INPUT                           OUTPUT

                    10                              4 9 16 36
                    3 4 7 5 9 3 16 21 36 8                    

Liệt kê các số nguyên tố theo thứ tự từ nhỏ đến lớn trong dãy số ~a~.

Ví dụ:

                    INPUT                           OUTPUT

                    10                              2 3 7 29 31 37
                    3 4 7 2 9 31 16 29 37 9                    

Cho một xâu ký tự ~s~. Yêu cầu: Ghi lại, tính độ dài xâu và sắp xếp lại các ký tự trong xâu ~s~.

Ví dụ:

            INPUT                   OUTPUT

            ABEHGCDVIM              ABEHGCDVIM
                                    10
                                    ABCDEGHIMV

Cho xâu ký tự ~s~. Đếm ký tự ~a~ và xóa ký tự này trong xâu ~s~, hiển thị xâu ~s~ sau khi xóa ký tự ~a~.

Ví dụ:

                INPUT                   OUTPUT

                abaebcda                3
                                        bebcd                

Cho xâu ký tự ~s~, các số nguyên dương ~k~ và ~n~.

Yêu cầu:

• Xóa ~n~ ký tự của xâu ~s~ từ vị trí thứ ~k~
• Xóa ~k~ vị trí đầu tiên
• Xóa ~n~ ký tự cuối cùng của xâu ~s~.

Ví dụ:

INPUT                       OUTPUT

sfasecwbdgmxv               sfbdgmxv
2 5                         bdgmxv
                            b

Cho hai xâu ký tự ~s1~ và ~s2~. Xóa tất cả các ký tự của xâu ~s1~ trong xâu ~s2~.

Ví dụ:

            INPUT                   OUTPUT

            ab                      sfscwbdgb
            sfabsabcwbdgbab

Cho xâu ký tự ~s~, thực hiện chuẩn hóa xâu ~s~ bằng cách xóa tất cả các dấu cách thửa, chỉ giữ lại một dấu cách.

Ví dụ:

INPUT                       OUTPUT

Do   Trung   Thanh              Do Trung Thanh

Cho xâu ký tự ~s~. Chuẩn hóa xâu bằng cách:

• Xóa tất cả các ký tự thừa (2 dấu cách trở lên để lại 1 dấu cách)
• Định dạng chữ cái đầu tiên của xâu thành chữ IN HOA.

Ví dụ:

                INPUT                       OUTPUT

                do Trung Thanh              Do Trung Thanh

Cho xâu ký tự ~s~. Chuẩn hóa xâu bằng cách:

• Xóa tất cả các ký tự thừa (2 dấu cách trở lên để lại 1 dấu cách)
• Định dạng toàn bộ xâu ký tự s thành chữ IN HOA.

Ví dụ:

                INPUT                       OUTPUT

                do trung thanh              DO TRUNG THANH

Cho xâu ký tự ~s~. Chuẩn hóa xâu bằng cách:

• Xóa tất cả các ký tự thừa (2 dấu cách trở lên để lại 1 dấu cách)
• Định dạng các ký tự đầu câu thành chữ IN HOA.

Ví dụ:

                INPUT                           OUTPUT

                dO truNg tHanh                  Do Trung Thanh

Cho hai xâu ký tự ~s1~, ~s2~. Hãy đếm số lần xuất hiện của xâu ~s1~ trong xâu ~s2~ đồng thời xóa các xâu ~s1~ có trong ~s2~.

Ví dụ:

INPUT                           OUTPUT

ab                              3
abxytabuvrbabxy                 xytuvrbxy  

Đếm số lần xuất hiện của mỗi ký tự trong xâu ~s~. Sắp xếp các ký tự và số lần xuất hiện theo thứ tự tăng.

Ví dụ:

                    INPUT                       OUTPUT

                    abceacbde                   a 2
                                                b 2
                                                c 2
                                                d 1
                                                e 2

Chuẩn hóa xâu ~s~ nhập vào.

Yêu cầu:

• Xóa tất cả dấu cách thừa
• Thay các ký tự đầu mỗi từ bằng chữ IN HOA
• Tách ra: Họ và tên đệm trên 1 dòng, tên trên một đòng.

Ví dụ:

                        INPUT                       OUTPUT

                        dO truNg tHanh              Do Trung
                                                    Thanh

Tách riêng các số trong xâu.

Ví dụ:

                    INPUT                        OUTPUT

                    dggfdgf15đff24gfhh57uy       15 24 57

Dọc theo một con đường thẳng người ta đã trồng một hàng gồm N cây xanh có khoảng cách đều nhau. Để trang trí cho con đường vào ban đêm, người ta gắn lên hàng cây một số bóng đèn theo quy tắc xen kẻ nhau, cứ hai cây liền kề nhau thì một cây được gắn đèn, một cây không gắn đèn. Biết rằng để gắn một bóng đèn lên một cây cần chi phí với số tiền là X đồng.

Yêu cầu: Hãy tính tổng chi phí để gắn được nhiều bóng đèn nhất cho hàng cây.

Kết quả ra: gồm một dòng ghi hai số nguyên dương ~N~ và ~X~ ~(1 \leq N \leq 10^9, 1 \leq X \leq 10^3)~ cách nhau một dấu cách.

Kết quả: một số nguyên là kết quả tìm được của bài toán.

Ví dụ:

Input                           Output
5 10                            30

Các con bò của nông dân John có sở thích là hay đi khám phá những vùng xung quanh nông trang. Ban đầu, tất cả ~N~ ~(1 \leq N \leq 1,000,000,000)~ con bò tập trung thành 1 nhóm và cùng bắt đầu chuyến đi trên 1 con đường. Cho tới khi gặp một ngã ba đường thì chúng đôi khi chọn cách chia làm 2 nhóm nhỏ hơn ( mỗi nhóm ít nhất 1 bò ) và mỗi nhóm lại tiếp tục hành trình trên con đường của nhóm chúng. Khi một trong những nhóm này gặp 1 ngã ba khác thì nhóm này lại có thể tách ra tiếp, và cứ như vậy.

Các con bò đã hình thành nên 1 quy tắc về việc chia nhóm như sau: nếu chúng có thể chia thành 2 nhóm mà chênh lệch số bò của 2 nhóm là đúng bằng ~K~ ~(1 \leq K \leq 1000)~ thì tại ngã ba đó chúng sẽ chia làm 2; nếu không thì chúng sẽ dừng cuộc hành trình và đứng ở đó nhấm nháp cỏ non.

Giả sử rằng luôn có những ngã ba mới trên các con đường, hãy tính xem cuối cùng có bao nhiêu nhóm bò tất cả.

Dữ liệu: Gồm hai số nguyên cách nhau bởi dấu cách: ~N~ và ~K~

Kết quả: Một số nguyên cho biết số lượng nhóm bò sau cùng.

Ví dụ:

Input                           Output
6 2                             3

Giải thích: Cuối cùng có 3 nhóm bò (1 nhóm có 2 bò, 1 nhóm có 1 và 1 nhóm có 3 ).

Cho số đầu tiên ~u_1~ và công sai ~d~ của cấp số cộng

Yêu cầu: Tính ~u_n~ và ~s_n~

Dữ liệu vào: Gồm ba số nguyên ~u_1, d, n~ cách nhau một khoảng trắng ~(-10^3 \leq d, u_1 \leq 10^3).~

Kết quả: Số nguyên đầu tiên là ~u_n~ và số tiếp theo là ~s_n~ ghi trên một hàng.

Ví dụ:

Input                           Output
-5 3 15                         37 240

Olympic Bóng bầu dục nghiệp dư được tổ chức theo hình thức mở: mọi cá nhân đều có thể đăng kí tham gia. Những người tham gia được chia thành các đội, mỗi đội 11 người.

Năm nay do yêu cầu dãn cách, ban tổ chức quyết định giảm số người mỗi đội xuống còn 7. Trước đó đã có ~k~ đội đăng kí, ~p~ người không hài lòng với quy định mới và đã xin rút nhưng lại có thêm ~q~ người đăng kí.

Hãy xác định ban tổ chức cần tìm thêm ít nhất bao nhiêu người nữa để có thể chia mọi người thành các đội theo thể thức 7 người/đội.

Dữ liệu: Vào từ thiết bị vào chuẩn gồm một dòng chứa 3 số nguyên ~k, p~ và ~q~ ~(1 \leq k \leq 1000, 1 \leq p \leq 11 × k, 1 \leq q \leq 1000).~

Kết quả: Đưa ra thiết bị ra chuẩn số người ít nhất cần tìm thêm.

Ví dụ:

Input                           Output
20 2 1                          5

Mẹ đang dở tay trong bếp và vì vậy đề nghị Alice chạy ra siêu thị mua thêm một mặt hàng, đồng thời qua bưu điện nhận bưu phẩm.

Alice không bao giờ từ chối giúp mẹ, nhưng muốn đi thật nhanh để về lập trình tiếp bài đang làm.

Đường đi từ nhà tới siêu thị có độ dài ~a~, từ nhà tới bưu điện – độ dài ~b~ và từ bưu điện tới siêu thị - độ dài ~c~. Với tay không tốc độ đi của Alice là ~v0~, khi mang hàng mua được hoặc bưu phẩm, Alice đi với tốc độ ~v1~, còn khi mang trên tay cả 2 thứ thì đi với tốc độ ~v~2 ~(v2 \leq v1 \leq v0).~

Để hoàn thành nhiệm vụ được giao Alice có thể đi và mang về nhà cùng lúc cả 2 thứ hoặc lần lượt mang từng thứ một về nhà.

Với thói quen của người lập trình Alice nhẩm tính cách thực hiện nhanh nhất nhiệm vụ được giao.

Hãy xác định thời gian ngắn nhất thực hiện nhiệm vụ.

Dữ liệu: Nhập 6 số thực ~a, b, c, v0, v1, v2 (1 \leq a, b, c \leq 100, 1 \leq v2 \leq v1 \leq v0 \leq 100).~

Kết quả: Đưa ra màn hình một số thực (sai số không quá ~10^4~) xác định thời gian ngắn nhất thực hiện nhiệm vụ.

Ví dụ:

Input                           Output
2 3 4 7 6 5                     1.4952

Tâm tạo ngẫu nhiên một dãy số nguyên làm dữ liệu vào để đánh giá hiệu quả giải thuật của mình. Các số trong dãy được ghi trên một dòng, cách nhau một hoặc nhiều dấu cách. Nhìn vào độ dài của dòng hay số lượng dấu cách không thể biết được dòng chứa bao nhiêu số. Để chuẩn hoá dữ liệu Tâm ghi lại các số thành nhiều dòng, mỗi dòng có đúng ~a~ số. Kết quả là dòng cuối cùng chỉ chứa có một số!

Tâm quyết định sẽ để mỗi dòng chứa đúng ~b~ số. Kết quả có vẻ đẹp hơn nhưng cũng không thật hoàn hảo: Dòng cuối cùng chỉ chứa ~b-1~ số.

Hãy xác định số lượng số có trong dãy được khởi tạo.

Dữ liệu: Vào từ thiết bị vào chuẩn gồm một dòng chứa 2 số nguyên a và b ghi cách nhau một dấu cách, ~(2 \leq a, b \leq 2×10^9).~

Kết quả: Đưa ra thiết bị ra chuẩn số lượng ít nhất các số được khởi tạo.

Lưu ý: Dữ liệu đảm bảo kết quả cần tìm không vượt quá ~2×10^9~.

Ví dụ:

Input                           Output
5 3                             11

Cho một mảng gồm n phần tử ~A[1], A[2], …, A[n]~ Các phần tử là các số nguyên trong nằm trong đoạn ~[0, m]~ với m là số cho trước. ~(1 \leq n \leq 10^5, 1 \leq m \leq 100)~

Đếm số cách thay số 0 có trong mảng bằng các số nằm trong đoạn ~[1, m]~ sao cho chênh lệch tuyệt đối giữa hai giá trị liền kề nhiều nhất là 1.

Dữ liệu:

• Dòng đầu vào đầu tiên có hai số nguyên ~n~ và ~m~: kích thước mảng và giới hạn trên cho mỗi giá trị.
• Dòng tiếp theo có ~n~ số nguyên ~A[1], A[2], …, A[n]~.

Kết quả: In một số nguyên: số lượng dãy chia lấy dư cho ~10^9 + 7.~

Ví dụ:

Input                           Output
3 5                             3
2 0 2

Giải thích: Các dãy ~[2,1,2]~, ~[2,2,2]~, ~[2,3,2]~ thoả mãn yêu cầu.

Ràng buộc:

• 50% số test tương ứng với 50% số điểm chỉ có 1 số có giá trị bằng 0 trong dãy ~A~.
• 50% số test tương ứng với 50% số điểm không có ràng buộc gì thêm.

Sau một ngày làm việc vất vả, Phát sẽ thưởng cho mình bằng những bữa ăn với những trái ớt ngon lành.

Anh ta có n trái ớt được nối với nhau qua n-1 cành, hai trái ớt bất kì luôn được nối với nhau qua chuỗi những cành. Tóm lại, những trái ớt đó tạo thành cây.

Phát sẽ có ba bữa ăn trong ngày. Để chuẩn bị cho bữa ăn, anh ta sẽ cắt 2 cành cây bất kì để có được 3 đùm ớt, mỗi đùm cho mỗi bữa.

Tuy nhiên Phat không muốn bất kì bữa ăn nào too spicy, nên anh ấy quyết định cắt sao cho độ chênh lệch giữa đùm có nhiều ớt nhất và ít nhất là nhỏ nhất. Bạn phải giúp anh ấy tìm độ chênh lệch đó.

Input:

• Dòng đầu chứa số nguyên n là số lượng ớt. Các trái ớt được đánh số từ ~1 → n~.
• Mỗi dòng trong ~n-1~ dòng còn lại gồm 2 số nguyên x và y ~( 1 \leq x,y \leq n )~ số hiệu 2 trái ớt nối trực tiếp với nhau.

Output: In ra độ chênh lệch tối thiểu giữa đùm có nhiều ớt nhất và ít ớt nhất.

Ví dụ:

Input                           Output
4                               1
1 2 
2 3 
3 4 

----------

6                               0
1 2 
1 3 
3 4 
3 5 
5 6

----------

9                               2
1 3 
2 3
3 4 
3 5 
5 6 
5 7 
7 8 
7 9 

Giải thích:

• Ở ví dụ thứ nhất có 3 cách cắt để tạo thành 1 đùm có 2 trái ớt và 2 đùm có 1 trái ớt. Do đó độ chêch lệch là 2 – 1 = 1.
• Ở ví dụ thứ ba, số lượng trái ớt trong các đùm lần lượt là 4 2 3 nên kết quả là 4 – 2 = 2.

Subtask:

• Subtask 1: (25% số điểm) ~3 \leq n \leq 200~.
• Subtask 2: (50% số điểm) ~3 \leq n \leq 2000~.
• Subtask 3: (100% số điểm) ~3 \leq n \leq 200000~.

Cho dãy số ~𝐴~ có ~n~ số nguyên ~a_1, a_2, ...,a_n~. Một dãy con liên tiếp các số hạng của dãy ~A~ là dãy các số hạng từ số hạng ~a_i~ đến số hạng ~a_j~ ~(1 \leq i \leq j \leq n)~. Hãy cho biết dãy ~A~ có bao nhiêu dãy con liên tiếp mà giá trị tuyệt đối của tổng các số hạng trong dãy con đó lớn hơn một số nguyên dương ~S~ cho trước.

Dữ liệu:

• Dòng thứ nhất chứa hai số nguyên dương ~n~ và ~S~ ~(n \leq 10^5,S \leq 10^14)~.
• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2,.., a_n~ ~(|a_i| \leq 10^9)~.

Kết quả: Một số nguyên duy nhất là số dãy con liên tiếp thỏa mãn yêu cầu của bài toán.

Ví dụ:

Input                           Output
4 4                             6
5 -1 8 -5 

----------

10 7                            12
-4 9 2 -11 -3 8 -6 5 -3 1

Giải thích: Trong ví dụ đầu tiên có 6 dãy con thỏa mãn yêu cầu là: ~{5}~, ~{8}~, ~{-5}~, ~{-1;8}~, ~{5;-1;8}~ và ~{5;-1;8;5}~.

Ràng buộc:

• Có 50% số test ứng với 50% số điểm của bài có ~n \leq 10^0~.
• Có 30% test khác ứng với 30% số điểm của bài có ~n \leq 10^3~.
• Có 20% test còn lại ứng với 20% số điểm của bài có ~n \leq 10^5~.