λͺ©λ‘μ 체 κΈ (1005)
π 곡λΆνλ μ§μ§μνμΉ΄λ μ²μμ΄μ§?
κ΅¬μ¬ νμΆμ μ§μ¬κ°ν 보λμ λΉ¨κ° κ΅¬μ¬κ³Ό νλ ꡬμ¬μ νλμ© λ£μ λ€μ, λΉ¨κ° κ΅¬μ¬μ ꡬλ©μ ν΅ν΄ λΉΌλ΄λ κ²μμ΄λ€. 보λμ μΈλ‘ ν¬κΈ°λ N, κ°λ‘ ν¬κΈ°λ Mμ΄κ³ , νΈμμ 1×1ν¬κΈ°μ μΉΈμΌλ‘ λλμ΄μ Έ μλ€. κ°μ₯ λ°κΉ₯ νκ³Ό μ΄μ λͺ¨λ λ§νμ Έ μκ³ , 보λμλ ꡬλ©μ΄ νλ μλ€. λΉ¨κ° κ΅¬μ¬κ³Ό νλ ꡬμ¬μ ν¬κΈ°λ 보λμμ 1×1ν¬κΈ°μ μΉΈμ κ°λ μ±μ°λ μ¬μ΄μ¦μ΄κ³ κ°κ° νλμ© λ€μ΄κ° μλ€. κ²μμ λͺ©νλ λΉ¨κ° κ΅¬μ¬μ ꡬλ©μ ν΅ν΄μ λΉΌλ΄λ κ²μ΄λ€. μ΄λ, νλ ꡬμ¬μ΄ ꡬλ©μ λ€μ΄κ°λ©΄ μ λλ€. μ΄λ, ꡬμ¬μ μμΌλ‘ 건λ릴 μλ μκ³ , μ€λ ₯μ μ΄μ©ν΄μ μ΄λ¦¬ μ 리 κ΅΄λ €μΌ νλ€. μΌμͺ½μΌλ‘ κΈ°μΈμ΄κΈ°, μ€λ₯Έμͺ½μΌλ‘ κΈ°μΈμ΄κΈ°, μμͺ½μΌλ‘ κΈ°μΈμ΄κΈ°, μλμͺ½μΌλ‘ κΈ°μΈμ΄κΈ°μ κ°μ λ€ κ°μ§ λμ κ°κ°μ λμμμ 곡μ λμμ μμ§μΈλ€. ..
μ€λμ μ€ννΈλ§ν¬μ λ€λλ μ¬λλ€μ΄ λͺ¨μ¬μ μΆκ΅¬λ₯Ό ν΄λ³΄λ €κ³ νλ€. μΆκ΅¬λ νμΌ μ€νμ νκ³ μ무 μ°Έμλ μλλ€. μΆκ΅¬λ₯Ό νκΈ° μν΄ λͺ¨μΈ μ¬λμ μ΄ Nλͺ μ΄κ³ μ κΈ°νκ²λ Nμ μ§μμ΄λ€. μ΄μ N/2λͺ μΌλ‘ μ΄λ£¨μ΄μ§ μ€ννΈ νκ³Ό λ§ν¬ νμΌλ‘ μ¬λλ€μ λλ μΌ νλ€. BOJλ₯Ό μ΄μνλ νμ¬ λ΅κ² μ¬λμκ² λ²νΈλ₯Ό 1λΆν° NκΉμ§λ‘ λ°°μ νκ³ , λ₯λ ₯μΉλ₯Ό μ‘°μ¬νλ€. λ₯λ ₯μΉ Sijλ iλ² μ¬λκ³Ό jλ² μ¬λμ΄ κ°μ νμ μνμ λ, νμ λν΄μ§λ λ₯λ ₯μΉμ΄λ€. νμ λ₯λ ₯μΉλ νμ μν λͺ¨λ μμ λ₯λ ₯μΉ Sijμ ν©μ΄λ€. Sijλ Sjiμ λ€λ₯Ό μλ μμΌλ©°, iλ² μ¬λκ³Ό jλ² μ¬λμ΄ κ°μ νμ μνμ λ, νμ λν΄μ§λ λ₯λ ₯μΉλ Sijμ Sjiμ΄λ€. μΆκ΅¬λ₯Ό μ¬λ―Έμκ² νκΈ° μν΄μ μ€ννΈ νμ λ₯λ ₯μΉμ λ§ν¬ νμ λ₯λ ₯μΉμ μ°¨μ΄λ₯Ό μ΅μ..
Nκ°μ μλ‘ μ΄λ£¨μ΄μ§ μμ΄ A1, A2, ..., ANμ΄ μ£Όμ΄μ§λ€. μμ μ μ¬μ΄μ λΌμλ£μ μ μλ N-1κ°μ μ°μ°μκ° μ£Όμ΄μ§λ€. μ°μ°μλ λ§μ (+), λΊμ (-), κ³±μ (×), λλμ (÷)μΌλ‘λ§ μ΄λ£¨μ΄μ Έ μλ€. μμ μ μ¬μ΄μ μ°μ°μλ₯Ό νλμ© λ£μ΄μ, μμμ νλ λ§λ€ μ μλ€. μ΄λ, μ£Όμ΄μ§ μμ μμλ₯Ό λ°κΎΈλ©΄ μ λλ€. μλ₯Ό λ€μ΄, 6κ°μ μλ‘ μ΄λ£¨μ΄μ§ μμ΄μ΄ 1, 2, 3, 4, 5, 6μ΄κ³ , μ£Όμ΄μ§ μ°μ°μκ° λ§μ (+) 2κ°, λΊμ (-) 1κ°, κ³±μ (×) 1κ°, λλμ (÷) 1κ°μΈ κ²½μ°μλ μ΄ 60κ°μ§μ μμ λ§λ€ μ μλ€ μμ κ³μ°μ μ°μ°μ μ°μ μμλ₯Ό 무μνκ³ μμμλΆν° μ§νν΄μΌ νλ€. λλμ μ μ μ λλμ μΌλ‘ λͺ«λ§ μ·¨νλ€. μμλ₯Ό μμλ‘ λλ λλ μμλ‘ λ°κΎΌ λ€ λͺ«μ μ·¨νκ³ , κ·Έ λͺ«μ μμ..
μ€λλΆν° N+1μΌμ§Έ λλ λ ν΄μ¬λ₯Ό νκΈ° μν΄μ, λ¨μ NμΌ λμ μ΅λν λ§μ μλ΄μ νλ €κ³ νλ€. λ°±μ€μ΄λ λΉμμκ² μ΅λν λ§μ μλ΄μ μ‘μΌλΌκ³ λΆνμ νκ³ , λΉμλ ν루μ νλμ© μλ‘ λ€λ₯Έ μ¬λμ μλ΄μ μ‘μλμλ€. κ°κ°μ μλ΄μ μλ΄μ μλ£νλλ° κ±Έλ¦¬λ κΈ°κ° Tiμ μλ΄μ νμ λ λ°μ μ μλ κΈμ‘ Piλ‘ μ΄λ£¨μ΄μ Έ μλ€. N = 7μΈ κ²½μ°μ λ€μκ³Ό κ°μ μλ΄ μΌμ νλ₯Ό 보μ. 1μΌμ μ‘νμλ μλ΄μ μ΄ 3μΌμ΄ 걸리며, μλ΄νμ λ λ°μ μ μλ κΈμ‘μ 10μ΄λ€. 5μΌμ μ‘νμλ μλ΄μ μ΄ 2μΌμ΄ 걸리며, λ°μ μ μλ κΈμ‘μ 15μ΄λ€. μλ΄μ νλλ° νμν κΈ°κ°μ 1μΌλ³΄λ€ ν΄ μ μκΈ° λλ¬Έμ, λͺ¨λ μλ΄μ ν μλ μλ€. μλ₯Ό λ€μ΄μ 1μΌμ μλ΄μ νκ² λλ©΄, 2μΌ, 3μΌμ μλ μλ΄μ ν μ μκ²..
μ΄ Nκ°μ μνμ₯μ΄ μκ³ , κ°κ°μ μνμ₯λ§λ€ μμμλ€μ΄ μλ€. iλ² μνμ₯μ μλ μμμμ μλ Aλͺ μ΄λ€. κ°λ κ΄μ μ΄κ°λ κ΄κ³Ό λΆκ°λ κ΄μΌλ‘ λ μ’ λ₯κ° μλ€. μ΄κ°λ κ΄μ ν μνμ₯μμ κ°μν μ μλ μμμμ μκ° Bλͺ μ΄κ³ , λΆκ°λ κ΄μ ν μνμ₯μμ κ°μν μ μλ μμμμ μκ° Cλͺ κ°κ°μ μνμ₯μ μ΄κ°λ κ΄μ μ€μ§ 1λͺ λ§ μμ΄μΌ νκ³ , λΆκ°λ κ΄μ μ¬λ¬ λͺ μμ΄λ λλ€. κ° μνμ₯λ§λ€ μμμλ€μ λͺ¨λ κ°μν΄μΌ νλ€. μ΄λ, νμν κ°λ κ΄ μμ μ΅μκ°μ ꡬνλ νλ‘κ·Έλ¨μ μμ± μ²«μ§Έ μ€μ μνμ₯μ κ°μ N(1 ≤ N ≤ 1,000,000)μ΄ μ£Όμ΄μ§λ€. λμ§Έ μ€μλ κ° μνμ₯μ μλ μμμμ μ Ai (1 ≤ Ai ≤ 1,000,000)κ° μ£Όμ΄μ§λ€. μ μ§Έ μ€μλ Bμ Cκ° μ£Όμ΄μ§λ€. (1 ≤ B, C ≤ 1,0..
λ‘λ΄ μ²μκΈ°κ° μ£Όμ΄μ‘μ λ, μ²μνλ μμμ κ°μλ₯Ό ꡬνλ νλ‘κ·Έλ¨ λ‘λ΄ μ²μκΈ°κ° μλ μ₯μλ N×M ν¬κΈ°μ μ§μ¬κ°νμΌλ‘ λνλΌ μ μμΌλ©°, 1×1ν¬κΈ°μ μ μ¬κ°ν μΉΈμΌλ‘ λλμ΄μ Έ μλ€. κ°κ°μ μΉΈμ λ²½ λλ λΉ μΉΈμ΄λ€. μ²μκΈ°λ λ°λΌλ³΄λ λ°©ν₯μ΄ μμΌλ©°, μ΄ λ°©ν₯μ λ, μ, λ¨, λΆμ€ νλμ΄λ€. μ§λμ κ° μΉΈμ (r, c)λ‘ λνλΌ μ μκ³ , rμ λΆμͺ½μΌλ‘λΆν° λ¨μ΄μ§ μΉΈμ κ°μ, cλ μμͺ½μΌλ‘ λΆν° λ¨μ΄μ§ μΉΈμ κ°μ λ‘λ΄ μ²μκΈ°λ λ€μκ³Ό κ°μ΄ μλνλ€. 1. νμ¬ μμΉλ₯Ό μ²μνλ€. 2. νμ¬ μμΉμμ νμ¬ λ°©ν₯μ κΈ°μ€μΌλ‘ μΌμͺ½λ°©ν₯λΆν° μ°¨λ‘λλ‘ νμμ μ§ν μΌμͺ½ λ°©ν₯μ μμ§ μ²μνμ§ μμ 곡κ°μ΄ μ‘΄μ¬νλ€λ©΄, κ·Έ λ°©ν₯μΌλ‘ νμ ν λ€μ ν μΉΈμ μ μ§νκ³ 1λ²λΆν° μ§ν μΌμͺ½ λ°©ν₯μ μ²μν 곡κ°μ΄ μλ€λ©΄, κ·Έ λ°©..
μ§κ΅¬ μ¨λνλ‘ μΈνμ¬ λΆκ·Ήμ λΉμ°μ΄ λ Ήκ³ μλ€. λΉμ°μ 2μ°¨μ λ°°μ΄μ νμ λΉμ°μ κ° λΆλΆλ³ λμ΄ μ 보λ λ°°μ΄μ κ° μΉΈμ μμ μ μλ‘ μ μ₯ λΉμ° μ΄μΈμ λ°λ€μ ν΄λΉλλ μΉΈμλ 0μ΄ μ μ₯λλ€. λΉμΉΈμ λͺ¨λ 0μΌλ‘ μ±μμ Έ μλ€κ³ μκ°νλ€. λΉμ°μ λμ΄λ λ°λ·λ¬Όμ λ§μ΄ μ ν΄μλ λΆλΆμμ λ 빨리 μ€μ΄λ€κΈ° λλ¬Έμ, λ°°μ΄μμ λΉμ°μ κ° λΆλΆμ ν΄λΉλλ μΉΈμ μλ λμ΄λ μΌλ λ§λ€ κ·Έ μΉΈμ λμλ¨λΆ λ€ λ°©ν₯μΌλ‘ λΆμ΄μλ 0μ΄ μ μ₯λ μΉΈμ κ°μλ§νΌ μ€μ΄λ λ€. λ¨, κ° μΉΈμ μ μ₯λ λμ΄λ 0λ³΄λ€ λ μ€μ΄λ€μ§ μλλ€. λ°λ·λ¬Όμ νΈμμ²λΌ λΉμ°μ λλ¬μΈμ¬ μμ μλ μλ€. 2μ°¨μ λ°°μ΄μμ λμλ¨λΆ λ°©ν₯μΌλ‘ λΆμ΄μλ μΉΈλ€μ μλ‘ μ°κ²°λμ΄ μλ€κ³ λ§νλ€ ν λ©μ΄λ¦¬μ λΉμ°μ΄ μ£Όμ΄μ§ λ, μ΄ λΉμ°μ΄ λ λ©μ΄λ¦¬ μ΄μμΌλ‘ λΆλ¦¬λλ μ΅μ΄..
μ€λμ κ°νΈμ λ©΄μ λ μ΄λ€. λ¦μ μ μ κ°νΈλ μ€ννΈλ§ν¬κ° μλ 건물μ λ¦κ² λμ°©νκ³ λ§μλ€. μ€ννΈλ§ν¬λ μ΄ FμΈ΅μΌλ‘ μ΄λ£¨μ΄μ§ κ³ μΈ΅ 건물μ μ¬λ¬΄μ€μ΄ μκ³ , μ€ννΈλ§ν¬κ° μλ κ³³μ μμΉλ GμΈ΅μ΄λ€. κ°νΈκ° μ§κΈ μλ κ³³μ SμΈ΅μ΄κ³ , μ΄μ μλ¦¬λ² μ΄ν°λ₯Ό νκ³ GμΈ΅μΌλ‘ μ΄λνλ €κ³ νλ€. λ³΄ν΅ μλ¦¬λ² μ΄ν°μλ μ΄λ€ μΈ΅μΌλ‘ μ΄λν μ μλ λ²νΌμ΄ μμ§λ§, κ°νΈκ° ν μλ¦¬λ² μ΄ν°λ λ²νΌμ΄ 2κ°λ°μ μλ€. Uλ²νΌμ μλ‘ UμΈ΅μ κ°λ λ²νΌ, Dλ²νΌμ μλλ‘ DμΈ΅μ κ°λ λ²νΌμ΄λ€. (λ§μ½, UμΈ΅ μ, λλ DμΈ΅ μλμ ν΄λΉνλ μΈ΅μ΄ μμ λλ, μλ¦¬λ² μ΄ν°λ μμ§μ΄μ§ μλλ€) κ°νΈκ° GμΈ΅μ λμ°©νλ €λ©΄, λ²νΌμ μ μ΄λ λͺ λ² λλ¬μΌ νλμ§ κ΅¬νλ νλ‘κ·Έλ¨μ μμ± μλ¦¬λ² μ΄ν°λ₯Ό μ΄μ©ν΄μ GμΈ΅μ κ° μ μλ€λ©΄, "use the sta..