Olympic Truyền thống 30/4 2018 - Tin học - Khối 11

Công ty viễn thông AZPHONE đang đối mặt với tình trạng nghẽn mạng 4G tại một số thời điểm
trong năm. Hiện tại công ty đã ghi nhận được số lượng thuê bao truy cập trong từng giây của \(N\) giây
liên tiếp, là dãy số nguyên không âm \(a_1, a_2, …, a_N\) (\(a_i\) là số lượng thuê bao tại giây \(i, 1 ≤ i ≤ N\)).
Công ty muốn biết tần suất truy cập \(T(i, L)\) của \(L\) giây liên tiếp kể từ giây \(i\), trong đó \(T(i, L) = (a_i + a_{i+1} + … + a_{i+L-1})/L (1 ≤ i < N - L)\) với điều kiện \(L\) phải không nhỏ hơn một hằng số \(K\) cho trước
\((1 ≤ K ≤ L ≤ N)\).

Yêu cầu: Cho biết \(K\) và dãy a_1, a_2, …, a_N. Hãy giúp công ty xác định giá trị lớn nhất của \(T(i, L)\).

Input

• Dòng đầu tiên là hai số nguyên \(N\) và \(K\) (\(1 ≤ N ≤ 300000\))
• Dòng thứ hai gồm dãy số nguyên không âm \(a_1, a_2, …, a_N (0 ≤ a_i ≤ 10^6)\).

Các số trên cùng một dòng cách nhau một ký tự trống (dấu cách).

Output

• Ghi ra duy nhất một dòng là giá trị lớn nhất của \(T(i, L)\), giá
  trị bình quân gồm 6 chữ số sau dấu chấm thập phân.

Example

4 1
1 0 4 3

4.000000

5 2
2 4 3 4 1

3.666667

Ràng buộc: 60% số test ứng với 60% số điểm của bài có \(N ≤ 5000\)

Tại sa mạc Sahar có \(S\) trạm rada mặt đất (đánh số từ 1 đến \(S\)) có chức năng thu-phát tín hiệu. Mỗi
trạm này thu tín hiệu từ vũ trụ rồi truyền phát những tín hiệu hữu ích thu được về trung tâm nghiên
cứu vũ trụ NAS. Trạm \(i\) đặt tại toạ độ (\(x_i, y_i\)), có bán kính truyền phát là \(r_i\) và dung lượng tín hiệu
cần truyền là \(m_i\) (đơn vị tính là TB-TeraByte).

Cũng trên sa mạc Sahar này, NAS có đặt nhiều trạm làm việc cố định để phục vụ nhiệm vụ thu thập
thông tin từ các trạm rada mặt đất nhờ các \(UAV\) chuyên dụng (máy bay tự hành cỡ nhỏ tầm thấp).
Trong phiên làm việc hôm nay, một UAV có tên Concor xuất phát từ trạm trung tâm có toạ độ (0,
0) sẽ bay qua \(N\) trạm làm việc (đánh số từ 1 đến \(N\)), lần lượt từ trạm 1 đến trạm \(N\) rồi quay trở về
trạm trung tâm. Concor sẽ chỉ bay theo một đường thẳng giữa hai trạm làm việc liên tiếp. Trong quá
trình bay, bất kì khi nào khoảng cách giữa vị trí của Concor và vùng có tín hiệu truyền phát của một
trạm rada mặt đất nhỏ hơn hoặc bằng \(D\), nó sẽ nhận được toàn bộ lượng tín hiệu cần truyền của trạm
rada đó. Đặc biệt, nếu có trạm rada nào đó nằm trên hành trình của Concor thì Concor có giải pháp
để bay qua trạm đó một cách an toàn và thu được toàn bộ lượng tín hiệu tại đây. Concor chỉ thu
nhận tín hiệu tại mỗi trạm rada không quá một lần.

Yêu cầu: Cho trước thông tin về các trạm rada cũng như các trạm làm việc, hãy tính tổng dung
lượng thông tin mà Concor thu nhận được trên hành trình.

Input

• Dòng đầu ghi 3 số nguyên \(S, N, D\) lần lượt là: số trạm rada mặt đất, số trạm làm việc và
  khoảng cách giới hạn mà Concor có thể nhận được tín hiệu từ các trạm rada (\(1 \le S, N \le 2000; 1 \le D \le 50\)).
• \(S\) dòng tiếp theo, dòng thứ \(i\) chứa 4 số nguyên \(x_i, y_i , r_i , m_i\) lần lượt là 2 toạ độ, bán kính
  truyền phát và lượng thông tin cần truyền của trạm rada thứ \(i\) như miêu tả phía trên (\(1 \le r_i \le 100; 1 \le m_i \le 10000\)).
• \(N\) dòng tiếp theo, dòng thứ \(i\) trong các dòng này chứa 2 số nguyên \(x_i, y_i\), là toạ độ của trạm
  làm việc thứ \(i\).

Các toạ độ \(x_i, y_i\) của các trạm rada cũng như các trạm làm việc, là các số nguyên có giá trị tuyệt
đối không vượt quá 5000. Các số thuộc cùng một dòng được ghi cách nhau bởi ít nhất một ký tự
trống (dấu cách). Dữ liệu đảm bảo không có hai trạm rada cũng như trạm làm việc nào có cùng
tọa độ.

Output

• Ghi ra duy nhất một số nguyên là tổng dung lượng
  thông tin (đơn vị tính là TB) mà Concor thu nhận được trên toàn bộ hành trình.

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(S, N \le 500\).
• Subtask \(2\) (\(50\%\) số điểm): Không có ràng buộc gì thêm.

Example

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

21

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

27

Cho 2 xâu ký tự \(S\) và \(T\) trong đó nếu xâu nào khác rỗng thì chỉ gồm các ký tự thuộc tập hợp {\(‘U’,‘L’, ‘R’\)}.

Xét một cây nhị phân vô hạn, mỗi nút trên cây có đúng một nút cha và hai nút con (nút cha của nút
gốc là chính nó). Xuất phát từ nút gốc, ta có thể di chuyển trên cây đã cho nhờ xâu \(S\) bằng cách
duyệt lần lượt các ký tự của xâu \(S\) theo quy tắc: \(‘L’\) là chuyển sang nút con trái, \(‘R’\) là sang nút con
phải và \(‘U’\) là chuyển về nút cha. Quá trình này kết thúc tại nút nào đó \(X\). Đương nhiên, nếu \(S\) là
xâu rỗng thì \(X\) chính là nút gốc.

Ký hiệu \(\Omega\) là tập hợp tất cả các xâu con của xâu \(T\) (mỗi xâu con của \(T\) nhận được từ \(T\) bằng cách
xoá bỏ một số tuỳ ý các ký tự của nó; xâu rỗng và bản thân \(T\) đều là xâu con của \(T\)).

Yêu cầu: Hãy cho biết số nút khác nhau trên cây có thể di chuyển đến được, bắt đầu từ nút \(X\), bằng
cách di chuyển trên cây nhờ tất cả các xâu trong \(\Omega\).

Input

• Dòng đầu ghi số nguyên \(T (T \le 50)\), là số lượng bộ dữ liệu vào.
• Mỗi bộ dữ liệu vào gồm 2 dòng liên
  tiếp trong đó mỗi dòng bắt đầu bằng ký
  tự ‘#’ và tiếp theo là xâu \(S\) (dòng đầu)
  hoặc xâu \(T\) (dòng tiếp theo). Độ dài
  mỗi xâu \(S, T\) đều không vượt quá
  \(100000 (10^5)\).

Output

• Ghi ra các số nguyên, mỗi số trên một dòng, là kết quả
  tìm được tương ứng với bộ dữ liệu vào. Các
  kết quả cần được lấy là dư của phép chia cho
  \(100000000 (10^8)\).

Scoring

• Subtask \(1\) (\(30\%\) số điểm): tổng độ dài các xâu \(S\) và \(T\) không vượt quá \(22\).
• Subtask \(2\) (\(50\%\) số điểm): xâu \(S\) là xâu rỗng (độ dài bằng 0).
• Subtask \(3\) (\(20\%\) số điểm): Không cỏ ràng buộc gì thêm.

Example

5
#
#LL
#LR
#
#LU
#RLL
#
#
#LR
#RLUL

3
1
6
1
8