Bể nước (OLP MT&TN 2022 CT)

Small

Bài B: Bể nước (bài 2 khối không chuyên)


TAMHOP - Bộ tam hợp (HSG'13)

corona

Cho dãy số nguyên \(a_1, a_2, ..., a_n\), các số khác nhau từng đôi một (\(3 <= N <= 5000\); với mọi i ta có \(|a_i| <= 10^6\)). Bộ ba số \(a_i, a_j, a_k (i <> j <> k)\) được gọi là Bộ tam hợp nếu có một số bất kỳ trong ba số đó bằng trung bình cộng của hai số còn lại.

Yêu cầu:

  • Hãy đếm số lượng bộ tam hợp và tìm bộ tam hợp có tổng giá trị của ba số là lớn nhất.

Dữ liệu vào:

  • Dòng 1 chứa số N;

  • Dòng 2 chứa n số \(a_1, a_2, ..., a_N\) cách nhau ít nhất một dấu cách

Kết quả:

  • Dòng 1 ghi một số nguyên dương là số lượng bộ tam hợp tìm được;

  • Dòng 2 ghi tổng giá trị ba số của bộ tam hợp là lớn nhất.

Input
7
6 1 9 2 3 4 8
Output
5
18

CANDYBOX (HSG10v2-2021)

Small

Input
8 4 2
1 1 3 2 10 10 8 1

Output
15

Giải thích:

  • Ta chọn dãy \([3, 2, 10, 10, 8]\) ta sẽ có dãy \([2, 3, 8, 10]\) sau khi rút gọn, \(S(3, 7) = 2 + 3 + 10 = 15\).

Giới hạn:

  • 40% số test: \(1 ≤ N ≤ 100\),
  • 30% số test: \(1 ≤ N ≤ 10^3\),
  • 30% số test: không có giới hạn gì thêm.

Chia Cặp 1

cuom1999

Lương Xiao Lin có \(n\) em gái có mức độ yêu thương lần lượt là \(a_1, a_2, ..., a_n\). Lương muốn chọn ra \(k\) cặp em gái rời nhau. Gọi \(x\) là chênh lệch lớn nhất giữa hai bạn trong một nhóm. Vì nếu chênh lệch mức độ yêu thương giữa 2 em gái quá lớn thì có thể một em sẽ buồn. Lương là anh trai cao cả, Lương không muốn em gái nào phải buồn. Do đó, Lương muồn x càng nhỏ càng tốt. Các bạn hãy tìm \(x\) giúp Lương nhé, Lương sẽ chia có các bạn 1 em gái nếu các bạn giúp Lương.

Input

Dòng đầu có 2 số nguyên \(n, k\).

Dòng thứ hai có \(n\) số nguyên \(a_1, a_2, ..., a_n \ \)

Output

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

Sample Input 1

6 3
1 4 3 7 11 9

Sample Output 1

3

Sample Input 2

6 2
1 4 3 7 11 9

Sample Output 2

2

Sample Input 3

6 1
1 4 3 7 11 9

Sample Output 3

1

Giải thích

  • Trong test ví dụ 1, chúng ta chia cặp như sau: \((1, 3), (4, 7), (9, 11)\). Cặp có khoảng cách lớn nhất là \((4, 7)\) và \(7-4=3\).
  • Trong test 2, chia cặp \((3, 4), (7, 9)\).
  • Trong test 3, chia cặp \((3, 4)\).

Giới hạn

\(100\)% test có \(2 \leq n \leq 3 \times 10^5, 1 \leq k \leq \dfrac{n}{2}\) và \(1 \leq a_i \leq 10^9\).

Ngẫu nhiên???

CarlavierVN

Sau dịp nghỉ Tết Nguyên Đán 2021, A519PhuongDN đã trở thành một con người bài bạc. Với chiếc điện thoại trong tay, A519PhuongDN có thể gạ solo tiến lên miền Nam ở bất cứ mọi nơi.

Vào một ngày đẹp trời, sau khi chơi qua hàng nghìn ván tiến lên miền Nam, cô bắt đầu cảm thấy chán. Thấy rằng kiếp đỏ đen bài bạc của mình quá phình phường, lại sực nhớ ra A519 đang mở server minecraft, cô bắt tay ngay vào công cuộc tạo nên một mod tiến lên miền Nam trong minercraft.

Là một trò chơi may rủi, cô sẽ phải dùng hàm RNG để sinh ra các trường hợp chia bài cho mỗi người chơi. Số p[i] của lần chơi thứ n được hàm RNG sinh ra có công thức tính như sau:

\(p[i] = x^{p[i - 1]} \mod (10^9 + 7)\)

với số p[i] trong tay, cô nắm bắt được vận mệnh của mình trong mọi ván bài. Nếu như số p[i] mod 2 là số lẻ thì cô sẽ luôn về nhất trong ván bài thứ i. Vì máy tính của cô là máy văn phòng đã vậy còn đang chạy minecraft nên rất ngốn cấu hình, A519PhuongDN nhờ các bạn tính số p[n] ở trận thứ n để cô biết được lúc nào nên all in, tạo tiền đề đạp đổ vị trí người giàu nhất server của CarlavierVN, biết rằng mỗi ván bài tốn 10 phút để hoàn thành và server của CarlavierVN còn 87 ngày nữa là sẽ bắt buộc phải đóng cửa.

Input:

  • Dòng 1 chứa hằng số \(x \le 10^9\)
  • Dòng 2 chứa số \(p[1]\) là số đã được sinh trong trận cô đang chơi \((p[i] \le 10^9)\)
  • Dòng 3 chứa số \(n\) là ván cô cần tính được số ngẫu nhiên mà máy tính sinh ra \((n \le 10^5)\)

Output: in ra YES nếu A519PhuongDN về nhất, nếu ngược lại thì in ra NO


Sample Input:

2
3
2

Sample Output:

NO

Chơi bài ma sói (E div 1)

WuTan, algorit, bin9638

Hôm nay bin9638 đang đánh bài ma sói với algoritWuTan, vì đã quá chán luật ma sói cũ nên cậu đã tự nghĩ ra luật mới.

Bộ bài ma sói gồm một số lá, gồm những lá như sau:

  • dân làng : được kí hiệu là "D", trong bộ bài có thể chứa nhiều lá dân làng.

  • ma sói: được kí hiệu là "M", trong bộ bài có thể chứa nhiều lá ma sói.

  • thợ săn: được kí hiệu là "T", trong bộ bài có thể chứa nhiều lá thợ săn.

  • phù thủy: được kí hiệu là "P", trong bộ bài có thể chứa nhiều lá phù thùy.

  • chiến thắng: được kí hiệu là "#", trong bộ bài chỉ chứa duy nhất MỘTchiến thắng.

Trong mỗi lượt chơi:

  • Chỉ được rút MỘT lá ở đầu hoặc cuối bộ bài.

  • Có thể sử dụng các lá bài thợ săn đang có trên tay, sau khi dùng một lá thợ săn, người chơi sẽ bỏ đồng thơi một lá thợ sănmột lá ma sói xuống (không dược bỏ lại vào bộ bài).

  • Có thể sử dụng các lá bài phù thùy đang có trên tay, sau khi dùng một lá phù thùy người chơi sẽ bỏ đồng thời một lá phù thùymột lá dân làng xuống (không được bỏ lại vào bộ bài).

  • Người chơi có thể sử dụng tùy ý số lượng lá bài mình đang có, tuy nhiên chỉ được rút một lá bài duy nhất. Không nhất thiết phải làm theo thứ tự, người chơi có thể rút bài trước rồi sử dụng các lá bài, hoặc sử dụng các lá bài trước, rồi sau đó mới rút bài.

  • Khi kết thúc một lượt chơi, nếu số lá ma sói người chơi đang có trên tay lớn hơn hẳn số lá dân làng người chơi đang có thì sói sẽ ăn hết dân, lúc này trò chơi kết thúc và người chơi sẽ thua cuộc.

  • Người chơi sẽ chiến thắng nếu rút được lá chiến thắng.

Tuy là người đặt ra luật của trò chơi này, nhưng bin9638 không biết cách chơi như thế nào để chiến thắng, đồng thời sau khi chiến thắng, anh ấy muốn chênh lệch giữa số lá dân làng còn lại trên tay và số lá ma sói còn lại trên tay là nhỏ nhất.

Hãy giúp bin9638 chơi một cách tối ưu nhất nhé!

Input

  • Dòng đầu tiên là số ván bài \(Q\).
  • \(Q\) dòng tiếp theo mỗi dòng là một xâu \(S\) miêu tả bộ bài.

Output

  • Gồm \(Q\) dòng với mỗi dòng là kết quả của ván đấu tương ứng, nếu bin9638 thua thì ghi "LOSE", ngược lại ghi số lá bài chênh lệch bé nhất sau khi thắng.

SampleInput:

5
M#DMMT
MD#DM
MM#DDDPPT
DDDP#DDDD
TPMD#MM

SampleOutput:

0
LOSE
0
2
0

Giải thích

  • Ở ván bài đầu tiên, bóc các lá lần lượt ở vị trí \(6,1,2\) (sử dụng lá T để loại một lá M để chiến thắng).
  • Ván bài thứ hai, người chơi không thể bóc bài vì bị chặn hai lá M ở hai đầu.
  • Ván bài thứ ba người chơi bóc các lá ở vị trí \(9,8,7,6,5,1,2,3\) ( không cần sử dụng các lá PT).
  • Ván thứ 4, người chơi bốc ở vị trí \(1,2,3,4,5\) ( sử dụng lá P).
  • Ván cuối, người chơi bốc ở vị trí \(1,2,3,4,5\) ( sử dụng cả lá TP )

Ràng buộc

  • \(Q \le 50\)
  • 30% số điểm tương ứng với : \(|S| ≤ 10.\)
  • 30% số điểm tương ứng với : \(|S| ≤ 100.\)
  • 20% số điểm tương ứng với : \(|S| ≤ 1000.\)
  • 20% số điểm tương ứng với : \(|S| ≤ 2000.\)

RICEATM

dophanthuan

Bài 1. RICEATM


.

Restangles

admin

Có bao nhiêu hình chữ nhật trong hình dưới đây?

enter image description here

Chúng ta có \(6\) hình chữ nhật \(1 \times 1\), \(4\) hình \(2 \times 1\), \(3\) hình \(1 \times 2\), \(2\) hình \(2 \times 2\), \(2\) hình \(3 \times 1\) và \(1\) hình \(3 \times 2\), tổng cộng là \(18\) hình. Rõ ràng chúng ta quan tâm đến các hình chữ nhật có các đỉnh nằm ở các đỉnh lưới, tức là các điểm nằm ở giao của các đường thẳng ngang và dọc, và nằm trọng vẹn trong lưới. Lưới trên có kích thước \(3 \times 2\).

Yêu cầu: Có bao nhiêu hình chữ nhật có chu vi ít nhất là \(6\) ở hình trên? Có thể tham khảo phần Ví dụ để biết câu trả lời.

Dữ liệu vào

  • Một dòng chứa 3 số nguyên \(n, m, p\) (\(1 ≤ n, m ≤ 5000, 4 ≤ p ≤ 2 \times (n+m)\)) cho biết kích thước của lưới và giới hạn dưới của chu vi các hình chữ nhật.

Kết quả

  • Một dòng in một số nguyên: số các hình chữ nhật có đỉnh nằm tại các điểm của lưới \(n \times m\), nằm trọn vẹn trong lưới và chu vi ít nhất là \(p\).

Sample Input

3 2 4

Sample Output

18

Sample Input

3 2 6

Sample Output

12

Nguồn: 2020 Thi thử Online lần 1

Đoán số

Small

Cho 8 số nguyên không âm \(𝑑_1, 𝑑_2, … , 𝑑_4\) và \(𝑟_1, 𝑟_2, … , 𝑟_4\) trong đó \(∀𝑖: 0 ≤ 𝑟_𝑖 < 𝑑_𝑖\)

Tìm số nguyên dương \(𝑛\) bé nhất thỏa mãn: \(𝑛\) chia \(𝑑_𝑖\) dư đúng \(𝑟_𝑖\) (\(∀𝑖: 1 ≤ 𝑖 ≤ 4\))

Dữ liệu

  • Dòng 1 chứa số \(𝑇 ≤ 10^4\) là số test.
  • \(𝑇\) khối dòng tiếp theo mỗi khối 4 dòng chứa dữ liệu cho 1 test: Dòng thứ \(𝑖\) chứa cặp số nguyên \(𝑑_𝑖\), \(𝑟_𝑖\) cách nhau bởi dấu cách (\(0 ≤ 𝑟_𝑖 < 𝑑_𝑖 ≤ 10^4\))

Kết quả

  • Với mỗi test ghi ra một số nguyên dương duy nhất là số \(𝑛\) tìm được, trong trường hợp không tồn tại số \(𝑛\) thỏa mãn điều kiện, ghi ra số -1

Sample input

2
20 3
15 3
21 18
35 18
5 1
5 2
5 3
5 4

Sample output

123
-1

Nguồn: LMH-ĐHSP

Ổn định

kid2201

Trong mạng xã hội, mỗi trang web được tổ chức trên một máy tính thành viên và cung cấp dịch vụ truy nhập tới một số trang web khác. Để truy nhập tới một trang web nào đó không có trong danh mục kết nối trực tiếp của mình, người dùng phải truy nhập tới trang web khác có kết nối với mình, dựa vào danh mục dịch vụ của trang web này để chuyển tới trang web khác theo tùy chọn, cứ như thế cho đến khi tới được trang web mình cần. Thời gian để truy nhập tới một trang web phụ thuộc chủ yếu và số lần mở trang web trong quá trình truy nhập. Như vậy, người dùng cần chủ động chọn lộ trình truy nhập hợp lí.

Sau một thời gian làm việc trên mạng, Sáng - một thành viên nhiệt thành đã tích lũy kinh nghiệm, tạo một cơ sở dữ liệu, cho biết từ một trang web có thể đi tới những trang web nào trong mạng. Trong cơ sở dữ liệu, các trang web được đánh số từ 1 đến \(n\) và có \(m\) bản ghi, mỗi bản ghi có dạng cặp có thứ tự \((u, v)\) cho biết trang web \(u\) có kết nối tới trang web \(v\) \(( 1 ≤ u, v ≤ n, u ≠ v)\). Cơ sở dữ liệu chưa được chuẩn hóa, vì vậy có thể chứa các cặp \((u, v)\) giống nhau.

Trang web của Sáng có số hiệu là \(s\). Dựa vào cơ sở dữ liệu, Sáng có thể xác định lộ trình truy nhập nhanh nhất (tức là số lần phải mở trang web là ít nhất) từ trang web \(s\) tới trang web \(u\) bất kì. Tuy vậy, ở mạng xã hội, mọi chuyện đều có thể xảy ra: một khu vực nào đó bị mất điện, máy của một thành viên bị hỏng, trang web đó đang bị đóng để nâng cấp, ... Kết quả là một vài trang web nào đó có thể tạm thời không hoạt động. Như vậy, nếu từ \(s\) có ít nhất hai lộ trình nhanh nhất khác nhau tới u thì khả năng thực hiện truy nhập được một cách nhanh nhất tới u là lớn hơn so với những trang web chỉ có duy nhất một lộ trình nhanh nhất. Hai lộ trình gọi là khác nhau nếu có ít nhất một trang web có ở lộ trình này mà không có ở lộ trình kia hoặc cả hai lộ trình cùng đi qua những trang web như nhau nhưng theo các trình tự khác nhau. Những trang web mà từ \(s\) tới đó có ít ra là hai lộ trình nhanh nhất khác nhau được gọi là ổn định đối với \(s\). Trang web mà từ \(s\) không có lộ trình tới nó là không ổn định đối với \(s\).

Ví dụ, với mạng nêu ở hình bên \((n = 6, m = 9)\) các trang web \(4\) và \(3\) là ổn định với \(s = 1\) (từ \(1\) tới \(4\) có \(2\) lộ trình nhanh nhất: \(1 - 2 - 4\) và \(1 - 5 - 4\), từ \(1\) tới \(3\) cũng có \(2\) lộ trình nhanh nhất: \(1 - 2 - 4 - 3\) và \(1 - 5 - 4 - 3\)).

enter image description here

Yêu cầu: Cho các số nguyên dương \(n, m, s\) và \(m\) cặp số \((u, v)\) xác định từ \(u\) có thể kết nối trực tiếp tới được \(v\). Hãy xác định số lượng trang web ổn định đối với \(s\).

Input:

  • Dòng đầu tiên chứa \(3\) số nguyên \(n,\) \(m\) và \(s (2≤ n ≤ 10000, 1 ≤ m ≤ 50000, 1 ≤ s ≤ n).\)
  • Mỗi dòng trong \(m\) dòng tiếp theo chứa \(2\) số nguyên \(u\) và \(v\) \((1 ≤ u, v ≤ n, u ≠ v).\)

Output:

Một số nguyên - số trang web ổn định đối với \(s\).

Ví dụ Input

6 11 1
1 5
1 5
5 6
1 2
5 4
2 4
4 3
5 4
5 2
3 2
6 5

Output

2

Nguồn: VOI 2010

Siêu thị (OLP MT&TN 2021 CT)

Small

Hệ thống giao thông của thành phố mà ĐN được quy hoạch có dạng một lưới hình chữ nhật gồm \(m× n\) ô vuông đơn vị với các con đường ngang và dọc chạy xuôi theo các ô của lưới. Các con đường ngang bắt đầu từ bên trái sang bên phải của lưới, song song với nhau và được đánh số từ 1 đến \(m+1\) theo thứ tự từ trên xuống dưới. Các con đường dọc bắt đầu từ phía trên xuống phía dưới của lưới, song song với nhau và được đánh số từ 1 đến \(n+1\) theo thứ tự từ trái sang phải. Giao của đường ngang thứ \(u\) với đường dọc thứ \(v\) gọi là địa điểm \((u,v)\).

Nơi ở hoặc nơi làm việc của người dân là một địa điểm trên lưới. Ban quy hoạch đô thị đã khảo sát được hàng ngày có một số lượng lớn người dân có thói quen ghé qua siêu thị sau giờ làm rồi mới trở về nhà. Căn cứ vào dữ liệu của d người dân ở các địa điểm \(A_1,A_2,…,A_d\) và có địa điểm làm việc tương ứng là \(B_1,B_2,…,B_d\) (người ở địa điểm \(A_i\) làm việc tại địa điểm \(B_i, 1≤ i≤ d\)), Ban quy hoạch quyết định chọn một tuyến phố thương mại xuôi theo một con đường ngang để xây dựng một số lượng \(k\) siêu thị phục vụ người dân thuận tiện sinh hoạt, tiết kiệm chi phí và thời gian đi lại. Các siêu thị được đặt tại các địa điểm trên lưới và có thể trùng với địa điểm nơi ở hoặc nơi làm việc của người dân.

Yêu cầu: Hãy giúp Ban quy hoạch đô thị chọn được một con đường ngang và \(k\) địa điểm trên con đường ngang này để xây dựng siêu thị sao cho tổng tất cả độ dài quãng đường từ nơi làm việc của từng người đến một siêu thị và từ siêu thị đó trở về nơi ở là nhỏ nhất. Độ dài quãng đường từ địa điểm (\(u,v\)) đến địa điểm (\(u',v'\)) được tính bằng \(|u-u'|+|v-v'|\).

Dữ liệu: Vào từ thiết bị vào chuẩn:

  • Dòng đầu tiên chứa bốn số nguyên dương \(m,n,d,k\ (m,n≤ 10^9; k≤ 15)\);
  • Dòng thứ hai chứa \(d\) cặp số nguyên dương \(u_1,v_1,u_2,v_2,…,u_d,v_d\) (\(1≤ u_i≤ m+1\) và \(1 ≤ v_i≤n+1\) với mọi \(1≤ i≤ d\)) là địa điểm nơi ở của d người dân;
  • Dòng thứ ba chứa \(d\) cặp số nguyên dương \(x_1,y_1,x_2,y_2,…,x_d,y_d\) (\(1≤ x_i≤ m+1\) và \(1≤ y_i≤ n+1\) với mọi \(1≤ i≤ d\)) là địa điểm nơi làm việc của d người dân.

Kết quả: Ghi ra thiết bị ra chuẩn một số nguyên duy nhất là tổng độ dài quãng đường nhỏ nhất tìm được khi đặt k siêu thị trên cùng một con đường ngang.

Ràng buộc:

  • Có 16% số test ứng với 16% số điểm của bài thỏa mãn: \(d≤ 300\) và \(v_i=y_i\) (với mọi \(1≤ i≤ d\));
  • 16% số test khác ứng với 16% số điểm của bài thỏa mãn: \(d≤ 3000\) và \(v_i=y_i\) (với mọi \(1≤ i≤ d\));
  • 20% số test khác ứng với 20% số điểm của bài thỏa mãn: \(d≤ 300\);
  • 24% số test khác ứng với 24% số điểm của bài thỏa mãn: \(d≤ 3000\);
  • 24% số test còn lại ứng với 24% số điểm của bài thỏa mãn: \(d ≤ 10^5\).

Ví dụ:

Dữ liệu

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

Kết quả

24

enter image description here

Giải thích ví dụ: Ban quy hoạch đô thị chọn con đường ngang số 3 và hai siêu thị \(S_1,S_2\) ở vị trí giao với đường dọc số 3 và số 4. Lịch trình di chuyển hàng ngày từ nơi làm việc về nhà của bốn người dân như sau:

  • Người thứ nhất đi từ \(B_1\) đến \(S_2\) rồi về \(A_1\) với tổng quãng đường là 8;
  • Người thứ hai đi từ \(B_2\) đến \(S_2\) rồi về \(A_2\) với tổng quãng đường là 4;
  • Người thứ ba đi từ \(B_3\) đến \(S_1\) rồi về \(A_3\) với tổng quãng đường là 6;
  • Người thứ tư đi từ \(B_4\) đến \(S_1\) rồi về \(A_4\) với tổng quãng đường là 6 .

Sắp xếp không tăng

Small

Cho một dãy gồm \(n\) số nguyên dương \(A_1, A_2,…, A_n\). (\(N ≤ 10^4, A_i ≤ 10^9\)). Hãy in ra dãy số sau khi sắp xếp dãy số giảm dần (\(A_i >= A_{i+1}\)).

Input

  • Dòng đầu chứa số \(n\),
  • Dòng thứ hai chứa \(n\) số nguyên dương \(A_1, A_2,…, A_n\).

Output

  • Một dòng chứa dãy số đã sắp xếp giảm dần.

Sample Input

6
91 451 43 3 451 54

Sample Output

451 451 91 54 43 3

Bắn cung

huyhau6a2

Bạn Huy đang tập bắn cung để chuẩn bị cho thi olympic. Hôm đó, mẹ của Huy ghi ra thông tin gồm \(n\) dòng, dòng thứ \(i\) ghi \(2\) số, khoảng cách tới tâm và số điểm nhận được. Số điểm nhận được là số vòng tròn bao hàm nó nếu không tính nó nằm trong cạnh của vòng đó. Gọi \(r\) là chênh lệch bán kính của mỗi vòng tròn. Hãy tìm \(r\) với các thông tin mẹ Huy đã viết

Dữ liệu vào:

  • Dòng \(1\) gồm số \(n\). không quá \(10^5\)
  • \(n\) dòng tiếp theo, mỗi dòng gồm 2 số chỉ thông tin ở dòng đó (theo đề bài) không quá \(10^9\)

Kết quả:

  • Nếu không tìm được \(r\) hoặc thông tin bị lỗi, xuất ERROR, nếu không hãy xuất ra số \(r\) nhỏ nhất thỏa mãn.

Sample Input

3
9 0
10 0
11 1

Sample Output

10

Dãy số

tkluannguyendang

Đề bài: Cho dãy số \(1\), \(4\), \(9\), \(16\), \(25\), ... , \(n\). Nhập vào số tự nhiên \(n\). In \(n\) số hạng đầu tiên của dãy số trên.

Input:

  • Một số tự nhiên \(n\).

Output:

  • Kết quả của bài toán

Input:

5

Output:

1 4 9 16 25

Diện tích đa giác nhỏ nhất

jumptozero

Cho ba điểm \(A,B,C\) có toạ độ lần lượt là \((x_A,y_A),(x_B,y_B),(x_C,y_C)\) trên mặt phẳng toạ độ \(Oxy\). Hãy tìm đa giác đều có diện tích nhỏ nhất thoả mãn ba điểm \(A,B,C\) là ba đỉnh của đa giác đó.

Input:

  • Dòng thứ nhất chứa số \(t(1\le t\le 50)\) - Thể hiện số lượng testcase

  • \(t\) block tiếp theo, mỗi block có dạng như sau:

    • Dòng thứ nhất chứa hai số thực \(x_A,y_A (|x_A|,|y_A|\le 1000)\) và chúng không có quá \(6\) chữ số ở hàng thập phân

    • Dòng thứ hai chứa hai số thực \(x_B,y_B (|x_B|,|y_B|\le 1000)\) và chúng không có quá \(6\) chữ số ở hàng thập phân

    • Dòng thứ ba chứa hai số thực \(x_C,y_C (|x_C|,|y_C|\le 1000)\) và chúng không có quá \(6\) chữ số ở hàng thập phân

Output:

  • Ứng với mỗi testcase, in ra diện tích của đa giác cần tìm. (Biết rằng đáp án phải chính xác đến ít nhất \(6\) chữ số thập phân)

Ví dụ:

Input:

1
0.000000 0.000000
2.000000 2.000000
0.000000 2.000000

Output:

3.999999

Dời xâu

dang7rickroll

Cho xâu ký tự \(S\), số \(k\), và ký tự \(ch\) chỉ bao gồm \(2\) ký tự \(L\) và \(R\).

Có \(2\) trường hợp xảy ra:

  • Nếu \(ch = L\), chuyển \(k\) ký tự cuối xâu lên đầu xâu.

  • Nếu \(ch = R\), chuyển \(k\) ký tự đầu xâu xuống cuối xâu.

Ví dụ: \(S = abcdef\), \(k = 2\), \(ch = L\), thì xâu mới (gọi là xâu \(S1\)) nhận được là: \(efabcd\).

Tương tự, \(ch = R\) thì \(S1 = cdefab\).

Yêu cầu: Hãy in ra xâu \(S1\).

Dữ liệu:

  • Dòng đầu ghi xâu \(S\) là các ký tự bất kì trong bảng mã \(ASCII\). \((abs(s) \le 1000)\)

  • Dòng tiếp theo ghi số nguyên dương \(k\) \((1 \le k \le |S|)\).

  • Dòng cuối ghi ra ký tự \(ch\) là \(L\) hoặc \(R\).

Kết quả:

  • Kết quả của bài toán.

Example Input:

bangtaniesiloveyou
4
L

Example Output

eyoubangtaniesilov

Tiền tố và đối xứng

jumptozero

Cho một xâu \(S\) chỉ bao gồm các ký tự số và chữ cái Latin. Gọi \(A(S)\) là "mức độ xinh đẹp" của xâu \(S\), và nó được định nghĩa theo công thức truy hồi như sau:

  • \(A(S)=0\) nếu \(S\) là xâu không đối xứng hoặc là xâu rỗng

  • Gọi \(n\) là độ dài của xâu \(S\), khi đó ta có: \(A(S)=k\) nếu tiền tố và hậu tố có độ dài là \(\left \lfloor{\frac{n}{2}}\right \rfloor \) của \(S\) đều có "mức độ xinh đẹp" là \(k-1\)

Yêu cầu:

  • Cho xâu \(S\), hãy in ra tổng "mức độ xinh đẹp" của tất cả các tiền tố của xâu \(S\)

Input:

  • Dòng thứ nhất chứa số \(t(1\le t\le 50)\) - Thể hiện số lượng testcase

  • \(t\) dòng tiếp theo, mỗi dòng chứa \(t\) xâu \(S(0\le |S|\le 10^5)\)

Output:

  • Ứng với mỗi testcase, in ra đáp án cần tìm.

Ví dụ:

Input 1:

4
Qc93vcc11z
cSschccV2cccqZ
wccnq1c5gcqEK7mxc7cc
cccrc6cLCE

Output 1:

1
1
1
5

Input 2:

5
tccPcq2Acc7mcs
7czY5SG8cGMccvQSQFnc
cccczsb1kgcySZcccicc
bDFckccfcrc
cccuHHcccccGcc

Output 2:

1
1
8
6
6

Input 3:

2
abac
aa

Output 3:

3
3

Giải thích:

  • Xét testcase \(3\):

  • Đối với xâu \("abac"\), ta sẽ có các tiền tố sau: \("a","ab","aba","abac"\). và "mức độ xinh đẹp" của chúng tương ứng là: \(A("a")=1,A("ab")=0,A("aba")=2,A("abac")=0\). Do đó tổng "mức độ xinh đẹp" của xâu đã cho là: \(1+0+2+0=3\)

Salary Queries

hhoangcpascal

Một công ty có \(N\) nhân viên với với mức lương nhất định. Nhiệm vụ của bạn là theo dõi mức lương và thực hiện truy vấn.

Dữ liệu vào:

  • Dòng thứ nhất gồm hai số nguyên dương \(N, Q\) là số nhân viên và số truy vấn. Các nhân viên được đánh số từ \(1\) tới \(N\).
  • Dòng thứ hai gồm \(N\) số nguyên dương \(A_1, A_2, ..., A_N\) là lương của mỗi người.
  • \(Q\) dòng tiếp theo, mỗi dòng gồm một truy vấn thuộc một trong hai dạng sau:
    • \(!\) \(k\) \(x\): thay đổi lương của người thứ \(k\) thành \(x\).
    • \(?\) \(a\) \(b\): đếm số người có mức lương từ \(a\) tới \(b\).

Kết quả: In ra kết quả cho truy vấn \(?\).

Ràng buộc:

  • Subtask 1 \((30\%)\): \(N, Q \leq 2.10^3\), \(1 \leq A_i \leq 10^9\) với \(\forall i, 1 \leq i \leq N\).
  • Subtask 2 \((30\%)\): \(N, Q \leq 2.10^5\), \(1 \leq A_i \leq 10^5\) với \(\forall i, 1 \leq i \leq N\).
  • Subtask 3 \((40\%)\): \(N, Q \leq 2.10^5\), \(1 \leq A_i \leq 10^9\) với \(\forall i, 1 \leq i \leq N\).

Ví dụ:

Input:

5 3
3 7 2 2 5
? 2 3
! 3 6
? 2 3

Output:

3
2

Nguồn: CSES