USACO 2013 - Tháng 3 - Hạng Vàng

Oanh Trúc Béo muốn đi phát quà liên khối cho \(n\) học sinh khối chuyên Tin. Các học sinh này đều đứng trên trục số và được đánh số lần lượt từ \(1\) đến \(n\), học sinh thứ \(i\) đứng ở tọa độ \(p_i\). Oanh Trúc đứng ở gốc tọa độ (điểm \(0\)) và muốn tìm một trình tự phát quà để tổng độ bất mãn của \(n\) học sinh này là nhỏ nhất có thể, biết rằng Oanh Trúc cần đúng \(1\) phút để di chuyển được một đơn vị độ dài trên trục số, đồng thời, nếu học sinh nào chưa được nhận quà, thì cứ mỗi phút trôi qua, độ bất mãn của bạn ấy sẽ tăng lên \(1\) (độ bất mãn ban đầu của mỗi người đều bằng \(0\)).

Các bạn hãy lập trình tính toán giúp Oanh Trúc độ bất mãn nhỏ nhất có thể nhé!

Input

• Dòng đầu chứa số nguyên dương \(n\) \((n\leq 1000)\).
• Dòng tiếp theo chứa \(n\) số nguyên \(p_1\), \(p_2\),..., \(p_n\) \(\left(-5\cdot 10^5\leq p_i\leq 5\cdot 10^5\right)\).

Output

• Tổng độ bất mãn nhỏ nhất có thể.

Example

4
-2 -12 3 7

50

Có \(N\) ngọn đồi (\(1 \le N \le 100\,000\)). Mỗi ngọn đồi có dạng một đoạn thẳng từ \((x1, y1)\) đến \((x2, y2)\), trong đó \(x1 < x2\) và \(y1 < y2\). Không có hai đoạn thẳng nào giao nhau hoặc chạm nhau, kể cả tại các đầu mút; ngoài ra, ngọn đồi đầu tiên thỏa mãn \((x1, y1) = (0,0)\).

Bò Bessie bắt đầu tại \((0,0)\) trên ngọn đồi đầu tiên. Mỗi khi ở trên một ngọn đồi, Bessie leo lên cho tới khi đến đầu cuối của nó. Sau đó cô nhảy khỏi mép đồi. Nếu đáp xuống một ngọn đồi khác, cô tiếp tục đi trên ngọn đồi đó; nếu không, cô rơi xuống rất xa cho tới khi đáp an toàn trên một tấm đệm gối tại \(y = -\infty\). Mỗi ngọn đồi \((x1, y1) \to (x2, y2)\) phải được coi là chứa điểm \((x1, y1)\) nhưng không chứa điểm \((x2, y2)\). Do đó, Bessie sẽ đáp xuống ngọn đồi nếu cô rơi từ phía trên nó tại vị trí có \(x = x1\), nhưng sẽ không đáp xuống ngọn đồi nếu cô rơi từ phía trên nó tại \(x = x2\).

Hãy đếm tổng số ngọn đồi mà Bessie chạm vào tại một thời điểm nào đó trong hành trình.

Dữ liệu vào

Dòng đầu tiên chứa số ngọn đồi \(N\).

Dòng thứ \(i+1\) trong \(N\) dòng tiếp theo chứa bốn số nguyên \((x1,y1,x2,y2)\) mô tả ngọn đồi thứ \(i\). Mỗi số nguyên nằm trong khoảng từ 0 đến \(1\,000\,000\,000\).

Dữ liệu ra

In ra số ngọn đồi Bessie chạm vào trong hành trình.

Ví dụ

4
0 0 5 6
1 0 2 1
7 2 8 5
3 0 7 7

3

Nguồn

USACO 2013 March Contest, Gold — Problem 2: Hill Walk

Tác giả đề: Travis Hance, 2013.

Bessie đã xếp một chuỗi gồm \(N\) viên đá, mỗi viên mang một chữ cái duy nhất trong bảng chữ cái, và muốn kết chúng thành một chiếc vòng cổ thời trang.

Vì muốn bảo vệ đồ đạc của mình, Bessie không muốn chia sẻ chiếc vòng cổ với con bò khác đang sống cùng phía chuồng. Tên của con bò kia là một chuỗi gồm \(M\) ký tự, và Bessie muốn bảo đảm rằng chuỗi độ dài \(M\) này không xuất hiện dưới dạng một chuỗi con liên tiếp ở bất kỳ đâu trong chuỗi biểu diễn chiếc vòng cổ của cô (nếu không, con bò kia có thể nhầm tưởng chiếc vòng cổ dành cho mình). Bessie quyết định bỏ đi một số viên đá trên vòng cổ để tên của con bò kia không xuất hiện dưới dạng chuỗi con. Hãy giúp Bessie xác định số viên đá ít nhất mà cô phải bỏ đi.

Dữ liệu vào

• Dòng 1 chứa một chuỗi độ dài \(N\) mô tả chiếc vòng cổ ban đầu của Bessie; mỗi ký tự nằm trong khoảng từ a đến z.
• Dòng 2 chứa tên có độ dài \(M\) của con bò khác trong chuồng, cũng chỉ gồm các ký tự từ a đến z.

Phân nhóm

Trong ít nhất 20% số trường hợp kiểm thử, \(N \le 20\).

Trong ít nhất 60% số trường hợp kiểm thử, \(N \le 1000\) và \(M \le 100\).

Trong mọi trường hợp kiểm thử, \(N \le 10000\) và \(M \le 1000\).

Trong mọi trường hợp kiểm thử, \(M \le N\).

Dữ liệu ra

• Dòng 1 chứa số viên đá ít nhất cần bỏ khỏi chiếc vòng cổ của Bessie để nó không chứa tên của con bò kia dưới dạng chuỗi con.

Ví dụ

ababaa
aba

1

Nguồn

USACO 2013 March Contest, Gold — Problem 3: Necklace

Tác giả đề: Yan Gu, 2013.