JUMP Contest Div 2

bin9638 là một cậu bé thích xếp hình, hôm nay cậu ấy dùng các hình lập phương \(1 * 1*1\) để xếp thành một hình hộp chữ nhật có kích thước \(a * b*c\). Sau đó bin9638 sơn lên mặt ngoài của hình hộp chữ nhật. Bây giờ bin9638 nhờ algorit tính xem có bao nhiêu hình lập phương nhỏ $111 $ được sơn ít nhất một mặt, các bạn hãy giúp cậu ấy nhé !

Input

• Gồm ba dòng lần lượt là ba số tự nhiên \(a,b,c(1\le a,b,c \le 100)\).

Output

• Gồm một số tự nhiên là số hình lập phương nhỏ được sơn.

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(1 \le a \le b \le c \le 100\).
• Subtask \(2\) (\(50\%\) số điểm): \(1\le a,b,c \le 100\).

Example

1 
2
3

6

3 
4 
3

34

Ngày xửa ngày xưa có \(5\) anh em siêu nhân, họ có khả năng trừ gian diệt ác, là đại diện của chính nghĩa, công lí. Họ được đặt tên theo các chất, đồng thời cũng nói lên năng lực của họ:

• Amonia: siêu nhân tè dầm.

• Hydro sulfide: Siêu nhân thả bom.

• Methamphetamine: siêu nhân bay lắc

• Dinito monoxide: siêu nhân hề hước.

• Silica: Siêu nhân khát nước.

Trong khi chiến đấu, bin9638 là chỉ huy của biệt đội siêu nhân đã nhận được một dãy mật mã về những siêu nhân đang chiến đấu, dãy này có chứa một số xâu con liên tiếp là tên của các siêu nhân. Với mỗi mật mã, bin9638 cần xác định xem có siêu nhân nào ở trong mật mã đó không (tên của siêu nhân phải ghi đúng cả chữ hoa thường và cả dấu cách), các bạn hãy giúp cậu ấy nhé !

Input

• Dòng đầu là số mật mã \(Q\) (\(Q \le 10\)).
• \(Q\) dòng tiếp theo mỗi dòng là một xâu \(S\) (Xâu \(S\) chứa các chữ các latin in thường, in hoa và dấu cách).

Output

• Ghi ra \(Q\) dòng, dòng thứ \(i\) ghi "Yes" nếu mật mã thứ \(i\) chứa siêu nhân, "No" nếu ngược lại.

Scoring

• Subtask \(1\) (\(40\%\) số điểm): |\(S\)|\(\le100\).
• Subtask \(2\) (\(60\%\) số điểm): |\(S\)|\(\le10^5\).

Example

5
Hydro sulfide thomqua
Methamphetamin phequa
loAmoniatrongquan
cuoicung dinito monoxide
SilicakhatnuocnenuongAmonia

Yes
No
Yes
No
Yes

Hôm nay bin9638 làm thơ tình ái tặng người yêu của mình, bài thơ có dạng như sau:

"Anh sẽ why em make poem tình ái

Anh sẽ gom cloud kết thành castle

Vì castle named tình ái

Đón two đứa chúng we mà thôi

Em ơi castle tình ái that

Chắc no yes trên trần gian

Anh take em vào bằng singing

Chắp đôi wing nhung thiên thần"

algorit thấy bin9638 làm thơ quá hay, quá xuất sắc nên cũng học làm theo. Mỗi tội vì mãi code quá nhiều nên bài thơ của cậu chỉ là một xâu kí tự \(S\).

Bây giờ thay vì thơ thì algorit lại nghĩ một vấn đề liên quan đến xâu này. Một xâu con của \(S\) là một đoạn kí tự liên tiếp của nó. Ví dụ xâu TTCC thì có các xâu con là T,C,TT,TC,CC,TTC,TCC,TTCC. Bây giờ bin9638 cần tính giá trị BTS của xâu \(S\), ta có BTS(\(S\))\(= \sum_{st∈S}^{} R(st)*|st|\). Ở đây \(st\) là xâu con của \(S\), \(R(st)\) là số lần xuất hiện của nó trong \(S\), \(|st|\) là độ dài xâu \(st\).

Ví dụ với \(S\)=TTCC thì BTS\((S)\)=\(2 * 1+2*1+1*2+1*2+1*2+1*3+1*3+1*4\)=\(20\).

Input: Một dòng duy nhất là xâu \(S\) gồm các chữ cái latin viết hoa.

Output: Một dòng duy nhất là đáp án.

Ví dụ:

Input:

TTCC

Output:

20

Giới hạn:

• \(30\)% test có |\(S\)| ≤ \(500\).

• \(30\)% test có |\(S\)| ≤ \(2000\).

• \(40\)% test có |\(S\)| ≤ \(500000\).

Quốc là một sinh viên chăm chỉ, cần cù và có một cậu bạn thân tên là Phú. Trong những năm tháng quá, Quốc luôn theo đuổi một cô gái mà Phú thầm yêu. Trong một lần đi chơi cùng cô ấy thì Quốc sử dụng tiền của mình để mua quà cho cô ấy, sau đó Quốc quyết định tỏ tình nhưng cô ấy đã từ chối. Quốc về nhà với một tâm trạng buồn bã, nhưng điều mà Quốc lo lắng nhất là trong ví chỉ còn vài đồng, "làm sao sống hết tháng này đây ?". Thế là Quốc quyết định lên mạng và mở một trò chơi cho mọi người cùng tham gia.

Trò chơi có \(N\) người tham gia vào trò chơi của Quốc và người chơi có thể chọn một kí tự \(C (C = 'A'\) hoặc \(C = 'B')\), sau đó mỗi người chơi đưa ra thông số \(A_i\) và muốn đặt cược \(B_i\) đồng. Quốc cũng đưa ra một thông số nhất định \(L(0 \le |L| \le 10^9)\) (Các thông số đều là các giá trị nguyên). Quốc tưởng tượng rằng mình có thể biết trước các thông số mà người chơi đưa ra.

Trong trường hợp người chơi đưa ra kí tự \(C = 'A'\)

• Nếu thông số của người chơi đưa ra là lớn hơn hoặc bằng thông số của Quốc \((A_i \ge L)\) thì người chơi đó sẽ nhận được \(B_i\) đồng và đồng thời Quốc sẽ mất \(B_i\) đồng.
• Ngược lại, nếu thông số của người chơi đưa ra bé hơn thông số của Quốc \((A_i < L)\) thì Quốc sẽ nhận được \(B_i\) đồng và người chơi đó sẽ mất \(B_i\) đồng.

Trong người hợp người chơi đưa ra kí tự \(C = 'B'\)

• Nếu thông số của người chơi đưa ra là bé hơn hoặc bằng thông số của Quốc \((A_i \le L)\) thì người chơi đó sẽ nhận được \(B_i\) đồng và đồng thời Quốc sẽ mất \(B_i\) đồng.
• Ngược lại, nếu thông số của người chơi đưa ra lớn hơn thông số của Quốc \((A_i > L)\) thì Quốc sẽ nhận được \(B_i\) đồng và người chơi đó sẽ mất \(B_i\) đồng.

Yêu cầu : Bạn hãy chọn cho Quốc mức thông số \(L\) nhỏ nhất sao cho số tiền thu về là nhiều nhất trong trí tưởng tượng của Quốc.

Input

• Dòng đầu tiên gồm một số nguyên \(N\) là số lượng người chơi tham gia.
• \(N\) dòng tiếp theo, mỗi dòng gồm kí tự \(C\) và hai số nguyên \(A_i , B_i (1 \le B_i \le 10^9)\) lần lượt là thông số và số tiền mà người chơi thứ \(i\) muốn đặt cược.

Output

• Gồm 2 số nguyên là \(L\) và số tiền nhận được khi Quốc đưa ra thông số \(L\).

Scoring

• Subtask \(1\) (\(25\%\) số điểm): \(N \le 1000\) và \(0 \le |A_i| \le 1000\)
• Subtask \(2\) (\(25\%\) số điểm): \(N \le 1000\) và \(0 \le |A_i| \le 10^9\)
• Subtask \(3\) (\(25\%\) số điểm): \(N \le 10^5\) và \(0 \le |A_i|, \le 10^6\)
• Subtask \(4\) (\(25\%\) số điểm): \(N \le 2 * 10^5\) và \(0 \le |A_i|\le 10^9\)

Example

5 
A 10 30
B 3 20
A 6 10
A 5 10
B 8 20

11 10

Bé Laurier vì nghỉ dịch ở nhà nên không có gì làm, vì quá chán nản nên cô bé òa khóc. Rất may là \(2\) người thân của cô ấy (Cô Tếch và Dì Ana) tới nhà chơi và rủ Laurier đi trồng dâu.

Vườn dâu của Cô Tếch và Dì Ana là một hình chữ nhật có dạng ô lưới gồm \(a\) đường kẻ ngang và \(b\) đường kẻ dọc cách nhau \(1\) đơn vị. Các cây dâu chỉ được trồng ở các điểm giao nhau giữa các đường kẻ và bắt buộc ở ngoài viền của vườn và \(2\) cây dâu bất kì phải có khoảng cách ít nhất là \(k\) đơn vị( khoảng cách giữa \(2\) cây dâu là độ dài đoạn thẳng nối chúng ).

Bây giờ Cô Tếch và Dì Ana giao vườn dâu cho Laurier trồng. Laurier phân vân không biết mình sẽ trồng được tối đa bao nhiêu cây dâu, hãy giúp cô ấy nhé !

Input

• Một dòng duy nhất là \(3\) số nguyên dương \(a,b,k (2 \le k \le a \le b \le 2*10^9)\).

Output

• Gồm một số nguyên duy nhất là số dâu trồng được tối đa.

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(k \le a \le b \le 10^5\).
• Subtask \(2\) (\(50\%\) số điểm): \(k \le a \le b \le 2*10^9\).

Example

2 3 1

6

4 4 2

4

Vào một buổi hoàng hôn, ánh nắng len lỏi qua ô cửa sổ của nhà em. Tôi đứng ngoài trời chỉ biết nhìn vào ô cửa sổ rồi mĩm cười. Trên đường về nhà, tôi cứ ngẩn ngơ vì cứ mãi suy nghĩ về em thế là tôi đã va vào một ông cụ, làm cho ông cụ bị thương. Tôi hốt hoảng, liền dẫn ông cụ đến bệnh viện để kiểm tra, cũng may là ông ấy chỉ bị trầy xước nhẹ, sau đó là lúc mà tôi phải trả tiền cho bác sĩ, tuy nhiên trong người tôi "không một xu dính túi". Ông cụ là một người cực kì giỏi toán, lúc trước ông từng là một giáo viên dạy toán xuất sắc, thế là ông đã đố tôi một bài toán và nếu giải được bài này thì tôi không cần phải trả tiền viện phí. Bài toán như sau

Ông cho một dãy số gồm \(N\) số nguyên \(A_1, A_2, A_3, ..., A_N\) và hai số nguyên \(L\) và \(R\), yêu cầu của ông là hãy chọn ra một đoạn con liên tiếp của dãy sao cho độ dài của đoạn con ít nhất là \(L\) và không quá \(R\) đồng thời có giá trị \(AVERAGE\) lớn nhất.

Giá trị \(AVERAGE\) được định nghĩa như sau: \(AVERAGE(u,v) = \frac{\sum_{i = u}^v A_i}{v - u + 1} = \frac{A_u + A_{u + 1} + ... + A_{v - 1} + A_v}{v - u + 1}\) và đảm bảo rằng \(L \le v - u +1 \le R\) \((u \le v)\).

Input

• Dòng đầu tiên là 2 số nguyên \(N, L , R\) \((1 \le L \le R \le N)\).
• Dòng thứ 2 là dãy số \(A_1, A_2, A_3, ..., A_N(|A_i| \le 10^9)\).

Output

• Gồm một số thực duy nhất là giá trị \(AVERAGE\) lớn nhất, đáp án được làm tròn đến \(4\) chữ số thập phân và chính xác đến từng chữ số.

Scoring

• Subtask \(1\) (\(60\%\) số điểm): \(N \le 2000\).
• Subtask \(2\) (\(20\%\) số điểm): \(N \le 2 \times 10^5\).
• Subtask \(3\) (\(20\%\) số điểm): \(N \le 10^6\).

Example

6 3 4
1 2 3 -4 6 -5

2.0000