MCC 2025 P2: Fans

Fans

Statement

You have $N$ groups of sticks, where the $i$-th group consists of $c_i$ sticks of colour $i$.

You want to use the sticks to make the biggest fan possible by arranging some sticks side by side (in a fan shape). However, you do not want two adjacent sticks to have the same colour.

What is the length of the longest sequence of sticks you can make?

Input Format

There are multiple test cases. The first line contains the number of test cases $T$. Each of the next two lines describes a test case. The description of a test case follows.

Output Format

Output $T$ lines. For each test case, output a single integer, the length of the longest sequence of sticks.

Constraints

For all tasks:

• $1 \le T \le 10$.
• $1 \le N \le 10^5$.

• $1 \le c_i \le 10^9$ ($1 \le i \le N$)

• Task 1 (6 points): $N \le 10$
• Task 2 (6 points): $N \le 10$
• Task 3 (7 points): $N \le 10$
• Task 4 (20 points): $N \le 100$
• Task 5 (60 points): $N \le 10^5$

Sample Input

2
3
3 7 2
1
4

Sample Output

11
1

Sample Explanation

Test case 1

There are 3 sticks of colour 1, 7 sticks of colour 2, and 2 sticks of colour 3.

One possible valid sequence of stick colours is $[2, 1, 2, 3, 2, 1, 2, 3, 2, 1, 2]$, which uses 11 sticks and leaves one stick of colour 2 unused as shown in Figure 1. The unused stick of colour 2 cannot be added into the sequences because adding it into any position would violate the constraint that no two adjacent sticks have the same colour. Figure 2 depicts an example of an invalid sequence.

Figure 1: An example of sample input where 11 sticks across 3 groups are arranged into a **valid** sequence.


Figure 2: An example of sample input where 12 sticks across 3 groups are arranged into an **invalid** sequence.

Test case 2

There are 4 sticks of colour 1. The only possible (non-empty) sequence of stick colours is $[1]$, which uses 1 stick.

Kipas

Pernyataan

Anda mempunyai $N$ kumpulan batang, di mana kumpulan ke-$i$ mengandungi $c_i$ batang berwarna $i$.

Anda ingin menggunakan batang-batang tersebut untuk membina kipas yang paling besar dengan menyusun beberapa batang secara bersebelahan (dalam bentuk kipas). Namun, anda tidak mahu dua batang bersebelahan mempunyai warna yang sama.

Apakah panjang urutan batang yang paling panjang yang boleh anda bina?

Format Input

Terdapat beberapa kes ujian (test case). Baris pertama mengandungi bilangan kes ujian, $T$. Setiap dua baris berikutnya menerangkan satu kes ujian.

Format Output

Keluarkan $T$ baris. Bagi setiap kes ujian, keluarkan satu integer yang mewakili panjang maksimum urutan batang yang boleh dibina.

Kekangan

Untuk semua tugasan:

• $1 \le T \le 10$.
• $1 \le N \le 10^5$.

• $1 \le c_i \le 10^9$ ($1 \le i \le N$)

• Tugasan 1 (6 markah): $N \le 10$
• Tugasan 2 (6 markah): $N \le 10$
• Tugasan 3 (7 markah): $N \le 10$
• Tugasan 4 (20 markah): $N \le 100$
• Tugasan 5 (60 markah): $N \le 10^5$

Contoh Input

2
3
3 7 2
1
4

Contoh Output

11
1

Penjelasan Contoh

Kes ujian 1

Terdapat 3 batang warna 1, 7 batang warna 2, dan 2 batang warna 3.

Salah satu urutan batang yang sah ialah $[2, 1, 2, 3, 2, 1, 2, 3, 2, 1, 2]$, yang menggunakan 11 batang dan meninggalkan satu batang warna 2 yang tidak digunakan (lihat Rajah 1). Batang warna 2 yang tidak digunakan itu tidak boleh dimasukkan ke mana-mana kedudukan tanpa melanggar syarat bahawa tiada dua batang bersebelahan yang mempunyai warna sama.

Rajah 1: Satu contoh input yang 12 batang melalui 3 kumpulan disusun menjadi urutan yang **sah**.


Figure 2: Satu contoh input yang 12 batang melalui 3 kumpulan disusun menjadi urutan yang **tidak sah**.

Kes ujian 2

Terdapat 4 batang warna 1. Satu-satunya urutan batang yang mungkin (dan tidak kosong) ialah $[1]$, yang menggunakan satu batang sahaja.

扇子

题目描述

你有 $N$ 组棍子， 第 $i$ 组有 $c_i$ 个颜色为 $i$ 的棍子。

你要用这些棍子并排摆放成最大的扇子。可是你不希望有两个相邻的棍子是同个颜色的。

你最多可以拼出多长的一段木棍序列？

输入格式

输入包含多个测试数据。第一行包含一个整数 $T$，表示测试数据的组数。接下来每两行描述一个数据，描述如下。

输出格式

输出 $T$ 行。对于每个数据，输出一个整数，表示最长木棍序列的长度。

约束

对于每项任务：

• $1 \le T \le 10$.
• $1 \le N \le 10^5$.

• $1 \le c_i \le 10^9$ ($1 \le i \le N$)

• 任务 1 (6 分): $N \le 10$
• 任务 2 (6 分): $N \le 10$
• 任务 3 (7 分): $N \le 10$
• 任务 4 (20 分): $N \le 100$
• 任务 5 (60 分): $N \le 10^5$

样例输入

2
3
3 7 2
1
4

样例输出

11
1

样例解释

数据一

给定3个颜色为1的棍子，7个颜色为2的棍子和2个颜色为3的棍子。

其中一个有效的颜色序列是 $[2, 1, 2, 3, 2, 1, 2, 3, 2, 1, 2]$。这个序列只使用了11个棍子（剩下1个棍子没有使用）如图一所示。仅剩下颜色为2的棍子无法插入序列中的任意位置因为插入任意位置讲导致其中两个相邻的棍子是相同颜色的。图二描绘了一个无效序列的例子。

图一：由11枝棍子组成**有效**序列的样例。


图二：由12枝棍子组成**无效**序列的样例。

数据二

有4个颜色为1的棍子，所以仅有一个非空的有效序列 - $[1]$ （只使用一个棍子）