[더블릿 - 12] 사다리/koi_ladd

프로그램 명: koi_ladd

제한시간: 1 초

여러 층으로 이루어진 직사각형 모양의 건물이 있다. 아래 그림 1은 5 개의 층으로 이루어진 직사각형 건물의 예이다. 각 층에는 하나의 막대기가 있는데, 각 막대기의 길이는 서로 다를 수 있다. 그리고 막대기들은 시간 0 에서 시작해서 동시에 왼쪽에서 오른쪽으로 혹은 오른쪽에서 왼쪽으로 움직인다. 시간은 정수시간 단위(0,1,2,...)로 흐르고, 모든 막대기들은 단위시간당 길이 1 만큼 움직인다.

아래 그림 1에서처럼 초기(시간 0)에 각 막대기는 직사각형의 왼쪽 변 또는 오른쪽 변에 닿아있다. 시간이 지남에 따라 각 막대기는 주어진 방향으로 움직이고 막대기의 양쪽 끝 중에 하나가 직사각형의 왼쪽 변 또는 오른쪽 변에 닿으면 진행하는 방향과 반대 방향으로 계속해서 움직인다.

철수(그림 1의 검정색 원)는 초기에 가장 아래층막대기 위에 위치하고 있다. 그리고 아래 조건 1)을 만족하면서 현재 막대기 위에서 움직일 수 있고, 조건 2)를 만족한다면, 하나 위층의 막대기로 올라 갈 수 있다.

• 조건 1) 현재 위치하고 있는 막대기 위에서는 0 시간에 움직일 수 있다. (즉, 막대기 위에서의 움직임은 시간이 걸리지 않는다.)
• 조건 2) 철수가 현재 위치하고 있는 막대기의 임의의 위치에서 수직으로 이동 했을 때, 바로 위 층의 막대기 구간 안에 있으면(구간의 양쪽 끝 포함) 0 시간에 바로 위 층의 막대기로 수직으로 올라갈 수 있다. (즉, 이 조건을 만족해서 하나 위층으로 올라 갈 수 있다면, 올라가는 움직임은 시간이 걸리지 않는다.)

예를 들어서, 아래 그림 2에서처럼 철수는 시간 2 에 두 번째 층을 지나 세 번째 층의 막대기로 움직일 수 있다. 그리고 그림 3에서처럼 시간 4 에 네 번째 층을 지나 다섯 번째 층의 막대기에 도달할 수 있다.

 

시간 0 의 초기 상태에서 출발해서 철수가 가장 아래층의 막대기에서 가장 위층의 막대기로 올라가는데 걸리는 최소 시간을 구하는 프로그램을 작성하시오.

입력

• 첫 번째 줄에 층 수 N ( 1 <= N <= 3000) 과 층의 길이 L ( 1 <= L <= 3000, L 은 짝수)이 주어진다. 가장 아래층은 1 층이고 가장 위층은 N층이다.
• 다음 N개의 줄 중 i 번째 줄에는 i 층의 막대기의 길이 l ( 1 <= l <= L ,l 은짝수) 과 초기에 막대기가 움직이는 방향 d (d=0,1) 가 주어진다. 여기서, d 의 값 0 은 왼쪽에서 오른쪽, 1 은 오른쪽에서 왼쪽을 의미한다. 또한 초기에 막대기들은 방향이 0 인 경우 층의 왼쪽 벽에, 1 인 경우 층의 오른쪽 벽에 닿아 있다고 가정한다.

출력

첫째 줄에 철수가 가장 아래층 막대기에서 가장 위층 막대기로 올라가는데 걸리는 최소 시간을 하나의 정수로 출력한다.

입출력 예

입력 

4 6
4 1
2 0
4 0
2 1

출력 

0

입력 

5 12
4 1
4 0
2 0
2 1
6 0

출력 

4

출처:2012 지역 본선 초등 4/5

재밌었던 문제였다.

2012/06/18 - [Algorithm/Dovelet] - [더블릿 - 11] 직사각형/koi_rect

이전 문제를 풀고 바로 이 문제를 풀어서 그런지 영향을 많이 받았다.

이전 문제나 이 문제나

같은 2012 지역 본선 초등 문제인걸 보면

문제 만든 사람이 의도한 것일 수도 있을거 같다.

이 문제를 풀기 위해 하나의 식을 만들었다.

t초 일 때 n층의 막대기의 중심 위치를 구하는 식이다.

층의 길이를 대문자 L,

n 층의 막대기의 길이를 ln라 정의하고

막대기가 1초마다 1만큼 이동한다면

n 층의 막대기는 (L - ln) 초마다 좌, 우 벽에 붙어있다.

막대기를 단진자운동으로 생각하면 (L - ln)은 운동 주기의 반으로 생각할 수 있다.

따라서.

t/(L - ln) 이 짝수면 막대기는 원래 위치에 있고

홀수면 막대기는 반대편 벽에 붙어있다고 말 할 수 있다.

( - t%(L - ln)이 0이라고 가정한다면..  )

이것을 막대기의 초기 방향(dn) 0 또는 1과 관련 지어 생각하면

t/(L - ln) ^ dn 이

1이면 막대기는 오른쪽 벽에 붙어있고

0이면 막대기는 왼쪽 벽에 붙어있다.

여기에 t%(L -ln)을 고려하면

( - 벽에서 부터 얼마나 떨어져있는가.. )

void CalcC(double *c, int fl)

{

    pair<int, int> dn = d[fl - 1];

    int s = L - dn.first;

    if (s == 0)

    {

        *c = dn.first/2;

        return;

    }

    *c = t%s;

    if (t/s ^ dn.second)

        *c = s - *c;

    *c += dn.first/2.;

}

위와 같은 식을 통해 t초 일 때, fl층의 막대기 중심 좌표를 구할 수 있고

중심좌표와 중심좌표로부터 막대기 끝점까지의 길이를 알면

이전 문제처럼 두 선분이 겹침을 구할 수 있다.

이제, 시간 t를 증가시키면서 제일 아래층에서 부터 꼭대기 층까지

올라갈 수 있는 최단 시간을 구해주면 된다.

#include <iostream>

#include <cmath>

#include <utility>

using namespace std;

 

int N,L,t,f;

double cf,cnf,dis,cmp;

pair<int, int> d[3000];

 

void CalcC(double *c, int fl)

{

    pair<int, int> dn = d[fl - 1];

    int s = L - dn.first;

    if (s == 0)

    {

        *c = dn.first/2;

        return;

    }

    *c = t%s;

    if (t/s ^ dn.second)

        *c = s - *c;

    *c += dn.first/2.;

}

void C()

{  

    CalcC(&cnf, f + 1);

    dis = abs(cf - cnf);

}

int main()

{

    cin >> N >> L;

    for (int i = 0; i < N; ++i)

        cin >> d[i].first >> d[i].second;

 

    CalcC(&cf, ++f);

    for(;;)

    {

        if (f == N)

        {

            cout << t;

            return 0;

        }

        C();

        cmp = (d[f - 1].first + d[f].first)/2;

        for(;;)

        {

            if (dis <= cmp)

            {

                ++f;

                cf = cnf;

                break;

            }

            ++t;

            CalcC(&cf, f);

            C();

        }

    }

}