1th Programming Contest in CAUCSE
1ν μ€μλνκ΅ μ»΄ν¨ν°κ³΅νκ³Ό νλ‘κ·Έλλ° κ²½μ§ λνμ λν μλ£.
1. μλ΄ ¶
- μκ°: 2002λ
10μ 26μΌ 9:30 -- 12:30
- μ₯μ: 7μΈ΅ PCμ€
- ν ꡬμ±: 2-3μΈ / ν λΉ PC νλ
- μ¬μ©μΈμ΄: C/C++ with Visual C++ 6.0
- λ¬Έμ μ±κ²©: κ΅λ΄ λνμ νλ‘κ·Έλ¨ κ²½μ§ λνμ λ¬Έμ μΆμ κ²½ν₯μ λ°λ₯Έλ€. 2002λ
λ λ¬Έμ μν( http://cs.kaist.ac.kr/~acmicpc/problem.html see also 2002λ
λACMλ¬Έμ μννμ΄ μ°Έμ‘°)
- κ²½μ μ£Όμμ¬ν:
- νμμ΄ μλ μ¬λκ³Ό λν κΈμ§
- ν΄λν°, μΈν°λ· μ¬μ© κΈμ§
- κ°μΈ λμ€μΌ, CD λ± ν΄λ κΈμ§. λμ€μΌμ λλ μ€ κ²λ§ μ¬μ©.
- νμμ΄ μλ μ¬λκ³Ό λν κΈμ§
- μ±μ κΈ°μ€:
- κ²½μ 3μκ°μ 3λ¬Έμ κ° μΆμ λλ€. (open book, closed internet)
- νμ ν λ¬Έμ μ λν΄ μμ€μ½λκ° μμ±λλ©΄ λμ€μΌμ λ΄μ μ±μ νμ μ μΆνλ€.
- μ±μ μ κ·Έ μμ€μ½λλ₯Ό μ»΄νμΌν΄μ μννμΌμ λ§λ€μ΄ μ±μ νλ€.
- κ·Έ λ¬Έμ μ λν΄μ μ€λΉλ ν
μ€νΈ λ°μ΄ν( λ³΄ν΅ 5-10κ°)μ λν΄μ λͺ¨λ λ§λ λ΅μ λ΄μΌ κ·Έ λ¬Έμ λ₯Ό λ§μΆ κ²μΌλ‘ νλ€.
- νλ‘κ·Έλ¨μ μ€νμκ°μ΄ μΌμ μκ°(μ: 10μ΄)μ μ§λλ λλμ§ μμ κ²½μ° νλ¦° λ¬Έμ κ° λ©λλ€.
- μ»΄νμΌ error, μ€ν μκ° error , μΆλ ₯ ν¬λ§·μ΄ λ¬Έμ μμ μ ν κ²κ³Ό λ€λ₯Έ κ²½μ°μλ νλ¦Ό.
- μ μΆν λ΅μμ΄ νλ Έμ κ²½μ°, λ§€λ² μΌμ ν penalty μ μ (10μ )λ₯Ό λ°κ² λλ€.
- νλ¦° λ¬Έμ λ λ€μ μ μΆν μ μλ€.
- λ§μΆ λ¬Έμ μ λν΄μλ κ²½μ μμλΆν° λ¬Έμ λ₯Ό μ μΆν μκ°κΉμ§ μκ°μ λΆμΌλ‘ νμ°ν κ²μ΄ μ μλ‘ μ£Όμ΄μ§λ€. (λ°λΌμ μ μκ° μ μμλ‘ μ 리) κ·Έλ¦¬κ³ μ¬κΈ°μ penalty μ μλ₯Ό ν©μ°ν κ²μ΄ κ·Έ λ¬Έμ μ μ΅μ’
μ μκ° λλ€. μλ₯Ό λ€μ΄, μ΄λ€ ν λ¬Έμ μ λν΄μ λ€μ― λ²μ§Έ μ μΆμ μμν 1μκ° 20λΆμ νμ¬ λ§μΆλ©΄, μ§λκ° μκ°μ΄ 80λΆμ΄λ―λ‘ 80μ , λ€ λ²μ§ΈκΉμ§λ νλ ΈμΌλ―λ‘ 4λ²*10μ =40μ μ΄ penalty, μ΅μ’
μ μλ 120μ μ΄ λλ€.
- κ²½μ νμλ λͺ» λ§μΆ λ¬Έμ λ μ μκ° μλ€.
- κ° νμ μ΅μ’
μ±μ μ λ§μΆ λ¬Έμ μμ μ μ ν©μ΄ λλ€.
- μμλ λ§μΆ λ¬Έμ μ μκ° λ§μμλ‘ μμ, κ°μ μμ λ¬Έμ λ₯Ό νλ©΄ 빨리 νΌ ν (μ¦, μ μ ν©μ΄ μ μ ν)μ΄ μμμ μ 리ν©λλ€.
- κ²½μ 3μκ°μ 3λ¬Έμ κ° μΆμ λλ€. (open book, closed internet)
- νλ‘κ·Έλ¨ μμ±μ μ μ μ¬ν:
- κ° λ¬Έμ λ λ°μ΄ν°λ₯Ό μΈλΆμμ μ
λ ₯λ°μμ νλ‘κ·Έλ¨μΌλ‘ λ΅μ κ³μ°ν ν λ°λμ μΆλ ₯μ νλ€. μ΄λ, μ
μΆλ ₯μ νμ€μ
μΆλ ₯λ§ μ¬μ©νλ€. νμΌ μ
μΆλ ₯λ¬Έμ μ°λ©΄ μλ¨.
μ:
C
~cpp scanf ( "%d", &n ); // νμ€ μ λ ₯ λΆλΆ printf ( "I got %d\n", n ); // νμ€ μΆλ ₯ λΆλΆ
C++
~cpp cin >> n; // νμ€ μ λ ₯ λΆλΆ cout << "I got " << n << endl; // νμ€ μΆλ ₯ λΆλΆ
- νμ μλ μ
μΆλ ₯μ νλ©΄ νλ¦° κ²μΌλ‘ μ±μ .
- νμ μλ νμΌμ μμ±νκ±°λ, νμ€μ
λ ₯μ νμ§ μκ³ νμΌ μ
λ ₯μ νλ©΄ μμ νλ¦Ό.
- μ±μ μ μκΈ° μ»΄ν¨ν°μμ νλ κ²μ΄ μλλΌ, μ±μ νμ μ»΄ν¨ν°μμ μ€ννλ€. μ΄μ μ μ μν κ². μ¦, μκΈ° μ»΄ν¨ν°μλ§ μλ νΉμν κΈ°λ₯μ μ¬μ©νκ² λλ©΄, μ±μ ν μ»΄ν¨ν°μμλ μ λμ κ° μ μμ.
- μ±μ νμ μ±μ μ νμν λ°μ΄ν°λ₯Ό νμΌλ‘ λ§λ€μ΄μ κ°μ§κ³ μλ€κ° μ΄λ₯Ό νμμ μννμΌμ νμΌ redirectλ₯Ό ν΅νμ¬ μννμΌμ μ
λ ₯μν¨λ€.
- λͺ¨λ λ¬Έμ λ μ«μ, μμ΄ λ¬Έμλ€μ μ
λ ₯μΌλ‘ λ°μμ, μμ μ«μλ μμ΄ λ¬Έμλ₯Ό μΆλ ₯νλλ‘ λμ΄ μλ€. κ·Έλν½ μΆλ ₯μ μμ.
- κ° λ¬Έμ λ λ°μ΄ν°λ₯Ό μΈλΆμμ μ
λ ₯λ°μμ νλ‘κ·Έλ¨μΌλ‘ λ΅μ κ³μ°ν ν λ°λμ μΆλ ₯μ νλ€. μ΄λ, μ
μΆλ ₯μ νμ€μ
μΆλ ₯λ§ μ¬μ©νλ€. νμΌ μ
μΆλ ₯λ¬Έμ μ°λ©΄ μλ¨.
2. λ¬Έμ ¶
- 1thPCinCAUCSE/ProblemA - Aλ² λ¬Έμ "μκ³"
- 1thPCinCAUCSE/ProblemB - Bλ² λ¬Έμ "μ«μ μ
λ ₯"
- 1thPCinCAUCSE/ProblemC - Cλ² λ¬Έμ "μκΉ λ°κΎΈκΈ°"
3. λ¬Έμ νμ΄ ¶
- μλ λ§ν¬λ₯Ό ν΄λ¦νμ¬ μμ μ λ¬Έμ νμ΄λ₯Ό μ¬λ¦¬λ©΄ λ©λλ€. μμ μ μ΄λ¦μ λ°ν μ£ΌμΈμ~
- 1thPCinCAUCSE/ProblemA/Solution
- 1thPCinCAUCSE/ProblemB/Solution
- 1thPCinCAUCSE/ProblemC/Solution
4. λν μ체μ λν΄ ¶
μ΄ λνλ₯Ό νκ³ , λμ μ μλ₯Ό λ°μ νμ μμ€ μ½λλ₯Ό 곡κ°νκ³ λͺ κ°μ§ "νμ μμ
"(μ컨λ κ° νμ νκ³ λ₯Ό ν¬ν¨, λνμ λν λ€νλ¨ΌνΈ μν€ λ¬ΈμλΌλ κ°)μ ν΄μ£Όλ©΄ μμ£Ό λ§μ κ²μ λ°°μ°κ² λ리 λΌ μκ°ν©λλ€.
μμ¬μ΄ μ μ΄λΌλ©΄, κ΅λ΄ λνμ νλ‘κ·Έλ¨ κ²½μ§ λνμ acmμ icpcλ₯Ό λͺ¨λΈλ‘ νλ λ― νλ°, κ·Έλ λ€λ©΄ μ¬μ©μΈμ΄μ νλ«νΌ μμ μ’ μ νμ ν μ λκ² ν΄μ£Όλ κ² μ’μ§ μμκΉ νκ΅°μ.
μ΄μ κΉμ§ μ κ° λ΄μ¨ λνμ μμ€μ κ²½μ§λν μ€μμ κ°λ°νκ²½κ³Ό μΈμ΄ λͺ¨λ λ₯Ό μ΄λ κ² νμ ν κ²½μ°λ, νΉμ νμ¬μμ μ€ν°μλ₯Ό νλ κ²½μ° λΉΌκ³ λ λ³Έ μ μ΄ μμ΅λλ€. (μ΅κ·Ό μ 보μ²λ¦¬ μκ²©μ¦ μ€κΈ° μνμμλ λͺ¨λ μΈμ΄λ₯Ό νμ©νλλ‘ λ°λμλ€κ³ ν©λλ€) λ λ§μ λ°°μμ κΈ°νκ° λ κ²μΈλ° μ°Έ μμ½κ΅°μ.
λ¬Όλ‘ Cλ C++μ μ¬μ©ν΄μΌλ§ νλ μν© μμ²΄κ° νλμ κ³Όμ μν©μ΄ λκ³ λλΆμ μ¬λ¬κ°μ§ 곡λΆκ° λκΈ΄ νκ² μ§λ§, μ°λ¦¬λ "μ C/C++ λ°μ μ¬μ©ν μ μλλ"λ μ‘°κΈ λ λ³Έμ§μ μΈ μ§λ¬Έμ ν΄λ΄μΌ ν©λλ€. νΉν νκ³Ό λΆμκΈ°κ° C/C++ μͺ½μΌλ‘ νΈμ€λμ΄ μλ μν©μμλ λ§μ΄μ£ .
νΉμλ μ΄λ° λ§μ ν κ²λλ€. "μ¬νμ λκ°μ μΌνλ€ λ³΄λ©΄ μκΈ°κ° μνλ νκ²½μμ μΌν μ μλ μν©μ΄ μλ μμ΄ λ§λ€. κ°μ΄ κΉλΌλ©΄ κΉλκ±°κ±°λ ." νμ§λ§ μ΄λ° μν©μ νκ΅μκΉμ§ μ°κ²°ν νμλ μμ΄ λ³΄μ
λλ€. μ°λ¦¬λ "κ΅μ‘"κ³Ό "νλ¬Έ"μ΄λ κ±Έ νλ κ²μ΄λκΉ μ.
λ μ΄μ¨λ C/C++ λ°μ μλλ€λ©΄ λ λλ¦λλ‘ μ₯μ μΌλ‘ λλ € μκ°νκ³ μ΄μ¬ν μ€λΉνλ κ²λ μλ―Έμκ² μ΅λλ€. μ΄λ° λνκ° μ΄λ Έλ€λ μμ²΄κ° κ·μ€ν κ²μ΄λκΉμ. μμΌλ‘ μ κΈ°μ μΌλ‘ μ΄λ¦¬λ©΄ νμλ€μκ² λ§μ λκΈ°λΆμ¬κ° λκ² μ΅λλ€.
νΉμ μ¬λ¬κ°μ§ μΈμ΄λ₯Ό μμ©νλ κ²½μ§λνκ° κΆκΈν μ¬λμ ICFP νλ‘κ·Έλλ° κ²½μ§ λν(http://icfpcontest.cse.ogi.edu/ )λ₯Ό νλ² λλ¬λ³΄μκΈ° λ°λλλ€. λμ΄ ν λ¨μΌ κ²λλ€. νΉν μ¬ν΄ μ£Όμ λ λ‘λ΄ νλ‘κ·Έλλ°μ
λλ€. λ¬΄μ² ν₯λ―Έλ‘μ΄ μ£Όμ μ§μ.
μ μκ°μλ κ²½μ§λν λ¬Έμ μνμμ κ° κΊΌλΈλ―ν(μ½κ°μ μ²νΈμΌλ₯ μ μΈ) λ¬Έμ λ€ μΈμλ νμλ€μ΄ μ’μν λ§ν νλ‘κ·Έ λλ° μ£Όμ κ° λ§μλ°, κ·Έλ° κ²λ€λ μλν΄ λ³΄λ©΄ μ΄λ¨κΉ ν©λλ€.
μν κ²½μ§ λν건, νλ‘κ·Έλλ° κ²½μ§ λν건 κ·Έκ±Έ μ€λΉνλ μ¬λλ€μ λ§€μΌ λΉμ·λΉμ·ν μ νμ λ¬Έμ λ€λ§ "μ΅λ¨μκ°λ΄μ" νμ΄μ λΌλ νλ ¨μ νκ³ , λλΆμ μ΄λ€ ν΄λ΅ μ§ν©μ 미리 μΈμ°κ³ μ μ΅λλ€. μκ³ λ¦¬μ¦ Xνλ©΄ λ°λ‘ 무μμμ μΌλ‘ μ λμμ ν΄λΉ μκ³ λ¦¬μ¦μ ꡬνν λͺ¨λ² λ΅μμ΄ νμ΄λμ€κ² μμ μ΄ νλ‘κ·Έλ¨ λμ΄ μμ£ . λ€ μ’μ΅λλ€λ§, λͺ¨λ μ¬λμ΄ κ·Έλ κ² νλ ¨λ°μ νμλ μμ§ μμκΉμ?
μ λ μμ΄κ³΅λΆλ₯Ό νλ μ¬λμκ² μ΄λ° λ§μ ν΄μ€λλ€. μμ΄κ³΅λΆλ₯Ό νλ €κ³ μμλ₯Ό κ³ λ₯Ό λμλ μΌλ¨ κ·Έ μ±
μ ν΅ν μμ΄κ³΅λΆμ μ΄λμ 무μνκ³ κ³ λ €λ₯Ό ν΄λ μ¬μ ν κ·Έ μ±
μ μ½μ λ§μμ΄ λλ, μ€μ¬ κ·Έ μ±
μ΄ κ΅μ΄λ‘ λμ΄ μλ€κ³ ν΄λ μ¬μ ν κ·Έ μ±
μ μ½μ λ§μμ΄ λλ κ·Έλ° μ±
μ 보λΌκ³ λ§μ
λλ€.
μ λ μΌλ¨μ νμλ€μ΄ κ·Έ μ£Όμ μμ²΄κ° λ§€λ ₯μ μ΄μ΄μ μ λ§ μ°Έμ¬ ν΄λ³΄κ³ μΆμ μκ°μ΄ λ§κ΅¬ λλ κ²½μ°κ° μ΄μμ μ΄λΌκ³ λ΄
λλ€. κΌ μ§μ λμ μ μ’μνλ μ¬λλ€λ§μ΄ μλμ§λΌλ "μΌ, μ κ±° νλ² ν΄λ³΄λ©΄ μ°Έ μ¬λ―Έμκ² λ€" κ·Έλ° μκ°μ΄ λλ κ² λ§μ΄μ£ . κ·Έλ¦¬κ³ κ±°κΈ°μμ κ°μμ μμ€μ λ§κ² μ λ§λ€ 무μΈκ° λ°°μ°κ³ μ»μ μ μλ€λ©΄ λ μ’κ² μ£ .
κ³Ό νμλ€λΌλ¦¬ μ΄λ° λνλ₯Ό μ£Όμ΅ν΄ 보λ 건 μ΄λ¨κΉ ν©λλ€. κΌ ICPC μ€νμΌμ λ΅μ΅ν νμλ μκ² μ£ .
--JuNe
5. μ λ΅ ¶
C/C++(VC++6.0)λ§ μ¬μ©ν μ μλ μν©μμλ STLμ μ¬μ©νλ μνλκ° μμ²λ μ°¨μ΄λ₯Ό λΆλ¬μ¬ κ²μ΄λΌ μκ°νλ€. κ·Έλ¦¬κ³ νμ΄ λλͺ
μ΄λ μΈλͺ
μ΄λλ μ€μνκΈ΄ ν ν°μΈλ°, μ΄λ»κ² μ‘°μ§μ μΌλ‘ μ νμ©νλλμ λ°λΌ μ°¨μ΄κ° μκΈ°λ νκ³ λ³λ‘ μκΈ°λ ν κ²μ΄λ€. λν μκ° ν
μ€νΈλ₯Ό ν΅ν΄ μ΄λ μ λ κ²μ¦λ νλ‘κ·Έλ¨λ§ μ μΆμ ν μ μλ€λ©΄ νλν°λ₯Ό μ€μΌ μ μκΈ° λλ¬Έμ ν¨μ¬ μ 리ν κ²μ΄λ€.
λν λͺ¨λ λ¬Έμ μ λν΄ μΆμ μκ° μμνλ ν΄λ΅μ΄ μμ κ²μ΄κ³ , μ¬λ°λ₯΄κ² μλμ νμ§λ§ μνμκ°μ΄ ν¨μ¬ λ 걸리λ(μκ³ λ¦¬μ¦μ μ»΄νλ μν°κ° ν¨μ¬ λμ) λ΅μμ΄ μμ ν°μΈλ°, "μΌμ μκ°" λ΄μ μνμ΄ μλ£λ μ μλ€λ©΄ λ λ¨μν λ΅μμ κ³ λ₯Ό μ μλ λ₯λ ₯λ μμ£Ό μ€μν κ²μ΄λ€. μ컨λ, μ΄λ² λνμ μμ λ¬Έμ Bλ²(http://cs.kaist.ac.kr/~acmicpc/B_word.pdf ) κ²½μ°, (μλ§λ) μΆμ μκ° μμνλ λ΅μμ μ€ν μκ°μ΄λ, νΉμ κ·Έλ μ§λ μμ§λ§(κ½€ 무μν λ°©λ²μ μ°μ§λ§) μ¬λ°λ₯΄κ² μλνλ λ΅μμ μ€ν μκ°μ΄λ λͺ¨λ 1μ΄ μ΄λ΄μ΄λ€. νμμ λ°©λ²μ μκ°ν΄ λ΄κ³ , νλ‘κ·Έλ¨ νλ λ°μλ λ³΄ν΅ μ μ°νκ³Ό νμμ΄λΌλ©΄(κ·Έλ¦¬κ³ κ·Έκ° STL, νΉν Permutation Generatorλ₯Ό λ€λ£° μ μλ€λ©΄) 5λΆμ΄λ©΄ λ‘μ μΉκ³ λ λ¨λλ€.
--JuNe
See Also 컴곡과νλ‘κ·Έλλ°κ²½μ§λν