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.|

PTITSU1F - Bài F - PTIT Summer 1

Công ty đồ chơi X nhập khẩu  con búp bê gỗ. Các con búp bê được đánh số từ 1 tới  trong đó con búp bê thứ  là một hộp rỗng có kích thước là một số nguyên . Người ta có thể lồng con búp bê thứ  vào trong con búp bê thứ  nếu con búp bê thứ  đang rỗng và , với  là một số nguyên dương cho trước. Bằng cách lồng các con búp bê vào nhau theo cách như vậy, công ty X chỉ cần tìm chỗ đặt những con búp bê ngoài cùng (những con búp bê không nằm trong bất kỳ con búp bê nào khác) vào kho.

Yêu cầu: Hãy giúp công ty X lồng các con búp bê vào nhau sao cho tổng kích thước các con búp bê ngoài cùng  là nhỏ nhất.

Input

Dòng đầu tiên chứa số bộ test T. Sau đó là T bộ test, mỗi bộ test có dạng:

-          Dòng 1 của chứa hai số nguyên dương  cách nhau ít nhất một dấu cách.

-          Dòng 2 của nhóm chứa  số nguyên dương  ( ) cách nhau ít nhất một dấu cách.

Output

Mỗi bộ test in trên một dòng một số nguyên duy nhất là tổng kích thước các con búp bê ngoài cùng theo phương án tìm được.

Example

Input:

1

8 2

8 4 2 1 1 3 5 9 Output: 18

Được gửi lên bởi:adm
Ngày:2012-07-06
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA

hide comments
2019-04-24 16:34:58
Black Hole cam on ban
2015-08-22 13:59:59 Cường
ủa bài này ko có giới hạn à :?
2014-05-31 12:39:57 Black Hole
Bài F - PTIT Summer 1
Mã bài: PTITSU1F
Công ty đồ chơi X nhập khẩu n con búp bê gỗ. Các con búp bê được đánh số từ 1 tới n trong đó con búp bê thứ i là một hộp rỗng có kích thước là một số nguyên a[i]. Người ta có thể lồng con búp bê thứ i vào trong con búp bê thứ j nếu con búp bê thứ j đang rỗng và m+a[i]<=a[j], với m là một số nguyên dương cho trước. Bằng cách lồng các con búp bê vào nhau theo cách như vậy, công ty X chỉ cần tìm chỗ đặt những con búp bê ngoài cùng (những con búp bê không nằm trong bất kỳ con búp bê nào khác) vào kho.
Yêu cầu: Hãy giúp công ty X lồng các con búp bê vào nhau sao cho tổng kích thước các con búp bê ngoài cùng là nhỏ nhất.
Input
Dòng đầu tiên chứa số bộ test T. Sau đó là T bộ test, mỗi bộ test có dạng:
- Dòng 1 của chứa hai số nguyên dương n và m cách nhau ít nhất một dấu cách.
- Dòng 2 của nhóm chứa n số nguyên dương cách nhau ít nhất một dấu cách.
Output
Mỗi bộ test in trên một dòng một số nguyên duy nhất là tổng kích thước các con búp bê ngoài cùng theo phương án tìm được.
Example
Input:
1
8 2
8 4 2 1 1 3 5 9

Output:
18


Last edit: 2014-05-31 12:41:15
2014-05-27 07:13:42 Black Hole
cái đề bài @@
2014-04-05 15:19:30 Hat Dau Nho
bai nay that su kho hieu! luc AC luc TLE
2013-01-23 08:56:24 Nguyễn Thị Minh Trang
Có ai có thể sửa lại đề cho đủ ko?
2013-01-15 15:20:35 Trần Vãn Dương D10CN2
De hien tai Hieen thij chuaw dur neen cacs banj hoiw khos theo doix hi hi
2012-08-15 03:02:55 Trần Vãn Dương D10CN2



Last edit: 2012-08-30 08:06:48
2012-07-10 12:24:29 Hoang Xuan Binh D11CN6


Last edit: 2012-07-11 01:38:32
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.