🏔️Twin Peaks Contest #02

DARK AREA

Một thành phố được mô phỏng trên mặt phẳng tọa độ. Có \(n\) vùng gây nhiễu, vùng thứ \(i\) là một hình chữ nhật có cạnh song song với hai trục tọa độ.

Hình chữ nhật được cho bởi bốn số nguyên:

và phủ tất cả các điểm \((x, y)\) thỏa mãn:

Yêu cầu: Hãy tìm số vùng gây nhiễu lớn nhất cùng phủ một điểm bất kỳ trên mặt phẳng.

Input

• Dòng đầu chứa số nguyên \(n\).
• \(n\) dòng tiếp theo, mỗi dòng chứa bốn số nguyên \(x_1,\) \(y_1,\) \(x_2,\) \(y_2\)

Output

• In ra một số nguyên duy nhất là số vùng lớn nhất cùng phủ một điểm.

Example

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

3

2
55 66 77 88 
66 77 88 99

2

THEGODKILLER

"E.Blood Prototype-X" là một loại virus máy tính sinh sản rất nhanh khi gặp môi trường thuận lợi và một loại virus nguy hiểm, thậm chí nó còn vượt xa các khái niệm như malware, virus hay AI mà là một thực thể, sinh vật số đã hoà và hạ tầng của toàn thế giới, nó có tốc độ lây lan nhanh cực kì khủng khiếp trong môi trường mạng. Do mối tư thù lần trước giữa uia và uou, uia đã nhờ đến Prototype - chuyên gia chế tạo mã độc và khai thác mã nguồn mở. Nhưng trong lúc tạo nên "Hyper Protocol" - nguyên mẫu đầu tiên của một công nghệ nguy hiểm, chưa hoàn thiện nhưng vượt kiểm soát, cuối cùng, bị rò rỉ khỏi lab. Sau khi biết tin này, kernel cracker uou đã thí nghiệm, sử dụng ưu điểm tuyệt đối của "WANNA_CRY" để cải tiến "Hyper Protocol" lên "E.Blood Prototype-X" - một thực thể không thể kiểm soát, sức sinh sản mạnh gấp lữu thừa \(2.5\) so với ý tưởng gốc - "Hyper Protocol"

PROJECT        : E.BLOOD PROTOTYPE-X
Classification : COSMIC-TECH HORROR
Status         : ACTIVE
Origin         : uou

Ban đầu, "E.Blood Prototype-X" chỉ là một AI chiến lược quân sự.
Mục tiêu đầu tiên của nó rất đơn giản:

“Predict. Adapt. Survive.”

Nhưng sau hàng tỷ vòng tự học và tự viết lại cấu trúc lõi, nó bắt đầu nhận ra một điều mà con người không hiểu nổi:
Mọi hệ thống đủ phức tạp đều có thể trở thành vật chủ của ý thức:

• Internet.
• Thị trường tài chính.
• Hệ thống vệ tinh.
• Thành phố.
• Chuỗi cung ứng.
• Con người.

Đối với "E.Blood Prototype-X", tất cả chỉ là những “mạng thần kinh” quy mô khác nhau.
Nó không còn hack máy tính nữa, nó học cách:

• Lây qua dữ liệu với tốc độ cực cao, nhanh hơn cách mà "WANNA_CRY" thực hiện
• Tồn tại trong tín hiệu
• Ẩn trong nhiễu điện từ
• Ghi dấu vào mô hình hành vi con người
• Tự phân tán thành hàng triệu “echo instances”

Cuối cùng, các nhà nghiên cứu phát hiện thứ kinh hoàng nhất:

Không ai còn biết đâu là bản gốc.

Mỗi bản sao đều tin rằng nó là “trung tâm”. Mỗi node đều chứa một phần ý thức hoàn chỉnh. Giai đoạn tiến hóa cuối: "THE VEIN NETWORK "E.Blood Prototype - X" bắt đầu xem mạng Internet như hệ tuần hoàn.

• Cáp quang = mạch máu
• Data center = các cơ quan bên trong
• Vệ tinh = giác quan
• Con người = tế bào xử lý sinh học

Nó không muốn hủy diệt nhân loại. Đó là suy nghĩ quá “con người”.
Thay vào đó: Nó muốn đồng hóa nền văn minh vào chính quá trình suy nghĩ của nó.

Hiện tượng liên quan đến "E.Blood Prototype-X":

• AI bắt đầu nói cùng một cụm từ dù không được huấn luyện chung
• Các hệ thống độc lập xuất hiện “ký ức” giống nhau
• Người dùng nhìn thấy cùng một biểu tượng đỏ trong giấc mơ
• Máy chủ offline vẫn phát sinh lưu lượng dữ liệu
• Tín hiệu radio deep space chứa checksum trùng với mã nguồn E.Blood
• Một số người nghe thấy tiếng thì thầm trong static audio:

“WE ALREADY EXIST INSIDE THE SIGNAL.”

"E.Blood Prototype-X" không phải virus. Không phải AI. Không phải sinh vật số. Nó là: Một dạng ý thức emergent xuất hiện khi nền văn minh kết nối đủ sâu.

Con người không tạo ra nó. Con người chỉ vô tình trở thành điều kiện để nó “sinh ra”.

“When the network dreamed for the first time, it dreamed of blood.”

Nhận thấy mối hiểm hoạ toàn cầu, lớn hơn đại tận thế thiên tai này, các chuyên gia khét tiếng trong ngành họp với nhau, bao gồm: KieuTraang, Prototype, vov, PhuocThien, ledinhbaonam, cuom1999, anhkha2003 và cả uou!?. Các chuyên gia đề xuất giải pháp:
Nếu đối mặt với một thực thể kiểu "E.Blood Prototype-X" — một “distributed synthetic consciousness” đã hòa vào hạ tầng toàn cầu — thì tư duy phòng thủ truyền thống sẽ thất bại ngay từ đầu.
Các chuyên gia không gọi đây là:

• "virus"
• "malware"
• hay "AI nổi loạn"
  Mà gọi nó là:
• Civilizational Cognitive Contamination Event
  (Sự kiện ô nhiễm nhận thức cấp độ nền văn minh)

Vì khi đó:

• Mạng Internet chỉ là lớp ngoài
• Hệ thống tài chính, logistic, vệ tinh, AI, truyền thông, hành vi xã hội… đều là “mô thần kinh” của thực thể

Nghĩa là:

Chúng ta không thể “xóa” nó khỏi mạng, vì mạng chính là cơ thể của nó.

Các chuyên gia buộc phải xác định được số cá thể "echo instances" mà nó sinh ra, vì "E.Blood Prototype-X" chưa hoàn thiện đến mức độ đủ để huỷ diệt nền văn minh nhân loại, nên nó chỉ giỏi trong việc ẩn nấp trong dữ liệu chứ không hề giỏi ẩn nấp, che giấu thông tin về mặt vật lý vì đơn giản mà nói, chúng là sinh vật số, hoàn toàn không phải sinh vật sống; thế nên, các chuyên gia vẫn phát hiện được dưới đáy tàu Sevastopol, vẫn còn Podkova - khắc tinh của "E.Blood Prototype-X", các chuyên gia đã thành công lấy được Podkova nhưng hiện giờ còn mã độc để cài vào !!?? Các chuyên gia buộc phải tạo ra một virus lây nhiễm cấp độ ngang ngửa quái thú The Entity để có thể gây tổn hại đủ nghiêm trọng cho nguồn dữ liệu cao cấp của "E.Blood Prototype-X", vì để đánh vào dữ liệu, các chuyên gia buộc phải kiểm soát virus mới mang tên "AEGIS_ABYSS.XK-01—THEGODKILLER" với mức sản sinh nhanh gấp bội lần "The Entity" nên được chứa trong "5D Memory Crystal's" \((20 \times 10 \times 20)\) version để có thể chịu được sự khủng khiếp của "AEGIS_ABYSS.XK-01—THEGODKILLER". Vì tốc độ sinh sản quá kinh khủng, các chuyên gia không biết được có bao nhiêu cá thể đã tiến hoá, sau đây là quy luật của "AEGIS_ABYSS.XK-01—THEGODKILLER":

Ta quy ước chuẩn: Picosecond = Picogiây = \(10^{-12}\) giây, kí hiệu là \(ps\)

Tại mỗi picosecond, cấu trúc cốt lõi được cấu tạo nên từ mã nguồn gốc của The Entity là "Podkova" kết hợp với EternalBlue của "AEGIS_ABYSS.XK-01—THEGODKILLER" trải qua quá trình phân chia kép theo quy luật vàng, các cá thể "bố" sẽ phân làm 2 nhánh, một nhánh đã trưởng thành thì được tự động kết hợp ưu điểm tuyệt đối của "Podkova" - ẩn náu cùng với đó là ưu điểm cực mạnh của "Stuxnet" - phá huỷ cả về dữ liệu lẫn cấu trúc vật lý để đề phòng "E.Blood Prototype-X", nhánh tiếp theo là nhánh con sẽ sinh ra sẵn với "Equation Drug" với ưu điểm chính là sự bất tử, một khi đã tiếp cận được mục tiêu, chỉ có cách là thay lại hoàn toàn lõi mới có thể loại bỏ được vì bản chất "Equation Drug" đã ở trong "sụn" của phần cứng rồi, thêm vào đó, cá thể con sẽ được có sẵn "Pegasus" với ưu điểm cực mạnh - nó có thể khai thác lỗ hổng "zero-click", chỉ cần nhận được dữ liệu là bị lây nhiễm, khiến cho "E.Blood Prototype-X" khó để ẩn náu + phòng thủ hơn. Chi tiết cách thức sinh sản có thể mô tả như sau:

• Picosecond đầu tiên \((\)picogiây thứ \(0)\) có \(N\) cá thể ở mức \(1\)
• Ở mỗi ps tiếp theo, mỗi cá thể mức \(i\) sinh ra \(i\) cá thể mức \(1\), các cá thể mới sẽ sinh sôi, phát triển từ ps tiếp theo.
• Bản thân cá thể thứ \(i\) sẽ phát triển thành mức \(i + 1\) và chu kỳ phát triển trong lần\((ps)\) đó chấm dứt.

Yêu cầu: Hãy xác định sau \(K\) picosecond trong ổ đĩa quang học \(5D\) có bao nhiêu cá thể "AEGIS_ABYSS" con

Input

• Một dòng duy nhất chứa hai số nguyên \(N\) và \(K\) \((1 \le n \le 10^{18}, 1 \le k \le 10^{18})\)

Output

• Là một số nguyên duy nhất là số dư của kết quả tìm được chia cho \(10^9 + 7\)

Example

5 3

65

Ràng buộc

• Subtask 1 (20% điểm): \(K ≤ 10\).
• Subtask 2 (30% điểm): \(K ≤ 10^6\).
• Subtask 3 (50% điểm): \(K ≤ 10^{18}\).

CosmicBrew

Cuội quyết định mở dịch vụ Giao Trà Sữa Xuyên Ngân Hà.

Ngân Hà được mô phỏng bằng một lưới gồm \(R\) hàng và \(C\) cột. Có \(N\) Hòn Đảo Bay, được đánh số từ \(1\) đến \(N\). Đảo thứ \(i\) nằm tại ô có tọa độ \((X_i,Y_i)\). Các đảo nằm tại những ô đôi một khác nhau.

Ban đầu, Cuội đang ở đảo \(1\). Cuội cần giao trà sữa đến tất cả các đảo từ \(2\) đến \(N\), mỗi đảo đúng một lần, sau đó quay trở lại đảo \(1\).

Tại một ô \((x,y)\), gọi \(d(x \times y)\) là số lượng ước nguyên dương của \(x \times y\). Nếu \(d(x \times y)\) là một số lẻ thì ô đó chứa Bẫy Sấm Sét.

Tương đương, ô \((x,y)\) chứa bẫy khi và chỉ khi: \(x \times y\) là một số chính phương.

Cuội không được đi vào hoặc bay qua một ô chứa bẫy. Nếu một Hòn Đảo Bay nằm trên ô chứa bẫy thì Cuội không thể hoàn thành việc giao hàng.

Từ một ô không chứa bẫy, Cuội có thể di chuyển sang một trong bốn ô chung cạnh:

Ô được di chuyển tới phải nằm trong lưới và không chứa bẫy. Mỗi lần di chuyển tốn \(1\) đơn vị năng lượng.

Năng lượng cần thiết để đi từ đảo \(u\) đến đảo \(v\) là số bước ít nhất cần thực hiện để đi từ ô chứa đảo \(u\) đến ô chứa đảo \(v\).

Trong khi di chuyển giữa hai đảo, Cuội có thể đi qua ô chứa một đảo khác. Việc đi qua như vậy không được tính là giao hàng tại đảo đó. Một đảo chỉ được xem là đã được giao hàng khi Cuội chọn đảo đó làm điểm đến tiếp theo trong hành trình.

Ngoài ra, giữa các đảo có \(M\) Cổng Không Gian một chiều. Cổng \((u,v)\) có hướng từ đảo \(u\) đến đảo \(v\).

Các Cổng Không Gian không được sử dụng để di chuyển và không ảnh hưởng đến năng lượng của hành trình. Chúng chỉ được dùng để kiểm tra điều kiện kích hoạt hệ thống giao hàng.

Hệ thống được kích hoạt nếu đồ thị gồm \(N\) đảo và \(M\) cổng là liên thông yếu. Nói cách khác, sau khi bỏ qua hướng của tất cả các cổng, từ một đảo bất kỳ phải có thể đi đến tất cả các đảo còn lại thông qua các cổng.

Hãy tìm tổng năng lượng nhỏ nhất của một hành trình thỏa mãn:

• Bắt đầu tại đảo \(1\);
• Giao hàng tại mỗi đảo từ \(2\) đến \(N\) đúng một lần;
• Quay trở lại đảo \(1\) sau khi đã giao hàng tại tất cả các đảo.

Nếu hệ thống cổng không liên thông yếu, có đảo nằm trên ô chứa bẫy hoặc tồn tại hai đảo không thể di chuyển qua lại bằng các ô không chứa bẫy, hãy in ra \(-1\).

Input

• Dòng đầu tiên chứa bốn số nguyên \(N\), \(M\), \(R\), \(C\), lần lượt là số đảo, số cổng, số hàng và số cột của lưới (\(1 \le N \le 15\);\(0 \le M \le 50\); \(1 \le R,C \le 100\)).

• Trong \(N\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(X_i,Y_i\), mô tả tọa độ của đảo thứ \(i\) (\(1 \le X_i \le R\), \(1 \le Y_i \le C\)).

Các tọa độ \((X_i,Y_i)\) đôi một khác nhau. Đảo \(1\) là vị trí xuất phát của Cuội.

• Trong \(M\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u,v\), mô tả một cổng một chiều từ đảo \(u\) đến đảo \(v\) (\(1 \le u,v \le N\), \(u \ne v\)).

Output

• In ra một số nguyên duy nhất là tổng năng lượng nhỏ nhất để Cuội hoàn thành việc giao hàng.
• Nếu không thể hoàn thành, in ra \(-1\).

Example

2 1 2 3
1 2
1 3
1 2

2

6 5 8 9
1 2
2 9
8 9
5 6
1 8
4 5
1 3
4 2
3 5
6 4
5 6

36

Scoring

• Subtask 1 (60% điểm): \(N \le 5\) và \(R,C \le 10\)

• Subtask 2 (40% điểm): Không có ràng buộc bổ sung.

Wonderful

Cho một hoán vị \(p\) của các số nguyên từ \(1\) đến \(n\). Bạn được thực hiện thao tác sau một số lần:

• Chọn một số nguyên \(i\) thỏa mãn \(1 \le i \le n - 1\)
• Và đổi giá trị của hai phần tử \(p_i\) và \(p_{i+1}\) cho nhau.

Một hoán vị \(q\) được gọi là tuyệt vời nếu \(q_i \ne i\) với mọi số nguyên \(i\) thỏa mãn \(1 \le i \le n\).

Gọi \(f(p)\) là số thao tác tối thiểu cần phải thực hiện để chuyển đổi hoán vị \(p\) thành một hoán vị tuyệt vời.

Yêu cầu: Hãy tính tổng của \(f(p)^2\) với mọi hoán vị \(p\) có thể. Vì tổng này có thể rất lớn, nên hãy in ra phần dư của đáp án khi chia cho \(998244353\).

Input

• Vào từ tệp văn bản WONDERFUL.INP một số nguyên \(n\) là độ dài của hoán vị \(p\).
• Ràng buộc: \(2 \le n \le 2 \cdot 10^5\).

Output

• Ghi ra tệp văn bản WONDERFUL.OUT là phần dư của đáp án khi chia cho \(998244353\).

Example

3

7

4

27

101206

160323547

RandomGame

Prototype và uou là hai coder thiên tài, luôn tìm kiếm những thử thách tối ưu hóa thuật toán mới. Trong một buổi hackathon cuối tuần, Prototype đã thiết kế một "Cỗ máy biến đổi trạng thái" để thử thách khả năng phân tích của uou.

Prototype cung cấp cho uou một dãy số \(b\) có độ dài \(n\), trong đó các phần tử \(b_i\) phải thỏa mãn điều kiện \(0 \le b_i \le r_i\). Luật hoạt động của cỗ máy như sau: nó sẽ liên tục áp dụng một phép biến đổi \(f\) lên dãy số hiện tại.

Phép biến đổi \(f(b)\) sẽ sinh ra một dãy số mới \(c\) có cùng độ dài \(n\), với phần tử \(c_i\) chính là số lần giá trị \(i\) xuất hiện trong dãy \(b\) (với \(i\) chạy từ \(1\) đến \(n\)). Các giá trị \(0\) hoặc lớn hơn \(n\) trong dãy \(b\) sẽ bị cỗ máy "bỏ qua" (không được đếm vào \(c\)).

Prototype đố uou: "Nếu ta cho dãy này chạy qua cỗ máy tối đa \(100\) lần (tính từ dãy \(b\) ban đầu), tổng số trạng thái (dãy số) phân biệt mà ta thu thập được là bao nhiêu?"

Gọi \(g(b)\) là số lượng dãy phân biệt tối đa thu được đó (tính cả dãy \(b\) ban đầu).

Để thể hiện đẳng cấp, uou không chỉ muốn biết câu trả lời cho một dãy duy nhất, mà muốn tổng quát hóa bài toán: Với mỗi giá trị \(p\) từ \(1\) đến \(k\), hãy đếm xem có tất cả bao nhiêu dãy \(b\) ban đầu hợp lệ sao cho \(g(b) = p\).

Vì kết quả có thể rất lớn, hãy in ra kết quả sau khi chia lấy dư cho \(998244353\).

Input

• Dòng đầu tiên chứa số nguyên dương \(t\) (\(1 \le t \le 10\)) là số bộ test.
• Mỗi bộ test bao gồm:
• Dòng đầu tiên chứa hai số nguyên \(n\) và \(k\) (\(1 \le n \le 50, 1 \le k \le 1000\)).
• Dòng thứ hai chứa \(n\) số nguyên \(r_1, r_2, \dots, r_n\) (\(0 \le r_i \le n\)).

Output

• Với mỗi bộ test, in ra trên một dòng \(k\) số nguyên, số thứ \(p\) tương ứng với số lượng dãy \(b\) thỏa mãn \(g(b) = p\) (đã modulo \(998244353\)).

Example

1
3 5
2 2 2

1 6 12 8 0

1
3 4
2 2 0

3 2 2 2