ApVirus

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

Point: 100

Bé Dino nhận được một mảnh giấy trên đó có ghi một đoạn ký tự chỉ có các ký tự latin in thường (a..z). Yêu cầu: Bạn hãy cho biết trong xâu ký tự Bé Dino nhận được có bao nhiêu lần xuất hiện đoạn ký tự virus.

Input

  • Gồm một xâu ký tự có độ dài 250 ký tự.

Output

  • Một số nguyên duy nhất là số lần xuất hiện xâu virus trong xâu ký tự đã cho.

Sample Input 1

Copy
hpvirushnviruss

Sample Output 1

Copy
2

Đếm Xâu

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

Point: 100


Đồng Hồ

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

Point: 100


Trung Bình

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

Point: 100


Đếm Hình

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

Point: 100


Số Ước

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

Point: 100


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

Time limit: 1.0 / Memory limit: 256M

Point: 100

Cho một dãy a gồm n phần tử nguyên không âm.

Hãy đếm số đoạn con liên tiếp [l,r] của dãy a sao cho tổng của đoạn con đó bằng độ dài của đoạn, hay al+al+1+...+ar=rl+1.

Input

  • Dòng đầu tiên chứa số nguyên dương n.
  • Dòng thứ hai gồm n số nguyên không âm miêu tả dãy a.

Output

  • In ra số đoạn con thỏa mãn.

Điều kiện

  • 1n2105.
  • 0a9.

Subtask

  • 50% số điểm: n1000.
  • 50% số điểm: n2105.

Ví dụ

Input 1:

Copy
3
1 2 0

Output 1:

Copy
3

Input 2:

Copy
5
1 1 0 1 1 

Output 2:

Copy
6

Tribonacci

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

Point: 100

Do đã quá quen với dãy fibonacci, hôm nay, chúng ta hãy cùng tìm hiểu về dãy tribonacci.

Số tribonacci thứ i sẽ có công thức truy hồi như sau: f[i]=f[i1]+f[i2]+f[i3] nếu i>3, ngược lại f[i]=i nếu i3.

Cho n số tribonacci đầu tiên và một số k (kn), hay tìm một dãy con bất kì (không nhất thiết phải liên tiếp) của dãy n số tribonacci này sao cho tổng của các phần tử trong dãy con đó chia hết cho k.

Input

  • Gồm một dòng chứa số nguyên dương n và số nguyên dương k (1kn105)

Output

  • Dòng đầu in ra số q là độ dài của dãy con thỏa mãn tìm được, nếu không tồn tại in ra 1.
  • Dòng thứ hai in ra q chỉ số của dãy con tìm được.
  • Nếu có nhiều hơn một dãy con thỏa mãn, in ra bất kì kết quả nào.

Subtask

  • 30% số test có n20.
  • 40% số test có n2000.
  • 30% số test còn lại có n105.

Sample Test

Input:

Copy
5 4

Output:

Copy
2
2 4

Giải thích:

  • 5 phần tử đầu tiên của dãy tribonacci là: 1 2 3 6 11
  • Chọn ra phần tử thứ 24 có tổng bằng: 2+6=8 chia hết cho 4.

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