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.

Cánh Diều - LEN - Độ dài xâu

Flower_On_Stone, tanprodium

Cho một xâu kí tự chỉ gồm các kí tự latin viết thường, hoa và dấu cách. Hãy đếm xem trong xâu có bao nhiêu kí tự (độ dài xâu).

Input

-Một dòng ghi xâu kí tự, có độ dài không quá ~10^6~.

Output

-Một số nguyên là độ dài xâu.

Ví dụ

Sample Input

I love Python

Sample Output

13

CSES - Distinct Routes II | Lộ trình phân biệt II

kitsune

Một trò chơi bao gồm ~n~ phòng và ~m~ cổng dịch chuyển tức thời. Vào đầu mỗi ngày, bạn bắt đầu ở phòng ~1~ và bạn phải đến phòng ~n~.

Bạn có thể sử dụng tối đa mỗi cổng dịch chuyển tức thời một lần trong trò chơi. Bạn muốn chơi trò chơi trong chính xác ~k~ ngày. Mỗi khi bạn sử dụng bất kỳ cổng dịch chuyển tức thời nào, bạn phải trả một đồng xu. Số đồng xu tối thiểu bạn phải trả trong ~k~ ngày nếu bạn chơi tối ưu là bao nhiêu?

Input

  • Dòng đầu vào đầu tiên có ba số nguyên ~n~, ~m~ và ~k~: số lượng phòng, số lượng cổng dịch chuyển tức thời và số ngày bạn chơi trò chơi. Các phòng được đánh số ~1, 2, \ldots, n~.
  • Sau này, có ~m~ dòng mô tả các cổng dịch chuyển tức thời. Mỗi dòng có hai số nguyên ~a~ và ~b~: có một cổng dịch chuyển tức thời từ phòng ~a~ đến phòng ~b~.
  • Không có hai cổng dịch chuyển tức thời có phòng bắt đầu và kết thúc giống nhau.

Output

  • Đầu tiên in một số nguyên: số đồng xu tối thiểu bạn phải trả nếu bạn chơi tối ưu. Sau đó, in ~k~ mô tả lộ trình theo ví dụ. Bạn có thể in bất kỳ giải pháp hợp lệ nào.
  • Nếu không thể chơi trò chơi trong ~k~ ngày, chỉ in ~-1~.

Constraints

  • ~2 \leq n \leq 500~
  • ~1 \leq m \leq 1000~
  • ~1 \leq k \leq n - 1~
  • ~1 \leq a, b \leq n~

Example

Sample input

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

Sample output

6
4
1 2 4 8
4
1 3 5 8

Fibo đầu tiên

admin

"Một đôi thỏ (gồm một thỏ đực và một thỏ cái) cứ mỗi tháng đẻ được một đôi thỏ con (cũng gồm một thỏ đực và thỏ cái); một đôi thỏ con, khi tròn 2 tháng tuổi, sau mỗi tháng đẻ ra một đôi thỏ con, và quá trình sinh nở cứ thế tiếp diễn. Hỏi sau n tháng có bao nhiêu đôi thỏ, nếu đầu năm (tháng Giêng) có một đôi thỏ sơ sinh

enter image description here

Trong hình vẽ trên, ta quy ước:

  • Cặp thỏ nâu là cặp thỏ có độ tuổi 1 tháng.
  • Cặp thỏ được đánh dấu (màu đỏ và màu xanh) là cặp thỏ có khả năng sinh sản.

Nhìn vào hình vẽ trên ta nhận thấy:

  • Tháng Giêng và tháng Hai: Chỉ có 1 đôi thỏ.
  • Tháng Ba: đôi thỏ này sẽ đẻ ra một đôi thỏ con, do đó trong tháng này có 2 đôi thỏ.
  • Tháng Tư: chỉ có đôi thỏ ban đầu sinh con nên đến thời điểm này có 3 đôi thỏ.
  • Tháng Năm: có hai đôi thỏ (đôi thỏ đầu và đôi thỏ được sinh ra ở tháng Ba) cùng sinh con nên ở tháng này có 2 + 3 = 5 đôi thỏ.
  • Tháng Sáu: có ba đôi thỏ (2 đôi thỏ đầu và đôi thỏ được sinh ra ở tháng Tư) cùng sinh con ở thời điểm này nên đến đây có 3 + 5 = 8 đôi thỏ.

Khái quát, nếu ~n~ là số tự nhiên khác 0, gọi ~f(n)~ là số đôi thỏ có ở tháng thứ ~n~, ta có:

  • Với ~n = 1~ ta được ~f(1) = 1.~
  • Với ~n = 2~ ta được ~f(2) = 1.~
  • Với ~n = 3~ ta được ~f(3) = 2.~
  • Do đó với ~n > 2~ ta được: ~f(n) = f(n-1) + f(n-2)~.

Nguồn: wikipedia

Dãy số trên gọi là dãy số ~Fibonacci~ và được định nghĩa như sau:

  • ~F_1 = F_2 = 1;~
  • ~…~
  • ~F_n = F_{n-2} + F_{n-1}~

Hãy viết chương trình in ~n~ số ~Fibonacci~ đầu tiên:

Dữ liệu vào:

  • Chứa duy nhất số ~n~ (~n≤90~)

Kết quả:

  • Chỉ một dòng ghi ~n~ số Fibonaci đầu tiên

Ví dụ:

Input

10

Output

1 1 2 3 5 8 13 21 34 55

Biểu thức nhân cộng

admin

Cho ~n~ số nguyên dương ~a_i,i=1..n~, bạn phải đặt giữa ~n~ số nguyên dương này ~2~ phép nhân và ~n-3~ phép cộng sao cho kết quả biểu thức là lớn nhất.

Ví dụ: với ~n=5~ và dãy ~a_i~ là ~4,7, 1, 5, 3~ thì bạn có thể có các biểu thức:

  • ~4 + 7 \times 1 + 5 \times 3~
  • ~4 \times 7 +1 + 5 \times 3~

Chú ý: Không được thay đổi thứ tự xuất hiện của ~a_i,i=1..n~ trong biểu thức thu được.

Dữ liệu

  • Dòng 1 chứa số nguyên dương ~n~ (~4 ≤ n ≤1.000~)
  • ~n~ dòng tiếp theo, dòng thứ ~i+1~ chứa số nguyên dương ~a_i~ (~1 ≤ a_i≤10.000,\ i=1..n~)

Kết quả

  • Ghi 1 số nguyên dương duy nhất là giá trị lớn nhất của biểu thức thu được.

Sample Input

5
4
7
1
5
3

Sample Output

44

Giải thích: Biểu thức thu được là: ~4 \times 7 +1 + 5 \times 3~

Mua Cô Ca

Small

Giữa giờ nghỉ chuyển tiết học Alice và Tôm tới ô tô mát bán nước giải khát để mua Cô ca. Không may trong máy không còn một lon Cô ca nào. Hai bạn quyết định chạy ra phố mua và dĩ nhiên chỉ cần một người đi là đủ. Trời nắng gắt và ai cũng ngại đi. Hai bạn quyết định chơi một trò chơi nhỏ và ai thua sẽ phải đi.

Trong tay Alice đang có một băng giấy gồm các ô vuông, mỗi ô được tô một trong 2 màu Đỏ (R) hoặc Xanh (B). Độ rộng băng giấy bằng độ rộng ô vuông. Hai người lần lượt cắt băng thành các đoạn độ dài (số ô trên đoạn) lớn hơn 0

Quy tắc chơi là hai người lần lượt đi, ai đến lượt mình đi chọn một đoạn có ô ở hai đầu khác màu nhau và cắt đoạn đó ở vị trí tùy chọn để nhận được 2 đoạn mỗi đoạn có độ dài lớn hơn 0.

Ai đến lượt đi nhưng không thể chọn được đoạn để cắt là thua và phải đi mua Cô ca.

Alice đi trước.

Cho trạng thái băng giấy. Hãy xác định Alice sẽ thắng hay thua và đưa ra thông báo tương ứng là Win hoặc Lose với giả thiết cả hai đều biết cách đi tối ưu.

Dữ liệu

  • Gồm một dòng chứa xâu ~s~ mô tả trạng thái ban đầu của băng giấy, ~s~ chỉ chứa các ký tự trong tập {R, B}, độ dài không vượt quá ~10^5~.

Kết quả

  • Đưa ra thông báo tương ứng tìm được.

Sample input

RBRB

Sample output

Win

Nguồn: Thầy Tùng

Hello, world ! (sample problem)

admin, stack_queue_4977

In ra dòng chữ:

Hello, world!

Gửi thư

admin

Vị Giám đốc công ty XYZ cần gửi một văn bản quan trọng tới một đối tác của mình. Văn bản là một xâu ~S~ các chữ cái la tinh in thường. Để bảo mật nội dung văn bản, ông Giám đốc gửi 2 bức thư. Bức thư thứ nhất là phần đầu ~Sb~ của xâu ~S~, bức thư thứ 2 là phần cuối ~Se~ của ~S~. Hai bức thư ~Sb~ và ~Se~ đảm bảo đầy đủ nội dung của ~S~, tuy nhiên có thể một phần cuối của ~Sb~ có thể được viết lặp lại trong phần đầu của ~Se~, song số kí tự được viết lặp lại không biết trước.

Ví dụ: với văn bản ~S=’truongnguyenduquannhat’~ tạo ra hai bức thư:

Sb=truongngueNdu
         ngueNduquanNhat=Se

~Sb=’truongnguyendu’~ và ~Se=’nguyenduquannhat’~

Yêu cầu: Cho hai xâu ~Sb~ và ~Se~, hãy xác định một xâu ~S~ có thể là nội dung của bức thư sao cho độ dài của xâu ~S~ là ngắn nhất.

Dữ liệu vào

  • Dòng đầu chứa xâu ~Sb~,
  • Dòng thứ hai chứa xâu ~Se~.

Mỗi xâu có độ dài không quá 250.

Kết quả

  • Ghi ra độ dài của xâu ~S~ tìm được.

Ví dụ

Input

truongnguyendu
nguyenduquannhat

Output

22

Nguồn: vn.spoj.com

Ngày tháng năm

admin

Viết chương trình nhập vào ba số nguyên biểu diễn ngày tháng năm, in ra ngày tháng năm dưới dạng ngay/thang/nam.

Dữ liệu vào

  • Ba số nguyên biểu diễn ngày tháng năm, mỗi số trên 1 dòng

Kết quả

  • In ra ngay/thang/nam

Sample Input

24 
9 
2020

Sample Output

24/9/2020

Mạng điện

tkluannguyendang

Đề bài: Xét một mạng điện gồm nút (đánh số từ ~1~ đến ~N~) và hệ thống gồm ~M~ đường dây, mỗi đường dây nối trực tiếp một cặp nút nào đó của mạng. Với mục đính khảo sát hiệu thế giữa hai nút ~s,t~ nào đó của mạng ảnh hưởng đến điện áp của các nút trong mạng, người ta muốn xác định các nút gọi là các nút thế năng của mạng. Một nút của mạng được gọi là nút thế năng nếu như việc truyền tải điện năng từ nút ~s~ đến nút ~t~ trên mạng có thể thực hiện theo tuyến đường dây có đi qua nút này đồng thời mỗi nút của mạng xuất hiện trên tuyến đường dây này không quá một lần.

Yêu cầu: Xác định tất cả các nút thế năng của mạng điện.

Input:

  • Dòng đầu tiên chứa bốn số ~N,M,s,t~ ~(N ≤ 1000, M ≤ 15000)~ .
  • Dòng thứ ~i~ trong ~M~ dòng tiếp theo chứa hai số ~D_i, C_i~ là các số hiệu hai nút tương ứng hai đầu mút của đường dây thứ ~i~.

Output:

  • Dòng đầu tiên ghi số ~K~ là số lượng nút thế năng tìm được.
  • Dòng thứ ~i~ trong ~K~ dòng cuối cùng ghi số hiệu của nút thế năng thứ ~i~, các chỉ số được ghi theo thứ tự tăng dần.

Input:

3 2 1 3
3 1
1 2

Output:

2
1
3

Nguồn: SPOJ

Con cừu hồng

CarlavierVN

CarlavierVN rất thích chơi minecraft. Một hôm được nghỉ, anh tạo một thế giới minecraft mới với cái tên “Super Ultimate Ultra Final Nonpareil Survival” và bật chế độ LAN, chơi cùng với Hội Anh em Đa cấp A519. Là một người yêu màu hường ghét sự giả dối, mục tiêu của anh không phải là thành lập một đế chế VierTech hùng mạnh và bá đạo mà là đi tìm những con cừu hồng được sinh ra tự nhiên trong thế giới minecraft đó.

Theo như con mắt tinh tường đã debug qua kha khá dòng code của CarlavierVN thì anh nhận thấy rằng cứ ~100~ giây thì sẽ luôn có ~1~ con cừu được cơ chế Random Generation sinh ra và tỉ lệ sinh ra cừu hồng bên cạnh những con cừu có lông không phải màu hồng cũng được quyết định thông qua hàm Random Number Generation là ~0.164\%~. với mỗi ~1~ con cừu được sinh ra, tỉ lệ con cừu tiếp theo được sinh ra là cừu hồng sẽ tăng thêm ~0.164\%~ vào số tỉ lệ tổng ~p~. Nếu nhân phẩm cao, con con cừu hồng vào một lúc nào đó sẽ sinh ra dựa theo số tỉ lệ tổng là ~p~. Tỉ lệ ~p~ càng cao, xác suất sinh ra cừu hồng càng lớn. Sau khi một con cừu hồng được sinh ra, tỉ lệ tổng p lập tức giảm xuống ~0\%~ như ban đầu. Với ~p=100\%~ thì con cừu tiếp theo được sinh ra chắc chắn sẽ là cừu hồng. Nhưng vừa nhớ ra là còn vài bài toán nhân ma trận chưa làm, CarlavierVN lập tức AFK và chuyển sang tab DevC++ để hoàn thành.

Vì quá bận debug những dòng code “không được clean cho lắm” của chính mình nhưng vẫn muốn chăn cừu, những bạn học sinh giỏi tin là những người CarlavierVN có thể tin tưởng giao cho nhiệm vụ cao cả này. Các bạn hãy giúp CarlavierVN in ra màn hình số con cừu hồng anh đã có sau ~n~ giây AFK nhé!!!

Lưu ý: vì đang chơi ở chế độ LAN nên khi CarlavierVN AFK cừu vẫn được sinh ra như bình thường.

input: gồm 1 số ~n~ là số giây CarlavierVN đã AFK ~(n \le 10^{50})~

output: gồm 1 số duy nhất là số cừu hồng mà CarlavierVN đã có sau ~n~ giây AFK

Sample:

Input: 50 Output: 0

Input: 500 Output: 0

Giải thích:

  • Test 1: Vì mới chỉ có ~50s~ sau khi tạo thế giới, chưa có con cừu nào được sinh ra trong thế giới của CarlavierVN cả
  • Test 2: sau ~500s~, tổng tỉ lệ ~p~ có giá trị là ~0.82\%~, quá thấp để có thể sinh ra được ~1~ con cừu hồng để thỏa mãn thú tính của CarlavierVN

Xâu con chung dài nhất 4

hhoangcpascal

Cho hai xâu ~S~ và ~T~ chỉ gồm các chữ cái thường 'a'..'z'. Tìm độ xâu con chung dài nhất (subsequence) của hai xâu ~S~ và ~T~.

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

  • Dòng thứ nhất chứa xâu ~S~.
  • Dòng thứ hai chứa xâu ~T~.

Kết quả: In ra độ dài xâu con chung dài nhất cần tìm.

Chú ý: Một xâu con của một xâu ~X~ bất kì thu được bằng cách xóa đi một vài kí tự (có thể không xóa kí tự nào) từ xâu ~X~ và nối những phần tử còn lại mà không thay đổi thứ tự của chúng.

Ví dụ:

Input:

axyb
abyxb

Output:

axb

Giới hạn:

  • ~50~% số test đầu tiên tương ứng với ~50~% số điểm có ~|S|, |T| \le 10^3~.
  • ~50~% số test còn lại tương ứng với ~50~% số điểm có ~|S|, |T| \le 10^4~.

Nguồn: Cấp độ khó hơn nữa của bài Xâu con chung dài nhất của jumptozero (nhưng chưa phải khó nhất)

Bắn cung

huyhau6a2

Bạn Huy đang tập bắn cung để chuẩn bị cho thi olympic. Hôm đó, mẹ của Huy ghi ra thông tin gồm ~n~ dòng, dòng thứ ~i~ ghi ~2~ số, khoảng cách tới tâm và số điểm nhận được. Số điểm nhận được là số vòng tròn không chứa nó, nếu nằm trong cạnh sẽ được tính là chứa. Gọi ~r~ là chênh lệch bán kính của mỗi vòng tròn. Hãy tìm ~r~ với các thông tin mẹ Huy đã viết

Dữ liệu vào:

  • Dòng ~1~ gồm số ~n~. không quá ~10^5~
  • ~n~ dòng tiếp theo, mỗi dòng gồm 2 số chỉ thông tin ở dòng đó (theo đề bài) không quá ~10^9~

Kết quả:

  • Nếu không tìm được ~r~ hoặc thông tin bị lỗi, xuất ERROR, nếu không hãy xuất ra số ~r~ nhỏ nhất thỏa mãn.

Sample Input

3
9 0
10 0
11 1

Sample Output

10

Dây cáp và máy tính

DeMen100ms, Monarchuwu

Có một số vấn đề xảy ra trong phòng tin học. Do đó, người ta đã kiểm tra lại hệ thống dây cáp của phòng học.

Biết rằng:

  • Máy chủ luôn kết nối với máy số 1
  • Mỗi sợi dây cáp chỉ kết nối giữa hai máy bất kỳ với nhau. Đồng nghĩa, thông tin có thể chuyển qua lại giữa 2 máy này
  • Máy chủ có thể gửi thông tin đến các máy khác nếu máy chủ kết nối với máy đó hoặc kết nối trung gian qua 1 số máy khác.

Quan trọng nhất : Đường dây liên thông khi và chỉ khi máy chủ có thể chuyển thông tin đến tất cả các máy còn lại (Bằng cách trực tiếp hoặc gián tiếp)

DeMen100ms là học sinh chuyên Tin, người ta đã nhờ anh thiết lập một chương trình trả lời câu hỏi :

  • Nếu đường dây liên thông thì có thể cắt tối đa bao nhiêu sợi dây để đảm bảo đường dây liên thông (In ra ký tự “-“ trước đáp án) (~-0~ cũng là một đáp án có thể xảy ra)
  • Ngược lại, thì phải gắn tối thiểu bao nhiêu sợi dây để đảm bảo đường dây liên thông (In ra ký tự “+” trước đáp án)

Các bạn hãy giúp anh làm việc này nhé !

INPUT

  • Dòng đầu là 2 số nguyên dương ~n~ và ~k~ lần lượt là số máy và số dây cáp của phòng học ~(n, k \leq 10^6)~
  • ~k~ dòng tiếp theo, dòng thứ ~i~ là ~2~ số nguyên dương ~a_i, b_i~ : Dây cáp thứ ~i~ nối 2 máy ~a_i~ và ~b_i~. ~(a_i, b_i \leq n, a_i \neq b_i)~

OUTPUT

  • In ra kết quả của câu hỏi trên

Sample input 1

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

Sample output 1

-1

Sample input 2

4 3
1 2
2 3
3 1

Sample output 2

+1

Subtask

  • ~30~% test : ~n \leq 5, k \leq 10~
  • ~30~% test : ~n, k \leq 10^3~
  • ~40~% test : ~n, k \leq 10^6~

Mua đồ

huyhau6a2

huyhau6a2 đang có dự định mua ~n~ món đồ tại ~n~ cửa hàng khác nhau. Cửa hàng thứ ~i~ ở tọa độ ~(x_i, y_i)~. huyhau6a2 đã dự định mua ~n~ món đồ và xếp thứ tự mua đồ theo ~1~ vòng tròn. Cụ thể huyhau6a2 sẽ chọn ~1~ cửa hàng để mua trước, sau đó cứ theo thứ tự vòng tròn mà mua ở những cửa hàng tiếp theo.

  • VD: xét ~n=5~ và nếu huyhau6a2 mua ở cửa hàng 4 trước thì ta sẽ có thứ tự mua: ~(4, 5, 1, 2, 3)~; nếu mua ở cửa hàng 2 trước thì ta sẽ có thứ tự mua: ~(2, 3, 4, 5, 1)~

Hãy giúp huyhau6a2 chọn số hiệu của cửa hàng cần mua trước sao cho độ dài đường đi cần phải đi là ít nhất, và độ dài ngắn nhất đó là bao nhiêu?

Dữ liệu vào:

  • Dòng 1 gồm duy nhất 1 số ~n(n<=10^5)~
  • ~n~ dòng tiếp theo, mỗi dòng gồm 2 số chỉ tọa độ của cửa hàng thứ ~i(|x_i|, |y_i|<=10^9)~

Kết quả:

  • Xuất ra 2 dòng, dòng thứ nhất xuất ra số hiệu của cửa hàng cần mua trước, dòng thứ hai xuất ra độ dài của đường đi ngắn nhất, kết quả dòng 2 phải xuất kết quả sau khi làm tròn ~6~ chữ số thập phân

Sample input

3
2 2
3 3
1 1

Sample output

3
2.828427

Rượu

Small

ở đất nước Free Contest, người dưới 18 tuổi không được phép uống rượu. Để trở thành một đất nước tiêu biểu, họ liền chỉ đạo Tèo đến quán nhậu bất kì để kiểm tra thử liệu có ai vi phạm hay không. Ở trong quán nhậu có ~N~ người (không tính Tèo) và Tèo đã đi hỏi lần lượt từng người về tuổi của người đó hoặc là hỏi loại đồ uống mà người đó đang uống.

Với những thông tin thu thập được, Tèo vẫn chưa biết chắc được người nào phạm luật và người nào thì không. Vì vậy Tèo quyết đinh quay lại hỏi những người trong quán nhậu thêm lần nữa, nhưng vì không muốn làm phiền mọi người Tèo muốn số lượng người mà Tèo hỏi thêm là ít nhất.

Các bạn hãy tính xem Tèo cần hỏi ít nhất bao nhiêu người nữa để có thể biết chắc chắn người nào trong quán nhậu chưa đủ tuổi mà vẫn uống rượu hay không.

Sau đây là tên tất cả loại rượu ở đất nước Free Contest: ABSINTH, TEQUILA, VODKA, WHISKEY, WINE, BEER, BRANDY, CHAMPAGNE, GIN, RUM, SAKE. Giả thiết rằng mỗi người chỉ uống một loại đồ uống duy nhất và mọi người đều nói thật.

Dữ liệu

  • Dòng đầu tiên chứa số nguyên dương ~N\ (N < 100)~.
  • ~N~ dòng tiếp theo mỗi dòng miêu tả thông tin của một người mà Tèo hỏi. Dòng thứ ~i~ gồm một số nguyên dương là tuổi của người thứ ~i~ hoặc là tên đồ uống mà người đó đã dùng (là một xâu chứa các kí tự Latinh in hoa có tối đa 100 kí tự).

Kết quả

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

Sample Input

9
CHAMPAGNE
BRANDY
23
TZWERCDLE
25
GIN
NSSFYHFAO
5
WINE

Sample Output

5

Giải thích: Tèo cần hỏi thêm người thứ 1, 2, 6, 8, 9.


Nguồn: BFC

Tam giác số (THT'19)

Small

Cho tam giác số có hình dạng một tam giác vuông cân gồm ~n~ cột và ~n~ hàng, trong đó hàng thứ ~i~ có ~i~ số (như hình dưới)

enter image description here

Yêu cầu: Tính tổng các số ở phần còn lại của tam giác sau khi đã xóa đi ~k~ cột liên tiếp (tính từ trái sang phải) của tam giác này.

Dữ liệu

  • Chứa 2 số nguyên dương ~n~ và ~k~ nằm trên 1 dòng, mỗi số cách nhau ít nhất một dấu cách, trong đó:
    • Số ~n~ là số hàng của tam giác ban đầu (~n \le 10^{16}~)
    • Số ~k~ là số cột được xóa (~k < n, k \le 10^5~)

Kết quả

  • Ghi ra số nguyên dương ~m~ thỏa mãn yêu cầu.

Sample Input

5 3

Sample Output

114

Giải thích: Với số hàng ban đầu ~n = 5~ và xóa đi ~k = 3~ cột liên tiếp (tính từ trái sang phải) thì tổng các số ở phần còn lại của tam giác là ~29 + 41 + 44 = 114~


Nguồn: Đề chọn đội tuyển QG Tin học trẻ B năm 2019, Đà Nẵng

Biến đổi (TS10LQĐ 2021)

Small

Cho dãy ~A~ gồm 8 số nguyên có giá trị từ 1 đến 8. Có 2 phép biến đổi trên dãy số này: Phép quay trái ~L~ và phép quay phải ~R~.

Phép biến đổi ~L~ là dời số trong dãy từ phải sang trái, số đầu dãy chuyển đến vị trí cuối dãy.

Ví dụ: Dãy ~A: 12345678~ Trạng thái dãy sau khi biến đổi ~L \rightarrow 23456781~

Tương tự, phép biến đổi ~R~ dời số trong dãy từ trái sang phải, số cuối dày chuyển đên vị trí đầu dãy.

Ví dụ: Dãy ~A: 12345678~ Trạng thái dãy sau khi biến đổi ~R \rightarrow 81234567~

Yêu cầu: Cho một dãy các phép biến đổi, sau khi thực hiện tuần tự các biển đổi đã cho, dãy ~A~ có trạng thái mới, biến đổi thành dãy ~B~. Hãy lập trình xác định dãy ~B~.

Dữ liệu

  • Chỉ gồm 1 hàng gồm các kí tự ~L, R~ viết liền nhau, dùng để biểu diễn dãy tuần tự các phép biến đổi cho trước. Chiều dài không quá 200 kí tự.

Kết quả

  • Ghi ra 1 dòng biểu diễn dãy B với các số viết liền nhau.

Input

RRRRRRR

Output

23456781

Nguồn: Bài 2 TS10 LQĐ TPĐN '2021