Bài Vè Mừng Ông Già Noel

Điểm: 3,00 (OI)

Giới hạn thời gian: 1.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

C++, Dart, Go, Groovy, Java, Javascript, Kotlin, Pascal, Perl, PHP, Python, Ruby, Rust, Scratch, Typescript, Zig

Cho một dãy gồm $n$ phần với độ dài (thời gian) lần lượt là $a_{1}, a_{2}, \dots, a_{n}$ . Bạn cần đọc các phần theo đúng thứ tự: đầu tiên là phần $a_{1}$ , kế đến là $a_{2}$ , và cứ thế. Người nghe chỉ lắng nghe trong tối đa $s$ giây, và bạn nhận được số quà bằng số phần được đọc trọn vẹn trong giới hạn thời gian đó.

Bạn được phép bỏ qua nhiều nhất một phần trong dãy (bỏ qua nhiều hơn một phần sẽ bị phát hiện). Hãy xác định bạn nên bỏ qua phần nào để số quà nhận được là lớn nhất. Nếu không cần bỏ qua phần nào (đọc trọn cả dãy vẫn trong giới hạn $s$ ), in ra $0$ . Nếu có nhiều đáp án tối ưu, in ra một đáp án bất kỳ.

Bạn phải xử lý $t$ test trong cùng một input.

Dữ liệu vào

Dòng đầu chứa số nguyên $t$ — số test ( $1 \leq t \leq 100$ ).
Với mỗi test:
- Dòng đầu chứa hai số nguyên $n$ và $s$ ( $1 \leq n \leq 10^{5}$ , $1 \leq s \leq 10^{9}$ ).
- Dòng thứ hai chứa $n$ số nguyên $a_{1}, a_{2}, \dots, a_{n}$ ( $1 \leq a_{i} \leq 10^{9}$ ).

Tổng $n$ trên tất cả các test không vượt quá $10^{5}$ .

Dữ liệu ra

Với mỗi test, in ra một số nguyên duy nhất — chỉ số (theo $1$ ) của phần cần bỏ qua để tối đa số quà, hoặc $0$ nếu không cần bỏ qua phần nào. Nếu có nhiều đáp án tối ưu, in ra đáp án bất kỳ.

Ràng buộc

$1 \leq t \leq 100$
$1 \leq n \leq 10^{5}$
$1 \leq s \leq 10^{9}$
$1 \leq a_{i} \leq 10^{9}$
Tổng $n$ trên tất cả các test không vượt quá $10^{5}$ .

Ví dụ

Input	Output	Giải thích
3 7 11 2 9 1 3 18 1 4 4 35 11 9 10 7 1 8 5	2 1 0	Test 1: bỏ qua phần thứ $2$ (giá trị $9$ ), dãy còn $2, 1, 3, 18, 1, 4$ với tổng tiền tố $2, 3, 6, 24, \dots$ — đọc được $3$ phần đầu (tổng $6 \leq 11$ ). Test 2: bỏ qua phần $1$ (giá trị $11$ ), tổng còn lại $9 + 10 + 7 = 26 \leq 35$ , đọc trọn $3$ phần. Test 3: tổng $5 \leq 8$ , đọc trọn cả dãy nên in $0$ .

Bình luận

Không có bình luận tại thời điểm này.