Á¦ 16ȸ

Á¦ 16ȸ´Â 2004³â 9¿ù 11ÀϺÎÅÍ 18ÀϱîÁö ±×¸®½º ¾ÆÅ׳׿¡¼­ ¿­·È´Ù. °°Àº Àå¼Ò¿¡¼­ IOI°¡ ´Ù½Ã °³ÃֵDZâ´Â ±×¸®½º ¾ÆÅ׳װ¡ óÀ½ÀÌ´Ù(1991³â¿¡ ¿­¸° Á¦ 3ȸ). À̹ø ´ëȸ¿¡¼­ ¾²ÀÎ Çϵå¿þ¾î ȯ°æÀº ·¥ 512MB, 3GHzÀÎ ÆæƼ¾ö 4·Î, Çظ¶´Ù ¼º´ÉÀÌ Çâ»óµÇ°í ÀÖ´Ù. ÀÌÁ¦ rhide(ÅëÇÕ °³¹ß ȯ°æ)¿Í GCC¿Í Free Pascal ÄÄÆÄÀÏ·¯´Â IOI¿¡¼­ Çʼö µµ±¸·Î ÀÚ¸®ÀâÀº µí ÇÏ´Ù.

±×¸®½º ½ÅÈ­ ºÐÀ§±â¸¦ ¹°¾À dz±â´Â ¹®Á¦ ³»¿ëÀÌ ÀÌ»öÀûÀÌ´Ù. Ç®À̹ýÀ¸·Î ´ÙÀ̳ª¹ÍÀ» ÀÀ¿ëÇÑ ¹®Á¦µéÀÌ ÁÖ·ù¸¦ À̷糪 ²Ï ¾î·Á¿î °Íµµ ´«¿¡ ¶è´Ù. ƯÈ÷ 3¹ø ´Ù°¢Çü ºÐÇØ ¹®Á¦´Â º»µð NP-complete ¹®Á¦ÀÎ °ÍÀ» Ư¼öÇÑ ÀüÁ¦ Á¶°ÇÀ» ÁÖ¾î Á¦ÃâÇüÀ¸·Î ÃâÁ¦ÇÑ °ÍÀÌ´Ù. ¸ðµç °æ½Ã ¹®Á¦µéÀÌ Å×½ºÆ® ÄÉÀ̽º¸¦ Ǫ´Â Á¦ÇÑ ½Ã°£Àº 1ÃÊ¿´À¸¸ç, ¸Þ¸ð¸® Á¦ÇÑÀº 16MB¿¡, 4¹ø¸¸ 128MB¿´´Ù. Ãâ·Â Çü½ÄÀÌ ºñ±³Àû ´Ü¼øÇßÀ¸¸ç, ºÎºÐ Á¡¼ö ¾øÀÌ ¿©¼¸ ¹®Á¦ ¸ðµÎ ÃÖÀûÇظ¦ ±¸Çß´À³Ä ¸øÇß´À³ÄÀÇ ¿©ºÎ¿¡ µû¶ó äÁ¡µÇ¾ú´Ù.

ÀÔ·Â Å©±âÀÇ Á¦ÇÑ Á¶°Ç¿¡ ´Ü¼øÇÑ ÃÖ¾Ç »óȲÀÇ ÇÑ°è»Ó¸¸ ¾Æ´Ï¶ó, Àüü Å×½ºÆ® Áß Àý¹ÝÀÌ ¼ÓÇÏ´Â "¿Ï¸¸ÇÑ" ȯ°æ¿¡ ´ëÇؼ­µµ ¾ð±ÞÇÏ°í Àִµ¥, ÀÌ´Â ¹®Á¦¸¦ ¿ÏÀüÈ÷ Ç®Áö ¸øÇØ ºñÈ¿À²ÀûÀÎ ¾Ë°í¸®ÁòÀ» ¾²´õ¶óµµ, ÀÌ·± ȯ°æ¿¡ ´ëÇؼ­¶óµµ 1ÃÊ ¾È¿¡ ¿Ã¹Ù¸¥ ´äÀ» Ãâ·ÂÇÏ´Â ÇÁ·Î±×·¥À» ÃÖ¼±À» ´ÙÇØ ¸¸µé¾î º¸¶ó´Â ÁÖÃÖ ÃøÀÇ ¹è·Á·Î º¸ÀδÙ.

¿ì¸®³ª¶ó´Â À̹ø ´ëȸ¿¡¼­ ±Ý¸Þ´Þ Çϳª, Àº¸Þ´Þ µÑÀ» ȹµæÇØ ºñ°ø½Ä(±¹°¡º° ¼øÀ§¸¦ ÁÖÃÖÃø¿¡¼­ °ø½Ä Áý°èÇÏÁö´Â ¾Ê´Â´Ù) Á¾ÇÕ ¼øÀ§ 9À§¸¦ Â÷ÁöÇß´Ù. ¹®Á¦´ç 100Á¡¿¡ ÃÑ 600Á¡ ¸¸Á¡À¸·Î, ±Ý¸Þ´Þ ÀÔ»óÀÚÀÇ ÃÖ°í Á¡¼ö´Â 565Á¡, µ¿¸Þ´Þ ÀÔ»óÀÚÀÇ ÃÖÀú Á¡¼ö´Â 265Á¡À̾ú´Ù.

¿ø¹®ÀÌ ÀÖ´Â °÷: http://www.ioi2004.org/html/competition_test1.html

1. ¾Æ¸£Å׹̽º

2. Ç츣¸Þ½ºÀÇ ½ÉºÎ¸§

3. ´Ù°¢Çü ºÐÇØ (Á¦ÃâÇü)

4. ¿¥Æ÷µð¿À

5. ³óºÎ

6. Çǵð¾Æ½º


1. ¾Æ¸£Å׹̽º

Á¦¿ì½º´Â Ȳ¹«ÁöÀÇ ¿©½ÅÀÎ ¾Æ¸£Å׹̽º¿¡°Ô, ½£À» Á¶¼ºÇ϶ó°í Á÷»ç°¢Çü ¸ð¾çÀÇ ¶¥À» ÁÖ¾ú´Ù. ÀÌ Á÷»ç°¢ÇüÀÇ ¿ÞÂÊ¿¡ ÀÖ´Â ¼öÁ÷¼±À» yÃàÀ¸·Î, ¾Æ·¡¿¡ ÀÖ´Â ¼öÆò¼±À» xÃàÀ¸·Î Àâ°í, ¿ÞÂÊ ¾Æ·¡ ¸ð¼­¸®ÀÇ Á¡À» (0, 0)ÀÎ ¿øÁ¡À̶ó ÇÏÀÚ. Á¦¿ì½º´Â ¾Æ¸£Å׹̽º¿¡°Ô, ÀÌ ¿µ¿ª¿¡¼­ Á¤¼ö ÁÂÇ¥¿¡ ÇØ´çÇÏ´Â À§Ä¡¿¡¸¸ ³ª¹«¸¦ ½ÉÀ¸¶ó°í ºÐºÎÇß´Ù. ¾Æ¸£Å׹̽º´Â ½£ÀÌ ÀÚ¿¬½º·´°Ô º¸ÀÌ´Â °É ÁÁ¾ÆÇϱ⠶§¹®¿¡, ¾î¶² ³ª¹« µÎ ±×·çµµ xÃàÀ̳ª yÃà¿¡ ÆòÇàÇÑ °£°ÝÀ¸·Î ÀÖÁö ¾Ê°Ô ³ª¹«µéÀ» ¹èÄ¡Çß´Ù.

À̵û±Ý¾¿ Á¦¿ì½º´Â ¾Æ¸£Å׹̽º·Î ÇÏ¿©±Ý ³ª¹«¸¦ º£¾î ´Þ¶ó°í ¿äûÇϱ⵵ ÇÑ´Ù. ³ª¹«¸¦ º£´Â ±ÔÄ¢Àº ´ÙÀ½°ú °°´Ù.

  1. ÃÖ¼ÒÇÑ T ±×·ç ÀÌ»óÀÇ ³ª¹«¸¦ º£¾î¾ß ÇÑ´Ù.
  2. ½£ ¾È¿¡ ÀÏÁ¤ÇÑ Á÷»ç°¢Çü ±¸¿ªÀ» Á¤ÇÏ°í, ±× ¾ÈÀ̳ª ±¸¿ª °æ°è¿¡ Á¢ÇØ ÀÖ´Â ³ª¹«¸¦ ¸ðµÎ º£¾î¾ß ÇÑ´Ù.
  3. ÀÌ Á÷»ç°¢Çü ±¸¿ªÀº ½£ÀÇ xÃà°ú yÃà¿¡ ÆòÇàÇÏ´Ù.
  4. Á÷»ç°¢ÇüÀÇ ÇÑ ²ÀÁöÁ¡°ú ±×°ÍÀÇ ´ë°¢¼± ¸ÂÀºÆí ²ÀÁöÁ¡Àº ¹Ýµå½Ã ³ª¹«°¡ ÀÖ´Â °÷À̾î¾ß ÇÑ´Ù. µû¶ó¼­, ±× ²ÀÁöÁ¡¿¡ ¼ÓÇÑ ³ª¹«µµ º£¾îÁö°Ô µÈ´Ù.

³ª¹«¸¦ ÁÁ¾ÆÇÏ´Â ¾Æ¸£Å׹̽º´Â ÇÊ¿ä ÀÌ»óÀÇ ³ª¹«¸¦ °¡´ÉÇÑ ÇÑ º£Áö ¾ÊÀ¸¸é¼­ À§ Á¶°ÇÀ» ¸¸Á·ÇÏ°Ô ³ª¹«¸¦ º£°í ½Í¾îÇÑ´Ù. ½£¿¡ ´ëÇÑ Á¤º¸¿Í º£¾î¾ß ÇÏ´Â ÃÖ¼ÒÇÑÀÇ ³ª¹«ÀÇ ¼ö T¸¦ ¹Þ¾Æµé¿©, ¾Æ¸£Å׹̽º°¡ ½£¿¡¼­ ³ª¹«¸¦ º£¾î¾ß ÇÒ ±¸°£À» Á¤ÇÏ´Â ÇÁ·Î±×·¥À» ÀÛ¼ºÇϽÿÀ.

ÀÔ·Â (artemis.in)

ù° ÁÙ¿¡´Â ½£¿¡ ÀÖ´Â ³ª¹«ÀÇ ±×·ç ¼ö NÀÌ µé¾îÀÖ´Ù. µÑ° ÁÙ¿¡´Â º£¾î¾ß ÇÏ´Â ÃÖ¼ÒÇÑÀÇ ³ª¹« ¼öÀÎ T°¡ µé¾îÀÖ´Ù. ±×¸®°í ´ÙÀ½ N°³ÀÇ ÁÙ¿¡´Â °¢ ³ª¹«µéÀÇ À§Ä¡°¡ XÁÂÇ¥¿Í YÁÂÇ¥ Â÷·Ê·Î µé¾îÀÖ´Ù. ¸ðµç Å×½ºÆ® ÄÉÀ̽º¿¡ ´ëÇØ, 1¡Â N ¡Â 20000, 0¡Â X,Y ¡Â 64000ÀÌ°í, 1<T¡ÂNÀÌ´Ù. ¶ÇÇÑ, Àüü Å×½ºÆ® ÄÉÀ̽º Áß Àý¹ÝÀº 1 < N < 5000ÀÌ´Ù.

3
2
1 1
2 3
5 6

Ãâ·Â (artemis.out)

ÇÑ ÁÙ¿¡ µÎ °³ÀÇ Á¤¼ö I, J¸¦ Ãâ·ÂÇÑ´Ù. ¾Æ¸£Å׹̽º°¡ ³ª¹«¸¦ ÀÚ¸£´Â ±âÁØÀ¸·Î »ïÀ» Á÷»ç°¢Çü ±¸¿ªÀº ÇÑÂÊ ²ÀÁöÁ¡ÀÌ I° ³ª¹«(ÀÔ·Â ÆÄÀÏ¿¡¼­ À§Ä¡ ÁÂÇ¥°¡ I+2° ÁÙ¿¡ ³ª¿À´Â °Í)ÀÌ°í, ´ë°¢¼± ¸ÂÀºÆí ²ÀÁöÁ¡Àº J° ³ª¹«(J+2° ÁÙ¿¡ ÀÖ´Â ³ª¹«ÀÇ À§Ä¡)·Î ÇÏ´Â °ÍÀÌ ÁÁ´Ù´Â ¶æÀÌ´Ù. µÎ Á¡ÀÇ ¼ø¼­´Â ¾î¶² °ÍÀ¸·Î Çصµ ¹«¹æÇϸç, ÃÖÀûÇØ°¡ ¿©·¯ °³ ÀÖ´õ¶óµµ ÇÑ °¡Áö °æ¿ì¿¡ ´ëÇؼ­¸¸ Ãâ·ÂÇÏ¸é µÈ´Ù. ¸ðµç Å×½ºÆ® ÄÉÀ̽º¿¡´Â Á¶°ÇÀ» ¸¸Á·ÇÏ´Â ÇØ°¡ Çϳª ÀÌ»ó ¹Ýµå½Ã Á¸ÀçÇÑ´Ù.

1 2


2. Ç츣¸Þ½ºÀÇ ½ÉºÎ¸§

±×¸®½º ½ÅµéÀÌ »ç´Â Çö´ë½Ä µµ½Ã¿¡´Â ±æ°Å¸®ÀÇ µµ·ÎµéÀÌ X, Y Ãà¿¡ ÆòÇàÇϸç Á¤¼ö ÁÂÇ¥·Î µÈ °ÝÀÚ ÇüÅ·Π¹è¿­µÇ¾î ÀÖ´Ù. ÀÓÀÇÀÇ Á¤¼ö Z¿¡ ´ëÇØ, y=Z·Î Ç¥ÇöµÇ´Â ¼öÆò µµ·Î°¡ ÀÖ°í, x=Z·Î Ç¥ÇöµÇ´Â ¼öÁ÷ µµ·Î°¡ ÀÖ´Ù. ±×·¡¼­ Á¤¼ö·Î ±¸¼ºµÈ ÁÂÇ¥´Â ¼öÆò¡¤ ¼öÁ÷ µµ·Î°¡ ¸¸³ª´Â ±³Â÷·Î°¡ µÈ´Ù.

³¯¾¾°¡ ´õ¿ì¸é ½ÅµéÀº ¹Ù·Î ÀÌ ±³Â÷·Îµé Áß ¾îµð¿£°¡ ÀÖ´Â Ä«ÆäÅ׸®¾Æ¿¡ µû·Î µû·Î Èð¾îÁ® ½®´Ù. ½ÅµéÀÇ ½ÉºÎ¸§²ÛÀÎ Ç츣¸Þ½º´Â À̳¯µµ ±æ°Å¸®ÀÇ µµ·Î¸¸ ÀÌ¿ëÇÏ¿© À̵¿ÇÑ µÚ, ¿©·¯ Ä«ÆäÅ׸®¾Æ¿¡ Èð¾îÁ® ÀÖ´Â ½Åµé¿¡°Ô ¸Þ½ÃÁö¸¦ ºÎÁö·±È÷ Àü´ÞÇÑ´Ù. ÇÑ ¸Þ½ÃÁö´Â ÇÑ ½Å¸¸À» ´ë»óÀ¸·Î ÇÏ°í ÀÖÀ¸³ª, Àü´Þ °úÁ¤¿¡¼­ ¸Þ½ÃÁö°¡ ´Ù¸¥ ½ÅÀÌ ÀÖ´Â ÁöÁ¡À» Åë°úÇÏ´õ¶óµµ »ó°üÀº ¾ø´Ù.

Ç츣¸Þ½º´Â Ãʱ⿡ ¿øÁ¡ (0, 0)¿¡ ÀÖ´Ù. Àü´Þ ¼ø¼­¶ó´Â °³³äÀÌ Á¸ÀçÇϱ⠶§¹®¿¡ Ç츣¸Þ½º´Â Àڽſ¡°Ô °¡±î¿î °÷ºÎÅÍ°¡ ¾Æ´Ï¶ó ¸ÕÀú ¼Ò½ÄÀ» ÀüÇØ¾ß ÇÏ´Â ½Å¿¡°Ô ¸ÕÀú ¸Þ½ÃÁö¸¦ Àü´ÞÇØ¾ß ÇÑ´Ù. ´Ü, ¸Þ½ÃÁö´Â Á÷ÁøÇÏ´Â ±¤ÀÚ¸¦ ¹ß»çÇÏ´Â ¹æ½ÄÀ¸·Î ÀüÇϱ⠶§¹®¿¡, Ç츣¸Þ½º´Â ¸ñÀûÁöÀÎ ½ÅÀÌ ÀÖ´Â °÷°ú x À§Ä¡°¡ °°°Å³ª y À§Ä¡°¡ °°Àº ÁöÁ¡±îÁö¸¸ °¡¸é µÈ´Ù. ÀüÇØ¾ß ÇÏ´Â ¸Þ½ÃÁö¸¦ ¸ðµÎ ÀüÇϸé Ç츣¸Þ½ºÀÇ ÀÓ¹«´Â ³¡³­´Ù.

°¡¾ß ÇÏ´Â Ä«ÆäÅ׸®¾ÆµéÀÇ À§Ä¡¸¦ ÀÔ·ÂÀ¸·Î ¹Þ¾Æ, Ç츣¸Þ½º°¡ °¢ ÁöÁ¡µéÀ» ¼ø¼­´ë·Î ¹æ¹®ÇÏ¸ç ¸Þ½ÃÁö¸¦ Àü´ÞÇÏ´Â µ¥ ÇÊ¿äÇÑ ÃÖ¼ÒÇÑÀÇ À̵¿·®À» °è»êÇÏ´Â ÇÁ·Î±×·¥À» ÀÛ¼ºÇϽÿÀ.

ÀÔ·Â (hermes.in)

ù° ÁÙ¿¡´Â ÀüÇØ¾ß ÇÏ´Â ¸Þ½ÃÁöÀÇ ÃÑ °³¼ö NÀÌ ÀÖ´Ù. ±×¸®°í ´ÙÀ½ NÁÙ¿¡´Â °¢ ¸Þ½ÃÁö¸¦ ÀüÇϱâ À§ÇØ ¹æ¹®ÇØ¾ß ÇÏ´Â Ä«ÆäÅ׸®¾Æ°¡ ±³Â÷·ÎÀÇ ¾î´À À§Ä¡¿¡ ÀÖ´ÂÁö, ±× ÁÂÇ¥°¡ ÇÑ ÁÙ¿¡ Çϳª¾¿, X, Y Ãà ¼øÀ¸·Î µé¾îÀÖ´Ù. ¸ðµç Å×½ºÆ® ÄÉÀ̽º¿¡ ´ëÇØ 1¡Â N ¡Â 20000, -1000¡Â Ä«ÆäÅ׸®¾ÆÀÇ X, YÁÂÇ¥ ¡Â 1000ÀÌ´Ù. ¶ÇÇÑ, Àüü Å×½ºÆ® ÄÉÀ̽º Áß Àý¹ÝÀº 1¡Â N ¡Â 80ÀÌ´Ù.

5
8 3
7 -7
8 1
-2 1
-2 1
6 -5

Ãâ·Â (hermes.out)

ÃÖ¼ÒÀÇ À̵¿ °Å¸®¸¦ ³ªÅ¸³»´Â ¼ýÀÚ Çϳª¸¦ ÇÑ ÁÙ¿¡´Ù Ãâ·ÂÇÑ´Ù.

11

(0, 0)¿¡¼­ (8, 0), (7, 0), (7, 1), (6, 1)ÀÇ ¼øÀ¸·Î À̵¿Çϸé, À̵¿·®ÀÌ ÃÖ¼ÒÀÎ 11ÀÌ µÇ¸é¼­ À§ÀÇ ´Ù¼¸ °÷¿¡ ¸ðµÎ ¼ø¼­´ë·Î ¸Þ½ÃÁö¸¦ ÀüÇÒ ¼ö ÀÖ´Ù.


3. ´Ù°¢Çü ºÐÇØ

´Ù°¢ÇüÀº ±× °æ°è À§¿¡ ³õÀÎ ¸ðµç Á¡°ú ±× ¾ÈÀÇ ¸ðµç ¿µ¿ªÀ¸·Î ±¸¼ºµÇ¾î ÀÖ´Ù. ±× Áß, ´Ù°¢Çü ¾ÈÀÇ ÀÓÀÇÀÇ µÎ Á¡ X, Y¿¡ ´ëÇØ À̵éÀ» ÀÕ´Â ¼±ºÐµµ ¿ÏÀüÈ÷ ±× ´Ù°¢Çü ¾È¿¡ ¼ÓÇØ ÀÖ´Â °ÍÀ» º¼·Ï´Ù°¢ÇüÀ̶ó ÇÑ´Ù. ´Ù°¢ÇüÀº µÎ °³(ÀÌ °æ¿ì, Á÷¼±ÀÌ µÇ¸ç Á÷¼±Àº ´Ù°¢ÇüÀÇ Æ¯¼öÇÑ ÇüÅÂÀÓ) ÀÌ»óÀÇ ²ÀÁöÁ¡À¸·Î ÀÌ·ç¾îÁ® ÀÖÀ¸¸ç ¼¼ ²ÀÁöÁ¡ÀÌ ÇÑ Á÷¼± À§¿¡ ÀÖ´Â °æ¿ì´Â ¾ø´Ù. ÀÌ ¹®Á¦¿¡¼­ ´Ù·ç´Â ´Ù°¢ÇüÀº ¸ðµÎ ÀÌ·¯ÇÑ Æ¯¼ºµéÀ» ¸¸Á·ÇÏ´Â °Í¸¸À» ´ë»óÀ¸·Î Çϸç, ¾ÕÀ¸·Î '´Ù°¢Çü'À̶ó°í¸¸ Çصµ ±×·± °ÍµéÀ» ÀÏıâ·Î ÇÏ°Ú´Ù.

µÎ ´Ù°¢Çü A, B°¡ ÀÖÀ» ¶§, À̵éÀÇ ¹ÎÄÚÇÁ½ºÅ° ÇÕÀº, AÀÇ ÀÓÀÇÀÇ ²ÀÁöÁ¡ ÁÂÇ¥ (x1, y1)¿Í BÀÇ ÀÓÀÇÀÇ ²ÀÁöÁ¡ ÁÂÇ¥ (x2, y2)¿¡ ´ëÇØ, ÀÖÀ» ¼ö ÀÖ´Â ¸ðµç (x1+x2, y1+y2) Á¶ÇÕÀ» ²ÀÁöÁ¡À¸·Î °®´Â µµÇüÀÌ´Ù. ´Ù°¢Çü A, BÀÇ ¹ÎÄÚÇÁ½ºÅ° ÇÕ ¿ª½Ã ´Ù°¢ÇüÀÓÀ» ¾Ë ¼ö ÀÖ´Ù. ´ÙÀ½Àº µÎ »ï°¢Çü°ú À̵éÀÇ ¹ÎÄÚÇÁ½ºÅ° ÇÕÀ» ±×¸²À¸·Î ³ªÅ¸³½ °ÍÀÌ´Ù.

¿ì¸®´Â ¹ÎÄÚÇÁ½ºÅ° ÇÕÀ¸·Î ÇÕ¼ºµÈ ´Ù°¢ÇüÀ», ¿ø·¡ÀÇ µÎ ´Ù°¢ÇüÀ¸·Î º¹¿øÇÏ·Á°í ÇÑ´Ù. Á»´õ ±¸Ã¼ÀûÀ¸·Î ¸»Çϸé, ¾î¶² ´Ù°¢Çü P°¡ ÀÖÀ» ¶§ ¿ì¸®°¡ ã´Â °ÍÀº µÎ ´Ù°¢Çü A, B·Î, À̵éÀº ´ÙÀ½°ú °°Àº Á¶°ÇÀ» ¸¸Á·ÇØ¾ß ÇÑ´Ù.

A³ª B°¡ P ±× ÀÚüÀÏ ¼ö´Â ¾øÀ½À» µÎ¸»ÇÒ ³ªÀ§°¡ ¾øÀ» °ÍÀÌ´Ù. A, B Áß Çϳª°¡ ¿ø·¡ÀÇ µµÇüÀÌ¸é ´Ù¸¥ Çϳª´Â (0, 0)¿¡ ÀÖ´Â Á¡ÀÌ µÇ¾î ¹ö¸®°í, ÀÌ°ÍÀº ´Ù°¢ÇüÀÌ ¾Æ´Ï±â ¶§¹®ÀÌ´Ù.

ÀÌ ¹®Á¦¿¡¼­´Â ´Ù°¢Çü P°¡ ¾î¶² ¸ð¾çÀÎÁö¸¦ ±â¼úÇÑ ¿©·¯ ÀÔ·Â ÆÄÀÏÀÌ ÁÖ¾îÁø´Ù. °¢ ÀԷ¿¡ ´ëÇØ À§ÀÇ Á¶°ÇÀ» ¸¸Á·ÇÏ´Â ¿ø·¡ ´Ù°¢Çü A, B¸¦ ±¸ÇÑ µÚ, À̵éÀÌ ¾î¶² ¸ð¾çÀÎÁö¸¦ Ãâ·Â ÆÄÀÏ·Î ¸¸µé¾î Á¦ÃâÇϽÿÀ. °¢ ÀԷµéÀº A¿Í B°¡ ¹Ýµå½Ã Á¸ÀçÇÏ´Â °æ¿ìµéÀ̸ç, Á¶°ÇÀ» ¸¸Á·ÇÏ´Â Ç®ÀÌ°¡ ¿©·¯ °³ Á¸ÀçÇÏ´õ¶óµµ Çϳª¸¸ ¼±ÅÃÇÏ¸é µÈ´Ù. À̹ø ¹®Á¦´Â Ãâ·Â ÆÄÀÏÀ» ¸¸µå´Â ÇÁ·Î±×·¥ÀÌ ¾Æ´Ï¶ó Ãâ·Â ÆÄÀÏ ÀÚü¸¸ Á¦ÃâÇϵµ·Ï ÇÑ´Ù.

ÀÔ·Â

polygon1.inºÎÅÍ polygon10.in±îÁö ¿­ °³ÀÇ ´Ù°¢Çü ¿¹Á¦¸¦ ¹Þ´Â´Ù. ÆÄÀÏ À̸§ µÚÀÇ ¹øÈ£°¡ Å×½ºÆ® ÄÉÀ̽ºÀÇ ¹øÈ£ÀÌ´Ù. °¢ ÆÄÀÏÀÇ Ã¹ ÁÙ¿¡´Â ´Ù°¢Çü PÀÇ ²ÀÁöÁ¡ °³¼öÀÎ NÀÌ µé¾îÀÖ°í, ´ÙÀ½ NÁÙ¿¡´Â ´Ù°¢Çü ²ÀÁöÁ¡µéÀÇ ÁÂÇ¥°¡ ¹Ý½Ã°è ¹æÇâÀ¸·Î ÇÑ ÁÙ¿¡ ÇÑ ²ÀÁöÁ¡¾¿ ¼ø¼­´ë·Î µé¾îÀÖ´Ù. °¢ ÁÙ¿¡¼­ ÁÂÇ¥´Â XÃà, YÃàÀÇ ¼øÀ¸·Î ÀÖ°í, ¼ýÀÚ »çÀÌ´Â °ø¹é ÇÑ Ä­À¸·Î ±¸ºÐµÅ ÀÖ´Ù. ¸ðµç ÁÂÇ¥´Â À½ÀÌ ¾Æ´Ñ Á¤¼öÀÌ´Ù.

polygon0.in
5
0 1
0 0
2 0
2 1
1 2

Ãâ·Â

°¢ 10°³ÀÇ ÀԷ¿¡ ´ëÇÑ ´Ù°¢Çü A, B¸¦ ±¸ÇÑ Ãâ·Â ÆÄÀÏÀ» 10°³ Á¦ÃâÇÑ´Ù. Ãâ·Â ÆÄÀÏ À̸§¿¡ ´ëÇÑ Æ¯º°ÇÑ ±ÔÁ¤Àº ¾øÀ¸¸ç, ´ÜÁö Ãâ·Â ÆÄÀÏÀÇ Çü½Ä¸¸ ´ÙÀ½°ú °°ÀÌ ¸ÂÃß¸é µÈ´Ù. ±× ±¸Á¶´Â ÀÔ·Â ÆÄÀÏÀÇ Çü½Ä°ú À¯»çÇÏ´Ù.

ù ÁÙ¿¡´Â "#FILE polygon I" (1¡Â I ¡Â10)À» ±â·ÏÇÑ´Ù. I´Â ÀÌ Ãâ·Â ÆÄÀÏ°ú ´ëÀÀÇÏ´Â ÀÔ·Â ¹®Á¦ÀÇ ¹øÈ£ÀÌ´Ù. µÑ° ÁÙ¿¡´Â ´Ù°¢Çü AÀÇ ²ÀÁöÁ¡ °³¼ö¸¦ ±â·ÏÇÏ°í(2¡Â NA ¡Â4), ´ÙÀ½ NA ÁÙ¿¡´Â ´Ù°¢Çü AÀÇ ²ÀÁöÁ¡À» ¹Ý½Ã°è ¹æÇâÀ¸·Î ÀÔ·Â ÆÄÀÏ°ú °°Àº Çü½ÄÀ¸·Î, Â÷·Ê´ë·Î ±â·ÏÇÑ´Ù.

NA+3° ÁÙ¿¡´Â ´Ù°¢Çü BÀÇ ²ÀÁöÁ¡ °³¼öÀÎ NB¸¦ ±â·ÏÇÑ´Ù(2 ¡Â NB). ±×¸®°í ´ÙÀ½ NB°³ÀÇ ÁÙ¿¡´Â ´Ù°¢Çü BÀÇ ²ÀÁöÁ¡ ÁÂÇ¥¸¦ ¹Ý½Ã°è ¹æÇâÀ¸·Î Â÷·Ê´ë·Î ±â·ÏÇÑ´Ù. À§ÀÇ ÀԷ¿¡ ´ëÇØ,

#FILE polygon 0
3
0 0
2 0
1 1
2
0 1
0 0

¿Í

#FILE polygon 0
3
0 0
2 0
1 1
3
0 1
0 0
1 0

´Â ¸ðµÎ ¸Â´Â Ç®ÀÌÀÌ´Ù. ´Ù°¢Çü A°¡, ÀÌ ÀԷ¿¡ ´ëÇØ °¡Àå ¸¹Àº º¯À» °¡Áú ¼ö ÀÖ´Â ÇüÅÂÀÎ »ï°¢ÇüÀ̶ó´Â Á¡¿¡¼­ °°±â ¶§¹®ÀÌ´Ù. (»çº¯ÇüÀÏ ¼ö´Â ¾øÀ½)


4. ¿¥Æ÷µð¿À

°í´ëÀÇ ¼öÇÐÀÚ¡¤ öÇÐÀÚÀÎ ÇÇŸ°í¶ó½º´Â, ½ÇÁ¸ÇÏ´Â °ÍÀÇ º»ÁúÀº ¼öÇÐÀ̶ó°í ¹Ï¾ú´Ù. ±× ÈÄ, ¿À´Ã³¯ÀÇ »ý¹°ÇÐÀÚµéÀº »ý¹°ÇÐÀû ¼ö¿­À̶ó´Â °ÍÀ» ¿¬±¸ÇÏ°í Àִµ¥, ÀÌ°ÍÀº M°³ÀÇ Á¤¼ö·Î µÇ¾î ÀÖÀ¸¸é¼­ ±× Â¥ÀÓÀÌ ´ÙÀ½ Á¶°ÇÀ» ¸¸Á·ÇÏ´Â ¼ö¿­ÀÌ´Ù.

¼ö¿­ ¾È¿¡¼­ µÑ ÀÌ»óÀÇ ÀÎÁ¢ÇØ ÀÖ´Â ÀϺΠ¿ø¼Ò¸¦ »ÌÀº °ÍÀ» ±¸°£À̶ó°í ÇÏÀÚ. »ý¹°ÇÐÀû ¼ö¿­ ¾È¿¡ ¾î¶² ±¸°£ÀÌ Àִµ¥, ù°, ±¸°£ÀÇ ¸Ç ¾Õ¿¡ ÀÖ´Â ¼ö°¡ ±× ±¸°£ ÀüüÀÇ ¼öµé Áß¿¡ °¡Àå ÀÛ°í, µÑ°, ±¸°£ ¸Ç µÚ¿¡ ÀÖ´Â ¼ö°¡ ±¸°£ Àüü¿¡¼­ °¡Àå Å« ¼öÀ̸ç, ¼Â°, ±× ±¸°£ ¾È¿¡ ÃÖ¼Ò°ª(óÀ½)°ú ÃÖ´ë°ª(³¡) »çÀÌÀÇ ¸ðµç ¼ö°¡ µé¾îÀÖÀ¸¸é ±× ±¸°£Àº "°®Ãá ±¸°£"À̶ó°í ÇÑ´Ù. ¿©±â¿¡ µ¡ºÙ¿©, ±× ±¸°£ ¾È¿¡ ´õ ªÀº °®Ãá ±¸°£ÀÌ Á¸ÀçÇÏÁö ¾ÊÀ¸¸é ±× °®Ãá ±¸°£À» ¿¥Æ÷µð¿À¶ó°í ÀÏÄ´´Ù.

¿¹¸¦ µé¾î, (0, 3, 5, 4, 6, 2, 1, 7)À̶ó´Â »ý¹°ÇÐÀû ¼ö¿­ÀÌ ÀÖ´Ù°í ÇÏÀÚ. »ý¹°ÇÐÀû ¼ö¿­ÀÇ Á¤ÀÇ´Â °®Ãá ±¸°£ÀÇ Á¶°ÇÀ» Æ÷ÇÔÇÏ°í Àֱ⠶§¹®¿¡ ÀÌ ¼ö¿­ Àüü°¡ °®Ãá ±¸°£À̶ó ÇÒ ¼ö ÀÖ´Ù. ±×·¯³ª ÀÌ ¾È¿¡´Â ´õ ªÀº °®Ãá ±¸°£ÀÎ (3, 5, 4, 6)ÀÌ ÀÖÀ¸¹Ç·Î ¼ö¿­ Àüü¸¦ ¿¥Æ÷µð¿À¶ó°í ÇÒ ¼ö´Â ¾ø´Ù. °®Ãá ±¸°£ (3, 5, 4, 6) ¾È¿¡´Â ´Ù¸¥ °®Ãá ±¸°£ÀÌ ´õ ¾øÀ¸¹Ç·Î ÀÌ°ÍÀº ¿¥Æ÷µð¿ÀÀÌ´Ù. ¶ÇÇÑ, ÀÌ ±¸°£ÀÌ ±× ¼ö¿­ Àüü¿¡¼­ À¯ÀÏÇÑ ¿¥Æ÷µð¿ÀÀÌ´Ù.

»ý¹°ÇÐÀû ¼ö¿­À» ÀÔ·Â¹Þ¾Æ ÀÌ ¾È¿¡ Á¸ÀçÇÏ´Â ¿¥Æ÷µð¿À ±¸°£À» ¸ðµÎ ã´Â ÇÁ·Î±×·¥À» ÀÛ¼ºÇϽÿÀ.

ÀÔ·Â (empodia.in)

ù ÁÙ¿¡´Â »ý¹°ÇÐÀû ¼ö¿­ÀÇ ±æÀ̸¦ ³ªÅ¸³»´Â Á¤¼ö MÀÌ µé¾îÀÖ´Ù. ´ÙÀ½ M°³ÀÇ ÁÙ¿¡´Â ¼ö¿­À» ±¸¼ºÇÏ´Â Á¤¼ö°¡ Çϳª¾¿ ¼ø¼­´ë·Î µé¾îÀÖ´Ù. ½º¹« °³ÀÇ Å×½ºÆ® ÄÉÀ̽º Áß Çϳª´Â 100¸¸¡Â M ¡Â110¸¸ÀÌ´Ù. ´Ù¸¥ ¸ðµç Å×½ºÆ® ÄÉÀ̽º´Â 1¡Â M ¡Â 60000À̳ª, ÀüüÀÇ Àý¹Ý(10°³)Àº M ¡Â 2600ÀÌ´Ù. Âü°í·Î, empodia´Â ¿¥Æ÷µð¿À(empodio)ÀÇ º¹¼öÇüÀ» Ç¥±âÇÑ °ÍÀÌ´Ù.

8
0
3
5
4
6
2
1
7

Ãâ·Â (empodia.out)

ù ÁÙ¿¡´Â ÀÌ »ý¹°ÇÐÀû ¼ö¿­¿¡ Á¸ÀçÇÏ´Â ¿¥Æ÷µð¿ÀÀÇ °³¼ö H¸¦ Ãâ·ÂÇÑ µÚ, ´ÙÀ½ HÁÙ¿¡´Â ¿¥Æ÷µð¿ÀÀÇ À§Ä¡¸¦ ÀÛÀº ¼ø¼­¿¡¼­ Å« ¼ø¼­·Î Â÷·Ê´ë·Î Ãâ·ÂÇÑ´Ù. °¢ ÁÙ¿¡´Â µÎ Á¤¼ö A¿Í B¸¦ °ø¹é Çϳª·Î ±¸ºÐÇÏ¿© Ãâ·ÂÇϴµ¥, A´Â °¢ ÁÙ¿¡ ÇØ´çÇÏ´Â ¿¥Æ÷µð¿ÀÀÇ Ã¹ ¿ø¼ÒÀÇ ¹øÈ£(1ºÎÅÍ ½ÃÀÛ)ÀÌ°í, B´Â ¸¶Áö¸· ¿ø¼ÒÀÇ ¹øÈ£ÀÌ´Ù.

1
2 5

(µÑ° ¿ø¼ÒÀÎ 3°ú, ´Ù¼¸Â° ¿ø¼ÒÀÎ 6À» ÀǹÌ)


5. ³óºÎ

¿©·¯ °³ÀÇ Á¤¿ø°ú ¿©·¯ °³ÀÇ À̶û--ÀÏ·Ä·Î ³ª¹«³ª °î½ÄÀ» ½É´Â ±æÂßÇÑ ±æ--À» ¼ÒÀ¯ÇÑ ÇÑ ³óºÎ°¡ ÀÖ´Ù. Á¤¿øÀÇ °æ°è´Â »çÀÌÇÁ·¯½º ³ª¹«·Î µÑ·¯½Î¿© ÀÖÀ¸¸ç, °¢ À̶û¿¡µµ »çÀÌÇÁ·¯½º ³ª¹«°¡ ½É¾îÁ® ÀÖ´Ù. ¶ÇÇÑ Á¤¿ø°ú À̶û ¸ðµÎ, µÎ »çÀÌÇÁ·¯½º ³ª¹« »çÀÌ¿¡´Â ¿Ã¸®ºê ³ª¹«°¡ ÇÑ ±×·ç ½É¾îÁ® ÀÖ´Ù. ÀÌ·± ½ÄÀ¸·Î ³óºÎÀÇ ¸ðµç »çÀÌÇÁ·¯½º ³ª¹«´Â Á¤¿øÀ» µÑ·¯½Î°Å³ª À̶ûÀ» µû¶ó ½É¾îÁ® ÀÖÀ¸¸ç, »çÀÌÇÁ·¯½º ³ª¹« µÎ ±×·ç »çÀÌ¿¡´Â ¹Ýµå½Ã ¿Ã¸®ºê ³ª¹«°¡ ÇÑ ±×·ç ³¢¿© ÀÖ´Ù.

±×·¯´ø ¾î´À³¯, ³óºÎ´Â ½ÉÇÑ º´¿¡ °É·Á ÀÓÁ¾À» ¾ÕµÎ°Ô µÇ¾ú´Ù. ¼ûÀ» °ÅµÎ±â ¸çÄ¥ Àü, ±×´Â ¸º¾Æµé¿¡°Ô ÀÌ·¸°Ô ¸»Çß´Ù. "³» Á¤¿ø°ú À̶û¿¡ ½É¾îÁø »çÀÌÇÁ·¯½º ³ª¹«µéÀ» ¾Æ¹« °Å³ª Q ±×·ç °ñ¶ó¶ó. ±×·¯¸é ±× ³ª¹«µé°ú, µÎ ³ª¹« »çÀÌ¿¡ ½É°ÜÁ® ÀÖ´Â ¿Ã¸®ºê ³ª¹«±îÁö ¸ðµÎ ³×°Ô ÁÖ°Ú´Ù."

¾Æ¹öÁöÀÇ À¯¾ð¿¡ µû¶ó ¾ÆµéÀº Á¤¿ø °æ°è³ª À̶û¿¡¼­ ¿¬¼ÓÇÏ´Â ±¸°£À» Çϳª ÀÌ»ó ¼±ÅÃÇÏ¿© »çÀÌÇÁ·¯½º ³ª¹«¸¦ ÃÖ´ë Q ±×·ç±îÁö ¾òÀ» ¼ö ÀÖ°í, ±× »çÀÌ¿¡ ÀÖ´Â ¿Ã¸®ºê ³ª¹«µéµµ ¾òÀ» ¼ö ÀÖ´Ù. ¾ÆµéÀº ¿Ã¸®ºê¸¦ ¸Å¿ì ÁÁ¾ÆÇϱ⠶§¹®¿¡ ¿Ã¸®ºê ³ª¹«¸¦ °¡Àå ¸¹ÀÌ ¾òÀ» ¼ö ÀÖ´Â ±¸°£À» ¼±ÅÃÇÏ°í ½Í¾îÇÑ´Ù.

³óºÎ¿¡°Ô Á¤¿ø°ú À̶ûÀÌ ¼¼ °³¾¿ ÀÖ°í, »çÀÌÇÁ·¯½º ³ª¹«°¡ °¢ °÷¿¡ À§ÀÇ ±×¸²°ú °°ÀÌ ÀÖ´Ù°í °¡Á¤ÇÏÀÚ. (»çÀÌÇÁ·¯½º ³ª¹« »çÀÌ¿¡ ÀÖ´Â ¿Ã¸®ºê ³ª¹«´Â ÆíÀÇ»ó Ç¥±âÇÏÁö ¾Ê¾Ò´Ù) ±×¸®°í Q=17±×·çÀÇ »çÀÌÇÁ·¯½º ³ª¹«¸¦ ¹°·Á¹ÞÀ» ¼ö ÀÖ´Ù°í ÇÏÀÚ. ±×·¸´Ù¸é ¾ÆµéÀº Á¤¿ø 1°ú 2¿¡ ÀÖ´Â »çÀÌÇÁ·¯½º ³ª¹«¸¸À» ¸ðµÎ ¼±ÅÃÇÏ¸é µÈ´Ù. Á¤¿øÀº À̶û°ú´Â ´Þ¸® °í¸®¸¦ ÀÌ·ç°í Àֱ⠶§¹®¿¡, ±× ¾È¿¡ ÀÖ´Â 17±×·çÀÇ ¿Ã¸®ºê ³ª¹«¸¦ ¸ðµÎ ¹°·Á¹ÞÀ» ¼ö Àֱ⠶§¹®ÀÌ´Ù.

¹ç°ú À̶û¿¡ ÀÖ´Â ³ª¹« ¼ö¿Í ¹°·Á¹ÞÀ» ¼ö ÀÖ´Â ³ª¹«ÀÇ ¼ö¸¦ ÀÔ·ÂÀ¸·Î ¹Þ¾Æ, ¾ÆµéÀÌ ¹°·Á¹ÞÀ» ¼ö ÀÖ´Â ¿Ã¸®ºê ³ª¹«ÀÇ ÃÖ´ë ¼ö¸¦ ±¸ÇÏ´Â ÇÁ·Î±×·¥À» ÀÛ¼ºÇϽÿÀ.

ÀÔ·Â (farmer.in)

ù° ÁÙ¿¡´Â ¾ÆµéÀÌ ¹°·Á¹ÞÀ» ¼ö ÀÖ´Â ³ª¹«ÀÇ ±×·ç ¼ö Q¿Í, Á¤¿øÀÇ ¼ö M, ±×¸®°í À̶ûÀÇ ¼ö K°¡ µé¾îÀÖ´Ù. µÑ° ÁÙ¿¡´Â °¢ Á¤¿ø¿¡ ÀÖ´Â »çÀÌÇÁ·¯½º ³ª¹«ÀÇ ¼ö°¡ M°³ ÀÖÀ¸¸ç(N1~Nm), ´ÙÀ½ ÁÙ¿¡´Â °¢ À̶û¿¡ ÀÖ´Â »çÀÌÇÁ·¯½º ³ª¹«ÀÇ ¼ö°¡ K°³ ÀÖ´Ù(R1~Rk).

0¡Â Q ¡Â15¸¸, 0¡Â M, K ¡Â2000ÀÌ°í, ÇÑ Á¤¿øÀ̳ª À̶û¿¡ ÀÖ´Â ³ª¹«ÀÇ ¼ö´Â 2 ÀÌ»ó 150 ÀÌÇÏÀÌ´Ù. ¸ðµç Á¤¿ø°ú À̶û¿¡ ÀÖ´Â ³ª¹«µéÀÇ ÃÑÇÕÀº ¹Ýµå½Ã Qº¸´Ù °°°Å³ª Å©´Ù. ¶ÇÇÑ Àüü Å×½ºÆ® ÄÉÀ̽ºÀÇ Àý¹ÝÀº Q¡Â1500ÀÌ´Ù.

17 3 3
13 4 8
4 8 6

Ãâ·Â (farmer.out)

¾ÆµéÀÌ ´ýÀ¸·Î ¹ÞÀ» ¼ö ÀÖ´Â ¿Ã¸®ºê ³ª¹«ÀÇ ÃÖ´ë ±×·ç ¼ö¸¦ Ãâ·ÂÇÑ´Ù.

17


6. Çǵð¾Æ½º

°í´ë ±×¸®½ºÀÇ À¯¸íÇÑ Á¶°¢°¡ÀÎ Çǵð¾Æ½º´Â ¶Ç´Ù¸¥ °ÉÀÛÀ» ¸¸µé±â À§ÇÑ Áغñ ÀÛ¾÷À» ÇÏ°í ÀÖ´Ù. ±×·¡¼­ °¡·Î ¼¼·Î Å©±â°¡ W1¡¿H1, W2¡¿H2, ... Wn¡¿HnÀÎ Á÷»ç°¢Çü ¸ð¾çÀÇ ´ë¸®¼® µ¹ÆÇÀÌ ¿©·¯ Àå ÇÊ¿äÇÑ »óÅÂÀÌ´Ù.

¾ó¸¶ Àü, Çǵð¾Æ½º´Â Ä¿´Ù¶õ Á÷»ç°¢Çü µ¹ÆÇÀ» ¹Þ¾Ò´Ù. ±×·¡¼­ ÀÌ°ÍÀ» ¿øÇÏ´Â Å©±â¿¡ ÇØ´çÇÏ´Â µ¹Æǵé·Î ÂÉ°³°í ½Í¾îÇÑ´Ù. µ¹ÆÇÀº ÀÓÀÇÀÇ Á¤¼ö À§Ä¡¿¡¼­ °¡·Î³ª ¼¼·Î·Î ¿ÏÀüÈ÷ Àß¶ó¼­ µÎ °³ÀÇ Á÷»ç°¢Çü ¸ð¾çÀ¸·Î ÀÚ¸¦ ¼ö ÀÖ´Ù. ÇÏÁö¸¸ ÀÛÀº µ¹ÆǵéÀ» ºÙ¿©¼­ Å« ÆÇÀ¸·Î ¸¸µé ¼ö´Â ¾ø´Ù. ¶ÇÇÑ, µ¹ÆÇ¿¡´Â ÀÏÁ¤ÇÑ ¹æÇâÀ¸·Î ¹«´Ì°¡ Àֱ⠶§¹®¿¡, ȸÀüÇؼ­ ¿øÇÏ´Â Å©±â¸¦ ¸¸µé ¼ö´Â ¾ø´Ù. ´Ù½Ã ¸»ÇØ, A¡¿B¶ó´Â Å©±â·Î À߶ú´Ù¸é ÀÌ°ÍÀ» B¡¿A¶ó´Â Å©±â¿¡ ¸ÂÃß¾î »ç¿ëÇÒ ¼ö´Â ¾ø´Ù´Â ¶æÀÌ´Ù. µ¹ÆÇ¿¡¼­ ¿øÇÏ´Â Å©±â¿¡ ÇØ´çÇÏ´Â ¸éÀ» ¸ðµÎ Àß¶ó ³½ µÚ, ¾î´À Å©±â·Îµµ ÂÉ°¶ ¼ö ¾ø¾î ³²°Ô µÈ ¸éµéÀº ¹ö·ÁÁø´Ù. Çǵð¾Æ½º´Â ¿øÆÇÀ» ¾î¶»°Ô ÀÚ¸£¸é ÀÌ·¯ÇÑ ¼Õ½ÇÀ» °¡´ÉÇÑ ÇÑ ÁÙÀÏ ¼ö ÀÖÀ»Áö ¾Ë°í ½Í¾îÇÑ´Ù.

°¡·Î ±æÀÌ°¡ 21ÀÌ°í ¼¼·Î ±æÀÌ°¡ 11ÀÎ Ä¿´Ù¶õ µ¹ÆÇÀ» ¿¹·Î µé¾î º¸ÀÚ. ±×¸®°í ¿ì¸®¿¡°Ô ÇÊ¿äÇÑ µ¹ÆÇ Å©±âÀÇ Á¾·ù°¡ 10¡¿4, 6¡¿2, 7¡¿5, ±×¸®°í 15¡¿10À̶ó°í °¡Á¤ÇÏÀÚ. ÀÌ °æ¿ì µ¹ÆÇÀ» ¾Æ·¡ ±×¸²°ú °°ÀÌ ÀÚ¸£¸é, °¢ Å©±â¿¡ ÇØ´çÇÏ´Â µ¹ÆÇÀ» °¢°¢ µÎ Àå, ¼¼ Àå, ¼¼ À徿 ¾òÀ¸¸é¼­ ¼Õ½ÇµÇ´Â ¿µ¿ªÀÇ ³ÐÀÌ´Â 10À¸·Î °¡Àå ÀÛ°Ô µÈ´Ù.

15¡¿10ÀÇ Å©±â´Â ÇÑ ÀåÀÌ¶óµµ ³ÖÀ» °æ¿ì ÀüüÀÇ ¼Õ½ÇÀÌ ³Ê¹« Ä¿Áö±â ¶§¹®¿¡, ¸¸µé±â¸¦ Æ÷±âÇÑ °ÍÀÌ´Ù. ÇÑÆíÀ¸·Î, °¡Àå ³ÐÀÌ°¡ ÀÛÀº µ¹ÆǸ¸À¸·Î ¿©·¯ ÀåÀ» Àß¶ó ³½´Ù°í Çصµ ¼Õ½ÇÀ» À̺¸´Ù ÁÙÀÏ ¼ö ¾ø´Ù´Â °ÍÀº, ¼ÕÀ¸·Î µûÁ® º¸¸é ±Ý¹æ ¾Ë ¼ö ÀÖ´Ù.

µ¹ÆÇÀÇ ¿ø·¡ Å©±â¿Í ¿ì¸®°¡ ¿øÇÏ´Â µ¹ÆÇ Å©±âµéÀ» ÀÔ·Â ¹ÞÀº µÚ, °¡Àå È¿À²ÀûÀ¸·Î µ¹ÆÇÀ» ÀÚ¸£´Â ¹æ¹ýÀ» °è»êÇÏ¿© ±×¶§ ¼Õ½ÇµÇ´Â ÃÖ¼ÒÇÑÀÇ µ¹ÆÇ ¸éÀûÀÇ ÇÕÀ» ±¸ÇÏ´Â ÇÁ·Î±×·¥À» ÀÛ¼ºÇϽÿÀ. ¾î´À Å©±âÀÇ µ¹ÆÇÀ» ¾ó¸¶³ª ¾ò´À³Ä°¡ ¾Æ´Ï¶ó, ¾î¶»°Ô ÀÚ¸£µç ¼Õ½ÇÀ» ÁÙÀÌ´Â °ÍÀÌ ¸ñÀûÀÌ´Ù.

ÀÔ·Â (phidias.in)

ù ÁÙ¿¡´Â ´ë¸®¼® ¿øÆÇÀÇ Å©±â¸¦ ³ªÅ¸³»´Â W(°¡·Î ±æÀÌ), H(¼¼·Î ±æÀÌ)°¡ µé¾îÀÖ´Ù. ´ÙÀ½ ÁÙ¿¡´Â ¿ì¸®°¡ ¿øÇÏ´Â Å©±âÀÇ °³¼ö NÀÌ ÀÖ°í, ±×´ÙÀ½ NÁÙ¿¡´Â ±× Å©±âµéÀÌ ¿ª½Ã °¡·Î, ¼¼·Î ¼øÀ¸·Î µé¾îÀÖ´Ù. 1¡Â W, H ¡Â600ÀÌ°í 0 < N ¡Â 200ÀÌ´Ù. À߶ó¾ß ÇÏ´Â Å©±â´Â °¡·Î¡¤ ¼¼·Î ¸ðµÎ 1 ÀÌ»óÀÌ°í ¿øÆÇÀÇ Å©±â ÀÌÇÏÀÌ´Ù. ´Ü, Àüü Å×½ºÆ® ÄÉÀ̽º Áß Àý¹ÝÀº W, H ¡Â20ÀÌ°í N¡Â5ÀÌ´Ù.

21 11
4
10 4
6 2
7 5
15 10

Ãâ·Â (phidias.out)

Á¤¼ö Çϳª¸¦ Ãâ·ÂÇÑ´Ù. ¿øÆÇÀ» °¡Àå Çö¸íÇÏ°Ô À߶úÀ» ¶§ ¼Õ½ÇµÇ´Â ¸éÀûÀÇ ÃÖ¼Ò°ªÀÌ´Ù.

10