Bnumber

Nộp bài
Time limit: 1.0 / Memory limit: 256M

Point: 100

Số đẹp được định nghĩa là một số nguyên dương và chia hết cho một trong hai số: 3 hoặc 5.

Ví dụ về dãy các số đẹp: 3,5,6,9,10,12,15,18,20,...

Hãy tìm số đẹp thứ k.

Input

  • Gồm một dòng chứa số nguyên dương k.

Output

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

Giới hạn:

  • Subtask 1 (50% số điểm): k106
  • Subtask 2 (50% số điểm): k1012

Sample Input 1

Copy
2

Sample Output 1

Copy
5

Sample Input 2

Copy
10

Sample Output 2

Copy
21

BSCOUNTK

Nộp bài
Time limit: 2.0 / Memory limit: 256M

Point: 100

Cho một dãy a gồm n phần tử và số nguyên dương k, hãy đếm số cặp (i,j) thỏa mãn i<jai+ajk.

Input

  • Dòng đầu chứa 2 số nguyên dương nk.
  • Dòng thứ hai gồm n phần tử nguyên dương miêu tả dãy a. (1ai106)

Output

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

Giới hạn:

  • Subtask 1 (50% số điểm): n5000
  • Subtask 2 (50% số điểm): n105

Sample Input 1

Copy
4 6
1 3 5 6

Sample Output 1

Copy
2

Sample Input 2

Copy
6 8
1 2 5 3 4 8

Sample Output 2

Copy
9

Time limit: 2.0 / Memory limit: 256M

Point: 100

Cho 2 mảng ab đều gồm n số nguyên dương và một số nguyên dương k. Mảng số nguyên c gồm n2 phần tử được xây dựng bằng cách với mỗi cặp i,j thỏa mãn 1i,jn, ta gán giá trị c(i1)n+j=ai+bj.

Sắp xếp mảng c lại theo thứ tự không giảm, hãy in ra số thứ k trong dãy c mới.

Input

  • Dòng đầu gồm 2 số nguyên dương nk.
  • Dòng tiếp theo gồm n số nguyên dương mô tả dãy a.
  • Dòng cuối cùng gồm n số nguyên dương mô tả dãy b.

Output

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

Constraints

  • 1n105, 1kn2.
  • 1ai,bi109.

Subtask

  • 50% số điểm có n1000.
  • 50% còn lại không có giới hạn gì thêm.

Sample Input 1

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

Sample Output 1

Copy
9

INCLRX_1

Nộp bài
Time limit: 1.0 / Memory limit: 512M

Point: 100


Time limit: 1.0 / Memory limit: 256M

Point: 100

Cho một xâu s có độ dài n chỉ bao gồm các kí tự a,b,c. Một đoạn [l,r] được gọi là tốt khi và chỉ khi có một kí tự trong đoạn có số lần xuất hiện lớn hơn một nửa độ dài đoạn. Nói cách khác, gọi cnt(d,l,r) là số lần xuất hiện của kí tự d trong đoạn [l,r], ta cần tồn tại một kí tự d trong đoạn [l,r] sao cho cnt(d,l,r)>(rl+1)/2. (Với d thuộc [a,b,c])

Hãy in ra độ dài đoạn tốt lớn nhất.

Input

  • Dòng đầu gồm số nguyên dương n miêu tả độ dài xâu. (1n105)
  • Dòng thứ hai miêu tả xâu s. Xâu s chỉ bao gồm các kí tự a,b,c và có độ dài n.
  • Ouput

  • In ra độ dài đoạn tốt lớn nhất.

Sample Test

Input

Copy
7
aabbbcc

Output

Copy
5

Giải thích: Chọn đoạn [1,5].


Điểm chung

Nộp bài
Time limit: 1.0 / Memory limit: 1G

Point: 100

Trên trục số Ox, cho 𝑁 đoạn thẳng, mỗi đoạn thẳng được xác định bởi hai điểm đầu và cuối là hai số nguyên. Một điểm 𝑀 được gọi là nằm trong đoạn thẳng 𝐴𝐵 nếu 𝐴𝑀𝐵.

Yêu cầu: Đếm xem có bao nhiêu điểm có toạ độ nguyên nằm trong đúng 𝐾 đoạn thẳng.

Dữ liệu nhập vào từ file văn bản DC.INP:

  • Dòng đầu tiên gồm hai số nguyên 𝑁𝐾 (1𝐾𝑁105);
  • 𝑁 dòng sau, mỗi dòng gồm hai số nguyên 𝑎,𝑏 mô tả hai điểm đầu và cuối của đoạn thẳng (1𝑎𝑏1018).

Kết quả ghi ra file văn bản DC.OUT:

Một số nguyên duy nhất là số lượng điểm có toạ độ nguyên nằm trong đúng 𝐾 đoạn thẳng.

Ràng buộc

  • 50% số test ứng với 50% số điểm của bài thoả mãn: 𝑎,𝑏103;
  • 30% số test khác ứng với 30% số điểm của bài thoả mãn: 𝐾=𝑁;
  • 20% số test còn lại ứng với 20% số điểm của bài không có ràng buộc gì thêm.

Ví dụ

Input
Copy
3 2
1 5
2 8
3 7
Output
Copy
3

Giải thích: Toạ độ của 3 điểm nằm trong đúng 2 đoạn thẳng là: 2,6,7.

  • Điểm có toạ độ 2 nằm trong 2 đoạn thẳng: đầu tiên và thứ hai.
  • Điểm có toạ độ 6,7 nằm trong 2 đoạn thẳng: thứ hai và thứ ba.
Input
Copy
3 1
1 5
2 8
3 7
Output
Copy
2   

Giải thích: Toạ độ của 2 điểm nằm trong đúng 1 đoạn thẳng là: 1,8.

  • Điểm có toạ độ 1 chỉ nằm trong đoạn thẳng đầu tiên.
  • Điểm có toạ độ 8 chỉ nằm trong đoạn thẳng thứ ba.
Input
Copy
3 3
1 5
2 8
3 7
Output
Copy
3

Giải thích: Toạ độ của 3 điểm nằm trong cả 3 đoạn thẳng là: 3,4,5.


Số Ước

Nộp bài
Time limit: 1.0 / Memory limit: 512M

Point: 100


Tổng Ước

Nộp bài
Time limit: 1.0 / Memory limit: 512M

Point: 100


Tổng tích ước

Nộp bài
Time limit: 1.5 / Memory limit: 512M

Point: 100


Time limit: 1.0 / Memory limit: 256M

Point: 100

Cho dãy số gồm n số nguyên a1,a2,,an2 số nguyên không âm L,R(LR).

Yêu cầu: Đếm số cặp (i,j) thỏa mãn điều kiện: ijL|ai++aj|R.

Input

  • Dòng đầu tiên chứa 3 số nguyên n,L,R (n3105;0LR109)
  • Dòng thứ hai chứa n số nguyên a1,a2,,an(|ai|109)

Output

  • Một số nguyên duy nhất là số lượng cặp (i,j) đếm được.

Subtask

  • Subtask 1 (30% số điểm): n103.
  • Subtask 2 (50% số điểm): n105ai0.
  • Subtask 3 (20% số điểm): Không có giới hạn gì thêm.

Sample Test

Input

Copy
3 0 1
1 -1 2

Output

Copy
4

Mảng cộng dồn - Cơ bản

Nộp bài
Time limit: 1.0 / Memory limit: 256M

Point: 100

Cho một dãy số nguyên a gồm n (1n105,1ai106) phần tử và q (1q105) truy vấn. Mỗi truy vấn có dạng l,r, hãy in ra tổng al,al+1,..,ar.

Input

Copy
5 4
1 2 3 4 5
1 2
2 3 
1 5
3 4

Output

Copy
3
5
15
7

Xâu Đầy Đủ

Nộp bài
Time limit: 1.0 / Memory limit: 256M

Point: 100

Bạn được nhận n xâu kí tự, mỗi xâu gồm các chữ cái tiếng Anh in thường. Cần chọn ra một số xâu trong n xâu đó sao cho khi ghép tất cả chúng lại, ta được một xâu mới bao gồm đầy đủ các kí tự trong bảng chữ cái tiếng Anh. Hãy đếm số cách để thực hiện yêu cầu trên. Hai cách được coi là khác nhau khi có một xâu được chọn ở cách này không được chọn trong cách kia.

Input

  • Dòng đầu tiên gồm số nguyên dương n (n25) miêu tả số lượng xâu.
  • n dòng tiếp theo, mỗi dòng bao gồm một xâu kí tự S (|S|30) gồm các chữ cái tiếng Anh in thường.

Output

  • In ra một số nguyên là kết quả bài toán.

Sample Test

Input1:

Copy
8
the
quick
brown
fox
jumps
over
lazy
dog

Output1:

Copy
1

Input2:

Copy
3
a
b
abcdefghijklmnopqrstuvwxyz

Output2:

Copy
4

Turtle Graph

Nộp bài
Time limit: 1.0 / Memory limit: 256M

Point: 100

Mrtee đang lặn lội trên con đường tìm ma pháp sư Marisa thì có một con Rùa và một con Thỏ cãi nhau xem ai nhanh hơn. Chúng quyết định giải quyết việc tranh luận bằng một cuộc thi chạy đua. Chúng đồng ý lộ trình và bắt đầu cuộc đua.

Thỏ xuất phát nhanh như tên bắn và chạy thục mạng rất nhanh, khi thấy rằng mình đã khá xa Rùa, Thỏ nghĩ nên nghỉ cho đỡ mệt dưới một bóng cây xum xê lá bên vệ đường và nghỉ thư giãn trước khi tiếp tục cuộc đua.

Vì quá tự tin vào khả năng của mình, Thỏ ngồi dưới bóng cây và nhanh chóng ngủ thiếp đi trên đường đua. Rùa từ từ vượt qua Thỏ và sớm kết thúc đường đua.

Khi Thỏ thức dậy thì rùa đã đến đích và trở thành người chiến thắng. Thỏ giật mình tỉnh giấc và nhận ra rằng nó đã bị thua.

Không thể chấp nhận sự thật, Thỏ quyết định tái đấu. Lần này, thay vì dùng một trò thiên về sức lực, Thỏ quyết định thách đấu bằng cách đố Rùa một câu hỏi đầy hóc búa.


Cho đồ thị vô hướng gồm n đỉnh và m cạnh, không có khuyên và cạnh lặp.

Để tạo ra được một đồ thị có độ đẹp, ta cần điền các số nguyên dương c trên mỗi đỉnh (c chỉ có thể là 1, 2, hoặc 3), sao cho với mỗi cạnh, tổng của hai số được điền trên 2 đỉnh được kết nối bởi cạnh đó là một số lẻ.

Thỏ đố Rùa có thể đếm số cách để điền các số 1,2,3 lên mỗi đỉnh sao cho tạo ra được một đồ thị đẹp. Do con số này có thể rất lớn, hãy in nó ra theo modulo 998244353.

Lưu ý: Rùa phải điền đúng một số trên mỗi đỉnh.

Để cho câu đố thêm phần học búa, Thỏ sẽ hỏi q câu có dạng như vậy.

Rùa dù là một sinh vật cute nhưng không giỏi đồ thị cho lắm, hãy giúp Rùa hoàn thành bài toán này nhé!

Input

  • Dòng đầu tiên gồm số nguyên dương q miêu tả số câu hỏi.
  • Đối với mỗi câu hỏi:
    • Dòng đầu tiên 2 số nguyên dương n,m miêu tả số đỉnh và cạnh của đồ thị.
    • m dòng tiếp theo, mỗi dòng gồm 2 số nguyên dương ui,vi (1ui,vin,uivi) miêu tả cạnh thứ i.

Output

  • Với mỗi câu hỏi, in ra một dòng là số nguyên duy nhất là số cách điền thỏa mãn sau khi lấy phần dư cho 998244353.

Điều kiện

  • 1q3×105.
  • 1n,m3×105.
  • Dữ liệu đảo bảo rằng tổng n trong tất cả các câu hỏi không vượt quá 3×105, tương tự với tổng m.

Subtask

  • 50% số điểm: n10,q10.
  • 30% số điểm: Trong mọi câu hỏi, đồ thị có dạng cây.
  • 20% số điểm: Không có ràng buộc gì thêm.

Ví dụ

Input:

Copy
2
7 7 
1 2
2 3
3 4
4 5
5 6
6 7
7 1
2 1
2 1

Output:

Copy
0
4

Giải thích:

Ở câu hỏi đầu tiên, không có cách điền nào thỏa mãn.

Ở câu hỏi thứ hai, có 4 cách điền như sau:

  • Điền số 1 vào đỉnh 1, số 2 vào đỉnh 2.
  • Điền số 3 vào đỉnh 1, số 2 vào đỉnh 2.
  • Điền số 2 vào đỉnh 1, số 1 vào đỉnh 2.
  • Điền số 2 vào đỉnh 1, số 3 vào đỉnh 2.

Time limit: 1.0 / Memory limit: 256M

Point: 100

Cho dãy số gồm n số nguyên c1,c2,,cn và số nguyên dương m. Nhiệm vụ của bạn là tìm một đoạn b1,b2,...,bk (1b1<b2<...<bkn) sao cho (cbi)%m là lớn nhất có thể. Đoạn con tìm được có thể rỗng.

Yêu cầu: Hãy in ra giá trị lớn nhất tìm được.

Input

  • Dòng đầu tiên chứa 2 số nguyên duyên n,m
  • Dòng thứ hai chứa dãy c gồm n phần tử.

Output

  • Một số nguyên duy nhất là giá trị lớn nhất tìm được.

Constraints

  • 1n40
  • 1m109
  • 1ci109

Subtask

  • 50% số test ứng với n20.
  • 50% số test ứng với n40.

Sample Input 1

Copy
4 4
5 2 4 1

Sample Output 1

Copy
3

Sample Input 2

Copy
3 20
199 41 299

Sample Output 2

Copy
19

Time limit: 1.0 / Memory limit: 256M

Point: 100

Cho một dãy a gồm n phần tử nguyên dương và hai giá trị nguyên dương k, x.

Ta có hàm cnt(l,r) là số các giá trị val xuất hiện nhiều hơn hoặc bằng x lần trong các phần tử thuộc đoạn [l,r] của dãy a.

Hãy tìm một đoạn con có độ dài bằng k sao cho cnt(l,r) của nó là lớn nhất.

Input

  • Dòng thứ nhất chứa 3 số nguyên dương n,k,x.
  • Dòng thứ hai gồm n số nguyên dương miêu tả dãy a.

Output

  • In ra giá trị của cnt(l,r) lớn nhất với rl+1=k.

Constraints

  • 1xkn2105.
  • 1ai2105.

Subtasks

  • Subtask 1: n1000 (50%)
  • Subtask 2: Không có ràng buộc gì thêm (50%)

Sample Input 1:

Copy
6 4 2
1 2 2 1 3 4

Sample Output 1:

Copy
2

Explanation 1:

Chọn đoạn [1,4].

Sample Input 2:

Copy
7 5 3
1 1 2 2 1 1 2 3

Sample Output 2:

Copy
1

Explanation 2:

Chọn đoạn [1,5].


Time limit: 1.0 / Memory limit: 256M

Point: 100

Cho t truy vấn và giá trị mod (1mod2109), mỗi truy vấn gồm hai số nguyên dương n, k. Kí hiệu C(k,n) là tổ hợp chập k của n, hãy in ra C(k,n) cho mỗi truy vấn tương ứng. Do kết quả có thể rất lớn nên hãy in nó sau khi lấy phần dư cho mod.

Subtask

  • Sub 1: t105, 1kn2000. (30%)
  • Sub 2: t=1, 1kn105. (30%)
  • Sub 3: t105, 1kn105, mod=109+7. (40%)

Input

  • Dòng đầu tiên gồm một số nguyên dương sub miêu tả subtask mà test này tương ứng. (1sub3)
  • Dòng thứ hai gồm hai số nguyên dương tmod.
  • t dòng sau, mỗi dòng gồm hai số nguyên dương n, k (kn) miêu tả truy vấn tương ứng.

Output

  • In ra t dòng, mỗi dòng là kết quả của truy vấn tương ứng.

Sample Test

Input:

Copy
1
3 2345
6 4
8 4
15 8

Output:

Copy
15
70
1745

Time limit: 1.0 / Memory limit: 256M

Point: 100

Cây - được định nghĩa là một đồ thị vô hướng liên thông gồm n đỉnh và không có chu trình. Cho một đồ thị vô hướng gồm n đỉnh và m cạnh, nếu đó là một cây thì in ra "Yes", ngược lại in ra "No".

Input:

  • Dòng đầu gồm 2 số nm. (2n,m1e5).
  • m dòng sau, mỗi dòng gồm 2 số u,v(1u,vn) chỉ ra tồn tại một cạnh vô hướng giữa 2 đỉnh này.

Output:

  • Nếu đồ thị đã cho là một cây, in ra "Yes", ngược lại in ra "No".

Sample Test 1

Input:

Copy
3 2
1 2
2 3

Output:

Copy
Yes

Sample Test 2

Input:

Copy
3 3 
1 2 
2 3 
3 1

Output:

Copy
No

Cây mèo

Nộp bài
Time limit: 1.0 / Memory limit: 256M

Point: 100

Cho một cây vô hướng gồm n đỉnh, có gốc là đỉnh 1. Đỉnh i gồm một số a[i], nếu a[i]=1, nghĩa là có một chú mèo ở đỉnh i, còn ngược lại thì không. Thinkies đang ở đỉnh 1, cậu chỉ có thể đi tới các đỉnh khác khi và chỉ khi từ đỉnh 1 tới đỉnh đó có số mèo trên các đỉnh liên tiếp nhỏ hơn hoặc bằng m. Hãy đếm số đỉnh lá (các đỉnh không có đỉnh con) mà Thinkies có thể đi vào.

Input:

Dòng đầu gồm 2 số nguyên nm (1mn105).

Dòng sau gồm n số biểu thị dãy a.

n1 dòng kế tiếp, mỗi dòng gồm 2 số uv, biểu thị có cạnh giữa 2 đỉnh uv.

Output:

In ra số lá mà Thinkies có thể đi vào

Mẫu:

Input:

Copy
4 1
1 1 0 0
1 2
1 3
1 4

Output:

Copy
2

Cây chẵn

Nộp bài
Time limit: 1.0 / Memory limit: 256M

Point: 100

Cho một cây có n đỉnh, hãy xác định số lượng cạnh lớn nhất có thể xóa bỏ để toàn bộ các vùng liên thông còn lại có kích thước chẵn.

Input

  • Dòng đầu tiên chứa số nguyên dương n105.
  • n1 dòng tiếp theo chứa 2 số u,v(u,vn) là các cạnh của cây.

Output

  • In ra một số nguyên số cạnh có thể xóa
  • Nếu không thể có cách cắt thỏa mãn, in ra -1.

    Sample Test 1

Input:

Copy
4
2 4
4 1
3 1

Output:

Copy
1

Sample Test 2

Input:

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

Output:

Copy
4

Cây tiền thưởng

Nộp bài
Time limit: 1.0 / Memory limit: 256M

Point: 100

Bạn vừa được HCV IOI nên thầy Tùng quyết định thưởng cho bạn. Thầy cho bạn một cây có n đỉnh. Với mỗi đỉnh i cho 2 số liri. Việc bạn cần làm là chọn một số vi ở mỗi đỉnh sao cho liviri và số tiền được thưởng (tính bằng triệu VND) sẽ là tổng của |vivj| với toàn bộ các cạnh (i,j) vô hướng của cây. Hãy in ra số tiền nhiều nhất bạn có thể được thầy thưởng.

Input

  • Dòng đầu tiên là số nguyên dương n105 là số đỉnh của cây.
  • n dòng tiếp theo mỗi dòng i gồm 2 số liri109 là chỉ số của đỉnh thứ i.
  • n1 dòng tiếp theo mỗi dòng là 2 số u,v là cạnh của cây.

Output

  • In ra một số là số tiền lớn nhất bạn có thể được thưởng.

Subtasks

  • Subtask 1: n20.
  • Subtask 2: Với mỗi i<n, tồn tại một cạnh i với i+1.
  • Subtask 3: Không có điều kiện gì thêm.

Sample Test

Input:

Copy
3
1 3
4 6
7 9
1 2
2 3

Output:

Copy
8

Đỉnh tốt

Nộp bài
Time limit: 1.0 / Memory limit: 256M

Point: 100

Cho một cây vô hướng gồm n đỉnh (1n1e5)m đỉnh đặc biệt (1mn), kèm một số k nguyên dương bất kì (1kn). Một đỉnh u được gọi là tốt nếu như với mọi đỉnh v thuộc tập m đỉnh đặc biệt, ta luôn có dist(u,v)k. Ở đây, dist(u,v) là khoảng cách của đỉnh uv trên cây, hay bằng số cạnh trên đường đi ngắn nhất từ đỉnh u tới đỉnh v. Hãy đếm xem có bao nhiêu đỉnh được coi là "tốt".

Input:

  • Dòng đầu gồm 3 số n,m,k.(1mn105,1k105).
  • n1 dòng sau mỗi dòng gồm 2 số u,v(1u,vn) là cạnh nối từ đỉnh u tới v.
  • Dòng cuối gồm m số miêu tả các đỉnh đặc biệt.

Output:

  • Số đỉnh tốt.

Sample Test

Input:

Copy
6 2 3 
1 5 
2 3 
3 4 
4 5 
5 6
1 2

Output:

Copy
3
Giải thích:
  • 3 đỉnh tốt là đỉnh 3,4,5.

Ràng buộc

  • Subtask 1: n<=500. (50%)
  • Subtask 2: Với mỗi thành phố, chỉ có tối đa 2 con đường nối tới các thành phố khác.
  • Subtask 3: Không giới hạn gì thêm. (20%).

Dọn tuyết

Nộp bài
Time limit: 3.0 / Memory limit: 256M

Point: 100

Alice Margatroid cần dọn tuyết trên mái nhà. Cô sẽ dùng chọn ra m con búp bê của mình để thực hiện nhiệm vụ. Alice có n thùng đựng búp bê, thùng thứ iai con, và cô muốn mỗi thùng chỉ được chọn ra tối đa 1 con búp bê. Hỏi có bao nhiêu cách để chọn ra m con búp bê.

Input

  • Dòng đầu tiên gồm 2 số tự nhiên n,m (1mn1000)
  • Dòng tiếp theo gồm n số tự nhiên là số lượng búp bê của từng thùng. (1a[i]109)

Output

  • Gồm 1 số tự nhiên duy nhất là số cách chọn búp bê modulo 109+7

Sample Test

Input:

Copy
3 2
1 2 1

Output:

Copy
5
Giải thích:
  • Có 5 cách chọn là: {1,2.1},{1,2.2},{1,3},{2.1,3},{2.2,3} với x.y là con búp bê thứ y của thùng thứ x

Time limit: 1.0 / Memory limit: 256M

Point: 100

Cho dãy số gồm n (n105) phần tử nguyên dương a1,a2,...,an (ai106) và một số nguyên dương k cho trước (k109)

Tìm dãy con liên tiếp dài nhất có tổng đúng bằng k

Input

  • Dòng đầu nhập số nguyên dương nk.
  • Dòng thứ 2 nhập n số nguyên a1,a2,...,an.

Output

  • In ra kết quả là độ dài dãy con thỏa mãn yêu cầu

Sample test

Input

Copy
7 7 
4 3 2 1 1 1 6

Output

Copy
4

Đếm Đoạn

Nộp bài
Time limit: 2.0 / Memory limit: 256M

Point: 100

Cho số nguyên dương N. Đếm xem có bao nhiêu cặp số nguyên [a,b] (0<ab) để tổng các số nguyên trong đoạn [a,b] bằng N. Hai đoạn khác nhau là hai đoạn có ít nhất một phần tử khác nhau.

Input

  • Gồm một dòng duy nhất chứa số nguyên dương N.

Output

  • Gồm một dòng duy nhất là kết quả bài toán.

Subtask

  • Subtask 1 (40% số điểm): n104
  • Subtask 2 (30% số điểm): n108
  • Subtask 3 (30% số điểm): n1015

Sample Input 1

Copy
9

Sample Output 1

Copy
3

Explanation 1

3 đoạn thỏa mãn là : [2,4], [4,5], [9,9].


Time limit: 1.0 / Memory limit: 256M

Point: 100

Cho dãy a nguyên dương gồm n phần tử. Ta định nghĩa hàm f(l,r) như sau: f(l,r)=1×a[l]+2×a[l+1]+3×a[l+2]+...(rl+1)×a[r].

q truy vấn, mỗi truy vấn gồm hai số l, r với 1lrn. Với mỗi truy vấn, hãy in ra f(l,r).

Input

  • Dòng đầu gồm 2 số nguyên dương nq. (1n,q105)
  • Dòng thứ hai gồm n số nguyên dương miêu tả dãy a. (1a[i]105).
  • q dòng tiếp theo, mỗi dòng gồm 2 số nguyên dương l, r miêu tả các truy vấn.

Ouput

  • In ra q dòng, mỗi dòng là kết quả của một truy vấn tương ứng.

Subtask

  • Subtask 1: n,q2×103 (30%)
  • Subtask 2: Trong tất cả các truy vấn, l=1.
  • Subtask 3: Không giới hạn gì thêm (40%).

Sample Test

Input

Copy
4 3
1 2 3 4
1 2
2 3
1 4 

Output

Copy
5
8
30

Tích 3 số

Nộp bài
Time limit: 1.0 / Memory limit: 256M

Point: 100

Cho số tự nhiên n, hãy đếm bộ 3 số nguyên dương (a,b,c) sao cho a×b×cn. Lưu ý (a,b,c) khác với (a,c,b) và tương tự.

Input

  • Gồm số tự nhiên n109.

Output

  • Số bộ số thỏa mãn.

Sample Test

Input:

Copy
3

Output:

Copy
7

Time limit: 3.0 / Memory limit: 256M

Point: 100

Cho đồ thị vô hướng không có trọng số gồm n đỉnh và m cạnh. Hãy đếm số thành phần liên thông của đồ thị đã cho.

Input

  • Dòng đầu tiên chứa hai số nguyên dương n,m.
  • m dòng sau, mỗi dòng gồm 2 số nguyên dương uv miêu tả cạnh (u,v).

Output

  • In ra số thành phần liên thông của đồ thị.

Điều kiện

  • 1n,m105.

Ví dụ

Input 1:

Copy
4 3
1 2
2 3
3 4

Output 1:

Copy
1

Input 2:

Copy
5 5
1 2
2 3
3 1
4 5
5 4

Output 2:

Copy
2

MinPath

Nộp bài
Time limit: 1.0 / Memory limit: 256M

Point: 100

Đất nước ABC gồm n thành phố, có m con đường hai chiều với độ dài là 1 nối giữa một cặp thành phố. Có k khách du lịch, vị khách thứ i đang ở thành phố ai. Hiện đang có một sự kiện xảy ra ở thành phố b, với mỗi khách du lịch, hãy in ra con đường ngắn nhất mà người đó phải đi để tới sự kiện này.

Input

  • Dòng đầu tiên chứa hai số nguyên dương n,m,k.
  • m dòng sau, mỗi dòng gồm 2 số nguyên dương uv miêu tả con đường (u,v).
  • Dòng tiếp theo gồm k số nguyên dương miêu tả thành phố mà vị khách thứ i đang ở.
  • Dòng cuối cùng chứa số nguyên dương b - thành phố nơi diễn ra sự kiện.

Output

  • Với mỗi vị khách, in ra con đường ngắn nhất mà người đó phải đi để tới sự kiện.

Điều kiện

  • 1n,m,k2105.

Subtask

  • 50% số điểm: n,m,k1000.
  • 50% số điểm: Không giới hạn gì thêm.

Ví dụ

Input 1:

Copy
4 3 3
1 2 
2 3
3 4
1 2 3
4

Output 1:

Copy
3 2 1

Input 2:

Copy
5 4 3
1 2
2 3
3 1
4 5
1 2 5
3

Output 2:

Copy
1 1 -1

Time limit: 1.0 / Memory limit: 256M

Point: 100

Vùng đất Midland đang có chiến tranh tàn khốc. Bạn đang ở vùng giao tranh, và giờ phải gửi tài liệu mật từ đơn vì tới cho sở chỉ huy. Vùng này được biểu diễn dưới dạng một ma trận n×m, ô ở hàng i cột j được gọi là ô (i,j).

Đây là tài liệu mật và khẩn cấp, vậy nên bạn được lệnh phải tìm một đường đi ngắn nhất từ đơn vị tới sở chỉ huy. Biết rằng bạn có thể đi sang 4 ô kề cạnh với ô đang đứng và mỗi ô (i,j) sẽ được miêu tả bằng một kí tự như sau:

  • c(i,j)=., nếu đây là một ô bình thường có thể đi.
  • c(i,j)=, đây là vùng nguy hiểm tuyệt đối không được đi vào.
  • c(i,j)=S, đây là đơn vị của bạn, sẽ chỉ có duy nhất một ô thế này xuất hiện.
  • c(i,j)=T, đây là sở chỉ huy, sẽ chỉ có duy nhất một ô thế này xuất hiện.

Input

  • Dòng đầu tiên gồm 2 số nguyên n,m, miêu tả kích thước bảng.
  • n dòng sau, mỗi dòng gồm m kí tự miêu tả vùng đất.

Output

  • In ra một dòng là đường đi ngắn nhất từ đơn vị tới sở chỉ huy. Nếu không có một đường đi nào như vậy, in ra 1.

Điều kiện

  • 1n,m1000

Ví dụ

Input 1:

Copy
3 4 
S...
....
...T

Output 1:

Copy
5

Input 2:

Copy
3 4 
S.*T
*.*.
*...

Output 2:

Copy
7

Biocoloring

Nộp bài
Time limit: 1.0 / Memory limit: 256M

Point: 100

Năm 1976, "Định lý bản đồ bốn màu" đã được chứng minh với sự hỗ trợ của máy tính. Định lý này cho rằng mọi bản đồ có thể được tô màu chỉ bằng bốn màu, theo cách mà không có vùng nào được tô màu sử dụng cùng màu với vùng lân cận.

Tuy nhiên, ở đây bạn được yêu cầu giải một bài toán tương tự nhưng đơn giản hơn. Bạn cần kiểm tra xem một đồ thị được cho có thể được "tô màu" hay không. Một đồ thị có thể coi là được "tô màu", nếu ta có thể gán một màu (chỉ sử dụng đúng hai màu) cho các nút sao cho không có hai nút liền kề nào có cùng màu.

Đồ thị được cho có một vài điều kiện như sau:

  • Không có khuyên.
  • Đồ thị vô hướng.
  • Đồ thị liên thông.

Input

  • Dòng thứ nhất gồm số nguyên dương t miêu tả số test case.
  • Đối với mỗi test case:
    • Dòng thứ nhất chứa số nguyên dương n miêu tả đỉnh của đồ thị. Lưu ý, các đỉnh trong đồ thị được đánh dấu từ 0 tới n1.
    • Dòng thứ hai gồm số nguyên dương m miêu tả số cạnh của đồ thị.
    • m dòng tiếp theo, mỗi dòng gồm hai số nguyên dương u,v miêu tả cạnh (u,v).

Output

  • Với mỗi test case, in ra "BICOLORABLE." nếu có thể "tô màu" đồ thị, ngược lại in ra "NOT BICOLORABLE.".

Constraints

  • 1t20
  • 1n,m200

Sample Input 1:

Copy
3

3
3
0 1
1 2
2 0

3
2
0 1
1 2

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

Sample Output 1:

Copy
NOT BICOLORABLE.
BICOLORABLE.
BICOLORABLE.

ThreeMove

Nộp bài
Time limit: 1.0 / Memory limit: 256M

Point: 100

Cho một đồ thị có hướng không trọng số gồm n đỉnh và m cạnh. Bạn đang đứng ở đỉnh S của đồ thị và mục tiêu của bạn là đến được đỉnh T. Tuy nhiên, khác với bình thường, mỗi bước đi của bạn chỉ có thể đi qua đúng 3 cạnh nối tiếp nhau bắt đầu từ đỉnh đang đứng. Ví dụ, có bốn cạnh (1,2),(2,3),(3,4),(3,5), khi đứng ở đỉnh 1 thì trong một bước bạn chỉ được đi tới đỉnh 4 hoặc 5.

Cho đỉnh ST hãy tìm số bước đi ngắn nhất để từ đỉnh S tới được T.

Input

  • Dòng đầu tiên gồm 2 số nguyên n,m, miêu tả số đỉnh và số cạnh.
  • m dòng sau, mỗi dòng gồm 2 số nguyên dương u,v miêu tả cạnh một chiều u,v.
  • Dòng cuối gồm 2 số nguyên dương ST miêu tả đỉnh xuất phát và đỉnh đích.

Output

  • In ra một số là số bước ít nhất để đi từ S tới T, nếu không có cách đi nào thì in ra 1.

Điều kiện

  • 1n,m2105

Ví dụ

Input 1:

Copy
5 5 
1 2
2 3
3 4
4 5
5 4
1 5

Output 1:

Copy
2

Input 2:

Copy
5 4
1 2
2 3
3 4
4 5
1 5

Output 2:

Copy
-1

DỊCH CHUYỂN TỨC THỜI

Nộp bài
Time limit: 1.4 / Memory limit: 512M

Point: 100

Trong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài


GHÉP CHỮ

Nộp bài
Time limit: 1.8 / Memory limit: 549M

Point: 100

Trong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài


Mua vé

Nộp bài
Time limit: 1.0 / Memory limit: 256M

Point: 100

n người xếp hàng mua vé một trận bóng theo thứ tự 1 đến n. Mỗi người cần mua một vé, nhưng người bán vé lại có thể bán cho mỗi người tối đa hai vé. Do đó, một số người có thể rời hàng và nhờ người đứng trước mình mua hộ vé. Biết ti là thời gian cần thiết để người thứ i mua vé cho mình. Nếu người thứ i+1 rời hàng và nhờ người i mua hộ vé thì mất ri thời gian để mua cho cả hai.

Hãy xác định thời gian mua vé nhỏ nhất.

Input

  • Dòng đầu chứa số nguyên dương n (n6104)
  • Dòng thứ hai chứa n số nguyên dương miêu tả dãy t[1],t[2],...,t[n].(t[i]30000)
  • Dòng thứ ba chứa n1 số nguyên dương miêu tả dãy r[1],r[2],...,r[n1]. (r[i]30000)

Output

  • In ra thời gian ít nhất để mua vé cho n người.

Sample Test

Input

Copy
5
2 5 7 8 4
4 9 10 10

Output

Copy
18

Tích chập

Nộp bài
Time limit: 1.0 / Memory limit: 549M

Point: 100


Bộ Năm Số

Nộp bài
Time limit: 1.0 / Memory limit: 256M

Point: 100

Trên dãy số nguyên a1,a2,...,an và với hai số nguyên w1,w2, ta định nghĩa một bộ năm chỉ số 1i1<i2<...<i5n được gọi là bộ năm và có trọng số được tính bằng: (w1×ai1)+(w2×ai2)+a3+(w2×ai4)+(w1×ai5).

Ví dụ, trên dãy gồm 7 số nguyên 2,8,1,9,1,1,8w1=1, w2=1 thì bộ năm chỉ số 2,3,4,6,7 là một bộ năm có trọng số bằng (1×8)+(1×1)+9+(1×(1))+(1×8)=25, đây cũng là bộ năm có trọng số lớn nhất trong tất cả các bộ năm.

Yêu cầu: Cho dãy số a1,a2,...,an và hai số nguyên w1w2. Hãy tìm bộ năm có trọng số lớn nhất.

Input

  • Dòng đầu chứa ba số nguyên n,w1,w2 (5n105;|w1|,|w2|100)
  • Dòng thứ hai gồm n số nguyên a1,a2,...,an (|ai|109).

Output

  • Gồm một số nguyên là trọng số của bộ năm lớn nhất tìm được.

Subtask

  • 20% số test ứng với 1n100
  • 20% số test ứng với w1=w2=0
  • 20% số test ứng với n5000,w1=0
  • 20% số test ứng với w1=0
  • 20% số test còn lại không có giới hạn gì thêm.

Sample Input 1

Copy
7 1 -1
2 8 1 9 1 -1 8

Sample Output 1

Copy
25

Sample Input 2

Copy
7 0 0
2 8 1 9 1 -1 8

Sample Output 2

Copy
9

Time limit: 1.0 / Memory limit: 256M

Point: 100

Cho một số nguyên dương n, hãy phân tích số n thành tổng của một số số nguyên dương sao cho bội chung nhỏ nhất của chúng là lớn nhất có thể.

Input

  • Gồm một số nguyên dương n, (1n340)

Output

  • In ra bội chung nhỏ nhất tìm được.

Sample Test

Input:

Copy
10

Output:

Copy
30

Giải thích: Số 10 được phân tích thành tổng của 3 số 2,3,5, bội chung nhỏ nhất của ba số đó bằng 30, đây là kết quả lớn nhất có thể.


Nghiện điện tử

Nộp bài
Time limit: 1.0 / Memory limit: 256M

Point: 100

Các nghiện thủ đang bị nhốt trong căn phòng có 1 mật mã được mã hóa trong mảng A có độ dài n. Bởi muốn nghiện Liên Quân, thần đồng đã sai người tìm và giải mã nó. Ta biết được mảng A có thể chia thành nhiều dãy con liên tiếp (và có 2n1 cách chia ). Với mỗi dãy con được chia, giá trị của dãy con đấy nếu gồm các số từ vị trí l đến r là :

  • rl+1 nếu tổng các số từ l đến r lớn hơn hẳn 0.
  • 0 nếu tổng các số từ l đến r bằng 0.
  • (rl+1) nếu tổng các số từ l đến r nhỏ hơn hẳn 0.

Gọi S là tổng các giá trị của dãy con trong 1 cách chia. Mã hóa của căn phòng là S lớn nhất trong tất cả các cách chia. Biết rằng tin Ams 21-24 toàn những feeder liên quân và best tin học, thần đồng muốn nhờ các bạn tìm mật mã trên.

Input

  • Dòng đầu tiên gồm số n
  • Dòng tiếp theo gồm n số của mảng A

Output

  • In ra một số là giá trị S lớn nhất tìm được.

Sample Test

Input:

Copy
5
-1 -2 3 -1 -1

Output

Copy
1

Sample Test 2

Input:

Copy
6
-1 2 -3 4 -5 6

Output

Copy
6

Sample Test 3

Copy
7
1 -1 -1 1 -1 -1 1

Output

Copy
-1
Giải thích:
  • Test 1 chia thành (-1 -2 ) (3 -1 -1)
  • Test 2 chia thành (-1 2 -3 4 -5 6)
  • Test 3 chia thành (1 -1 -1 1 -1) (-1 1)

Ràng buộc:

  • Ai109
  • Subtask 1: n20 (30%)
  • Subtask 2: n5000 (40%)
  • Subtask 3: n5105 (30%)