시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 837 493 376 64.384%

문제

학생들은 3주가 지난 기념으로 매점에서 1월 1일이 지나 싸게 파는 폭죽을 사서 터뜨리고 있다.

폭죽쇼를 하는 동안 N명의 학생들이 폭죽을 터뜨린다. 그리고 이 N명의 학생은 각각 일정한 주기로 폭죽을 터뜨린다. 물론 이 주기는 학생들마다 같을 수도, 다를 수도 있다. 그리고 우리는 초 단위로 관찰을 하고, 폭죽 역시 초 단위로 터진다.

폭죽쇼가 끝날 때까지 얼마나 많은 시간동안 밤하늘에 폭죽이 터지는 것을 볼 수 있는지 궁금해 하는 조교를 도와주자.

입력

첫 줄에 폭죽을 터뜨리는 학생의 수 N(1 ≤ N ≤ 100)과 폭죽쇼가 끝나는 시간 C(1 ≤ C ≤ 2,000,000)가 주어진다. 그 다음 N개의 줄에는 학생들이 폭죽을 터뜨리는 주기가 한 줄에 하나씩 주어진다. 주기는 1보다 크거나 같고, C보다 작거나 같은 자연수이다.

출력

폭죽쇼가 시작되고 끝날 때까지 밤하늘에 폭죽을 볼 수 있는 총 시간을 출력한다.

예제 입력 1

2 20
4
6

예제 출력 1

7

힌트

                                    2                       
            1     2     1           1           1     2     1
0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20
            1     2     3           4           5     6     7

위의 그림에서 1,2가 쓰여있는 4, 6, 8, 12, 16, 18, 20초에 폭죽이 밤 하늘에 터진다. 단 12초에는 두 폭죽이 동시에 하늘에 터지지만 한번으로 세는 것에 주의하자.

W3sicHJvYmxlbV9pZCI6IjE3NzMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQzZWRcdWM4ZmRcdWMxZmMiLCJkZXNjcmlwdGlvbiI6IjxwPlx1ZDU1OVx1YzBkZFx1YjRlNFx1Yzc0MCAzXHVjOGZjXHVhYzAwIFx1YzljMFx1YjA5YyBcdWFlMzBcdWIxNTBcdWM3M2NcdWI4NWMgXHViOWU0XHVjODEwXHVjNWQwXHVjMTFjIDFcdWM2ZDQgMVx1Yzc3Y1x1Yzc3NCBcdWM5YzBcdWIwOTggXHVjMmY4XHVhYzhjIFx1ZDMwY1x1YjI5NCBcdWQzZWRcdWM4ZmRcdWM3NDQgXHVjMGFjXHVjMTFjIFx1ZDEzMFx1YjcyOFx1YjlhY1x1YWNlMCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDNlZFx1YzhmZFx1YzFmY1x1Yjk3YyBcdWQ1NThcdWIyOTQgXHViM2Q5XHVjNTQ4IE5cdWJhODVcdWM3NTggXHVkNTU5XHVjMGRkXHViNGU0XHVjNzc0IFx1ZDNlZFx1YzhmZFx1Yzc0NCBcdWQxMzBcdWI3MjhcdWI5YjBcdWIyZTQuIFx1YWRmOFx1YjlhY1x1YWNlMCBcdWM3NzQgTlx1YmE4NVx1Yzc1OCBcdWQ1NTlcdWMwZGRcdWM3NDAgXHVhYzAxXHVhYzAxIFx1Yzc3Y1x1YzgxNVx1ZDU1YyBcdWM4ZmNcdWFlMzBcdWI4NWMgXHVkM2VkXHVjOGZkXHVjNzQ0IFx1ZDEzMFx1YjcyOFx1YjliMFx1YjJlNC4gXHViYjNjXHViODYwIFx1Yzc3NCBcdWM4ZmNcdWFlMzBcdWIyOTQgXHVkNTU5XHVjMGRkXHViNGU0XHViOWM4XHViMmU0IFx1YWMxOVx1Yzc0NCBcdWMyMThcdWIzYzQsIFx1YjJlNFx1Yjk3YyBcdWMyMThcdWIzYzQgXHVjNzg4XHViMmU0LiBcdWFkZjhcdWI5YWNcdWFjZTAgXHVjNmIwXHViOWFjXHViMjk0IFx1Y2QwOCBcdWIyZThcdWM3MDRcdWI4NWMgXHVhZDAwXHVjYzMwXHVjNzQ0IFx1ZDU1OFx1YWNlMCwgXHVkM2VkXHVjOGZkIFx1YzVlZFx1YzJkYyBcdWNkMDggXHViMmU4XHVjNzA0XHViODVjIFx1ZDEzMFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkM2VkXHVjOGZkXHVjMWZjXHVhYzAwIFx1YjA1ZFx1YjBhMCBcdWI1NGNcdWFlNGNcdWM5YzAgXHVjNWJjXHViOWM4XHViMDk4IFx1YjljZVx1Yzc0MCBcdWMyZGNcdWFjMDRcdWIzZDlcdWM1NDggXHViYzI0XHVkNTU4XHViMjk4XHVjNWQwIFx1ZDNlZFx1YzhmZFx1Yzc3NCBcdWQxMzBcdWM5YzBcdWIyOTQgXHVhYzgzXHVjNzQ0IFx1YmNmYyBcdWMyMTggXHVjNzg4XHViMjk0XHVjOWMwIFx1YWQ4MVx1YWUwOFx1ZDU3NCBcdWQ1NThcdWIyOTQgXHVjODcwXHVhZDUwXHViOTdjIFx1YjNjNFx1YzY0MFx1YzhmY1x1Yzc5MC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWM5MDRcdWM1ZDAgXHVkM2VkXHVjOGZkXHVjNzQ0IFx1ZDEzMFx1YjcyOFx1YjlhY1x1YjI5NCBcdWQ1NTlcdWMwZGRcdWM3NTggXHVjMjE4IE4oMSAmbGU7IE4gJmxlOyAxMDApXHVhY2ZjIFx1ZDNlZFx1YzhmZFx1YzFmY1x1YWMwMCBcdWIwNWRcdWIwOThcdWIyOTQgXHVjMmRjXHVhYzA0IEMoMSAmbGU7IEMgJmxlOyAyLDAwMCwwMDApXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhZGY4IFx1YjJlNFx1Yzc0YyBOXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWQ1NTlcdWMwZGRcdWI0ZTRcdWM3NzQgXHVkM2VkXHVjOGZkXHVjNzQ0IFx1ZDEzMFx1YjcyOFx1YjlhY1x1YjI5NCBcdWM4ZmNcdWFlMzBcdWFjMDAgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWQ1NThcdWIwOThcdWM1MjkgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM4ZmNcdWFlMzBcdWIyOTQgMVx1YmNmNFx1YjJlNCBcdWQwNmNcdWFjNzBcdWIwOTggXHVhYzE5XHVhY2UwLCBDXHViY2Y0XHViMmU0IFx1Yzc5MVx1YWM3MFx1YjA5OCBcdWFjMTlcdWM3NDAgXHVjNzkwXHVjNWYwXHVjMjE4XHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1ZDNlZFx1YzhmZFx1YzFmY1x1YWMwMCBcdWMyZGNcdWM3OTFcdWI0MThcdWFjZTAgXHViMDVkXHViMGEwIFx1YjU0Y1x1YWU0Y1x1YzljMCBcdWJjMjRcdWQ1NThcdWIyOThcdWM1ZDAgXHVkM2VkXHVjOGZkXHVjNzQ0IFx1YmNmYyBcdWMyMTggXHVjNzg4XHViMjk0IFx1Y2QxZCBcdWMyZGNcdWFjMDRcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD48c3BhbiBzdHlsZT1cImZvbnQtZmFtaWx5OmNvdXJpZXIgbmV3XCI+Jm5ic3A7Jm5ic3A7Jm5ic3A7Jm5ic3A7Jm5ic3A7Jm5ic3A7Jm5ic3A7Jm5ic3A7Jm5ic3A7Jm5ic3A7Jm5ic3A7Jm5ic3A7Jm5ic3A7Jm5ic3A7Jm5ic3A7Jm5ic3A7Jm5ic3A7Jm5ic3A7Jm5ic3A7Jm5ic3A7Jm5ic3A7Jm5ic3A7Jm5ic3A7Jm5ic3A7Jm5ic3A7Jm5ic3A7Jm5ic3A7Jm5ic3A7Jm5ic3A7Jm5ic3A7Jm5ic3A7Jm5ic3A7Jm5ic3A7Jm5ic3A7Jm5ic3A7IDImbmJzcDsmbmJzcDsmbmJzcDsmbmJzcDsmbmJzcDsmbmJzcDsmbmJzcDsmbmJzcDsmbmJzcDsmbmJzcDsmbmJzcDsmbmJzcDsmbmJzcDsmbmJzcDsmbmJzcDsmbmJzcDsmbmJzcDsmbmJzcDsmbmJzcDsmbmJzcDsmbmJzcDsmbmJzcDsmbmJzcDs8YnIgXC8+XHJcbiZuYnNwOyZuYnNwOyZuYnNwOyZuYnNwOyZuYnNwOyZuYnNwOyZuYnNwOyZuYnNwOyZuYnNwOyZuYnNwOyZuYnNwOyAxJm5ic3A7Jm5ic3A7Jm5ic3A7Jm5ic3A7IDImbmJzcDsmbmJzcDsmbmJzcDsmbmJzcDsgMSZuYnNwOyZuYnNwOyZuYnNwOyZuYnNwOyZuYnNwOyZuYnNwOyZuYnNwOyZuYnNwOyZuYnNwOyZuYnNwOyAxJm5ic3A7Jm5ic3A7Jm5ic3A7Jm5ic3A7Jm5ic3A7Jm5ic3A7Jm5ic3A7Jm5ic3A7Jm5ic3A7Jm5ic3A7IDEmbmJzcDsmbmJzcDsmbmJzcDsmbmJzcDsgMiZuYnNwOyZuYnNwOyZuYnNwOyZuYnNwOyAxPGJyIFwvPlxyXG4wJm5ic3A7IDEmbmJzcDsgMiZuYnNwOyAzJm5ic3A7IDQmbmJzcDsgNSZuYnNwOyA2Jm5ic3A7IDcmbmJzcDsgOCZuYnNwOyA5IDEwIDExIDEyIDEzIDE0IDE1IDE2IDE3IDE4IDE5IDIwPGJyIFwvPlxyXG4mbmJzcDsmbmJzcDsmbmJzcDsmbmJzcDsmbmJzcDsmbmJzcDsmbmJzcDsmbmJzcDsmbmJzcDsmbmJzcDsmbmJzcDsgMSZuYnNwOyZuYnNwOyZuYnNwOyZuYnNwOyAyJm5ic3A7Jm5ic3A7Jm5ic3A7Jm5ic3A7IDMmbmJzcDsmbmJzcDsmbmJzcDsmbmJzcDsmbmJzcDsmbmJzcDsmbmJzcDsmbmJzcDsmbmJzcDsmbmJzcDsgNCZuYnNwOyZuYnNwOyZuYnNwOyZuYnNwOyZuYnNwOyZuYnNwOyZuYnNwOyZuYnNwOyZuYnNwOyZuYnNwOyA1Jm5ic3A7Jm5ic3A7Jm5ic3A7Jm5ic3A7IDYmbmJzcDsmbmJzcDsmbmJzcDsmbmJzcDsgNyA8XC9zcGFuPjxcL3A+XHJcblxyXG48cD5cdWM3MDRcdWM3NTggXHVhZGY4XHViOWJjXHVjNWQwXHVjMTFjIDEsMlx1YWMwMCBcdWM0ZjBcdWM1ZWNcdWM3ODhcdWIyOTQgNCwgNiwgOCwgMTIsIDE2LCAxOCwgMjBcdWNkMDhcdWM1ZDAgXHVkM2VkXHVjOGZkXHVjNzc0IFx1YmMyNCBcdWQ1NThcdWIyOThcdWM1ZDAgXHVkMTMwXHVjOWM0XHViMmU0LiBcdWIyZTggMTJcdWNkMDhcdWM1ZDBcdWIyOTQgXHViNDUwIFx1ZDNlZFx1YzhmZFx1Yzc3NCBcdWIzZDlcdWMyZGNcdWM1ZDAgXHVkNTU4XHViMjk4XHVjNWQwIFx1ZDEzMFx1YzljMFx1YzljMFx1YjljYyBcdWQ1NWNcdWJjODhcdWM3M2NcdWI4NWMgXHVjMTM4XHViMjk0IFx1YWM4M1x1YzVkMCBcdWM4ZmNcdWM3NThcdWQ1NThcdWM3OTAuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxNzczIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiRmlyZXdvcmtzIFNob3ciLCJkZXNjcmlwdGlvbiI6IjxwPkl0JiMzOTtzIEluZGVwZW5kZW5jZSBEYXksIGFuZCBGYXJtZXIgSm9obiBoYXMgdGFrZW4gdGhlIGNvd3MgdG8gdGhlIGZpcmV3b3JrcyBzaG93LiBCZXNzaWUgd29uZGVycyBob3cgbXVjaCBvZiB0aGUgc2hvdyB0aGUgY293cyB3aWxsIGJlIGFibGUgdG8gc2VlIHNpbmNlIHRoZXkgbWlnaHQgbm90IGJlIGFibGUgdG8gc3RheSBmb3IgdGhlIGVudGlyZSBkaXNwbGF5LjxcL3A+XHJcblxyXG48cD5UaGUgc2hvdyBmZWF0dXJlcyBDICgxICZsZTsgQyAmbGU7IDEwMCkgZmlyZXdvcmtzIGNhbm5vbnMgY29udmVuaWVudGx5IG51bWJlcmVkIDEuLkMuIENhbm5vbiBpIHNob290cyBmaXJld29ya3MgZXZlcnkgVGkgKDEgJmxlOyBUaSAmbGU7IE4pIHNlY29uZHMgKGFsbCB0aW1lcyBpbiB0aGlzIHRhc2sgYXJlIGludGVnZXIgc2Vjb25kcykuIEluIGEgc3BlY3RhY3VsYXIgb3BlbmluZywgYWxsIGNhbm5vbnMgZmlyc3Qgc2hvb3QgYXQgdGltZSAwLiBGaXJld29ya3MgYXJlIHZpc2libGUgb25seSBkdXJpbmcgdGhlIHNlY29uZCBpbiB3aGljaCB0aGV5IGFyZSBsYXVuY2hlZCBmcm9tIHRoZSBjYW5ub24uIFRoZSBjb3dzIHdpbGwgc3RheSBhdCB0aGUgc2hvdyBmcm9tIHRpbWUgMSB0aHJvdWdoIHRpbWUgTiAoMSAmbGU7IE4gJmxlOyAyLDAwMCwwMDApLjxcL3A+XHJcblxyXG48cD5IZWxwIEJlc3NpZSBmaWd1cmUgb3V0IGhvdyBtYW55IGRpZmZlcmVudCB0aW1lcyB0aGUgY293cyB3aWxsIGJlIGFibGUgdG8gc2VlIGZpcmV3b3JrcyBkdXJpbmcgdGhlIHRpbWUgcGVyaW9kIHRoYXQgdGhleSBhcmUgYXQgdGhlIHNob3cuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD4qIExpbmUgMTogVHdvIHNwYWNlLXNlcGFyYXRlZCBpbnRlZ2VyczogQyBhbmQgTi48XC9wPlxyXG5cclxuPHA+KiBMaW5lcyAyLi5DICsgMTogTGluZSBpKzEgY29udGFpbnMgdGhlIHNpbmdsZSBpbnRlZ2VyIFRpLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPiogTGluZSAxOiBBIHNpbmdsZSBpbnRlZ2VyIHRoYXQgaXMgdGhlIG51bWJlciBvZiBkaXN0aW5jdCBzZWNvbmRzIGluIHRoZSB0aW1lIGludGVydmFsIGZyb20gMSB0aHJvdWdoIE4gdGhhdCB0aGUgY293cyB3aWxsIGJlIGFibGUgdG8gc2VlIGZpcmV3b3Jrcy48XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

Olympiad > USA Computing Olympiad > 2006-2007 Season > USACO March 2007 Contest > Bronze 1번

  • 문제를 번역한 사람: author6
  • 데이터를 추가한 사람: djm03178
  • 문제의 오타를 찾은 사람: sunhong