μΌ | μ | ν | μ | λͺ© | κΈ | ν |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 |
- SQL
- λ°±μ€
- μλ£κ΅¬μ‘°
- κ·Έλνμνλ¬Έμ
- μμνμ
- BFS
- μ λ ¬
- λ³ν©μ λ ¬
- νλ‘μ΄λμμ¬
- κΉμ΄μ°μ νμ
- κ·Έλννμ
- λ°μ΄ν°λ² μ΄μ€
- λλΉμ°μ νμ
- ꡬν
- LIS
- νλ‘κ·Έλλ¨Έμ€
- db
- λ€μ΄λλ―Ήνλ‘κ·Έλλ°
- DP
- μ°μ μμν
- μμꡬνκΈ°
- λ¨Έμ§μνΈ
- 11650
- Side Menu
- 그리λ
- λμ κ³νλ²
- DFS
- μκ³ λ¦¬μ¦
- μν
- κ·Έλν
λͺ©λ‘ꡬν (4)
πππ°πΈ π£πΆπ΅ π΄π΅π¦π’π₯πΊ
λ¬Έμ β³β³ κ²μλνκ° κ°μ΅λμμ΅λλ€. μ΄ λνλ Nλͺ μ΄ μ°Έκ°νκ³ , ν λλ¨ΌνΈ νμμΌλ‘ μ§νλ©λλ€. Nλͺ μ μ°Έκ°μλ κ°κ° 1λΆν° Nλ²μ μ°¨λ‘λλ‘ λ°°μ λ°μ΅λλ€. κ·Έλ¦¬κ³ , 1λ²↔2λ², 3λ²↔4λ², ... , N-1λ²↔Nλ²μ μ°Έκ°μλΌλ¦¬ κ²μμ μ§νν©λλ€. κ° κ²μμμ μ΄κΈ΄ μ¬λμ λ€μ λΌμ΄λμ μ§μΆν μ μμ΅λλ€. μ΄λ, λ€μ λΌμ΄λμ μ§μΆν μ°Έκ°μμ λ²νΈλ λ€μ 1λ²λΆν° N/2λ²μ μ°¨λ‘λλ‘ λ°°μ λ°μ΅λλ€. λ§μ½ 1λ²↔2λ² λΌλ¦¬ 겨루λ κ²μμμ 2λ²μ΄ μΉλ¦¬νλ€λ©΄ λ€μ λΌμ΄λμμ 1λ²μ λΆμ¬λ°κ³ , 3λ²↔4λ²μμ 겨루λ κ²μμμ 3λ²μ΄ μΉλ¦¬νλ€λ©΄ λ€μ λΌμ΄λμμ 2λ²μ λΆμ¬λ°κ² λ©λλ€. κ²μμ μ΅μ’ ν λͺ μ΄ λ¨μ λκΉμ§ μ§νλ©λλ€. μ΄λ, μ²μ λΌμ΄λμμ Aλ²μ κ°μ§ μ°Έκ°μλ κ²½μμλ‘ μκ°νλ Bλ² μ°Έκ°μμ λͺ λ²μ§Έ ..
λ¬Έμ μ’ννλ©΄μ μ’μνλ μ§μλ xμΆκ³Ό yμΆμ΄ μ§κ΅νλ 2μ°¨μ μ’ννλ©΄μ μ μ μ°μΌλ©΄μ λκ³ μμ΅λλ€. μ§μλ λ μμ μ μ k, dκ° μ£Όμ΄μ§ λ λ€μκ³Ό κ°μ΄ μ μ μ°μΌλ € ν©λλ€. μμ (0, 0)μΌλ‘λΆν° xμΆ λ°©ν₯μΌλ‘ a*k(a = 0, 1, 2, 3 ...), yμΆ λ°©ν₯μΌλ‘ b*k(b = 0, 1, 2, 3 ...)λ§νΌ λ¨μ΄μ§ μμΉμ μ μ μ°μ΅λλ€. μμ κ³Ό κ±°λ¦¬κ° dλ₯Ό λλ μμΉμλ μ μ μ°μ§ μμ΅λλ€. μλ₯Ό λ€μ΄, kκ° 2, dκ° 4μΈ κ²½μ°μλ (0, 0), (0, 2), (0, 4), (2, 0), (2, 2), (4, 0) μμΉμ μ μ μ°μ΄ μ΄ 6κ°μ μ μ μ°μ΅λλ€. μ μ kμ μμ κ³Όμ 거리λ₯Ό λνλ΄λ μ μ dκ° μ£Όμ΄μ‘μ λ, μ μ΄ μ΄ λͺ κ° μ°νλμ§ return νλ solution ν¨μλ₯Ό μμ±..
λ¬Έμ μκ·Ό(Albert), λ―Όν(Barbara), μ μ(Casper), μ°½μ(Dinko), νμ§(Eustahije)μ΄κ° λ§λΌν€ ν±νν κ²μμ νλ €κ³ νλ€. μ΄ κ²μμ N×N 보λμμ μ§ννλ€. 맨 μ²μμ 보λμ λͺ¨λ μΉΈμ λΉμ΄μλ€. νλ μ΄μ΄λ ν΄μ λ²κ°μκ°λ©΄μ μμ μ μμ΄ μ΄λ¦μ 첫 κΈμλ₯Ό λΉ μΉΈμ μ λλ€. (λ μ¬λμ μμ΄ μ΄λ¦μ 첫 κΈμκ° κ°μ κ²½μ°λ μλ€) κ²μμ μΈ κΈμκ° ν, μ΄, λλ λκ°μ μΌλ‘ μ°μν λ, κ·Έ νλ μ΄μ΄κ° μΉλ¦¬νλ©°, κ²μμ΄ λλκ² λλ€. 보λνμ μνκ° μ£Όμ΄μ‘μ λ, κ²μμ΄ λλ¬λμ§ μλμ§λ₯Ό κ²°μ νκ³ , λλ¬λ€λ©΄ μΉμκ° λꡬμΈμ§ ꡬνλ νλ‘κ·Έλ¨μ μμ±νμμ€. μ λ ₯ 첫째 μ€μ 보λνμ ν¬κΈ° Nμ΄ μ£Όμ΄μ§λ€. (1 ≤ N ≤ 30) λ€μ Nκ° μ€μλ 보λνμ μνκ° μ£Όμ΄μ§λ€. '.'λ..
λ¬Έμ μλνΌμ μμ£Ό μ§μ μμ Nκ°μ νΌμ λ°μ£½μ μ€λΈμ λ£κ³ ꡬμ°λ €κ³ νλ€. κ·Έλ°λ°, μλνΌμμμ λ§λλ νΌμ λ°μ£½μ μ§λ¦μ΄ μ κ°κ°μ΄λ€. κ·Έλ°κ°νλ©΄, μλνΌμμμ μ¬μ©νλ μ€λΈμ λͺ¨μλ λͺΉμ μ€λ¬νλ€. μ΄ μ€λΈμ κΉμ κ΄μ²λΌ μκ²Όλλ°, κ΄μ μ§λ¦μ΄ κΉμ΄μ λ°λΌ λ€μλ μνκ² λ³νλ€. μλλ μ€λΈμ λ¨λ©΄ μμμ΄λ€. νΌμ λ°μ£½μ μμ±λλ μμλλ‘ μ€λΈμ λ€μ΄κ°λ€. μ΄λ κ² Nκ°μ νΌμκ° μ€λΈμ λͺ¨λ λ€μ΄κ°κ³ λλ©΄, 맨 μμ νΌμκ° μΌλ§λ κΉμ΄ λ€μ΄κ° μλμ§κ° κΆκΈνλ€. μ΄λ₯Ό μμλ΄λ νλ‘κ·Έλ¨μ μμ±νμμ€. μ λ ₯ 첫째 μ€μ μ€λΈμ κΉμ΄ Dμ νΌμ λ°μ£½μ κ°μ Nμ΄ κ³΅λ°±μ μ¬μ΄μ λκ³ μ£Όμ΄μ§λ€. (1 ≤ D, N ≤ 300,000) λμ§Έ μ€μλ μ€λΈμ μ΅μλ¨λΆν° μμνμ¬ κΉμ΄μ λ°λ₯Έ μ€λΈμ μ§λ¦μ΄ μ°¨λ‘λλ‘ μ£Όμ΄μ§λ€..