2022 · Tin học trẻ - Bảng B · Quảng Trị

Nếu có số tự nhiên ~x~ chia hết cho số tự nhiên ~y~ thì ta nói ~y~ là ước số của ~x~. Ví dụ: ~1, 2, 3, 12~ là ước của ~12~; còn ~5, 8~ thì không phải là ước của ~12~.

Huy có một danh sách gồm ~N~ số nguyên dương ~A[1],A[2],...,A[N]~. Huy đặc biệt thích các số tự nhiên có đúng hai ước nên sẽ thay đổi các phần tử thuộc dãy ~A~ nếu chúng có nhiều hơn hai ước. Với mỗi phần tử ~A[i]~ (~1 \leq i \leq N~) có nhiều hơn hai ước Huy sẽ lặp lại việc thay đổi ~A[i]=A[i]-1~ cho đến khi ~A[i]~ có đúng hai ước.

Yêu cầu: Cho ~N~ và dãy ~A~, hãy in ra dãy ~A~ sau khi Huy thay đổi.

Input

Vào từ file văn bản HAIUOC.INP:

• Dòng đầu tiên là số nguyên dương ~N~;
• Dòng thứ hai lần lượt là ~N~ số nguyên dương ~A[1],A[2],...,A[N]~.

Output

Vào từ file văn bản HAIUOC.OUT là dãy ~A~ sau khi thay đổi. Các số viết cách nhau một dấu cách.

Scoring

• Subtask ~1~ ~(60\%)~: ~2 \leq N,A[i] \leq 2000~;
• Subtask ~2~ ~(20\%)~: ~2 \leq N,A[i] \leq 20000~;
• Subtask ~3~ ~(20\%)~: ~2 \leq N,A[i] \leq 2000000~.

Example input 1

3
2 9 16

Example output 1

2 7 13

Cư dân trên hành tinh Gliese sống và sinh hoạt với điều kiện hết sức thú vị. Họ tập trung tại một khu bằng phẳng, có thể xem như là hệ trục toạ độ ~Oxy~ ở trái đất. Có ~N~ cư dân sinh sống tại đây, cư dân thứ ~i~ đang ở toạ độ ~(x[i],y[i])~ và đang di chuyển theo hướng ~s[i]~. Trong đó ~s[i]~ = L là di chuyển sang trái, ~s[i]~ = R là di chuyển sang phải. Họ chỉ di chuyển theo hướng duy nhất này. Cư dân Gliese thích gặp nhau nên mỗi lần gặp nhau họ sẽ bắt tay nhau 3 lần, chào hỏi nhau, rồi mỗi cư dân tiếp tục di chuyển theo hướng của họ.

Yêu cầu: Cho ~N~, vị trí và hướng di chuyển của ~N~ cư dân, hãy viết chương trình tính số lượng cái bắt tay được ~N~ cư dân thực hiện. Biết rằng tốc độ di chuyển của mỗi cư dân là như nhau nên nếu cùng hướng đi thì không bao giờ gặp nhau do không có hai cư dân nào ở cùng toạ độ.

Input

Vào từ file văn bản BATTAY.INP:

• Dòng đầu tiên là số nguyên dương ~N~;
• ~N~ dòng tiếp theo, dòng thứ ~i~ là tọa độ ~(x[i],y[i])~ của cư dân thứ ~i~;

Output

Vào từ file văn bản BATTAY.OUT một số nguyên duy nhất là số lượng bắt tay đã được ~N~ cư dân thực hiện.

Scoring

• Subtask ~1~ ~(40\%)~: ~1 \leq N \leq 2000; 1 \leq x[i],y[i] \leq 2022~;
• Subtask ~2~ ~(30\%)~: ~2000 < N \leq 10^5; -10^9 \leq x[i] \leq 10^9;y[i] = 2022~;
• Subtask ~3~ ~(30\%)~: ~2000 < N \leq 10^5; -10^9 \leq x[i],y[i] \leq 10^9~.

Example input 1

3
5 1
7 1
9 1
RLL

Example output 1

6

Note 1

• Hãy vẽ hệ trục toạ độ ~Oxy~, đánh dấu 3 điểm lên hệ trục toạ độ. Ta sẽ thấy cư dân 1 sẽ gặp cư dân 2 và 3 trong quá trình di chuyển nên họ bắt tay nhau 6 lần. Cư dân 2, 3 thì không gặp nhau.

Vào sinh nhật thứ 11 của mình, Harry Potter được mời đến trường phù thủy để học. Một trong những bài học đầu tiên là sử dụng cây đũa thần. Harry ra vườn hoa của trường để tập luyện.

Trường Hogwarts có một luống hoa dài trồng ~N~ cây hoa phép thuật, cây thứ ~i~ có vẻ đẹp là ~a[i]~. Chọn ra một đoạn gồm các cây hoa liền tiếp có tổng lớn nhất chính là vẻ đẹp của luống hoa. Nếu không có đoạn nào có tổng dương, thì vẻ đẹp của luống hoa được tính là ~0~.

Harry có thể không sử dụng đũa thần hoặc sử dụng đũa thần một lần duy nhất để làm phép thuật lên luống hoa. Phép thuật có thể tác động lên một đoạn bất kỳ gồm các cây hoa liền tiếp. Gọi ~[u..v]~ là đoạn mà Harry đã làm phép (~1 ≤ u ≤ v ≤ N~). Khi đó, cây hoa thứ ~i~ (với ~u ≤ i ≤ v~) sẽ có giá trị vẻ đẹp mới là ~a[i] * X~.

Harry muốn làm phép thuật sao cho vẻ đẹp của luống hoa là lớn nhất có thể. Tuy nhiên luống hoa khá dài và Harry chưa biết chọn đoạn nào để làm phép. Hãy giúp Harry!

Yêu cầu: Cho ~N, X, a~, hãy giúp Harry tính vẻ đẹp tối đa của luống hoa sau khi sử dụng phép thuật.

Input

Vào từ file văn bản FLOWER.INP:

• Dòng thứ nhất: hai số nguyên ~N, X~ (~1 \leq N \leq 5*10^5, -10^6 \leq X \leq 10^6~);
• Dòng thứ hai: ~N~ số nguyên ~a[1],a[2],...,a[N]~ (~-10^6 \leq a[i] \leq 10^6~).
-

Output

Vào từ file văn bản FLOWER.OUT một số nguyên duy nhất — vẻ đẹp tối đa của luống hoa sau khi Harry sử dụng phép thuật.

Scoring

• Subtask ~1~ ~(40\%)~: ~1 \leq N \leq 50~;
• Subtask ~2~ ~(20\%)~: ~50 < N \leq 500~;
• Subtask ~3~ ~(20\%)~: ~500 < N \leq 5000~.
• Subtask ~4~ ~(20\%)~: ~5000 < N \leq 5*10^5~.

Example input 1

5 2
-1 2 4 -3 4

Example output 1

14

Note 1

• Làm phép đoạn ~[2,4,-3,4]~ luống hoa trở thành: ~[-1, 4, 8, -6, 8]~ có vẻ đẹp là ~4+8-6+8 = 14~.

Example input 2

5 -3
-1 2 4 -3 4

Example output 2

19

Note 2

• Làm phép đoạn ~[-3]~ luống hoa trở thành: ~[-1, 2, 4, 9, 4]~ có vẻ đẹp là ~2+4+9+4 = 19~.

Example input 3

5 3
-1 -2 -3 -5 -2

Example output 3

0

Note 3

• Có làm phép thuật hay không thì vẻ đẹp vẫn là ~0~.