Nguồn đề: Beginner Free Contest 31

Đề bài: https://drive.google.com/file/d/1QM7BhfqwVzq8jaE-hcR2eR7F-UU32i7t/view?usp=sharing

Lời giải: https://drive.google.com/file/d/1FqlW9e2JypBmYYHDhP6RZpkFk0iM0p7C/view?usp=sharing

Bài giải: https://drive.google.com/file/d/1yabVc6U-IA5zqXiQWGN17HSPlWrYe1O1/view?usp=sharing

Một cửa hàng A ban đầu có M món hàng đánh số từ 1 đến M. Món hàng thứ i có giá tiền là i đồng vàng. Cửa hàng này có một đặc điểm đặc biệt là không có hàng trong kho và cần mất một ngày để nhập hàng mới, tức là nếu một món hàng i được bán vào ngày hôm qua, thì đến tận ngày mai mới có thể bán tiếp món hàng có giá tiền tương ứng.

Sau nhiều thời gian dành dụm, Anh đã để dành được N đồng vàng. Anh quyết định sẽ dùng N đồng vàng, mỗi ngày mua quà ở cửa hàng A tặng cho crush của mình. "Mưa dầm thấm lâu", Anh muốn tặng quà cho crush nhiều ngày liên tục nhất có thể.

Tính số ngày liên tiếp mà Anh có thể mua quà cho crush mình.

Input

Dòng 1: T - số lượng test ~(1 ≤ T ≤ 10^4).~

T dòng tiêp theo, mỗi dòng chứa 2 số nguyên M, N ~ (1 ≤ M ≤ N ≤ 10^9). ~

Kết quả

Gồm T dòng, mỗi dòng chứa số nguyên là số ngày liên tục nhiều nhất mà ANh có thể mua quà tặng cho crush ứng với mỗi test case.

Sample Input

3
1 1
2 2
3 3

Sample Output

1
1 
2

Nguồn đề: Beginner Free Contest 24

Đề bài: https://drive.google.com/file/d/15Twi2BfkzcuK3jgO57Tbiw62-SNG1PnM/view?usp=sharing

Lời giải: https://drive.google.com/file/d/1EYgp2ui1N63-H-n1FGLTtTaRGzqXTetJ/view?usp=sharing

Bài giải: https://drive.google.com/file/d/15rfCyF76k7KJ8zbrbtdwjaLeHXu5HUWV/view?usp=sharing

Long đang trên đường đi học thì không may bị một kẻ xấu bắt nhốt vào trong một mê cung. Mê cung gồm n + 1 căn phòng xắp xếp nối tiếp nhau theo thứ tự phòng 1, phòng 2, ..., phòng n + 1. Long hiện đang ở phòng 1 và lối thoát ở phòng n + 1.

Giữa n + 1 căn phòng có n cánh cửa. Ban đầu tại thời điểm 0, tất cả cánh cửa đều đóng. Sau đó, cánh cửa thứ i sẽ chỉ mở ra mỗi ~a_i~ giây. Do Long khá nhanh nhẹn nên cậu có thể di chuyển giữa 2 căn phòng mà không mất thời gian nào.

Long bắt đầu di chuyển tại phòng 1 từ thời điểm 0. Câu hỏi đặt ra cho bạn là hãy tìm thời điểm sớm nhất mà Long sẽ thoát khỏi mê cung.

Input

Dòng 1: n - số lượng cánh cửa có trong mê cung ~(1 ≤ n ≤ 10^5).~

Dòng 2: n số nguyên ~a_i~ - cánh cửa thứ i sẽ mở ra mỗi ~a_i~ giây ~(1 ≤ a_i ≤ 10^9).~

Kết quả

In ra một số nguyên duy nhất là thời điểm sớm nhất mà Long sẽ thoát khỏi mê cung.

Sample Input 1

4
3 2 3 4

Sample Output 1

8

Sample Input 2

5
2 2 2 3 3

Sample Output 2

3

Sample Input 3

6
4 5 4 5 4 5

Sample Output 3

15

Sample Input 4

10
2 4 6 8 10 2 4 6 8 10

Sample Output 4

20

Giải thích

Ở ví dụ 1, Long sẽ thoát khỏi mê cung như sau:

• Long ở phòng 1 tại thời điểm 0, cửa 1 đóng, đợi qua 3 giây để cửa 1 mở, Long đi qua phòng 2.
• Long ở phòng 2 tại thời điểm 3, cửa 2 đóng, đợi qua 1 giây để cửa 2 mở, Long đi qua phòng 3.
• Long ở phòng 3 tại thời điểm 4, cửa 3 đóng, đợi qua 2 giây để cửa 3 mở, Long đi qua phòng 4.
• Long ở phòng 4 tại thời điểm 6, cửa 4 đóng, đợi qua 2 giây để cửa 4 mở, Lòng đi qua phòng 5 và thoát khỏi mê cung.

Vì tổng thời gian ít nhất cần để thoát mê cung là 8 giây nên ta in ra 8.

Nguồn đề: Free contest 126

Đề bài: https://drive.google.com/file/d/1gpMCqTKMpHQCAV7_OmOSVQnWuxSTzobn/view?usp=sharing

Lời giải: https://drive.google.com/file/d/1rCpSEQ8Y8eyXVfkHjsgT4yFWkuK1DSpf/view?usp=sharing

Bài giải: https://drive.google.com/file/d/1PoXm1kEXub1YQ9gIqCGdzuqhxo00S-fz/view?usp=sharing

Bạn được cho một xâu gồm N kí tự liền kề nhau. Mỗi kí tự có thể là kí tự 'a', 'b' hoặc '?'. Ta có thể thay thế những kí tự '?' trong xâu ban đầu thành kí tự 'a' hoặc kí tự 'b'.

Giả sử chúng ta đã thay thế hết các kí tự '?', thì với mỗi cặp hai kí tự liền kề nhau trong xâu ban đầu, chúng ta định nghĩa giá trị của cặp đó như sau:

• 'aa' = 0
• 'ab' = 1
• 'bb' = 0
• 'ba' = -1

Tổng giá trị của một xâu là tổng giá trị của n - 1 cặp hai kí tự liền kề.

Bài toán đặt ra cho bạn là trong tất cả các cách thay thế những kí tự '?' trong xâu ban đầu, bạn hãy in ra tổng giá trị lớn nhất có thể.

Input

Dòng 1: n độ dài của xâu ~(1 ≤ n ≤ 10^6).~

Dòng 2: Một xâu gồm n kí tự.

Kết quả

In ra một số nguyên duy nhất là tổng giá trị lớn nhất có thể trong tất cả các cách thay thế.

Sample Input 1

5
aabbb

Sample Output 1

1

Sample Input 2

6
a?a?bb

Sample Output 2

1

Sample Input 3

5
b????

Sample Output 3

0

Giải thích

Ở test ví dụ 1, ta có từng cặp xâu liên tiếp là 'aa', 'ab', 'bb', 'bb', tổng giá trị của xâu là 0 + 1 + 0 + 0 = 1

Ở test ví dụ 2, ta có thể thay thế các kí tự '?' thành xâu ababbb. Những cặp xâu liên tiếp là 'ab', 'ba', 'ab', 'bb', 'bb', tổng giá trị của xâu là 1 + (-1) + 1 + 0 + 0 = 1

Ở test ví dụ 3, ta có thể thay thế các kí tự '?' thành xâu bbbbb, tổng giá trị của xâu là 0.

Nguồn đề: Beginner Free Contest 28

Đề bài: https://drive.google.com/file/d/1ZqYBoUEHEFYfkRQBgMNRVJbAzo91utlK/view?usp=sharing

Lời giải: https://drive.google.com/file/d/1Oc4FkVQeGOctovtnjWJ2aB9eO18meGGO/view?usp=sharing

Đất nước X xinh đẹp có n thành phố, đánh số từ 1 đến n. Các thành phố được nối với nhau bởi hệ thống giao thông gồm m tuyến đường hai chiều, mỗi tuyến đường nối trực tiếp một cặp thành phố, đảm bảo luôn có đường đi lại giữa hai thành phố bất kì trong nước (trực tiếp hoặc đi qua một số thành phố khác). Giữa hai thành phố bất kì không có quá một tuyến đường nối trực tiếp.

Có tổng cộng b kho lương thực đặt trên khắp cả nước, mỗi kho nằm ở một thành phố khác nhau. Để bảo vệ đất nước khỏi quân xâm lược, thủ tướng đã chọn ra r thành phố khác nhau để đặt trại quân sự.

Để giải quyết vấn đề lương thực cho quân doanh, với mỗi thành phố được đặt trại quận sự, nhiệm vụ của bạn là tính toán số tuyến đường ít nhất cần đi nếu xuất phát từ thành phố đó đến một kho lương thực bất kì.

Input

Dòng 1: Gồm 4 số nguyên n, m, b, r ~(2 ≤ n ≤ 5.10^5, 1 ≤ m ≤ 5.10^5, 1 ≤ b, r ≤ n).~

Dòng 2: Gồm b số nguyên ~b_i~ là chỉ số của các thành phố đặt kho lương thực ~(1 \leq b_i \leq n)~

Dòng 3: Gồm r số nguyên ~r_i~ là chỉ số của các thành phố đặt trại quân sự ~(1 \leq r_i \leq n)~

m dòng tiếp theo, mỗi dòng gồm 2 số nguyên u và v thể hiện có một tuyến đường 2 chiều nối trực tiếp hai thành phố u và v

Kết quả

In ra r số nguyên trên cùng một dòng là kết quả tính được của các thành phố đặt trại quân sự theo thứ tự của dữ liệu.

Sample Input

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

Sample Output

1 2 1

Giải thích

• Thành phố 1: 1->2
• Thành phố 4: 4->3
• Thành phố 5: 5->4->3

Mạnh Đạt mới được tặng một chiếc đồng hồ nhân dịp sinh nhật giống chiếc đồng hồ ở trên. Đạt bèn chạy đi khoe 03010v0 về chiếc đồng hồ mới của mình với đầy sự tự hào. Nhưng thật không may, trên đường đi Đạt lại làm rơi chiếc đồng hồ. Chiếc đồng hồ dừng hoạt động và Đạt nhìn thấy đồng hồ lúc bấy giờ là 11:21:80 thay vì 08:12:11. Đạt chợt nhận ra mình đã nhìn lộn ngược chiếc đồng hồ. Vì là một cao thủ toán học, Đạt liền nảy ra một bài toán để đố 03010v0 đó là: số hiển thị trên đồng hồ có phải là một số nguyên tố và khi số đó bị đảo ngược thì nó còn là số nguyên tố nữa hay không.

Có vài điều cần chú ý, một vài số khi bị lộn ngược sẽ không có ý nghĩa như: 3, 4, 7, một số chữ số thay đổi giá trị là 6, 9, một số chứ số giữ nguyên giá trị là 0, 1, 2, 5, 8.

Ví dụ: 18161 -> 19181, 2589 -> 6852.

Hãy giúp 03010v0 trả lời câu hỏi của Đạt nhé.

Input

Dòng 1: số nguyên T - số lượng testcase ~(1 ≤ T ≤ 20).~

T dòng tiếp theo : số nguyên n - số hiển thị trên đồng hồ ~(1 ≤ n ≤ 10^{18}).~

Output

T dòng - mỗi dòng in ra "YES" nếu n là số nguyên tố nguyên tố và số lộn ngược của n cũng là số nguyên tố, ngược lại in ra "NO".

Sample Input

3
151
23
1811

Sample Output

YES
NO
YES

Nguồn đề: Beginner Free Contest 12

Đề bài: https://drive.google.com/file/d/1dp4k6EWJc6z8S-WgVTAr8J3NajsmVwDK/view?usp=sharing

Bài giải: https://drive.google.com/file/d/1mV3Lac3xh3i_hEKD1wKwTRrW7rgjIg5q/view?usp=sharing

Sau khi chinh phục mọi đỉnh cao về lập trình thi đấu toàn thế giới, Hải đã nghĩ đến việc rửa tay gác kiếm. Hải được Long chỉ điểm rằng có một đại lục màu mỡ mang tên Topcoder và liền đến đó xem thử tình hình. Đại lục được xem như là một mặt phẳng tọa độ, trên đó có một vườn cây N cây hoa Đăng Tiêu mọc lên, cây thứ i mọc ở ô ~(x_i, y_i)~.

Với sở thích code đẹp của Hải, anh nghĩ rằng mình nên dời một số cây đi và trồng lại vào một vị trí khác để N cây đó tạo thành một hàng dọc hoặc một hàng ngang trong đó các cây liên tiếp nhau và song song với hệ trục tọa độ. Việc di chuyển cây là vô cùng khó khăn và Hải chỉ có thể di chuyển tối đa một cây cùng lúc và mất 1 đơn vị thể lực để di chuyển cây đi một đơn vị. Hơn nữa, anh chỉ có thể di chuyển song song với hệ trục tọa độ.

Vì bận đi chơi nên Hải muốn nhờ các bạn giúp mình tìm các di chuyển cây trong vườn cây này sao cho lượng thể lực anh mất là nhỏ nhất có thể.

Input

Dòng 1: N số lượng cây hoa Đăng tiêu trong vườn cây ~(1 ≤ N ≤ 10^6).~

N dòng tiếp theo: mỗi dòng chứa 2 số nguyên ~x_i, y_i~ ~(-10^5 \leq x_i,y_i \leq 10^5)~ là tọa độ của cây thứ i.

Kết quả

Ghi ra một số nguyên duy nhất là lượng thể lực tối thiểu mà Hả cần để đạt được mong muốn của mình.

Sample Input 1

3
1 1
2 2
3 1

Sample Output 1

1

Sample Input 1

2 
1 1
1 3

Sample Output 1

1

Giải thích:

• Ở ví dụ 1: Có thể di chuyển cây ở vị trí (2, 2) sang vị trí (2, 1).

• Ở ví dụ 12: Có thể di chuyển cây ở vị trí (1, 1) sang vị trí (1, 2).

Nguồn đề: Free contest 126

Đề bài: https://drive.google.com/file/d/1eorQb6XwIPi2iXXfYsqYsIPXebvAVhTl/view?usp=sharing

Lời giải: https://drive.google.com/file/d/11SIPA7TjUz0hofqUYeP99HQXYZzUSmmj/view?usp=sharing

Bài giải: https://drive.google.com/file/d/1aWuYyfQa8m-3R-Nugfr9eep0bbU_1wr1/view?usp=sharing

Cho một mảng a chứa các số được đánh thứ tự từ 1 đến n. Định nghĩa số k của một mảng là số nhỏ nhất xuất hiện trong tất cả các mảng con có độ dài k (Mảng con có độ dài k là một phần của mảng a và chứa k phần tử liên tiếp của nó). Nếu không có số nào xuất hiện trong tất cả các mảng con có độ dài k thì số k là -1.

Với k từ 1 đến n, tìm số k của mảng a.

Input

Dòng 1: T số test ~(1 ≤ T ≤ 50).~

Dòng đầu tiên của mỗi test chứa số n - độ dài của mảng a ~(1 \leq n \leq 10^3). ~

Dòng thứ hai của test chứa n số nguyên của mảng a: ~a_1, a_2, a_3, ... , a_n ~ ~(1 \leq a_i \leq n).~

Kết quả

Với mỗi test, in ra n số với số thứ i là số i của mảng.

Sample Input

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

Sample Output

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