Tin học trẻ B - Tỉnh Quảng Nam 2023

Thị xã Điện Bàn được coi là cái nôi của truyền thống hiếu học. Cậu bé Nam được sinh ra và lớn lên tại nơi đây. Em ấy rất tự hào về quê hương của mình. Nam nổi tiếng thông minh, học giỏi. Niềm đam mê của em là thích nghiên cứu, tìm tòi giải các bài toán khó. Chuyên đề “Số chính phương” trong tiết học tuần qua thầy giáo có nói:
Số chính phương là số tự nhiên có căn bậc hai là một số tự nhiên, hay nói cách khác, số chính phương bằng bình phương (lũy thừa bậc 2) của một số nguyên.

Ví dụ:

• \(1^2 = 1\)
• \(2^2 = 4\)
• \(3^2 = 9\)
• ….

Để nắm vững kiến thức, Nam được thầy giáo giao cho bài tập về nhà liên quan đến nội dung này. Yêu cầu cụ thể như sau:

Cho số nguyên dương \(N\) (\(N \le 10^7\)). Hãy đếm xem có bao nhiêu số chính phương trong phạm vi từ \(K\) đến \(N\) (\(1 \le K \le N\)).

Input

• Gồm một dòng chứa hai số nguyên \(N\) và \(K\) (mỗi số cách nhau một khoảng trắng).

Output

• In ra một số \(D\) là kết quả cần tìm.

Example

20 1

4

Scoring

• Có \(50\%\) số test tương ứng \(50\%\) số điểm của bài với \(1 \le N \le 10^4; 1 \le K \le N\).
• Có \(50\%\) số test tương ứng \(50\%\) số điểm của bài với \(10^4 < N \le 10^7; 1 \le K \le N\).

Được biết, giải nhì là thành tích cao nhất của Lâm sau khi tham gia kỳ thi Tin học trẻ cấp tỉnh năm học 2021-2022. Vì thế, Lâm đã được bố mẹ dẫn đi tham quan khu du lịch Đại Nam thuộc tỉnh Bình Dương. Nơi đây có trò chơi “MONEY - BALL” hấp dẫn làm Lâm thích thú. Trong trò chơi này, người người ta cho một dãy quả bóng tròn, mỗi quả bóng mang một ký tự chữ số hoặc ký tự chữ cái. Trò chơi yêu cầu loại bỏ một số quả bóng ra khỏi dãy sao cho \(K\) số lượng bóng cuối cùng theo đúng thứ tự vị trí đó tạo thành số lớn nhất. Con số này cũng chính là số tiền mà Lâm nhận được khi thắng cuộc trò chơi.

Sau khi nghe xong luật chơi, Lâm quyết tâm dành chiến thắng để có được tiền mua quà về cho em gái mình. Bạn nghĩ xem, với người giỏi lập trình như Lâm, em ấy sẽ làm cách nào để nhận được số tiền như mong đợi.

Input

• Dòng thứ nhất là một xâu \(s\) cho trước, xâu chỉ chứa các ký tự số và chữ cái (bao gồm cả ký tự thường và ký tự hoa). (\(s\) không quá \(10^6\) ký tự)
• Dòng thứ 2 chứa số nguyên dương \(K\) (\(1 \le\) số lượng số \(K \le 10^6\))

Output

• Ghi ra một dòng duy nhất chứa kết quả cần tìm.

Scoring

• Có \(50\%\) số test tương ứng \(50\%\) số điểm của bài với \(1 \le\) số lượng số \(K \le 20\), độ dài xâu \(st\) không quá \(255\) ký tự.
• Có \(25\%\) số test tương ứng \(25\%\) số điểm của bài với \(1 \le\) số lượng số \(K \le 10^3\), độ dài xâu \(st\) không quá \(10^3\) ký tự.
• Có \(25\%\) số test tương ứng \(25\%\) số điểm của bài với \(1 \le\) số lượng số \(K \le 10^6\), độ dài xâu \(st\) không quá \(10^6\) ký tự.

Example

A79C3e8
2

98

Tinhoc95Tre68nam2023
3

983

Thầy A nổi tiếng là thầy giáo dạy giỏi. Thầy rất được học sinh yêu quý. Năm học 2020-2021, thầy đã hứa với trò của mình rằng: “Bạn nào thi đỗ vào trường THPT chuyên Lê Thánh Tông hoặc Nguyễn Bỉnh Khiêm thì thầy sẽ tặng cho mỗi em một cuốn sách thuật toán & lập trình môn Tin học”.

Và đúng như lời thầy nói, sau khi biết được kết quả và số lượng thí sinh đỗ trường THPT chuyên, thầy A đã vội vã đi mua sách. Khi đến tại cửa hàng sách Fahasha, thầy được nhân viên giới thiệu là có \(N\) cuốn sách lập trình với nhiều ngôn ngữ khác nhau \((2 \le N \le 10^6)\), cuốn sách thứ \(i\) \((1 \le i \le N)\) có giá \(a_i\) đồng \((1 \le a_i \le 10^{15})\). Thầy A muốn chọn mua \(M\) cuốn sách để tặng cho \(M\) bạn \((2 \le M \le N)\).

Với tình yêu thương học trò, để đảm bảo tính công bằng giữa các em, không để em nào chịu thiệt, thầy \(A\) muốn mua các cuốn sách sao cho giá tiền chênh lệch giữa các cuốn sách có giá tiền cao nhất và thấp nhất là nhỏ nhất có thể.

Input

• Dòng \(1\): Chứa hai số nguyên dương \(N\) và \(M\) (các giá trị cách nhau một khoảng trắng).
• Dòng \(2\): Chứa \(N\) số nguyên dương \(a_1, a_2, \ldots, a_N\) (các giá trị cách nhau một khoảng trắng).
• Ràng buộc:
  • \(2 \le N \le 10^6\)
  • \(2 \le M \le N\)
  • \(1 \le a_i \le 10^{15}\)

Output

• Ghi ra một số \(K\) duy nhất là kết quả cần tìm.

Example

5 3
4 7 2 9 3

2

Scoring

• Subtask \(1\) (\(25\%\) số điểm):
  • \(N \le 15\)
  • \(M \le 15\)
  • \(1 \le a_i \le 100\)
• Subtask \(2\) (\(25\%\) số điểm):
  • \(N \le 10^3\)
  • \(M \le 10^3\)
  • \(1 \le a_i \le 10^5\)
• Subtask \(3\) (\(50\%\) số điểm):
  • \(N \le 10^6\)
  • \(M \le 10^6\)
  • \(1 \le a_i \le 10^{15}\)

Năm 2020, Công ty cổ phần liên doanh ô tô Hyundai Việt Nam đã xuất khẩu 5 lần, mỗi lần xuất đi với \(n\) chiếc xe ô tô bằng cách cho tàu thủy mang biển kiểm soát VN6789 vận chuyển qua đường biển.

Với mỗi chiếc ô tô thứ \(i\ (1 \le i \le n)\), có trọng lượng là \(K_i\ (1 \le K_i \le 10^9)\) và giá trị \(U_i\ (1 \le U_i \le 10^9)\). Công ty mong muốn xuất được nhiều xe nhưng tàu chỉ vận chuyển khối lượng hàng nằm trong quy định cho phép \(Q\ (1 \le Q \le 1000)\). Vì thế, công ty đã thử chọn phương án cho mỗi lần xuất khẩu là mỗi loại xe chỉ lấy đi một chiếc sao cho những chiếc xe đã xuất đi có tổng giá trị lớn nhất.

Kể từ những lần xuất khẩu của năm đó, lợi nhuận của công ty tăng lên vượt bậc. Dự kiến đến năm 2025, công ty cổ phần liên doanh ô tô Hyundai Việt Nam sẽ xuất khẩu ô tô thêm 5 lần nữa. Trong năm này, Giám đốc công ty đưa ra yêu cầu cho bộ phận kinh doanh phải tiếp tục hợp đồng với tàu chở hàng VN6789 để mỗi lần xuất khẩu, các xe sẽ chọn đi sao cho tổng giá trị năm 2025 phải cao hơn tổng giá trị các chiếc xe mỗi lần xuất đi năm 2020. Đồng thời, tính giá trị hao hụt qua các lần xuất khẩu giữa năm 2020 và 2025 là bao nhiêu? Biết rằng, phương án được chọn cho các chuyến đi năm 2025 là mỗi loại xe có thể chọn số lượng nhiều.

Yêu cầu: Để đáp ứng mong đợi của ban giám đốc, theo em bộ phận kinh phải làm thế nào để đưa ra giá trị hao hụt qua những lần xuất khẩu của năm 2020 so với 2025.

Input

• Dòng đầu tiên chứa hai số nguyên dương \(n\) và \(Q\) (các giá trị cách nhau một khoảng trắng)
• \(n\) dòng tiếp theo, mỗi dòng chứa hai số nguyên dương \(K_i\) và \(U_i\) (các giá trị cách nhau một khoảng trắng).

Output

• Ghi ra tệp văn bản BOATCAR.OUT gồm 3 dòng:
  • Dòng thứ nhất chứa tổng giá trị cho mỗi lần xuất khẩu xe đi trong năm 2020.
  • Dòng thứ hai chứa tổng giá trị cho mỗi lần xuất khẩu xe đi trong năm 2025.
  • Dòng thứ ba chứa giá trị hao hụt các xe đã xuất khẩu trong năm 2020 so với năm 2025.

Example

5 12
1 1
2 2
10 4
4 18
2 3 

24 
54 
150

Scoring

• Có \(40\%\) test tương ứng \(40\%\) số điểm của bài với \(n \le 30; 1 \le U_i \le 10^2; 1 \le K_i \le 10^2\)
• Có \(40\%\) test tương ứng \(40\%\) số điểm của bài với \(n < 10^2; 10^2 < U_i \le 10^6; 10^2 < K_i \le 10^6\)
• Có \(20\%\) test tương ứng \(20\%\) số điểm của bài với \(n \le 10^3; 10^6 < U_i \le 10^9; 10^6 \le K_i \le 10^9\)