CSES - Line Segment Intersection | Giao điểm hai đoạn thẳng

PhanDinhKhoi, Flower_On_Stone

There are two line segments: the first goes through the points ~(x_1,y_1)~ and ~(x_2,y_2)~, and the second goes through the points ~(x_3,y_3)~ and ~(x_4,y_4)~.

Your task is to determine if the line segments intersect, i.e., they have at least one common point.

Input

  • The first input line has an integer ~t~: the number of tests.
  • After this, there are ~t~ lines that describe the tests. Each line has eight integers ~x_1~, ~y_1~, ~x_2~, ~y_2~, ~x_3~, ~y_3~, ~x_4~ and ~y_4~.

Output

  • For each test, print YES if the line segments intersect and NO otherwise.

Constraints

  • ~1 \ \leq \ t \ \leq \ 10^5~
  • ~-10^9 \ \leq \ x_1, y_1, x_2, y_2, x_3, y_3, x_4, y_4 \ \leq \ 10^9~
  • ~x_1 \neq x_2~ or ~y_1 \neq y_2~
  • ~x_3 \neq x_4~ or ~y_3 \neq y_4~

Example

Sample input

5
1 1 5 3 1 2 4 3
1 1 5 3 1 1 4 3
1 1 5 3 2 3 4 1
1 1 5 3 2 4 4 1
1 1 5 3 3 2 7 4

Sample output

NO
YES
YES
YES
YES

Thử trí cân voi (Bản siêu khó)

huyhau6a2, nguyendanghau2006

huyhau6a2 được nhận lời thách thức của nguyendanghau2006. Thử thách của huyhau6a2 là cân ~1~ con voi cân nặng ~m~(chỉ nguyendanghau2006 biết được), và chỉ được sử dụng ~n~ viên đá. Cậu cũng được cho một chiếc cân Rô-béc-van gồm ~2~ chiếc đĩa ở ~2~ bên. Với mỗi viên đá, huyhau6a2 có thể đặt ở ~1~ trong ~2~ chiếc đĩa hoặc không sử dụng. Vấn đề quan trọng là huyhau6a2 cần xác định được cân nặng của con voi nên muốn nhờ các bạn tính xem có thể xác định được cân nặng của con voi hay không, nếu có thì hãy đếm số cách có thể cân được con voi đó(xem vd để hiểu rõ hơn). Nếu hoàn thành thử thách thì huyhau6a2 sẽ được tặng luôn con voi đó. Hãy giúp huyhau6a2 nhé!

Dữ liệu vào:

  • Dòng ~1~ gồm ~2~ số ~n~ và ~m~ ~(n≤30, 0≤m≤3*10^6)~.
  • Dòng ~2~ gồm ~n~ số chỉ cân nặng của mỗi viên đá, lớn hơn ~0~ và nặng không quá ~10^5~.

Dữ liệu ra:

  • Nếu có thể, dòng ~1~ xuất YES, dòng ~2~ chỉ số cách cân, không thì xuất NO.

Sample Input:

3 2
1 3 9

Sample Output:

YES
2

Giải thích: Có thể đặt cục nặng ~3~ vào đĩa ~1~, đặt con voi và cục nặng ~1~ vào đĩa ~2~ và ngược lại

Mỹ thuật Domino (DHHV 2021)

Small

Hai chị em Hồng, Phúc có một mảnh giấy to gồm ~m~ hàng ~n~ cột, các hàng được đánh số từ 1 đến ~m~ từ trên xuống dưới, các cột được đánh số từ 1 đến ~n~ từ trái sang phải, ô nằm giao giữa hàng ~i~ và cột ~j~ được gọi là ô (~i,j~). Hai chị em cùng nhau vẽ và tô màu trên mảnh giấy, em Phúc đã lựa chọn một số ô và tô màu các ô đó, Hồng rất thích kiểu giấy domino nên Hồng muốn vẽ ~k~ hình domino (mỗi hình có kích thước ~1× 2~ hoặc ~2× 1~ và chứa chọn hai ô chưa được tô màu của mảnh giấy). Để tạo điểm nhấn trên mảnh giấy, Hồng muốn lựa chọn các vị trí vẽ ~k~ hình domino để sau đó có thể chọn được một hình vuông lớn nhất, hình vuông không chứa ô đã bị tô màu cũng như ô thuộc vào một trong ~k~ hình domino, hình vuông đó sẽ cho em Phúc vẽ và tô màu.

Yêu cầu: Cho ~m,n,k~ và vị trí các ô mà em Phúc đã tô màu, hãy giúp Hồng lựa chọn các vị trí vẽ ~k~ hình domino để có thể tìm được hình vuông lớn nhất thỏa mãn yêu cầu trên.

Dữ liệu

  • Dòng đầu chứa ba số nguyên ~m,n,k~;
  • Tiếp theo là ~m~ dòng, mỗi dòng chứa một xâu độ dài ~n~ mô tả mảnh giấy, ví trí các ô chưa tô màu là ký tự ., vị trí các ô đã được tô màu là #. Dữ liệu đảm bảo để có thể vẽ được ~k~ hình domino.

Kết quả

  • Ghi ra gồm ~k~ dòng, mỗi dòng chứa 3 số nguyên ~x,y,h~ trong đó ~x,y~ là vị trí ô trên mảnh giấy chứa ô trái trên của hình domino, ~h~ là hướng (bằng 1 nếu domino vẽ ngang có kích thước ~1× 2~, bằng 2 nếu domino vẽ dọc có kích thước ~2× 1~).

(Cập nhật : Chỉ cần output ra độ dài cạnh hình vuông lớn nhất).

Ràng buộc:

  • Có 40% số lượng test ứng với 40% số điểm thỏa mãn điều kiện: ~m,n≤ 8,k≤ 3~;
  • Có 30% số lượng test khác ứng với 30% số điểm thỏa mãn điều kiện: ~m≤ 8,n≤ 32~;
  • Có 30% số lượng test còn lại ứng với 30% số điểm thỏa mãn điều kiện: ~m,n≤ 32~.

Input

3 5 2
.....
....#
....#

Output

2 4 2
1 4 1

3 (<- đây là output)

Giải thích

...22
...1#
...1#

Chữ số 1 và 2 thể hiện các ô chứa hình domino. Diện tích hình vuông lớn nhất chọn được là 9.


Nguồn: DHHV 2021

CSES - Rectangle Cutting | Cắt hình chữ nhật

a522QuangNHN, Flower_On_Stone, kitsune

Với một hình chữ nhật ~a \times b~, nhiệm vụ của bạn là cắt nó thành các hình vuông. Trong mỗi bước, bạn có thể chọn một hình chữ nhật và cắt nó thành hai hình chữ nhật sao cho tất cả độ dài các cạnh vẫn là số nguyên. Số bước tối thiểu có thể là bao nhiêu?

Input

  • Dòng đầu vào duy nhất có hai số nguyên ~a~ và ~b~.

Output

  • In một số nguyên: số lần di chuyển tối thiểu.

Constraints

  • ~1 \leq a, b \leq 500~

Example

Sample input

3 5

Sample output

3

Dãy ngoặc

corona

Có thể định nghĩa khái niệm dãy ngoặc đúng dưới dạng đệ quy như sau:

  1. "~()~" là dãy ngoặc đúng

  2. ~C~ là dãy ngoặc đúng nếu ~C = (A)~ hay ~C = AB~ với ~A, B~ là các dãy ngoặc đúng.

Ví dụ dãy ngoặc đúng: ~(), (()), ()(), (())()~

Ví dụ dãy ngoặc sai: ~)(, ((((, ()((, )))), )()(~

Bạn hãy viết chương trình liệt kê tất cả các dãy ngoặc đúng có chiều dài ~n~ (~n~ chẵn)

Dữ liệu nhập:

  • Là số nguyên ~n~ ~(n~ chẵn, ~2 ≤ n ≤ 30)~

Dữ liệu xuất:

  • In số ~m~ là số lượng các dãy ngoặc đúng có chiều dài ~n~

Sample Input

4

Sample Output

2

Sample Input

2

Sample Output

1

Giải thích:

  • Ví dụ 1: Có 2 dãy ngoặc đúng là: ~(())~, ~()()~

  • Ví dụ 2: Có 1 dãy ngoặc đúng là: ~()~

Trò chơi bắt chước

Small

Turing hiện đang làm việc để crack các máy bí ẩn. Nhưng ông thấy rằng có hai hàm toán học là ~f(n)~ và ~g(n)~ được sử dụng để mã hóa tin nhắn của người Đức. Ông muốn thử nghiệm khám phá của mình để bắt chước cách mã hóa của máy tính.

Các hàm được định nghĩa là:

  • ~g (n + 1) = 4 \times g (n) + f (n + 1) + c~
  • ~f (n + 2) = 3 \times f (n + 1) + 2 * f (n)~

Dữ liệu ban đầu:

  • ~f (0) = 1;~
  • ~f (1) = 1;~
  • ~g (-1) = 1;~
  • ~g (0) = 1;~
  • ~c = 2;~

Yêu cầu: Cho số nguyên ~n~, cần phải tìm giá trị ~g(n)\mod 10^9+7~.

Dữ liệu

  • Dòng đầu tiên ghi số lượng các trường hợp thử nghiệm ~T~,
  • ~T~ dòng tiếp theo mỗi dòng ghi một giá trị của ~n~.

Kết quả

  • Với mỗi test ~T~, xuất ra giá trị của ~g(n)~.

Input

5
1
2
3
6
1000

Output

7
35
159
12835
566998663

Nguồn: www.codechef.com

SEQ19845

cuom1999

Con số ~19845~ có gợi cho bạn điều gì không? Khi học lịch sử Việt Nam, Vinh biết rằng ngày ~19-8-1945~ là ngày Tổng khởi nghĩa, ngày nhân dân cả nước ta nhất tề đứng lên làm cuộc Cách mạng Tháng Tám vĩ đại. Con số này đã gợi ý cho cuom1999 khảo sát dãy số ~\textbf{SEQ19845}~ sau đây: Dãy số nguyên không âm ~a_1~, ~a_2~,..., ~a_n~ được gọi là dãy ~\textbf{SEQ19845}~ nếu không tồn tại hai chỉ số ~i~ và ~j~ ~(1 \leq i,j \leq n)~ mà ~a_i-a_j~ hoặc là bằng ~19~ hoặc là bằng ~8~ hoặc là bằng ~4~ hoặc là bằng ~5~.

Ví dụ:

Dãy số nguyên ~1~, ~3~, ~4~, ~17~ là dãy ~\textbf{SEQ19845}~.

cuom1999 quan tâm tới bài toán sau đây: Cho dãy số nguyên không âm ~b_1~, ~b_2~,..., ~b_m~, hãy tìm cách loại bỏ một số ít nhất phần tử của dãy để được dãy còn lại là ~\textbf{SEQ19845}~.

Yêu cầu

Hãy giúp cuom1999 giải quyết bài toán đặt ra


Dữ liệu

Dòng đầu chứa số nguyên dương ~m~;

Dòng thứ hai chứa ~m~ số nguyên không âm ~b_1~, ~b_2~,..., ~b_m~ ~\left(b_i \leq 10^9\right)~.


Kết quả

Ghi ra số nguyên ~k~ là số phần tử bị loại bỏ. Ghi số ~0~ nếu dãy đã cho là ~\textbf{SEQ19845}~.


Ví dụ

Input
6
7 3 5 1 9 21
Output
3

Ràng buộc:

  • Có ~25\%~ số test ứng với ~25\%~ số điểm của bài có ~m \leq 20~.
  • Có ~75\%~ số test còn lại ứng với ~75\%~ số điểm của bài có ~m \leq 2000~.

Ý tưởng: VOI 2016

Sự cố Mạng lưới | CSES - Network Breakdown

Elektrikar

Mạng lưới của Syrjälä có ~n~ máy tính và ~m~ kết nối giữa chúng. Mạng lưới gồm các thành phần các máy tính có thể gửi tin nhắn cho nhau.

Không ai ở Syrjälä biết cách mạng lưới hoạt động. Vì lý do này, nếu một kết nối gặp sự cố, sẽ không ai sửa nó. Trong tình huống này, một thành phần có thể bị chia thành hai thành phần.

Nhiệm vụ của bạn là tính số lượng thành phần sau mỗi sự cố kết nối.

Input

Dòng đầu tiên là ba số nguyên ~n, m~ và ~k~ : số lượng máy tính, kết nối và sự cố. Các máy tính được đánh số ~1,2,...,n~.

Tiếp theo là ~m~ dòng mô tả các kết nối. Mỗi dòng chứa hai số nguyên ~a~ và ~b~ : có một kết nối giữa hai máy ~a~ và ~b~. Mỗi kết nối là giữa hai máy tính khác nhau và có nhiều nhất một kết nối giữa hai máy.

Cuối cùng là ~k~ dòng mô tả các sự cố. Mỗi dòng chứa hai số nguyên ~a~ và ~b~ : kết nối giữa hai máy ~a~ và ~b~ gặp sự cố.

Output

Sau mỗi sự cố, in ra số lượng thành phần.

Giới hạn | Constraints

  • ~1 \le n \le 10^5~

  • ~1 \le m \le 2 \cdot 10^5~

  • ~1 \le k \le m~

  • ~1 \le a,b \le n~

    Ví dụ | Example

    Input
    5 5 3
    1 2
    1 3
    2 3
    3 4
    4 5
    3 4
    2 3
    4 5
    Output
    2 2 3
  • Không thích các số 3 (THTA Sơn Trà 2022)

    Small

    Polycarp không thích các số nguyên chia hết cho 3 hay có tận cùng bằng 3 (trong biểu diễn thập phân của số). Các số thỏa mãn cả hai điều kiện, Polycarp cũng không thích.

    Polycarp bắt đầu viết các số nguyên dương (lớn hơn 0) mà anh ấy thích: ~1, 2, 4, 5, 7, 8, 10, 11, 14, 16, …~

    Yêu cầu: Hãy in ra số thứ ~k~ trong dãy này (các số được đánh thứ tự từ 1)

    Dữ liệu

    • Một dòng chứa một số nguyên dương ~k\ (1 \le k \le 10^9)~

    Kết quả

    • In ra một dòng chứa số nguyên dương ~x~ - là số thứ ~k~ trong dãy mà Polycarp viết ra

    Sample Input

    3

    Sample Output

    4

    Dãy con chung dài nhất (Phiên bản 2)

    hhoangcpascal

    Cho dãy ~A~ gồm ~N~ phần tử gồm các số nguyên dương ~A_1, A_2, ..., A_N~ và dãy ~B~ gồm ~M~ phần tử gồm các số nguyên dương ~B_1, B_2, ..., B_M~. Dãy ~C~ được gọi là dãy con chung độ dài ~K~ của ~A, B~ nếu tồn tại hai dãy chỉ số như sau:

    • ~1 \leq i_1 < i_2 < ... < i_K \leq N~.
    • ~1 \leq j_1 < j_2 < ... < j_K \leq M~.

    Sao cho ~C_p = A_{i_p} = B_{j_p}~.

    Yêu cầu: Tìm dãy ~C~ là dãy con chung của ~A, B~ sao cho độ dài ~K~ lớn nhất có thể.

    Dữ liệu vào: Gồm ba dòng:

    • Dòng thứ nhất chứa hai số nguyên dương ~N, M~.
    • Dòng thứ hai gồm ~N~ số nguyên dương ~A_1, A_2, ..., A_N~ ~(A_i \leq 10^6)~.
    • Dòng thứ ba gồm ~M~ số nguyên dương ~B_1, B_2, ..., B_M~ ~(B_i \leq 10^6)~.

    Kết quả: Gồm hai dòng:

    • Dòng thứ nhất in ra số ~K~ là độ dài dãy con chung ~C~ dài nhất tìm được.
    • Dòng thứ hai in ra ~K~ số nguyên dương ~C_1, C_2, ..., C_K~. Nếu có nhiều dãy ~C~ thoả mãn, in ra một dãy bất kì.

    Ví dụ:

    Sample input:

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

    Sample Output:

    7 
    1 2 3 4 5 6 9

    Giới hạn:

    • ~50~% số test đầu tiên tương ứng với ~50~% số điểm có ~N \leq 10^3, M \leq 10^3~.
    • ~50~% số test còn lại tương ứng với ~50~% số điểm có ~N \leq 10^3, M \leq 10^6~.
    • Nếu in ra đúng số ~K~ thì sẽ được ~50~% số điểm của test. Nếu in ra thêm được dãy ~C_1, C_2, ..., C_K~ mà đúng sẽ được thêm ~50~% số điểm của test.

    Lưu ý: Đọc dạng bài trước khi làm

    Ước tự nhiên (QNOI 2020)

    BichSonNhat

    Một số tự nhiên ~N~, nếu tồn tại ~2~ số tự nhiên ~a~ và ~b~ sao cho ~N = a × b~, thì ~a~ và ~b~ là các ước tự nhiên của ~N~.

    Yêu cầu: Cho 2 số tự nhiên ~x~ và ~y~ ~(x ≤ y)~. Hãy tính số lượng và tổng các ước tự nhiên của các số tự nhiên trong đoạn ~[x,y]~.

    Dữ liệu vào:

    • Dòng đầu tiên ghi số nguyên dương ~T~ là số bộ dữ liệu;

    • ~T~ dòng tiếp theo, mỗi dòng chứa ~2~ số tự nhiên ~x, y~ tương ứng với ~1~ bộ dữ liệu.

    Kết quả:

    Gồm ~T~ dòng, mỗi dòng ghi hai số nguyên ~U~ và ~S~ lần lượt là số lượng và tổng các ước tự nhiên tương ứng với dữ liệu vào.

    Ví dụ:

    Sample Input

    2
    1 2
    4 5

    Sample Output

    3 4
    5 13

    Ràng buộc:

    • Có ~40~% số test ứng với ~40~% số điểm của bài có ~T ≤ 10; 1 ≤ x ≤ y ≤ 10 ^ 3~;

    • Có ~30~% số test ứng với ~30~% số điểm của bài có ~T ≤ 10; 1 ≤ x ≤ y ≤ 10 ^ 6~;

    • Có ~30~% số test ứng với ~30~% số điểm còn lại của bài có ~T ≤ 10 ^ 6; 1 ≤ x ≤ y ≤ 10 ^ 6~.

    Cờ vua vô hạn

    cuom1999, zipdang04

    Trên một bàn cờ vua có chiều dài và chiều rộng vô hạn, xuất hiện ~n~ con vua: ~K = \{(x_1, y_1), (x_2, y_2), \dots, (x_n, y_n) \}~.

    Nếu các bạn chưa biết chơi cờ, con vua mỗi bước có thể đi sang 8 ô kề nó, tính cả đi chéo.

    Bạn có thêm một quân vua TỐI CAO đứng tại vị trí ~(x, y)~, có sức mạnh của là tổng của từng số bước đi tối thiểu để con vua tối cao này có thể đi tới từng con vua khác.

    Một cách quy củ, gọi ~d_i~ là số bước đi tối thiểu để vua tối cao có thể đi tới vua thứ ~i~, thì sức mạnh của vua tối cao là ~\sum_{i=1}^{n} d_i~.

    ~n~ con vua trên không muốn vị tối cao này lộng hành, nên muốn sức mạnh của nó nhỏ nhất có thể. Bạn hãy tìm lượng sức mạnh tối thiểu này là bao nhiêu, và số lượng vị trí để đạt lượng tối thiểu này nhé.

    Input:

    • Dòng đầu tiên gồm số ~n~
    • ~n~ dòng sau lần lượt gồm ~x_i, y_i~ là vị trí của con vua thứ ~i~.

    Output:

    • Gồm 2 số, là sức mạnh tối thiểu của con vua tối cao, và số vị trí đặt con vua này để đạt lượng sức mạnh tối thiểu.

    Sample Input

    3
    0 0
    1 3
    4 1

    Sample Output

    5 1

    CSES - Planets Cycles | Chu trình hành tinh

    zipdang04, Flower_On_Stone, kitsune

    Bạn đang chơi một trò chơi bao gồm ~n~ hành tinh. Mỗi hành tinh có một cổng dịch chuyển đến một hành tinh khác (hoặc chính hành tinh đó).

    Bạn bắt đầu trên một hành tinh và sau đó đi qua các cổng dịch chuyển cho đến khi bạn đến một hành tinh mà bạn đã thăm trước đó.

    Nhiệm vụ của bạn là tính toán cho mỗi hành tinh số lần dịch chuyển sẽ có nếu bạn bắt đầu trên hành tinh đó.

    Input

    • Dòng đầu vào đầu tiên có hai số nguyên ~n~ và ~q~: số lượng hành tinh và truy vấn. Các hành tinh được đánh số ~1,2,\ldots,n~.
    • Dòng thứ hai có ~n~ số nguyên ~t_1,t_2,\ldots,t_n~: với mỗi hành tinh, điểm đến của của cổng dịch chuyển. Có thể là ~t_i=i~.

    Output

    • In ~n~ số nguyên theo đề bài.

    Constraints

    • ~1 \leq n \leq 2 \cdot 10 ^ 5~
    • ~1 \leq t_i \leq n~

    Example

    Sample input

    5
    2 4 3 1 4

    Sample output

    3 3 1 3 4

    Nối Ô

    ami

    ami có một ma trận 2 chiều A gồm n hàng và m cột. Các hàng và cột được đánh số từ 0. Ô nằm trên giao của hàng i và cột j được kí hiệu là ô (i , j). Mỗi ô trong ma trận được tô một màu là ~A_{i,j}~.

    Từ một ô (~x_1~ , ~y_1~) ta có thể đi đến ô (~x_2~ , ~y_2~) nếu hai ô này có cùng màu và chung một cạnh. Hai ô (~x_1~ , ~y_1~) và (~x_2~ , ~y_2~) được gọi là liên thông nếu ta có thể di chuyển từ ô (~x_1~ , ~y_1~) đến ô (~x_2~ , ~y_2~) qua một vài ô trung gian thoả mãn điều kiện ở trên.

    Các bạn cần trả lời một vài câu hỏi của ami. Mỗi câu hỏi là một cặp ô (~x_1~ , ~y_1~) và (~x_2~ , ~y_2~), các bạn cần xác định xem có cách nào làm 2 ô này liên thông nếu đổi màu tối đa một ô trong ma trận hay không.

    Input

    Dòng đầu tiên chứa số nguyên dương ~n~ là số hàng của ma trận.

    Dòng tiếp theo chứa số nguyên dương ~m~ là số cột của ma trận.

    ~n~ dòng tiếp theo, môi dòng chứa ~m~ số nguyên dương biểu thị một màu của một ô trong ma trận.

    Tiếp theo là một số nguyên dương ~q~ là số câu hỏi.

    Dòng tiếp theo chứa số 4.

    ~q~ dòng tiếp theo, mỗi dòng chứa 4 số nguyên dương ~x_1~ , ~y_1~ , ~x_2~ , ~y_2~ biểu thị một câu hỏi.

    Output

    Với mỗi câu hỏi, hãy in ra "YES" nếu hai ô đó liên thông và "NO" nếu ngược lại

    Sample Input

    3
    3
    1 2 1
    1 1 3
    2 2 1
    3
    4
    0 0 2 2
    0 0 1 1
    1 2 2 0

    Sample Output

    YES
    YES
    NO

    Giới hạn

    Trong tất cả các test có ~1 \leq X \leq 10^{6}~.

    ~60~% điểm tương ứng với ~1 \leq n, m, q \leq 50~.

    ~15~% điểm tương ứng với ~1 \leq n, m, q \leq 100~.

    ~25~% điểm tương ứng với ~1 \leq n, m, q \leq 500~.

    Giải thích

    Với hai ô (0 , 0) và (2 , 2), ta có thể đổi màu ô (1 , 2) thành màu 1.

    Với hai ô (0 , 0) và (1 , 1), ta không cần đổi màu ô nào.

    Ta không thể chỉ đổi màu 1 ô để làm 2 ô (1 , 2) và (2 , 0) liên thông.

    LMHT

    PhanDinhKhoi

    Trong Liên minh huyền thoại có ~N~ vị tướng, vị tướng thứ ~i~ có ~2~ sát thương vật lý và sát thương phép.

    Vị tướng thứ ~i~ được cho là mạnh hơn vị tướng thứ ~j~ nếu có sát thương vật lý mạnh hơn.

    Hai vị tướng có cùng sát thương vật lý thì vị tướng mạnh hơn sẽ có sát thương phép lớn hơn.

    Hãy cho biết chỉ số sát thương vật lý và phép của vị tướng mạnh thứ ~m~.

    Input

    • Dòng đầu chứa số ~n, m (1 \leq m \leq n \leq 10000) ~
    • ~n~ dòng, mỗi dòng chứa 2 số nguyên ~A_i(~vật lý~),B_i(~phép~) (0 \leq A_i,B_i \leq 10000)~.

    Output

    • Chỉ số sát thương

    Input

      3  2
      1  2
      3  2
      1  3

    Output

      1  3

    COUNT SQUARE

    dang7rickroll

    Cho một lưới hình ô vuông có kích thước ~n \times n~. Đếm số lượng hình vuông có trong hình đó.

    Dữ liệu:

    • Dòng đầu ghi ~q~ không quá ~100~ - số câu hỏi.
    • ~q~ dòng tiếp theo, mỗi dòng ghi ~n~ không quá ~10^9~

    Kết quả:

    • Ứng với mỗi câu hỏi, in ra kết quả cần tìm sau khi ~\mod 10^9 + 7~

    Sample input

    1
    1

    Sample output

    1

    Số lớn thứ k

    Small

    Cho một dãy gồm ~N~ số nguyên dương ~A_1, A_2,…, A_N~.(~N ≤ 10^4, A_i ≤ 10^9~) và số ~K~ (~K ≤ N~). Hãy in ra số lớn thứ ~K~ trong dãy.

    Input

    • Dòng đầu chứa số ~N, K~,
    • Dòng thứ hai chứa ~N~ số nguyên dương ~A_1, A_2,…, A_N~.

    Output

    • Một dòng chứa dãy số lớn thứ ~K~ trong dãy.

    Input

    6 2    
    91 451 43 3 452 54

    Output

    451

    CSES - Pyramid Array | Mảng hình "kim"

    letangphuquy

    Cho trước một mảng gồm ~n~ số nguyên phân biệt. Tại mỗi lượt, bạn có thể đảo vị trí của hai phần tử kề nhau.

    Bạn muốn biến đổi mảng này thành dạng kim tự tháp. Nghĩa là mảng kết quả đầu tiên phải tăng dần, và sau đó giảm dần. Cho phép mảng cuối cùng chỉ tăng hoặc chỉ giảm.

    Số lượng lượt đi tối thiểu là bao nhiêu?

    Input

    • Dòng đầu vào đầu tiên chứa ~n~: kích thước của mảng.
    • Dòng tiếp theo chứa ~n~ số nguyên phân biệt ~x_1, x_2, \dots, x_n~: nội dung của mảng.

    Output

    • In một số nguyên: số lượng nước đi tối thiểu.

    Constraints

    • ~1 \leq n \leq 2 \cdot 10^5~
    • ~1 \leq x_i \leq 10^9~

    Example

    Sample input:

    4
    2 1 5 3

    Sample output:

    1

    Note

    Bạn có thể đổi chỗ hai phần tử đầu tiên, tạo nên mảng hình "kim" ~[1,2,5,3]~

    Thuật toán Dial trên lưới

    zipdang04

    Cho một lưới gồm ~m~ hàng, ~n~ cột. Bạn Hiếu có ~k~ lọ sơn, và với mỗi ô, bạn sẽ chọn một trong số ~k~ màu để tô lên.

    Từ một ô có thể đi sang các ô kề cạnh. Cụ thể hơn, từ ô ~(x, y)~, chúng ta có thể đi sang ô ~(x-1, y), (x, y-1), (x, y+1), (x+1, y)~.

    Để đi từ ô có màu ~x~ sang ô có màu ~y~, chi phí dịch chuyển là ~c_{xy}~. Lưu ý, ~c_{xy}~ có thể khác ~c_{yx}~.

    Hãy trả lời ~q~ câu hỏi, mỗi câu có dạng "Chi phí thấp nhất để đi từ ô ~(u, v)~ tới ô ~(x, y)~ là bao nhiêu?".

    Dữ liệu

    Input:

    • Dòng đầu chứa 3 số ~m, n, k~
    • ~m~ dòng sau, dòng thứ ~i~ chứa n số: ~a_{i1}, a_{i2}, \dots, a_{in}~ biểu thị màu của từng ô.
    • k dòng sau, dòng thứ i chứa k số: ~c_{i1}, c_{i2}, \dots, c_{ik}~. ~c_{ij}~ là chi phí chuyển từ ô màu i sang ô màu j.
    • Dòng tiếp theo chứa số ~q~
    • ~q~ dòng cuối, dòng thứ ~i~ chứa 4 số ~u_i, v_i, x_i, y_i~ biểu thị cho câu hỏi thứ ~i~.

    Output: In ra ~q~ dòng, mỗi dòng in ra đáp án của câu hỏi thứ ~i~.

    Ví dụ

    Input

    3 4 2
    2 1 1 2
    1 2 1 2
    1 1 2 2
    1 2
    3 1
    3
    1 2 2 3
    1 1 3 2
    2 1 2 2

    Output

    2
    5
    2

    Giới hạn

    • ~m, n \le 2000, k \le 4, q \le 10~
    • ~\forall 1 \le i \le m, 1 \le j \le n: a_{ij} \le 4~
    • ~\forall 1 \le i,j \le k: c_{ij} \le 10. \forall 1 \le i \le k: c_{ii} = 1~

    Hotel Queries

    hhoangcpascal

    Có ~N~ khách sạn trên một con đường. Với mỗi khách sạn bạn biết được số phòng còn trống. Nhiệm vụ của bạn là chỉ định các phòng khách sạn cho ~M~ nhóm khách du lịch. Tất cả các thành viên trong cùng một nhóm muốn trọ chung một khách sạn.

    Các nhóm sẽ lần lượt đến và bạn biết số phòng yêu cầu của mỗi nhóm. Với mỗi nhóm, bạn luôn tìm khách sạn đầu tiên mà đủ số phòng trống và chỉ định nhóm đấy vào phòng này. Sau đó, số phòng trống của khách sạn này sẽ giảm đi.

    Dữ liệu vào:

    • Dòng đầu tiên gồm hai số nguyên dương ~N, M~: Số khách sạn và số nhóm. Các khách sạn được đánh số theo thứ tự từ ~1~ tới ~N~.
    • Dòng thứ hai gồm ~N~ số nguyên dương ~H_1, H_2, ..., H_N~ ~(1 \leq H_i \leq 10^9)~: số phòng trống của mỗi khách sạn.
    • Dòng cuối cùng gồm ~M~ số nguyên dương ~R_1, R_2, ..., R_M~ ~(1 \leq R_i \leq 10^9)~: số phòng trống mà mỗi nhóm yêu cầu.

    Kết quả: In ra ~M~ số nguyên là chỉ số của khách sạn được phân cho mỗi nhóm. Nếu nhóm nào đó không được chỉ định vào khách sạn (do không tìm được), in ra số ~0~.

    Ràng buộc:

    • Subtask 1 ~(50\%)~: ~N, M \leq 2.10^3~.
    • Subtask 2 ~(50\%)~: ~N, M \leq 2.10^5~.

    Ví dụ:

    Input:

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

    Output:

    3 5 0 1 1

    Nguồn: CSES