โจทย์ทั้งหมด
ปานกลาง 0 ข้อที่แก้แล้ว อัตราผ่าน 0%

คู่จำนวนห้าเหลี่ยม

นับคู่ของจำนวนห้าเหลี่ยมที่ผลบวกเป็นจำนวนห้าเหลี่ยมด้วย

สิ่งที่คุณจะได้เรียนรู้

  • สร้างจำนวนห้าเหลี่ยม
  • ตรวจสอบการเป็นสมาชิกด้วยสูตร
  • นับคู่ด้วยลูปซ้อนสองชั้น

โจทย์

จำนวนห้าเหลี่ยมคือ P(k) = k(3k − 1) / 2 ได้แก่ 1, 5, 12, 22, 35, 51, 70, ... บางคู่บวกกันแล้วได้จำนวนห้าเหลี่ยมอีกตัวหนึ่ง เช่น P(4) + P(7) = 22 + 70 = 92 = P(8) ให้นับคู่ j < k ≤ n ที่ P(j) + P(k) เป็นจำนวนห้าเหลี่ยม มีวิธีตรวจสอบที่รวดเร็วคือ x เป็นจำนวนห้าเหลี่ยมก็ต่อเมื่อ 24x + 1 เป็นกำลังสองสมบูรณ์ s² ที่ s % 6 = 5

จงเขียนฟังก์ชัน pentagonal_pair(n)

อินพุต

n: ดัชนี k ที่มากที่สุดที่ใช้

เอาต์พุต

คืนค่าจำนวนคู่ (j, k) ที่ 1 ≤ j < k ≤ n และ P(j) + P(k) เป็นจำนวนห้าเหลี่ยม

เงื่อนไข

1 ≤ n ≤ 1000

ตัวอย่าง

ตัวอย่างที่ 1
อินพุต:
n = 7

ผลลัพธ์ที่คาดหวัง:
expected = 1
อินพุต:
long long n = 7;

ผลลัพธ์ที่คาดหวัง:
long long expected = 1;
อินพุต:
long n = 7;

ผลลัพธ์ที่คาดหวัง:
long expected = 1;

คำอธิบาย

จาก 21 คู่ที่ k ไม่เกิน 7 มีเพียง P(4) + P(7) = 92 = P(8) ที่เป็นจำนวนห้าเหลี่ยม คำตอบจึงเป็น 1

ตัวอย่างที่ 2
อินพุต:
n = 1

ผลลัพธ์ที่คาดหวัง:
expected = 0
อินพุต:
long long n = 1;

ผลลัพธ์ที่คาดหวัง:
long long expected = 0;
อินพุต:
long n = 1;

ผลลัพธ์ที่คาดหวัง:
long expected = 0;

คำอธิบาย

ไม่มีคู่ใดที่ j < k ≤ 1 คำตอบจึงเป็น 0

แนวทางการแก้

ลองทำเองก่อน แล้วค่อยเปิดคำใบ้ทีละข้อ

คำใบ้ 1

P(k) = k(3k − 1) / 2

คำใบ้ 2

ตรวจว่า 24x + 1 เป็นกำลังสองสมบูรณ์ด้วยรากที่สองแบบจำนวนเต็ม แล้วตรวจรากนั้นด้วยมอดุโล 6

คำใบ้ 3

นับเฉพาะคู่ที่ j < k

ความซับซ้อนที่คาดหวัง

เวลา O(n²), หน่วยความจำเพิ่ม O(n)

แหล่งอ้างอิง

โจทย์นี้ปรับให้เหมาะกับ CodeUtility กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน

คำตอบที่ผ่านดีที่สุดของแต่ละคน คำตอบที่เร็วกว่า ใช้หน่วยความจำน้อยกว่า และได้คะแนนดีกว่าจะอยู่ด้านบน

ยังไม่มีคำตอบที่ผ่าน แก้โจทย์นี้แล้วคว้าอันดับหนึ่งไปเลย

เรียนรู้จากคนอื่น

แนวทางจากชุมชน

ยังไม่มีวิธีทำที่เผยแพร่ ลองแก้โจทย์นี้เพื่อแชร์วิธีแรก