Luyện tập ngày 09 & 13/01

Cho 2 số nguyên dương \(n, k\). Hãy tính tổng \(S\) là các số chia hết cho \(k\) trong đoạn từ \(1\) đến \(n\).

Ví dụ: \(n = 20, k = 5\) thì tổng \(S = 5 + 10 + 15 + 20 = 50\)

Yêu cầu: Cho 2 số nguyên dương \(n, k\), hãy tìm và in ra giá trị \(S\).

Input

• Dữ liệu nhập vào từ bàn phím gồm hai dòng:
  • Dòng thứ nhất chứa tự nhiên \(n\) \((n \leq 1.000.000.000)\)
  • Dòng thứ hai chứa tự nhiên \(k\) \((k \leq 10)\)

Output

• In ra màn hình một số \(S\) duy nhất là tổng các số chia hết cho \(k\) trong đoạn từ \(1\) đến \(n\).

Example

20
3

63

14
2

56

Bạn viết dòng chữ "HOI THI TIN HOC TRE CAP THANH PHO" lặp lại nhiều lần thành dãy ký tự liên tiếp như sau:

HOITHITINHOCTRECAPTHANHPHOHOITHITINHOCTRECAPTHANHPHOHOITHITIN...

Yêu cầu: Cho số tự nhiên \(n\) và ký tự \(ch\) in hoa bất kỳ, đếm xem từ ký tự thứ nhất đến ký tự thứ \(n\) có bao nhiêu ký tự \(ch\).

Ví dụ: \(n = 40\), \(ch =\) O, trong 40 ký tự đầu tiên của dãy có \(5\) ký tự O:

HOITHITINHOCTRECAPTHANHPHOHOITHITINHOCTRECAPTHANHPHOHOITHITIN...

Input

• Dữ liệu nhập vào từ bàn phím gồm hai dòng:
  • Dòng thứ nhất chứa tự nhiên \(n\) \((n \leq 10.000.000)\)
  • Dòng thứ hai chứa ký tự \(ch\) (ký tự in hoa)

Output

• In ra màn hình một số duy nhất là số lượng ký tự \(ch\) trong \(n\) ký tự đầu tiên của dãy ký tự.

Example

40
O

5

30
L

0

Cho tam giác số như sau:

Hàng 1: 1
Hàng 2: 2 3 4
Hàng 3: 5 6 7 8 9
Hàng 4: 10 11 12 13 14 15 16
......

Yêu cầu: Cho số nguyên dương \(n\), hãy in ra \(S\) là tổng các số trên hàng thứ \(n\) của tam giác số đã cho.

Input

• Dữ liệu nhập vào từ bàn phím gồm một số tự nhiên \(n\) (\(n \leq 10.000.000\)).

Output

• In ra màn hình một số duy nhất \(S\) là tổng các số trên hàng thứ \(n\) của tam giác số.

Example

2

9

4

91

An thích các số may mắn. Mọi người đều biết rằng các số may mắn là các số nguyên dương chỉ chứa các chữ số thuộc tập \({6, 8}\). Ví dụ: các số \(68, 866, 6\) là số may mắn và \(5, 18, 678\) thì không. An gọi một số là gần may mắn nếu nó chia hết cho một số may mắn. Lưu ý rằng tất cả các số may mắn đều là số gần may mắn, vì bất kỳ số nào cũng chia hết cho chính nói.

Bạn hãy giúp An kiểm tra xem số \(n\) cho trước có là số gần may mắn hay không?

Input

• Gồm một dòng chứa số nguyên \(n\) \((0 \leq n \leq 10^{6})\).

Output

• Nếu \(n\) là số gần may mắn thì ghi ra YES, ngược lại ghi ra NO.

Example

12

YES

10

NO

Hiếu là một học sinh thích học môn Toán, bạn ấy thường khám phá những kiến thức toán học rất thú vị.

Bạn Hiếu đang tìm hiểu về số chính phương (là bình phương của một số tự nhiên, ví dụ \(9, 16, 25, 49, \dots\)).

Yêu cầu: Nhập một số nguyên dương \(x\), tìm số chính phương gần \(x\) nhất.

Input

• Một số nguyên dương \(x\) không quá \(10^{12}\).

Output

• Số chính phương gần \(x\) nhất.

Example

10

9

140

144

Bạn Hiếu là một học sinh rất tài năng, không những giỏi Toán mà còn rất thích học môn tiếng Việt. Lần này bạn tìm hiểu về từ trong chuỗi. Từ là các ký tự liên tiếp cách nhau bởi dấu tách.

Yêu cầu: Cho chuỗi \(S\), hãy giúp bạn Hiếu tìm từ dài nhất có trong chuỗi, nếu có nhiều từ dài nhất thì in ra từ có thứ tự từ điển lớn nhất.

Input

• Chuỗi \(S\) có độ dài không quá \(10000\) ký tự.

Output

• Từ thỏa mãn đề bài.

Example

Giao duc Quan Son Tra

Quan

Lần này Hiếu khám phá các chữ số trong hệ thập phân, bạn ấy nhận thấy các số có chứa những "lỗ trống" nhất định. Số lỗ trống được tính như sau:

• Số \(8\) có 2 lỗ trống;
• Số \(0; 4; 6; 9\) có 1 lỗ trống;
• Số \(1; 2; 3; 5; 7\) không có lỗ trống.

Yêu cầu: Cho số nguyên dương \(n\), hãy tìm số lượng lỗ trống trong các chữ số của \(n\).

Input

• Chứa một số nguyên dương \(n\) (\(n \le 10^{10000}\)).

Output

• Số lỗ trống có trong \(n\).

Example

6789012345

6

Cho dãy số nguyên gồm \(n\) phần tử \(a_1,a_2,…,a_n\).

Yêu Cầu: Tìm bộ ba chỉ số \(i < j < k\) sao cho \(a_i - a_j + a_k\) là lớn nhất

Dữ liệu:

• Dòng đầu tiên chứa số \(n (3≤n ≤10^5)\).
• Dòng tiếp theo chưa \(n\) số nguyên \(a_1,a_2,…,a_n (-10^9≤a_i≤10^9)\).

Kết quả: Ghi ra một số nguyên duy nhất là giá trị lớn nhất của bài toán.

Input:

5
1 2 3 4 5

Output:

4

Subtask:

• 50% số test ứng với 50 số điểm bài toán có \(N \le 100\)
• 50% số test còn lại ứng với 50 số điểm còn lại có \(N \le 10^5\)

Có hai siêu máy tính cùng hoạt động, máy thứ nhất hoạt động liên tiếp trong 5 ngày thì được
tắt trong một ngày để bảo trì, sau ngày đó, máy tính này lại được bật để hoạt động lại. Tương tự
như vậy, máy thứ hai hoạt động liên tiếp trong 8 ngày, sau đó được tắt trong một ngày để bảo trì
trước khi tiếp tục làm việc. Hãy lập trình nhập vào giá trị của biến \(n\) và đưa ra màn hình trong \(n\)
ngày liên tiếp có bao nhiêu ngày có ít nhất một máy hoạt động (cả hai máy cùng bật và hoạt động
từ ngày đầu tiên trong chuỗi \(n\) ngày)

Input

• Một dòng chứa số nguyên \(n\ (1 ≤ n ≤ 10^{18})\)

Output:

• Một số nguyên duy nhất là số ngày cần tìm.

Input

60

Output

57

Giới hạn

• Sub1 (50): \(n \le 10^6\)
• Sub2 (50): \(n \le 10^{18}\)