CSES - Ferris Wheel | Bánh xe Ferris

Xem PDF



Tác giả:
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

\(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\)\(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


  • -1
    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()

    1 phản hồi

    • -1
      kay    9:17 p.m. 18 Tháng 6, 2024

      n, x = map(int, input().split())
      P = list(map(int, input().split()))
      P.sort()
      E = 0
      l = 0
      r = n - 1
      while l <= r:
      if P[l] + P[r] <= x:
      l += 1
      r -= 1
      else:
      r -= 1
      E += 1
      print(E)


      • -1
        tk22NguyenHongPhuc    11:19 a.m. 14 Tháng 1, 2024

        n,x=map(int,input().split())
        P=list(map(int,input().split()))
        P.sort()
        E=0
        l=0
        r=n-1
        while l<=r:
        if P[l]+P[r]<=x:
        l+=1
        r-=1
        E+=1
        print(E)

        3 phản hồi

        • 1
          xthabao1    7:27 a.m. 13 Tháng 9, 2023

          Giải thích hộ mình với mn oi

          1 phản hồi