2389 . TOAI

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

abcabcabc
快去寫 TIOJ 2311 > <

User's AC Ratio

33.3% (2/6)

Submission's AC Ratio

15.4% (2/13)

Tags

CKsim 2024-CKsim

Description

2100 年時，人類近乎被 AI 取代了，連資奧都只剩 AI 在打。2100 年的 TOI 選訓營有非常多 AI 機器人在比賽，因為機器人都長得一樣，所以每個機器人都有一個自己的身分證字號來做區別。因為是機器人，所以這些身分證字號都是長度不等的 01 字串（只由 0 和 1 組成的字串）。其中，總共有 $n$ 個身分證字號，因為給身分證字號的程式寫爛了，所以會有很多機器人有同樣的身分證字號：對於第 $i$ 個身分證字號來說，有 $c_i$ 個機器人的身分證字號是它（因為程式真的很爛，所以那 $n$ 個身分證字號自己也有可能重複）。

作為 TOI 的主辦人，你不想要認錯任何機器人。對於任何兩個機器人，你都不希望其中一個人的身分證字號剛好是另一個人身分證字號的前綴。具體來說，如果身分證字號較短的機器人為 $A$（ $A$ 的長度為 $len$ ），另一個機器人為 $B$，那你不希望 $B$ 的前 $len$ 個字元都跟 $A$ 一樣。

你想要在某些機器人的身分證字號後面加上一些字元，使得這件事情不發生。在一秒鐘中，你可以選一個機器人，並把他的身分證字號尾巴加上 0 或 1。請寫一個程式，算出你最少要花多少秒，才能達到你的目的。

Input Format

第一行有一個正整數 $n$ ，意義如題目所述
接下來 $n$ 行中，每行有一個字串 $s_i$ 跟一個正整數 $c_i$，代表第 $i$ 個身分證字號跟它的出現次數

對於所有測試資料：

  • $1 \leq n \leq 10 ^ 5$
  • $1 \leq c_i \leq 10 ^ 4$
  • 所有字串的長度總和不超過 $10 ^ 6$

Output Format

輸出一個整數，代表你最少要花的時間

Sample Input 1

3
1 1
11 1
111 1

Sample Output 1

2

Sample Input 2

3
1 1
1 1
11 1

Sample Output 2

4

Sample Input 3

5
0 1
01 1
0011 1
010 1
01 1

Sample Output 3

6

Sample Input 4

2
0 5
1 9

Sample Output 4

41

Sample Input 5

3
1 1
1 1
1 1

Sample Output 5

5

Hints

Problem Source

USACO

Subtasks

No. Testdata Range Constraints Score
1 0~3 範例測資 0
2 0, 4~6 $\forall 1 \leq i \leq n$，$s_i=0$ 或 $s_i=1$，$c_i=1$ 10
3 0~4, 7~14 $n \leq 100$，所有字串長度和不超過 $1000$，$c_i=1$ 20
4 0~4, 15~24 $c_i=1$ 30
5 0~49 無特別限制 40

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 3000 1048576 65536 1 2 3 4 5
1 3000 1048576 65536 1 3 4 5
2 3000 1048576 65536 1 3 4 5
3 3000 1048576 65536 1 3 4 5
4 3000 1048576 65536 2 3 4 5
5 3000 1048576 65536 2 5
6 3000 1048576 65536 2 5
7 3000 1048576 65536 3 5
8 3000 1048576 65536 3 5
9 3000 1048576 65536 3 5
10 3000 1048576 65536 3 5
11 3000 1048576 65536 3 5
12 3000 1048576 65536 3 5
13 3000 1048576 65536 3 5
14 3000 1048576 65536 3 5
15 3000 1048576 65536 4 5
16 3000 1048576 65536 4 5
17 3000 1048576 65536 4 5
18 3000 1048576 65536 4 5
19 3000 1048576 65536 4 5
20 3000 1048576 65536 4 5
21 3000 1048576 65536 4 5
22 3000 1048576 65536 4 5
23 3000 1048576 65536 4 5
24 3000 1048576 65536 4 5
25 3000 1048576 65536 5
26 3000 1048576 65536 5
27 3000 1048576 65536 5
28 3000 1048576 65536 5
29 3000 1048576 65536 5
30 3000 1048576 65536 5
31 3000 1048576 65536 5
32 3000 1048576 65536 5
33 3000 1048576 65536 5
34 3000 1048576 65536 5
35 3000 1048576 65536 5
36 3000 1048576 65536 5
37 3000 1048576 65536 5
38 3000 1048576 65536 5
39 3000 1048576 65536 5
40 3000 1048576 65536 5
41 3000 1048576 65536 5
42 3000 1048576 65536 5
43 3000 1048576 65536 5
44 3000 1048576 65536 5
45 3000 1048576 65536 5
46 3000 1048576 65536 5
47 3000 1048576 65536 5
48 3000 1048576 65536 5
49 3000 1048576 65536 5
Submit
Back to Top