HSG THPT Hải Phòng 2023 - Bài 4

View as PDF
Submit solution
Points: 0.01
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout
Author:
bedao
Problem source:
Kỳ thi Học sinh giỏi THPT TP Hải Phòng 2023
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Cho dãy gồm ~N~ số nguyên dương ~a_1, a_2, \ldots, a_N~. Hãy kiểm tra xem trong dãy số đã cho có hay không cặp ~(u, v)~ ~(1 \leq u, v \leq N)~ thoả mãn:

  • ~a_u~ là số chẵn

  • ~a_v~ là số lẻ.

  • ~a_u + a_v = k~.

Input

Dòng đầu tiên chứa số nguyên dương ~t~ ~(2 \leq t \leq 5)~ là số bộ test, mỗi bộ test được mô tả trên ~2~ dòng:

  • Dòng thứ nhất chứa hai số nguyên dương ~(N, k)~.

  • Dòng thứ hai chứa ~N~ số nguyên dương ~a_i~ ~(1 \leq i \leq N)~.

Output

Ghi ra ~t~ ký tự, ký tự thứ ~i~ là ~1~ nếu bộ test thứ ~i~ có cặp ~(u, v)~ thỏa mãn điều kiện đề bài, ngược lại ghi ~0~.

Scoring

Subtask Điểm Giới hạn
1 ~60~ ~n \leq 1000, 1 \leq a_i \leq 10^9, 1 \leq k \leq 2 \times 10^9~
2 ~20~ ~n \leq 10^6, 1 \leq a_i \leq 2000, 1 \leq k \leq 4000~
3 ~20~ ~n \leq 10^5, 1 \leq a_i \leq 10^9, 1 \leq k \leq 2 \times 10^9~

Sample Input 1

2
4 6
3 2 4 3
9 13
11 7 1 5 3 2 4 6 9

Sample Output 1

01

Notes

  • Test 1: Không có cặp ~(u, v)~ nào thỏa mãn điều kiện đề bài.

  • Test 2 : Có nhiều cặp ~(u, v)~ thỏa mãn như cặp ~u = 6; v = 1~ có ~a_u+a_v=13~.

Comments

Please read the guidelines before commenting.


  • -8
    Hechbros  commented on Dec. 4, 2024, 6:17 p.m. ← edit 4

    This comment is hidden due to too much negative feedback. Show it anyway.


    • 0
      dmnguyel23  commented on Jan. 6, 2025, 3:49 a.m.

      chép thì được cái gì khôkhông


      • -1
        Hechbros  commented on Jan. 13, 2025, 12:31 p.m.

        ầy mấy tk cha cày top thôi mỗi tội có elo r mà làm cái trò hơi bẩn tí hôm đó tôi cay chửi có elo học lập trình thi đấu thì biết THAM KHẢO thôi chứ ai làm z


    • 0
      khoangvan46  commented on Dec. 26, 2024, 6:53 a.m.

      con chó nào chép bài bạn vậy


      • 0
        Hechbros  commented on Jan. 13, 2025, 12:33 p.m.

        :) best submission 3 anh bạn trên tôi nha copy còn bẩn tính bài đặt bài mình làm nào là đẩy hết lên 1 dòng nào là đẩy vài lệnh lên 1 dòng r thêm #pragma


        • -1
          khoangvan46  commented on Jan. 31, 2025, 5:08 p.m.

          thôi kệ nó đi bro, quan trọng là nó ko được tí kiến thức gì từ bài tập cả =)))


  • 3
    kc017  commented on Nov. 29, 2024, 8:34 a.m.

    bài này lúc nhập vào kiểm tra xem số nào chẵn thì ném qua 1 vt (hoặc lẻ qua 1 vt), rồi làm 1 mảng đánh dấu, số nào có xuất hiện thì cho = 1, chạy từng phần tử trong vt, ở mỗi pt thì lấy tmp = k-a[i], kiểm tra xem check[tmp] = 1 thì in 1, break, nếu chạy hết mà k có thì in 0, mỗi vòng t nhớ rs các mảng. tối ưu hơn là dùng tìm kiếm nhị phân


    • -1
      dmnguyel23  commented on Jan. 6, 2025, 3:51 a.m.

      Check nếu k chẵn , thì thêm vào 0 luôn ( au av là chẵn lẻ nên tổng lẻ ) còn không sort mảng a, dùng hai con trỏ đầu cuối để tìm a[l] + a[r] == kk


  • -7
    anhtuancabun  commented on July 9, 2024, 4:47 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


  • 1
    daotrungkiena1k46  commented on June 13, 2024, 12:32 p.m.

    sao đề Hải Phòng 2023 dễ v


  • -4
    khanhnon  commented on March 22, 2024, 9:08 a.m.

    ủa sao 5e6 map tle :vvv


    • -4
      hieuhfgr  commented on March 22, 2024, 12:17 p.m.

      hetcuu


  • -7
    hmkhanh472010  commented on Jan. 25, 2024, 12:51 p.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


  • 3
    eya  commented on Jan. 4, 2024, 11:03 a.m.

    Bài này dùng tìm kiếm nhị phân code: https://ideone.com/ROQOal


    • -5
      phamdinhtuananh  commented on Feb. 7, 2024, 5:57 a.m. ← edited

      This comment is hidden due to too much negative feedback. Show it anyway.


      • -6
        nhanhtq2023  commented on Feb. 27, 2024, 12:19 p.m. ← edited

        This comment is hidden due to too much negative feedback. Show it anyway.


      • -3
        Phuong2008  commented on Feb. 14, 2024, 7:53 a.m.

        cũng chưa chắc, đồng ý là một chẵn một lẻ không thể cộng thành số chẵn được nhưng cũng không phải k lẻ là chắc chắn tìm dc. giả sử cái dãy n phần tử toàn những phần tử nhỏ hơn 10 nhưng k lại đến 1e9+7 chẳng hạn. thế thì chắc chắn là cách if else sai rồi


      • -3
        phamvuhoang486  commented on Feb. 14, 2024, 7:50 a.m.

        Ơ nếu trường k là số lẻ nhưng ko tìm thấy 2 cặp (u,v) thì phải in ra 0 đúng không


        • 0
          thienquynh  commented on Feb. 15, 2024, 2:38 p.m.

          Tui làm if else giống bạn kia mà ac rồi =))