문제
베시는 최근 새로운 에라 투어에서 그의 최애 팝 아티스트 엘시 스위프트가 공연을 한다는 것을 알게 되었습니다! 유감스럽게도 티켓이 빠르게 매진되어, 베시는 다른 도시로 비행하여 콘서트에 참석할 생각입니다. 에라 투어는 N(2≤N≤750)개의 도시에서 진행되며, 각 도시 쌍 (i,j)에 대해 i<j이면 i에서 j로의 직접 비행이 있을 수도 없을 수도 있습니다.
도시 a에서 도시 b로의 비행 경로(a<b)는 k≥2인 도시 시퀀스 a=c1<c2<⋯<ck=b로 정의됩니다. 여기서 1≤i<k인 모든 i에 대해 도시 ci에서 도시 ci+1로의 직접 비행이 있어야 합니다. i<j인 모든 도시 쌍 (i,j)에 대해 그들 사이의 비행 경로 수의 홀짝 여부가 주어집니다(0은 짝수, 1은 홀수).
여행 일정을 계획하다가 베시는 살짝 머리가 복잡해져서 이제 도시 쌍 간에 직접 비행이 몇 개인지 궁금해졌습니다. 답은 유일하게 결정될 수 있다고 합니다.
Bessie recently discovered that her favorite pop artist, Elsie Swift, is performing in her new Eras Tour! Unfortunately, tickets are selling out fast, so Bessie is thinking of flying to another city to attend the concert. The Eras tour is happening in N (2≤N≤750) cities labeled 1…N, and for each pair of cities (i,j) with i<j there either exists a single direct flight from i to j or not.
A flight route from city a to city b (a<b) is a sequence of k≥2 cities a=c1<c2<⋯<ck=b such that for each 1≤i<k, there is a direct flight from city ci to city ci+1. For every pair of cities (i,j) with i<j, you are given the parity of the number of flight routes between them (0 for even, 1 for odd).
While planning her travel itinerary, Bessie got distracted and now wants to know how many pairs of cities have direct flights between them. It can be shown that the answer is uniquely determined.
입력
첫 번째 줄에는 N이 주어집니다.
다음으로 N-1줄이 따릅니다. i번째 줄에는 N-i개의 정수가 있습니다. i번째 줄의 j번째 정수는 i에서 i+j로의 비행 노선 수의 홀짝 여부입니다.
The first line contains N.
Then follow N−1 lines. The ith line contains N−i integers. The jth integer of the ith line is equal to the parity of the number of flight routes from i to i+j.
출력
직접 비행이 있는 도시 쌍의 수를 출력하세요.
Output the number of pairs of cities with direct flights between them.
예제 #1
3
11
1
2
여기에는 두 개의 직접 비행이 있습니다: 1→2 및 2→3. 1에서 2로, 그리고 2에서 3으로의 각각이 하나의 직접 비행으로 이루어진 하나의 비행 노선이 있습니다. 또한 1에서 3으로의 비행 노선이 하나 있습니다 (1→2→3).
There are two direct flights: 1→2 and 2→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→2→3).
예제 #2
5
1111
101
01
1
6
여섯 개의 직접 비행이 있습니다: 1→2, 1→4, 1→5, 2→3, 3→5, 4→5. 이로 인해 다음과 같은 비행 노선 수가 발생합니다:
비행 노선 수:
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
There are six direct flights 1→2,1→4,1→5,2→3,3→5,4→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 (mod2).
로그인해야 코드를 작성할 수 있어요.