NOI Singapore 2026 - Famished Cats - LQDOJ: Le Quy Don Online Judge

NOI Singapore 2026 - Famished Cats

Dạng bài

Ngôn ngữ cho phép

Assembly, Awk, C, C#, C++, Clang, Cobol, D, Haskell, JS, Java, Kotlin, Lua, Node JS, OCaml, ObjectiveC, Output, PHP, Pascal, Perl, Prolog, Pypy, Pypy 3, Python, Ruby, Rust, Scala, Scratch

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

Vương quốc mèo nằm dọc một con đường rất dài từ tây sang đông. Ngân hàng thức ăn ở đầu phía tây. Có $n$ ngôi nhà mèo về phía đông, đánh số từ $1$ đến $n$; $n$ là số chẵn. Nhà $1$ cách ngân hàng $d_1$ km. Với $i\ge2$, nhà $i$ cách nhà $i-1$ một đoạn $d_i$ km.

Hình 1: Ngân hàng thức ăn và các nhà mèo theo thứ tự từ tây sang đông; $d_i$ là khoảng cách đến vị trí liền trước.

Ket lái xe tải giao thức ăn từ ngân hàng với $x$ đơn vị nhiên liệu. Một đơn vị nhiên liệu cho phép đi $1$ km. Nhà $i$ có $f_i$ đơn vị nhiên liệu mà xe có thể lấy. Xe chứa nhiên liệu không giới hạn, chỉ dừng khi hết nhiên liệu và không cần quay về.

Ket có thể dùng đũa phép để hoán đổi lượng nhiên liệu ở nhà $i$ và nhà $n-i+1$. Chỉ được hoán đổi khi nhiên liệu ở cả hai nhà chưa được sử dụng.

Hãy tìm chỉ số xa nhất $D$ của ngôi nhà Ket có thể tới sau một số bất kỳ phép hoán đổi, đồng thời tìm số phép hoán đổi nhỏ nhất $S$ cần để tới được nhà $D$.

Dữ liệu vào

Dòng đầu chứa $n,x$.
Dòng thứ hai chứa $d_1,d_2,\ldots,d_n$.
Dòng thứ ba chứa $f_1,f_2,\ldots,f_n$.

Dữ liệu ra

In hai số nguyên $D$ và $S$.

Giới hạn

\[ 2\le n\le500\,000,\quad n\text{ chẵn},\quad d_1\le x\le10^9 \]

\[ 1\le d_i,f_i\le10^9 \]

Chấm điểm

Phần	Điểm	Giới hạn thêm
1	7	Tồn tại hằng số $k$ sao cho $
2	12	$n\le40$
3	14	$f_i\le f_{i+1}$ với mọi $1\le i<n$
4	19	$D\le n/2$
5	21	$n\le5000$
6	27	Không có giới hạn thêm

Ví dụ

Ví dụ 1

Input

6 1
1 1 3 1 1 6
1 1 1 4 3 2

Output

5 1

Note

Ket tới nhà $1$, lấy nhiên liệu rồi tới nhà $2$. Hoán đổi nhiên liệu ở nhà $2$ và $5$ giúp xe lần lượt tới nhà $3$, $4$, $5$. Xe còn $4$ đơn vị nhưng cần $6$ để tới nhà $6$, nên $D=5$ và số hoán đổi nhỏ nhất là $S=1$.

Hình 2: Khoảng cách, nhiên liệu ban đầu và hành trình trong ví dụ 1.

Ví dụ 2

Input

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

Output

6 1

Ví dụ 3

Input

6 2
2 24 25 40 5 11
4 12 14 16 20 30

Output

3 2

Ví dụ 4

Input

6 10
3 6 3 7 8 6
4 3 1 7 1 6

Output

5 1

Bình luận

Tải bình luận...

Không có bình luận nào.

Kỳ thi:

NOI Singapore 2026 - Vòng chung kết (14 Tháng ba, 2026)

Phần	Điểm	Giới hạn thêm
1	7	Tồn tại hằng số \(k\) sao cho $
2	12	\(n\le40\)
3	14	\(f_i\le f_{i+1}\) với mọi \(1\le i<n\)
4	19	\(D\le n/2\)
5	21	\(n\le5000\)
6	27	Không có giới hạn thêm