Orange Contest #02

BabyOrange và CandySnowy đang cùng nhau thực hiện một dự án bao gồm \(n\) dòng code.
BabyOrange bắt đầu làm việc ngay lập tức và viết với tốc độ \(x\) dòng mỗi giờ cho đến tận cuối cùng.
CandySnowy có hai lựa chọn

• Không sử dụng AI và viết ngay từ đầu với tốc độ \(y\) dòng mỗi giờ
• Dành \(z\) giờ để thiết lập trợ lí AI, không viết gì trong thời gian đó, và sau đó viết với tốc độ \(10 \times y\) dòng mỗi giờ.

CandySnowy đưa ra lựa chọn này trước khi bắt đầu công việc và không thay đổi nó sau đó.
Trong khi CandySnowy thiết lập AI, anh ấy không viết bất kỳ dòng code nào, nhưng BabyOrange vẫn tiếp tục làm việc với tốc độ \(x\) dòng code mỗi giờ.
Dự án được coi là hoàn thành ngay khi BabyOrange và CandySnowy cùng nhau viết được ít nhất \(n\) dòng code. Nếu dự án có thể hoàn thành trước khi quá trình thiết lập AI kết thúc, thì công việc kết thúc vào thời điểm đó.
Thời gian được tính bằng giờ trọn vẹn: nếu một dự án hoàn thành vào giữa một giờ, giờ đó được tính là một giờ trọn vẹn.
Xác định số giờ trọn vẹn tối thiểu để dự án được hoàn thành.

Input

• Dòng đầu tiên chứa số truy vấn \(t\) \((1 \le t \le 5000)\)
• \(t\) dòng tiếp theo, mỗi dòng chứa 4 số \(n, x, y, z\) \((1 \le n,x,y,z \le 10000)\)

Output

• Với mỗi truy vấn in ra một số thể hiện số giờ trọn vẹn tối thiểu đề hoàn thành dự án nếu CandySnowy làm việc một cách tối ưu

Example

10
1 1 1 1
2 1 1 5
3 1 1 1
110 10 9 1
54 14 1 1
30 8 1 13
6 2 1 3
82 4 5 7
200 3 2 4
76 211 743 432

1
1
2
2
3
4
2
8
13
1

Sau khi thành công thiết lập AI, BabyOrange và CandySnowy chưa kịp ăn mừng thì tự nhiên một tiếng réo vang lên. Họ nhận ra bụng họ đã đói vì vậy họ quyết định đến siêu thị để mua đồ ăn.
Khi tới siêu thị, họ bị một đám người lạ bắt cóc. Khi CandySnowy hỏi lý do bắt cóc họ, đám người lạ nói: "Thứ bọn ta muốn chính là hệ thống AI đó, nếu các ngươi không giao nộp cho bọn ta, bọn ta sẽ cho ăn 100 quả chích điện, trừ khi các ngươi giải được câu đố của bọn ta.
Vì không muốn bị ăn 100 quả chích điện 100 vôn, nên BabyOrange và CandySnowy quyết định giải câu đố. Câu đố của bọn họ như sau:
Trong siêu thị, các mặt hàng cùng loại thường đặt cạnh nhau để kệ trông gọn gàng và khách hàng dễ dàng tìm thấy những gì mình cần.
Chiếc kệ được mô tả bởi một mảng \(a\) gồm \(n\) phần tử, trong đó \({a_i}\) là loại hàng hóa tại vị trí \(i\)
Chúng ta nói chiếc kệ được xếp đúng nếu với mỗi hai vị trí \(i\) và \(j\) sao cho \(1 \le i \le j \le n\) và \({a_i} = {a_j}\) thì thỏa mãn điều kiện sau: Với mỗi \(k\) từ \(i\) tới \(j\), \({a_k}\) phải luôn bằng \({a_j}\). Nói cách khác, các hàng hóa cùng loại phải ở liền kề nhau. Ví dụ, giả sử có 2 loại hàng hóa là 1 và 2, thì dãy 1 1 2 2 là xếp đúng, còn 1 2 1 2 là xếp sai.
Bạn được chọn 2 vị trí khác nhau và thay đổi vị trí những hàng hóa này, nhưng bạn chỉ được thay đổi đúng 1 lần. Bạn cũng có thể không thay đổi vị trí hàng hóa nào cả.
Hãy cho biết có thể xếp kệ sao cho đúng được không.
Nghe xong câu đố, BabyOrange và CandySnowy hoàn toàn có thể giải được. Nhưng vì chưa có gì bỏ bụng nên họ đành nhờ các bạn giải dùm.

Input

• Dòng đầu tiên ghi số truy vấn \(t\) \((1 \le t \le 10^4)\)
• Mỗi truy vấn sẽ gồm 2 dòng:
• Dòng đầu tiên chứa số nguyên \(n\) \((2 \le n \le 2 \times 10^5)\) - số lượng hàng hóa trên kệ
• Dòng thứ hai chứa \(n\) số \({a_i}\) \((1 \le {a_i} \le 10^9)\), \({a_i}\) chỉ loại hàng hóa tại vị trí \(i\)

Output

• Với mỗi truy vấn, in ra NO nếu không thể xếp được và YES nếu có thể xếp được kệ đúng chỉ trong một lần thay đổi hàng hóa.

Example

2
3
1 2 1
6
1 2 3 1 2 3

YES
NO

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

YES
YES
NO
YES
NO

Sau khi thành công chống lại mã độc, CandySnowy liền nói: "Hay là mình đi chơi chút cho xả stress đi".
Vì vừa mới căng thẳng viết code, BabyOrange liền đồng ý. Trong chuyến đi, họ định đi tới công viên để chơi, ai dè họ lại bị đi lạc tới một "mê cung" kỳ quái, nói đúng hơn là một mạng lưới các trạm dịch chuyển.
Hệ thống dịch chuyển này gồm \(n\) trạm, giữa bất kỳ hai trạm phân biệt \(u\) và \(v\) nào cũng có một đường dẫn dịch chuyển. Tuy nhiên, việc di chuyển sẽ tiêu tốn một mức năng lượng được tính bằng công thức: \(w(u,v) = \frac{max(u,v)}{gcd(u,v)}\).
Trong đó, \(gcd(x,y)\) là ước chung lớn nhất của \(x\) và \(y\)
Hiện tại, hai người đang đứng ở trạm \(a\) và cửa thoát hiểm nằm ở trạm \(b\). Họ rất muốn ra nhưng vì đã dùng hết IQ để viết code nâng cấp nên giờ này không còn sức để giải nữa.
Hãy giúp BabyOrange và CandySnowy tìm đường từ \(a\) tới \(b\) mà tốn ít năng lượng nhất

Input

• Một dòng duy nhất chứa ba số \(n,a,b\) \((2 \le n \le 10^9, 1 \le a,b \le n, a \neq b)\)

Output

• Một số nguyên duy nhất biểu thị số năng lượng ít nhất để tới trạm \(b\)

Example

10 9 8

7

100 16 27

10

100 55 11

5

Sau khi thoát khỏi "mê cung", họ cuối cùng cũng tới được công viên, tại công viên họ thấy PhuocThien, bạn của BabyOrange và CandySnowy. PhuocThien rủ hai bạn tham gia bữa tiệc của anh ấy vào ngày mai, và họ đồng ý.
Khi tới nơi tổ chức bữa tiệc, họ thấy bạn bè của PhuocThien đang xếp hàng để vào bữa tiệc.
Bữa tiệc của PhuocThien có \(x\) bàn tại bữa tiệc, mỗi bàn có \(s\) chỗ ngồi, mỗi chỗ chỉ chứa được một người
Mỗi người bạn của PhuocThien có một trong ba tính cách sau:

• Hướng nội (I): Người có tính cách này chỉ ngồi ở bàn trống
• Hướng ngoại (E): Bắt buộc phải ngồi ở bàn không trống (Bàn đã có người ngồi)
• Hướng trung (A): Có thể ngồi ở bất kỳ bàn nào

Ban đầu tất cả các chỗ đều đang trống. Tuy nhiên, vì các bạn đã xếp thành hàng, PhuocThien không thể thay đổi vị trí của các bạn trong hàng. Với mỗi người trong hàng, PhuocThien phải chỉ định cho họ một bàn hoặc... đuổi họ ra khỏi bưa tiệc. Mỗi người được xếp chỗ trước khi người tiếp theo được chỉ định vị trí chỗ ngồi.
Vì PhuocThien đang rất bận cho việc chuẩn bị bữa tiệc, anh ấy liền nhờ BabyOrange và CandySnowy giúp anh trong việc sắp xếp chổ ngồi sao cho càng nhiều người có chổ ngồi càng tốt. Háy giúp BabyOrange và CandySnowy tìm ra số lượng bạn bè tối đa mà cô ấy có thể mời đến bữa tiệc
Lưu ý: khi bạn bè đã ngồi vào chỗ, họ không được phép di chuyển ngay cả khi vị trí đó không còn phủ hợp với tính cách của họ nữa.

Input

• Dòng đầu tiên chứa số lượng truy vấn \(t\) \((1 \le t \le 500)\)
• Mỗi truy vấn chứa hai dòng:
• Dòng đầu tiên chứa 3 số \(n, x, s\) \((1 \le n,x,s \le 3000)\)
• Dòng thứ hai chứa một dãy \(u\) có độ dài \(n\) gồm các ký tự A,E,I

Output

• Với mỗi truy vấn, in ra số lượng người tối đa có chỗ ngồi

Example

1
5 2 2
EIAIE

4

5
20 5 5
AEIEEEEIEAAEIEEEEIEA
8 2 4
AAAAAIEE
8 4 2
AIEAEAAI
8 3 3
AIEAEAAI
4 2 2
IAEE

20
7
7
7
4

Sau khi xếp chỗ cho mọi người xong, PhuocThien lại nhờ BabyOrange và CandySnowy chút chuyện.
Chuyện là PhuocThien đang làm một chiếc bánh cho bữa tiệc. Tuy nhiên, vì làm quá vội vàng, nên lớp kem trên chiếc bánh không đều nhau. Đều giải quyết vấn đề này, anh ấy quyết định sử dụng một con dao và đặt nó ở một chiều cao nhất định và quét lớp kem từ trái sang phải.
Gọi \({a_i}\) là chiều cao lớp kem ở vị trí \(i\). Giả sử PhuocThien đặt con dao ở chiều cao \(h\). Nếu chiều cao lớp kem ở vị trí \(i\) cao hơn \(h\), toàn bộ lớp kem thừa sẽ bị đẩy xuống vị trí \(i + 1\). Toàn bộ lớp kem thừa tại vị trí \(n\) dẽ bị đẩy hoàn toàn ra khỏi chiếc bánh.
Vì PhuocThien biết các bạn mình rất thích lớp kem trên bánh, nên anh ấy muốn lớp kem trên bánh cao nhất có thể. CandySnowy còn góp ý thêm là nên phục vụ một phần chiếc bánh thay vì cả cái bánh. PhuocThien đồng ý với ý kiến này. Hãy giúp ba bạn tìm chiều cao cao nhất của lớp kem sao cho lớp kem ở \(i\) vị trí đầu tiên đều nhau \((1 \le i \le n)\)

Input

• Dòng đầu tiên in ra số truy vấn \(t\) \((1 \le t \le 10^4)\)
• Mỗi truy vấn có hai dòng:
• Dòng đầu tiên chứa số nguyên \(n\) \(( 2 \le n \le 2 \times 10^5)\)
• Dòng thứ hai chứa \(n\) số nguyên \({a_1}, {a_2}, ..., {a_n}\) \((1 \le {a_i} \le 10^9)\)

Output

• Với mỗi truy vấn in ra \(n\) số nguyên, số thứ \(i\) biểu thị chiều cao cao nhất có thể của lớp kem sao cho lớp kem ở \(i\) vị trí đầu tiên đều nhau.

Example

1
3
4 2 3

4 3 3

4
5
2 3 4 3 2
5
3 3 3 1 1
3
913764826 346182673 764382516
8
6 7 6 7 6 7 6 7

2 2 2 2 2
3 3 3 2 2
913764826 629973749 629973749
6 6 6 6 6 6 6 6