์•„์ง ๋งŒ๋“ค๊ณ  ์žˆ๋Š” ํŽ˜์ด์ง€์ž…๋‹ˆ๋‹ค.

์ด ํŽ˜์ด์ง€๋Š” ์•„์ง ๋งŒ๋“œ๋Š” ์ค‘์ž…๋‹ˆ๋‹ค. ๋ณด์ด๋Š” ๋‚ด์šฉ์€ ๋ฐ”๋€” ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

๐ŸŽต๋‹ˆ๊ฐ€ ์‹ซ์–ด ์‹ซ์–ด ๋„ˆ๋ฌด ์‹ซ์–ด ์‹ซ์–ด ์˜ค์ง€ ๋งˆ ๋‚ด๊ฒŒ ์ฐ์ฉ๋Œ€์ง€๋งˆ๐ŸŽต - 1

๋ฉด์ ‘ ๋Œ€๋น„

์‹œ๊ฐ„ ์ œํ•œ1์ดˆ๋ฉ”๋ชจ๋ฆฌ ์ œํ•œ1024 MB

์š”์•ฝ
N๊ฐœ์˜ ๋ฐ˜์—ด๋ฆฐ ๊ตฌ๊ฐ„ [์ž…์žฅ, ํ‡ด์žฅ)์ด ์ฃผ์–ด์งˆ ๋•Œ, ๋ฐฉ์— ๋™์‹œ์— ์žˆ๋Š” ๋ชจ๊ธฐ์˜ ์ตœ๋Œ“๊ฐ’๊ณผ ๊ทธ ์ตœ๋Œ“๊ฐ’์ด ์œ ์ง€๋˜๋Š” ๊ฐ€์žฅ ์ด๋ฅธ ์ตœ๋Œ€ ๊ตฌ๊ฐ„์„ ๊ตฌํ•œ๋‹ค.
๋‚œ์ด๋„

๋ณดํ†ต10์  ์ค‘ 6์ 

์œ ํ˜•
์ •๋ ฌ, ๊ตฌ๊ฐ„, ๋ฐฐ์—ด, ํˆฌ ํฌ์ธํ„ฐ
์ •๋‹ต์ž
์•„์ง ์ œ์ถœ์ด ์—†์Šต๋‹ˆ๋‹ค

๋ฌธ์ œ

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

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

์ž…๋ ฅ

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

๋‹ค์Œ NN๊ฐœ์˜ ์ค„์— ๋ชจ๊ธฐ์˜ ์ž…์žฅ ์‹œ๊ฐ TET_E์™€ ํ‡ด์žฅ ์‹œ๊ฐ TXT_X๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. (0โ‰คTE<TXโ‰ค2,100,000,0000 \le T_E < T_X \le 2,100,000,000)

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

์ถœ๋ ฅ

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

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

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

์˜ˆ์ œ1

  1. ์˜ˆ์ œ 1

    ์ž…๋ ฅ
    3
    2 16
    4 6
    6 10
    
    ์˜ˆ์ƒ ์ถœ๋ ฅ
    2
    4 10