์‹œ๊ฐ„ ์ œํ•œ ๋ฉ”๋ชจ๋ฆฌ ์ œํ•œ ์ œ์ถœ ์ •๋‹ต ๋งž์€ ์‚ฌ๋žŒ ์ •๋‹ต ๋น„์œจ
1 ์ดˆ 1024 MB 127 53 45 47.368%

๋ฌธ์ œ

๐ŸŽต๋‹ˆ๊ฐ€ ์‹ซ์–ด ์‹ซ์–ด ๋„ˆ๋ฌด ์‹ซ์–ด ์‹ซ์–ด ์˜ค์ง€๋งˆ ๋‚ด๊ฒŒ ์ฐ์ฉ๋Œ€์ง€๋งˆ๐ŸŽต - ์œ ์ž, ๋ชจ๊ธฐ์†ก ไธญ

๋ชจ๊ธฐ๋ฅผ ์‹ซ์–ดํ•˜๋Š” ์ง€๋™์ด๋Š” ์–ด๋Š ๋‚  ๋ฌธ๋“ ์ž์‹ ์˜ ๋ฐฉ์— ๋ชจ๊ธฐ๊ฐ€ ๊ฐ€์žฅ ๋งŽ์ด ์žˆ๋Š” ์‹œ๊ฐ„๋Œ€๊ฐ€ ์–ธ์ œ์ธ์ง€ ๊ถ๊ธˆํ•ด์กŒ๋‹ค. ๋‹คํ–‰ํžˆ ์ง€๋™์ด ๋ฐฉ์€ ์ตœ์ฒจ๋‹จ ์‹œ์Šคํ…œ์ด ๊ฐ–์ถฐ์ ธ ์žˆ์–ด ์–ด๋–ค ๋ชจ๊ธฐ๊ฐ€ ๋ฐฉ์— ์–ธ์ œ ์ž…์žฅํ–ˆ๊ณ  ์–ธ์ œ ํ‡ด์žฅํ–ˆ๋Š”์ง€๋ฅผ ๊ธฐ๋กํ•  ์ˆ˜ ์žˆ๋‹ค.

์ง€๋™์ด๋ฅผ ๋„์™€ ๋ชจ๊ธฐ๋“ค์˜ ๋ฐฉ ์ž…์žฅ, ํ‡ด์žฅ ์‹œ๊ฐ์ด ์ฃผ์–ด์กŒ์„ ๋•Œ ๋ชจ๊ธฐ๋“ค์ด ๊ฐ€์žฅ ๋งŽ์ด ์žˆ๋Š” ์‹œ๊ฐ„๋Œ€์™€ ํ•ด๋‹น ์‹œ๊ฐ„๋Œ€์— ๋ชจ๊ธฐ๊ฐ€ ๋ช‡ ๋งˆ๋ฆฌ๊ฐ€ ์žˆ๋Š”์ง€ ๊ตฌํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ๋งŒ๋“ค์–ด๋ณด์ž. 

์ž…๋ ฅ

์ฒซ์งธ ์ค„์— ์ง€๋™์ด์˜ ๋ฐฉ์— ์ถœ์ž…ํ•œ ๋ชจ๊ธฐ์˜ ๋งˆ๋ฆฟ์ˆ˜ N(1 ≤ N ≤ 1,000,000)๊ฐ€ ์ฃผ์–ด์ง„๋‹ค.

๋‹ค์Œ N๊ฐœ์˜ ์ค„์— ๋ชจ๊ธฐ์˜ ์ž…์žฅ ์‹œ๊ฐ TE๊ณผ ํ‡ด์žฅ ์‹œ๊ฐ TX์ด ์ฃผ์–ด์ง„๋‹ค. (0 ≤ TE < TX ≤ 2,100,000,000)

๋ชจ๊ธฐ๋Š” [TE, Tx)๋™์•ˆ ์กด์žฌํ•œ๋‹ค.

 

์ถœ๋ ฅ

์ฒซ์งธ ์ค„์— ์ง€๋™์ด ๋ฐฉ์— ๋ชจ๊ธฐ๊ฐ€ ๊ฐ€์žฅ ๋งŽ์ด ์žˆ๋Š” ์‹œ๊ฐ„๋Œ€์˜ ๋ชจ๊ธฐ ๋งˆ๋ฆฟ์ˆ˜๋ฅผ ์ถœ๋ ฅํ•œ๋‹ค.

์ง€๋™์ด ๋ฐฉ์— ๋ชจ๊ธฐ๊ฐ€ ๊ฐ€์žฅ ๋งŽ์ด ์žˆ๋Š” ์‹œ๊ฐ„๋Œ€์˜ ์—ฐ์† ๊ตฌ๊ฐ„ ์ „์ฒด๋ฅผ [TEm, TXm)์ด๋ผ๊ณ  ํ•  ๋•Œ,

๋‘˜์งธ ์ค„์— TEm, TXm์„ ๊ณต๋ฐฑ์œผ๋กœ ๊ตฌ๋ถ„ํ•˜์—ฌ ์ถœ๋ ฅํ•œ๋‹ค. ๋‹จ, ์—ฌ๋Ÿฌ ๊ฐ€์ง€ ๋ฐฉ๋ฒ•์ด ์žˆ์œผ๋ฉด ๊ฐ€์žฅ ๋น ๋ฅธ ์‹œ์ž‘ ์‹œ๊ฐ์„ ๊ธฐ์ค€์œผ๋กœ ์ถœ๋ ฅํ•œ๋‹ค.

์˜ˆ์ œ ์ž…๋ ฅ 1

3
2 16
4 6
6 10

์˜ˆ์ œ ์ถœ๋ ฅ 1

2
4 10

์˜ˆ์ œ์— ๋”ฐ๋ฅธ ๋ชจ๊ธฐ์˜ ์กด์žฌ ์‹œ๊ฐ„์„ ๋ง‰๋Œ€ ๊ทธ๋ฆผ์œผ๋กœ ๋‚˜ํƒ€๋‚ด๋ฉด ์œ„์™€ ๊ฐ™๋‹ค.

๋ชจ๊ธฐ๊ฐ€ ๊ฐ€์žฅ ๋งŽ์€ ์‹œ๊ฐ„๋Œ€์˜ ์—ฐ์† ๊ตฌ๊ฐ„์€ [4, 10) ์ด๊ณ  ํ•ด๋‹น ์‹œ๊ฐ„๋Œ€์˜ ๋ชจ๊ธฐ์˜ ์ˆ˜๋Š” 2๋งˆ๋ฆฌ์ด๋‹ค.

์ถœ์ฒ˜

University > ํ•œ์–‘๋Œ€ ERICA > Zero One Algorithm Contest 2020 E๋ฒˆ