PVHOI 2.0 - Bài 5: Vẽ cây

skyvn97

Rảnh rỗi vì không có ngiu, GS. PVH lấy giấy ra vẽ cây. GSPVH đã vẽ được một cây gồm \(n\) đỉnh và đánh số các đỉnh từ \(1\) đến \(n\).

Nhắc lại, cây là đồ thị vô hướng phi chu trình. Một cây gồm \(n\) đỉnh chắc chắn có \(n - 1\) cạnh.

Sau khi vẽ xong, GS. PVH chọn ra \(k\) đỉnh phân biệt trên cây và tô các đỉnh này bằng màu xanh lá cây. Tiếp theo đó, GS lại tiếp tục tô màu vàng vào những đỉnh mà GS coi là "xung yếu". Một đỉnh được GS coi là "xung yếu" khi và chỉ khi đỉnh này không được tô màu xanh lá cây; và nếu xóa đỉnh này ra khỏi cây, sẽ có hai đỉnh nào đó vừa được tô màu xanh lá cây không thể đi tới nhau nữa.

Tô màu đủ kiểu rồi, vẫn thấy mình còn dư quá nhiều thời gian, GS. PVH quyết định vẽ một bức tranh "siêu to khổng lồ to nhất Việt Nam" bằng việc liệt kê tất cả các cách chọn ra \(k\) đỉnh trong số \(n\) đỉnh của cây. Sau đó, với mỗi cách chọn, GS lại vẽ ra một cây và tô hai màu xanh lá cây và vàng vào các đỉnh theo quy tắc ở trên.

Thế nhưng, GS sắp hết bút sáp màu vàng. Vì vậy, GS. muốn nhờ bạn tính tổng số đỉnh được tô màu vàng trong bức tranh siêu to khổng lồ của mình.

Để làm khó bạn hơn, GS cho bạn trước một con số \(p\) và yêu cầu bạn phải tính ra kết quả theo modulo \(p\). Các bạn hãy chiều GS nhé.

Input

Dòng đầu tiên chứa ba số nguyên \(n\), \(k\) và \(p\) \((1 \leq k \leq n \leq 10^6, p \in \{10^9 + 19972207, 10^9 + 22071997\})\), lần lượt là số đỉnh trên cây, số đỉnh được GS. PVH lựa chọn để tô màu xanh lục và số \(p\) được nhắc đến trong đề bài.

Trong \(n - 1\) dòng còn lại, mỗi dòng chứa hai số nguyên \(u\) và \(v\) \((1 \leq u, v \leq n)\) cho biết trên cây có một cạnh nối hai đỉnh \(u\) và \(v\).

Output

In ra tổng số đỉnh màu vàng trong bức tranh của GS. PVH.

Subtasks

Bộ test của bài được chia làm các subtask như sau:

  • Subtask \(1\) (\(12.6\) điểm): \(n \leq 20\)
  • Subtask \(2\) (\(8.4\) điểm): \(n \leq 5000\)
  • Subtask \(3\) (\(7\) điểm): \(k = 1\)
  • Subtask \(4\) (\(12.6\) điểm): \(k = 2\)
  • Subtask \(5\) (\(11.2\) điểm): \(p = 10^9 + 19972207\)
  • Subtask \(6\) (\(18.2\) điểm): Không có ràng buộc gì thêm.

Điểm tối đa của bài là \(70\) điểm.

Ví dụ

Input

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

Output

16

Giải thích

Dưới đây là bức tranh siêu to khổng lồ to nhất Việt Nam do GS. PVH vẽ trong ví dụ ở trên. Có tất cả \(20\) cách chọn ra \(k = 3\) đỉnh trong một cây gồm \(n = 6\) đỉnh. Tổng số đỉnh được tô màu vàng trong các cách này là.

Phần 1: https://drive.google.com/file/d/1OrUsJqXopX3uGIqdz1MUAKDPg-b5rZhx/view?usp=sharing

Phần 2: https://drive.google.com/file/d/1uRvPyI3uTY-GKU5NVIfBbzn_y3-SP1rX/view?usp=sharing

Trò chơi trên dãy số (DHBB CT '19)

admin

Long và Vân cùng nhau chơi trò chơi trên dãy số như sau: Long sẽ chọn một dãy gồm \(𝑛\) số \(𝑎_1, 𝑎_2, … , 𝑎_𝑛\). Sau đó, Vân sẽ tìm cách biến đổi dãy số nguyên \(𝑎_1, 𝑎_2, … , 𝑎_𝑛\) về dãy đẹp bậc \(𝑑\) bằng dãy các bước biến đổi như sau: Mỗi bước, chọn một số trong dãy, tăng hoặc giảm số đó đi một đơn vị. Một dãy \(𝑏_1, 𝑏_2, … , 𝑏_𝑛\) được gọi là dãy đẹp bậc \(𝑑\) nếu \(𝑏_𝑖 = 𝑏_{𝑖−1} + 𝑑\) với \(𝑖 = 2, 3, … , 𝑛\). Cụ thể, dãy \(𝑏_1, 𝑏_2 = 𝑏_1 + 𝑑, … , 𝑏_𝑛 = 𝑏_{𝑛−1} + 𝑑\) là dãy đẹp bậc \(𝑑\).

Ví dụ, dãy (\(3, 2, 2\)) với \(𝑑 = 1\) mất ít nhất \(3\) phép biến đổi để đưa về dãy (\(1, 2, 3\)) là một dãy đẹp bậc \(1\).

Yêu cầu: Cho dãy số nguyên \(𝑎_1, 𝑎_2, … 𝑎_𝑛\) và số nguyên dương \(𝑑\), hãy tính số bước ít nhất cần dùng để biến đổi dãy \(𝑎_1, 𝑎_2, … , 𝑎_𝑛\) thành một dãy đẹp bậc \(𝑑\).

Dữ liệu vào

  • Dòng đầu chứa số nguyên \(𝑛\) (\(𝑛 ≤ 1000\)) và \(𝑑\);
  • Dòng thứ hai chứa \(𝑛\) số nguyên mô tả dãy \(𝑎_1, 𝑎_2, … , 𝑎_𝑛\).

Kết quả

  • Một dòng, chứa một số nguyên là số bước ít nhất cần dùng để biến đổi dãy \(𝑎_1, 𝑎_2, … , 𝑎_𝑛\) thành một dãy đẹp bậc \(𝑑\).

Sample Input

3 1 
3 2 2

Sample Output

3

Ràng buộc:

  • Có 25% số test ứng với 25% số điểm của bài có \(𝑑 = 0\) và \(|𝑎_𝑖| ≤ 10^3\);
  • Có 25% số test khác ứng với 25% số điểm của bài có \(𝑑 = 0\) và \(|𝑎_𝑖| ≤ 10^9\);
  • Có 25% số test khác ứng với 25% số điểm của bài có \(𝑑 = 1\) và \(|𝑎_𝑖| ≤ 10^3\);
  • Có 25% số test còn lại ứng với 25% số điểm còn lại của bài có \(𝑑 ≤ 10^9\) và \(|𝑎_𝑖| ≤ 10^9\).

Nguồn: 2019 chính thức

Đường đi trên bảng

CaiWinDao

dungde99 vừa vẽ ra một bảng số nguyên dương gồm \(M\) hàng và \(N\) cột, các hàng được đánh số từ \(1\) đến \(M\) từ trên xuống và các cột được đánh số từ \(1\) đến \(N\) từ trái sang phải. dungde99 ký hiệu ô \((i, j)\) là ô nằm ở giao điểm của hàng \(i\) và cột \(j\) của bảng. Sau đó, dungde99 đưa ra bộ bốn số \(x_1\), \(y_1\), \(x_2\) và \(y_2\) rồi đố Flow God tìm một đường đi tối ưu từ ô \(\left(x_1, y_1\right)\) đến ô \(\left(x_2, y_2\right)\), tức là một đường đi xuất phát tại ô \(\left(x_1, y_1\right)\) mà tại mỗi bước Flow God chỉ có thể di chuyển sang ô kề bên phải hoặc ô kề bên dưới của ô hiện tại, đồng thời tổng các số ghi ở các ô trên đường đi (bao gồm cả ô \(\left(x_2, y_2\right)\)) phải nhỏ nhất có thể. Flow God nhanh chóng trả lời được câu đố đầu tiên của dungde99 nhưng sau đó dungde99 lại hỏi tiếp hàng loạt câu hỏi dạng tương tự như vậy khiến Flow God phải bó tay trong sự lúng túng. Các bạn hãy giúp Flow God giải đáp tất cả các câu đố này nhé!


Input

Dòng đầu chứa hai số nguyên dương \(M\) và \(N\) \((1\leq M, N\leq 100)\).

\(M\) dòng sau, mỗi dòng chứa \(N\) số nguyên dương mô tả một hàng ngang của bảng. Các số này có giá trị không vượt quá \(10^6\).

Dòng tiếp theo chứa số nguyên dương \(Q\).

\(Q\) dòng sau, mỗi dòng chứa bốn số nguyên dương \(x_1\), \(y_1\), \(x_2\) và \(y_2\) mô tả một truy vấn đường đi tối ưu từ ô \(\left(x_1, y_1\right)\) đến ô \(\left(x_2, y_2\right)\) trong bảng \(\left(1\leq x_1\leq x_2\leq M, 1\leq y_1\leq y_2\leq N\right)\).


Output

Gồm \(Q\) dòng, mỗi dòng chứa một số nguyên là tổng các số trên đường đi tối ưu tương ứng.


Ví dụ

Input
4 5
1 2 3 4 5
5 4 3 2 1
2 4 6 8 10
11 9 5 3 7
2
1 1 3 3
1 2 4 5
Output
14
26

Ràng buộc

  • Subtask 1 (30 điểm): \(Q\leq 10^6\) và tất cả các số ghi trong bảng đều bằng \(1\).
  • Subtask 2 (30 điểm): \(Q\leq 10^4\).
  • Subtask 3 (40 điểm): \(Q\leq 10^6\).

Xâu nguyên tố

An09855, dang7rickroll

Xâu \(S\) này được gọi là xâu nguyên tố nếu số lượng kí tự chỉ xuất hiện đúng 1 lần trong xâu \(S\) là số nguyên tố.

Yêu cầu:

Bạn được cho xâu \(S\) chỉ bao gồm các ký tự thường trong bảng chữ cái \(ABC\). Vậy hãy kiểm tra xem xâu \(S\) có phải là xâu nguyên tố hay không?

Dữ liệu:

  • Dòng đầu ghi số \(q (q≤100)\), là số câu hỏi.

\(q\) dòng tiếp theo, mỗi dòng ghi ra xâu \(S\) (độ dài xâu \(S\) không quá \(1000\)).

Kết quả:

  • Gồm \(q\) dòng, mỗi dòng ghi ra kết quả tương ứng của mỗi câu hỏi.

Sample Input


4
lcgfwrkvudgzzckaadeg
flildnmjaxhfpwjuiowd
truirounxoarzmeriwyt
ipoqfcmgdadtlajeecni

Sample Output

YES
NO
NO
NO

Đếm nguyên âm

tkluannguyendang

Đề bài: Trong thời gian nghỉ dịch thì Minh đã quên hết các nguyên âm là gì và đã quyết định học lại. Vì không có tài liệu nên cậu quyết định học bằng cách lập trình để hiểu rõ (Các nguyên âm là: \(a,e,i,o,u\)). Nhưng vì Minh mới học code nên chưa làm được, các bạn coder hãy giúp cậu ấy nhé :D

Input:

  • Nhập vào số tự nhiên \(n\).
  • \(n\) dòng sau là một xâu kí tự \(s\). Đếm số nguyên âm có trong các xâu \(s\) đó.

Output:

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

Input:

2
Hello
Bonjour

Output:

2 3

Dãy Cuốm

ami

Anh Kha và cuom1999 là một cặp huynh đệ đồng môn dưới sự chỉ dạy của sư phự ami ở bộ môn Liên Minh of Legend. Anh Kha đã lĩnh hội thành công phương thức gánh team bằng giao thức Apeliot. cuom1999 rất ghen tị. Sau một trận đấu có KDA 1/9/2, cuom1999 quyết định nhờ Anh Kha chỉ dạy bí thuật Apeliot cho mình.

Anh Kha là một thiếu niên nghiêm túc và đầy lòng trắc ẩn. Cậu nhận thấy rằng nếu chỉ đơn giản đưa bí kíp cho cuom1999, cuom1999 sẽ không thể nhớ được. Vì vậy, mỗi lần truyền thụ một bí kíp, Anh Kha sẽ đưa cho cuom1999 một xâu kí tự \(S\) chỉ chứa các kí tự trong tập {c , u , o , m , g , a , v , l}, cuom1999 sẽ thêm một kí tự cũng thuộc tập trên vào một vị trí bất kì trong xâu \(S\) sao cho số lượng xâu kí tự \(cu\) xuất hiện trong xâu \(S\) sau khi thêm là nhiều nhất. Số lượng kí tự \(cu\) này chính là khẩu quyết mà Anh Kha muốn truyền đạt.

Xâu \(cu\) được gọi là xuất hiện trong xâu \(S\) nếu sau khi xoá đi một vài hoặc không kí tự trong xâu \(S\) và ghép các kí tự còn lại theo đúng thứ tự tương đối của nó, ta thu được xâu \(cu\).

Ví dụ, xâu \(cu\) xuất hiện trong xâu \(cạcu\) nhưng không xuất hiện trong xâu \(amivippro\)

Input

Dòng đầu tiên chứa \(N\) là độ dài xâu \(S\).

Dòng thứ hai chứa \(N\) kí tự thuộc xâu \(S\).

Output

Hãy in ra số lần xuất hiện nhiều nhất có thể của xâu \(cu\) sau khi thêm một kí tự bất kì vào xâu \(S\).

Sample Input 1

8
cuomgavl

Sample Output 1

2

Sample Input 2

6
cumcal

Sample Output 1

3

Giới hạn

\(30\)% số điểm có \(n \leq 1000\).

\(30\)% số điểm có \(n \leq 5000\)

\(40\)% số điểm có \(n \leq 10^6\)

Giải thích

Ở test ví dụ 1, có thể thêm kí tự u vào sau chữ \(m\) để thu được xâu \(cuomugavl\). Xâu \(cu\) xuất hiện 2 lần.

Ở test ví dụ 2, có thể thêm kí tự u vào sau chữ \(a\) để thu được xâu \(cucaul\). Xâu \(cu\) xuất hiện 3 lần.

Tính tổng

admin, daicadihoc

Viết chương trình tính tổng các số nguyên được nhập từ bàn phím cho đến khi nhập số 0 thì dừng.

Input:

  • Nhập các số nguyên.

Output:

  • Tổng các số vừa nhập

Ví dụ

Input

7 3 2 4 0

Output

16

Giả thuyết Goldbach

Small

Giả thuyết Goldbach do nhà toán học người Đức Christian Goldbach (1690-1764) nêu ra vào năm 1742 trong một lá thư gửi tới Leonhard Euler, là một trong những bài toán lâu đời và nổi tiếng còn chưa giải được trong lý thuyết số nói riêng và toán học nói chung. Giả thuyết phỏng đoán rằng: Mọi số tự nhiên chẵn lớn hơn 2 có thể biểu diễn bằng tổng của hai số nguyên tố. Trong bài toán này bạn được cho một số tự nhiên chẵn \(𝑛\), bạn hãy đếm số lượng cặp số nguyên tố \(𝑎, 𝑏\ (𝑎 ≤ 𝑏)\) mà \(𝑎 + 𝑏 = 𝑛\).

Dữ liệu • Gồm một dòng chứa một số tự nhiên chẵn \(𝑛\).

Kết quả • Gồm dòng chứa một số là số lượng cặp số nguyên tố \(𝑎, 𝑏\) mà \(𝑎 ≤ 𝑏\) và \(𝑎 + 𝑏 =n\)

Sample input

10

Sample output

2

Ràng buộc

  • Có 50% test ứng với 50% số điểm có \(𝑛 ≤ 10^3\);
  • Có 50% test còn lại ứng với 50% số điểm có \(𝑛 ≤ 10^6\)

Số đường đi

Small

Cho lưới ô vuông kích thước \(n× m\), ô (\(1, 1\)) ở góc dưới trái, ô (\(n,m\)) – trên phải. Có \(k\) ô chứa chướng ngại vật, ô thứ \(i\) ở tọa độ (\(x_i, y_i\)), \(1 ≤ x_i ≤ n, 1 ≤ y_i ≤ m, i = 1 ÷ k\), Không có chướng ngại vật ở ô (\(1, 1\)) và (\(n, m\)).

Rô bốt xuất phát từ ô (\(1, 1\)), ở mỗi bước được chuyển sang ô kề cạnh bên phải hoặc bên trên nếu ô tới không chứa chướng ngại vật.

Hãy xác định số lượng đường rô bốt có thể đi từ ô (\(1, 1\)) đến ô (\(n, m\)) và đưa ra số lượng theo mô đun \(p\), trong đó \(p\) – số nguyên tố.

Dữ liệu

  • Dòng đầu tiên chứa 4 số nguyên \(n, m, k, p\) (\(1 ≤ n, m ≤ 10^5, 0 ≤ k ≤ 100,2 \times max{m,n} < p < 2 × 10^9\)),
  • Nếu \(k > 0\), dòng thứ \(i\) trong \(k\) dòng tiếp theo chứa 2 số nguyên \(x_i, y_i\) (\(1 ≤ x_i ≤ n, 1 ≤ y_i ≤ m\)).

Kết quả

  • Đưa ra một số nguyên không âm – số lượng đường tìm được theo mô đun \(p\).

Sample input

5 6 3 101
2 2
3 5
4 2

Sample output

25

Nguồn: Thầy Tùng

Đếm tập con chẵn

cuom1999

Cho dãy số \(a_1, a_2, …, a_n\) và \(q\) thao tác thuộc 1 trong 2 loại sau:

1 k b: gán \(a_k=b\)

2 l r: Tính số lương tập con \(\{k_1, k_2, ..., k_m\}\) khác rỗng của tập \(\{l,l+1,…,r\}\) sao cho \(a_{k_1} + a_{k_2} + ... + a_{k_m}\) là số chẵn.

Yêu cầu: Với thao tác loại 2, hãy in ra số dư của kết quả khi chia cho \(10^9+7\).

Dữ liệu

  • Dòng đầu chứa 2 số nguyên \(n,q\).
  • Dòng tiếp theo chứa \(n\) số \(a_1,a_2,…,a_n (1\leq a_i \leq 10^9)\).

  • \(q\) dòng tiếp theo mỗi dòng chứa một trong hai loại thao tác :

    • 1 k b \((1 \leq k \leq n; 1 \leq b \leq 10^9)\)
    • 2 l r \((1\leq l \leq r \leq n)\)

Kết quả: Với mỗi thao tác loại 2, in ra số lượng tập con thỏa mãn \((mod \ 10^9+7)\) trên một dòng.

Ví dụ

Input

5 6
2 4 6 8 10
2 1 3
2 4 4
2 4 5
1 4 7
2 4 4
2 4 5

Output

7
1
3
0
1

Giới hạn:

  • 20% số test có \(n,q \leq 20\).
  • 20% số test có \(n,q \leq 5000\).
  • 20% số test có \(n \leq 10^5, q \leq 100\).
  • 40% số test có \(n,q \leq 10^5\).

Cửa hàng bán hoa

Small

SK mở hai cửa hàng bán hoa và nhập hoa từ \(N\) vườn. Mỗi vườn có \(A_i\) bông hoa với tổng giá trị là \(C_i\). SK sẽ mua hết số hoa trong \(N\) vườn và đưa đến hai cửa hàng của mình. Hoa của một vườn chỉ có thể đưa đến một cửa hàng duy nhất.

Với giá hoa trung bình tại cửa hàng 1 là \(P_1\), giá hoa trung bình tại cửa hàng hai là \(P_2\) và giá hoa trung bình trong mỗi cửa hàng được tính bằng tổng giá trị hoa chia cho số bông hoa có trong cửa hàng đó, SK muốn phân chia hoa về các cửa hàng sao cho tích \(P_1 \times P_2\) là nhỏ nhất có thể.

Yêu cầu: Giúp SK phân chia hoa về hai cửa hàng sao cho \(P_1 \times P_2\) là nhỏ nhất có thể, với chú ý sau khi phân chia hoa về các cửa hàng thì phải có ít nhất một cửa hàng nhận hoa từ \(L\) vườn.

Dữ liệu

  • Dòng 1 gồm hai số nguyên \(N\) và \(L\) (\(2 ≤ N ≤ 100,1 ≤ L < N\)) – số bông hoa và số hoa trong ít nhất một cửa hàng.
  • Dòng 2 gồm \(N\) số nguyên \(A_i (1 ≤ A_i ≤ 100)\), tổng các số nguyên \(A_i ≤ 500\).
  • Dòng 3 gồm \(N\) số nguyên \(C_i (1 ≤ C_i ≤ 1000000)\).

Các số trên một dòng của input file được ghi cách nhau bởi dấu cách.

Kết quả

  • Ghi ra một số thực duy nhất là tích \(P_1 \times P_2\) nhỏ nhất có thể (làm tròn tới ba chữ số phần thập phân).

Input

3 1
3 2 1
1 2 3

Output

0.556

Input

3 2
2 2 2
3 3 3

Output

2.250

Ràng buộc: 30% số điểm tương ứng với 30% số test có N≤20.


Nguồn: DHBB 2017 (HP)

Chia kẹo 01

admin

Sau khi vượt qua một bài kiểm tra, Vasya được nhận một hộp gồm \(n\) cây kẹo. Anh quyết định ăn một lượng kẹo bằng nhau mỗi sáng cho đến khi không còn cây kẹo nào trong hộp nữa. Tuy nhiên, Petya đã phát hiện thấy chiếc hộp và quyết định "chôm" một ít kẹo cho mình.

Quá trình ăn kẹo là như sau: ban đầu Vasya chọn một số nguyên duy nhất là \(k\), bằng nhau đối với tất cả các ngày. Sau đó, vào buổi sáng anh ấy ăn \(k\) cái kẹo từ chiếc hộp (nếu còn ít hơn k cái kẹo trong hộp, anh ấy ăn tất cả chúng), sau đó vào buổi tối Petya ăn \(10\%\) số kẹo còn lại trong hộp. Nếu vẫn còn kẹo trong hộp, quá trình này được lặp lại - ngày hôm sau Vasya ăn \(k\) kẹo một lần nữa, và Petya ăn \(10\%\) kẹo còn lại trong một hộp và cứ như vậy... Nếu số lượng kẹo trong hộp không chia hết cho \(10\), Petya làm tròn xuống theo số lượng anh ta lấy từ hộp. Ví dụ, nếu có \(97\) Kẹo trong hộp, Petya sẽ chỉ ăn 9 trong số chúng. Đặc biệt, nếu có ít hơn \(10\) cái kẹo trong hộp, Petya sẽ không ăn chút nào.

Nhiệm vụ của bạn là tìm ra số lượng tối thiểu \(k\) mà Vasya có thể chọn để anh ta ăn ít nhất một nửa trong \(n\) cái kẹo anh ban đầu có trong hộp. Lưu ý rằng số \(k\) phải là số nguyên.

Dữ liệu vào

  • Dòng đầu tiên chứa một số nguyên duy nhất \(n\) (\(1 ≤ n ≤ 10^{18}\)) là số lượng kẹo ban đầu trong hộp.

Kết quả

  • Xuất ra một số nguyên duy nhất là số lượng tối thiểu \(k\) điều đó sẽ cho phép Vasya ăn ít nhất một nửa số kẹo mà anh ta có.

Sample Input

68

Sample Output

3

Giải thích: Trong ví dụ, lượng kẹo với k = 3, sẽ thay đổi theo cách sau (Vasya ăn trước) \(68 → 65 → 59 → 56 → 51 → 48 → 44 → 41 → 37 → 34 → 31 → 28\) \( → 26 → 23 → 21 → 18 → 17 → 14 → 13 → 10 → 9 → 6 → 6 → 3 → 3 → 0\).

Tổng cộng, Vasya sẽ ăn 39 viên kẹo, trong khi Petya ăn 29.

Ràng buộc:

  • Có 70% số điểm thỏa mãn điều kiện: \(n ≤ 10^6\).
  • 30% số điểm còn lại thỏa mãn điều kiện \(n ≤ 10^{18}\)

Nguồn: 2019 CLC

Los Santos Vagos

hhoangcpascal

Nhóm của CJ - tức là nhóm Grove Street Families và nhóm Los Santos Vagos trước giờ là kẻ thù của nhau, và bây giờ vẫn vậy. Và giờ nhóm Los Santos Vagos sẽ cố để chiếm lấy vùng của Grove Street Families mà trước đó CJ đã tịch thu từ Ballas. CJ thì đang tìm khu vực trọng điểm trong vùng để tập trung lực lượng chống trả nhóm Los Santos Vogas.

Trên bản đồ vùng của Grove Street Families có \(N\) điểm căn cứ, các căn cứ được đánh số theo thứ tự từ \(1\) tới \(N\), và \(M\) tuyến đường một chiều nối trực tiếp giữa hai căn cứ. Khu vực trọng điểm là khu có nhiều căn cứ nhất, sao cho bất kỳ hai căn cứ nào cũng có thể đi đến để yểm trợ cho nhau. Định nghĩa căn cứ \(u\) có thể đi tới căn cứ \(v\) là tồn tại một đường đi từ \(u\) tới \(v\), tức là tồn tại dãy các căn cứ \(P=⟨u=p_0,p_1,...,p_k=v⟩\) sao cho \(∀i:1 \leq i \leq k\) thì tồn tại tuyến đường trực tiếp từ căn tứ \(p_{i-1}\) tới căn cứ \(p_i\).

Yêu cầu: Hãy tìm cho CJ khu vực trọng điểm trên. Nếu có nhiều khu vực trọng điểm như vậy, chỉ ra một khu vực bất kì.

Dữ liệu vào: Gồm \(M + 1\) dòng:

  • Dòng đầu tiên chứa hai số nguyên dương \(N\), \(M\) thể hiện số căn cứ và số con đường một chiều.
  • \(M\) dòng tiếp theo, dòng thứ \(i\) chứa hai số \(u_i\) và \(v_i\) thể hiện có đường một chiều nối từ căn cứ \(u_i\) tới căn cứ \(v_i\).

Kết quả: Ghi ra hai dòng:

  • Dòng đầu tiên ghi số \(K\) là số căn cứ lớn nhất trong khu vực trọng điểm tìm được
  • Dòng tiếp theo là ghi ra số hiệu của \(K\) căn cứ trong khu vực trọng điểm theo thứ tự tăng dần.

Ví dụ

Input:

11 15
1 2
1 8
2 3
3 4
4 2
4 5
5 6
6 7
7 5
8 9
9 4
9 10
10 8
10 11
11 8

Output:

4
8 9 10 11

Giới hạn:

  • \(30\)% số test đầu tiên có \(N \leq 10^3, M \leq 2.10^3\)
  • \(70\)% số test còn lại có \(N \leq 10^5, M \leq 2.10^5\)

Cánh diều - NAMNHUAN - Kiểm tra năm nhuận (T76)

DKingQA, Flower_On_Stone, habelle

Năm nhuận là những năm chia hết cho \(400\) hoặc là những năm chia hết cho \(4\) mà không chia hết cho \(100\). Nhập vào một số nguyên dương \(n\), hãy đưa thông báo "Khong la nam nhuan" nếu năm \(n\) không phải năm nhuận; "Nam nhuan" nếu \(n\) là năm nhuận.

Input:

Một số nguyên \(n\) \((1<=n<=10^6)\).

Output:

In ra kết quả.

Ví dụ:

Sample Input

2000

Sample Output

Nam nhuan

Yero binary number

phanhuykhang

Hệ nhị phân là một hệ đếm, dùng hai ký tự để biểu đạt một số. Hai ký tự đó là \(0\) và \(1\). Một số nguyên được gọi là Yero binary number nếu như biểu diễn nhị phân của nó chỉ chứa một số \(0\). Ví dụ, \(11\) là một Yero binary number, còn \(4\) và \(7\) thì không phải. Bạn được cho một số nguyên dương N, hãy đếm xem trong khoảng từ 1...N có bao nhiêu Yero binary number.

Input:

  • Dòng thứ nhất chứa số \(T(1 ≤ T ≤ 100)\) - Thể hiện số lượng test case.
  • \(T\) dòng tiếp theo, mỗi dòng chứa số nguyên \(n (1 <= n <= 10 ^ {18})\).

Output:

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

Example Input

2
5
11

Example Output

2
4

Công việc (OLP MT&TN 2021 CT)

Small

Cho \(n\) công việc và mối quan hệ xử lí trước sau được mô tả bằng một cây. Mỗi nút tương ứng với một công việc và phải thực hiện trong một đơn vị thời gian. Các công việc tương ứng với nút lá cần được thực hiện trước công việc tương ứng với nút cha. Có m máy, mỗi máy trong một đơn vị thời gian chỉ xử lí liên tục được một công việc.

Yêu cầu: Xếp lịch để thời gian hoàn thành là sớm nhất.

Dữ liệu: Vào từ thiết bị vào chuẩn có khuôn dạng:

  • Dòng đầu chứa hai số \(n, m\);
  • Tiếp theo là \(n-1\) dòng, mỗi dòng mô tả một cạnh của cây.

Kết quả: Ghi ra thiết bị ra chuẩn một số nguyên là thời gian nhỏ nhất cần để thực hiện.

Ràng buộc:

  • Có 40% số test ứng với 40% số điểm của bài thỏa mãn: \(n≤ 3000\);
  • 60% số test còn lại ứng với 60% số điểm của bài thỏa mãn: \(n≤ 300000\).

Ví dụ:

Dữ liệu vào

14 3
1 3
2 3
3 4
7 4
4 5
5 6
10 11
9 11
8 11
11 5
12 13
13 6
14 6

Kết quả ra

6

Giải thích

enter image description here

Đổi tiền

Small

Bạn được cho một tập hợp các mệnh giá tiền. Tập hợp luôn chứa phần tử mang gía trị 1. Mỗi mệnh giá có vô hạn các đồng tiền mang mệnh giá đó. Cho số tiền \(S\), hãy tìm cách đổi \(S\) thành ít đồng tiền nhất, sao cho mỗi đồng tiền có mệnh giá thuộc vào tập hợp đã cho.

Input

  • Dòng 1: Hai số nguyên dương \(N\) (số phần tử của tập hợp mệnh giá tiền) và \(S\) (số tiền cần đổi) (\(1 ≤ N ≤ 100; 1 ≤ S ≤ 10^9\)).
  • Dòng 2: \(N\) số nguyên dương biểu thị mệnh giá của các phần tử trong tập hợp (giá trị không vượt quá 100).

Output

  • Dữ liệu ra gồm một số nguyên duy nhất là số đồng tiền ít nhất có thể đổi được.

Input

2 3
1 2

Output

2

Nguồn: SPOJ

Nước lạnh

Small

Mùa hè oi ả ở Wisconsin đã khiến cho lũ bò phải đi tìm nước để làm dịu đi cơn khát. Các đường ống dẫn nước của nông dân John đã dẫn nước lạnh vào 1 tập \(N\) (\(3≤ N≤ 99999; N\) lẻ) nhánh (đánh số từ \(1 ... N\)) từ một cái bơm đặt ở chuồng bò.

Khi nước lạnh chảy qua các ống, sức nóng mùa hè sẽ làm nước ấm lên. Bessie muốn tìm chỗ có nước lạnh nhất để cô bò có thể tận hưởng mùa hè một cách thoải mái nhất.

Bessie đã vẽ sơ đồ toàn bộ các nhánh ống nước và nhận ra rằng nó là một đồ thị dạng cây với gốc là chuồng bò và ở các điểm nút ống thì có chính xác 2 nhánh con đi ra từ nút đó. Một điều ngạc nhiên là các nhánh ống này đều có độ dài là 1.

Cho bản đồ các ống nước, hãy cho biết khoảng cách từ chuồng bò tới tất cả các nút ống và ở các phần cuối đường ống.

"Phần cuối" của một đường ống, có thể là đi vào một nút ống hoặc là bị bịt, được gọi theo số thứ tự của đường ống. Bản đồ có \(C\ (1≤ C≤ N)\) nút ống, được mô tả bằng 3 số nguyên: là "phần cuối" của ống \(E_i\ (1≤ E_i ≤ N)\) và 2 ống nhánh đi ra từ đó là \(B_{1i}\) và \(B_{2i}\) (\(2≤ B_{1i} ≤ N; 2≤ B_{2i} ≤ N\)). Đường ống số 1 nối với chuồng bò; khoảng cách từ phần cuối của đường ống này tới chuồng bò là 1.

Input

  • Dòng 1: 2 số nguyên cách nhau bởi dấu cách: \(N\) và \(C\)
  • Dòng \(2 ... C+1\): Dòng i+1 mô tả nút ống i với ba Số nguyên cách nhau bởi dấu cách: \(E_i, B_{1i}\), và \(B_{2i}\)

Output

  • Dòng \(1 ... N\): Dòng \(i\) chứa 1 số nguyên là khoảng cách từ chuồng tới "phần cuối" của ống thứ \(i\).

input

5 2
3 5 4
1 2 3

output

1
2
2
3
3

Giải thích ví dụ

Dữ liệu ở trên mô tả bản đồ ống nước sau:
                +-––––––-+
                | Chuồng |
                +-––––––-+
                   | 1
                   *
                2 / \ 3
                     *
                  4 / \ 5
Ống 1 luôn cách chuồng 1 đoạn là 1. Ống 2 và 3 nối với ống 1 nên khoảng cách sẽ là 2. Ống 4 và 5 nối với ống 3 nên khoảng cách sẽ là 3.

Nguồn: SPOJ

dance01

corona

Câu chuyện tình yêu Elo Cruz và Mara ở Philippines là một minh chứng cho tình yêu đích thực, không màng đến ngoại hình. Họ khiến cư dân mạng thế giới phải khâm phục vì một tình yêu bất chấp những khác biệt về ngoại hình. Tuy nhiên admin rất lo lắng cho Elo, không biết anh chàng này sẽ phải chọn cây ghế cao thế nào để hôn vợ. Cho nên trong buổi tiệc khiêu vũ “Cơn gió đêm hè!” sắp đến đây admin muốn các cặp đôi có chiều cao chênh lệch phải đúng bằng K mới được khiêu vũ cùng nhau.

Bạn hãy tính giúp cho admin xem có thể có bao nhiêu cách sắp xếp từng cặp đôi với nhau thỏa mãn.

Input:
  • Dòng đầu tiên là N - số lượng người tham gia bữa tiệc và số K (\(N≤10^5\), \(K≤10^9\))

  • Các dòng tiếp theo là chiều cao của N người tham gia bữa tiệc – không có 2 người nào có chiều cao giống nhau. (\(H_i\) ≤ \(10^9\))

Output:
  • Gồm một số duy nhất là số cách lớn nhất có thể sắp xếp.
Ví dụ
input
6 2
1 3 2 4 9 5
output
3

Những đường thẳng

algorit, bin9638

Hôm nay bin9638, vị thần tham lam nhận được một câu đố của vị thần ngu dốt algorit.

algorit cho bin9638 một dãy \(n\) điểm có tọa độ \(x,y\) \((|x|,|y| ≤ 10^9)\) trên mặt phẳng tọa độ. algorit đố bin9638 với \(n\) điểm trên thì có bao nhiêu cặp đường thẳng vuông góc sao cho mỗi đường thẳng nối \(2\) điểm phân biệt bất kì trong \(n\) điểm trên.

Nếu bin9638 giải ra thì sẽ nhận được một cái nịt siêu to khổng lồ từ algorit, các bạn hãy giúp bin9638 nhé !

  • Input:
    • Dòng đầu tiên là số \(n\).
    • \(n\) dòng tiếp theo mỗi dòng chứa 2 số nguyên \(x,y\) là tọa độ của điểm tương ứng.
  • Output: \(1\) số duy nhất là kết quả.

  • SampleInput

    4
    1 0
    0 2
    0 1
    -1 0
  • SampleOutput

    2
  • SampleInput

    5
    1 0
    0 -1
    0 1
    -1 0
    2 0
  • SampleOutput

    7
  • Ràng buộc

    • \(50\)% test có \(n ≤ 10\)
    • \(50\)% test có \(n ≤ 1000\)