Flight Routes
골드 I의견: 0
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\le N\le 750\)) cities labeled \(1\dots N\), and for
each pair of cities \((i,j)\) with \(i
flight from \(i\) to \(j\) or not.
A flight route from city \(a\) to city \(b\) (\(a
\(a=c_1
from city \(c_i\) to city \(c_{i+1}\). For every pair of cities \((i,j)\) with \(i
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.
Problem credits: Benjamin Qi
SCORING
- Inputs 3-4: \(N\le 6\)
- Inputs 5-12: \(N\le 100\)
- Inputs 13-22: No additional constraints.
Problem credits: Benjamin Qi
The first line contains \(N\).
Then follow \(N-1\) lines. The \(i\)th line contains \(N-i\) integers. The \(j\)th
integer of the \(i\)th 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.
3
11
12There 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\)).
5
1111
101
01
16There 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
평가 및 의견
Flight Routes
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Flight Routes