Bài tập Tin học: 2016-07-24

Thứ Bảy, 30 tháng 7, 2016

Akhil And Colored Balls

Akhil có rất nhiều quả bóng trắng và đen. Một ngày, anh chơi với chúng. Trong khi chơi, anh ta xếp các quả bảnh thành hai hàng, mỗi hàng chứa N quả banh. Hai hàng banh này được cung cấp cho bạn dưới dạng 2 chuỗi X, Y. Cả 2 chuỗi này chỉ chứa 'W' và 'B' trong đó 'B' ký hiệu cho qua banh màu trắng và 'B' ký hiệu cho quả banh màu đen.

Ngoài hai hàng banh này, Akhil có số lượng vô hạn các quả banh của mỗi màu. Anh ta muốn tạo ra một dòng nữa gồm N quả banh, ký hiệu bằng Z, sao cho tổng khoảng cách hamming giữa X và Z và khoảng cách hamming giữa Y và Z là tối đa.

Khoảng cách hamming giữa hai chuỗi X và Y được đỉnh nghĩa là số lượng vị trí mà màu của trái banh trong X khác với hàng Y ở tại vị trí đó. Ví dụ, khoảng cách hamming giữa “WBB” và “BWB” là 2, vì ở ví trí 1 và 2, màu tương ứng trong hai chuỗi khác nhau.

Vì có thể có nhiều cách tạo hàng Z, Akhil muốn bạn tìm chuỗi có thứ tự từ điển nhỏ nhất mà có giá trị như nói ở trên là lớn nhất.

Dữ liệu vào

· Dòng đầu tiên của tập tin dữ liệu vào chứa một số nguyen T là số lượng bô test. Mô tả của T bộ test như sau:

· Dòng đầu tiên của mỗi bộ test sẽ chứa một chuỗi X là cách sắp xếp các quả banh trong hàng đầu tiên.

· Dòng thứ hai chứa một chuỗi Y là cách sắp xếp các quả banh trong hàng thứ hai.

Dữ liệu ra

· Với mỗi bộ test, xuất ra một dòng duy nhất chứa chuỗi có độ dài là N là cách sắp xếp các quả banh trong hàng Z.

Ràng buộc

• 1 ≤ T ≤ 3

Giới hạn

· Subtask #1 (10 điểm) : 1 ≤ N ≤ 16

· Subtask #2 (20 điểm) : 1 ≤ N ≤ 10³

· Subtask #3 (70 điểm) : 1 ≤ N ≤ 10⁵

Ví dụ

Input:

WBWB

WBBB

Output:

BWBW

Giải thích

Ví dụ 1. Như đã biết, khoảng các Hamming(WBWB, BWBW) và khoảng cách Hamming(WBBB, BWBW) = 4 + 3 = 7.

Bạn có thể thử những ía trị khác cho chuỗi Z, giá trị sẽ không bao giờ vượt quá 6

Drumpf for President!

Nguồn: https://www.codechef.com

Donald Drumpf đã dành toàn bộ thời gian mùa hè để vận động tranh cử cho cuộc tuyển chọn hội đồng sinh viên. Ở trường đại học của anh ta, có tất cả N sinh viên. Mỗi sinh viên trong trường bỏ một phiếu. Số lượng sinh viên trong hội đồng được xác định bằng số lượng sinh viên nhận được ít nhất K phiếu bầu.

Mỗi người nhận được ít nhất K phiếu sẽ có một ghế trong hội đồng sinh viên. Trưởng khoa để ý thấy mỗi năm, có một số sinh viên tự bỏ phiếu cho mình. Ông đã quyết định thêm luật để loại bỏ những cá nhân tự bỏ phiếu cho chính mình tức là họ sẽ không được vào hội đồng sinh viên.

Bạn được cho một mảng A, với A_i thể hiện người mà sinh viên thứ i bỏ phiếu cho. Bạn có thể tính được hội đồng sinh viên có bao nhiêu người không?

Dữ liệu vào:

· Dòng đầu tiên chứa một số nguyên T – số lượng test.

· Với mỗi test, dòng đầu tiên chứa 2 số nguyên N, K.

· Dòng thứ hai của mỗi test chứa N số thể hiện mảng A, với số thứ i là A_i.

Dữ liệu ra:

· Với mỗi test, in ra một dòng duy nhất chứa một số nguyên tương ứng với số người trong hội đồng sinh viên.

Ràng buộc:

· 1 ≤ T ≤ 100

· 1 ≤ K ≤ N

Subtasks

Subtask #1: (30 điểm)

· 1 ≤ N ≤ 3

Subtask #2: (70 điểm)

· 1 ≤ N ≤ 100

Ví dụ:

Input

3 2

2 1 2

2 1

1 2

Output

Giải thích:

Trong test đầu tiên, có 3 học sinh. Một học sinh nhật được ít nhất 2 phiếu bầu sẽ được tham gia vào hội đồng sinh viên. Sinh viên 1 bỏ phiếu cho sinh viên 2, sinh viên 2 bỏ phiếu cho sinh viên 1, sinh viên 3 bỏ phiếu cho sinh viên 2. Do đó, sinh viên 2 nhận được 2 phiếu bầu và là người duy nhất đủ điều kiện vào hội đồng sinh viên.

Trong test thứ hai, mặc dù cả hai học sinh đều nhận được đủ số phiếu yêu cầu, tuy nhiên họ bị loại vì tự bỏ phiếu cho mình. Vì vậy, số người trong hội đồng sinh viên là 0

Laddu

Nguồn: https://www.codechef.com/

Bạn hẳn đã nghe về hệ thống phân phối kẹo mới của chúng tôi, với tên gọi “hệ thống cộng dồn kẹo”. Vấn đề này sẽ giúp bạn có một cái nhìn thoáng qua về nó. Bạn có thể đọc về nó ở trang một trước khi giải quyết bài tập này nếu bạn muốn, tất nhiên ở đây chúng tôi vẫn sẽ cung cấp đủ các thông tin về nó.

Hệ thống cộng dồn kẹo là một chương trình mới của chúng tôi. Trong chương trình này, chúng tôi sẽ phân phối kẹo cho các vị trí trong các cuộc thi mà bạn đạt được (được mô tả ở dưới), mà bạn thực hiện trên hệ thống của chúng tôi.

Bây giờ chúng tôi cho bạn biết về các hoạt động khác nhau và số lượng kẹo bạn sẽ nhận khi tham gia chúng:

· Chiến thắng cuộc thi (CodeChef’s Long, Cook-Off, LTIME, hay bất cứ cuộc thi nào của chúng tôi): 300+ phần thưởng (phần thường=20-vị trí của bạn trên bảng xếp hạng). Nếu vị trí của bạn lớn hơn 20, bạn sẽ không được nhận phần thường

· Top đóng góp: 300

· Người tìm lỗi trong code: 50->1000, tùy thuộc vào mức độ nghiêm trọng của lỗi.

· Người tạo cuộc thi: 50

Bạn dùng kẹo này để đổi lấy quà, mỗi tháng một lần. Số kẹo để đổi lấy quà trên thực tế là 200 cho người Ấn Độ và 400 cho người nước khác.

Bạn đang đưa ra lịch sử các hoạt động của người dùng. Biết ban đầu người dùng không có bất cứ viên kẹo nào. Tính số quà lớn nhất và người dùng có thể đổi được.

Input

· Số nguyên T, số test đề bài

· T bộ test tiếp theo có dạng:

· Dòng đầu tiên là activities, origin, với activities là số lượng hoạt động của người dùng, origin là người Ấn Độ hoặc không phải người Ấn Độ.

· activities dòng tiếp theo , mỗi dòng thuộc 1 trong 4 loại sau:

o Contest Win : Input sẽ có: CONTEST_WON rank, với rank là thứ hạng của người dùng

o Top Contributor : Input có: TOP_CONTRIBUTOR.

o Bug Finder : Input có: BUG_FOUND severity, với severity là mức độ nghiêm trọng của vấn đề

o Contest Hosting : Input có: CONTEST_HOSTED.

Output

Với mỗi bộ test, in ra trên mỗi dòng là số quà tối đa đổi được

Constraints

· 1 ≤ T, activities ≤ 100

· 1 ≤ rank ≤ 5000

· 50 ≤ severity ≤ 1000

Subtasks:

Chỉ có duy nhất một subtask với 100 điểm.

Example

Input:

4 INDIAN

CONTEST_WON 1

TOP_CONTRIBUTOR

BUG_FOUND 100

CONTEST_HOSTED

4 NON_INDIAN

CONTEST_WON 1

TOP_CONTRIBUTOR

BUG_FOUND 100

CONTEST_HOSTED

Output:

Giải thích:

Trong test đầu tiên

Đứng đầu cuộc thi , người dùng nhận 300 + 20 - 1 = 319 kẹo.

Top đóng góp, người dùng nhận 300 kẹo.

Tìm lỗi với mức độ nghiêm trọng là 100, người dùng nhận 100 kẹo.

Tổ chức cuộc thi, người dùng nhận 50 kẹo.

Tổng cộng người dùng thu được319 + 300 + 100 + 50 = 769 kẹo.

Và người dùng là người Ấn Độ, anh ta có thể đổi 200 kẹo để lấy quà mỗi tháng. Vì vậy, trong ba tháng đầu tiên anh ta đổi 3 món quà mất 200*3=600 kẹo, còn dư lại 169 kẹo, anh ta không thể đổi lấy được món quà thứ 4.

Vậy, kết quả là 3

Trong test thứ 2, người dùng không phải người Ấn Độ, anh ta có thể đổi 400 kẹo lấy quà mỗi tháng. Vì vậy, trong tháng đầu tiên, anh ta đổi mất 400 kẹo và còn dư 369 kẹo, và anh ta không thể đổi lấy món quà nào nữa.

Vì vậy, kết quả là 1.

Lumpy – The Bus Driver

Nguồn: https://www.codechef.com/

Lumpy là một tài xế xe buýt. Hôm nay, tên lơ xe nghỉ vì vậy Lumpy phải phụ trách luôn công việc của hắn ta. Trên xe buýt có N người. Đôi lúc sẽ có một số người không mang theo tiền thối và không thể trả vừa đúng giá trị của vé xe. Mỗi người trên xe buýt hôm nay vừa phải trả một số tiền lớn hơn giá trị thật sự của vé xe. Bạn được cho biết trước thông tin về số tiền trả thêm của mỗi người thông qua một mảng A có kích thước là N, trong đó A_i là số tiền (số lượng rupee, trong đó rupee là đơn vị tiền tệ của Ấn Độ) mà người thứ i phải trả thêm.

Sau khi kết thúc hành trình, Lumpy để ý rằng anh ta có P đồng mệnh giá một rupee và Q đồng mệnh giá hai rupee. Anh ta muốn thối lại những hành khách của anh ta bằng số tiền này. Vì là một người tốt bụng, Lumpy muốn thối lại đủ tiền cho càng nhiều người càng tốt. Lưu ý rằng Lumpy sẽ không thối lại tiền cho người thứ i nếu anh ta không thể trả đúng số tiền dư với những đồng xu anh ta có.

Lumpy đang bận lái xe buýt và cũng một phần không muốn tính số lượng người tối đa mà anh ta có thể làm hài lòng - Anh ta sẽ gây ra tai nạn nếu anh ta thử làm như vậy. Bạn có thể giúp anh ta với bài toán này?

Dữ liệu vào:

· Dòng đầu tiên của dữ liệu vào chứa số nguyên T là số lượng bộ test. Mô tả của T bộ test như sau.

· Với mỗi bộ test, dòng đầu tiên chứa ba số nguyên cách nhau bởi khoảng trắng N, P và Q.

· Dòng thứ hai chứa N số nguyên cách nhau bởi khoảng trắng, trong đó số nguyên thứ i mô tả A_i.

Dữ liệu ra:

· Với mỗi bộ test, xuất ra một dòng duy nhất chứa một số nguyên tương ứng với số lượng người tối đa mà Lumpy có thể thối lại.

Ràng buộc:

^·1 ≤ T ≤ 10⁶

^·1 ≤ N ≤ 10⁵

^·1 ≤ A_i ≤ 10⁹

^·0 ≤ P, Q ≤ 10¹⁴

^·Tổng các giá trị của N trong tất cả các bộ test không vượt quá 10⁶

Subtasks:

Subtask #1 (15 điểm)

· P = 0

Subtask #2 (15 điểm)

· Q = 0

Subtask #3 (70 điểm)

· Như ràng buộc gốc

Ví dụ:

Input

3 3 0

1 2 2

3 2 1

1 2 1

4 5 4

2 3 4 5

Output

Giải thích:

Trong test 1, Lumpy vừa có 3 đồng với mệnh giá một rupee.

Anh ta có thể trả những người có số hiệu {1, 2} hoặc những người có số hiệu {1, 3} với những đồng tiền này. Vì vậy, câu trả lời là 2.

Trong test 2, Lumpy có 2 đồng mệnh giá một rupee và 1 đồng mệnh giá hai rupee.

Trong phương án tối ưu, Lumpy có thể đưa đồng mệnh giá hai rupee cho người thứ 2 và những đồng mệnh giá một rupee cho người thứ 1 và 3. Vì vậy kết quả là 3.

Sticks

Nguồn: https://www.codechef.com

Chef và em trai đang chơi với những chiếc que. Họ có tất cả N chiếc que. Độ dài của chiếc que thứ i là Ai. Chef đố em trai chọn 4 chiếc que có thể tạo thành hình chữ nhật. Chef muốn em trai không bẻ gẫy bất kỳ chiếc que nào mà phải dùng toàn bộ chiều dài của que. Ngoài ra, Chef muốn diện tích hình chữ nhật lớn nhất có thể trong những hình em trai có thể tạo ra.

Em trai Chef chấp nhận thử thách và đã vượt qua nó. Bạn có thể làm được điều đó không? Bạn phải chỉ ra có thể tạo được một hình chữ nhật hay không? Nếu có, bạn phải chỉ ra diện tích lớn nhất của hình chữ nhật.

Dữ liệu vào:

· Dòng đầu tiên của input chứa một số tự nhiên T – số lượng test.

· Dòng đầu tiên của mỗi test chứa một số nguyên N – số lượng que.

· Dòng thứ hai của mỗi test chứa N số nguyên A1, A2, ..., AN là độ dài của những chiếc que.

Dữ liệu ra:

· Với mỗi test, in ra một dòng chứa một số nguyên là diện tích của hình chữ nhật lớn nhất hoặc in ra -1 nếu không thể tạo được hình chữ nhật nào từ những que đã cho.

Ràng buộc:

· 1 ≤ T ≤ 100

· 1 ≤ N ≤ 10³

· 1 ≤ Tổng của N trong một file input ≤ 10³

· 1 ≤ Ai ≤ 10³

Ví dụ:

Input

1 2 3 1 2

1 2 2 3

Output:

2 -1

Giải thích:

Ví dụ 1. Chef có thể chọn những que có độ dài 1, 2, 1, 2. Anh ta tạo được hình chữ nhật có diện tích 1 * 2 = 2.

Ví dụ 2. Không thể tạo ra được một hình chữ nhật từ 4 que đã cho.

One more weird game

Nguồn: https://www.codechef.com

Leha đang chơi một trò vô cùng thú vị. Trò chơi được chơi trên một lưới hình chữ nhật gồm N hàng và M cột. Ban đầu tất cả các ô trong lưới đều chưa được tô màu.

Số điểm ban đầu của Leha là 0. Với mỗi lượt chơi, anh ta chọn một ô chưa được tô màu, và tô màu nó. Điểm số của một bước là số ô láng giềng đã được tô màu của ô Leha tô trong bước đó. Hai ô gọi là láng giềng nếu có chung cạnh. Trò chơi sẽ kết thúc nếu tất cả các ô đều được tô màu. Kết thúc, điểm số chung cuộc là tổng số điểm mỗi lượt.

Leha muốn biết điểm số cao nhất anh ta có thể đạt được. Bạn có thể giúp anh ta tìm ra nó không?

Dữ liệu vào:

· Dòng đầu tiên của input chứa một số tự nhiên T – số lượng test.

· T dòng tiếp theo, mỗi dòng chứa hai số nguyên N và M là thích thước của lưới.

Dữ liệu ra:

· Với mỗi test, in ra một dòng chứa một số nguyên tương ứng với số điểm lớn nhất Leha có thể đạt được.

Ràng buộc:

· 1 ≤ T ≤ 100

· 1 ≤ N, M ≤ 1 000

Subtask:

· Subtask #1[30 điểm]: 1 ≤ N, M ≤ 3

· Subtask #2[70 điểm]: 1 ≤ N, M ≤ 1 000

Ví dụ:

Input

2 2

Output:

Giải thích:

Leha có thể đạt số điểm chung cuộc là 4 theo cách sau.

· Ban đầu, anh ta tô màu ô trái dưới, tất cả các ô láng giềng đều chưa được tô màu nên được cộng 0 điểm.

· Bước hai, anh ta tô màu ô phải trên và cũng được 0 điểm.

· Bước ba anh ta tô màu ô trái trên. Ô này có hai láng giềng và đều đã được tô màu nên sẽ được cộng 2 điểm.

· Bước cuối, anh ta chọn ô phải dưới. Ô này có hai láng giềng và đều đã được tô màu nên sẽ được cộng 2 điểm.

Leha không thể đạt số điểm nhiều hơn 4. Do đó 4 là đáp án.