20.6 แบบฝึกหัด

เขียนแต่ละข้อเป็นไฟล์ใหม่ใน Code::Blocks รันแล้วเทียบกับผลลัพธ์ที่ต้องได้ให้ตรงทุกตัวอักษร รวมถึงช่องว่างและการขึ้นบรรทัด ติดจริงๆ ค่อยเปิดคำใบ้ และเปิดเฉลยหลังทำเสร็จแล้วเท่านั้น

ข้อ 1 สมุดเยี่ยมงานเลี้ยงรุ่น

ระดับง่าย เวลาไม่เกิน 1 วินาที

งานเลี้ยงรุ่นมีสมุดเยี่ยมให้แขกเขียนชื่อตอนเข้างาน แขกบางคนออกไปข้างนอกแล้วกลับเข้ามาใหม่ จึงเขียนชื่อซ้ำ บางคนเขียนสามสี่รอบ ทั้งสมุดมีชื่อเขียนไว้ N ครั้ง กรรมการอยากรู้ว่าวันนี้มีแขกมากี่คน และอยากได้รายชื่อแขกเรียงตามตัวอักษรเพื่อส่งรูปให้ทีหลัง

ชื่อเดียวกันถือว่าเป็นคนเดียวกัน

ข้อมูลเข้า

บรรทัดแรกมีจำนวนเต็ม N (1 ≤ N ≤ 100000)

อีก N บรรทัด บรรทัดละหนึ่งชื่อ ตามลำดับที่เขียนในสมุด แต่ละชื่อเป็นตัวอักษรภาษาอังกฤษตัวพิมพ์เล็ก a ถึง z ยาว 1 ถึง 20 ตัว

ข้อมูลออก

บรรทัดแรกพิมพ์จำนวนแขกที่ไม่ซ้ำกัน D

อีก D บรรทัดพิมพ์ชื่อแขก บรรทัดละหนึ่งชื่อ เรียงตามตัวอักษรจากน้อยไปมากแบบพจนานุกรม

7
nok
beam
arm
nok
ploy
beam
nok

4
arm
beam
nok
ploy

1
somchai

1
somchai

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    set<string> guests;
    for (int i = 0; i < n; i++) {
        string name;
        cin >> name;
        guests.insert(name);
    }
    cout << guests.size() << '\n';
    for (const string &name : guests) {
        cout << name << '\n';
    }
    return 0;
}

ข้อ 2 เพลงที่คนขอมากที่สุด

ระดับง่าย เวลาไม่เกิน 1 วินาที

สถานีวิทยุของโรงเรียนเปิดให้นักเรียนส่งข้อความขอเพลงช่วงพักเที่ยง แต่ละข้อความมีรหัสเพลงหนึ่งรหัส วันนี้มีข้อความเข้ามา N ข้อความ ดีเจอยากรู้ว่าเพลงไหนมีคนขอมากที่สุด และมีคนขอกี่ครั้ง ถ้ามีหลายเพลงที่คนขอเท่ากันมากที่สุด ให้ตอบเพลงที่รหัสน้อยที่สุด

ข้อมูลเข้า

บรรทัดแรกมีจำนวนเต็ม N (1 ≤ N ≤ 200000)

บรรทัดที่สองมีรหัสเพลงของข้อความที่ 1 ถึง N คั่นด้วยช่องว่าง แต่ละรหัสเป็นจำนวนเต็มตั้งแต่ 1 ถึง 10⁹

ข้อมูลออก

บรรทัดเดียว มีรหัสเพลงที่คนขอมากที่สุด ตามด้วยช่องว่าง แล้วตามด้วยจำนวนครั้งที่เพลงนั้นถูกขอ

7
5021 77 5021 900000001 77 5021 3

5021 3

5
40 12 40 12 999

12 2

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    map<int, int> votes;
    for (int i = 0; i < n; i++) {
        int song;
        cin >> song;
        votes[song]++;
    }
    int best_song = 0;
    int best_votes = 0;
    for (auto entry : votes) {
        if (entry.second > best_votes) {
            best_song = entry.first;
            best_votes = entry.second;
        }
    }
    cout << best_song << ' ' << best_votes << '\n';
    return 0;
}

ข้อ 3 ส่งพัสดุชิ้นที่หนักที่สุด

ระดับง่าย เวลาไม่เกิน 1 วินาที

โกดังพัสดุแห่งหนึ่งมีรถขนของออกไปทีละคัน รถแต่ละคันรับพัสดุได้ทีละชิ้น และหัวหน้าสั่งว่าให้ส่งชิ้นที่หนักที่สุดในโกดังออกไปก่อนเสมอ ตลอดวันมีเหตุการณ์ Q ครั้งเรียงตามเวลา แต่ละครั้งเป็นแบบใดแบบหนึ่งต่อไปนี้

• + w มีพัสดุหนัก w กรัมเข้ามาในโกดัง
• - มีรถมารับของ ให้ส่งพัสดุที่หนักที่สุดในโกดังขณะนั้นออกไป ถ้าหนักเท่ากันหลายชิ้น ส่งชิ้นไหนก็ได้เพราะน้ำหนักที่พิมพ์ออกมาเท่ากัน

ข้อมูลเข้า

บรรทัดแรกมีจำนวนเต็ม Q (1 ≤ Q ≤ 300000)

อีก Q บรรทัด บรรทัดละหนึ่งเหตุการณ์ในรูปแบบข้างบน โดยที่ 1 ≤ w ≤ 10⁹

ข้อมูลออก

ทุกเหตุการณ์ - ให้พิมพ์หนึ่งบรรทัด เป็นน้ำหนักของพัสดุที่ส่งออกไป ถ้าตอนนั้นโกดังว่าง ให้พิมพ์ EMPTY

9
+ 1200
+ 450
-
+ 3000
+ 450
-
-
-
-

1200
3000
450
450
EMPTY

3
-
+ 7
-

EMPTY
7

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int q;
    cin >> q;
    priority_queue<int> parcels;
    for (int i = 0; i < q; i++) {
        char op;
        cin >> op;
        if (op == '+') {
            int weight;
            cin >> weight;
            parcels.push(weight);
        } else if (parcels.empty()) {
            cout << "EMPTY\n";
        } else {
            cout << parcels.top() << '\n';
            parcels.pop();
        }
    }
    return 0;
}

ข้อ 4 คำยอดฮิตในกระทู้

ระดับกลาง เวลาไม่เกิน 1 วินาที

ทีมดูแลเว็บบอร์ดของโรงเรียนอยากทำป้ายคำยอดฮิตประจำสัปดาห์ จึงรวบรวมคำทุกคำจากกระทู้ทั้งหมดมาได้ N คำ ให้หาคำที่ปรากฏบ่อยที่สุด M อันดับแรก

เรียงอันดับตามจำนวนครั้งที่ปรากฏจากมากไปน้อย ถ้าจำนวนครั้งเท่ากัน คำที่มาก่อนตามลำดับพจนานุกรมได้อันดับดีกว่า ถ้ามีคำต่างกันไม่ถึง M คำ ให้พิมพ์ทุกคำที่มี

ข้อมูลเข้า

บรรทัดแรกมีจำนวนเต็ม N และ M คั่นด้วยช่องว่าง (1 ≤ N ≤ 100000, 1 ≤ M ≤ 100)

จากนั้นเป็นคำ N คำ คั่นด้วยช่องว่างหรือขึ้นบรรทัดใหม่ แต่ละคำเป็นตัวอักษรภาษาอังกฤษตัวพิมพ์เล็กยาว 1 ถึง 15 ตัว

ข้อมูลออก

พิมพ์ตามอันดับ บรรทัดละหนึ่งคำ แต่ละบรรทัดมีคำ ตามด้วยช่องว่าง แล้วตามด้วยจำนวนครั้งที่คำนั้นปรากฏ

15 3
the exam is on monday the room is near the library is
the exam hard

the 4
is 3
exam 2

3 5
ok ok fine

ok 2
fine 1

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    map<string, int> count;
    for (int i = 0; i < n; i++) {
        string word;
        cin >> word;
        count[word]++;
    }
    vector<pair<int, string>> ranking;
    for (auto entry : count) {
        ranking.push_back({-entry.second, entry.first});
    }
    sort(ranking.begin(), ranking.end());
    int shown = min(m, (int)ranking.size());
    for (int i = 0; i < shown; i++) {
        cout << ranking[i].second << ' ' << -ranking[i].first << '\n';
    }
    return 0;
}

ข้อ 5 หัวชาร์จที่ใกล้ที่สุด

ระดับกลาง เวลาไม่เกิน 1 วินาที

ทางหลวงสายหนึ่งยาว 10⁹ เมตร มีจุดบอกระยะตั้งแต่เมตรที่ 0 ไปจนสุดทาง บริษัทพลังงานทยอยเปิดและปิดหัวชาร์จรถไฟฟ้าตามจุดต่างๆ จุดเดียวกันมีหัวชาร์จได้หลายหัว เพราะสถานีใหญ่ติดตั้งหลายหัวเรียงกัน ส่วนแอปนำทางต้องตอบผู้ขับขี่ว่าจากจุดที่อยู่ หัวชาร์จที่เปิดอยู่ที่ใกล้ที่สุดห่างไปกี่เมตร จะอยู่ข้างหน้าหรือข้างหลังก็ได้

มีเหตุการณ์ Q ครั้งเรียงตามเวลา แต่ละครั้งเป็นแบบใดแบบหนึ่งต่อไปนี้

• + x เปิดหัวชาร์จเพิ่มหนึ่งหัวที่เมตรที่ x ที่จุดนี้อาจมีหัวที่เปิดอยู่แล้วกี่หัวก็ได้
• - x ปิดหัวชาร์จหนึ่งหัวที่เมตรที่ x รับประกันว่าตอนนั้นมีหัวที่เปิดอยู่ที่จุดนี้อย่างน้อยหนึ่งหัว ถ้ามีหลายหัว หัวที่เหลือยังเปิดอยู่
• ? x ผู้ขับขี่อยู่ที่เมตรที่ x ถามระยะไปยังหัวชาร์จที่เปิดอยู่ที่ใกล้ที่สุด

ข้อมูลเข้า

บรรทัดแรกมีจำนวนเต็ม Q (1 ≤ Q ≤ 200000)

อีก Q บรรทัด บรรทัดละหนึ่งเหตุการณ์ในรูปแบบข้างบน โดยที่ 0 ≤ x ≤ 10⁹

ข้อมูลออก

ทุกเหตุการณ์ ? ให้พิมพ์หนึ่งบรรทัด เป็นระยะไปยังหัวชาร์จที่ใกล้ที่สุด ถ้าตอนนั้นไม่มีหัวชาร์จเปิดอยู่เลย ให้พิมพ์ -1

9
? 500
+ 1200
+ 300
? 500
? 1200
+ 900
? 1000
- 900
? 1000

-1
200
0
100
200

7
+ 0
+ 0
? 1000000000
- 0
? 7
- 0
? 7

1000000000
7
-1

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int q;
    cin >> q;
    multiset<int> chargers;
    for (int i = 0; i < q; i++) {
        char op;
        int x;
        cin >> op >> x;
        if (op == '+') {
            chargers.insert(x);
        } else if (op == '-') {
            chargers.erase(chargers.find(x));
        } else if (chargers.empty()) {
            cout << -1 << '\n';
        } else {
            int best = INT_MAX;
            auto it = chargers.lower_bound(x);
            if (it != chargers.end()) {
                best = min(best, *it - x);
            }
            if (it != chargers.begin()) {
                best = min(best, x - *prev(it));
            }
            cout << best << '\n';
        }
    }
    return 0;
}

ข้อ 6 จองที่นั่งสอบ

ระดับกลาง เวลาไม่เกิน 1 วินาที

ห้องสอบใหญ่มีที่นั่ง N ที่ หมายเลข 1 ถึง N เรียงจากหน้าห้องไปหลังห้อง ตอนเริ่มทุกที่ว่าง ระบบจองที่นั่งรับคำสั่ง Q คำสั่งตามลำดับเวลา แต่ละคำสั่งเป็นแบบใดแบบหนึ่งต่อไปนี้

• B x นักเรียนคนหนึ่งขอที่นั่งหมายเลข x ถ้าที่นั่ง x ว่าง ระบบให้ที่นั่ง x ถ้าไม่ว่าง ระบบให้ที่นั่งว่างที่หมายเลขน้อยที่สุดที่มากกว่า x ถ้าไม่มีที่ว่างตั้งแต่ x ไปจนถึง N เลย นักเรียนคนนี้ไม่ได้ที่นั่ง
• L x นักเรียนที่นั่งอยู่ที่หมายเลข x ลุกออกไป ที่นั่ง x กลับมาว่าง รับประกันว่าตอนนั้นมีคนนั่งที่ x อยู่

ข้อมูลเข้า

บรรทัดแรกมีจำนวนเต็ม N และ Q คั่นด้วยช่องว่าง (1 ≤ N ≤ 200000, 1 ≤ Q ≤ 200000)

อีก Q บรรทัด บรรทัดละหนึ่งคำสั่งในรูปแบบข้างบน โดยที่ 1 ≤ x ≤ N

ข้อมูลออก

ทุกคำสั่ง B ให้พิมพ์หนึ่งบรรทัด เป็นหมายเลขที่นั่งที่นักเรียนได้ ถ้าไม่ได้ที่นั่ง ให้พิมพ์ 0

5 9
B 2
B 2
B 5
B 4
B 4
L 2
B 1
B 1
B 1

2
3
5
4
0
1
2
0

1 4
B 1
B 1
L 1
B 1

1
0
1

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    set<int> empty_seats;
    for (int seat = 1; seat <= n; seat++) {
        empty_seats.insert(seat);
    }
    for (int i = 0; i < q; i++) {
        char op;
        int x;
        cin >> op >> x;
        if (op == 'L') {
            empty_seats.insert(x);
            continue;
        }
        auto it = empty_seats.lower_bound(x);
        if (it == empty_seats.end()) {
            cout << 0 << '\n';
        } else {
            cout << *it << '\n';
            empty_seats.erase(it);
        }
    }
    return 0;
}

ข้อ 7 คะแนนอันดับที่ K

ระดับกลาง เวลาไม่เกิน 1 วินาที

รายการประกวดร้องเพลงออนไลน์เปิดให้ผู้เข้าประกวดส่งคลิปทีละคน กรรมการให้คะแนนทันทีที่ดูคลิปจบ ประกาศกติกาไว้ว่าผู้ที่อยู่ใน K อันดับแรกเมื่อปิดรับสมัครจะได้เข้ารอบ ทุกครั้งที่มีคะแนนใหม่ ผู้เข้าประกวดอยากรู้ว่าตอนนี้ต้องได้คะแนนอย่างน้อยเท่าไรถึงจะติด K อันดับแรก ซึ่งก็คือคะแนนของอันดับที่ K ในขณะนั้น

คะแนนที่เท่ากันนับแยกกันคนละอันดับ เช่น ถ้าคะแนนตอนนี้คือ 90 85 85 70 อันดับที่ 3 คือ 85

ข้อมูลเข้า

บรรทัดแรกมีจำนวนเต็ม N และ K คั่นด้วยช่องว่าง (1 ≤ K ≤ N ≤ 300000)

บรรทัดที่สองมีคะแนนของผู้เข้าประกวดคนที่ 1 ถึง N ตามลำดับที่ส่ง คั่นด้วยช่องว่าง แต่ละคะแนนเป็นจำนวนเต็มตั้งแต่ 0 ถึง 10⁹

ข้อมูลออก

N บรรทัด บรรทัดที่ i เป็นคะแนนของอันดับที่ K หลังจากได้คะแนนของคนที่ 1 ถึง i แล้ว ถ้ายังมีผู้เข้าประกวดไม่ถึง K คน ให้พิมพ์ -1

7 3
70 90 85 60 85 95 40

-1
-1
70
70
85
85
85

2 1
500 200

500
500

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k;
    cin >> n >> k;
    priority_queue<int, vector<int>, greater<int>> best;
    for (int i = 0; i < n; i++) {
        int score;
        cin >> score;
        best.push(score);
        if ((int)best.size() > k) {
            best.pop();
        }
        if ((int)best.size() < k) {
            cout << -1 << '\n';
        } else {
            cout << best.top() << '\n';
        }
    }
    return 0;
}

ข้อ 8 ตลาดหนังสือมือสอง

ระดับยาก เวลาไม่เกิน 1 วินาที

ชมรมห้องสมุดเปิดแผงขายหนังสือมือสอง มีหนังสือ N เล่ม เล่มที่ i ราคา p_i บาท หลายเล่มอาจราคาเท่ากัน ลูกค้า M คนมาที่แผงทีละคนตามลำดับ คนที่ j บอกงบที่มี b_j บาท แล้วจะซื้อหนังสือเล่มที่แพงที่สุดที่ราคาไม่เกินงบ หนึ่งเล่ม ถ้าทุกเล่มที่เหลือแพงเกินงบ ลูกค้าคนนั้นเดินผ่านไปโดยไม่ซื้อ หนังสือที่ขายไปแล้วไม่กลับมาที่แผงอีก

ให้บอกว่าลูกค้าแต่ละคนจ่ายเงินไปเท่าไร

ข้อมูลเข้า

บรรทัดแรกมีจำนวนเต็ม N และ M คั่นด้วยช่องว่าง (1 ≤ N, M ≤ 200000)

บรรทัดที่สองมีราคาหนังสือ p₁ ถึง p_N คั่นด้วยช่องว่าง

บรรทัดที่สามมีงบของลูกค้า b₁ ถึง b_M ตามลำดับที่มา คั่นด้วยช่องว่าง

ราคาและงบเป็นจำนวนเต็มตั้งแต่ 1 ถึง 10⁹

ข้อมูลออก

M บรรทัด บรรทัดที่ j เป็นราคาหนังสือที่ลูกค้าคนที่ j ซื้อ ถ้าไม่ได้ซื้อ ให้พิมพ์ -1

5 6
120 80 250 80 40
100 100 100 30 300 260

80
80
40
-1
250
120

1 3
50
49 50 50

-1
50
-1

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    multiset<int> books;
    for (int i = 0; i < n; i++) {
        int price;
        cin >> price;
        books.insert(price);
    }
    for (int j = 0; j < m; j++) {
        int budget;
        cin >> budget;
        auto it = books.upper_bound(budget);
        if (it == books.begin()) {
            cout << -1 << '\n';
        } else {
            it = prev(it);
            cout << *it << '\n';
            books.erase(it);
        }
    }
    return 0;
}

ข้อ 9 ร้านสะดวกซัก

ระดับยาก เวลาไม่เกิน 1 วินาที

ร้านสะดวกซักหน้ามหาวิทยาลัยมีเครื่องซักผ้า K เครื่อง หมายเลข 1 ถึง K วันนี้มีลูกค้า N คน คนที่ i มาถึงร้านเวลา t_i (นาทีนับจากร้านเปิด) และต้องใช้เครื่องนาน d_i นาที ลูกค้าได้ใช้เครื่องตามลำดับที่มาถึงร้าน คนที่มาก่อนได้ก่อนเสมอ ถ้ามาถึงพร้อมกัน คนที่อยู่ก่อนในข้อมูลเข้าได้ก่อน

เมื่อถึงคิวของลูกค้าคนหนึ่ง เขาเริ่มซักทันทีที่มีเครื่องว่าง ถ้าตอนนั้นมีเครื่องว่างหลายเครื่อง เขาเลือกเครื่องที่หมายเลขน้อยที่สุด ถ้าไม่มีเครื่องว่างเลย เขารอจนกว่าจะมีเครื่องซักเสร็จ เครื่องที่ซักเสร็จเวลา f ว่างให้คนถัดไปใช้ได้ตั้งแต่เวลา f พอดี ลูกค้าคนที่ i ที่เริ่มซักเวลา s จะซักเสร็จเวลา s + d_i

ให้บอกว่าลูกค้าแต่ละคนได้เครื่องหมายเลขอะไร และซักเสร็จเวลาเท่าไร

ข้อมูลเข้า

บรรทัดแรกมีจำนวนเต็ม N และ K คั่นด้วยช่องว่าง (1 ≤ N, K ≤ 200000)

อีก N บรรทัด บรรทัดที่ i มีจำนวนเต็ม t_i และ d_i คั่นด้วยช่องว่าง (0 ≤ t_i ≤ 10⁹, 1 ≤ d_i ≤ 10⁹) รับประกันว่า t₁ ≤ t₂ ≤ ... ≤ t_N

ข้อมูลออก

N บรรทัด บรรทัดที่ i มีหมายเลขเครื่องของลูกค้าคนที่ i ตามด้วยช่องว่าง แล้วตามด้วยเวลาที่ซักเสร็จ

6 2
0 30
5 10
10 20
15 5
40 5
40 5

1 30
2 15
2 35
1 35
1 45
2 45

3 3
100 7
200 7
300 7

1 107
1 207
1 307

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k;
    cin >> n >> k;
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> busy;
    priority_queue<int, vector<int>, greater<int>> idle;
    for (int id = 1; id <= k; id++) {
        idle.push(id);
    }
    long long last_start = 0;
    for (int i = 0; i < n; i++) {
        long long arrive, duration;
        cin >> arrive >> duration;
        long long now = max(arrive, last_start);
        while (!busy.empty() && busy.top().first <= now) {
            idle.push(busy.top().second);
            busy.pop();
        }
        if (idle.empty()) {
            now = busy.top().first;
            while (!busy.empty() && busy.top().first == now) {
                idle.push(busy.top().second);
                busy.pop();
            }
        }
        int machine = idle.top();
        idle.pop();
        busy.push({now + duration, machine});
        last_start = now;
        cout << machine << ' ' << now + duration << '\n';
    }
    return 0;
}

ข้อ 10 ช่วงกำไรพอดีเป้าที่ยาวที่สุด

ระดับยาก เวลาไม่เกิน 1 วินาที

ร้านกาแฟของสหกรณ์โรงเรียนจดกำไรของแต่ละวันไว้ N วัน วันที่ขาดทุนจดเป็นค่าติดลบ ผู้จัดการอยากเขียนรายงานว่า "ร้านทำกำไรได้ตรงเป้า K บาทพอดีในช่วงเวลา X วันติดกัน" และอยากให้ X มากที่สุดเท่าที่ทำได้ ให้หาว่าช่วงวันติดกันที่กำไรรวมเท่ากับ K พอดี ยาวที่สุดกี่วัน

ช่วงหนึ่งคือวันที่ l ถึงวันที่ r เมื่อ 1 ≤ l ≤ r ≤ N ยาว r - l + 1 วัน ช่วงที่มีวันเดียวก็นับ

ข้อมูลเข้า

บรรทัดแรกมีจำนวนเต็ม N และ K คั่นด้วยช่องว่าง (1 ≤ N ≤ 200000, -10¹⁵ ≤ K ≤ 10¹⁵)

บรรทัดที่สองมีกำไรของวันที่ 1 ถึง N คั่นด้วยช่องว่าง แต่ละค่าเป็นจำนวนเต็มตั้งแต่ -10⁹ ถึง 10⁹

ข้อมูลออก

ความยาวเป็นจำนวนวันของช่วงที่ยาวที่สุดที่กำไรรวมเท่ากับ K ถ้าไม่มีช่วงไหนเลยให้พิมพ์ 0

6 400
300 -100 200 -200 300 100

4

5 7
2 4 6 8 10

0

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    long long target;
    cin >> n >> target;
    map<long long, int> first_day;
    first_day[0] = 0;
    long long prefix = 0;
    int best = 0;
    for (int i = 1; i <= n; i++) {
        long long profit;
        cin >> profit;
        prefix += profit;
        auto it = first_day.find(prefix - target);
        if (it != first_day.end()) {
            best = max(best, i - it->second);
        }
        if (first_day.count(prefix) == 0) {
            first_day[prefix] = i;
        }
    }
    cout << best << '\n';
    return 0;
}