숲속에서 새 구경하기

• 재미있는 문제. 힌트를 참고해서 풀었다
• t가 범위로 주어지는 것이 아니라 Av*k+As=t 와 같은 형태로 값으로 주어지는 조건이었다면, 연립 선형 합동식이 되므로 쉽게 답을 구할수 있었을 것이다. 하지만, 여기에서는 그런 방법은 불가능.
• 떠올릴수 있는 가장 쉬운 방법은 그냥 t를 1부터 증가시키면서 조건을 만족하는지 테스트하는 것이다. 최대 lcm(Av,Bv,Cv)까지만 테스트해보고 그 범위 안에 해가 없으면 해가 업슨것으로 처리해도 된다. 하지만 이렇게 하더라도 lcm(Av,Bv,Cv)=O(Av*Bv*Cv)는 일일히 찾아보기에는 너무 큰 수이다.
• 시간복잡도를 줄이기 위해서 필요한 관찰은, 조건을 만족시키는 최초의 시간은 적어도 한 종류의 새에 대해서 그 새가 보이는 범위중에서 최초의 시간이라는 것이다. 다시 말해서 t는 Av*x+As, Bv*y+Bs, Cv*z+Cs 중에 한가지이다. 범위 내에서 Av*x+As 형태의 수는 O(Bv*Cv)개이므로 이것들은 모두 테스트해보는 것이 가능하다. 마찬가지로 Bv*y+Bs, Cv*z+Cs 도 테스트해보면 전부 O(Bv*Cv + Av*Cv + Av*Bv) = O(max(Av,Bv,Cv)*2) 에 해결 가능하다. (
  • 그리고 이 방법이 공식 풀이에서 제공된 방법이다)
• 다른 풀이 방법은 세개의 구간을 가리키는 포인터를 유지하면서, 조건에 맞춰서 포인터를 다음 구간으로 이동시키는 쓰리포인터? 비슷한 방식으로 접근하는 것이다.
• 처음에 Ia=(As,Ae), Ib=(Bs,Be), Ic=(Cs,Ce) 로 구간 세개를 초기화 한다. 세 구간을 시작점 순서로 정렬한것을 I1, I2, I3으로 썼을때 (I1.left ≤ I2.left ≤ I3.left 가 되도록), I3.left ≤ I1.right && I3.left ≤ I2.right 를 만족시킨다면 겹치는 구간이 존재하고, 그 구간의 시작지점은 I3.left가 된다. 조건이 만족되지 않는다면, I1의 시작점과 끝점을 인터벌만큼 증가시켜서 다음 구간으로 이동시킨후, 다시 정렬하고 비교하는 것을 반복하면 된다.
• 두번째 방식으로 코드를 짰는데, 가독성을 높여서 깔끔하게 짜려 했더니 (dataclass등을 동원해서..) TLE가 났다. 가독성을 살짝 희생하면서 코드를 좀더 최적화시켜서 통과시켰다.

"""Solution code for "BOJ 25196. 숲속에서 새 구경하기".

- Problem link: https://www.acmicpc.net/problem/25196
- Solution link: http://www.teferi.net/ps/problems/boj/25196
"""

import math
import dataclasses


@dataclasses.dataclass(order=True, slots=True)
class Interval:
    v: int = dataclasses.field(compare=False)
    s: int = dataclasses.field(compare=True)
    e: int = dataclasses.field(compare=False)


def main():
    a_interval = Interval(*[int(x) for x in input().split()])
    b_interval = Interval(*[int(x) for x in input().split()])
    c_interval = Interval(*[int(x) for x in input().split()])

    lcm = math.lcm(a_interval.v, b_interval.v, c_interval.v)
    intervals = [a_interval, b_interval, c_interval]
    first, second, third = sorted(intervals)
    while first.s <= lcm:
        if first.e < third.s:
            first.s += first.v
            first.e += first.v
        elif second.e < third.s:
            second.s += second.v
            second.e += second.v
        else:
            print(third.s)
            break
        first, second, third = sorted(intervals)
    else:
        print('-1')


if __name__ == '__main__':
    main()

"""Solution code for "BOJ 25196. 숲속에서 새 구경하기".

- Problem link: https://www.acmicpc.net/problem/25196
- Solution link: http://www.teferi.net/ps/problems/boj/25196
"""

import math


def main():
    A_v, A_s, A_e = [int(x) for x in input().split()]
    B_v, B_s, B_e = [int(x) for x in input().split()]
    C_v, C_s, C_e = [int(x) for x in input().split()]

    lcm = math.lcm(A_v, B_v, C_v)
    first, second, third = sorted(
        [[A_s, A_v, A_e - A_s], [B_s, B_v, B_e - B_s], [C_s, C_v, C_e - C_s]]
    )
    while first[0] <= lcm:
        if first[0] + first[2] < third[0]:
            first[0] += first[1]
            if first > third:
                first, second, third = second, third, first
            elif first > second:
                first, second = second, first
        elif second[0] + second[2] < third[0]:
            second[0] += second[1]
            if second > third:
                second, third = third, second
        else:
            print(third[0])
            break
    else:
        print('-1')


if __name__ == '__main__':
    main()