Hẳn chúng ta ai cũng biết hành trình từ đáy xã hội đi lên của idol tên Đ nào đó. Ngày hôm nay, gia đình của anh ấy - gia đình Villa, đã đón tiếp 1 thành viên mới, đó chính là _nhphuc. Để chào mừng thành viên mới và gắn kết gia đình, Đ quyết định cho cả gia đình thực hiện hành trình đi lên đỉnh xã hội trên một cây có $n$ đỉnh và $n–1$ cạnh. Đỉnh $1$ của cây tượng trưng cho cánh cổng dẫn tới đỉnh xã hội và các đỉnh lá dưới cùng của cây tượng trưng cho ngôi nhà của Mân đàn, Vozer,…. (đứng đầu là HoBaoPhuc2009). Cụ thể, trong một đơn vị thời gian, mỗi thành viên của gia đình sẽ đi tới đỉnh cha mà đỉnh họ đang đứng cho tới khi tới được đỉnh $1$ và sau đó thoát khỏi cây.

Nhưng con đường lên tới đỉnh xã hội không dễ dàng như vậy, mỗi đỉnh trên cây không thể chứa hai thành viên của gia đình cùng một lúc, vì vậy tổng lãnh tên Đ đã đưa ra một phương án đó chính là: Với mỗi “đáy” mà một thành viên đứng ban đầu, thành viên đó có thể chèn thêm một đỉnh con khác cho đỉnh đó, sau đó chuyển sang đứng ở “đáy” mới này.

Các thành viên của gia đình tuy không muốn bị “ùn tắc giao thông” khi lên đỉnh xã hội nhưng cũng muốn số lần “đáy” mới được thêm vào là ít nhất, hãy giúp họ tính toán nhé.

5
1 2
1 3
3 4
3 5

1

Bạn được cho một tập hợp $S$ gồm các số nguyên dương từ $1$ đến $n$. Nhiệm vụ của bạn là tìm số chính phương lớn nhất là tích của một tập hợp con của tập hợp $S$.

6

144

Cây nhị phân cân bằng bậc $n$ được định nghĩa bao gồm tổng cộng $2^n-1$ đỉnh và được đánh số từ $1$ đến $2^n-1$. Với mọi đỉnh thứ $i$ từ $1$ đến $2^{n-1}-1$ sẽ có đúng 2 đỉnh con là $2i$ và $2i+1$. Tất cả các đỉnh từ $2^{n-1}$ đến $2^n-1$ không có đỉnh con nào.

Một hôm, weqd muốn thử thách khả năng lập trình của bạn bằng một trò chơi. Ban đầu, weqd có 1 món đồ chơi có dạng cây nhị phân cân bằng bậc $n$. Cậu ta sẽ đánh các giá trị trên cây, với đỉnh thứ $i$, cậu ta sẽ đánh giá trị là $i$. Sau đó, weqd sẽ tiến hành thay đổi giá trị giữa $2$ đỉnh bất kì (anh ấy sẽ thực hiện điều đó trong $q$ lần). weqd sẽ yêu cầu bạn tính giá trị hàm $f(i)+g(i)$ với mọi $1\le i\le 2^n-1$. Trong đó, hàm $f(x)$ là giá trị nhỏ nhất trong đường đi từ đỉnh $1$ tới đỉnh thứ $x$, còn hàm $g(x)$ là giá trị lớn nhất trong đường đi từ đỉnh $1$ tới đỉnh thứ $x$

Nhiệm vụ của bạn là hãy viết chương trình để hoàn thành thử thách trên.

2 2
1 2
2 3

4 5 3

Bạn được cho một dãy số $A$ gồm $n$ phần tử bất kỳ $(1\le A_i\le 10^8)$. Bạn được cho thêm 2 giá trị là $l$ và $r$, với $l=min(A), r=max(A)$.

Nhiệm vụ của bạn là in ra toàn bộ dãy số $A$ bằng cách hỏi câu lệnh sau: $?\ i\ j$ $(1\le i,j\le n)$. Sau khi bạn hỏi lệnh thì máy sẽ trả về một giá trị là $A_i-A_j$.

Bạn được hỏi lệnh này tối đa $n-1$ lần. Sau đó, bạn bắt buộc phải in ra toàn bộ dãy số $A$ với lệnh $!\ A_1\ A_2\ \dots\ A_{n-1}\ A_n$.

Ăn ba tô cơm để khỏe

Trường của mondellbit009 mới mở bán trú để cho học sinh ăn và nghỉ trưa tại trường. Là một đứa có nhà ở rất xa, mondellbit009 liền đăng ký ngay. Sau $69$ tháng mở bán trú, trường của mondellbit009 đang gặp một vấn đề đau đầu đó là: Học sinh ở đó ăn rất ít, khiến nhà trường bị nghi ngờ là nấu đồ ăn ít + không đảm bảo. Vì thế nhà trường phát động phong trào đó là Ăn ba tô cơm. Nhà trường sẽ trao thưởng cho bạn nếu bạn ăn nhiều hơn hoặc bằng 3 tô cơm với điều kiện để ăn một tô cơm là:

• Ăn cơm không
• Ăn cơm với thịt
• Ăn cơm với canh
• Hoặc là ăn cơm + thịt + canh

Học sinh sẽ tự lấy cho mình $a$ tô cơm, $b$ tô thịt, $c$ tô canh. Hãy kiểm tra xem học sinh đó có đủ điều kiện để nhận thưởng không?

3
3 1 2
1 2 1
69 3 2

YES
NO
YES

Đây là 1 bài tương tác với máy chấm

huyhau6a2 đang có 1 hoán vị $a$ độ dài $n$. Nhiệm vụ của bạn là tìm ra hoán vị mà huyhau6a2 đang có. Mỗi lần bạn được hỏi huyhau6a2 cung cấp dữ kiện để tìm kiếm bằng cách chọn 2 chỉ số $i,j$ $(1\le i,j\le n; i\ne j)$ và huyhau6a2 sẽ cho bạn biết giá trị của $a_i\ mod\ a_j$

Bạn chỉ được hỏi huyhau6a2 không quá $2n-2$ lần. Nhiệm vụ của bạn là tìm ra hoán vị mà huyhau6a2 đang có.

Bạn được biết $m$ mô tả về dãy bit. Mỗi mô tả có thể thuộc $1$ trong $2$ loại sau:

• $1\ l\ r$: Dãy bit con $[l,r]$ chứa ít nhất $1$ bit $0$.
• $2\ l\ r$: Dãy bit con $[l,r]$ chứa ít nhất $1$ bit $1$.

Nhiệm vụ của bạn là đếm số lượng dãy bit có độ dài $n$ sao cho nó khớp với mô tả trên.

3 2
1 1 2
2 2 3

4

Cho dãy số nguyên dương $n$ phần tử $a_1,a_2,\ldots,a_n$. Tìm số lượng bộ $k$ chỉ số $i_1,i_2,\ldots, i_k$ thỏa mãn $1\le i_1<i_2<\ldots <i_k\le n$, sao cho $a_{i_1}\times a_{i_2}\times \ldots \times a_{i_k}=1$.

5 4
1 1 1 1 1

5

ngvanminh_ có 1 xâu $s$ có độ dài $n$ chỉ gồm các chữ cái thường. Cậu thực hiện $q$ thao tác, thao tác thứ $i$ chứa số nguyên $x_i$ và kí tự $c_i$: ngvanminh_ sẽ thay đổi kí tự ở vị trí thứ $x_i$ thành $c_i$.

Nhiệm vụ của bạn là đếm số lượng xâu khác nhau đã được tạo ra sau $q$ thao tác (tính cả xâu ban đầu).

3 7
abc
1 n
2 v
3 m
1 a
2 b
3 c
2 b

6

Never gonna give you up...

Vào 1 ngày đẹp trời và lúc Astley đang vội làm toán để anh ấy mai có thể kịp biểu diễn bài hát Never Gonna Give You Up, anh ấy đã gặp trúng 1 bài toán hơi căng, nội dung của bài toán là:

Cho một số nguyên chẵn $x$. Nhiệm vụ của bạn là kiểm tra xem có thể biểu diễn $x$ dưới dạng tổng của 2 số nguyên tố $p_a$ và $p_b$ hay không.

3
2
4
6

0
1
1

Sqrt, sqrt, sqrt!

Ban đầu bạn có một số $x=1$. Mỗi lần bạn tăng $x$ lên $\left \lfloor \sqrt x \right \rfloor$. Trong đó $\left \lfloor x \right \rfloor$ là phép làm tròn xuống. Ví dụ: $\left \lfloor 5.2 \right \rfloor=5,\left \lfloor 6.9 \right \rfloor=6$

Nhiệm vụ của bạn là kiểm tra xem sau $k$ bước, giá trị $x$ bằng bao nhiêu.

10
1
2
3
4
5
6
7
8
9
10

2
3
4
6
8
10
13
16
20
24

Lời thách đấu của Kaito huyhau6a2 the Kid tới Edogawa Sunlight

Ta đã bắt cóc bạn gái của ngươi là aisukiuwu Ran (có hình ảnh minh họa)

8 giờ tối nay, vào đêm trăng (tròn hay không không quan trọng), hãy đến quảng trường TLE. Chúng ta hãy thách đấu với nhau trên quảng trường đó. Nếu ngươi thắng, ta sẽ thả bạn gái của ngươi ra và sẽ cho ngươi 200k để đi chơi với người yêu. Chúng ta cùng thách đấu nào!

Kaito huyhau6a2 the Kid

Đó chính là lời thách đấu của Kaito huyhau6a2 the Kid tới Edogawa Sunlight. Edogawa Sunlight sau khi biết được tin này đã rất hoảng loạn, cậu ta đã chuẩn bị món quà nhỏ nhỏ xinh xinh nhân ngày kỷ niệm hơn 9 tháng yêu nhau cùng với aisukiuwu Ran rồi. Vậy mà lại xảy ra cơ sự như thế này. Nhưng đây biết đâu lại là cơ hội, vì nếu cậu ta cứu được aisukiuwu Ran thì sẽ có cơ hội tỏ tình với cô ấy. Thế là vào đúng lúc 8 giờ tối hôm ấy, cậu lướt ván trượt nhanh như bay, và đã tới được nơi mà Kaito huyhau6a2 the Kid thách đấu. Ở đấy đã có rất nhiều người theo dõi, trên ti vi cũng live trận thách đấu của cậu ta. Từ trước giờ, cậu chưa bao giờ gặp trận thách đấu nào căng thẳng đến như thế này, nhưng mà vì aisukiuwu Ran, cậu không thể dừng lại được. Trận đấu bắt đầu!

Kaito huyhau6a2 the Kid quyết định thách đấu với Edogawa Sunlight bằng cách là mỗi người sẽ ra 1 bài toán cho đối phương giải. Edogawa Sunlight ra bài trước, nhưng mà Kaito huyhau6a2 the Kid rất nhanh đã giải được chỉ trong vòng $27022009\ ms$ (ăn may :D). Tới luợt Kaito huyhau6a2 the Kid ra bài. Ra bài xong, sau một thời gian, Edogawa Sunlight đã nghĩ ra thuật, nhưng mà... "Chắc chưa?" - một câu hỏi đơn giản đã làm Edogawa Sunlight phải toát mồ hôi hột. Vì thế xin nhờ các bạn hãy cùng Edogawa Sunlight giải bài toán này nhé! Nếu bạn giải được bài toán này cho Edogawa Sunlight thì sẽ được tặng vé xem phim Tàu ngầm sắt màu đen mới nhất đang chiếu trên rạp đó! Bài toán như sau:

Ta gọi một dãy số $a$ được gọi là dãy đáng ghét khi có một giá trị $k$ không âm thỏa mãn cả $k$ và $\sqrt k$ đều xuất hiện trong dãy số đó.

Bạn được cho một dãy số $a$ gồm $n$ phần tử. Nhiệm vụ của bạn là thực hiện $q$ truy vấn thuộc 1 trong 2 loại như sau:

• $1\ i\ k$: Đặt $a_i=k$
• $2\ l\ r$: Kiểm tra xem dãy số $a_l,a_{l+1},\dots,a_r$ có phải là dãy số đáng ghét không. Nếu có, nhiệm vụ của bạn là tìm một cặp số $l\le u\le v\le r$ thỏa mãn $a_u=\sqrt {a_v}$ hoặc $a_v=\sqrt {a_u}$. Ưu tiên xuất giá trị $u$ nhỏ nhất, sau đó tới $v$ nhỏ nhất

Lưu ý là các truy vấn loại 1 sẽ độc lập với nhau, hay nói cách khác, truy vấn loại 1 thứ $i-1$ sẽ hết hiệu lực ngay trước khi thực hiện truy vấn loại 1 thứ $i$

5 6
3 2 4 6 9
2 1 5
2 2 4
1 3 36
2 2 4
1 5 10
2 1 5

1 5
2 3
3 4
2 3

There are some imposustor among sus

Among sus là một trò chơi rất thú vị mà bạn có thể chơi với bạn bè. Về cơ bản thì trò chơi này cũng không khác werewolf là mấy. Các bạn sẽ ở trong 1 con tàu và sẽ có một vài người là imposustor - kẻ giả mạo sẽ tìm mọi cách để sát hại người khác hay phá hoại, crewmate - người thường sẽ phải hoàn thành nhiệm vụ và tìm ra imposustor trong quá trình sửa chữa con tàu. Crewmate sẽ chiến thắng nếu hoàn thành hết nhiệm vụ hoặc tìm ra hết imposustor, còn imposustor sẽ thắng khi số imposustor ít hơn hoặc bằng so với số crewmate hay là họ phá hủy con tàu thành công.

Trong thời gian nghỉ hè, huyhau6a2 vì đã quá chán với những trò chơi như Free Fire, Liên Quân Mobile, Osu, Geometry Dash, ... nên cậu quyết định tìm một trò chơi mới đủ thú vị và có thể chơi cùng bạn bè. Ngày đó cũng như ngày thường, cậu vào Google Play lướt tìm trò chơi và đã tìm thấy tựa game Among sus. Sau khi nghiên cứu và coi những video ~~của mấy ông Ấn Độ~~ chơi trên youtube thì cậu đã cảm thấy trò này rất thú vị. Thế là cậu đã dựa vào quan hệ bạn bè gần xa, bà con cuối phố. Và cậu đã rủ được $n-1$ người khác cùng chơi trò này, cộng thêm cậu nữa thì tổng cộng $n$ người.

Sau khi chơi với những người bạn của cậu được một thời gian, huyhau6a2 bỗng nảy ra một bài toán mới. Nhưng sau khi suy nghĩ xong, vì quá lười + cậu đã nghiện game Among sus rồi nên cậu đành nhường lại cho các bạn. Bài toán như sau:

Giả sử các bạn chơi trò chơi này trên bàn gồm $n$ người. Người thứ $i\ (1\le i\le n)$ sẽ ở cạnh người $i-1$ và người $i+1$ (người thứ nhất chỉ ở cạnh người thứ hai và người thứ $n$ chỉ ở cạnh người thứ $n-1$). Mỗi người trong trò chơi này sẽ được cấp vai trò cho mình, vai trò của người thứ $i$ sẽ là $a_i$ ($0\le a_i\le 1$, $a_i=0$ tức là vai trò của người đó là crewmate, $a_i=1$ tức là vai trò của người đó là imposustor). Imposustor sau khi nhận vai trò sẽ chọn 1 trong 2 người kề bên là crewmate và sát hại người đó. Hai imposustor không thể sát hại cùng 1 crewmate, imposustor này không thể sát hại imposustor kia.

huyhau6a2 định nghĩa một trò chơi được cho là gay cấn khi với mỗi imposustor, họ đều có thể tìm được 1 crewmate để sát hại. Ví dụ:

• Trò chơi 0 là trò chơi gay cấn vì không có imposustor
• Trò chơi 010 là trò chơi gay cấn vì người thứ hai là imposustor có thể chọn người thứ nhất hoặc thứ ba để sát hại
• Trò chơi 0110 là trò chơi gay cấn vì người thứ hai có thể chọn người thứ nhất và người thứ ba có thể chọn người thứ tư để sát hại
• Trò chơi 01110 không là trò chơi gay cấn vì người thứ ba không thể chọn được crewmate có thể sát hại
• Trò chơi 101 không là trò chơi gay cấn vì chỉ có 1 crewmate mà có tận 2 imposustor

huyhau6a2 đang thắc mắc với $n$ người thì sẽ có thể tạo ra bao nhiêu trò chơi gay cấn khác nhau. Hai trò chơi $a$ và $b$ được cho là khác nhau khi có tối thiểu một giá trị $i$ thỏa mãn $a_i\ne b_i$. Vì kết quả có thể rất lớn nên bạn hãy xuất kết quả sau khi $mod\ 998244353$

5
1
2
3
4
5

1
3
4
9
14