CSES - Ferris Wheel | Bánh xe Ferris

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
Flower_On_Stone , ming
Dạng bài
Điểm: 900 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Có \(n\) đứa trẻ muốn đi đến một bánh xe Ferris, và nhiệm vụ của bạn là tìm một chiếc gondola cho mỗi đứa trẻ.

[Chú thích: có khả năng là khu vui chơi nằm ở bên kia dòng sông nên các bạn trẻ cần đi thuyền qua.

Mỗi chiếc gondola có thể có một hoặc hai đứa trẻ trong đó, và ngoài ra, tổng trọng lượng trong một chiếc gondola không được vượt quá \(x\). Bạn biết cân nặng của mỗi đứa trẻ.

Số lượng chiếc gondola tối thiểu cần thiết cho những đứa trẻ là bao nhiêu?

Input

  • Dòng đầu vào đầu tiên chứa hai số nguyên \(n\) và \(x\): số lượng đứa trẻ và trọng lượng tối đa cho phép.
  • Dòng tiếp theo chứa \(n\) số nguyên \(p_1,p_2,\ldots,p_n\): trọng lượng của mỗi đứa trẻ.

Output

  • In một số nguyên: số lượng gondola tối thiểu.

Constraints

  • \(1 \leq n \leq 2 \cdot 10 ^ 5\)
  • \(1 \leq x \leq 10 ^ 9\)
  • \(1 \leq p_i \leq x\)

Example

Sample input

4 10
7 2 3 9

Sample output

3

Bình luận


  • -2
    vietnammuonnam_mvn    5:50 p.m. 31 Tháng 8, 2024

    Code python acc 100%
    def sum_of_digits(n):
    return sum(int(digit) for digit in str(n))

    def main():
    import sys
    input = sys.stdin.read
    data = input().split()

    # Đọc số lượng test case
t = int(data[0])

# Xử lý từng test case
results = []
for i in range(1, t + 1):
    n = int(data[i])
    results.append(sum_of_digits(n))

# In kết quả
for result in results:
    print(result)

    if name == "main":
    main()


    • 0
      PhucDepZai    6:37 p.m. 6 Tháng 10, 2024

      ad ơi có thằng chatgpt kìa ad ơi


      • 0
        nhatnam3004    9:35 p.m. 10 Tháng 10, 2024

        nhìn nó giống


        • 0
          nhatnam3004    9:34 p.m. 10 Tháng 10, 2024 ← đã chỉnh sửa

          tao mới thử chatgpt thì nó ra kết quả này
          def ferris_wheel(weights, max_weight):
          weights.sort()
          i, j = 0, len(weights) - 1
          trips = 0

          while i <= j:
    if weights[i] + weights[j] <= max_weight:
        i += 1  # Lightest person gets on
    j -= 1  # Heaviest person gets on
    trips += 1  # One trip is made

return trips

          Example usage

          n = int(input())
          weights = list(map(int, input().split()))
          max_weight = int(input())
          result = ferris_wheel(weights, max_weight)
          print(result)
          nhìn cũng giống lắm

        3 bình luận nữa