RiseOJ – 비행 경로

설명

베시는 최근 자신이 가장 좋아하는 팝 아티스트 엘시 스위프트가 새 Eras Tour 공연을 한다는 것을 알게 되었다! 안타깝게도 티켓이 빠르게 매진되고 있어서, 베시는 다른 도시로 비행기를 타고 가서 콘서트에 참석할까 생각 중이다. Eras Tour는 $1\dots N$ 으로 라벨이 붙은 $$N$$ ( $2\le N\le 750$ )개의 도시에서 열리며, $$i인 각 도시 쌍 \((i,j)$에 대해 $i$에서 $j$로 가는 직항편이 하나 존재하거나 존재하지 않는다.$

도시 $$a$$ 에서 도시 $$b$$ ( $$a)로의 비행 경로는 \(a=c_1인 \(k\ge 2$개의 도시로 이루어진 수열로, 각 $1\le i에 대해 도시 \(c_i$에서 도시 $c_{i+1}$로 가는 직항편이 존재하는 것을 말한다. $i인 모든 도시 쌍 \((i,j)$에 대해, 두 도시 사이의 비행 경로 개수의 홀짝성(짝수면 0, 홀수면 1)이 주어진다.$

여행 일정을 계획하던 중 베시는 딴생각에 빠져서, 이제 직항편이 있는 도시 쌍이 몇 개인지 알고 싶어졌다. 답이 유일하게 결정됨을 보일 수 있다.

문제 제공: Benjamin Qi

제약

채점 방식

입력 3-4: $N\le 6$
입력 5-12: $N\le 100$
입력 13-22: 추가 제약 조건 없음.

문제 제공: Benjamin Qi

입력 형식

첫째 줄에 $$N$$ 이 주어진다.

다음으로 $$N-1$$ 개의 줄이 주어진다. $$i$$ 번째 줄에는 $$N-i$$ 개의 정수가 있다. $$i$$ 번째 줄의 $$j$$ 번째 정수는 $$i$$ 에서 $$i+j$$ 로의 비행 경로 개수의 홀짝성과 같다.

출력 형식

직항편이 있는 도시 쌍의 개수를 출력한다.

예제 1

입력

3
11
1

출력

설명

There are two direct flights: $1\to 2$ and $2\to 3$ . There is one flight route
from $$1$$ to $$2$$ and $$2$$ to $$3$$ , each consisting of a single direct flight. There
is one flight route from $$1$$ to $$3$$ ( $1\to 2\to 3$ ).

예제 2

입력

출력

설명

There are six direct flights $1\to 2, 1\to 4, 1\to 5, 2\to 3, 3\to 5, 4\to 5$ .
These result in the following numbers of flight routes:

Flight Route Counts:

            dest
          1 2 3 4 5

       1  0 1 1 1 3
       2  0 0 1 0 1
source 3  0 0 0 0 1
       4  0 0 0 0 1
       5  0 0 0 0 0

which is equivalent to the sample input after taking all the numbers $\pmod{2}$ .

문제 정보

riseoj 작성

출처 올림피아드 > USACO > 2023-2024 > December > Gold

올림피아드 > USACO > 2023-2024 > December > Gold

태그

JudgeUSACO

비행 경로

평가 및 의견

풀이 제출