CSES - Ferris Wheel | Bánh xe Ferris

View as PDF



Authors:
Problem types
Points: 900 (p) Time limit: 1.0s Memory limit: 512M Input: stdin Output: stdout

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


Comments

  • vietnammuonnam_mvn 5:50 p.m. 31 aug, 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()

    • kay 9:17 p.m. 18 jun, 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)

      • MinhTri2400811 11:19 a.m. 14 jan, 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)

        • xthabao1 7:27 a.m. 13 sep, 2023

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