게놈 덮개 timer 1s memory 128MB

유전자 조립 문제에 있어서 일반적인 일은 조각이라고 하는 작은 유전자들이 주어질 때, 합리적인 특성을 갖는 전체 유전자를 찾는 것이다. 우리가 다룰 문제는 어떤 전체 유전자와그 조각 유전자들이 주어질 때, 어떤 특성을 계산해내는 것이다.

전체 유전자의 길이 L, 조각유전자의 개수 N, 한 정수 k가 주어진다. 전체 유전자는 일차원 배열처럼 길며 각 공간에 유전자 문자가 들어 있고, 각 공간은 1부터 L까지 번호가 매겨 있다고 가정한다. 또한 i번째 조각 유전자는 (bi, ei)의 순서쌍으로 표현되는데 각각 전체 유전자에서의 어떤 구간을 나타낸다.

전체 유전자에서 x위치의 유전자 문자가 잘 덮여있다고 하는 것은.  

1) bi ≤ x-k and x ≤ ei 를 만족하는 조각유전자 (bi, ei)가 존재하고  

2) bj ≤ x and x+k ≤ ej 를 만족하는 다른 조각 유전자 (bj, ej)가 존재하는 경우이다.

여러분이 해야 할 일은 주어진 정보를 이용하여 전체 유전자에서 잘 덮여있지 못한 위치의개수를 구하는 것이다.