JOI 2009/2010 - Vòng chung kết - Bộ đề bài

#	Bài tập	Điểm	Thời gian:	Giới hạn bộ nhớ
1	JOI 2010 - A Traveler	100 (p)	1.0s	64M
2	JOI 2010 - Dividing Snacks	100 (p)	1.0s	64M
3	JOI 2010 - Icicles	100 (p)	1.0s	64M
4	JOI 2010 - Exposition	100 (p)	1.0s	64M
5	JOI 2010 - Dungeon	100 (p)	1.0s	64M

1. JOI 2010 - A Traveler

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 64M Input: bàn phím Output: màn hình

Bạn là một lữ khách đang đi trên con đường JOI. Con đường này chạy thẳng theo hướng đông–tây, với \(n\) thị trấn dừng chân được đánh số từ \(1\) đến \(n\) theo thứ tự từ tây sang đông. Thị trấn \(1\) nằm xa nhất về phía tây, còn thị trấn \(n\) nằm xa nhất về phía đông.

Bạn xuất phát từ thị trấn \(1\) và thực hiện chuyến đi kéo dài \(m\) ngày. Lịch trình được xác định bởi dãy \(a_1,a_2,\ldots,a_m\). Số nguyên khác \(0\) \(a_i\) mô tả cách di chuyển trong ngày thứ \(i\): nếu bắt đầu ngày đó ở thị trấn \(k\), bạn đi thẳng từ thị trấn \(k\) đến thị trấn \(k+a_i\).

Yêu cầu

Cho số thị trấn \(n\), số ngày đi \(m\), khoảng cách giữa các thị trấn và dãy \(a_1,a_2,\ldots,a_m\), hãy viết chương trình tính phần dư khi chia tổng quãng đường bạn đi trong \(m\) ngày cho \(100000=10^5\).

Dữ liệu vào

Dữ liệu được cung cấp qua đầu vào chuẩn.

Dòng đầu tiên chứa hai số nguyên \(n,m\), cách nhau bởi dấu cách, lần lượt là số thị trấn trên đường JOI và số ngày của chuyến đi.
\(n-1\) dòng tiếp theo mô tả khoảng cách giữa các thị trấn. Dòng thứ \(i+1\) (\(1\le i\le n-1\)) chứa số nguyên dương \(s_i\), là khoảng cách giữa thị trấn \(i\) và thị trấn \(i+1\).
\(m\) dòng tiếp theo chứa lịch trình của \(m\) ngày. Dòng thứ \(i+n\) (\(1\le i\le m\)) chứa số nguyên khác \(0\) \(a_i\), mô tả cách di chuyển trong ngày thứ \(i\).

Dữ liệu ra

In ra đầu ra chuẩn một dòng chứa phần dư khi chia tổng quãng đường đi trong \(m\) ngày cho \(100000=10^5\).

Ràng buộc

Giới hạn trong kỳ thi gốc: thời gian \(1\) giây, bộ nhớ \(64\) MB.
\(2\le n\le100000=10^5\).
\(1\le m\le100000=10^5\).
\(1\le s_i\le100\) (\(1\le i\le n-1\)).
\(a_i\) là số nguyên khác \(0\) (\(1\le i\le m\)).
Trong mọi dữ liệu chấm, bạn không bao giờ đi về phía tây vượt quá thị trấn \(1\) hoặc về phía đông vượt quá thị trấn \(n\).

Phân nhóm

Bài này có tổng cộng \(20\) điểm, gồm \(10\) bộ dữ liệu, mỗi bộ \(2\) điểm. Các tỷ lệ dưới đây được tính trên tổng điểm của bài.

\(50\%\) số điểm dành cho các dữ liệu thỏa mãn \(n\le100\) và \(m\le100\).

Ví dụ

Ví dụ 1

Input

Output

Giải thích

Ngày thứ \(1\), bạn đi từ thị trấn \(1\) đến thị trấn \(3\). Ngày thứ \(2\), bạn đi từ thị trấn \(3\) đến thị trấn \(2\). Ngày thứ \(3\), bạn đi từ thị trấn \(2\) đến thị trấn \(5\). Ngày thứ \(4\), bạn đi từ thị trấn \(5\) đến thị trấn \(7\). Ngày thứ \(5\), bạn đi từ thị trấn \(7\) đến thị trấn \(4\). Tổng quãng đường đi trong \(5\) ngày là \(18\).

2. JOI 2010 - Dividing Snacks

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 64M Input: bàn phím Output: màn hình

Có một thanh bánh dài \(N\) milimét, trong đó \(N\) là số chẵn. Hai người có liên quan đến JOI quyết định cắt thanh bánh thành nhiều đoạn rồi chia nhau, sao cho mỗi người nhận được các đoạn có tổng chiều dài là \(N/2\) milimét.

Không rõ vì sao, độ dễ cắt của thanh bánh lại khác nhau tùy theo vị trí. Hai người đã kiểm tra từng vị trí cách nhau \(1\) milimét tính từ đầu trái và xác định số giây cần để cắt tại mỗi vị trí.

Yêu cầu

Hãy viết chương trình tính tổng thời gian cắt ít nhất, tính bằng giây, để hai người có thể chia thanh bánh như trên.

Dữ liệu vào

Dữ liệu được cung cấp qua đầu vào chuẩn.

Dòng đầu tiên chứa số nguyên chẵn \(N\), là chiều dài thanh bánh tính bằng milimét.
Dòng thứ \(i+1\) (\(1\le i\le N-1\)) chứa số nguyên \(t_i\), là số giây cần để cắt tại vị trí cách đầu trái \(i\) milimét.

Lưu ý rằng chỉ có \(N-1\) vị trí có thể cắt.

Dữ liệu ra

In ra đầu ra chuẩn một dòng chứa tổng số giây ít nhất cần để cắt thanh bánh cho hai người chia nhau.

Ràng buộc

Giới hạn trong kỳ thi gốc: thời gian \(1\) giây, bộ nhớ \(64\) MB.
\(2\le N\le10000\).
\(N\) là số chẵn.
\(1\le t_i\le10000\) (\(1\le i\le N-1\)).
Mọi giá trị trong dữ liệu vào đều là số nguyên.

Phân nhóm

Bài này có tổng cộng \(20\) điểm, gồm \(20\) bộ dữ liệu, mỗi bộ \(1\) điểm. Các tỷ lệ dưới đây được tính trên tổng điểm của bài.

\(5\%\) số điểm dành cho các dữ liệu mà thời gian nhỏ nhất có thể đạt được bằng cách cắt tại không quá \(2\) vị trí.
\(10\%\) số điểm dành cho các dữ liệu mà thời gian nhỏ nhất có thể đạt được bằng cách cắt tại không quá \(3\) vị trí.
\(20\%\) số điểm dành cho các dữ liệu thỏa mãn \(N\le20\).

Ví dụ

Ví dụ 1

Input

Output

Giải thích

Trong trường hợp này, cắt tại hai vị trí cách đầu trái \(1\) milimét và \(4\) milimét sẽ cho tổng thời gian nhỏ nhất. Hai lần cắt lần lượt mất \(1\) giây và \(6\) giây, tổng cộng \(7\) giây.

3. JOI 2010 - Icicles

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 64M Input: bàn phím Output: màn hình

Dưới mái hiên nhà cậu bé JOI sống ở Canada đã hình thành những cột băng rất đẹp. Nhân dịp này, JOI quyết định tìm hiểu về chúng.

Có \(N\) cột băng dưới mái hiên, nằm trên cùng một đường thẳng. Cột băng thứ \(i\) nằm ở vị trí cách đầu trái của mái hiên \(i\) cm (\(1\le i\le N\)), và ban đầu dài \(a_i\) cm, trong đó \(a_i\) là số nguyên dương. Các cột băng dài ra theo các quy tắc sau:

Cột băng thứ \(i\) chỉ dài ra với tốc độ \(1\) cm mỗi giờ khi nó dài hơn cả cột băng thứ \(i-1\) lẫn cột băng thứ \(i+1\). Với hai cột băng ở hai đầu, chỉ xét cột băng bên cạnh duy nhất: cột thứ \(1\) dài ra nếu dài hơn cột thứ \(2\); cột thứ \(N\) dài ra nếu dài hơn cột thứ \(N-1\).
Ngay khi đạt chiều dài \(L\) cm, một cột băng sẽ gãy ngay tại gốc. Từ đó trở đi, cột băng đã gãy được xem là có chiều dài \(0\) cm.

Ban đầu, mọi cặp cột băng kề nhau đều có chiều dài khác nhau. Với điều kiện này, sau đủ lâu, cả \(N\) cột băng đều sẽ gãy và có chiều dài \(0\) cm. JOI muốn biết cần bao lâu để đạt đến trạng thái đó.

Yêu cầu

Cho chiều dài ban đầu của \(N\) cột băng và chiều dài giới hạn \(L\), hãy viết chương trình tính thời gian cho đến khi tất cả các cột băng đều gãy.

Dữ liệu vào

Dữ liệu được cung cấp qua đầu vào chuẩn.

Dòng đầu tiên chứa hai số nguyên \(N,L\), theo thứ tự này và cách nhau bởi dấu cách, lần lượt là số cột băng và chiều dài giới hạn của chúng.
Dòng thứ \(i+1\) (\(1\le i\le N\)) chứa số nguyên \(a_i\), là chiều dài ban đầu của cột băng thứ \(i\).

Dữ liệu ra

In ra đầu ra chuẩn một dòng chỉ chứa một số nguyên: thời gian tính bằng giờ cho đến khi tất cả các cột băng đều gãy.

Ràng buộc

Giới hạn trong kỳ thi gốc: thời gian \(1\) giây, bộ nhớ \(64\) MB.
\(2\le N\le100000=10^5\).
\(2\le L\le50000\).
\(1\le a_i<L\) (\(1\le i\le N\)).
\(a_i\ne a_{i+1}\) (\(1\le i<N\)).
Mọi giá trị trong dữ liệu vào đều là số nguyên.

Phân nhóm

Bài này có tổng cộng \(20\) điểm, gồm \(10\) bộ dữ liệu, mỗi bộ \(2\) điểm. Các tỷ lệ dưới đây được tính trên tổng điểm của bài.

\(30\%\) số điểm dành cho các dữ liệu thỏa mãn \(N\le500\) và \(L\le1000\).

Ví dụ

Ví dụ 1

Input

Output

Giải thích

Các cột băng thứ \(1,2,3,4\) lần lượt gãy sau \(2,8,4,1\) giờ. Vì vậy, tất cả các cột băng đều gãy sau \(8\) giờ, nên in ra \(8\).

Ví dụ 2

Input

Output

4. JOI 2010 - Exposition

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 64M Input: bàn phím Output: màn hình

Thành phố JOI quyết định tổ chức một cuộc triển lãm quy mô lớn.

Cuộc triển lãm lần này có hai chủ đề. Mỗi một trong \(N\) cơ sở trưng bày của thành phố sẽ tổ chức trưng bày theo đúng một trong hai chủ đề đó.

Vị trí của mỗi cơ sở được biểu diễn bằng tọa độ \((x,y)\) trên mặt phẳng. Thời gian di chuyển từ cơ sở tại \((x,y)\) đến cơ sở tại \((x',y')\) là

\[ |x-x'|+|y-y'|. \]

Với số nguyên \(a\), ký hiệu \(|a|\) biểu thị giá trị tuyệt đối của \(a\).

Để tạo sự thống nhất giữa các cơ sở cùng chủ đề và tránh gây bất tiện cho những người chỉ quan tâm đến một chủ đề, thành phố muốn phân chia chủ đề sao cho thời gian di chuyển giữa hai cơ sở cùng chủ đề ngắn nhất có thể. Có thể phân chia theo bất kỳ cách nào, miễn là không gán cùng một chủ đề cho tất cả các cơ sở.

Yêu cầu

Gọi \(M\) là thời gian di chuyển lớn nhất giữa hai cơ sở được gán cùng chủ đề. Cho vị trí của \(N\) cơ sở, hãy viết chương trình tìm giá trị nhỏ nhất có thể của \(M\).

Dữ liệu vào

Dữ liệu được cung cấp qua đầu vào chuẩn.

Dòng đầu tiên chứa số nguyên \(N\), là số cơ sở trưng bày.
Dòng thứ \(i+1\) (\(1\le i\le N\)) chứa hai số nguyên \(x_i,y_i\), cách nhau bởi dấu cách, cho biết cơ sở thứ \(i\) nằm tại tọa độ \((x_i,y_i)\).

Không có hai cơ sở nào nằm tại cùng một tọa độ.

Dữ liệu ra

In ra đầu ra chuẩn đúng một dòng chứa giá trị nhỏ nhất có thể của \(M\), tức thời gian di chuyển lớn nhất giữa hai cơ sở cùng chủ đề.

Ràng buộc

Giới hạn trong kỳ thi gốc: thời gian \(1\) giây, bộ nhớ \(64\) MB.
\(3\le N\le100000=10^5\).
\(|x_i|\le100000=10^5\) và \(|y_i|\le100000=10^5\) (\(1\le i\le N\)).
Các tọa độ \((x_i,y_i)\) đôi một khác nhau.
Mọi giá trị trong dữ liệu vào đều là số nguyên.

Phân nhóm

Bài này có tổng cộng \(20\) điểm, gồm \(10\) bộ dữ liệu, mỗi bộ \(2\) điểm. Các tỷ lệ dưới đây được tính trên tổng điểm của bài.

\(40\%\) số điểm dành cho các dữ liệu thỏa mãn \(N\le2000\).

Ví dụ

Ví dụ 1

Input

Output

Giải thích

Chẳng hạn, gán một chủ đề cho các cơ sở tại \((0,0)\), \((1,0)\), \((0,1)\) và chủ đề còn lại cho các cơ sở tại \((-1,-2)\), \((-1,1)\). Khi đó, thời gian di chuyển giữa mọi cặp cơ sở cùng chủ đề đều không vượt quá \(3\).

Không thể làm cho tất cả các thời gian di chuyển này đều không vượt quá \(2\), nên in ra \(3\).

5. JOI 2010 - Dungeon

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 64M Input: bàn phím Output: màn hình

Bạn muốn lấy kho báu nằm ở tầng ngầm thứ \(N\) của một hầm ngục. Ban đầu, bạn đang ở tầng ngầm thứ \(1\) và có \(H\) thể lực, trong đó \(H\) là số nguyên dương. Mỗi lần xuống tầng bên dưới, bạn sẽ tiêu hao thể lực. Lượng thể lực tiêu hao khi đi xuống từ mỗi tầng đã được biết trước.

Mỗi tầng có một suối hồi phục. Lượng thể lực hồi phục sau mỗi lần sử dụng suối được xác định riêng cho từng tầng. Nếu thể lực giảm xuống \(0\) hoặc thấp hơn, bạn sẽ chết. Thể lực cũng không bao giờ vượt quá \(H\), kể cả khi hồi phục. Bạn có thể sử dụng suối bao nhiêu lần tùy ý, nhưng việc hồi phục mất thời gian, nên bạn muốn dùng suối ít lần nhất có thể.

Một khi đã xuống tầng bên dưới, bạn không thể quay lại tầng phía trên cho đến khi lấy được kho báu.

Yêu cầu

Cho \(N\), \(H\), lượng thể lực tiêu hao khi đi xuống từ mỗi tầng và lượng thể lực hồi phục sau mỗi lần sử dụng suối ở từng tầng, hãy viết chương trình tính số lần sử dụng suối ít nhất cần thiết để đến tầng ngầm thứ \(N\) mà không để thể lực giảm xuống \(0\) hoặc thấp hơn.

Dữ liệu vào

Dữ liệu được cung cấp qua đầu vào chuẩn, gồm \(N\) dòng.

Dòng đầu tiên chứa hai số nguyên \(N,H\), cách nhau bởi dấu cách. Kho báu nằm ở tầng ngầm thứ \(N\); \(H\) vừa là thể lực ban đầu khi bạn đến tầng ngầm thứ \(1\), vừa là thể lực tối đa.
\(N-1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên cách nhau bởi dấu cách. Dòng thứ \(i+1\) (\(1\le i\le N-1\)) chứa \(d_i,h_i\): \(d_i\) là thể lực tiêu hao khi đi từ tầng ngầm thứ \(i\) xuống tầng ngầm thứ \(i+1\), còn \(h_i\) là thể lực hồi phục sau mỗi lần sử dụng suối tại tầng ngầm thứ \(i\). Việc hồi phục không thể làm thể lực vượt quá \(H\).

Mọi dữ liệu chấm đều bảo đảm có cách đến được tầng ngầm thứ \(N\).

Dữ liệu ra

In ra đầu ra chuẩn một dòng chứa số lần sử dụng suối ít nhất cần thiết để đến tầng ngầm thứ \(N\) mà không để thể lực giảm xuống \(0\) hoặc thấp hơn.

Ràng buộc

Giới hạn trong kỳ thi gốc: thời gian \(1\) giây, bộ nhớ \(64\) MB.
\(2\le N\le100000=10^5\).
\(1\le H\le10000000=10^7\).
\(0\le d_i<H\) (\(1\le i\le N-1\)).
\(1\le h_i<H\) (\(1\le i\le N-1\)).
Mọi giá trị trong dữ liệu vào đều là số nguyên.
Luôn tồn tại cách đến tầng ngầm thứ \(N\).

Phân nhóm

Bài này có tổng cộng \(20\) điểm, gồm \(10\) bộ dữ liệu, mỗi bộ \(2\) điểm. Các tỷ lệ dưới đây được tính trên tổng điểm của bài.

\(10\%\) số điểm dành cho các dữ liệu thỏa mãn \(N\le1000\) và \(H\le1000\).
\(30\%\) số điểm dành cho các dữ liệu thỏa mãn \(N\le1000\).
\(50\%\) số điểm dành cho các dữ liệu mà số lần sử dụng suối ít nhất không vượt quá \(10^6\).

Lưu ý

Các số nguyên cần xử lý trong bài này có thể vượt quá phạm vi biểu diễn của số nguyên 32 bit.

Ví dụ

Ví dụ 1

Input

Output