Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

MAUGIAO - The problem for kid

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/maugiao


Chuyện kê rằng ngày xưa, bác HCĐào mới tốt nghiệp đại học, được chính phủ nước Trái Na cho sang Việt Nam để xin được kết giao, lưu thông buôn bán. Tuy nhiên, vừa sang được biên giới, thì giỏ lương thực của bác đã bị lũ khi núi chôm mất. Thật may cho bác là cách đó không xa là bản làng của người Tày, và họ đã tiếp đón nhiệt tình. Trong buổi tiệc tiếp đón ở vùng núi, bác lỡ ba hoa về tấm bằng đại học mới nhận được.  Cũng muốn khoe mẽ nên bác ấy đề ra một bài toán cho các bô lão, và dùng tấm bằng để đánh cược. Các bô lão bật cười, và gọi một đứa bé 5 tuổi đang chơi ngoài sân vào chơi thử. Thế rồi đứa bé đó trả lời rằng: “Những bài toán này thì con mới thua đố cược em gái con ngày hôm qua xong. Chẳng đáng để con phải làm.”

Bác Đào  thấy thế mới cầu xin được gặp con bé để nghe lời giải, để mang về lãnh thưởng viện Hàn lâm khoa học Trái Na.

Cô bé 4 tuổi vừa ở lớp mẫu giáo về, được mời vào gặp bác Đào, bác ấy vô cùng sửng sốt trước câu trả lời này.  Câu chuyện này đến tai một nhà báo nghiệp dư trong vùng. Và được đăng lên số báo ngày hôm đó. Bài toán đó như sau:

Bác Đào có n người con gái nuôi, và muốn gã cho n vị tiến sỹ trẻ năm ấy. Thế nhưng không biết nên sắp xếp hôn nhân thế nào cho lợi. Một nhà hiền triết được mời đến để tham khảo ý kiến. Nhà hiền triết sau khi xem xét đã báo cáo kết quả thành 1 bảng n*n và nói rằng “nếu cô con gái thứ i kết hôn cùng tiến sỹ j thì sẽ làm ra được lượng tài sản bằng với số ở hàng i cột j từ nay đến hết đời.” Nhưng khổ nổi ông hiền triết cũng không biết sắp xếp hôn nhân sao cho bác Đào có được ngôi mộ hoành tráng nhất sau khi bác chết.

 

Về sau, bài toán trở thành câu đố dân gian của người Tày và mỗi em bé mẫu giáo nơi đây đều giải được..

 

Để thư giãn xã hơi sau kì thi VM vừa qua,  anh quandum ngõ ý set bài này lên để mọi người thư giãn, đồng thời thêm 1 yêu cầu là có bao nhiêu cách để cho ra cùng 1 kết quả tốt nhất.

Input

Dòng đầu gồm số nguyên dương n (1 <= n <= 20).

n dòng sau mỗi dòng chứa n số nguyên A[i,j] với A[i,j] là số tiền có được khi con gái thứ i kết hôn với tiến sỹ j (0

Output

Tổng tài sản lớn nhất nhận được và số cách để có được tổng tài sản như thế.

Example

Input:

4

1 2 3 4

5 6 7 8

9 10 11 12

13 14 15 16

Output:

34 24

 

Note:  n<=16: time 1s, các trường hợp còn lại: time 2s.


Được gửi lên bởi:Duy Khanh Nguyen
Ngày:2012-07-21
Thời gian chạy:1s-2s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ASM64 GOSU PERL6 PYPY RUST SED
Nguồn bài:Trần Mạnh Chánh Quân

hide comments
2021-08-05 03:02:36
toi la NGUYEN XUAN HIEU den tu HAI PHONG.
XIN CHAO CAC FAN HAM MO NHE.
2019-09-23 15:45:29
trò trẻ :v
duonght_pro_xinhgainhathemattroi_:)
2018-07-14 18:11:31
Bài này sử dụng qhd trạng thái nha
Dành cho ai muốn tham khảo
http://bit.ly/2Rns9oq

Last edit: 2019-01-12 01:42:26
2018-06-13 13:00:03
wtf sao số cách lấy lại là 24, chỉ có 24 trường hợp có thể xảy ra thôi mà??
2017-12-30 18:48:42
quay lui thôi mà 0đ là sao
2017-10-09 14:52:04
Đề bài lầy vc @@
2017-08-08 17:16:42
ko hiểu sao in ra số cách là 1 mà vẫn AC?
2017-06-20 16:34:37
Lam dung yeu cau test van 0 la sao ta
2017-05-06 15:56:33
tính số cách như nào vậy

Last edit: 2017-05-06 16:02:55
2016-12-08 04:42:13 le tuan dung
Tôi là Lê Tuấn Dũng. Xin chào các fan hâm mộ.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.