TKPC - Chuyên Hưng Yên vs liên quân Quảng - Đà

Khu du lịch Tam Chúc (Ba Sao Hà Nam) được mệnh danh là “Vịnh Hạ Long trên cạn”, nơi khoác lên mình vẻ đẹp ngút ngàn và đẹp như cõi mộng, nơi mà du khách sẽ cảm nhận được sự thuần khiết, thanh bình và yên ả. Quanh khu du lịch có rất nhiều địa điểm có thể khám phá như: Chùa Ngọc, Điện Tam Thế, Điện Pháp Chủ, Điện Quan Âm, Cổng Tam Quan, Phòng họp Quốc tế,… Giả sử có \(N\) điểm du lịch, tại một điểm bất kì có thể đi đến 2 địa điểm khác theo hướng trái L hoặc hướng phải R). Một tour du lịch cho khách sẽ xuất phát từ điểm 1, đi theo \(M\) chỉ dẫn chỉ gồm các ký tự L và R. Bé Bông lần đầu được đi du lịch ở Tam Chúc nên rất thích, mỗi tour du lịch bé muốn khám phá \(K\) lần. Vậy bạn hãy giúp mẹ bé tìm ra điểm dừng cuối cùng theo lộ trình bé Bông đã đi

Input

• Dòng đầu tiên ghi ba số nguyên dương \(N, M, K\) (\(N \le 10^3, M \le 5 \times 10^2, K \le 10^9\))
• \(N\) dòng tiếp theo, mỗi dòng ghi hai số nguyên là số hiệu của điểm tiếp theo nếu xuất phát từ điểm \(i\) đi theo hướng trái hoặc hướng phải.
• Dòng cuối cùng chứa \(M\) ký tự cách nhau bởi dấu trống chỉ gồm hai ký tự L và R là các chỉ dẫn của tour du lịch

Output

• Một số nguyên duy nhất là số hiệu của điểm dừng cuối cùng.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(K \le 10^2\).
• Subtask \(2\) (\(40\%\) số điểm): \(K \le 10^5\);
• Subtask \(3\) (\(40\%\) số điểm): \(K \le 10^9\).

Example

4 3 3
2 4
3 1
4 2
1 3
L L R

4

4 3 3
2 4
3 1
4 2
1 3
L R R

2

Buổi liên khối chuyên Tin của trường Nguyễn Bỉnh Khiêm diễn ra với sự tham gia của \(N\) học sinh. Cuối giờ, Oanh Trúc Béo ra hiệu cho các học sinh này xếp thành một hàng và đánh số họ từ \(1\) đến \(N\) tương ứng với vị trí đứng của họ trong hàng. Oanh Trúc muốn chụp một số tấm ảnh kỷ niệm cho buổi liên khối, mỗi tấm sẽ chụp lại một đoạn liên tiếp các bạn trong hàng. Vì là một sự kiện trong đại nên Trúc muốn mỗi bạn học sinh tham dự đều có mặt trong ít nhất một tấm ảnh.

Tuy nhiên, trong \(N\) học sinh này có tồn tại \(K\) đôi bạn xung khắc nhau (đã từng là bạn thân nhưng hiện tại tình nghĩa đã vô cùng rạn nứt vì crush chung một em gái nào đó), các đôi bạn xung khắc này đều không muốn đứng chung với nhau trong một tấm ảnh. Bộ nhớ của điện thoại Oanh Trúc không còn nhiều nên cô ấy đã nhờ bạn lập trình tính toán số tấm ảnh ít nhất cần chụp để thỏa mãn tất cả các ràng buộc trên.

Input

• Dòng đầu chứa hai số nguyên dương \(N\) và \(K\) (\(2\leq N\leq 10^9\), \(2\leq K\leq 1000\)).

• Dòng thứ \(i\) trong \(K\) dòng tiếp theo chứa hai số nguyên dương phân biệt \(A_i\) và \(B_i\) thể hiện một đôi bạn xung khắc \(\left(A_i, B_i\right)\) - họ không thể cùng đứng chung trong một tấm ảnh.

Output

• Một số nguyên duy nhất là số tấm ảnh ít nhất mà Oanh Trúc Béo cần chụp.

Example

7 3
1 3
2 4
5 6

3

Ta có thể chia một đa giác đều \(P\) gồm \(n\) cạnh thành tối đa \(n-2\) tam giác bằng cách nối một số đường chéo không giao nhau của \(P\). Ví dụ, một hình vuông có thể được chia thành hai hình tam giác và một hình ngũ giác đều có thể được chia thành ba hình tam giác. Ta gọi mỗi cách chia này là một cách tam giác phân của \(P\). Nếu \(n > 3\) thì \(P\) sẽ tồn tại ít nhất hai cách tam giác phân.

Ta định nghĩa khoảng cách giữa hai tam giác trong một cách tam giác phân của \(P\) chính là số cạnh mà ta phải băng qua để từ tam giác này đến được tam giác kia (không được đi ra khỏi \(P\)). Ví dụ, khoảng cách giữa tam giác \(a\) và tam giác \(d\) trong cách tam giác phân ở hình dưới là \(3\).

Ta tiếp tục quy ước đường kính của một cách tam giác phân của \(P\) chính là khoảng cách giữa hai tam giác xa nhất trong \(P\) theo cách tam giác phân đó. Cho biết \(n\) là số lượng cạnh của đa giác đều \(P\), bạn hãy lập trình tính toán đường kính nhỏ nhất có thể trong số các cách tam giác phân của \(P\) nhé!

Input

• Số nguyên dương \(n\) (\(3\leq n\leq 10^6\)).

Output

• Một số nguyên là đường kính nhỏ nhất tìm được.

Example

3

0

4

1

6

2

Cho \(n\) đoạn thẳng trên trục Ox, đoạn thứ \(i\) (ký hiệu là \(T_i\)) bắt đầu tại điểm \(x_i\) và có độ dài \(l_i\). Ở mỗi đoạn ta cần chọn ra một điểm đại diện của đoạn đó. Biết rằng không có hai đoạn nào hoàn toàn chứa nhau (nói cách khác, không tồn tại \(i\) và \(j\) khác nhau sau cho \(x_j\leq x_i\) và \(x_i+l_i\leq x_j+l_j\)), bạn hãy lập trình xác định một cách chọn \(n\) điểm đại diện sao cho khoảng cách giữa hai điểm gần nhất là lớn nhất có thể.

Ví dụ, hai hình dưới đây thể hiện hai cách chọn điểm đại diện cho \(6\) đoạn thẳng (điểm đại diện được tô đậm màu đen ở mỗi đoạn màu đỏ). Ở cách chọn đầu tiên, hai điểm gần nhất cách nhau \(20\) đơn vị độ dài. Ở cách chọn thứ nhì, hai điểm gần nhất cách nhau \(25\) đơn vị độ dài.

Input

• Dòng đầu tiên chứa số nguyên dương \(n\) (\(2\leq n\leq 10^5\)).

• Dòng thứ \(i\) trong \(n\) dòng tiếp theo chứa hai số nguyên \(x_i\) và \(l_i\) (\(0\leq x_i\leq 10^9\), \(1\leq l_i\leq 10^9\)).

Example

6
0 67
127 36
110 23
50 51
100 12
158 17

25

6
0 40
10 55
45 28
90 40
83 30
120 30

30

3
0 20
40 10
100 20

50

CaiWinDao có \(n\) em gái. Một hôm, CaiWinDao triệu tập \(n\) em gái này lại và cho xếp thành một hàng dọc. Sau đó, anh ấy bắt đầu đi từ đầu hàng đến cuối hàng, phát \(1\) cây kẹo cho em gái đầu tiên, \(2\) cây kẹo cho em gái thứ nhì, \(3\) cây kẹo cho em gái thứ ba, và cứ thế. Bạn hãy lập trình tính toán số kẹo CaiWinDao cần có để phát đến cuối hàng nhé!

Input

• Một số nguyên dương \(n\) (\(1\leq n\leq 100\)).

Output

• Số lượng kẹo CaiWinDao cần có để phát đủ cho \(n\) em gái.

Example

3

6

10

55

Định có một dãy số \(N\) nguyên \(a_1\), \(a_2\),..., \(a_N\). Định muốn biến đổi để tất cả các phần tử trong dãy trở thành các số nguyên bằng nhau. Chi phí để biến đổi phần tử \(a_i\) thành giá trị \(x\) là \((a_i-x)^2\). Bạn hãy lập trình xác định chi phí nhỏ nhất để Định đạt được mục tiêu nhé!

Input

• Dòng đầu tiên chứa số nguyên dương \(N\) (\(1\leq N\leq 100\)).
• Dòng tiếp theo chứa \(N\) số nguyên \(a_1\), \(a_2\),..., \(a_N\) (\(-100\leq a_i\leq 100\)).

Output

• Một số nguyên là chi phí nhỏ nhất tìm được.

Example

2
4 8

8

3
1 1 3

3

Cho dãy số nguyên \(a_1\), \(a_2\),..., \(a_N\). Ở mỗi thao tác ta có thể chọn một phần tử nguyên dương trong dãy và giảm nó xuống \(1\) đơn vị. Hãy lập trình tính số thao tác tối thiểu cần thực hiện để mọi cặp phần tử liên tiếp trong dãy đều có tổng không vượt quá giá trị \(X\).

Input

• Dòng đầu chứa hai số nguyên \(N\) và \(X\) (\(2\leq N\leq 10^5\), \(0\leq X\leq 10^9\)).

• Dòng tiếp theo chứa \(N\) số nguyên \(a_1\), \(a_2\),..., \(a_N\) (\(0\leq a_i\leq 10^9\)).

Output

• Một số nguyên là số thao tác ít nhất cần thực hiện.

Example

3 3
2 2 2

1

6 1
1 6 1 2 0 4

11

5 9
3 1 4 1 5

0