LQDOJ Contest #10 - Sinh Nhật LQDOJ (Bảng A)

tknhatbm và tktungtd đang chơi cờ vua với tỉ số hiện tại lần lượt là \(A : B\). Nhận thấy mình có nguy cơ thua cuộc, tknhatbm liền lấy cục tẩy và xoá đi chữ số cuối cùng của điểm của tktungtd, nếu số điểm của tktungtd chỉ còn một chữ số thì tknhatbm sẽ không xoá chữ số nào vì làm vậy sẽ bị tktungtd nghi ngờ.

Ví dụ:

• \(B = 69\) thì Nhật chỉ xoá số \(9\) và được \(B = 6\)
• \(B = 5\) thì Nhật sẽ không xoá chữ số nào và được \(B = 5\)

Liệu rằng nếu Nhật lấy cục tẩy và xoá đi chữ số cuối cùng của điểm của Tùng thì Nhật có thể lật kèo và giành chiến thắng không?

Input

• Một dòng chứa \(2\) số tự nhiên \(A\), \(B\) (\(A,B \leq 10^{18}\)).

Output

• In ra A nếu tknhatbm thắng, nếu không thì in ra B nếu tktungtd thắng hoặc hoà.

Example

10 60

A

42 690

B

tktungtd và tk21quytransi đang thi lái xe với nhau. Ở thời điểm hiện tại, tktungtd đang cách vạch xuất phát \(T\) mét và lái xe với vận tốc \(D\) \((m/s)\), tk21quytransi đang cách vạch xuất phát \(Q\) mét và lái xe với vận tốc \(I\) \((m/s)\). Biết rằng đường đua là một đường thẳng và hai xe đang di chuyển song song theo đường thẳng đó và xa dần vạch xuất phát.

Hỏi sau \(K\) giây nữa thì khoảng cách giữa hai xe là bao nhiêu, giả sử hai xe đi thằng và luôn giữ vận tốc như thế.

Input

• Một dòng chứa \(5\) số tự nhiên \(T\), \(D\), \(Q\), \(I\), \(K\).

Output

• In ra khoảng cách giữa \(2\) xe sau \(K\) giây.

Scoring:

• Subtask \(1\) (\(50\%\) số điểm): \(K \le 10^6\)
• Subtask \(2\) (\(50\%\) số điểm): \(K \le 10^{18}\)

Example

1 5 2 4 1

0

1 100 1 99 2

2

Lipon là một cậu bé đam mê toán học, cậu rất muốn khám phá ra nhưng điều mới lạ trong toán học. Một ngày nọ, cậu khám phá ra dãy số Fibonacci, Lipon càng tìm hiểu sâu hơn thì biết được dãy số ấy được tạo ra bởi Leonardo Fibonacci. Cậu ấy liền nghĩ ra một dãy số và đặt tên nó là dãy số Lipon.

Dãy số Lipon được định nghĩa như sau:

• \(L_1\) \(=\) \(14\)
• \(L_i\) \(=\) \((L_{i-1} * 2 + 2) \bmod 1000\)

Khi đi học lại, Lipon giới thiệu cho Anfel (người bạn thân nhất của Lipon) thì Anfel đã thử thách Lipon. Anfel cho Lipon 2 số tự nhiên \(a\) và \(b\) và bảo Lipon tính tổng các số từ số thứ \(a\) đến số thứ \(b\) của dãy số Lipon trong vòng 1 giây. Vì số \(a\) và số \(b\) mà Anfel cho quá lớn nên Lipon không thể tính nhanh được, cậu nhờ các coder (trong đó có bạn) để giải hộ thử thách của Anfel.

Vì là một coder tốt bụng, bạn hãy giúp Lipon nhé.

Input

• Dòng đầu tiên chứa hai số tự nhiên \(a\) và \(b\) \((a\leq b\leq 10^{16})\)

Output

• Dòng đầu tiên là kết quả tìm được

Subtasks

• Subtask 1: \((a\leq b\leq 10^{5})\) (40% số điểm)
• Subtask 2: \((a\leq b\leq 10^{16})\) (60% số điểm)

Example

1 10

1348

tk21quytransi là một vận động viên bóng rổ chuyên nghiệp. Một ngày tk21quytransi muốn đếm lại xem hiện tại mình đang có bao nhiêu chiếc giày. Sau khi kiểm tra, tk21quytransi còn \(n\) chiếc giày, chiếc thứ \(i\) có màu độ sáng \(s_i\) (\(1 \leq i \leq n\)), độ sáng càng lớn thì màu càng sáng.
Mỗi trận đấu tk21quytransi lấy ra một đôi sử dụng, sau trận đấu đó, anh tháo giày và tặng lại cho các fan hâm mộ của mình. Hai chiếc giày mà anh chọn phải có độ sáng chênh lệch nhau không quá \(d\), tức là hai chiếc giày thứ \(i\) và \(j\) (\(i ≠ j\)) có thể được chọn nếu \(\lvert s_i - s_j \rvert \leq d\).
Em hãy viết chương trình tính giúp tk21quytransi xem với \(n\) chiếc giày hiện có anh ấy sẽ chơi được tối đa bao nhiêu trận đấu.

Input

• Dòng đầu tiên chứa số tự nhiên \(n\) và \(d\) (\(n \leq 10^6, d \leq 10^9\)).
• Dòng tiếp theo chứa \(n\) só tự nhiên \(s_1, s_2, ..., s_n\) (\(s_i \leq 10^9\)).

Output

• In ra số trận đấu tối đa tk21quytransi có thể chơi được.

Scoring

• Subtask \(1\) (\(25\%\) số điểm): \(d = 0, a_i \le 10 ^ {6}\)
• Subtask \(2\) (\(25\%\) số điểm): \(d = 0\)
• Subtask \(3\) (\(25\%\) số điểm): \(n \le 10 ^ {3}\)
• Subtask \(4\) (\(25\%\) số điểm): \(n \le 10 ^ {6}\)

Example

5 1
4 5 1 3 2

2

tknhatbm là một người nghiện game. Mỗi ngày tknhatbm đều vô game và chơi tới đêm khuya. Hôm nay, trong lúc đang chơi thì tknhatbm bị văng game, phát hiện ra mình đã bị hack tài khoản. Để lấy lại tài khoản, tknhatbm cần nhập đúng mật khẩu của mình, nhưng giờ thứ tknhatbm biết là mật khẩu của mình là tổng các số trong dãy \(A\) = \(1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, ...\) có chỉ số từ \(A\) đến \(B\) . Là một người nghiện game nên tknhatbm không biết phải làm sao để khôi phục mật khẩu , đành nhờ các bạn trên LQDOJ giúp.
Yêu cầu : Em hãy viết chương trình giúp Nhật tính ra mật khẩu tài khoản game.

Input:

• Một dòng duy nhất chứa \(2\) số nguyên dương \(a\) và \(b\) \((1 \leq a,b \leq 10^{18})\)

Output:

• Một dòng duy nhất chứa kết quả của bài toán sau khi chia lấy dư cho \(10^9+7\).

Scoring:

• Subtask \(1\) (\(50\%\) số điểm): \(a,b \leq 10^6\)
• Subtask \(2\) (\(50\%\) số điểm): \(a,b \leq 10^{18}\)

Example

1 4

8

Để kỷ niệm sinh nhật lần thứ \(4\) của LQDOJ, BTC đã đưa ra trò chơi rút gỗ dành riêng cho các bạn Tiểu học như sau:
Có \(n\) chồng gỗ, chồng thứ \(i\) có \(h_i\) viên gỗ. Mỗi lần chơi, các bạn rút một viên gỗ ở chồng bất kỳ, số điểm đạt được chính là số viên gỗ ở chồng vừa rút viên gỗ ra.
Bạn có \(k\) lần chơi, nếu bạn có số điểm cao nhất sẽ được BTC tặng một chiếc áo sinh nhật LQDOJ lần thứ \(4\) rất xịn xò, xinh xắn.

Ví dụ, \(n=3, k = 3\) và lần lượt có số viên gỗ của mỗi chồng tương ứng là \({4;5;2}\). Bạn sẽ rút hai viên gỗ ở chồng thứ hai và một viên gỗ ở chồng thứ nhất. Tổng số điểm là \(5 + 4 + 4 = 13\). Đây cũng là số điểm lớn nhất của trò chơi này.

Yêu cầu : Cho \(n, k\) và dãy \(h_1,h_2,...,h_n\). Hãy giúp các thí sinh Tiểu học chơi trò rút gỗ đạt số điểm tối đa.

Input:

• Dòng đầu tiên chứa hai số nguyên \(𝑁\) và \(𝐾\).
• Dòng thứ hai chứa \(𝑁\) số nguyên \(h_i\) tương ứng với số viên gỗ của chồng thứ \(𝑖\).

Output:

• Một dòng duy nhất chứa kết quả của bài toán.

Scoring:

• Subtask \(1\) (\(60\%\) số điểm): \(n,k \le 10^5; h_i \le 10^5\)
• Subtask \(2\) (\(40\%\) số điểm): \(n \le 10^5; k \le 10^9; h_i \le 10^9,\)

Example

3 3
4 5 2

13