Đếm hoán vị

cuom1999

Cho hai số nguyên dương ~n, k~. Đếm xem có bao nhiêu hoán vị ~p_1, p_2, ..., p_n~ của ~1, 2, ..., n~ thỏa mãn ~p_i > p_{i / k}~ với mọi ~1\leq i\leq n~.

Trong đó, ~a/b~ là số nguyên lớn nhất không vượt quá ~\dfrac{a}{b}~ và quy ước ~p_0 = 0~.

Input

Gồm hai số nguyên dương ~n, k \ (1 \leq n, k \leq 10^6)~

Output

In ra số lượng hoán vị thỏa mãn điều kiện sau khi ~\mod (10^9+7)~

Sample Input 1

3 2

Sample Output 1

2

Sample Input 2

8 3

Sample Output 2

2520

Giải thích

Trong test 1, chúng ta cần tìm các hoán vị thỏa mãn ~p_3>p_1~ và ~p_2>p_1~. Có 2 hoán vị như vậy ~(1, 2, 3)~ và ~(1, 3, 2)~.

Giới hạn

  • ~20~% test có ~n \leq 10~
  • ~10~% test có ~k > n~
  • ~10~% test có ~k = n~
  • ~20~% test có ~k > \frac{n}{2}~
  • ~20~% test có ~n, k \leq 10^3~
  • ~20~% test có ~n, k \leq 10^6~

Phép toán

Small

Vì nghỉ hè quá lâu nên bạn Nam học sinh lớp 3 đã quên hết các phép toán : cộng, trừ, nhân, chia. Các em hãy giúp Nam ôn tập lại các phép toán đó nhé!

Input

  • Dòng 1 chứa số nguyên dương ~a~
  • Dòng 2 chứa số nguyên dương ~b~

Output

  • In ra giá trị của các phép toán cộng ~(+)~, trừ ~(-)~, nhân ~(*)~, chia lấy nguyên ~(//)~.
  • Mỗi giá trị trên một dòng.

sample Input

10
2

Sample Output

12
8
20
5

Chuyến đi vui vẻ

Small

"Có công mài sắt, có ngày nên kim". Sau bao năm miệt mài với khu rừng zigzag, tuankiet65 đã chặt hết chúng xuống để bán lấy tiền. Giờ đây thì tiền bạc rảnh rúng, cậu bèn bày ra kế hoạch đi du lịch cho túi đỡ nặng. Lục lọi trong danh sách top 65535 công ty lữ hành tốt nhất thế giới, anh bị thu hút bởi công ty đứng vị trí #69 Aventure Joyeux do bangjdev, một người bạn cũ của anh sáng lập. Như một ưu đãi cho người đồng đội cũ, bangjdev đã đích thân vạch ra một kế hoạch tham quan các địa điểm du lịch nổi tiếng nhất thế giới với một mức giá vô cùng ưu đãi. Tuy nhiên, với tính cách ngỗ nghịch của mình, tuankiet65 đã đưa ra một thử thách cho vị CEO này, anh ta muốn các chuyến du lịch của mình phải thật "vui".

"Vui là sao cơ?" - bangjdev thắc mắc

Một chuyến du lịch "vui" là một chuyến du lịch trong ~N~ ngày liên tiếp (~N >= 2~), mỗi ngày 1 địa điểm, sao cho địa điểm của ngày đầu tiên và ngày cuối cùng phải khác nhau, hơn nữa các địa điểm từ ngày thứ ~2~ tới ngày thứ (~N - 1~) cũng phải khác địa điểm ngày đầu tiên và ngày cuối cùng.

"Tớ muốn biết có tất cả bao nhiêu cách để chọn ra các chuyến đi vui từ các địa điểm mà cậu đề xuất"

Với tư cách là một cựu học sinh chuyên tin, bangjdev không hề lúng túng mà tìm ngay ra cách giải quyết bài toán này.

"Haha lại những bài toán giải thuật quá ảo" - bangjdev cười mãn nguyện

Liệu các bạn có tài giỏi như anh chàng CEO này của chúng ta hay không? Thử xem nhé!

Yêu cầu: Cho xâu kí tự độ dài ~L~ mô tả danh sách các địa điểm du lịch mà bangjdev đề xuất. Hãy tính số lượng các chuyến du lịch vui có thể chọn ra từ danh sách này (không được thay đổi thứ tự các địa điểm)

Dữ liệu vào

  • Một xâu kí tự chiều dài ~L~ (~L \le 10^5~) mô tả kế hoạch tham quan mà bangjdev đã đề xuất. Kí tự thứ ~i~ biểu thị địa điểm du lịch ở ngày thứ ~i~. Các địa điểm du lịch được đánh kí tự tới a tới z.

Kết quả

  • Gồm một dòng duy nhất chứa 1 số nguyên là số lượng các chuyến đi vui.

Sample Input 1

abbcccddddeeeee

Sample Output 1

10

Giải thích: Có 10 chuyến du lịch khác nhau thoả mãn điều kiện

ab
abbc
abbcccd
abbcccdddde
bc
bcccd
bcccdddde
cd
cdddde
de

CSES - Flight Routes

edatnvt

Nhiệm vụ của bạn là tìm ~k~ lộ trình bay ngắn nhất từ Syrjälä đến Metsälä. Một lộ trình bay có thể đi qua một thành phố nhiều lần.

Lưu ý rằng các lộ trình có cùng chi phí cũng đều được xét (xem ví dụ).

Input

Dòng đầu gồm ba số ~n~, ~m~, và ~k~: số thành phố, số chuyến bay, và số ~k~. 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ó chi phí là ~c~. Tất cả các chuyến bay đều là chuyến bay một chiều.

Giả sử luôn có ít nhất ~k~ lộ trình từ Syrjälä đến Metsälä.

Output

In ra ~k~ số là chi phí của ~k~ chuyến bay rẻ nhất theo thứ tự không giảm.

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~
  • ~1 \le k \le 10~

Ví dụ

Sample input:

4 6 3
1 2 1
1 3 3
2 3 2
2 4 6
3 2 8
3 4 1

Sample output:

4 4 7

Giải thích: các lộ trình rẻ nhất lần lượt là ~1 \rightarrow 3 \rightarrow 4~ (chi phí là ~4~), ~1 \rightarrow 2 \rightarrow 3 \rightarrow 4~ (chi phí là ~4~), và ~1 \rightarrow 2 \rightarrow 4~ (chi phí là 7).

Duyệt thư mục

letangphuquy

Trong thư mục root có chứa tổng cộng ~n~ thư mục và tập tin (bao gồm chính nó). Dễ thấy, ngoại trừ thư mục root thì mỗi tập tin hoặc thư mục đều có chính xác một thư mục bao chứa nó - tạm gọi là thư mục cha. Vì thế có tổng cộng ~n-1~ quan hệ cha-con trong thư mục root. Bạn được cho biết tên của các thư mục và tập tin, cũng như các quan hệ cha-con. Nhằm theo dõi nội dung của thư mục, bạn cần in ra tất cả mọi đường dẫn hợp lệ, (bắt đầu bằng root). Hãy lập trình giải quyết vấn đề trên.

Input

Dòng đầu chứa ~n~ : số lượng tập tin và thư mục.

Dòng tiếp theo chứa ~n~ xâu là tên của tập tin hoặc thư mục tương ứng.

~n-1~ dòng tiếp theo, mỗi dòng chứa 2 số ~u,v~, có ý nghĩa là tên thứ ~u~ trong danh sách tên trên bao chứa tên thứ ~v~. Dữ liệu đảm bảo ~u~ là một thư mục.

Dữ liệu đảm bảo tồn tại duy nhất một xâu root.

Output

In ra ~n~ dòng, dòng thứ ~i~ là đường dẫn tới tập tin hoặc thư mục thứ ~i~.

Scoring

~1 \le n \le 200~ trong mọi test

Example

Sample input

8
break.zip program.docx sense.exe list.mp3 outside.pptx root purpose.jpg okay.pptx 
6 7
6 2
6 4
6 8
6 5
6 1
6 3

Sample output

root/break.zip
root/program.docx
root/sense.exe
root/list.mp3
root/outside.pptx
root
root/purpose.jpg
root/okay.pptx

Robot (THT BC Vòng Tỉnh/TP 2022)

Small
Robot (Bài 3 bảng C2, Bài 2 bảng C1)

Minh mới tạo ra một robot có khả năng nhận dạng trên sàn và di chuyển theo các chỉ dẫn đó. Sàn là một bảng gồm ~R~ hàng và ~C~ cột. Các hàng được đánh số từ 1 đến ~R~ từ trên xuống duới, các cột đuợc đánh số từ 1 đến ~C~ từ trái sang phải. Ô ở hàng thứ ~u\ (1 \le u \le R)~ và cột thứ ~v\ (1 \le v \le C)~ đuợc gọi là ô (u,v). Mồi ô của bảng sẽ có chỉ dẫn cho buớc đi tiếp theo cho robot.

Ví dụ, bảng phía dưới là một ví dụ.

enter image description here

  • Robot ban đầu ở vị trí ô (~1,1~), buớc tiếp theo robot sẽ di chuyển sang phải tới ô (~1, 2~).
  • Ở ô (~1, 2~), robot nhận chỉ dẫn di chuyển tiếp xuống duới là ô (~2, 2~).
  • Ở ô (~2, 2~), robot nhận chỉ dẫn di chuyển tiếp xuống duới là ô (~3, 2~).
  • Ở ô (~3, 2~), robot nhận chỉ dẫn di chuyển lên trên là ô (~2, 2~).
  • Robot sẽ di chuyển giữa hai ô (~2, 2~) và (~3, 2~).

Minh muốn thử nghiệm đua robot di chuyển từ ô (~x_s, y_s~) tới đuợc ô (~x_t, y_t~) nhung bảng huớng dẫn có thể không làm cho robot di chuyển đuợc nhu vậy. Bạn đuợc quyền thay đồi huớng dẫn của một số ô để robot có thể đi từ (~x_s,y_s~) đến (~x_t,y_t~). Nhiệm vụ của bạn là chọn ít nhất các ô và thay đổi chỉ dẫn của các ô này để robot có thể đi từ đi từ (~x_s,y_s~) đến (~x_t,y_t~). Nếu có nhiều cách thay đổi chỉ dẫn các ô, hãy đếm số cách thay đổi khác nhau. Truờng hợp không cần thay đổi ô nào thì số cách là 1. Nguợc lại, hai cách thay đổi đuợc coi là khác nhau nếu một trong hai điều sau xảy ra:

  • Tồn tại một ô được thay đồi trong cách thứ nhất mà không đuợc thay đổi trong cách thứ hai.
  • Tồn tại một ô được thay đổi trong cả hai cách, nhưng chỉ dẫn sau khi thay đồi ở cách thứ nhất khác cách thứ hai.
Input
  • Dòng đầu chứa ba số ~R, C~ và ~q~, trong đó ~R, C~ là kích thuớc của bảng và ~q~ là số truờng hợp thứ nghiệm;
  • Tiếp theo là ~R~ dòng, mỗi dòng chửa xâu kí tụ độ dài ~C~. Kí tụ thứ ~v~ trên dòng thứ ~u~, thể hiện chỉ dẫn của ô (~u, v~). Chỉ dẫn thuộc một trong 4 kí tự ~U, D, L, R~ tương ứng với đi lên trên, xuống duới, sang trái, sang phải; • ~q~ dòng cuối, mỗi dòng chứa bốn số nguyên ~x_s, y_s, x_t, y_t~ tương ứng với một thử nghiệm.
Output
  • Ghi ra gồm ~q~ dòng, mỗi dòng gồm hai số cách nhau một dấu cách: số thứ nhất ghi ra số ô phải thay đổi ít nhất, số thứ hai là phần dư trong phép chia số cách thay đổi khác nhau chia cho (~10^9 + 7~).
Scoring
  • Có 15% số luợng test ứng với 15% số điểm có ~R, C \le 4; q \le 3~;
  • Có 15% số luợng test khác ứng với 15% số điểm có ~R = 1; q \le 3~;
  • Có 20% số luợng test khác ứng với 20% số điểm có ~R,C \le 100; q \le 3~;
  • Có 20% số luợng test khác ứng với 20% số điểm có ~R,C \le 1000; q \le 3~;
  • Có 10% số luợng test khác ứng với 10% số điểm có ~R,C \le 1000; q \le 10~;
  • Có 20% số luợng test còn lại ứng với 20% số điểm có ~R \times C \le 10^6; q \le 10~;
Example

Sample input

3 4 2
RDRD
RDRD
UUUL
1 1 3 2 
1 1 3 4

Sample output

0 1
1 3

Note:

  • Trường hợp đầu tiên không cần thay đổi chỉ dẫn dẫn nào
  • Trường hợp thứ hai, chỉ cần thay đổi 1 ô bằng 1 trong 3 cách sau:
    • ô (~1,2~) từ ~D~ sang ~R~
    • ô (~2,2~) từ ~D~ sang ~R~
    • ô (~3,2~) từ ~U~ sang ~R~

Sample input

2 2 1
UD
RR
1 1 2 2

Sample output

1 2

Note: Thay đổi chỉ dẫn ô (~1,1~) từ U thành R hoặc D đều có thể đưa robot đến đích

Mã hóa dãy ngoặc

jumptozero
  • Giả sử ta có một chuỗi ngoặc đơn đúng, ta gọi chuỗi này là ~S~, khi đó ~S~ có hai cách giải mã sau đây:

    • Cách 1: ~S~ sẽ được mã hóa dưới dạng ~P=p_1,p_2,...,p_n~. Trong đó ~p_i~ là số lượng ngoặc đơn trái "(" đứng trước ngoặc đơn phải ")" thứ ~i~ tính từ trái.

    • Cách 2: ~S~ sẽ được mã hóa dưới dạng ~W=w_1,w_2,...,w_n~. Gọi ~r~ là vị trí dấu ngoặc đơn ")" thứ ~i~ tính từ trái sang. Gọi ~l~ là vị trí của dấu ngoặc đơn trái "(" tương thích với dấu ngoặc ")" đó. Khi đó ~w_i~ chính bằng số lượng dấu ngoặc đơn phải ")" nằm trong đoạn từ ~l~ tới ~r~.

  • Ví dụ: Ta có chuỗi ~S=(((()()())))~. Khi đó ta có dãy ~P~ tương ứng là: ~P=4,5,6,6,6,6~ và dãy ~W~ tương ứng là ~W=1,1,1,4,5,6~. ~W[1] = 1~ vì dấu ngoặc đơn ")" thứ nhất nằm ở vị trí ~5~ tương ứng với dấu ngoặc "(" nằm ở vị trí ~4~. Trong đoạn ~4~ tới ~5~ của ~S~ có ~1~ dấu ngoặc đơn ")".

Yêu cầu: Cho dãy ~P~ bất kì, tìm dãy ~W~ tương ứng.

Input:

  • Dòng thứ nhất chứa chứa số nguyên dương ~n(1\le n\le 10^5)~ - Là độ dài của dãy ~P~

  • Dòng thứ hai chứa ~n~ số nguyên dương ~p_i(1\le p_i\le n)~ - Mỗi số cách nhau bởi dấu cách.

Output:

  • Nếu không tồn tại dãy ~W~ thỏa mãn yêu cầu bài toán, in ra "-1". Ngược lại, in ra dãy ~W~ cần tìm

Ví du:

Input:

3
2 2 3

Output:

1 2 1
  • Subtask 1: ~1\le n\le 10~. (10%)

  • Subtask 2: ~11 \le n \le 100~.(20%)

  • Subtask 3: ~101 \le n \le 5000~.(30%)

  • Subtask 4: ~5001 \le n \le 10^5~. (40%)

Sinh nhị phân

corona

Sinh xâu nhị phân độ dài n.

Yêu cầu: Cho n hẫy in tất cả các xâu nhị phân theo thứ tự từ điển.

Dữ liệu:

  • Số nguyên dương n (n<=12)

Kết quả

  • Tất cả các xâu nhị phân theo thứ tự từ điển

Ví dụ

Input

3

Output

000
001
010
011
100
101
110
111

Số nguyên tố

Small

Cho dãy số nguyên (~a_1, a_2, ..., a_n~), ~1 \le n \le 10000~; với mọi ~i~ sao cho ~a_i \le 10^9~.

Yêu cầu: Hãy tìm số nguyên tố lớn nhất trong dãy trên.

Dữ liệu

  • Dòng thứ nhất chứa số nguyên dương ~n~.
  • Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, ..., a_n~.

Kết quả

  • Dòng thứ nhất ghi số nguyên tố lớn nhất.
  • Dòng thứ hai ghi các chỉ số trong dãy mà giá trị của nó là số nguyên tố lớn nhất.

Sample Input

9
19 7 81 33 17 4 19 21 13

Sample Output

19
1 7

Ngày kỷ niệm (TS10LQĐ 2018)

Small

Để kỷ niệm ngày 5/6/2018 là ngày thi vào Trường THPT chuyên Lê Quý Đôn của mình, bạn Mây muốn đặt ra một bài toán nào đó có liên quan đến ngày thi. Sau một lúc suy nghĩ, Mây phát hiện ra rằng, nếu dùng số 562018 ghép lại với nhau một số lần sẽ được một số ~K~ là bội của một số nguyên tố ~N~ cho trước nào đó (ở đây số ~N~ khác 2 và 5; ~N~ không phải là ước của số 562018). Chẳng hạn, với ~N = 3~ thì ta có thể ghép được số ~K = 562018562018562018~ là bội của 3.

Yêu cầu: Cho trước số nguyên tố ~N~ (~N~ khác 2 và 5; ~N~ không phải là ước của số 562018). Hãy tìm số lượng các chữ số của số ~K~ nhỏ nhất là bội của số ~N~ (~K~ là số tạo thành từ việc ghép số các số 562018 như đã nói ở trên).

Dữ liệu

  • Một số nguyên tố ~N\ (N < 562018)~.

Kết quả

  • Ghi ra một số nguyên là số lượng các chữ số của số nguyên ~K~ như đã trình bày ở trên.

Sample Input

3

Sample Output

18

Nguồn: TS10LQD 2018

Thông thạo 7 Yasuo

PhanDinhKhoi

Khôi rất thích chơi Liên Minh Huyền Thoại, đặc biệt là vị tướng Yasuo. Tuy nhiên anh ấy chơi Yasuo rất tệ nên anh ấy đang tập luyện để chơi vị tướng này một cách thành thạo.

Biết rằng từ tọa độ ~(x,y)~ Yasuo có thể lướt thẳng đến một trong các vị trí ~(x-1,y), (x+1,y), (x,y-1), (x,y+1) ~

hoặc lướt chéo đến một trong các vị trí ~(x-1,y-1), (x-1,y+1), (x+1,y-1), (x+1,y+1)~

Khôi sẽ tập luyện lướt Yasuo trong ~Q~ trận, trong trận thứ ~i~ mục tiêu của anh ấy là lướt tới điểm ~(n,m)~ từ tọa độ ~(0,0)~ trong chính xác ~k~ lần lướt. Tuy nhiên vì để được Thông Thạo 7 Yasuo, Khôi sẽ lướt đến điểm ~(n,m)~ với số lần lướt chéo là nhiều nhất.

Câu hỏi của bạn là, trong trận thứ ~i~, bạn hãy xác định số lần lướt chéo nhiều nhất của Khôi hoặc nói rằng Khôi không thể lướt từ điểm ~(0,0)~ tới điểm ~(n,m)~ trong chính xác ~k~ lần lướt.

Input

  • Dòng đầu tiên: Số nguyên dương ~Q~ ~(Q \leq 10^4)~ - số câu hỏi
  • ~Q~ dòng tiếp theo chứa số nguyên dương ~n~, ~m~, ~k~ ~(n,m,k \leq 10^{18})~

Output

  • Gồm ~Q~ dòng, tại dòng thứ ~i~, in ra ~“-1”~ nếu Khôi không thể lướt từ điểm ~(0,0)~ đến điểm ~(n,m)~ trong chính xác ~k~ lần lướt, ngược lại in ra số lần lướt chéo nhiều nhất của Khôi

Sample Input 1

3
2 2 3
4 3 7
10 1 9

Sample Output 1

1
6
-1

Giải thích

  • Một trong những cách lướt trong câu hỏi 1: ~(0,0)→(1,0)→(1,1)→(2,2)~
  • Một trong những cách lướt trong câu hỏi 2 ~(0,0)→(0,1)→(1,2)→(0,3)→(1,4)→(2,3)→(3,2)→(4,3)~
  • Câu hỏi 3: Khôi không thể lướt từ ~(0,0)~ đến ~(10,1)~ trong ~9~ lần lướt

Ràng buộc

  • 50% test ~n,m \leq 10~
  • 50% test ~n,m \leq 10^{18}~

Workers Roadmap

Small

Nguồn: ICPC North 2021

Xếp Hộp

algorit, bin9638

Hôm nay Roronoa Zoro, thợ săn quỷ mạnh nhất đang đến tiki shop để mua nhận luân kiếm cho trận chiến sống còn với chúa quỷ Muzan sắp tới. Khi Zoro tới thì chủ tiệm là algorit đang loay hoay xếp kiếm, algorit mãi chưa xếp xong kiếm nên đành nhờ Zoro giúp xếp hộ kiếm.

Trong tiệm ~N~ thanh kiếm có trọng lượng , độ dài , độ cao lần lượt là ~C_i , W_i , H_i~ , chiều rộng của mỗi thanh kiếm bằng với chiều rộng của tủ kiếm. Trọng lượng và độ dài của mỗi ngăn mà tủ kiếm có thể chứa là ~P~ và ~Q~ .

Bây giờ algorit muốn nhờ Zoro chia ~N~ hộp thành các đoạn liên tiếp để xếp vào ngăn. Biết độ cao của mỗi ngăn là độ cao của thanh kiếm cao nhất trong các hộp đã được xếp vào ngăn. Nếu Zoro giúp được thì algorit sẽ tặng cho anh ~1~ thanh kiếm Trung Quốc hàng xịn, hãy giúp anh ấy nhé !

  • Yêu cầu : Hãy tính chiều cao tối thiểu của tủ khi xếp các kiếm vào tủ 1 cách tối ưu .
  • Input :
    • Dòng đầu tiên gồm 3 số nguyên dương ~N , P , Q~ . ~(N \le 9999, (P,Q) \le 10^{12})~
    • N dòng tiếp theo gồm 3 số nguyên dương ~C_i , W_i , H_i~ . ~(C_i \le P,W_i \le Q,H_i \le 10^9)~
  • Output :
    • Gồm 1 số nguyên dương duy nhất là kết quả của bài toán .
  • Sample input :
    5 18 16
    5 7 3
    6 5 4
    2 1 9
    8 4 2
    3 2 3
  • Sample output :
    12
  • Giải thích : Chúng ta sẽ chia thanh 2 đoạn ~->~ ~(1,2,3)~ và ~(4,5)~
  • Giới hạn :
    • 40% số điểm tương ứng với : ~N \le 400 , P \le 10^3 , Q \le 10^3 , H_i \le 10^3 .~
    • 60% số điểm còn lại không có ràng buộc gì thêm .

Diff-Query (version 1)

hhoangcpascal

Cho dãy số ~A~ gồm ~N~ phần tử gồm các số nguyên dương ~A_1, A_2, ..., A_N~, và ~Q~ truy vấn, truy vấn thứ ~i~ gồm ~2~ số nguyên dương ~L_i, R_i~ ~(1 \leq L_i \leq R_i \leq N)~.

Yêu cầu: Với mỗi truy vấn thứ ~i~, hãy đếm số phần tử phân biệt trong khoảng từ ~L_i~ tới ~R_i~.

Dữ liệu vào: Gồm ~Q+2~ dòng:

  • Dòng thứ nhất chứa hai số nguyên dương ~N, Q~.
  • Dòng thứ hai chứa ~N~ số nguyên dương ~A_1, A_2, ..., A_N~ ~(1 \leq A_i \leq 10^6)~.
  • ~Q~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên dương ~L_i, R_i~.

Kết quả: In ra ~Q~ dòng, dòng thứ ~i~ là số phần tử phân biệt trong khoảng từ ~L_i~ tới ~R_i~.

Ràng buộc:

  • ~50~% số test đầu tiên tương ứng với ~50~% số điểm có ~N, Q \leq 10^3~.
  • ~50~% số test còn lại tương ứng với ~50~% số điểm có ~N, Q \leq 10^5~.

Ví dụ:

Input:

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

Output:

3
2
3

CSES - Grundy's Game

Elektrikar

Có một đống ~n~ đồng xu và hai người chơi luân phiên. Ở mỗi lượt đi, người chơi sẽ chọn một đống xu và chia thành hai đống không rỗng có số lượng xu khác nhau. Người chơi thực hiện lượt đi cuối cùng sẽ giành chiến thắng.

Nhiệm vụ của bạn là tìm ra ai sẽ thắng nếu cả hai người chơi cùng chơi tối ưu.

Input

Dòng đầu tiên là một số nguyên ~t~ : số lượng test.

Tiếp theo là ~t~ dòng mô tả test. Mỗi dòng là một số nguyên ~n~ : số lượng xu của đống ban đầu.

Output

Với mỗi test, in ra first nếu người chơi thứ nhất thắng, và second nếu người chơi thứ hai thắng.

Constraints

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

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

    Example

    Input
    3
    6
    7
    8
    Output
    first
    second
    first
  • Cuộc đua xe F1

    Small

    Một cuộc thi đua xe công thức 1 mở rộng vô cùng hoành tráng sắp được tổ chức tại thành phố XYZ. Ray cũng sẽ tham gia cuộc đua xe lần này. Vốn là một tay đua xe có hạng, cậu rất tự tin rằng không ai có thể đánh bại được mình trong bất kì cuộc đua nào. Tuy nhiên, thể lệ cuộc đua xe lần này lại có nhiều điều đặc biệt khiến cậu cảm thấy rất bối rối.

    Như mọi lần khác, cuộc đua được tổ chức trên quy mô toàn thành phố, mỗi thí sinh sẽ chạy xe theo các con đường được kẻ vạch sẵn để di chuyển qua những địa điểm dừng. Có tất cả ~n~ địa điểm dừng được đánh số thứ tự từ 1 đến ~n~, 2 địa điểm bất kì đều có 2 con đường kết nối. Điểm đặc biệt của cuộc thi lần này là mỗi thí sinh sẽ phải sử dụng những chiếc xe đua được ban tổ chức chuẩn bị sẵn cho từng người. Cụ thể, mỗi thí sinh được chuẩn bị sẵn ~m~ chiếc xe khác nhau và có thể đổi xe liên tục tại bất kì địa điểm dừng nào (mỗi chiếc xe có thể sử dụng lại nhiều lần, thời gian đổi xe không đáng kể). Một chiếc xe lại tốn một khoảng thời gian trung bình khác nhau để di chuyển qua mỗi đoạn đường khác nhau. Cuộc thi gồm có ~r~ vòng đua, tại vòng thứ ~i~ ban tổ chức lại yêu cầu các thí sinh xuất phát từ địa điểm ~s_i~ và đích đến là địa điểm ~f_i~, đồng thời tại vòng này các thí sinh chỉ được phép đổi xe tối đa ~k_i~ lần. Ray đua xe rất giỏi nhưng thể lệ cuộc đua lần này quá mới lạ với cậu, vì thế nên Ray cần tới sự giúp đỡ của bạn. Hãy tính toán cách đua xe hợp lý để Ray có thể hoàn thành mỗi vòng đua trong tổng thời gian nhỏ nhất với mỗi vòng nhé!

    Dữ liệu vào

    • Dòng thứ nhất gồm 3 số nguyên dương ~n, m, r\ (2 ≤ n ≤ 50)~.
    • Tiếp theo là ~m~ bảng 2 chiều kích thước ~n x n~ biểu diễn thông tin của những chiếc xe, trong mỗi bảng ô giao giữa dòng ~i~ và cột ~j~ gồm 1 số nguyên dương ~a_{ij}~ (~0 ≤ a_{ij} ≤ 10^6~) là thời gian để chiếc xe tương ứng di chuyển qua đoạn đường nối 2 địa điểm dừng ~i, j~.
    • ~r~ dòng tiếp theo, dòng thứ ~i~ gồm 3 số nguyên ~s_i, t_i, k_i~ (~1 ≤ s_i, f_i ≤ n; s_i ≠ f_i; 0 ≤ k_i ≤ 10^5~) cho biết địa điểm xuất phát, địa điểm đích và số lần đổi xe tối đa của vòng đua thứ ~i~.

    Kết quả

    • Đưa ra ~r~ dòng, mỗi dòng ghi tổng thời gian nhỏ nhất cần để Ray hoàn thành vòng đua tương ứng.

    Sample Input 1

    4 2 3
    0 1 5 6
    2 0 3 6
    1 3 0 1
    6 6 7 0
    0 3 5 6
    2 0 1 6
    1 3 0 2
    6 6 7 0
    1 4 2
    1 4 1
    1 4 3

    Sample Output 1

    3
    4
    3

    Giới hạn:

    • Subtask 1: 30% số điểm có ~m = 1, 1 ≤ r ≤ 10^5~.
    • Subtask 2: 30% số điểm có ~1 ≤ m ≤ 50, 1 ≤ r ≤ 10^5, k_i = 0~.
    • Subtask 3: 40% số điểm có ~1 ≤ m ≤ 50, 1 ≤ r ≤ 10^5~.

    Nguồn: 2019 CHV-PT

    Kaninho cùng người bạn Henry

    jumptozero

    Nhân dịp ~Henry~ qua nhà chơi, ~Kaninho~ đã rủ ~Henry~ chơi một trò chơi như sau:

    Bắt đầu trò chơi, ~Kaninho~ sẽ có một số nguyên ~n~ ~(1\le n \le 10^9)~ và ~Henry~ cũng có một số nguyên ~k~ ~(1\le k\le n)~. Ở mỗi lượt, nếu ~n~ > 0, một người chơi có thể chọn một số nguyên ~x~ ~(1\le x\le max(1,n-k))~ bất kì và gán ~n=n-x~. Người chơi nào không thể chơi được nữa thì được xem là thua cuộc.

    Nếu ~Henry~ bắt đầu trước, và giả sử rằng, cả hai đều chơi một cách tối ưu, thì ai là người thắng cuộc ?

    Input:

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

    • ~t~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~n,k(1\le k\le n\le 10^9)~

    Output:

    • Ứng với mỗi testcase, in ra tên của người chiến thắng

    Ví dụ:

    Input:

    2
    2 1
    4 1

    Output:

    Kaninho
    Henry

    Subtask:

    • ~37.5\text{%}~ số điểm ứng với ~1\le k\le n\le 50~.

    • ~62.5\text{%}%~ số điểm không có điều kiện gì đặc biệt.

    Cây thông dấu sao

    Small

    Dùng lệnh print để in ra hình vẽ sau

         *
        ***
       *****
      *******
     *********
    ***********
         *
         *
         *

    Nhảy về đích (HSG11v2-2022)

    Small

    Bài 2: Nhảy về đích (7 điểm)


    TABLE

    Cho một bảng kí tự kích thước ~M*N~, chỉ gồm hai kí tự `~X~` và `~.~`.

    Yêu cầu: Tìm hình chữ nhật có chu vi lớn nhất thỏa mãn:

    • Các cạnh của hình chữ nhật song song với các cạnh của bảng kí tự.
    • Chỉ chứa kí tự `~.~`.
    • Hình chữ nhật có chu vi lớn nhất.

    Input

    • Dòng đầu chứa hai số nguyên dương ~M,N (M,N \leq 400)~;
    • Dòng thứ ~i~ trong số ~M~ dòng tiếp theo chứa ~N~ kí tự ~A_{i,1},A_{i,2},\ldots,A_{i,N} (A_{i,j}=~`~X~` hoặc `~.~`~)~

    Output

    • In ra duy nhất một số là chu vi hình chữ nhật lớn nhất tìm được.

    Example

    Sample input 1

    2 2
    ..
    ..

    Sample output 1

    8

    Sample input 2

    4 4
    X.XX
    X..X
    ..X.
    ..XX

    Sample output 2

    10

    Sample input 3

    3 3
    X.X
    .X.
    X.X

    Sample output 3

    4