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

Thiên An và Tuyết Ny cùng đi du ngoạn sơn thủy trên một chiếc du thuyền tự động. Chiếc du thuyền này sẽ đưa họ đi thăm mạng lưới sông ngòi của đất nước Byteland, gồm tổng cộng \(N\) bến cảng được đánh số từ \(1\) đến \(N\), mỗi bến cảng có đúng một "bến cảng bên trái" và đúng một "bến cảng bên phải". Du thuyền của An và Ny xuất phát ở thành phố \(1\). Sau khi ghé thăm mỗi bến cảng, chiếc du thuyền này sẽ tự động rẽ sang "bến cảng bên trái" hoặc "bến cảng bên phải" của bến cảng hiện tại. Cụ thể, người ta đã lập trình sẵn một dãy gồm \(M\) chỉ thị L hoặc R (tương ứng với đích đến tiếp theo là bến cảng trái hoặc phải) cho chiếc du thuyền, và nó sẽ tự động thực hiện lặp lại dãy \(M\) chỉ thị này đúng \(K\) lần.

Bạn hãy lập trình dự đoán bến cảng cuối cùng mà An và Ny cập bến nhé!

Lưu ý: "Trái" và "phải" được bỏ vào ngoặc kép vì chỉ mang tính quy ước: bến cảng \(a\) nằm bên trái bến cảng \(b\) thì không nhất thiết bến cảng \(b\) phải nằm bên phải bến cảng \(a\).

Input

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

• Dòng thứ \(i\) trong \(N\) dòng tiếp theo chứa hai số nguyên tương ứng thể hiện lần lượt số hiệu của bến cảng bên trái và bên phải của bến cảng \(i\).

• Dòng cuối cùng chứa \(M\) ký tự (cách nhau bởi khoảng trắng) thể hiện dãy chỉ thị mà chiếc du thuyền được lập trình.

Output

• Một số nguyên duy nhất là số hiệu của bến cảng cuối cùng trong hành trình của An và Ny.

Example

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

4

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