Á¦ 19ȸ

Á¦ 19ȸ´Â 2007³â 8¿ù 15ÀϺÎÅÍ 22ÀϱîÁö Å©·Î¾ÆƼ¾Æ ÀÚ±×·¹ºê¿¡¼­ ¿­·È´Ù. 05³â°ú ¸¶Âù°¡Áö·Î Á¦ÃâÇü ¹®Á¦°¡ µîÀåÇÏÁö ¾Ê¾ÒÀ¸¸ç, ºÎºÐÁ¡¼ö°¡ ÀüÇô ¾ø´Â ±ò²ûÇÑ ÃÖÀûÇØ ¹®Á¦µéÀÌ´Ù. ´ëÈ­ÇüÀ¸·Î À§Ä¡¸¦ Âï¾î ¾Ë¾Æ ¸ÂÈ÷´Â ¹®Á¦¸¦ "Å©·Î¾ÆƼ¾Æ ½Ä" ü½ºÆÇ ¹«´Ì¿¡´Ù Á¢¸ñÇÑ 1¹øÀº ¿Ü°èÀÎ ¼ÒÀç±îÁö µ¿¿øÇÑ °Ô ³ª¸§´ë·Î ÀçÄ¡±îÁö ´À²¸Áø´Ù.

04³âºÎÅÍ °ü·ÊÀûÀ¸·Î µ¡ºÙ¿©Áö°í ÀÖ´Â 'ÀÛÀº Å×½ºÆ® ÄÉÀ̽º' Á¶°Ç¿¡ ´ëÇÑ ¹è·Á(Àüü Å×½ºÆ® ÄÉÀ̽º Áß ¸î Á¡Àº NÀÇ °ªÀÌ ¸Å¿ì ÀÛ´Ù´Â ½Ä)´Â ´õ¿í ÀÚ»óÇØÁ³´Ù. ÀϺΠ¹®Á¦´Â °æ½Ã µµÁß¿¡µµ °ø½Ä äÁ¡ ½Ã½ºÅÛÀ» ºÎºÐÀûÀ¸·Î È°¿ëÇÏ¿© ÀÛ¼º ÁßÀÎ ÇÁ·Î±×·¥À» "¿¹ºñ äÁ¡"ÇØ º¼ ¼öµµ ÀÖ°Ô ¼öÇèÀÚ¸¦ ¹è·ÁÇß´Ù. (2, 4, 6¹ø) ¿ÃÇØ´Â ÃÖÃÊ·Î ¸î¸î ¹®Á¦¿¡ "64ºñÆ® Á¤¼ö¸¦ »ç¿ëÇÏ¿© Ãâ·ÂÇϽÿÀ"¶õ ´Ü¼­°¡ ºÙÀº °Íµµ ÀλóÀûÀÌ´Ù. (3¹ø°ú 5¹ø)

600Á¡ ¸¸Á¡¿¡ ±Ý¸Þ´Þ ÀÔ»óÀÚÀÇ ÃÖ°í Á¡¼ö´Â 574Á¡, µ¿¸Þ´Þ ÀÔ»óÀÚÀÇ ÃÖÀú Á¡¼ö´Â 187Á¡À̾ú´Ù. ¿ì¸®³ª¶ó´Â Àº¸Þ´Þ 2°³, µ¿¸Þ´Þ 2°³¸¦ ȹµæÇØ ¿¹³âº¸´Ù ¼ºÀûÀÌ »ó´ëÀûÀ¸·Î ÀúÁ¶Çß´Ù. Áß±¹Àº Âü°¡ÀÚ 4¸í Àü¿øÀÌ ±Ý¸Þ´ÞÀ» ȹµæÇÏ°í, ·¯½Ã¾Æµµ ±Ý 3, Àº 1À̾ú´Ù.

¿ø¹®ÀÌ ÀÖ´Â °÷: http://ioi2007.hsin.hr/index.php?page=tasks

1. ¹Ì¸£ÄÚÀÇ ¹Ì½ºÅ͸® ¼­Å¬ (´ëÈ­Çü)

2. È«¼ö ½Ã¹Ä·¹À̼Ç

3. µÀ´Ü¹è

4. ±¤ºÎµéÀÇ ½Ä»ç

5. °¡±î¿î ¦ ã±â

6. »çÀÌŬ ¿¬½À ÄÚ½º


1. ¹Ì¸£ÄÚÀÇ ¹Ì½ºÅ͸® ¼­Å¬

¹Ì½ºÅ͸® ¼­Å¬¿¡ ´ëÇؼ­ µé¾î º¸¾Ò´Â°¡? (³ÐÀº ¹çÀ» °øÁß¿¡¼­ ³»·Á´ÙºÃÀ» ¶§, °î½ÄÀÇ ÀϺθ¸ ´©±º°¡¿¡ ÀÇÇØ ±âÇÏÇÐÀûÀÎ Àǹ̸¦ ¶ì´Â ÇüÅ·Π¿¬´Þ¾Æ Áþ´­·Á ÀÖ´Â ¸ð½À. ¿Ü°èÀÎÀÇ ¼ÒÇàÀÎ °ÍÀ¸·Î ÃßÁ¤µÊ) ¹Ì¸£ÄÚ´Â ÀÌ ±«ÀÌÇÑ ¹«´Ì¿¡ °ü½ÉÀÌ ¸Å¿ì ¸¹´Ù.

±×·¯´ø ¾î´À ¿©¸§³¯ ¹ã, ±×´Â ÇÒ¸Ó´ÏÀÇ ¹ç¿¡ ÀڱⰡ ±×·± ¼­Å¬À» Á÷Á¢ ¸¸µé¾î º¸±â·Î ¸¶À½¸Ô¾ú´Ù. ±×´Â ±¹°¡¿¡ ´ëÇÑ ÀںνÉÀÌ ³²´Ù¸¥Áö¶ó ¸ð¾çµµ Å©·Î¾ÆƼ¾Æ ÀüÅë ¹®Àå¿¡ µé¾î°¡ Àִ ü½ºÆÇ ¹«´Ì·Î Á¤Çß´Ù. 13°³ÀÇ ºÓÀº Ä­°ú 12°³ÀÇ Èò Ä­ÀÌ ±³Â÷ÇÏ´Â 5x5 Å©±âÀÇ Ã¼½ºÆÇ ¸ð¾ç ¸ð´ÌÀÌ´Ù.

ÇÒ¸Ó´ÏÀÇ ¹çÀº N¡¿N°³ÀÇ Ä­À¸·Î ±¸¼ºµÈ Á¤»ç°¢Çü ¸ð¾çÀÌ´Ù. ÁÂÃø ÇÏ´ÜÀÌ ÁÂÇ¥»óÀ¸·Î (1, 1)ÀÌ°í ¿ìÃø »ó´ÜÀÌ (N, N)ÀÌ´Ù.

¹Ì¸£ÄÚ´Â ½ÇÁ¦ ü½ºÆÇ ¹«´Ì¿¡¼­ »¡°£»öÀ¸·Î Ä¥ÇØÁö´Â ºÎºÐ¿¡ ÇØ´çÇÏ´Â Ä­ÀÇ °î½Ä¸¸ Áþ´­·¯¼­ Ç¥°¡ ³ª°Ô Çß´Ù. ±× Å©±â´Â Ȧ¼ö M¡Ã3À» ÅÃÇؼ­ ü½ºÆÇÀÇ ÇÑ Á¤»ç°¢ÇüÀº ¹ç¿¡¼­ M¡¿M¸¸Å­ÀÇ Ä­À» Â÷ÁöÇÏ°Ô ¼³Á¤Çß´Ù. ¹°·Ð ±×·¸°Ô ±×·ÁÁø 5¡¿5 Å©±âÀÇ Ã¼½ºÆÇ Àüü(µû¶ó¼­ ÇÑ º¯ÀÇ ±æÀÌ´Â 5M)°¡ ¹ç ¾È¿¡ À߸®´Â ¿µ¿ª ¾øÀÌ ¸ðµÎ µé¾î°£´Ù.

±×·¸°Ô ¹ç¿¡´Ù ü½ºÆÇ ¹«´Ì ¡®¹Ì½ºÅ͸® ¼­Å¬¡¯À» ¸¸µé¾î ³õÀº µÚ ¹Ì¸£ÄÚ´Â Àáµé¾ú´Ù. ±× »çÀÌ¿¡ ÀÌ ¹«´Ì´Â ±×ÀÇ ¹Ù¶÷´ë·Î ÁøÂ¥ ¿Ü°èÀεéÀÇ ½Ã¼±À» »ç·ÎÀâ°Ô µÇ¾ú´Ù. ±×µéÀº ¹ç À§¸¦ °í°ø ºñÇàÇϸ鼭 Ư¼öÇÑ Àåºñ·Î ¹çÀÇ »óŸ¦ ÃøÁ¤Çϱ⠽ÃÀÛÇߴµ¥, ÀÌ Àåºñ´Â ÇÑ ¹ø¿¡ ¹çÀÇ ÇÑ Ä­ÀÇ »óŸ¸À» ÃøÁ¤ÇÒ ¼ö ÀÖ´Ù. (°î½ÄÀÌ Áþ´­·È´ÂÁöÀÇ ¿©ºÎ)

¿Ü°èÀεéÀº ¾à°£ÀÇ ³ë·Â ³¡¿¡ °î½ÄÀÌ Áþ´­·Á ÀÖ´Â ÇÑ Ä­À» ã¾Æ³Â´Ù. ÇÏÁö¸¸ MÀÇ °ª(ü½ºÆÇ Á¤»ç°¢Çü Çϳª°¡ Â÷ÁöÇÏ´Â Å©±â)µµ ¸ð¸£°í ÀÌ Á¤º¸¸¸À¸·Î´Â ¾ÆÁ÷ ü½ºÆÇ ¹«´ÌÀÇ Çüü¸¦ ÆľÇÇϱ⿡ ¸Å¿ì ºÎÁ·ÇÏ´Ù. ¿©·¯ºÐÀº ¿Ü°èÀεéÀÌ ¹Ì¸£ÄÚÀÇ °ÉÀÛÇ°À» º¸¸é¼­ ¸¶À½²¯ °¨ÅºÇÒ ¼ö ÀÖµµ·Ï ±×µéÀ» µµ¿Í¾ß ÇÑ´Ù.

¹çÀÇ Å©±â N (15¡ÂN¡Â2,000,000,000)°ú °î½ÄÀÌ Áþ´­·Á ÀÖ´Â ½ÃÀÛÁ¡ÀÇ À§Ä¡ (X0, Y0)¸¦ ÀÔ·Â ¹Þ°í, ¿Ü°èÀÎÀÇ Æ¯¼ö Àåºñ¸¦ µ¿¿øÇÏ¿© ÀÌ ¹ç¿¡ ÀÖ´Â ¹Ì¸£ÄÚÀÇ Ã¼½ºÆÇ ¹«´ÌÀÇ Á¤Áß¾ÓÀ» ã´Â ÇÁ·Î±×·¥À» ÀÛ¼ºÇϽÿÀ. ÇÑ Å×½ºÆ® ÄÉÀ̽º¿¡ ´ëÇؼ­ À§Ä¡ Äõ¸®´Â ÃÖ´ë 300¹ø±îÁö ÇÒ ¼ö ÀÖ´Ù.

ÀÔÃâ·Â

ÀÌ ¹®Á¦´Â ´ëÈ­ÇüÀÌ´Ù. Ç¥ÁØ Ãâ·Â ½ºÆ®¸²À» ÅëÇØ ¿Ü°èÀÎ Àåºñ¿¡´Ù ¸í·ÉÀ» º¸³»°í, Ç¥ÁØ ÀÔ·Â ½ºÆ®¸²À» ÅëÇØ ±× Àåºñ·ÎºÎÅÍ ÀÀ´äÀ» ¾òÀ¸¸é µÈ´Ù.

äÁ¡ ÇÁ·Î±×·¥°ú ¿øÈ°È÷ ÀÇ»ç ¼ÒÅëÇϱâ À§Çؼ­´Â ¹®ÀÚ¿­À» Ãâ·ÂÇÑ µÚ¿¡ ¾ðÁ¦³ª Ç¥ÁØ Ãâ·Â ½ºÆ®¸²À» flushÇØ ÁÖ¾î¾ß ÇÑ´Ù. ÇÔ²² Á¦°øµÇ´Â ¿¹Á¦ Äڵ忡 ¾ð¾îº°·Î ±¸Ã¼ÀûÀÎ ¿ä·ÉÀÌ ³ª¿Í ÀÖ´Ù. ÀÌ ÄÚµå´Â äÁ¡ ½Ã½ºÅÛ°ú ÀÇ»ç ¼ÒÅëÇÏ´Â ¿¹¸¸À» º¸¿©ÁÙ »Ó Á¤È®ÇÑ ´äÀ» ±¸ÇÏ´Â ´ä¾È ÇÁ·Î±×·¥ÀÌ ¾Æ´ÔÀ» À¯ÀÇÇϱ⠹ٶõ´Ù.

¸ðµç Å×½ºÆ® ÄÉÀ̽º´Â ¼öÇèÀÚÀÇ ´ä¾È ÇÁ·Î±×·¥ÀÌ ¾î¶² ÇüÅ·ΠÄõ¸®¸¦ ÇÏµç »ó°ü¾øÀÌ À¯ÀÏÇÑ Á¤´äÀ» ±¸ÇÒ ¼ö ÀÖ´Â ÇüÅÂÀÌ´Ù. ¶ÇÇÑ, Å×½ºÆ® ÄÉÀ̽º Áß ÀüüÀÇ 40Á¡¿¡ ÇØ´çÇÏ´Â ÄÉÀ̽º´Â ü½ºÆÇ Á¤»ç°¢ÇüÀÇ Å©±â MÀÌ 100º¸´Ù ÀÛ´Ù.

¿¹Á¦

´ÙÀ½Àº ¾ÕÀÇ ±×¸²°ú °°Àº ¼³Á¤¿¡¼­ ´ä¾È ÇÁ·Î±×·¥ÀÌ ÀÔÃâ·ÂÀ» ÁÖ°í ¹ÞÀ¸¸ç ´äÀ» ±¸ÇØ °¡´Â °úÁ¤À» ³ªÅ¸³½ °ÍÀÌ´Ù.

Ãâ·Â (¸í·É) ÀÔ·Â (ÀÀ´ä)
¡¡ 19 7 4¡¡
examine 11 2 true¡¡
examine 2 5 false
examine 9 14 false
examine 18 3 true
solution 12 9 ¡¡

Å×½ºÆ®

´ëȸ ÁøÇà Áß¿¡ ¼öÇèÀÚ°¡ ÀÚ½ÅÀÇ ´ä¾È ÇÁ·Î±×·¥À» Å×½ºÆ®ÇÏ´Â ¹æ¹ýÀº ¼¼ °¡Áö°¡ ÀÖ´Ù.

°¡Àå °£´ÜÇÑ ¹æ¹ýÀº ÇÁ·Î±×·¥ÀÌ ÀüÀûÀ¸·Î Ç¥ÁØ ÀÔÃâ·Â¿¡ ÀÇÁ¸ÇÏ´Â ¸¸Å­, Å°º¸µå·Î ¼öÇèÀÚ°¡ Á÷Á¢ ¿Ü°èÀÎÀÇ Àåºñ¸¦ °¡Á¤ÇÏ¿© ÇÁ·Î±×·¥¿¡ Á¤º¸¸¦ °ø±ÞÇÏ´Â °ÍÀÌ´Ù.

µÑ°´Â ¿Ü°èÀÎÀÇ Àåºñ¸¦ Èä³»³»´Â ÇÁ·Î±×·¥À» º°µµ·Î ÀÛ¼ºÇÏ´Â °ÍÀÌ´Ù. ´ä¾È ÇÁ·Î±×·¥°ú ±× Àåºñ ÇÁ·Î±×·¥À» »óÈ£ ¿¬°áÇØ ÁÖ´Â "connect"¶ó´Â À¯Æ¿¸®Æ¼°¡ ÁÖÃÖÃø ½Ã½ºÅÛ¿¡¼­ Á¦°øµÇ°í ÀÖÀ¸¹Ç·Î À̸¦ È°¿ëÇÏ¸é µÈ´Ù. ÇÁ·Î±×·¥À» ½ÇÇàÇÒ ¶§ "./connect ./´ä¾ÈÇÁ·Î±×·¥¸í ./ÀåºñÇÁ·Î±×·¥¸í" ½ÄÀ¸·Î ¸í·ÉÀ» ³»¸®µµ·Ï ÇÑ´Ù. ±× ÀÌÈÄÀÇ ¸Å°³º¯¼öµéÀº ¸ðµÎ Àåºñ ÇÁ·Î±×·¥¿¡ ±×´ë·Î Àü´ÞµÈ´Ù.

¼Â°´Â äÁ¡ ½Ã½ºÅÛ¿¡ ÀÖ´Â TEST ±â´ÉÀ» ÀÌ¿ëÇÏ¿©, äÁ¡ ½Ã½ºÅÛÀÌ ¼öÇèÀÚ°¡ ¼³Á¤ÇØ ³õÀº Á¤´ä(ÁöÁ¤µÈ M °ª°ú ÁöÁ¤µÈ Á¤Áß¾Ó À§Ä¡)À» °¡Á¤ÇÏ¿© ´ä¾È ÇÁ·Î±×·¥ÀÇ Äõ¸®¿¡ ÀÀ´äÇÏ°Ô ÇÏ´Â °ÍÀÌ´Ù. ´Ü, ÀÌ ±â´ÉÀº ¹çÀÇ Å©±â NÀ» ÃÖ´ë 100±îÁö·Î¸¸ ¼³Á¤ÇÒ ¼ö ÀÖ´Ù.

Å×½ºÆ® ÄÉÀ̽º¿¡´Â ¼¼ ÁÙÀÌ ÀÖ¾î¾ß ÇÑ´Ù.

äÁ¡ ½Ã½ºÅÛÀº ´ä¾È ÇÁ·Î±×·¥°ú ÀÔÃâ·ÂÀ» ÁÖ°í¹ÞÀº °á°ú¸¦ »ó¼¼ÇÑ ·Î±× ÆÄÀÏ·Î ¾Ë·ÁÁÙ »Ó¸¸ ¾Æ´Ï¶ó ¾Æ·¡ÀÇ »óȲó·³ Å×½ºÆ® ÄÉÀ̽º ÀÚü¿¡ À߸øÀÌ ÀÖÀ» ¶§¿¡µµ ¿¡·¯ ¸Þ½ÃÁö¸¦ Ãâ·ÂÇØ ÁØ´Ù.

´ÙÀ½Àº ¾ÕÀÇ ±×¸²°ú °°Àº ¼³Á¤À» Å×½ºÆ® ÄÉÀ̽º·Î ³ªÅ¸³½ ¿¹ÀÌ´Ù.

19 3
7 4
12 9


2. È«¼ö ½Ã¹Ä·¹À̼Ç

Áö³­ 1964³â¿¡´Â ±â·ÏÀûÀÎ ´ëÈ«¼ö°¡ ÀÚ±×·¹ºê ½Ã°¡Áö¸¦ °­Å¸Çß¾ú´Ù. À̶§ °Ç¹°ÀÌ ¸¹ÀÌ Æı«µÇ¾ú´Âµ¥, ÀÌ´Â ¹°ÀÇ ÇÏÁßÀ¸·Î ÀÎÇØ °Ç¹°À» ÀÌ·ç´Â º®ÀÌ ºØ±«Ç߱⠶§¹®ÀÌ´Ù. À̹ø ¹®Á¦¿¡¼­´Â ±×·± µµ½Ã ÇüŸ¦ ´Ü¼øÇÏ°Ô ¸ðµ¨È­ÇÑ Á¤º¸°¡ ÀÔ·ÂÀ¸·Î µé¾î¿Â´Ù. ¿©·¯ºÐÀº À̸¦ Åä´ë·Î ¾î¶² º®ÀÌ È«¼ö ÈÄ¿¡µµ ºØ±« ¾øÀÌ Á¸¼ÓÇÒ °ÍÀÎÁö¸¦ ã¾Æ¾ß ÇÑ´Ù.

ÀÌ ¸ðµ¨Àº ÁÂÇ¥Æò¸é »ó¿¡¼­ N°³ÀÇ Á¡°ú W°³ÀÇ º®À¸·Î Ç¥ÇöµÈ´Ù. º®Àº ±× N°³ÀÇ Á¡ Áß µÑÀ» ¿¬°áÇÑ ¼±ÀÇ ÇüÅ·ΠÁ¸ÀçÇϴµ¥, ±× ¼±Àº Áß°£¿¡ ´Ù¸¥ Á¡À» °üÅëÇÏÁö ¾ÊÀ¸¸ç ´Ù¸¥ ¼±°ú °ãÄ¡°Å³ª ±³Â÷ÇÏÁöµµ ¾Ê´Â´Ù. ´ÜÁö ¼±ÀÇ ³¡Á¡¸¸ÀÌ ¼­·Î °ãÄ¥ ¼ö ÀÖ´Ù. ¶ÇÇÑ ¼±Àº ÁÂÇ¥Æò¸é »ó¿¡¼­ ¼öÆò¼±À̳ª ¼öÁ÷¼±À¸·Î¸¸ Á¸ÀçÇÑ´Ù.

¸ðµ¨ÀÇ Ãʱ⠻óÅ´ ºñ°¡ ¿À±â ÀüÀ¸·Î ¸ðµç Æò¸éÀÌ À°ÁöÀÌ´Ù. ±×·¯´Ù 0À̶ó´Â ½Ã°¢¿¡ È«¼ö°¡ ½ÃÀ۵Ǿî, º®À¸·Î »ç¹æÀÌ µÑ·¯½ÎÀÌÁö ¾ÊÀº ¸ðµç ¿Ü°ûÀÌ ¹°·Î µÚµ¤ÀδÙ. ±×·ÎºÎÅÍ Á¤È®È÷ 1½Ã°£ ÈÄ¿¡´Â ¹°°ú À°ÁöÀÇ ¾ç¸é °æ°è¸¦ ÀÌ·ç°í ÀÖ´ø º®ÀÌ ¼ö¾ÐÀ» °ßµðÁö ¸øÇÏ°í ¸ðµÎ ¹«³ÊÁø´Ù. º®ÀÌ ¹«³ÊÁüÀ¸·Î½á °æ°è°¡ ¾ø¾îÁø °÷¿¡´Â À̳» ¹°ÀÌ ´õ ±í¼÷ÀÌ µé¾î¿À°í, ¹«³ÊÁø º®ÀÇ ³»ºÎ¿¡ ÀÖ´ø ´Ù¸¥ º®ÀÌ À°Áö¿Í ¹°ÀÇ °æ°è°¡ µÈ´Ù. ÀÌ º®µµ ¿ª½Ã 1½Ã°£ÀÌ ´õ Áö³ª¸é ¹«³ÊÁú °ÍÀÌ´Ù. ÀÌ °úÁ¤ÀÌ µÇÇ®À̵ÊÀ¸·Î½á °á±¹ ¹«³ÊÁú º®Àº ´Ù ¹«³ÊÁö°í ¸ðµç ¿µ¿ª¿¡ ¹°ÀÌ Â÷°Ô µÈ´Ù.

´ÙÀ½Àº Áö±Ý±îÁö ¼³¸íÇÑ µµ½Ã ¸ðµ¨ÀÇ ÇÑ ¿¹¸¦ ¹¦»çÇÑ °ÍÀÌ´Ù.

N°³ÀÇ Á¡ÀÇ ÁÂÇ¥¿Í À̵é Á¡À» ¿¬°áÇÏ´Â W°³ÀÇ º®¿¡ ´ëÇÑ Á¤º¸¸¦ ÀÔ·Â ¹Þ¾Æ, À̵é Áß È«¼ö ÈÄ¿¡µµ ¹«³ÊÁöÁö ¾Ê°í ³²¾Æ ÀÖ´Â º®ÀÌ ¹«¾ùÀÎÁö ã´Â ÇÁ·Î±×·¥À» ÀÛ¼ºÇϽÿÀ.

ÀÔ·Â

ù° ÁÙ¿¡´Â Á¤¼ö N (2¡ÂN¡Â100,000)ÀÇ °ªÀÌ µé¾îÀÖ´Ù. ÁÂÇ¥Æò¸é¿¡ ÀÖ´Â Á¡ÀÇ °³¼öÀÌ´Ù. ´ÙÀ½ N°³ÀÇ ÁÙ¿¡´Â 1ºÎÅÍ N°±îÁö °¢ Á¡ÀÇ X, Y ÁÂÇ¥°¡ Çϳª¾¿ µé¾îÀÖ´Ù. ¹üÀ§´Â 0 ÀÌ»ó 1,000,000 ÀÌÇÏÀÌ´Ù. Á¡µéÀÇ À§Ä¡´Â ¸ðµÎ ´Ù¸£¸ç, µÎ Á¡ÀÌ °°Àº ÁöÁ¡¿¡ °ãÄ¡´Â °æ¿ì´Â ¾ø´Ù.

´ÙÀ½ ÁÙ¿¡´Â º®ÀÇ °³¼ö W (1¡ÂW¡Â2N)ÀÇ °ªÀÌ µé¾îÀÖ´Ù. ±×¸®°í ´ÙÀ½ W°³ÀÇ ÁÙ¿¡´Â ¼­·Î ´Ù¸¥ Á¤¼ö A, B (1¡ÂA¡ÂN, 1¡ÂB¡ÂN)°¡ ÀÖÀ¸¸ç ÀÌ´Â Ãʱ⠻óÅ¿¡ ÀÌ ¸ðµ¨¿¡ A° Á¡°ú B° Á¡À» ¿¬°áÇÏ´Â º®ÀÌ Á¸ÀçÇÔÀ» ³ªÅ¸³½´Ù. º® ¿ª½Ã 1ºÎÅÍ W±îÁö Àд ¼ø¼­´ë·Î ¼­¿­À» ¸Å±â¸é µÈ´Ù.

15
1 1
8 1
4 2
7 2
2 3
4 3
6 3
2 5
4 5
6 5
4 6
7 6
1 8
4 8
8 8
17
1 2
2 15
15 14
14 13
13 1
14 11
11 12
12 4
4 3
3 6
6 5
5 8
8 9
9 11
9 10
10 7
7 6

Ãâ·Â

ù° ÁÙ¿¡´Â È«¼ö ÈÄ¿¡µµ ³²¾Æ ÀÖ´Â º®ÀÇ °³¼ö K¸¦ Ãâ·ÂÇÑ´Ù. ±×¸®°í ´ÙÀ½ K°³ÀÇ ÁÙ¿¡´Â ±× º®ÀÇ ¼­¿­ ¹øÈ£¸¦ ÇÑ ÁÙ¿¡ Çϳª¾¿ Ãâ·ÂÇÑ´Ù. ¾Æ¹« ¼ø¼­·Î³ª Ãâ·ÂÇصµ ¹«¹æÇÏ´Ù. (¸Þ¸ð¸® Á¦ÇÑ: 32MB, ½Ã°£ Á¦ÇÑ: 2ÃÊ)

4
6
15
16
17

Å×½ºÆ® ÄÉÀ̽º Áß ÀüüÀÇ 40Á¡¿¡ ÇØ´çÇÏ´Â ÄÉÀ̽º´Â ÁÂÇ¥ÀÇ ÃÖ´ë ¹üÀ§°¡ 500ÀÌ´Ù. (1¹é¸¸º¸´Ù ÈξÀ ÀÛÀº) ±×¸®°í À§ÀÇ ÄÉÀ̽º»Ó¸¸ ¾Æ´Ï¶ó ³ª¸ÓÁö 15Á¡¿¡ ÇØ´çÇÏ´Â Ãß°¡ ÄÉÀ̽º´Â(ÃÑ 55Á¡) Á¡ NÀÇ ÃÖ´ë °³¼ö°¡ 500ÀÌ´Ù.

ÇÁ·Î±×·¥ ÀÛ¼ºÀÇ ÆíÀǸ¦ µµ¸ðÇϱâ À§ÇØ, ÀÌ ¹®Á¦´Â ´ëȸ ÁøÇà Áß¿¡ ºÎºÐÀûÀ¸·Î ¿¹ºñ äÁ¡ÀÌ °¡´ÉÇÏ´Ù. ¼öÇèÀÚ´Â ÀÛ¼ºÇÏ°í ÀÖ´Â ÇÁ·Î±×·¥À» ÃÖ´ë 10¹ø±îÁö Á¦ÃâÇؼ­ Á¤½Ä äÁ¡ ¶§ ¾²ÀÌ´Â Å×½ºÆ® ÄÉÀ̽ºÀÇ ÀϺο¡ ´ëÇÑ Ã¤Á¡ °á°ú¸¦ ÅëÁö ¹ÞÀ» ¼ö ÀÖ´Ù.


3. µÀ´Ü¹è

»õ·Î¿î ÇØÀû¼±ÀÌ °ÇÁ¶ ÁßÀÌ´Ù. ¹è¿¡´Â ±æÀÌ°¡ ´Ù¸¥ N°³ÀÇ µÀ´ë°¡ ÀÖ´Ù. °¢ µÀ´ë´Â ´ÜÀ§ ±æÀÌ¿¡ ÇØ´çÇÏ´Â ¸¶µð·Î ³ª´µ¸ç µÀ´ëÀÇ ³ôÀÌ´Â ¾ðÁ¦³ª ±× ´ÜÀ§ ±æÀÌÀÇ ¹è¼öÀÌ´Ù. µÀ´ë¿¡ ²ÈÈ÷´Â µÀÀº ±ÕÀÏÇÑ Å©±â·Î¼­ ±× ³ôÀÌ°¡ ´ÜÀ§ ±æÀÌ¿Í ÀÏÄ¡ÇÏ°í, Á¤È®ÇÏ°Ô µÀ´ëÀÇ °¢ ¸¶µð¿¡ ²À ¸Â°Ô¸¸ ÀåÂøµÈ´Ù. µÀÀº ±×·± ½ÄÀ¸·Î µÀ´ëÀÇ ¾Æ¹« ¸¶µð¿¡³ª °í¸£°Ô ÀåÂøÇÒ ¼ö ÀÖÁö¸¸ µÀ´ëÀÇ ¸¶µð Çϳª¿¡´Â µÀÀ» ÃÖ´ë Çϳª¸¸ ´Þ ¼ö ÀÖ´Ù.

¹è´Â µÚ¿¡¼­ ºÒ¾î¿À´Â ¹Ù¶÷À» ¹Þ°í ¾ÕÀ¸·Î ¹Ð·Á ³ª¾Æ°¡´Âµ¥, °°Àº ¹Ù¶÷À» ¹Þ¾Æµµ µÀÀ» ¾î¶»°Ô ´Ù³Ä¿¡ µû¶ó ¹è°¡ ¹Þ´Â µ¿·ÂÀÌ ´Þ¶óÁø´Ù. ÁøÇà ¹æÇâÀ» ±âÁØÀ¸·Î ¾ÕÂÊ¿¡ ÀÖ´Â µÀÀº °°Àº ³ôÀÌ¿¡ ÀÖ´Â µÚÂÊ µÀ¿¡ °¡·Á¼­ ¹Ù¶÷À» µÚÂʺ¸´Ù ´ú ¹Þ°Ô µÇ°í, ±×¸¸Å­ µÀÀ¸·Î¼­ÀÇ ¿ªÇÒÀ» Á¦´ë·Î ¸ø ÇÏ°Ô µÈ´Ù.

ÀÌ¿¡ ¿ì¸®´Â °¢ µÀ¿¡ ´ëÇØ ¡®ºñÈ¿À² Áö¼ö¡¯¶ó´Â °³³äÀ» Á¤ÀÇÇϱâ·Î ÇÑ´Ù. ±× µÀ°ú ³ôÀÌ°¡ °°À¸¸é¼­ µÚ¿¡ ÀÖ´Â µÀÀÇ °³¼ö¸¦ ¸»ÇÑ´Ù. ¶ÇÇÑ ¹èÀÇ ¡®Àüü ºñÈ¿À² Áö¼ö¡¯¶õ, ±× ¹èÀÇ ¸ðµç µÀÀÇ ºñÈ¿À² Áö¼öÀÇ ÇÕÀ» ÀÏÄ´´Ù.

¹è¿¡ ¼¼¿ì°íÀÚ ÇÏ´Â µÀ´ëÀÇ °³¼ö¿Í °¢°¢ÀÇ ³ôÀÌ, ±×¸®°í °¢ µÀ´ë¸¶´Ù ´Þ°íÀÚ ÇÏ´Â µÀÀÇ °³¼ö¸¦ ÀÔ·Â ¹Þ¾Æ¼­ ±× ¹è°¡ ±¸Á¶ÀûÀ¸·Î °¡Áú ¼ö ÀÖ´Â ÃÖ¼Ò ¡®Àüü ºñÈ¿À² Áö¼ö¡¯¸¦ °è»êÇÏ´Â ÇÁ·Î±×·¥À» ÀÛ¼ºÇϽÿÀ.

ÀÔ·Â

ù° ÁÙ¿¡´Â µÀ´ëÀÇ °³¼ö N (2¡ÂN¡Â100,000)ÀÇ °ªÀÌ µé¾îÀÖ´Ù. ±×¸®°í ´ÙÀ½ N°³ÀÇ ÁÙ¿¡´Â Á¤¼ö H¿Í K (1¡ÂH¡Â100,000; 1¡ÂK¡ÂH)°¡ Àִµ¥ °¢°¢ µÀ´ëÀÇ ³ôÀÌ¿Í ±× µÀ´ë¿¡ ÀåÂøµÇ´Â µÀÀÇ °³¼öÀÌ´Ù. µÀ´ë¿¡ ´ëÇÑ Á¤º¸´Â ÁøÇà ¹æÇâÀ» ±âÁØÀ¸·Î ¾Õ¿¡¼­ µÚ·Î °¡´Â ¼ø¼­·Î ³ª¿Í ÀÖ´Ù.

6
3 2
5 3
4 1
2 1
4 3
3 2

Ãâ·Â

ÀÌ ¹èÀÇ ÃÖ¼Ò Àüü ºñÈ¿À² Áö¼ö Çϳª¸¸À» Ãâ·ÂÇÏ¸é µÈ´Ù. (¸Þ¸ð¸® Á¦ÇÑ: 64MB, ½Ã°£ Á¦ÇÑ: 1ÃÊ)

10

ÁÖÀÇ: 64ºñÆ® Á¤¼ö¸¦ »ç¿ëÇϵµ·Ï ÇÑ´Ù. (C/C++¿¡¼­´Â long long, ÆĽºÄ®¿¡¼­´Â int64)

Å×½ºÆ® ÄÉÀ̽º Áß ÀüüÀÇ 25Á¡¿¡ ÇØ´çÇÏ´Â ÄÉÀ̽º´Â µÀÀ» µÀ´ë¿¡ ¹èÄ¡ÇÏ´Â Á¶ÇÕ °¡Áþ¼ö°¡ 1¹é¸¸ °¡Áö ÀÌÇÏÀÌ´Ù.


4. ±¤ºÎµéÀÇ ½Ä»ç

¼®ÅºÀ» ij´Â ±¤»êÀÌ µÎ ±ºµ¥ ÀÖ°í, °¢ ±¤»ê¿¡´Â ±¤ºÎµéÀÌ ÀÛ¾÷À» ÇÏ°í ÀÖ´Ù. ä±¼ ÀÛ¾÷Àº °íµÈ ÀÏÀ̱⠶§¹®¿¡ ±¤ºÎ¿¡°Ô´Â À½½ÄÀ» ÅëÇÑ Áö¼ÓÀûÀÎ ¿µ¾ç ¼·Ãë°¡ ÇÊ¿äÇÏ´Ù. ¸Å ½Ã°¢¸¶´Ù ÇÑ À½½Ä ¼¼Æ®°¡ µµÂøÇÏ°í À̸¦ °ø±Þ ¹ÞÀº ±¤ºÎµéÀº ÀÏÁ¤·®ÀÇ ¼®ÅºÀ» »ý»êÇØ ³½´Ù. À½½Ä ¼¼Æ®¿¡´Â °í±â, »ý¼±, »§ ÀÌ·¸°Ô ¼¼ Á¾·ù°¡ ÀÖ´Ù.

±¤ºÎµéÀº ´Ù¾çÇÑ ¸Þ´º·Î ½Ä»ç¸¦ ÇÏ°í ½Í¾îÇϱ⠶§¹®¿¡ ³¢´Ï¸¶´Ù À½½Ä ¼¼Æ®°¡ Á¦°¢°¢Àϼö·Ï ÀÛ¾÷ »ý»ê¼ºÀÌ ¿Ã¶ó°£´Ù. À̸¦ ±¸Ã¼ÀûÀ¸·Î Ç¥ÇöÇϸé ÀÌ·¸´Ù. À½½Ä ¼¼Æ®°¡ Çϳª µµÂøÇϸé À̸¦ ¸Ô°í ±¤ºÎµéÀÌ ÀÛ¾÷À» Çؼ­ ¼®ÅºÀ» »ý»êÇϴµ¥, ±× »ý»ê·®Àº Áö±Ý ¸ÔÀº À½½Ä ¼¼Æ®¿Í ±× Àü°ú ±× ÀüÀü¿¡ ¸ÔÀº À½½Ä ¼¼Æ®(¸¸¾à ±×·± ÀûÀÌ ÀÖ´Ù¸é) ÀÌ·¸°Ô ÃÖ´ë ¼¼ ¼¼Æ®¸¦ ºñ±³ÇßÀ» ¶§,

¸Å ½Ã°¢¸¶´Ù ¾ÕÀ¸·Î ¾î¶² À½½Ä ¼¼Æ®°¡ ¼ø¼­´ë·Î °ø±ÞµÉ °ÍÀÎÁö ½ºÄÉÁÙÀÌ ³ª¿Í ÀÖ´Ù. ±× ¼ø¼­ ÀÚü¸¦ ¹Ù²Ü ¼ö´Â ¾øÁö¸¸ ¾î¶² À½½ÄÀ» µÎ ±¤»ê Áß ¾îµð¿¡ º¸³¾Áö¸¦ ÀûÀýÈ÷ Á¶ÀýÇÔÀ¸·Î½á ±¤ºÎµé¿¡°Ô ÃÖ´ëÇÑ ±ÕÇü ÀâÈù ½Ä´ÜÀ» Á¦°øÇÒ ¼ö ÀÖ°í, ÀÌ°ÍÀÌ ±¤»ê ä±¼ È¿À²À» ±Ø´ëÈ­ÇÒ ¼ö ÀÖ´Ù. À½½Ä ¼¼Æ® Çϳª¸¦ µÑ·Î ³ª´­ ¼ö´Â ¾øÀ¸¸ç ¾îÂ÷ÇÇ °°Àº ½Ã°£¿£ À½½ÄÀ» ¹ÞÀº ÇÑ ±¤»ê¿¡¼­¸¸ ÀÛ¾÷ÀÌ ÁøÇàµÈ´Ù.

µÎ ±¤»ê¿¡ ±ÕÇü ÀâÈù Ƚ¼ö³ª °£°ÝÀ¸·Î À½½ÄÀ» °ø±ÞÇØ¾ß ÇÒ ÇÊ¿ä´Â ¾ø´Ù. ÇÑ ±¤»êÀ» ÇÑÂü µ¿¾È ³î¸®°í À־ µÇ°í, ¾Æ¿¹ ÇÑ °÷¿¡´Ù°¡¸¸ °ø±ÞÀ» ¿ÃÀÎÇصµ ±¦Âú´Ù. ¿À·ÎÁö ƯÁ¤ ±¤»ê¿¡ À½½ÄÀ» °ø±ÞÇÒ ¶§, ¿¹Àü°ú ºñ±³Çؼ­ ¸Þ´ºÀÇ ´Ù¾ç¼º¸¸ º¸ÀåµÇ¸é µÈ´Ù.

±¤»ê¿¡ °ø±ÞµÇ´Â À½½Ä ¼¼Æ® ¸®½ºÆ®¸¦ ÀÔ·Â ¹Þ¾Æ, À̸¦ µÎ ±¤»ê¿¡ Àû´çÇÑ ¼ø¼­·Î º¸³ÂÀ» ¶§ Ķ ¼ö ÀÖ´Â ¼®ÅºÀÇ ÃÖ´ë·®À» °è»êÇÏ´Â ÇÁ·Î±×·¥À» ÀÛ¼ºÇϽÿÀ.

ÀÔ·Â

ù° ÁÙ¿¡´Â À½½Ä ¼¼Æ®ÀÇ ÃÑ °³¼ö N (1¡ÂN¡Â100,000)ÀÇ °ªÀÌ µé¾îÀÖ´Ù. ±×¸®°í µÑ° ÁÙ¿¡´Â ½Ã°£ ¼øÀ¸·Î °ø±ÞµÇ´Â À½½Ä ¼¼Æ®¸¦ ÀǹÌÇÏ´Â ¹®ÀÚ¿­ÀÌ N ±ÛÀÚ µé¾îÀÖ´Ù. ¹®ÀÚ´Â ´ë¹®ÀÚ·Î M(°í±â), F(»ý¼±), B(»§) ÀÌ·¸°Ô ¼Â Áß ÇϳªÀÌ´Ù.

#1 #2
6
MBMFFB
16
MMBMBBBBMMMMMBMB

Ãâ·Â

ÀÌ °ø±Þ ÇÏ¿¡¼­ °¡´ÉÇÑ ¼®ÅºÀÇ ÃÖ´ë ä±¼·®À» Á¤¼ö Çϳª·Î Ãâ·ÂÇÑ´Ù.  (¸Þ¸ð¸® Á¦ÇÑ: 16MB, ½Ã°£ Á¦ÇÑ: 1.5ÃÊ)

#1 #2
12 29

ÀÔ·Â ¿¹Á¦ #1À» »ìÆ캸ÀÚ(M1B2M3F4F5B6). À½½Ä ¼¼Æ®¸¦ °¢°¢ 1, 1, 2, 2, 1, 2¹ø ±¤»êÀÇ ¼øÀ¸·Î º¸³¾ °æ¿ì 1¹ø ±¤»ê¿¡´Â M1B2F5, 2¹ø ±¤»ê¿¡´Â M3F4B6°¡ °ø±ÞµÇ¾î µÎ ±¤»ê¿¡ ¸ðµÎ ¼­·Î ´Ù¸¥ ½Ä»ç°¡ Á¦°øµÇ°í µû¶ó¼­ ä±¼·®µµ 1, 2, 3ÀÇ ¼øÀ¸·Î ¿Ã¶ó°£´Ù. ±×·¡¼­ ÃÖ´ë ä±¼·®Àº 1+2+3°ú 1+2+3ÀÇ ÇÕÀÎ 12°¡ µÈ´Ù. ¹°·Ð 1, 2, 2, 2, 1, 1 °°Àº ´Ù¸¥ ¼ø¼­·Îµµ ÃÖ´ë ä±¼·®À» ´Þ¼ºÇÒ ¼ö ÀÖ´Ù.

Å×½ºÆ® ÄÉÀ̽º Áß ÀüüÀÇ 45Á¡¿¡ ÇØ´çÇÏ´Â ÄÉÀ̽º´Â NÀÇ °ªÀÌ ÃÖ´ë 20ÀÌ´Ù.

ÇÁ·Î±×·¥ ÀÛ¼ºÀÇ ÆíÀǸ¦ µµ¸ðÇϱâ À§ÇØ, ÀÌ ¹®Á¦´Â ´ëȸ ÁøÇà Áß¿¡ ºÎºÐÀûÀ¸·Î ¿¹ºñ äÁ¡ÀÌ °¡´ÉÇÏ´Ù. ¼öÇèÀÚ´Â ÀÛ¼ºÇÏ°í ÀÖ´Â ÇÁ·Î±×·¥À» ÃÖ´ë 10¹ø±îÁö Á¦ÃâÇؼ­ Á¤½Ä äÁ¡ ¶§ ¾²ÀÌ´Â Å×½ºÆ® ÄÉÀ̽ºÀÇ ÀϺο¡ ´ëÇÑ Ã¤Á¡ °á°ú¸¦ ÅëÁö ¹ÞÀ» ¼ö ÀÖ´Ù.


5. °¡±î¿î ¦ ã±â

¹Ì¸£ÄÚ¿Í ½½¶óºêÄÚ´Â µ¿¹° ¸ð¾çÀÇ Àå³­°¨À» °®°í ³î°í ÀÖ´Ù. ³ë´Â ¹æ¹ýÀº ´ÙÀ½°ú °°´Ù. ¸ÕÀú ¾Æ·¡ ±×¸²°ú °°Àº ¼¼ °³ÀÇ °ÔÀÓÆÇ(1~3Â÷¿ø Ä­À¸·Î µÈ ±ÕÀÏ °£°Ý °ÝÀÚ) Áß Çϳª¸¦ °í¸¥´Ù. ±×¸®°í °ÔÀÓÆÇ ³»ºÎ ÀÓÀÇÀÇ Ä­(±×¸²¿¡¼­ µ¿±×¶ó¹Ì·Î Ç¥ÇöµÈ)¿¡ N°³ÀÇ µ¿¹° Àå³­°¨À» Áý¾î³Ö´Â´Ù.

±×¸²¿¡¼­ º¸´Ù½ÃÇÇ ¾î¶² Ä­¿¡¼­ ÀÎÁ¢ÇÑ Ä­Àº °¢ Â÷¿øÀÇ Ãà°ú ÆòÇàÇÑ ¼±ºÐÀ¸·Î¸¸ ¿¬°áµÇ¾î Àִµ¥, µÎ Ä­ÀÇ ¡®°Å¸®¡¯´Â ´Ù¸¥ Ä­À¸·Î °¡±â À§ÇØ °ÅÃÄ¾ß ÇÏ´Â ¼±ºÐÀÇ ÃÖ¼Ò °³¼ö·Î Á¤ÀǵȴÙ. ´Ù½Ã ¸»ÇØ 3Â÷¿øÀ» ¿¹·Î µé ¶§ ÀÓÀÇÀÇ À§Ä¡¿¡ ÀÖ´Â Ä­ A(x1, y1, z1)¿Í B(x2, y2, z2)ÀÇ °Å¸®´Â ´Ü¼øÈ÷ |x1-x2|+|y1-y2|+|z1-z2|°¡ µÇ¸ç, 2Â÷¿øÀ̳ª 1Â÷¿øÀÇ °æ¿ìµµ °°Àº °è»ê¹ýÀÌ ¼º¸³ÇÑ´Ù´Â ¶æÀÌ´Ù.

°ÔÀÓÆÇ¿¡¼­ ¼­·Î °Å¸®°¡ D ÀÌÇÏÀÎ Ä­¿¡ ÀÖ´Â µÎ µ¿¹°Àº ¿ïÀ½¼Ò¸®¸¦ ÅëÇØ »ó´ë¹æÀ» ¾Ë¾ÆÂ÷¸± ¼ö ÀÖ´Ù. ½½¶óºêÄÚ´Â ÀÌ·¸°Ô ¼­·Î ¾Ë¾ÆÂ÷¸± ¼ö ÀÖ´Â µ¿¹°ÀÇ ½ÖÀÌ ¾ó¸¶³ª µÇ´ÂÁö ¾Ë°í ½Í¾îÇÑ´Ù.

°ÔÀÓÆÇÀÇ Á¾·ù, ±× °ÔÀÓÆÇ¿¡ ÀÖ´Â ¸ðµç µ¿¹°µéÀÇ À§Ä¡¿Í ÃÖÀå °¡Ã» °Å¸® D °ªÀ» ÀÔ·Â ¹Þ¾Æ ¼­·Î ÃæºÐÈ÷ °¡±îÀÌ ÀÖ´Â µ¿¹°ÀÇ ½ÖÀÌ ¾ó¸¶³ª ÀÖ´ÂÁö ã´Â ÇÁ·Î±×·¥À» ÀÛ¼ºÇϽÿÀ.

ÀÔ·Â

ù° ÁÙ¿¡´Â ³× °³ÀÇ Á¤¼ö°¡ µé¾îÀÖÀ¸¸ç Àǹ̴ ¼ø¼­´ë·Î ´ÙÀ½°ú °°´Ù.

B=1ÀÏ ¶§´Â MÀº ÃÖ´ë 75,000,000À̸ç B=2ÀÏ ¶§´Â ÃÖ´ë 75,000ÀÌ´Ù. B=3ÀÏ ¶§´Â ÃÖ´ë 75ÀÌ´Ù.

´ÙÀ½ N°³ÀÇ ÁÙ¿¡´Â °¢ ÁÙ¸¶´Ù µ¿¹°ÀÇ À§Ä¡ ÁÂÇ¥¸¦ ³ªÅ¸³»´Â Á¤¼ö°¡ B°³ µé¾îÀÖ´Ù. Á¤¼öÀÇ ¹üÀ§´Â 1 ÀÌ»ó M ÀÌÇÏÀÌ´Ù. ÇÑ Ä­¿¡ µÎ ¸¶¸® ÀÌ»óÀÇ µ¿¹°ÀÌ °ãÃÄ ÀÖÀ» ¼öµµ ÀÖ´Ù.

#1 #2 #3
1 6 5 100
25
50
50
10
20
23
2 5 4 10
5 2
7 2
8 4
6 5
4 4
3 8 10 20
10 10 10
10 10 20
10 20 10
10 20 20
20 10 10
20 10 20
20 20 10
20 20 20

Ãâ·Â

ÃÖÀå °¡Ã» °Å¸® À̳»¿¡ ÀÖ´Â µ¿¹°ÀÇ ½Ö¼ö¸¦ Ãâ·ÂÇÑ´Ù. (¸Þ¸ð¸® Á¦ÇÑ: 150MB, ½Ã°£ Á¦ÇÑ: 4ÃÊ)

ÁÖÀÇ: 64ºñÆ® Á¤¼ö¸¦ »ç¿ëÇϵµ·Ï ÇÑ´Ù. (C/C++¿¡¼­´Â long long, ÆĽºÄ®¿¡¼­´Â int64)

#1 #2 #3
4 8 12

ÀÔ·Â ¿¹Á¦ #1(1Â÷¿ø) »ìÆ캸¸é, À§¿¡¼­ºÎÅÍ 1¹ø°ú 5¹ø µ¿¹°(25, 20), 1¹ø°ú 6¹ø(25, 23), 2¹ø°ú 3¹ø(50, 50), 5¹ø°ú 6¹ø(20, 23) µ¿¹°ÀÇ °Å¸®°¡ ÃÖÀå °¡Ã» °Å¸®ÀÎ 5 ÀÌÇÏÀÌ´Ù. ÀÌ·¸°Ô ÃÑ 4½ÖÀÌ´Ù.

#2 (2Â÷¿ø)´Â 1¹ø°ú 2¹ø(°Å¸® 2+0=2), 1¹ø°ú 4¹ø(1+3=4), 1¹ø°ú 5¹ø(1+2=3), 2¹ø°ú 3¹ø(1+2=3), 2¹ø°ú 4¹ø(1+3=4), 3¹ø°ú 4¹ø(2+1=3), 3¹ø°ú 5¹ø(4+0=4), 4¹ø°ú 5¹ø(2+1=3) ÀÌ·¸°Ô ÃÑ 8½ÖÀÌ´Ù.

Å×½ºÆ® ÄÉÀ̽º Áß ÀüüÀÇ 30Á¡¿¡ ÇØ´çÇÏ´Â ÄÉÀ̽º´Â NÀÇ °ªÀÌ ÃÖ´ë 1000ÀÌ´Ù. ±×¸®°í 1, 2, 3Â÷¿ø Áß ´Ü ÇÑ °æ¿ì¿¡ ´ëÇؼ­¶óµµ ¿Ïº®ÇÏ°Ô ¹®Á¦¸¦ Ç®¸é ÃÖ¼ÒÇÑ 30Á¡ ÀÌ»óÀ» ¹ÞÀ» ¼ö ÀÖ´Ù.


6. »çÀÌŬ ¿¬½À ÄÚ½º

¹Ì¸£ÄÚ¿Í ½½¶óºêÄÚ´Â Å©·Î¾ÆƼ¾Æ¿¡¼­ Çظ¶´Ù ¿­¸®´Â 2Àν »çÀÌŬ Àå°Å¸® °æÁÖÀÇ Âü°¡¸¦ ¾ÕµÎ°í ¿­½ÉÈ÷ ±â·®À» ½×°í ÀÖ´Ù. ±×µéÀº ¿¬½À ÄÚ½º¸¦ ¼³Á¤ÇØ ³õ°í ±× ÄÚ½º´ë·Î ²ÙÁØÈ÷ ÁÖÇà ¿¬½ÀÀ» ÇÏ°í ½Í¾îÇÑ´Ù.

ÁÖº¯¿¡´Â N°³ÀÇ µµ½Ã¿Í M°³ÀÇ ±æÀÌ ÀÖ´Ù. ±æÀº µÎ µµ½Ã¸¦ ¿¬°áÇÏ¸ç ¾î´À ¹æÇâÀ¸·Î³ª ÁÖÇàÀÌ °¡´ÉÇÏ´Ù. M°³ÀÇ ±æ Áß Á¤È®ÇÏ°Ô N-1°³´Â Æ÷ÀåµÈ µµ·ÎÀ̸ç, ³ª¸ÓÁö´Â ºñÆ÷Àå ¿À¼Ö±æÀÌ´Ù. ´Ü, ¸ðµç µµ½Ã´Â Æ÷Àå µµ·Î¸¸À¸·Îµµ »óÈ£ ¿Õ·¡°¡ °¡´ÉÇÏ°Ô ¿¬°áµÅ ÀÖ´Ù. ´Ù½Ã ¸»ÇØ N°³ÀÇ µµ½Ã¿Í N-1°³ÀÇ Æ÷Àå µµ·Î´Â Æ®¸® ±¸Á¶¸¦ Çü¼ºÇÑ´Ù´Â ¶æÀÌ´Ù.

¾Æ¿ï·¯, ÇÑ µµ½Ã¸¦ °üÅëÇÏ´Â ±æ(Æ÷Àå, ºñÆ÷Àå ¸··Ð)ÀÇ ÃÖ´ë °³¼ö´Â 10°³ÀÌ´Ù.

¿¬½À ÄÚ½º´Â ÇÑ µµ½Ã¿¡¼­ ½ÃÀÛÇؼ­ ÀÓÀÇÀÇ ±æÀ» µû¶ó ¿îÇàÇÑ µÚ, ´Ù½Ã ±× µµ½Ã·Î µ¹¾Æ¿À´Â ÇüÅÂÀÌ´Ù. ¹Ì¸£ÄÚ¿Í ½½¶óºêÄÚ´Â ´Ã »õ·Î¿î ±æÀ» °¡´Â °ÍÀ» ÁÁ¾ÆÇϱ⠶§¹®¿¡, Àü¿¡ Áö³ªÃÆ´ø µµ½Ã¸¦ ¶Ç µé¸£°Å³ª Àü¿¡ ÁÖÇàÇß´ø µµ·Î¸¦ ´Ù½Ã ÁÖÇàÇÏ´Â ÀÏÀÌ ¾øµµ·Ï ÄÚ½º¸¦ ¸¸µé°í ½Í¾îÇÑ´Ù. ÄÚ½º´Â ¾Æ¹« µµ½Ã¿¡¼­³ª ½ÃÀÛÇصµ µÇ¸ç, ¸ðµç µµ½Ã¸¦ ´Ù °ÅÃÄ¾ß ÇÒ ÇÊ¿ä´Â ¾ø´Ù.

2Àν ÀÚÀü°Å´Â µÚ¿¡ Ÿ´Â °Ô ü·Â ¼Ò¸ð°¡ ´õ Àû´Ù. ¾Õ »ç¶÷ÀÌ ¿ªÇ³À» °¡·Á Áֱ⠶§¹®ÀÌ´Ù. ±×·¡¼­ µÑÀº »õ·Î¿î µµ½Ã¿¡ µµÂøÇÒ ¶§¸¶´Ù ÀÚ¸®¸¦ ±³´ëÇÑ´Ù. ÀÌ·± »óȲ¿¡¼­ µÎ »ç¶÷ÀÌ ¼­·Î µ¿ÀÏÇÑ ¾ç¸¸Ä¡ ÈÆ·ÃÀ» Çϱâ À§Çؼ­´Â ¿¬½À ÄÚ½º´Â ¦¼ö °³ÀÇ ±æÀ» °æÀ¯Çϵµ·Ï Á¤ÇØ¾ß ÇÑ´Ù.

±×·±µ¥ ¹Ì¸£ÄÚ¿Í ½½¶óºêÄÚ¸¦ ½Ã»ùÇÏ´Â °æÀïÀÚµéÀº, ±æÀÇ ÀϺθ¦ Æó¼âÇÔÀ¸·Î½á ±× µÎ »ç¶÷ÀÌ À§¿¡¼­ ¾ð±ÞÇÑ ¸ðµç Á¶°ÇÀ» ¸¸Á·ÇÏ´Â ¿¬½À ÄÚ½º¸¦ ÀüÇô ãÀ» ¼ö ¾ø°Ô ¸¸µé±â·Î ÀÛÁ¤Çß´Ù. ºñÆ÷Àå±æÀº Æó¼âÇϴµ¥ Á¦°¢±â ºñ¿ëÀÌ µé¸ç, ±× ºñ¿ëÀº ¾çÀÇ Á¤¼ö·Î Ç¥ÇöµÈ´Ù. ´Ù¸¸ Æ÷Àå µµ·Î´Â Æó¼â°¡ ºÒ°¡´ÉÇÏ´Ù.

µµ½Ã¿Í µµ·Î¸Á¿¡ ´ëÇÑ Á¤º¸¸¦ ÀÔ·Â ¹Þ¾Æ, À§¿¡¼­ ¾ð±ÞÇÑ ¸ðµç Á¶°ÇÀ» ¸¸Á·ÇÏ´Â »çÀÌŬ ¿¬½À ÄÚ½º°¡ Á¸ÀçÇÏÁö ¾Ê°Ô ¸¸µå´Âµ¥ ÇÊ¿äÇÑ ÃÖ¼ÒÇÑÀÇ µµ·Î Æó¼â ºñ¿ëÀ» °è»êÇÏ´Â ÇÁ·Î±×·¥À» ÀÛ¼ºÇϽÿÀ.

ÀÔ·Â

ù° ÁÙ¿¡´Â µµ½ÃÀÇ °³¼ö N°ú ±æÀÇ °³¼ö MÀÌ ÀÖ´Ù. (2¡ÂN¡Â1000, N-1¡ÂM¡Â5000) ±×¸®°í ´ÙÀ½ M°³ÀÇ ÁÙ¿¡´Â ±æÀÇ Á¤º¸¸¦ ³ªÅ¸³»´Â Á¤¼ö A, B, C°¡ ÀÖ´Ù. (1¡ÂA¡ÂN, 1¡ÂB¡ÂN, 0¡ÂC¡Â10,000) µµ½Ã A¿Í µµ½Ã B°¡ ±æ·Î ¿¬°áµÇ¾î ÀÖÀ¸¸ç, ÀÌ ±æÀÇ Æó¼â ºñ¿ëÀÌ CÀÓÀ» ÀǹÌÇÑ´Ù. ´Ü, C°¡ 0À̸é ÀÌ ±æÀº Æó¼âÇÒ ¼ö ¾ø´Â Æ÷Àå µµ·Î¶ó´Â ¶æÀÌ´Ù.

±×·¡ÇÁ »óÀ¸·Î ÇÑ µµ½Ã Á¤Á¡¿¡ ºÙÀ» ¼ö ÀÖ´Â µµ·Î ¼±ºÐÀÇ ÃÖ´ë °³¼ö´Â ¾Õ¼­ ¸»ÇßµíÀÌ 10ÀÌ´Ù. ÀÓÀÇÀÇ µÎ µµ½Ã¸¦ ¿¬°áÇÏ´Â µµ·Î´Â ÃÖ´ë Çϳª¹Û¿¡ Á¸ÀçÇÏÁö ¾Ê´Â´Ù. (´ç¿¬ÇÑ ¸»ÀÓ. Áï, ÇÑ Á÷Åë µµ·Î°¡ ¸·Çû´Ù°í Çؼ­ ´Ù¸¥ Á÷Åë µµ·Î¸¦ ÀÌ¿ëÇÏ¸é µÇ´Â »óȲ±îÁö °í·ÁÇÏÁö´Â ¾Ê¾Æµµ µÈ´Ù´Â ¶æ.)

#1 #2
5 8
2 1 0
3 2 0
4 3 0
5 4 0
1 3 2
3 5 2
2 4 5
2 5 1
9 14
1 2 0
1 3 0
2 3 14
2 6 15
3 4 0
3 5 0
3 6 12
3 7 13
4 6 10
5 6 0
5 7 0
5 8 0
6 9 11
8 9 0

Ãâ·Â

¹®Á¦ Á¶°ÇÀ» ÃæÁ·Çϱâ À§ÇØ ¸·¾Æ¾ß ÇÏ´Â ±æµéÀÇ Æó¼â ºñ¿ëÀÇ ÇÕÀ» Á¤¼ö·Î Ãâ·ÂÇÏ¸é µÈ´Ù. (¸Þ¸ð¸® Á¦ÇÑ: 64MB, ½Ã°£ Á¦ÇÑ: 0.3ÃÊ)

#1 #2
5 48

À§ÀÇ ±×¸²Àº ÀÔ·Â ¿¹Á¦ #1À» ½ÇÁ¦ ±×·¡ÇÁ·Î Ç¥ÇöÇÑ °ÍÀÌ´Ù. ±½Àº ¼±Àº Æ÷Àå µµ·Î¸¦ ÀǹÌÇÑ´Ù. À̶§ ¹Ì¸£ÄÚ¿Í ½½¶óºêÄÚÀÇ Á¶°ÇÀ» ¸¸Á·ÇÏ´Â ¿¬½À ÄÚ½º´Â ¿À¸¥ÂÊ°ú °°ÀÌ ´Ù¼¸ °¡Áö°¡ Á¸ÀçÇϴµ¥, µµ·Î 1-3, 3-5, 2-5¸¦ Æó¼âÇؼ­ Á¦°ÅÇÏ¸é ´Ù¼¸ °¡Áö °æ·Î Áß ¾î´À °Íµµ Á¦ ±¸½ÇÀ» ¸ø ÇÏ°Ô µÈ´Ù. ¼¼ µµ·Î¸¦ Æó¼âÇÏ´Â ºñ¿ëÀº 2+2+1=5ÀÌ´Ù.

¹°·Ð µµ·Î 2-4¿Í 2-5 ÀÌ·¸°Ô µÑ¸¸ ¸·¾Æµµ ¸ñÇ¥¸¦ ´Þ¼ºÇÒ ¼ö´Â ÀÖÁö¸¸ ÀÌ °æ¿ì ºñ¿ëÀº 6À¸·Î ´õ Ä¿Áö°Ô µÈ´Ù.

Å×½ºÆ® ÄÉÀ̽º Áß ÀüüÀÇ 30Á¡¿¡ ÇØ´çÇÏ´Â ÄÉÀ̽º´Â ¿¹Á¦ #1ó·³ Æ÷Àå µµ·Î°¡ µµ½Ã¿Í µµ½Ã¸¦ ÀÏ·Ä·Î Âß ¿¬°áÇÏ°í ÀÖ´Ù. Áï, ÇÑ µµ½Ã¿¡¼­ ¼¼ °³ ÀÌ»óÀÇ Æ÷Àå µµ·Î°¡ ¸¸³ªÁö ¾Ê´Â´Ù´Â ¶æÀÌ´Ù.

ÇÁ·Î±×·¥ ÀÛ¼ºÀÇ ÆíÀǸ¦ µµ¸ðÇϱâ À§ÇØ, ÀÌ ¹®Á¦´Â ´ëȸ ÁøÇà Áß¿¡ ºÎºÐÀûÀ¸·Î ¿¹ºñ äÁ¡ÀÌ °¡´ÉÇÏ´Ù. ¼öÇèÀÚ´Â ÀÛ¼ºÇÏ°í ÀÖ´Â ÇÁ·Î±×·¥À» ÃÖ´ë 10¹ø±îÁö Á¦ÃâÇؼ­ Á¤½Ä äÁ¡ ¶§ ¾²ÀÌ´Â Å×½ºÆ® ÄÉÀ̽ºÀÇ ÀϺο¡ ´ëÇÑ Ã¤Á¡ °á°ú¸¦ ÅëÁö ¹ÞÀ» ¼ö ÀÖ´Ù.