Tổng Ami

CarlavierVN

Cho số tự nhiên n (0 \le n \le 100).
In ra hai số nguyên a,b chứa được trong 32-bit thỏa mãn a+b=n.

Input

  • Số tự nhiên n.

Output

  • Hai số nguyên a, b thỏa mãn yêu cầu đề bài, cách nhau một dấu cách.

Example

Sample input

5

Sample output
2 3

Tổng chữ số các số siêu lẻ không vượt quá N

Số tự nhiên x được gọi là số siêu lẻ:

  • Các chữ số của x đều lẻ.
  • Tổng các chữ số của x là số lẻ.

Ví dụ: Các số tự nhiên siêu lẻ đầu tiên là: 1, 3, 5, 7, 9, 111, 113 . . .
Input: Gồm 1 dòng duy nhất là số tự nhiên N (1=<N<=10^18).
Output: In ra tổng chữ số các số siêu lẻ không vượt quá N.

Input: 9
Output: 25
Input: 117
Output: 49

Tính tổng 04

letangphuquy

Nhập vào số n (1 \le n \le 10^9), tính:

P = 1^3 + 2^3 + 3^3 + ... + n^3

Hãy in ra P sau khi chia lấy dư cho 2004010501

(tham khảo lời giải: link)

Tính tổng 02

letangphuquy

Nhập vào số n (1 \le n \le 10^9), tính:

P = 1^2 + 2^2 + 3^2 + 4^2 + \dots + n^2

Hãy in ra P sau khi chia lấy dư cho 2004010501

Tính tổng 01

letangphuquy

Nhập vào số n (1 \le n \le 10^9), tính:

P = 1.2 + 2.3 + 3.4 + 4.5 + \dots + (n-1)n

Hãy in ra P sau khi chia lấy dư cho 2004010501

Hệ số nhị thức

kitsune

Cho hai số nguyên nk. Hãy tính \displaystyle \binom{n}{k}.

Input

  • Một dòng duy nhất chứa hai số nguyên nk.

Output

  • Một dòng duy nhất chứa một số nguyên là phần dư của đáp án khi chia cho 10 ^ 9 + 7.

Constraints

  • 0 \leq k \leq n \leq 10^{18}.

Scoring

  • Subtask 1 (20\% số điểm): n \leq 10.
  • Subtask 2 (20\% số điểm): n \leq 10^3.
  • Subtask 3 (20\% số điểm): n \leq 10^6.
  • Subtask 4 (20\% số điểm): n \leq 10^9.
  • Subtask 5 (20\% số điểm): Không có ràng buộc gì thêm.

Example

Test 1

Input
5 2
Output
10

Tổng chữ số

zipdang04

T câu hỏi có dạng: Cho hai số ab. Tính tổng toàn bộ các chữ số của các số từ a tới b.

Hãy trả lời T câu hỏi trên.

Input

  • Dòng đầu tiên chứa số T
  • T dòng sau, mỗi dòng lần lượt chứa 2 số ab

Output

In ra T dòng lần lượt tương ứng với kết quả của T câu hỏi trên.

Sample

Sample 1

Input

2
5 12
12 60

Output

41
378

Counting Towers II

edatnvt

Note: this problem differs from CSES - Counting Towers | Đếm tháp only in the constraints of t and n.

Your task is to build a tower whose width is 2 and height is n. You have an unlimited supply of blocks whose width and height are integers.

For example, here are some possible solutions for n = 6:

Given n, how many different towers can you build? Mirrored and rotated towers are counted separately if they look different.

Input

  • The first input line contains an integer t: the number of tests.
  • After this, there are t lines, and each line contains an integer n: the height of the tower.

Output

  • For each test, print the number of towers modulo 10^9 + 7.

Constraints

  • 1 \le t \le 10^4
  • 1 \le n \le 10^{18}

Example

Sample Test
Input
3
2
6
1337
Output
8
2864
640403945

Bộ k nguyên tố

huyhau6a2

Cặp số x, y được gọi là nguyên tố cùng nhau khi ước chung lớn nhất của chúng bằng 1
Yêu cầu: Cho 2 số n, k. Hãy đếm số cách chọn k số có giá trị trong khoảng [1,n] sao cho chúng nguyên tố cùng nhau. 2 bộ số a_1, a_2, ...,a_nb_1, b_2, ..., b_n được cho là khác nhau khi có giá trị i (1\leq i\leq k) thỏa mãn a_i khác b_i. Vì kết quả có thể rất lớn nên bạn hãy xuất kết quả mod 10^9+7

Input

  • Gồm duy nhất hai số nk

Output

  • Gồm duy nhất một số là số bộ k nguyên tố thỏa mãn mod 10^9+7

Constraints

  • n\leq 10^6,k\leq 10^{18}

Scoring

  • Subtask #1 (20\% số test): n\leq 3
  • Subtask #2 (30\% số test): n\leq 10^3
  • Subtask #3 (50\% số test): Không có ràng buộc gì thêm

Example

Test 1

Input
3 2
Output
7
Note

Có 7 bộ số: (1,1,1); (1,1,2); (1,2,1); (1,2,2); (2,1,1); (2,1,2); (2,2,1)

Test 2

Input
4 4
Output
239

Test 3

Input
2 64
Output
582344007

Two Groups

dang7rickroll

Cho dãy số a gồm n phần tử. Hãy tìm cách chia dãy số này thành 2 dãy con liên tiếp s_1,s_2 (có thể là dãy rỗng) sao cho:

  • Với mọi 1 \le i \le n, a_i thuộc đúng một nhóm.
  • Tổng |sum(s_1)|-|sum(s_2)| đạt giá trị lớn nhất có thể. Trong đó sum(s_1) thể hiện cho tổng tất cả các phần tử của dãy s_1

Input

  • Dòng thứ nhất chứa số nguyên dương t (t \le 10^3) - số testcase;
  • Mỗi testcase tiếp theo có dạng như sau:
    • Dòng thứ nhất chứa số nguyên dương n (n \le 10^3);
    • Dòng thứ hai chứa n số nguyên a_1,a_2,...,a_n (-10^9 \le a_i \le 10^9)

Output

  • Ứng với mỗi test case in ra giá trị |sum(s_1)|-|sum(s_2)| lớn nhất có thể.

Example

Test 1

Sample input
4
2
10 -10
4
-2 -1 11 0
3
2 3 2
5
-9 2 0 0 -4
Sample output
0
8
7
11
Explanation
  • Trong testcase thứ nhất, ta có thể chia thành hai dãy s_1=\{10\}, s_2=\{-10\}.
  • Trong testcase thứ hai, ta có thể chia thành hai dãy s_1=\{0;11;-1\}, s_2=\{-2\}
  • Trong testcase thứ ba, ta có thể chia thành hai dãy s_1=\{2;3;2\}, s_2=\{\}
  • Trong testcase thứ tư, ta có thể chia thành hai dãy s_1=\{-9;-4;0\}, s_2=\{2;0\}

Note

  • Nguồn: CF Round 832 div 2

Bất ngờ chưa?

Toilaaibanbietko7A4

Bài tập này chỉ là một bài tập để giải trí, không nên xem bài tập này như là một cái gì đó quá khó chịu đâu ❤️

Mình nghĩ dạo này mọi người cũng không có nhiều chuyện vui đâu, thế nên bài tập này ra đời để cho mấy bạn giải trí thêm một chút.
Bạn sẽ nhận một con số k. Trong mỗi test, con số k được cho sẽ chính là số thứ tự của test.
Trong 12 test đầu tiên, sẽ có một xâu kí tự S với độ dài tối đa là 10^3, chỉ bao gồm các kí tự thường. Ta có bánh xe gồm 26 ô, mỗi ô điền một kí tự thường, sao cho ô ở trên ô đó có giá trị ASCII nhỏ hơn một đơn vị (ngoại trừ phía trên 'a' là kí tự 'z'). Đối với kí tự thứ i, thì nếu như q < 0 thì sẽ từ vị trí chứa kí tự S_i thì sẽ quay bánh xe lên phía trên |q| ô, còn nếu như q > 0 thì sẽ từ vị trí chứa kí tự S_i thì sẽ quay bánh xe xuống phía dưới q ô. Ghi lại kết quả của từng vị trí. In ra xâu S sau khi "xoay vòng vòng" như vậy (Vui lòng xuống dòng dưới các đáp án để máy chấm nhận được đáp án của bạn). Nếu đáp án đúng, máy chấm sẽ đưa ra một clue là một số có 2 chữ số.

Example

Nếu S_i = 'b'q = -2 thì sẽ xoay bánh xe lên hai nấc, tương ứng với kết quả là 'z'. Lúc này S_i = 'z'.

INPUT

1
b
-2

OUTPUT

z

Feedback

Accepted. The clue of this test is "nothing"

Để qua được test cuối cùng (test số 13), bạn cần phải in ra Password dựa trên tất cả các clue mà bạn đã tìm thấy (không in dấu cách). Chưa hết, bạn cần phải sử dụng tất cả các clue theo thứ tự xuất hiện trong bộ test để tìm ra keyword thực sự.
Nếu trong test cuối, bạn tìm ra được Passwordkeyword, thì sẽ được toàn bộ số điểm, bằng không sẽ không có điểm.
Chúc các bạn may mắn . Hãy cố gắng trở thành người đầu tiên tìm ra được keyword nhé (không tính mấy bác superuser 🙃)

XOR-Sum

dang7rickroll

Tính 1 \oplus 2 \oplus 3 \oplus \dots \oplus n với n được nhập từ bàn phím.

Input

  • Dòng 1 chứa t (t \leq 10^5) - số câu hỏi.
  • t dòng tiếp theo, mỗi dòng chứa một số nguyên dương n.

Output

  • Ứng với mỗi câu hỏi in ra đáp án cần tìm.

Constraints

  • Subtask 1 [10%]: n \le 10;
  • Subtask 2 [90%]: n \le 10^{12}.

Example

Test 1

Input
2
3
6
Output
0
7

Note

  • Nguồn: SPOJ

Real Value

dang7rickroll

"Real Value" của một số nguyên dương x là số có 1 chữ số thu được bằng cách làm như sau:

  • Nếu n \leq 5 thì Realval(x)=x
  • Ngược lại, Realval(x)= Realval(Y) với Y là tổng các chữ số của x chia cho 2.

Input

  • Số nguyên dương n (n \le 10^{18})

Output

  • Realval(n)

Example

Test 1

Input
28032007
Output
1

Bonus Có một truyền thuyết kể rằng real_value ngày sinh của một người chính là số giải của người đó khi tham gia cuộc thi VOI =))

Căn bậc B của A

NguyenHuuNhatQuang

Cho hai số nguyên dương AB, tìm số nguyên dương C sao cho C^B=A.

Input

  • Gồm 1 dòng duy nhất chứa 2 số A, B.

Output

  • In ra số C cần tìm.

Constraints

  • C \leq 10^5, B \leq 3 \times 10^4.
  • A có không quá 15 \times 10^4 chữ số.
  • Dữ liệu đầu vào đảm bảo luôn tìm được C nguyên dương.

Example

Example test 1

Sample input 1
25921 2
Sample output 1
161

Example test 2

Sample input 2
353393243 3
Sample output 2
707

Example test 3

Sample input 3
254116810000 4
Sample output 3
710

Giá trị lớn nhất

bruh

Cho một dãy gồm n phần tử có giá trị ban đầu bằng 0.

Cần thực hiện m thao tác thuộc hai loại:

  • Tăng giá trị của mỗi phần tử trong một đoạn con liên tiếp lên vài đơn vị.
  • Tìm giá trị lớn nhất trong đoạn con bất kỳ

Input

  • Dòng đầu tiên: Chứa hai số n,m (1 \le n \le 50000, 1 \le m \le 10^5)
  • m dòng tiếp theo, mỗi dòng có thể có một trong hai định dạng sau:
  • 0 u v k: Tăng mỗi phần tử từ vị trí u đến vị trí v lên k đơn vị (1 \le u \le v \le n, 0 < k)
  • 1 u v: Cho biết giá trị lớn nhất thuộc đoạn [u, v] là bao nhiêu?

Dữ liệu vào đảm bảo giá trị của một phần tử không bao giờ vượt quá 2^{31}-1

Output

Với mỗi câu hỏi, ghi ra đáp án trên từng dòng

Example

Sample input:

6 3
0 1 3 3
0 4 6 4
1 1 6

Sample output:

4

Nguồn: vn.spoj.vn

Comment ça va ?

dang7rickroll

Steve học ngoại ngữ. Bài tập hôm nay là học thuộc tên các chữ số (ở hệ cơ số 10). Để rèn luyện kỹ năng phản xạ nhanh, Steve viết một dãy n số nguyên dương a_1, a_2, . . ., a_n, mỗi số không vượt quá 10^9 và không có các số 0 không có nghĩa ở đầu (1\leq n\leq 1000). Với mỗi số Steve sẽ đọc chữ số có tên lớn nhất (theo thứ tự từ điển) trong số các tên xuất hiện trong số này.

Ví dụ, Steve học tiếng Pháp. Tên các chữ số trong tiếng Pháp là như sau:

Chữ số Tên tiếng Pháp
0 zero
1 un
2 deux
3 trois
4 quatre
5 cinq
6 six
7 sept
8 huit
9 neuf

Với số 908, chữ số mà Steve đọc là zero.

Yêu cầu: Cho dãy 10 tên các chữ số từ 0 đến 9, số nguyên n và n số nguyên a_1, a_2, . . ., a_n. Với mỗi số nguyên hãy nêu tên chữ số được đọc.

Input

  • Dòng đầu tiên chứa 10 xâu, xâu thứ i là tên chữ số i, 0 \le i \le 9, mỗi xâu không quá 50 ký tự, các xâu cách nhau một dấu cách,
  • Dòng thứ 2 chứa số nguyên n,
  • Dòng thứ i trong n dòng tiếp theo chứa số nguyên a_i.

Output

  • Đưa ra n tên các chữ số được đọc, mỗi tên đưa ra trên một dòng, dòng thứ i xác định tên đọc trong số a_i.

Example

Example test

Sample Input
zero un deux trois quatre cinq six sept huit neuf
3
123
456
908
Sample Output
un
six
zero

Note

  • Nguồn: NTT - YB

Động viên đàn bò

Small

Bác John dạo này lười đến nỗi không muốn bảo trì các con đường dẫn bác đến thăm N\ (5 \le N \le 10.000) cánh đồng (đánh số từ 1 đến N) nữa. Mỗi cánh đồng là nơi ở của một cô bò. Bác John có kế hoạch loại bỏ nhiều nhất P\ (N-1 \le P \le 100,000) con đường sao cho các cánh đồng vẫn liên thông.

Bạn phải xác định N-1 con đường cần giữ lại.

Đường nối hai chiều j nối giữa cánh đồng S_jE_j (1 \le S_j \le N; 1 \le E_j \le N; S_j \neq E_j) và cần L_j (0 \le Lj \le 1000) thời gian để di chuyển. Không có hai cánh đồng nào được nối trực tiếp bởi nhiều hơn một con đường.

Đàn bò buồn vì hệ thống giao thông của chúng sắp bị rút gọn. Bạn phải thăm mỗi cô bò ít nhất một lần trong ngày để động viên. Mỗi lần thăm cánh đồng i (dù chỉ đi ngang qua), bạn phải trò chuyện với cô bò trong thời gian C_i\ (1 \le C_i \le 1000).

Bạn sẽ nghỉ lại đêm trên cùng một cánh đồng (bạn sẽ được chọn) cho đến khi đàn bò đều đã hết bị suy sụp. Bạn sẽ trò chuyện với cô bò trong cánh đồng mà bạn nghỉ lại ít nhất 2 lần vào buổi sáng thức dậy và vào buổi tối khi trở về nghỉ.

Giả dụ bác John theo lời khuyên của bạn giữ lại một số con đường và bạn sẽ chọn cánh đồng tối ưu nhất để nghỉ lại, hãy xác định thời gian nhỏ nhất bạn cần để thăm tất cả đàn bò ít nhất một lần trong ngày.

Input

  • Dòng 1: Hai số nguyên NP cách nhau bởi khoảng trắng
  • Dòng 2..N+1: Dòng i+1 chứa một số nguyên duy nhất C_i
  • Dòng N+2..N+P+1: Dòng N+j+1 chứa ba số nguyên phân biệt: S_j, E_jL_j

Output

  • Một số nguyên duy nhất, tổng thời gian cần để thăm tất cả đàn bò (bao gồm hai lần thăm cô bò ở nơi mà bạn nghỉ).

Example

Test 1

Input

5 7
10
10
20
6
30
1 2 5
2 3 5
2 4 12
3 4 17
2 5 15
3 5 6
4 5 12

Output

176

Note

NN


Nguồn: SPOJ

Xây dựng thành phố

Small

Nước Anpha đang lập kế hoạch xây dựng một thành phố mới và hiện đại. Theo kế hoạch, thành phố sẽ có N vị trí quan trọng, được gọi là N trọng điểm và các trọng điểm này được đánh số từ 1 tới N. Bộ giao thông đã lập ra một danh sách M tuyến đường hai chiều có thể xây dựng được giữa hai trọng điểm nào đó. Mỗi tuyến đường có một thời gian hoàn thành khác nhau.

Các tuyến đường phải được xây dựng sao cho N trọng điểm liên thông với nhau. Nói cách khác, giữa hai trọng điểm bất kỳ cần phải di chuyển được đến nhau qua một số tuyến đường. Bộ giao thông sẽ chọn ra một số tuyến đường từ trong danh sách ban đầu để đưa vào xây dựng sao cho điều kiện này được thỏa mãn.

Do nhận được đầu tư rất lớn từ chính phủ, bộ giao thông sẽ thuê hẳn một đội thi công riêng cho mỗi tuyến đường cần xây dựng. Do đó, thời gian để hoàn thành toàn bộ các tuyến đường cần xây dựng sẽ bằng thời gian lâu nhất hoàn thành một tuyến đường nào đó.

Yêu cầu: Giúp bộ giao thông tính thời gian hoàn thành các tuyến đường sớm nhất thỏa mãn yêu cầu đã nêu.

Input

  • Dòng chứa số NM (1 ≤ N ≤ 1000; 1 ≤ M ≤ 10000).
  • M tiếp theo, mỗi dòng chứa ba số nguyên u, vt cho biết có thể xây dựng tuyến đường nối giữa trọng điểm u và trọng điểm v trong thời gian t. Không có hai tuyến đường nào nối cùng một cặp trọng điểm.

Output

  • Một số nguyên duy nhất là thời gian sớm nhất hoàn thành các tuyến đường thỏa mãn yêu cầu đã nêu.

Example

Test 1

Input

5 7
1 2 2
1 5 1
2 5 1
1 4 3
1 3 2
5 3 2
3 4 4

Output

3


Nguồn: SPOJ

MULTI-GAME

dang7rickroll

Do bão lũ nên An và Bình phải ở nhà. Vì quá chán nên An và Bình đã nghĩ ra trò chơi với những con số như sau:

An và Bình, mỗi người sẽ chọn một số nguyên dương bất kỳ (gọi con số An chọn là X và con số Bình chọn là Y). Có tổng cộng N lượt chơi và An là người chơi trước. Ở mỗi lượt chơi thì người chơi sẽ gấp đôi con số mình đã chọn lên (tức là X=2\times X hoặc Y=2\times Y).

Yêu cầu: Sau N lượt chơi, gọi G = \left[ \frac{\max(X, Y)}{\min(X, Y)} \right]. Hãy tìm giá trị G.

Input

  • Dòng đầu tiên chứa Q - số lượng câu hỏi cần trả lời (Q \le 10^5)
  • Q dòng tiếp theo, mỗi dòng chứa ba số nguyên dương X, Y, N (X, Y, N \le 10^{12}) - lần lượt là con số ban đầu mà An chọn, Bình chọn và số lượt chơi.

Output

  • Ứng với mỗi câu hỏi in ra giá trị G thỏa mãn yêu cầu đề bài.

Example

Example test

Sample Input
2
1 1 2
1 2 3
Sample Output
1
1

Note

  • Ở truy vấn thứ nhất:
    • Lượt 1: An gấp đôi số của mình lên (1 \times 2 = 2);
    • Lượt 2: Bình gấp đôi số của mình lên (1 \times 2 = 2);
    • Sau hai lượt chơi, giá trị G=1.
  • [\alpha] là phần nguyên của giá trị thực \alpha

Scoring

  • Subtask 1 (20\%): Q \le 100, X, Y, N \le 10^4
  • Subtask 2 (80\%): Không ràng buộc gì thêm.

Bánh xe

Small

Alice và Bob đang học về cơ khí và họ gặp đôi chút khó khăn về sự chuyển động của các bánh răng. Việc kết nối phức tạp và họ cần bạn giúp đỡ.

Một hệ thống các bánh răng bao gồm các bánh răng trong đó một số cặp liên kết chuyển động với nhau. Về mặt cơ học, hai bánh răng kết nối với nhau tức là các bánh răng của chúng cài vào nhau và khi bánh răng này chuyển động kéo theo chuyển động của bánh răng kia theo chiều ngược lại.

Mỗi bánh răng thuộc một trong 2 loại. Bánh răng T là bánh răng loại kết nối ngoài nếu T kết nối chuyển động với một bánh răng khác thì bánh răng đó nằm ngoài T. Bánh răng T là bánh răng loại kết nối trong nếu T kết nối chuyển động với một bánh răng khác thì bánh răng đó nằm trong T.

Trong ví dụ bên trái có 5 bánh răng đánh số từ 1 tới 5, có 5 sự kết nối giữa các bánh răng là (1,2), (1,3), (2,4),(3,4),(4,5). Nếu ta quay bánh răng 1 theo dương, kéo theo bánh răng 2 và 3 quay theo chiều âm, kéo theo bánh răng 4 quay theo chiều dương. Cuối cùng bánh răng 5 quay theo chiều âm.

Trong ví dụ bên phải có 6 bánh răng, có sự kết nối giữ các bánh răng là (1,2),(1,3),(1,4),(1,5),(2,6), (3,6),(4,6),(5,6). Khi quay bánh răng 1 theo chiều dương, các bánh răng 2, 3, 4, 5 quay theo chiều âm, bánh răng 6 quay theo chiều âm.

Cho biết hệ thống liên kết giữa các bánh răng và q truy vấn, mỗi truy vấn Alice và Bob mỗi người chọn một bánh răng (có thể trùng nhau) và quay theo chiều nhất định. Hỏi hệ thống bánh răng có ổn thỏa không? Hệ thống ổn thỏa nếu không có hai bánh răng nào bị tác động lực dẫn quay theo hai chiều khác nhau?

Input

  • Dòng đầu tiên chứa ba số nguyên n,m,q\ (1≤n,q≤10^5;0≤m≤10^5) là số bánh răng của hệ thống, số cặp liên kết giữa các bánh răng và số truy vấn.
  • Dòng thứ 2 chứa n số nguyên a_1,a_2,…,a_n\ (a_i∈{-1,1}) trong đó a_i=1 nếu bánh răng thứ i nếu liên kết với một bánh răng nào đó thì bánh răng đó nằm bên ngoài bánh răng i, a_i=-1 nếu bánh răng thứ i nếu liên kết với một bánh răng nào đó thì bánh răng đó nằm bên trong bánh răng i.
  • m dòng tiếp theo mỗi dòng chứa hai số nguyên phân biệt u,v\ (1≤u,v≤n) mô tả có liên kết chuyển động giữa hai bánh răng u,v.
  • q dòng tiếp theo, mỗi dòng chứa 4 số nguyên g_1,g_2,d_1,d_2\ (1≤g_1,g_2≤n;d_1,d_2∈{-1,1}) cho biết bánh răng mà Alice chọn, bánh răng mà Bob chọn, chiều chuyển động của bánh răng g_1, chiều chuyển động của bánh răng g_2.

Output

  • Gồm q dòng, dòng thứ i ghi YES nếu hệ thống ổn thỏa, ghi NO nếu hệ thống không ổn thỏa

Example

** Sample input **

8 8 3
1 1 1 1 1 1 1 1
1 2
1 3
2 4
3 4
4 5
6 7
7 8
8 6
1 5 1 1
1 5 1 -1
6 7 1 1

** Sample output **

NO
YES
NO


Nguồn: CĐ DHBB Chuyên Hạ Long