import1234   1년 전

1. 우울 달래기

우울 기간이 $T$이고, 우울 구간이 시작하는 날짜를 $S$라 합시다. 이 때, $S-2T$일부터 $S-1$일까지 하루에 한 개의 꽃을 반드시 선물해야 합니다.

현재 날짜를 0이라고 할 때, 현재 날짜보다 이전에 꽃을 선물할 수 없습니다. 한 마디로, 날짜가 $S-2T\lt0$인 케이스는 고려하지 않습니다.

만약 어떤 우울 구간이 현재 날짜와 너무 가까워서($=S-2T\lt0$인 경우) 상범이의 우울함을 덜어줄 수 없다고 하더라도 현재 날짜부터 $S-1$일까지 하루에 한 개의 꽃을 선물해 최대한 상범이의 우울을 위로해줘야 합니다.


2. 최장 우울 구간

최장 우울 구간을 $T_M$이라 하고, 그 우울 구간이 시작하는 날짜를 $S_M$이라 합시다. 최장 우울 구간에 대해선 특별히 $S_M-3T_M$부터 $S_M-1$까지 하루에 한 개의 꽃을 선물해야 합니다.

최장 우울 구간이 여러 개인 경우, 딱 하나의 최장 우울 구간만 $3T_M$일 이전부터 선물하고 나머지 구간들은 반드시 $2T_M$일 이전부터 선물해야 합니다.(그러므로 어느 최장 구간을 선택해서 $3T_M$일 이전부터 꽃을 줄 지를 결정하는 게 이 문제의 핵심입니다.)


3. 그 외 규칙들

  • 꽃은 하루에 하나만 줄 수 있고, 두 개 이상은 줄 수 없습니다. 따라서 한 날짜가 여러 우울 구간을 달랠 수 있는 날짜에 속한다고 하더라도 꽃은 하나만 주어야 합니다.
  • 입력으로 0이 들어올 수 있습니다.
  • 우울 구간 내 속하는 날에도 조건에 해당한다면 꽃을 선물할 수 있습니다.

아래는 테스트케이스입니다.

댓글을 작성하려면 로그인해야 합니다.