Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: [Giải thuật] Cắt thanh sô-cô-la

    Có nnn thanh sô-cô-la, thanh thứ iii dài aia_iai​ đơn vị. Cô giáo muốn chia cho kkk bạn nhỏ, mỗi bạn nhận đúng một đoạn sô-cô-la có độ dài bằng nhau là xxx (số nguyên dương).

    Từ một thanh dài aia_iai​ ta có thể cắt ra ⌊ai/x⌋\lfloor a_i / x \rfloor⌊ai​/x⌋ đoạn dài xxx (phần dư bỏ đi). Tổng số đoạn cắt được từ tất cả các thanh phải ≥k\ge k≥k thì mới đủ chia.

    Hãy tìm giá trị xxx lớn nhất sao cho vẫn cắt được ít nhất kkk đoạn. Nếu không thể chia đủ với x≥1x \ge 1x≥1, in ra 000.

    • Định dạng đầu vào:

      Dòng đầu chứa hai số nguyên nnn và kkk. Dòng thứ hai chứa nnn số nguyên a1,…,ana_1, \dots, a_na1​,…,an​.

    • Ràng buộc đầu vào:

      1≤n≤1051 \le n \le 10^51≤n≤105; 1≤k≤1091 \le k \le 10^91≤k≤109; 1≤ai≤1091 \le a_i \le 10^91≤ai​≤109.

    • Định dạng đầu ra:

      In ra một số nguyên là độ dài đoạn lớn nhất xxx, hoặc 000 nếu không chia đủ.

    Ví dụ:

    Đầu vào:

    3 7
5 9 4

    Đầu ra:

    2

    Giải thích:

    Với x=2: 5//2+9//2+4//2 = 2+4+2 = 8 >= 7. Với x=3: 1+3+1=5 < 7. Vậy x lớn nhất = 2.

    Đang tải editor...