Dãy xâu

Small

Cho một dãy gồm n xâu s_1,s_2,…, s_n và một số nguyên dương k. Một cặp hai xâu s_is_j trong dãy được gọi là tương thích với nhau nếu thỏa mãn:

  • 0 < j-i ≤ k
  • Hai xâu s_is_j có cùng độ dài.

Yêu cầu: Hãy xác định số cặp các xâu tương thích với nhau trong dãy các xâu đã cho.

*Dữ liệu *

  • Dòng đầu chứa hai số nguyên nk (3 ≤ n ≤ 3 \times 10^5; 1 ≤ k ≤ n).
  • n dòng tiếp theo mỗi dòng chứa một xâu có độ dài từ 2 đến 20 kí tự gồm các chữ cái tiếng Anh in hoa.

Kết quả

  • Một dòng duy nhất là kết quả của bài toán.

Sample Input 1

4 2
OTN
ABC
THA
HUN

Sample Output 1

5

Sample Input 2

6 3
CFETHIA   
LLOYD
STEVIE
KEVIN
MALCABC
DABNEY

Sample Output 2

2

Ràng buộc:

  • Có 40% số điểm ứng với n ≤ 5000
  • Có 60% số điểm ứng với n ≤ 300.000.

Nguồn: 2019 CBH-H.Nam

J4F #01 - Accepted

stack_queue_4977

Thách bạn Wrong Answer được bài này.

Input


Output


Tam giác Pascal

admin

Cho số tự nhiên n (n \le 100000). Hãy in ra hàng thứ n của tam giác Pascal. Cho biết tam giác Pascal có hình dạng như sau :

Hàng 0: 1
Hàng 1: 1 1
Hàng 2: 1 2 1
Hàng 3: 1 3 3 1
Hàng 4: 1 4 6 4 1
...

Yêu cầu: Với mỗi số tìm được, hãy in ra số dư của nó khi chia 10^9 + 7.

Dữ liệu

Dòng đầu chứa T (T \le 100) là số test.
T dòng tiếp theo, mỗi dòng chứa một số nguyên dương n.

Kết quả

Gồm T dòng, mỗi dòng là đáp số tương ứng với mỗi trường hợp n.

Ví dụ

Input

3
1
2
3

Output

1 1
1 2 1
1 3 3 1

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à: ()

Kiểm tra dãy giảm

minhkhangcqt

Cho một mảng n số nguyên. Kiểm tra xem mảng có giảm dần không. Mảng giảm dần là mảng mà số sau nhỏ hơn số trước.

Đầu vào:

  • Dòng đầu tiên là số nguyên n (3 ≤ n ≤ 10^6).

  • Dòng thứ 2 là mảng n số nguyên, các số cách nhau bởi dấu cách, trị tuyệt đối của các số này không quá 10^18

Đầu ra: Nếu mảng giảm dần in ra “TRUE”, nếu không in ra “FALSE”.
Ví dụ:

input1:

5

5 4 4 3 2

output1:

FALSE

input2:

3

4 2 -9

ouput2:

TRUE

Covid'19 (DHBB CT)

Small

Dịch Covid-19 đã được kiểm soát, trong gần một tháng qua, tại Việt nam không có ca nhiễm
mới trong cộng đồng. Lệnh cách ly đã được nới lỏng, Hồng và các bạn được đi học trở lại, đó
cũng là thời điểm thầy Phương mở trại HCC cho các bạn yêu thích lập trình, một hoạt động
mà thầy đã duy trì trong nhiều năm qua. Tham gia HCC, Hồng rất thích thú với một bài toán
của thầy Phương, bài toán mô phỏng việc di chuyển của virus, cụ thể bài toán như sau:
Xét lưới ô vuông thước 𝑚 × 𝑛, các dòng được đánh số từ 1 đến 𝑚 từ trên xuống, các cột được
đánh số từ 1 đến 𝑛 từ trái sang phải. Ô nằm trên giao của dòng 𝑖, cột 𝑗 được gọi là ô (𝑖,𝑗) và
ô này chứa một số nguyên dương a(𝑖,𝑗). Nếu một virus đang ở ô (𝑥, 𝑦), virus có thể thực
hiện bước di chuyển sau:

  • Virus di chuyển sang ô kề cạnh với ô (𝑥, 𝑦) nằm trong lưới, việc di chuyển này mất 1
    đơn vị thời gian;
  • Virus di chuyển sang ô (𝑢, 𝑣) nằm trong lưới nếu 𝑢 × 𝑣 = 𝑎(𝑥, 𝑦), việc di chuyển này
    mất 3 đơn vị thời gian.

Bài toán yêu cầu tính thời gian nhỏ nhất để virus di chuyển từ ô (𝑝, 𝑞) đến ô (𝑟, 𝑠).

Đây là bài toán khó đối với Hồng nên Hồng nhờ các anh chị tham gia kỳ thi Duyên Hải năm
2020 giải giúp.

Yêu cầu: Cho lưới kích thước 𝑚 × 𝑛 và các số trên lưới. Có câu hỏi, với câu hỏi thứ 𝑘\ (𝑘 =1, 2, . . . , ℎ) cần phải trả lời thời gian nhỏ nhất để virus di chuyển từ ô (𝑝_𝑘, 𝑞_𝑘) đến ô (𝑟_𝑘, 𝑠_𝑘)là bao nhiêu?

Dữ liệu vào

  • Dòng đầu chứa ba số nguyên dương 𝑚, 𝑛, ℎ\ (ℎ ≤ 5);
  • Dòng thứ 𝑖\ (𝑖 = 1, 2, … , 𝑚) trong 𝑚 dòng tiếp theo chứa 𝑛 số nguyên dương 𝑎(𝑖, 1), 𝑎(𝑖, 2), … , 𝑎(𝑖, 𝑛). Các số có giá trị không vượt quá 10^6.
  • Dòng thứ 𝑘\ (𝑘 = 1, 2, … , ℎ) trong dòng tiếp theo chứa bốn số nguyên 𝑝_𝑘, 𝑞_𝑘, 𝑟_𝑘, 𝑠_𝑘.

Kết quả

  • Ghi ra dòng, dòng thứ 𝑘\ (𝑘 = 1, 2, … , ℎ) ghi một số nguyên là thời gian nhỏ nhất để virus di chuyển từ ô (𝑝_𝑘, 𝑞_𝑘) đến ô (𝑟_𝑘, 𝑠_𝑘).

Sample Input 1

2 5 2
8 6 4 1 1
1 1 1 1 1
1 1 2 5
2 5 1 1

Sample Output 1

4
3

Giới hạn

  • Có 20% số lượng test ứng với 20% số điểm thỏa mãn điều kiện: 𝑚 × 𝑛 ≤ 10^2;
  • Có 20% số lượng test khác ứng với 20% số điểm thỏa mãn điều kiện: 𝑚 × 𝑛 ≤ 10^3;
  • Có 20% số lượng test ứng khác với 20% số điểm thỏa mãn điều kiện: 𝑚 × 𝑛 ≤ 10^4;
  • Có 20% số lượng test khác ứng với 20% số điểm thỏa mãn điều kiện: 𝑚 × 𝑛 ≤ 10^5;
  • Có 20% số lượng test còn lại ứng với 20% số điểm thỏa mãn điều kiện: 𝑚 × 𝑛 ≤ 10^6

Nguồn: 2020 Chính thức

Chú ếch và hòn đá 1

jumptozero

N hòn đá được đánh số 1,2,3,...,N. Với mỗi i(1\le i\le N), chiều cao của hòn đá thứ ih_i

Có một con ếch ban đầu ở hòn đá 1. Nó lặp lại hành động sau với một số lần bất kì cho đến khi nó đến được hòn đá N.

  • Nếu con ếch đang ở hòn đá i, thì nó có thể nhảy sang hòn đá thứ i+1 hoặc i+2 với chi phí là |h_i-h_j|, trong đó j là vị trí nó muốn nhảy tới.

Tìm chi phí tối thiểu để nó đến được hòn đá thứ N.

Input:

  • Dòng thứ nhất chứa số nguyên N(2\le N\le 10^5)

  • Dòng thứ hai chứa N số nguyên : h_1,h_2,...,h_N với 1\le h_i\le 10^4

Output:

  • In ra chi phí tối thiểu cần tìm

Ví dụ:

Input:

4
10 30 40 20

Output:

30

Giải thích: Con ếch sẽ nhảy như sau: 1\rightarrow 2 \rightarrow 4, với chi phí là |10-30|+|30-20|=30

Nguồn: DP Contest Atcoder

Mã Morse

BichSonNhat

Để chào mừng năm học mới $ 2020 - 2021 $, BichSonNhat được thầy Hùng cho một đoạn tin nhắn gồm các kí tự ., -, / (biểu diễn dấu cách).

Thực chất ., - là những kí tự biểu diễn cho mã Morse.

Vì nghỉ hè quá lâu nên BichSonNhat đã quên cách lập trình, các bạn hãy giúp anh ấy giải mã nhé!

Dữ liệu vào: Một chuỗi kí tự chỉ chứa ., -, /. (Luôn đảm bảo rằng tin nhắn đã được giải mã chỉ bao gồm những chữ cái in hoadấu cách) (1 ≤ s.length ≤ 10^3)

Dữ liệu ra: Tin nhắn đã được giải mã.

Sample Input

.... . .-.. .-.. --- / .-- --- .-. .-.. -..

Sample Output

HELLO WORLD

Chu trình lẻ trong đồ thị vô hướng

jumptozero

Bạn được cho một đồ thị G vô hướng gồm N đỉnh. Các đỉnh được đánh số từ 0 đến N-1. Ngoài ra, bạn còn được cho ma trận kề của đồ thị này, trong đó G[i][j]='Y' nếu hai đỉnh i,j kề nhau ngược lại G[i][j]='N' nếu hai đỉnh i,j không kề nhau.

Một chu trình "đơn lẻ" là một dãy các đỉnh V[0],V[1],...,V[l-1] thoả mãn:

  • l lớn hơn hoặc bằng 3

  • l lẻ

  • Tất cả các V[i] khác nhau từng đôi một

  • Với mỗi i(0\le i<l-1),V[i]V[i+1] kề nhau.

  • V[l-1],V[0] kề nhau.

Yêu cầu: In ra kết quả bài toán dưới dạng như sau: C[0]\text{ } -1\text{ } C[1]\text{ } -1\text{ } C[2]\text{ } ...-1\text{ } C[n-1]. Trong đó: Gọi C[i] là tập chu trình "đơn lẻ" bất kỳ đi qua đỉnh i của đồ thị G.

Input:

  • Dòng thứ nhất chứa số nguyên N(1\le N\le 50) - Số đỉnh của đồ thị

  • Tiếp theo ma trận kề thể hiện đồ thị G

Output:

  • In ra đáp án cần tìm.

Ví dụ:

Input:

3
NYY
YNY
YYN

Output:

11
0 2 1 -1 0 2 1 -1 0 2 1

Nguồn: Topcoder

CSES - Cut and Paste | Cắt và dán

kitsune

Cho một xâu, nhiệm vụ của bạn là xử lý các thao tác trong đó bạn cắt một xâu con và dán nó vào cuối xâu. Xâu cuối cùng sau tất cả thao tác là gì?

Input

  • Dòng đầu vào đầu tiên có hai số nguyên nm: độ dài của xâu và số lượng thao tác. Các ký tự của chuỗi được đánh số 1, 2,\ldots, n.
  • Dòng tiếp theo có một xâu độ dài n bao gồm các kí tự AZ.
  • Cuối cùng, có m dòng mô tả các thao tác. Mỗi dòng có hai số nguyên ab: bạn cắt một xâu con từ vị trí a đến vị trí b.

Output

  • In xâu cuối cùng sau tất cả thao tác.

Constraints

  • 1 \leq n, m \leq 2 \cdot 10 ^ 5
  • 1 \leq a \leq b \leq n

Example

Sample intput

7 2
AYBABTU
3 5
3 5

Sample output

AYABTUB

Xin chào

Small

Nhập họ tên của mình và in ra màn hình lại câu "Xin chao: " và họ tên vừa nhập.

Input

  • Một dòng chứa họ tên

Output

  • In ra câu "Xin chao: " và họ tên vừa nhập.

sample Input

Small

Sample Output

Xin chao: Small

Tổng ước số (HSG10v1-2021)

Small

Input

5 3
2 3 8 9 100
1 3 
4 4
3 5

Output

10
4
10

Thao Tác Lớn Nhất

ami

ami có một dãy hoán vị A độ dài n. Nhắc lại, một hoán vị độ dài n là một dãy số mà mỗi số nguyên dương từ 1 đến n đều xuất hiện trong dãy đúng một lần.

Các bạn có thể chọn cặp số ij khác nhau và đổi chỗ A_iA_j. Các bạn được áp dụng thao tác trên đúng 1 lần. Mục đích là cần làm cho giá trị S sau đạt lớn nhất:

S = \sum A_i * (n+1)^{1 + n - i} \forall 1 \leq i \leq n.

Hãy in ra dãy số tối ưu A sau khi thực hiện thao tác trên đúng một lần. Nếu có nhiều đáp án, các bạn có thể in ra một đáp án bất kì.

Input

Dòng đầu tiên chứa hai số nguyên dương n là số phần tử của dãy A.

Dòng tiếp theo chứa n số nguyên dương A_i biểu thị một phần tử của dãy A.

Dữ liệu đảm bảo dãy

Output

Hãy in ra dãy A sau khi thực hiện thao tác một cách tối ưu.

Sample Input 1

3 
1 2 3

Sample Output 1

3 2 1

Sample Input 2

2
1 2

Sample Output 2

2 1

Giới hạn

  • 50% điểm tương ứng với 2 \leq n\leq 10.

  • 50% điểm tương ứng với 2 \leq n \leq 5000.

Giải thích

Ở ví dụ 1, các cách thực hiện thao tác là:

  • Đổi cặp (1, 2) ta được 2 1 3, tổng S = 2*4^2 + 1*4^1 + 3*4^0 = 39.
  • Đổi cặp (2, 3) ta được 1 3 2, tổng S = 1*4^2 + 3*4^1 + 2*4^0 = 30.
  • Đổi cặp (1, 3) ta được 3 2 1, tổng S = 3*4^2 + 2*4^1 + 1*4^0 = 57.

Vậy đáp án là [3 2 1].

Ở ví dụ 2, chỉ có một cách đổi là đổi cặp (1, 2). Ta sẽ nhận được dãy [2 1].

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

Thay đổi chữ số (THTA Vòng sơ loại 2022)

Flower_On_Stone

Cho một số tự nhiên N. Hãy thay đổi tối đa hai chữ số của N để được một số nhỏ nhất chia hết cho 4. Số mới tạo thành phải có số chữ số bằng số chữ số của N và không chứa chữ số 0 ở đầu.

Input

  • Gồm một số tự nhiên N (10 \leq N \leq 10^{15}).

Output

  • Ghi ra một số là kết quả của bài toán.

Scoring

  • Nếu chương trình chạy đúng những trường hợp 10 \leq N \leq 10^4, thí sinh sẽ được 40 điểm.
  • Nếu chương trình chạy đúng những trường hợp 10 \leq N \leq 10^{15}, thí sinh sẽ được 100 điểm.

Example

Sample input 1

168

Sample output 1
100

Sample input 2
26622

Sample output 2
16612

Note

  • Ví dụ 1: Có nhiều cách đổi thành số chia hết cho 4 như: 108, 104, 164, 160, 200, ... nhưng 100 là đáp án nhỏ nhất thỏa mãn.
  • Ví dụ 2: Có nhiều các đổi thành số chia hết cho 4 như: 26600, 20612, 20620, ... nhưng 16612 là đáp án nhỏ nhất thỏa mãn.

CSES - Swap Game | Trò chơi hoán đổi

nhphucqt

Bạn được cung cấp một lưới 3 × 3 chứa các số 1,2,…, 9. Nhiệm vụ của bạn là thực hiện một chuỗi các bước di chuyển để lưới trở về dạng như sau:

$
\begin{matrix}
1 \ \ 2 \ \ 3 \
4 \ \ 5 \ \ 6 \
7 \ \ 8 \ \ 9
\end{matrix}
$

Trên mỗi lần di chuyển, bạn có thể hoán đổi các số trong hai ô vuông liền kề bất kỳ (theo chiều ngang hoặc chiều dọc). Số lần di chuyển cần thiết tối thiểu là bao nhiêu?

Input

  • Gồm ba dòng, mỗi dòng gồm ba số nguyên.

Output

  • In ra đáp án là số lần di chuyển ít nhất.

Example

Sample input

2 1 3
7 5 9
8 4 6

Sample output
4

Số chính phương

admin, daicadihoc

Viết chương trình nhập vào một số nguyên n. Kiểm tra xem n có phải là số chính phương hay không?
(Số chính phương là bình phương của một số nguyên ví dụ như 16=4^2)?

Dữ liệu vào

  • Một số nguyên dương n.

Kết quả

  • Nếu n là số chính phương thì in YES, ngượi là in NO

Sample Input

16

Sample Output

YES

Sample Input

 10

Sample Output

NO

Hình chữ nhật kì thú

jumptozero

Cho hai hình chữ nhật, trong đó hình chữ nhật 1 có tỉ lệ hai cạnh là: \frac{a}{b} và hình chữ nhật 2 có tỉ lệ hai cạnh là: \frac{c}{d}, trong đó a,b,c,d lần lượt là các số nguyên dương. (tỉ lệ các cạnh ở đây ta hiểu là bề ngang trên bề dọc)

Vì đây là các hình chữ nhật kì thú nên chúng có thể tuỳ biến thay đổi kích thước sao cho tỉ lệ giữa các cạnh trong một hình vẫn không thay đổi.

Yêu cầu: Bạn hãy thay đổi các hình chữ nhật trên sao cho, khi đặt hình chữ nhật 2 vào hình chữ nhật 1 thì diện tích hình chữ nhật 2 phải chiếm diện tích lớn nhất có thể, và tất cả các cạnh của hình chữ nhật 2 phải nằm trong (hoặc trùng) với các cạnh của hình chữ nhật 1. Và bạn hãy in ra tỉ lệ diện tích của phần còn lại (tức là phần không bị chiếm) so với hình chữ nhật 1, biết rằng, các hình được thay đổi kích thước nhưng không được thực hiện bất cứ phép xoay hình nào ! (Để hiểu rõ hơn yêu cầu bài toán, bạn có thể xem ví dụ minh hoạ)

Ps: Hình vuông là một trường hợp đặc biệt của hình chữ nhật

Input:

  • Dòng thứ nhất chứa số t(1\le t\le 50) - Thể hiện số lượng testcase

  • t dòng tiếp theo, mỗi dòng chứa 4 số nguyên dương 1\le a,b,c,d\le 1000

Output:

  • Ứng với mỗi testcase, in ra một phân số có dạng p\text{/}q, trong đó: p là số nguyên không âm và q số nguyên dương thoả mãn: gcd(p,q)=1.

Ví dụ:

Input:

3
9 8 10 2
8 8 4 2
4 8 9 4

Output:

31/40
1/2
7/9

Giải thích:

Minh hoạ ví dụ 2:

CSES - Forbidden Cities | Thành Phố Cấm

ngpin_04

n thành phố và m con đường giữa chúng. Kaaleppi hiện đang ở thành phố a và muốn đi du lịch đến thành phố b. Tuy nhiên, có một vấn đề: Kaaleppi gần đây đã cướp một ngân hàng ở thành phố c và không thể vào thành phố, bởi vì cảnh sát địa phương sẽ bắt được anh ta. Nhiệm vụ của bạn là kiểm tra xem có tuyến đường nào từ thành phố a đến thành phố b mà không đến thành phố c hay không.

Để bổ sung độ thách thức cho bài toán này, bạn phải xử lý q truy vấn trong đó a, bc khác nhau.

Input

Dòng đầu vào đầu tiên chứa ba số nguyên n, mq: số thành phố, đường và truy vấn. Các thành phố được đánh số 1, 2, \ldots, n.

Sau đó, có m dòng mô tả các con đường. Mỗi dòng chứa hai số nguyên ab: có một đường giữa thành phố ab. Mỗi con đường là hai chiều.

Cuối cùng, có q dòng mô tả các truy vấn. Mỗi dòng chứa ba số nguyên a, bc: có tuyến đường nào từ thành phố a đến thành phố b mà không đến thành phố c không?

Bạn có thể giả định rằng có một tuyến đường giữa hai thành phố bất kì.

Output

Đối với mỗi truy vấn, in YES nếu có một tuyến đường như vậy và NO nếu ngược lại.

Constraints

  • 1 \leq n \leq 10 ^ 5
  • 1 \leq m \leq 2 \cdot 10 ^ 5
  • 1 \leq q \leq 10 ^ 5
  • 1 \leq a, b, c \leq n

Example

Input:

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

Output:

YES  
NO  
YES

Ví dụ 001

emtapcode

Tính tổng 2 số

Dữ liệu

  • Dòng 1: số a
  • Dòng 1: số b

Kết quả:

  • Tổng của 2 số

Input

4
5

Output

9

Nguồn: ABC