nguồn đề: https://drive.google.com/drive/folders/1qNReFFCovMfXFB6vO8Z8XugKnr9l8TT7?usp=sharing đề 2014 bài 3

Dãy fibonacci được định nghĩa theo công thức sau :

$$f_n = \begin{cases} f_1 = f_2 = 1 \\ f_n = f_{n-1}+f_{n-2} & \text{if } n \geq 3 \end{cases}$$

dãy ~a_n~ được gọi là dãy tỷ lệ với ~f_n~ nếu: $$\frac{a_1}{f_1} = \frac{a_2}{f_2} = ... = \frac{a_n}{f_n}$$

Cho 2 số ~a_1~ và ~n~ yêu cầu tính tổng ~S~ của dãy số tỉ lệ gồm ~n~ số đầu tiên và đưa ra số dư của ~S~ chia cho ~10^9 +7~.

Input

Dòng đầu tiên chứa ~T (1 \leq T \leq 10^5) ~ Số trường hợp thử.

T dòng tiếp theo, chứa ~a_1~ và ~n~ , ~ (0 \leq a_1,n \leq 10^{15}) ~

có 50% test có ~ (0 \leq n \leq 10^{6}) ~

50% test còn lại không có điều kiện gì thêm

Output

~T~ dòng, mỗi dòng chứa 1 số nguyên duy nhất, số ~S~ được chia dư cho ~10^9 +7~.

có 50% test có ~ (0 \leq n \leq 10^{6}) ~

50% test còn lại không có điều kiện gì thêm

Sample Input

1
3 5

Sample Output

36

Nhiệm vụ của bạn là tìm kiếm k tuyến đường ngắn nhất từ thành phố 1 đến thành phố n. Biết rằng bạn có thể ghé thăm một thành phố nhiều lần.

Input

• Dòng đầu tiên chứa 3 số nguyên n , m , k lần lượt là : số lượng thành phố, số lượng đường đi và tham số k.
• m dòng tiếp theo chứa 3 số nguyên a, b, c : thành phố a đến thành phố b và khoảng cách là c (không có chiều ngược lại) .

Outpput

• In ra k số nguyến được sắp xếp tăng dần

Constraints

• ~2 \leq n \leq 10^5 ~
• ~ 1 \leq m \leq 2.10^5 ~
• ~ 1 \leq a,b \leq n~
• ~ 1 \leq k \leq 10^9~
• ~ 1 \leq k \leq 10 ~

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

Explanation

• 1 -> 3 -> 4 (result = 4 )
• 1 -> 2 -> 3 -> 4 (result = 4 )
• 1 -> 2 -> 4 (result =7 )

nguồn đề: https://oj.vnoi.info/problem/fc011_wordpow

Một mùa vu lan mới lại đến, một ngày lễ đặc biệt để con cái báo hiếu với cha mẹ. Nhưng vì đã chán với cách báo hiếu thông thường nên thầy Sena quyết định báo nhà 3 tỷ 3. Quả thật là nhân văn T.T ?

Chủ nợ đã gửi ~M~ giấy báo nợ về nhà cho thầy Sena, mỗi giấy báo nợ có 1 tên có 1 chuỗi kí tự có độ dài không quá ~30~ kí tự. Nhưng vì là con người cẩn thận nên Sena đã dùng ~N~ tên giả khác nhau để đi bốc bát. Mỗi cái tên giả là chuỗi có ký tự có độ dài không quá ~1000~ kí tự. Các ký tự này gồm các chữ cái latin hoa hoặc thường

Do biết Sena có nhiều tên giả nên các chủ nợ đã không ghi tên của Sena vào, thay vào đó họ viết 1 chuỗi con trong tên của Sena vào giấy ghi nợ. Ví dụ tên giả là ~Sena~ thì sẽ có các chuỗi con là ~Se,Sa,Sn,en,ea,na~ mà không có chuỗi là ~ne~. Bạn hãy giúp Sena xem mỗi tên giả của anh xuất hiện trong bao nhiêu giấy báo nợ của chủ nợ để anh ấy có 1 mùa vu lan thật ý nghĩa <3.

Input

Dòng đầu tiên của mỗi test chứa số nguyên ~N ~ và ~M~ ~(1 ≤ N ≤ 1000, 1 ≤ M ≤ 100)~

N dòng tiếp theo, mỗi dòng chứa các tên giả của Sena

M dòng tiếp theo, mỗi dòng chứa 1 phần của các tên giả đó.

Output

đưa ra N dòng, mỗi dòng đưa ra một số duy nhất là số lần xuất hiện của cái tên đó trong các giấy báo nợ

Sample Input

5 3
Bessie
Jonathan
Montgomery
Alicia
Angola
se
nGo
Ont

Sample Output

1
1
2
0
1

Giải thích:

Bessie xuất hiện trong giấy báo thứ nhất, với chuỗi kí tự là se

Jonathan xuất hiện trong giấy báo thứ ba, với chuỗi kí tự là Ont

Cho vị trí của quân Mã trên bàn cờ vua tiêu chuẩn, tìm số nước đi khác nhau mà quân Mã có thể thực hiện.

Example

• Với vị trí = "a1", kết quả sẽ là chessKnightMoves(cell) = 2.

  

  • Với vị trí = "c2", kết quả sẽ là chessKnightMoves(cell) = 6.
  • 

input

string s

* constrains *

• ~len(s) = 2~
• ~ a \le s[0] \le h~
• ~1 \le s[1] \le 8 ~

output:

Kết quả là số bước đi của quân mã

Sample Input

a1

Sample Output

2

nguồn đề: http://ntucoder.net/Problem/Details/5558

Sau khi đã chán với việc pha chế kiếm 1 tỷ 1 tháng, người anh sinh năm 96 Bách Khoa chuyển ngang sang pha chế liền định khởi nghiệp. Nhưng để khởi nghiệp thì rất cần vốn, vậy nên anh đã quyết định tham gia Sắc Ma (1 chương trình hỗ trợ khởi nghiệp).

Nhưng để chứng minh rằng mình đủ khả năng là mình là 1 người tài năng, anh phải chơi cùng các nhà đầu tư 1 trò chơi đơn giản. Trò chơi có luật như sau:

Mỗi một số nguyên dương đều có thể biểu diễn dưới dạng tích của 2 số nguyên dương ~X~,~Y~ sao cho ~X<=Y~ . Nếu như trong phân tích này ta thay ~X~ bởi ~X-1~ còn ~Y~ bởi ~Y+1~ thì sau khi tính tích của chúng ta thu được hoặc là một số nguyên dương mới hoặc là số ~0~ .

Ví Dụ : Số 12 có 3 cách phân tích ~1*12 ,3*4 , 2*6~ . Cách phân tích thứ nhất cho ta tích mới là 0 : ~(1-1)*(12+1) = 0~ , cách phân tích thứ hai cho ta tích mới 10 : ~(3-1)*(4+1) = 10~ , còn cách phân tích thứ ba cho ta ~7 : (2-1)*(6+1)=7~ . Nếu kết quả là khác ~0~ ta lại lặp lại thủ tục này đối với số thu được . Rõ ràng áp dụng liên tiếp thủ tục trên , cuối cùng ta sẽ đến được số 0 , không phụ thuộc vào việc ta chọn cách phân tích nào để tiếp tục. Cho 1 số nguyên dương ~N~ yêu cầu đưa ra tất cả số nguyên dương có thể trong các cách phân tích trên.

Vì vốn là 1 vozer lâu năm, tuy có thể trên thông thiên văn dưới tường địa lý nhưng anh lại rất dốt toán. Mọi người hãy giúp người anh phân tích các con số này nhé.

Input

Gồm 1 dòng duy nhất chứa 1 số nguyên dương ~N~ ~(1 \leq N \leq 10000)~

Output

Dòng đầu tiên là số lượng số phân tích được

Dòng thứ hai bao gồm các số phân biệt nhận được sau quá trình phân tích và được sắp xếp theo thứ tự tăng dần.

Sample Input

12

Sample Output

6
0 3 4 6 7 10

nguồn đề: https://atcoder.jp/contests/arc146/tasks/arc146_a

Có N thẻ, được đánh số 1 đến N . Thẻ i có số nguyên dương ~a i~ được viết trên đó.

Bạn có thể chọn ba trong số các thẻ này và nối các số nguyên được viết trên chúng theo bất kỳ thứ tự nào bạn muốn để tạo thành một số nguyên mới. Ví dụ: nếu bạn chọn thẻ có 1, 23 và 4 được viết trên chúng, bạn có thể tạo các số nguyên chẳng hạn như 1234 vvà 4231

Tìm số nguyên lớn nhất bạn có thể tạo thành.

* CONSTRAINTS *

~ 3 \le N \le 2.10^5 ~

~ 1 \le a_i \le 10^6 ~

*Sample Input *

5
1 4 3 5 8

* Sample Output *

854

Chúng ta có hai hoán vị P và Q có kích thước N ( cả P và Q cả hai đều là sự sắp xếp lại của (1, . 2. ...N )

Chúng ta có thể có N! là hoán vị có kích thước N. Trong số đó, P và Q là hoán vị ở vị trí a và b nhỏ nhất về mặt từ vựng của N! hoán vị. Nhiệm vụ của bạn là tìm | a- b|.

* Input*

~ 1 \le N \le 8~ Dòng tiếp theo có N số nguyên ~ P_1, P_2 , ... P_n~

Dòng cuối cùng chứa N số nguyên ~ Q_1, Q_2,... Q_n ~

* Output *

Số nguyên duy nhất là kết quả |a - b |

* Sample Input 1*

3
1 3 2
3 1 2

* Sample Output 1*

3

Note Sample Input 1

Chúng ta có tất cả 6 hoán vị được sắp xếp theo mặt từ vựng nhỏ nhất là : (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), và (3, 2, 1). 
Chúng ta có (1, 3, 2) ở vị trí 2 và  (3, 1, 2) ở vị trí  5 vì vậy kết quả là |2-5∣=3.

* Sample Input 2*

3
1 2 3
1 2 3

* Sample Output 2*

0