Đếm các tập con

Submit solution
Points: 3 (partial)
Time limit: 0.1s
JAVA11 1.0s
Python 3 1.0s
Memory limit: 98M
JAVA11 977M
Python 3 977M
Author:
creator
Problem type
Allowed languages
Ada, Assembly, Awk, C, C++, C11, CLANG, CLANGX, Classical, COBOL, Coffee, CSC, D lang, DART, F95, FORTH, Fortrn, GAS32, GO, Haskell, Itercal, Java, kotlin, LEAN, LISP, LUA, MONOVB, Nasm, OCAML, Pascal, Perl, php, PIKE, prolog, Pypy, Python, Ruby 2, RUST, Scala, SCM, SED, SWIFT, TCL, TUR, V8JS, VB, ZIG

Cho S là một tập hợp các số tự nhiên và số tự nhiên m; đếm số lượng tập con phân biệt của S (trừ tập rỗng) mà tổng các phần tử trong mỗi tập con đó bằng m.

Đầu vào

Dòng đầu gồm số tự nhiên n (1≤n≤1000) và số tự nhiên m (0≤m≤1000).

Dòng tiếp theo gồm n số tự nhiên trong đoạn [0,109] là các phần tử của tập hợp.

Ghi chú: n số tự nhiên nhập vào đảm bảo đôi một phân biệt.

Đầu ra

Một số tự nhiên duy nhất là số lượng tập con cần tìm.

Chú ý: Kết quả lấy mod không âm cho 109+7.

Ví dụ

Đầu vào:

Copy
5 5
1 2 3 4 5

Đầu ra:

Copy
3

Giải thích: Có 3 tập con có tổng bằng 5 là {1,4}, {2,3}, {5}.

.

QDUY

Comments


  • 0
    02200123  commented on April 13, 2023, 8:00 a.m. ← edited

    mình 1 vòng for mà vẫn bị tle

    Copy
    import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class demcactapcon {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n,m,temp;
        Map<Integer,Integer> map = new HashMap<>();
        n = sc.nextInt();
        m = sc.nextInt();
        int result = 0;
        for(int i = 0;i < n; i++)
        {
            temp = sc.nextInt();
            if(temp == m)
                result +=1;
            else
                if(map.get(m - temp) != null)
                    result +=1;
            map.put(temp,1);
        }
        System.out.println(result);
    }
}

    • 0
      creator  commented on April 13, 2023, 7:37 p.m.

      Mình đã bổ sung thêm nn java, bạn xem lại bài nộp của nhé.


      • 0
        02200123  commented on April 14, 2023, 1:59 a.m.

        ok mình cảm ơn nhé


  • 0
    ToMinhTien_CNTT4_K62  commented on July 7, 2022, 9:20 a.m.

    Giới hạn thời gian có 0.1s mà 2 for vẫn AC :v