Chữ số thứ N chia hết cho 3 hoặc 5

Đề bài

Hãy viết liên tiếp các số tự nhiên chia hết cho 3 hoặc 5, nhưng không chia hết cho 15, theo thứ tự tăng dần.

Ta ghép các số đó lại thành một dãy chữ số mới:

3569101218212425273033...

Hỏi: chữ số thứ N trong dãy ghép trên là chữ số nào?

Dữ liệu nhập

Một dòng duy nhất chứa số tự nhiên N

1 ≤ N ≤ 10^12

Kết quả

In ra một chữ số là chữ số thứ N trong dãy ghép được tạo ra.

Ví dụ

Giải thích ví dụ

Dãy số cần ghép là:

3, 5, 6, 9, 10, 12, 18, 20, 21, 24, 25, 27, 33, ...

Ghép lại:

3569101218202124252733...

Chữ số thứ 4 là 9.

Ràng buộc

• 50% số test có N ≤ 10^5
• 50% số test còn lại có N ≤ 10^12

Ma trận xoắn ốc 5

Cho một ma trận xoắn ốc kích thước N × N.

Ma trận được điền các số từ 1 đến N² theo quy tắc:

• Số 1 nằm ở gần trung tâm.
• Các số tiếp theo được điền tăng dần theo hình xoắn ốc ngược chiều kim đồng hồ.

Ví dụ với N = 5:

17 16 15 14 13
18  5  4  3 12
19  6  1  2 11
20  7  8  9 10
21 22 23 24 25

Yêu cầu

Hãy tính tổng số lớn nhất trên mỗi hàng của ma trận.

Dữ liệu vào

Một số nguyên:

N

Trong đó:

1 ≤ N ≤ 10^10

Dữ liệu ra

In ra tổng các số lớn nhất trên mỗi hàng của ma trận.

Vì kết quả có thể rất lớn, in kết quả lấy dư:

10^9 + 9

Ví dụ 1

Input

3

Output

20

Giải thích

Ma trận:

5 4 3
6 1 2
7 8 9

Số lớn nhất mỗi hàng:

5
6
9

Tổng:

20

Ví dụ 2

Input

5

Output

99

Giải thích

Ma trận:

17 16 15 14 13
18  5  4  3 12
19  6  1  2 11
20  7  8  9 10
21 22 23 24 25

Số lớn nhất mỗi hàng:

17
18
19
20
25

Tổng:

99

Ví dụ 3

Input

4

Output

49

Giải thích

Ma trận:

16 15 14 13
 5  4  3 12
 6  1  2 11
 7  8  9 10

Số lớn nhất mỗi hàng:

16
12
11
10

Tổng:

49

Ví dụ 4

Input

7

Output

286

Giải thích

Số lớn nhất mỗi hàng:

37
38
39
40
41
42
49

Tổng:

286

B. Bóng bàn (Table Tennis)

Giới hạn thời gian: 2 giây
Giới hạn bộ nhớ: 256 MB

Đề bài

Có n người đứng thành một hàng để chơi bóng bàn.

Ban đầu:

• Hai người đầu tiên chơi một trận bóng bàn.
• Người thua sẽ đi xuống cuối hàng.
• Người thắng sẽ tiếp tục chơi với người tiếp theo trong hàng.

Quá trình này tiếp tục cho đến khi có một người thắng liên tiếp k trận. Người đó được tuyên bố là người chiến thắng.

Bạn biết sức mạnh của từng người chơi, và sức mạnh của mỗi người là khác nhau.

Người có sức mạnh lớn hơn luôn luôn thắng.

Hãy xác định người chiến thắng.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên:

n k

Trong đó:

2 ≤ n ≤ 500
2 ≤ k ≤ 10^12

• Dòng thứ hai chứa n số nguyên:

a1 a2 ... an

Trong đó:

1 ≤ ai ≤ n

Các giá trị ai là một hoán vị, nghĩa là tất cả đều khác nhau.

ai biểu diễn sức mạnh của người chơi thứ i.

Dữ liệu ra

In ra một số nguyên:

sức mạnh của người chiến thắng

Ví dụ 1

Input

2 2
1 2

Output

2

Ví dụ 2

Input

4 2
3 1 2 4

Output

3

Giải thích

Các trận đấu:

• 3 đấu với 1 → 3 thắng, 1 xuống cuối hàng
• 3 đấu với 2 → 3 thắng tiếp

3 thắng liên tiếp 2 trận nên chiến thắng.

Ví dụ 3

Input

6 2
6 5 3 1 2 4

Output

6

Ví dụ 4

Input

2 1000000000000
2 1

Output

2

Số thứ N không chia hết cho 4, 5 hoặc 6

Đề bài

Từ dãy số tự nhiên ban đầu:

1, 2, 3, 4, 5, 6, 7, ...

người ta loại bỏ tất cả các số chia hết cho 4, 5 hoặc 6.

Khi đó, dãy số mới sẽ là:

1, 2, 3, 7, 9, 11, 13, 14, 17, ...

Yêu cầu

Cho số tự nhiên N. Hãy xác định số thứ N trong dãy số mới này.

Input

Một dòng duy nhất chứa số tự nhiên N.

N

Điều kiện:

1 <= N <= 10^12

Output

Một số duy nhất là số thứ N trong dãy các số tự nhiên không chia hết cho 4, 5 hoặc 6.

Scoring

• 40% điểm với N <= 1000.
• 60% điểm với N <= 10^12.

Sample Input

5

Sample Output

9

Bảng cửu chương

Bảng cửu chương (THT A Vòng Sơ loại Toàn quốc 2026 - Lần 1)

Đề bài

Bé Bi chỉ mới học thuộc bảng cửu chương, các phép nhân từ 1 × 1 đến 9 × 9.

Cho trước số tự nhiên X, nếu X là kết quả của một phép nhân trong bảng cửu chương, hãy tìm xem X nằm ở bảng cửu chương nào.

Nếu X nằm ở nhiều bảng khác nhau, hãy đưa ra số thứ tự của bảng nhỏ nhất.

Nếu X không có mặt trong bảng cửu chương, hãy đưa ra kết quả là 0.

Input

Gồm một số tự nhiên X.

1 <= X <= 100

Output

In ra một số tự nhiên duy nhất là số thứ tự của bảng cửu chương nhỏ nhất chứa X.

Nếu X không phải là kết quả của bất kỳ phép nhân nào trong bảng cửu chương, in ra 0.

Ví dụ 1

Input

12

Output

2

Giải thích

12 có thể là kết quả của các phép nhân:

2 × 6 = 12
3 × 4 = 12
4 × 3 = 12
6 × 2 = 12

Bảng cửu chương nhỏ nhất chứa số 12 là bảng 2.

Ví dụ 2

Input

14

Output

2

Giải thích

14 nằm trong bảng cửu chương vì:

2 × 7 = 14

Bảng nhỏ nhất là bảng 2.

Ví dụ 3

Input

13

Output

0

Giải thích

Không có hai số tự nhiên nào từ 1 đến 9 có tích bằng 13, nên in ra 0.

Mật mã

Là một học sinh với thẩm mỹ cằn cỗi và tình cảm nghèo nàn, Rotund không mấy khi có tinh thần khi học môn Văn. Tuy nhiên trong giờ Văn học hôm nay, cậu lại có hứng thú về ý tưởng Dancing Men trong tiểu thuyết trinh thám được giới thiệu trong tiết học.

Cậu quyết định tạo ra một cách mã hóa để có thể thoải mái trò chuyện với các bạn trong nhóm của mình mà không sợ bị ai nhìn trộm.

Chuỗi ký tự được mã hóa chỉ bao gồm chữ cái tiếng Anh, gồm cả chữ in hoa và chữ in thường.

Quy tắc mã hóa như sau:

• Ký tự thứ i trong chuỗi sẽ được dịch sang i vị trí trong bảng chữ cái.
• Vẫn giữ nguyên kiểu chữ hoa hoặc chữ thường của ký tự.
• Ký tự ở vị trí lẻ sẽ bị dịch sang trái.
• Ký tự ở vị trí chẵn sẽ bị dịch sang phải.
• Khi dịch vượt quá hai đầu bảng chữ cái thì quay vòng:
  • Bên trái a là z, bên trái A là Z.
  • Bên phải z là a, bên phải Z là A.

Ví dụ:

• Ký tự B dịch sang trái 2 vị trí sẽ trở thành Z.
• Ký tự B dịch sang phải 2 vị trí sẽ trở thành D.

Tuy nhiên, với một đám học sinh mẫu giáo ham chơi nhanh chán thì việc giải mã những thông điệp Rotund gửi đến vẫn là một công việc rất thử thách tính chính xác và quá khó khăn.

Hãy giúp nhóm bạn của Rotund hiểu được nội dung tin nhắn mà cậu đã gửi.

Yêu cầu

Cho một chuỗi ký tự đã được Rotund mã hóa. Hãy giải mã chuỗi đó về nội dung ban đầu.

Input

Một dòng duy nhất chứa xâu ký tự s, là tin nhắn đã được mã hóa.

Điều kiện:

1 ≤ |s| ≤ 10^6

Chuỗi s chỉ gồm các chữ cái tiếng Anh:

a → z
A → Z

Output

In ra chuỗi ban đầu sau khi giải mã.

Ví dụ 1

Input

zdz

Output

abc

Giải thích

Chuỗi đã mã hóa là zdz.

Ta giải mã từng ký tự:

• Vị trí 1 là z, vị trí lẻ nên khi giải mã dịch phải 1 vị trí: z → a.
• Vị trí 2 là d, vị trí chẵn nên khi giải mã dịch trái 2 vị trí: d → b.
• Vị trí 3 là z, vị trí lẻ nên khi giải mã dịch phải 3 vị trí: z → c.

Vậy chuỗi ban đầu là:

abc

Ví dụ 2

Input

GczoYxxid

Output

HackDream

Giải thích

Ta giải mã từng ký tự:

Vậy chuỗi ban đầu là:

HackDream

Subtask

• Có 50% số test tương ứng với 50% số điểm có n ≤ 10^3.
• Có 50% số test còn lại tương ứng với 50% số điểm không có giới hạn gì thêm.

Tô Màu Bàn Cờ Theo Xoắn Ốc Đồng Tâm

Mô tả

BTC THT có một bàn cờ kích thước N × N ô vuông.

BTC muốn tô bàn cờ bằng K màu khác nhau theo quy luật xoắn ốc đồng tâm như sau:

• Tầng ngoài cùng của bàn cờ được gọi là tầng 1.
• Đi vào một vòng nữa là tầng 2.
• Tiếp tục như vậy cho đến tâm bàn cờ.

Màu của ô không phụ thuộc vào vị trí cụ thể mà chỉ phụ thuộc vào số tầng chứa ô đó.

Ta đánh số màu từ 1 đến K, sau đó lặp lại:

Tầng 1 → Màu 1
Tầng 2 → Màu 2
...
Tầng K → Màu K
Tầng K+1 → Màu 1
Tầng K+2 → Màu 2
...

Yêu cầu

Hãy tính số ô được tô màu 1.

Dữ liệu

Gồm hai số nguyên dương:

N
K

Với:

1 ≤ N ≤ 10^12
1 ≤ K ≤ 10^5

Kết quả

In ra số ô được tô màu 1.

Sample Input 1

5
2

Sample Output 1

17

Giải thích

1 1 1 1 1
1 2 2 2 1
1 2 1 2 1
1 2 2 2 1
1 1 1 1 1

Số ô màu 1:

16 + 1 = 17

Sample Input 2

6
3

Sample Output 2

20

Minh họa

1 1 1 1 1 1
1 2 2 2 2 1
1 2 3 3 2 1
1 2 3 3 2 1
1 2 2 2 2 1
1 1 1 1 1 1

Có 20 ô được tô màu 1.