Cánh diều - SUBSTR - Đếm số lần xuất hiện xâu con

DKingQA, Flower_On_Stone

Một xâu ~A~ được gọi là xâu con của xâu ~B~ nếu các kí tự của xâu ~A~ được xuất hiện liên tiếp trong xâu ~B~. Ví dụ ~“apple”~, ~“appl”~, ~“pple”~, ~“ple”~ là xâu con của xâu ~“apple”~; nhưng xâu ~“ppal”~ không là xâu con của xâu ~“apple”~.

Yêu cầu: Cho xâu ~B~ và xâu ~A~; Đếm số lần xuất hiện không giao nhau của xâu ~A~ trong xâu ~B~.

Input:

Dòng đầu ghi xâu ~B~.

Dòng thứ hai ghi xâu ~A~.

Các xâu chỉ gồm kí tự latin viết thường không chứa dấu cách. Các xâu có độ dài không quá ~100~.

Output:

Một số nguyên là số lần xuất hiện của xâu ~A~ trong ~B~

Ví dụ:

Sample Input

aaa
aa

Sample Output

1

Doraemon và những chú khỉ khá là không liên quan

zipdang04, thenymphsofdelphi

Trong lúc Doraemon và những người bạn vẫn còn vui vẻ dưới ánh nắng tươi vàng trong một tiết trời hè nóng nực bên bãi biển tươi xanh thơm ngát mùi muối và những cánh chim trên cao bay dập dờn, dập dờn báo hiệu một mùa thu sắp đến và kết thúc một chuỗi ngày hè nóng nực nhưng cực kì đẹp đẽ và vui tươi thì ở phía bên kia xa xăm của hòn đảo tươi đẹp, dưới những tán cây dừa, một đàn khỉ nhí nhố gồm ~N~ chú đang háo hức xách cặp đến trường để đón lễ khai giảng nửa năm học mới 2019,5 - 2020.

Nhưng đâu phải chú nào cũng có tốc độ ngang nhau nên có chú đến sớm và có chú đến muộn và không có chú nào đến cùng thời điểm. Biết rằng khi chú thứ ~i~ đến thì có ~A_i~ chú khỉ khác có mặt trong lớp (tính cả chú thứ ~i~). Hiệu trưởng kiêm giáo viên chủ nhiệm đã nhờ bác bảo vệ xây dựng lại thứ tự đến trường của các chú khỉ để có biện pháp xử lí thích đáng với những chú khỉ đi trễ.


Input

Dòng đầu tiên chứa một số ~N~ là sĩ số của lớp ~(1 \le N \le 10^6)~.

~N~ dòng tiếp theo, dòng thứ ~i~ chứa một số duy nhất ~A_i~ ~(1 \le A_i \le N)~.


Output

Một dòng duy nhất gồm ~N~ số, số thứ ~i~ là thứ tự đến trường của các chú khỉ ~i~.


Ví dụ

Input:

6
5 4 2 1 6 3

Output:

4 3 6 2 1 5

Trò chơi với robot

Small

Trên lưới ô vuông gồm ~𝑚~ dòng và ~𝑛~ cột. Các dòng được đánh số từ 1 đến ~𝑚~ từ trên xuống dưới, các cột được đánh số từ 1 đến ~𝑛~ từ trái sang phải. Ô nằm giao giữa dòng ~𝑖~ và cột ~𝑗~ gọi là ô (~𝑖,𝑗~). Ban đầu, tại thời điểm 0, máy tính sẽ đặt ~𝑘~ robot trên lưới, robot thứ ~𝑟~ (~𝑟 =1,2, … , 𝑘~) được đặt ở ô (~𝑥_𝑟, 𝑦_𝑟~), các ô khác của lưới có thể đặt vật cản hoặc không. Mỗi đơn vị thời gian, người chơi phải điều khiển di chuyển một số con robot trong ~𝑘~ robot (có thể không điều khiển con nào). Robot chỉ thực hiện di chuyển sang một trong các ô kề cạnh hoặc kề đỉnh với ô robot đang đứng và ô đó không có vật cản, việc di chuyển này mất đúng một đơn vị thời gian.

Nhiệm vụ của người chơi là di chuyển để ~𝑘~ robot gặp nhau là sớm nhất, ~𝑘~ robot được gọi là gặp nhau nếu chúng cùng đứng trong một ô. Để trò chơi thêm thú vị, nếu ô (~𝑖,𝑗~) có vật cản thì ở thời điểm ~𝑑_{𝑖𝑗}~ vật cản sẽ biến mất và robot có thể đi vào ô (~𝑖,𝑗~) tính từ thời điểm ~𝑑_{𝑖j}~

Dữ liệu

  • Dòng đầu tiên chứa 3 số ~𝑚, 𝑛, 𝑘~ (~𝑚 × 𝑛 ≤ 5000~);
  • Dòng thứ ~𝑖~ trong ~𝑚~ dòng tiếp theo chứa ~𝑛~ số nguyên, số thứ ~𝑗~ trong dòng nhận giá trị 0 mô tả ô (~𝑖,𝑗~) không có vật cản, hoặc -1 mô tả ô (~𝑖,𝑗~) có đặt robot, hoặc một số nguyên dương ~𝑑_{𝑖𝑗}~ mô tả ô (~𝑖,𝑗~) có vật cản và ~𝑑_{𝑖𝑗}~ là thời điểm vật cản ở ô đó biến mất (~𝑑_{𝑖𝑗} ≤ 10^9~).

Kết quả • Gồm một dòng chứa một số nguyên là thời điểm sớm nhất mà ~𝑘~ robot gặp nhau, nếu không tồn tại cách di chuyển ghi -1.

Sample input

3 4 2
-1 0 3 0
19 9 9 0
0 0 0 -1

Sample output

3

Ràng buộc

  • Có 25% số lượng test ứng với 25% số điểm thỏa mãn điều kiện: ~𝑘 = 2~ và không có ô nào đặt vật cản;
  • Có 25% số lượng test khác ứng với 25% số điểm thỏa mãn điều kiện: ~𝑘 ≤ 5~ và không có ô nào đặt vật cản;
  • Có 25% số lượng test ứng với 25% số điểm thỏa mãn điều kiện: ~𝑘 = 2~;
  • Có 25% số lượng test còn lại ứng với 25% số điểm thỏa mãn điều kiện: ~𝑘 ≤ 5~.

Giả thuyết Goldbach (THTB Đà Nẵng 2022)

Small

Bài 3: Giả thuyết Goldbach

.

[enter link description here][1]

Saba1000kg

CaiWinDao

Cho đồ thị vô hướng gồm ~N~ đỉnh và ~E~ cạnh. Xét ~P~ đồ thị con trong đồ thị đó, tập đỉnh của mỗi đồ thị con là một tập con trong tập đỉnh của đồ thị gốc, và tập cạnh của đồ thị con chính là tập tất cả các cạnh nối hai đỉnh bất kỳ trong tập đỉnh con đó. Hãy đếm xem những đồ thị con đó có bao nhiêu thành phần liên thông.


Input

Dòng đầu tiên chứa số ba nguyên ~N~, ~E~ và ~P~ ~\left(1\leq N, P\leq 10^5, 0\leq E\leq 10^5\right)~.

~E~ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương ~u~ và ~v~ (~u\neq v~) thể hiện một cạnh nối trực tiếp giữa hai đỉnh ~u~ và ~v~ trong đồ thị.

~P~ dòng tiếp theo mô tả các đồ thị con của đồ thị đã cho. Mỗi dòng bắt đầu bằng số lượng đỉnh trong tập đỉnh con và theo sau bởi các đỉnh tương ứng.

Tổng kích thước của các tập đỉnh con không vượt quá ~10^5~.


Output

Gồm ~P~ dòng, mỗi dòng chứa một số nguyên là số thành phần liên thông trong đồ thị con tương ứng.


Ví dụ:

Input:

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

Output:

2
1
1

Input:

5 1 1
1 2
5 5 4 3 2 1

Output:

4

Nguồn bài: CERC 2019

Khoảng cách lớn nhất

PhanDinhKhoi

Khôi được cho ~N~ điểm trên hệ trục tọa độ ~Oxy~. Mỗi điểm này luôn nằm trên trục ~Ox~ hoặc ~Oy~.

Khôi muốn tìm khoảng cách lớn nhất giữa hai điểm bất kỳ trong ~N~ điểm trên. Bạn hãy giúp Khôi tính khoảng cách trên.

Biết rằng khoảng cách giữa điểm ~A~ tọa độ ~(xa,ya)~ và điểm ~B~ tọa độ ~(xb,yb)~ là ~ \sqrt{(xa-xb)^2+(ya-yb)^2} ~

Input

  • Dòng đầu tiên chứa số nguyên dương ~N~ ~\ (2\leq N \leq 10^6)~
  • ~N~ dòng tiếp theo, mỗi chứa 2 số nguyên ~xi,yi~ ~(-10^9 \leq xi,yi \leq 10^9)~ - là tọa độ điểm thứ ~i~

Output

  • Khoảng cách lớn nhất giữa hai điểm bất kỳ. Kết quả chêch lệch không quá ~10^{-6}~

Sample Input 1

4
-1 0
1 0
0 1
0 -1

Sample Output 1

2.000000

Tổng các chữ số chia hết cho D(*)

jumptozero

Tìm số các số nguyên dương từ ~1~ đến ~K~ thỏa mãn tổng các chữ số của nó là bội của ~D~.

Vì đáp án có thể lớn nên cần lấy mod ~10^9+7~ trước khi in ra.

Input:

  • Dòng thứ nhất chứa số nguyên ~K(1<K<10^{10000})~

  • Dòng thứ hai chứa số nguyên ~D(1\le D\le 100)~

Output:

  • In ra kết quả cần tìm sau khi đã lấy mod ~10^9+7~

Ví dụ:

Input:

30
4

Output:

6

Giải thích: Có ~6~ số từ ~1~ đến ~30~ thỏa mãn yêu cầu bài toán đó là ~4,8,13,17,22,26~.

Nguồn: Tham khảo từ Atcoder

Cánh diều - Vacxin (T85)

DKingQA, Flower_On_Stone, habelle

Để thử nghiệm lâm sàng vacxin mới ở giai đoạn 1, người ta cần tuyển những người trong độ tuổi từ ~18~ đến ~64~ tuổi và thoả mãn điều kiện ~18.5~ ~<=~ cân nặng/(chiều cao)^2 ~<= 22.9~.

Theo tập hồ sơ nhận được từ những người tình nguyện hãy đưa ra màn hình số người sẽ được xét để tham gia thử nghiệm. Số liệu về tuổi, cân nặng ~(kg)~ và chiều cao ~(m)~ của mỗi hồ sơ nhập vào từ bàn phím, mỗi số trên một dòng. Nhập tuổi bằng ~0~ để kết thúc tập hồ sơ.

Input:

Dữ liệu gồm nhiều bộ test, mỗi bộ gồm 3 dòng:

Dòng đầu ghi số tuổi, giá trị tuổi trong ~[1,150]~

Dòng 2 ghi số cân nặng, giá trị số thực

Dòng 3 ghi chiều cao, giá trị số thực

Output:

Ghi một số nguyên là số lượng người được xét

Ví dụ:

Sample Input

19 
54 
1.61 
21 
30 
1.7 
0

Sample Output

1

Sửa điểm

nvatuan

Bạn là một hacker chuyên nghiệp, hiện tại đã một cách thành công xâm nhập vào cơ sở dữ liệu nơi chứa điểm của bạn. Điểm của bạn là một danh sách gồm ~N~ số thực, có giá trị trong đoạn ~[0.0, 10.0]~ và chỉ có một chữ số ở hàng thập phân.

Trong khả năng của mình, bạn có thể sửa một số trong ~N~ số đó mà không bị phát hiện. Hỏi, tổng điểm sau khi đã sửa cao nhất có thể là bao nhiêu?

Lưu ý, không thể sửa một điểm quá ~10.0~ hoặc thấp hơn ~0.0~.

Input
  • Dòng đầu tiên chứa một số nguyên dương ~N~ ~(1 \leq N \leq 10^5)~
  • Dòng thứ hai chứa ~N~ số thực cách nhau bởi 1 ký tự khoảng trống, có giá trị trong đoạn ~[0.0, 10.0]~ và chỉ có một chữ số ở phần thập phân.
Output

Gồm một dòng, trên đó có một số thực là tổng điểm cao nhất có thể sau khi sửa 1 con điểm. Đáp án sẽ được chấp nhận đúng nếu output của bạn và output của bộ test lệch nhau không quá ~0.0001~.

Sample Input
Input 1
3
10.0 10.0 8.0
Output 1
30.0

Bạn sẽ sửa con ~8.0~ duy nhất của mình lên ~10.0~. Cho ra tổng điểm là ~30.0~.

Input 2
1
10.0
Output 1
10.0

Bạn không cần sửa gì cả.

giaoxu06

PhanDinhKhoi

Nhập ~n~. Hãy đếm có bao nhiêu số tự nhiên đối xứng có độ dài ~2n + 1~ có tổng các chữ số chia hết cho 10.

Input

  • ~n \leq 30~.

Output

  • Kết quả tìm được

Input

1

Output

9

Nguồn: SKY

Phân số nhỏ nhất (THTA Vòng sơ loại 2022)

Flower_On_Stone

Cho ba số tự nhiên ~A, B, C~. Từ ba số đó, hãy tạo ra một phân số nhỏ nhất có thể. In ra tổng của tử số và mẫu số của phân số nhỏ nhất đã được tối giản.

Input

  • Ba tự nhiên ~A, B, C~ ~(0 < A, B, C \leq 1000)~, mỗi số trên một dòng.

Output

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

Example

Sample input

3
2
4

Sample output

3

Note

Những phân số có thể tạo ra: ~\dfrac{3}{2}; \dfrac{3}{4}; \dfrac{2}{3}; \dfrac{2}{4}; \dfrac{4}{3}; \dfrac{4}{2}~

Phân số bé nhất là ~\dfrac{2}{4} = \dfrac{1}{2}~

Vậy kết quả là ~1 + 2 = 3~

CSES - Flight Discount

edatnvt

Nhiệm vụ của bạn là tìm một lộ trình bay rẻ nhất từ Syrjälä đến Metsälä. Bạn có thể giảm nửa giá một chuyến bay bất kì bằng một phiếu giảm giá. Tuy nhiên, bạn chỉ có thể sử dụng phiếu đó đúng một lần.

Input

Dòng đầu gồm hai số ~n~ và ~m~: số thành phố và số chuyến bay. Các thành phố được đánh số ~1, 2, ..., n~. Thành phố 1 là Syrjälä, và thành phố ~n~ là Metsälä.

~m~ dòng tiếp theo mô tả các chuyến bay. Mỗi dòng gồm ba số ~a~, ~b~ và ~c~: chuyến bay bắt đầu ở thành phố ~a~, kết thúc ở thành phố ~b~ có giá tiền là ~c~. Mỗi chuyến bay đều là hai chiều.

Giả sử ta luôn có thể đi từ Syrjälä đến Metsälä.

Output

In ra số tiền của lộ trình bay rẻ nhất từ Syrjälä đến Metsälä.

Khi bạn sử dụng phiếu giảm giá cho một chuyến bay với giá tiền ~x~, giá tiền của chuyến bay đó sẽ trở thành ~\lfloor x/2 \rfloor~ (~\lfloor x \rfloor~ là phép làm tròn xuống).

Giới hạn

  • ~2 \le n \le 10^5~
  • ~1 \le m \le 2 \cdot 10^5~
  • ~1 \le a,b \le n~
  • ~1 \le c \le 10^9~

Ví dụ

Sample input:

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

Sample output:

2

[Assembly_Training] Loop 5

jumptozero

Input

  • Một dòng duy nhất chứa xâu ~s~ chỉ gồm các kí tự la tinh thường, độ dài xâu ~s~ không quá ~100~

Output:

  • In ra ~5~ dòng, mỗi dòng chứa xâu ~s~ đã cho

Ví dụ:

Input:

abc

Output:

abc
abc
abc
abc
abc

CSES - Planets Queries II

zipdang04

Bạn đang chơi một trờ chơi. Trong trò chơi đó có ~n~ hành tinh. Mỗi hành tinh có một cổng dịch chuyển tức thời, đưa bạn từ hành tinh này đến hành tinh khác (hoặc đến chính hành tinh bạn đang đứng)

Nhiệm vụ của bạn là trả lời ~Q~ truy vấn, mỗi truy vấn bạn sẽ phải trả lời một câu hỏi như sau: Khi bạn xuất phát tại hành tinh thứ ~a~ và kết thúc tại hành tinh ~b~, bạn sẽ cần đi qua ít nhất bao nhiêu cổng thời gian?

Input

  • Dòng thứ nhất gồm hai số ~n~ và ~Q~, thể hiện số lượng hành tinh và số lượng truy vấn bạn cần trả lời. Các hành tinh được đánh số từ ~1 \rightarrow n~;
  • Dòng thứ hai gồm có ~n~ số nguyên ~t_1, t_2, t_3,~ ~...~ ~, t_n~. ~t_i~ thể hiện điểm đến của cánh cửa dịch chuyển tại hành tinh thứ ~i~ (lưu ý vẫn có thể xảy ra ~t_i = i~);
  • ~Q~ dòng cuối cùng, mỗi dòng thể hiện một truy vấn gồm hai số ~a~ và ~b~, thể hiện câu hỏi rằng bạn sẽ cần đi ít nhất bao nhiêu cổng dịch chuyển để đi từ hành tinh ~a~ đến hành tinh ~b~.

Output

  • Đối với mỗi truy vấn, in ra đáp án của từng truy vấn: số lượng cổng dịch chuyển ít nhất sẽ phải đi qua;
  • Nếu không tìm được đáp án, in ra ~-1~.

Giới hạn:

  • ~1 ≤ n, Q ≤ 2\times10^5~
  • ~1 ≤ t_i ≤ n~
  • ~1 ≤ a, b ≤ n~

Example

Input:

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

Output:

1
2
-1

Tổng chẵn

admin

Nhập vào một dãy ~N~ số nguyên ~A_1,A_2,...,A_N~ (~N ≤ 10000, |A_i| ≤ 10^9~).

Hãy in ra màn hình tổng các phần tử có giá trị chẵn.

Dữ liệu vào:

  • Dòng đầu tiên chứa số ~N~
  • N dòng tiếp theo chứa ~N~ số nguyên ~A_1,A_2,...,A_N~.

Kết quả:

  • Tổng các phần tử có giá trị chẵn của dãy số.

Sample Input

7
7 
-6 
-4
19
22
51
82

Sample Output

94

CSES - Tree Distances I

Elektrikar

Bạn được cho một cây có ~n~ nút.

Nhiệm vụ của bạn là xác định khoảng cách xa nhất từ mỗi nút đến một nút khác.

Input

Dòng đầu tiên chứa một số nguyên ~n~ : số lượng nút. Các nút được đánh số ~1,2,...,n~.

Tiếp theo là ~n−1~ dòng mô tả các cạnh. Mỗi dòng chứa hai số nguyên ~a~ và ~b~ : có một cạnh nối hai nút ~a~ và ~b~.

Output

In ra ~n~ số nguyên: với mỗi nút ~1,2,...,n~, khoảng cách xa nhất đến một nút khác.

Constraints

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

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

    Example

    Input
    5
    1 2
    1 3
    3 4
    3 5
    Output
    2 3 2 3 3
  • K-Amazing Numbers

    jumptozero
    • Cho mảng ~a~ gồm ~n~ số nguyên dương

    • Gọi ~q_k~ là số nguyên nhỏ nhất có mặt ở tất cả các đoạn con (gồm các phần tử liên tiếp) có kích thước là ~k~.

    • Nếu không tồn tại ~q_k~ thỏa mãn điều trên thì ~q_k=-1~.

    Nhiệm vụ của chúng ta là in ra tất cả các giá trị ~q_i~ với ~1\le i\le n~.

    Input:

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

    • Tiếp theo là ~t~ block, mỗi block có dạng như sau:

      • Dòng thứ nhất chứa số nguyên ~n(1\le n\le 3.10^5)~

      • Dòng thứ hai chứa số nguyên ~a_1,a_2,...,a_n~ với ~1\le a_i\le n~

    (Biết rằng: Tổng các giá trị của ~n~ ở tất cả testcase không quá ~3.10^5~)

    Output:

    • ứng với mỗi testcase ,in ra các giá trị ~q_1,q_2,...,q_n~ tương ứng

    Ví dụ:

    Input:

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

    Output:

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

    Nguồn: Cốt Phốt

    Tổng các chữ số (THTB Hòa Vang 2022)

    kid2201

    Bài 1: Tổng các chữ số

    .

    [enter link description here][1]

    Biến đổi

    PhanDinhKhoi

    Cho trước hai dãy số, dãy số ~a~ gồm ~n~ số nguyên và dãy số ~b~ gồm ~m~ số nguyên.

    Bạn có thể làm hành động ~1~ bất kỳ số lần và hành động ~2~ bất kỳ số lần:

    • Hành động ~1~: Chọn phần tử ~i~ của dãy ~a~ ~(1 \leq i < n)~. Sau đó cộng ~a_{i+1}~ vào ~a_i~ và xóa phần tử thứ ~i+1~.

    • Hành động ~2~: Chọn phần tử ~i~ của dãy ~b~ ~(1 \leq i < m)~. Sau đó cộng ~b_{i+1}~ vào ~b_i~ và xóa phần tử thứ ~i+1~.

    Nhiệm vụ của của bạn là kiểm tra có cách nào để làm cho hai dãy số ~a~ và ~b~ giống hệt hau. Biết rằng nếu dãy ~a~ giống hệt dãy ~b~ thì độ dài của dãy ~a~ bằng độ dài của dãy ~b~ và với từng vị trí ~i~ của dãy ~a~ thì ~a_i~ = ~b_i~.

    Input

    • Dòng đầu tiên chứa số nguyên dương ~n \ (1 \leq n \leq 10^5)~ - là số phần tử của mảng a.
    • Dòng thứ hai chứa ~n~ số nguyên dương, số thứ ~i~ là ~a_i~ ~( a_i \leq 10^9)~
    • Dòng đầu ba chứa số nguyên dương ~m \ (1 \leq m \leq 10^5)~ - là số phần tử của mảng b.
    • Dòng thứ tư chứa ~m~ số nguyên dương, số thứ ~i~ là ~b_i~ ~( b_i \leq 10^9)~

    Output

    • Nếu có cách làm hai dãy giống nhau thì in ra độ dài lớn nhất mà hai dãy có thể có. Ngược lại in ra -1.

    Sample Input 1

    5
    11 2 3 5 7
    4
    11 7 3 7

    Sample Output 1

    3

    Sample Input 1

    2
    1 1
    1
    100

    Sample Output 1

    -1

    Cánh diều - PHOTOS - Các bức ảnh

    DKingQA

    Trong một hoạt động ngoại khoá của lớp, giáo viên chủ nhiệm đã chụp được n bức ảnh, các bức ảnh được lưu trên máy tính có kích thước tương ứng là d1, d2,…, dn (đơn vị Kb)

    Giáo viên dự định ghi một số đĩa CD làm phần thưởng cho học sinh. Đĩa CD mà giáo viên dùng chỉ có thể ghi tối đa W (đơn vị Kb). Vì tất cả các bức ảnh đều rất đẹp và thú vị nên giáo viên muốn lựa chọn các bức ảnh để ghi vào với tiêu chí càng nhiều bức ảnh được ghi vào đĩa CD càng tốt. Giáo viên còn băn khoăn và muốn biết số lượng tối đa các bức ảnh có thể ghi vào đĩa CD là bao nhiêu?

    Input:

    Dòng thứ nhất ghi hai số nguyên ~n, W~ ~(1 \le n\le 10^5; 0\le W\le 10^9)~

    Dòng thứ hai ghi ~n~ số ~d_1, d_2, …, d_n~

    Output:

    Ghi một số nguyên là số lượng ảnh tối đa có thể ghi vào đĩa.

    Ví dụ:

    Sample Input

    3 5
    1 2 3

    Sample Output

    2