Artifact 19f42a31025a41f778ec26e9277c557f48db7659:
0000: 23 69 6e 63 6c 75 64 65 20 3c 76 65 63 74 6f 72 #include <vector
0010: 3e 0a 23 69 6e 63 6c 75 64 65 20 3c 73 74 72 69 >.#include <stri
0020: 6e 67 3e 0a 23 69 6e 63 6c 75 64 65 20 3c 63 6d ng>.#include <cm
0030: 61 74 68 3e 0a 23 69 6e 63 6c 75 64 65 20 3c 61 ath>.#include <a
0040: 6c 67 6f 72 69 74 68 6d 3e 0a 75 73 69 6e 67 20 lgorithm>.using
0050: 6e 61 6d 65 73 70 61 63 65 20 73 74 64 3b 0a 0a namespace std;..
0060: 76 65 63 74 6f 72 3c 64 6f 75 62 6c 65 3e 20 73 vector<double> s
0070: 6f 6c 76 65 5f 6c 69 6e 65 61 72 5f 65 71 28 20 olve_linear_eq(
0080: 69 6e 74 20 6e 2c 20 76 65 63 74 6f 72 3c 20 76 int n, vector< v
0090: 65 63 74 6f 72 3c 64 6f 75 62 6c 65 3e 20 3e 20 ector<double> >
00a0: 4d 2c 20 63 6f 6e 73 74 20 76 65 63 74 6f 72 3c M, const vector<
00b0: 64 6f 75 62 6c 65 3e 26 20 56 20 29 0a 7b 0a 09 double>& V ).{..
00c0: 76 65 63 74 6f 72 3c 64 6f 75 62 6c 65 3e 20 41 vector<double> A
00d0: 28 56 29 3b 0a 09 66 6f 72 28 69 6e 74 20 69 3d (V);..for(int i=
00e0: 30 3b 20 69 3c 6e 3b 20 2b 2b 69 29 0a 09 7b 0a 0; i<n; ++i)..{.
00f0: 09 09 2f 2f 20 70 69 76 6f 74 0a 09 09 69 66 28 ..// pivot...if(
0100: 20 4d 5b 69 5d 5b 69 5d 20 3d 3d 20 30 20 29 0a M[i][i] == 0 ).
0110: 09 09 09 66 6f 72 28 69 6e 74 20 6a 3d 69 2b 31 ...for(int j=i+1
0120: 3b 20 6a 3c 6e 3b 20 2b 2b 6a 29 0a 09 09 09 09 ; j<n; ++j).....
0130: 69 66 28 20 4d 5b 6a 5d 5b 69 5d 20 21 3d 20 30 if( M[j][i] != 0
0140: 20 29 0a 09 09 09 09 09 7b 73 77 61 70 28 4d 5b )......{swap(M[
0150: 69 5d 2c 20 4d 5b 6a 5d 29 3b 20 73 77 61 70 28 i], M[j]); swap(
0160: 41 5b 69 5d 2c 20 41 5b 6a 5d 29 3b 20 62 72 65 A[i], A[j]); bre
0170: 61 6b 3b 7d 0a 09 09 69 66 28 20 4d 5b 69 5d 5b ak;}...if( M[i][
0180: 69 5d 20 3d 3d 20 30 20 29 0a 09 09 09 74 68 72 i] == 0 )....thr
0190: 6f 77 20 22 6e 6f 20 61 6e 73 65 72 22 3b 0a 0a ow "no anser";..
01a0: 09 09 2f 2f 20 4d 5b 69 5d 5b 69 5d 20 3c 2d 2d ..// M[i][i] <--
01b0: 20 31 0a 09 09 64 6f 75 62 6c 65 20 70 20 3d 20 1...double p =
01c0: 4d 5b 69 5d 5b 69 5d 3b 0a 09 09 66 6f 72 28 69 M[i][i];...for(i
01d0: 6e 74 20 6a 3d 69 3b 20 6a 3c 6e 3b 20 2b 2b 6a nt j=i; j<n; ++j
01e0: 29 0a 09 09 09 4d 5b 69 5d 5b 6a 5d 20 2f 3d 20 )....M[i][j] /=
01f0: 70 3b 0a 09 09 41 5b 69 5d 20 2f 3d 20 70 3b 0a p;...A[i] /= p;.
0200: 0a 09 09 2f 2f 20 4d 5b 2a 5d 5b 69 5d 20 3c 2d ...// M[*][i] <-
0210: 2d 20 30 0a 09 09 66 6f 72 28 69 6e 74 20 6a 3d - 0...for(int j=
0220: 30 3b 20 6a 3c 6e 3b 20 2b 2b 6a 29 20 69 66 28 0; j<n; ++j) if(
0230: 6a 21 3d 69 29 0a 09 09 7b 0a 09 09 09 64 6f 75 j!=i)...{....dou
0240: 62 6c 65 20 72 20 3d 20 4d 5b 6a 5d 5b 69 5d 3b ble r = M[j][i];
0250: 0a 09 09 09 66 6f 72 28 69 6e 74 20 6b 3d 69 3b ....for(int k=i;
0260: 20 6b 3c 6e 3b 20 2b 2b 6b 29 0a 09 09 09 09 4d k<n; ++k).....M
0270: 5b 6a 5d 5b 6b 5d 20 2d 3d 20 4d 5b 69 5d 5b 6b [j][k] -= M[i][k
0280: 5d 20 2a 20 72 3b 0a 09 09 09 41 5b 6a 5d 20 2d ] * r;....A[j] -
0290: 3d 20 41 5b 69 5d 20 2a 20 72 3b 0a 09 09 7d 0a = A[i] * r;...}.
02a0: 09 7d 0a 09 72 65 74 75 72 6e 20 41 3b 0a 7d 0a .}..return A;.}.
02b0: 0a 2f 2f 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d .//-------------
02c0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
02d0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
02e0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
02f0: 0a 2f 2f 20 43 68 65 63 6b 20 74 68 65 20 67 69 .// Check the gi
0300: 76 65 6e 20 6c 69 73 74 20 63 61 6e 20 62 65 20 ven list can be
0310: 61 20 64 65 67 72 65 65 20 6c 69 73 74 20 6f 66 a degree list of
0320: 20 73 6f 6d 65 20 67 72 61 70 68 0a 2f 2f 20 20 some graph.//
0330: 20 4f 28 6e 5e 32 20 6c 6f 67 20 6e 29 0a 2f 2f O(n^2 log n).//
0340: 0a 2f 2f 20 56 65 72 69 66 69 65 64 20 62 79 0a .// Verified by.
0350: 2f 2f 20 20 20 2d 20 53 52 4d 20 33 39 38 20 44 // - SRM 398 D
0360: 69 76 31 20 4c 56 33 0a 2f 2f 0a 2f 2f 28 28 0a iv1 LV3.//.//((.
0370: 2f 2f 20 48 61 76 65 6c 2d 48 61 6b 69 6d 69 0a // Havel-Hakimi.
0380: 2f 2f 20 20 20 49 66 20 47 5b 30 5d 2c 20 2e 2e // If G[0], ..
0390: 2e 2c 20 47 5b 6e 5d 20 28 64 65 63 72 65 61 73 ., G[n] (decreas
03a0: 69 6e 67 29 20 69 73 20 67 72 61 70 68 69 63 61 ing) is graphica
03b0: 6c 2c 0a 2f 2f 20 20 20 74 68 65 6e 20 47 5b 31 l,.// then G[1
03c0: 5d 2d 31 2c 20 47 5b 32 5d 2d 31 2c 20 2e 2e 2e ]-1, G[2]-1, ...
03d0: 2c 20 47 5b 47 5b 30 5d 5d 2d 31 2c 20 47 5b 47 , G[G[0]]-1, G[G
03e0: 5b 30 5d 2b 31 5d 2c 20 2e 2e 2c 20 47 5b 6e 5d [0]+1], .., G[n]
03f0: 0a 2f 2f 20 20 20 69 73 20 61 6c 73 6f 20 67 72 .// is also gr
0400: 61 70 68 69 63 61 6c 2e 0a 2f 2f 29 29 0a 2f 2f aphical..//)).//
0410: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0420: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0430: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0440: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 0a 0a 62 -------------..b
0450: 6f 6f 6c 20 69 73 47 72 61 70 68 69 63 61 6c 28 ool isGraphical(
0460: 20 76 65 63 74 6f 72 3c 69 6e 74 3e 20 47 20 29 vector<int> G )
0470: 0a 7b 0a 09 73 6f 72 74 28 20 47 2e 62 65 67 69 .{..sort( G.begi
0480: 6e 28 29 2c 20 47 2e 65 6e 64 28 29 20 29 3b 0a n(), G.end() );.
0490: 0a 09 76 65 63 74 6f 72 3c 69 6e 74 3e 3a 3a 69 ..vector<int>::i
04a0: 74 65 72 61 74 6f 72 20 62 20 3d 20 6c 6f 77 65 terator b = lowe
04b0: 72 5f 62 6f 75 6e 64 28 20 47 2e 62 65 67 69 6e r_bound( G.begin
04c0: 28 29 2c 20 47 2e 65 6e 64 28 29 2c 20 31 20 29 (), G.end(), 1 )
04d0: 3b 0a 09 76 65 63 74 6f 72 3c 69 6e 74 3e 3a 3a ;..vector<int>::
04e0: 69 74 65 72 61 74 6f 72 20 65 20 3d 20 47 2e 65 iterator e = G.e
04f0: 6e 64 28 29 3b 0a 0a 09 77 68 69 6c 65 28 20 62 nd();...while( b
0500: 20 3c 20 65 20 29 0a 09 7b 0a 09 09 69 6e 74 20 < e )..{...int
0510: 6e 20 3d 20 2a 28 2d 2d 65 29 3b 0a 09 09 69 66 n = *(--e);...if
0520: 28 20 65 2d 62 20 3c 20 6e 20 29 0a 09 09 09 72 ( e-b < n )....r
0530: 65 74 75 72 6e 20 66 61 6c 73 65 3b 0a 09 09 66 eturn false;...f
0540: 6f 72 28 76 65 63 74 6f 72 3c 69 6e 74 3e 3a 3a or(vector<int>::
0550: 69 74 65 72 61 74 6f 72 20 69 3d 65 2d 6e 3b 20 iterator i=e-n;
0560: 69 21 3d 65 3b 20 2b 2b 69 29 0a 09 09 09 2d 2d i!=e; ++i)....--
0570: 2a 69 3b 0a 09 09 69 6e 70 6c 61 63 65 5f 6d 65 *i;...inplace_me
0580: 72 67 65 28 20 62 2c 20 65 2d 6e 2c 20 65 20 29 rge( b, e-n, e )
0590: 3b 0a 09 09 62 20 3d 20 6c 6f 77 65 72 5f 62 6f ;...b = lower_bo
05a0: 75 6e 64 28 20 47 2e 62 65 67 69 6e 28 29 2c 20 und( G.begin(),
05b0: 47 2e 65 6e 64 28 29 2c 20 31 20 29 3b 0a 09 7d G.end(), 1 );..}
05c0: 0a 09 72 65 74 75 72 6e 20 74 72 75 65 3b 0a 7d ..return true;.}
05d0: 0a 0a 73 74 72 75 63 74 20 4d 79 46 72 69 65 6e ..struct MyFrien
05e0: 64 73 0a 7b 0a 09 73 74 72 69 6e 67 20 63 61 6c ds.{..string cal
05f0: 63 46 72 69 65 6e 64 73 28 76 65 63 74 6f 72 20 cFriends(vector
0600: 3c 69 6e 74 3e 20 73 75 6d 46 72 69 65 6e 64 73 <int> sumFriends
0610: 2c 20 69 6e 74 20 6b 29 0a 09 7b 0a 09 09 69 6e , int k)..{...in
0620: 74 20 6e 20 3d 20 73 75 6d 46 72 69 65 6e 64 73 t n = sumFriends
0630: 2e 73 69 7a 65 28 29 3b 0a 0a 09 09 76 65 63 74 .size();....vect
0640: 6f 72 3c 20 76 65 63 74 6f 72 3c 64 6f 75 62 6c or< vector<doubl
0650: 65 3e 20 3e 20 4d 28 6e 2c 20 76 65 63 74 6f 72 e> > M(n, vector
0660: 3c 64 6f 75 62 6c 65 3e 28 6e 29 29 3b 0a 09 09 <double>(n));...
0670: 66 6f 72 28 69 6e 74 20 69 3d 30 3b 20 69 3c 6e for(int i=0; i<n
0680: 3b 20 2b 2b 69 29 0a 09 09 09 66 6f 72 28 69 6e ; ++i)....for(in
0690: 74 20 6a 3d 30 3b 20 6a 3c 6e 3b 20 2b 2b 6a 29 t j=0; j<n; ++j)
06a0: 0a 09 09 09 09 4d 5b 69 5d 5b 6a 5d 20 3d 20 28 .....M[i][j] = (
06b0: 69 3d 3d 6a 20 7c 7c 20 28 69 2b 6b 29 25 6e 3d i==j || (i+k)%n=
06c0: 3d 6a 20 3f 20 30 20 3a 20 31 29 3b 0a 0a 09 09 =j ? 0 : 1);....
06d0: 2f 2f 20 63 61 6c 63 20 23 66 72 69 65 6e 64 73 // calc #friends
06e0: 20 6f 66 20 65 61 63 68 20 6b 69 64 0a 09 09 76 of each kid...v
06f0: 65 63 74 6f 72 3c 64 6f 75 62 6c 65 3e 20 56 28 ector<double> V(
0700: 20 73 75 6d 46 72 69 65 6e 64 73 2e 62 65 67 69 sumFriends.begi
0710: 6e 28 29 2c 20 73 75 6d 46 72 69 65 6e 64 73 2e n(), sumFriends.
0720: 65 6e 64 28 29 20 29 3b 0a 09 09 76 65 63 74 6f end() );...vecto
0730: 72 3c 64 6f 75 62 6c 65 3e 20 41 64 20 3d 20 73 r<double> Ad = s
0740: 6f 6c 76 65 5f 6c 69 6e 65 61 72 5f 65 71 28 20 olve_linear_eq(
0750: 6e 2c 20 4d 2c 20 56 20 29 3b 0a 09 09 76 65 63 n, M, V );...vec
0760: 74 6f 72 3c 69 6e 74 3e 20 41 3b 0a 09 09 66 6f tor<int> A;...fo
0770: 72 28 69 6e 74 20 69 3d 30 3b 20 69 3c 6e 3b 20 r(int i=0; i<n;
0780: 2b 2b 69 29 0a 09 09 09 41 2e 70 75 73 68 5f 62 ++i)....A.push_b
0790: 61 63 6b 28 20 28 69 6e 74 29 66 6c 6f 6f 72 28 ack( (int)floor(
07a0: 41 64 5b 69 5d 2b 30 2e 35 29 20 29 3b 0a 0a 09 Ad[i]+0.5) );...
07b0: 09 2f 2f 20 76 65 72 69 66 79 0a 09 09 66 6f 72 .// verify...for
07c0: 28 69 6e 74 20 69 3d 30 3b 20 69 3c 6e 3b 20 2b (int i=0; i<n; +
07d0: 2b 69 29 0a 09 09 7b 0a 09 09 09 69 6e 74 20 73 +i)...{....int s
07e0: 75 6d 20 3d 20 30 3b 0a 09 09 09 66 6f 72 28 69 um = 0;....for(i
07f0: 6e 74 20 6a 3d 30 3b 20 6a 3c 6e 3b 20 2b 2b 6a nt j=0; j<n; ++j
0800: 29 0a 09 09 09 09 73 75 6d 20 2b 3d 20 28 69 3d ).....sum += (i=
0810: 3d 6a 20 7c 7c 20 28 69 2b 6b 29 25 6e 3d 3d 6a =j || (i+k)%n==j
0820: 20 3f 20 30 20 3a 20 41 5b 6a 5d 29 3b 0a 09 09 ? 0 : A[j]);...
0830: 09 69 66 28 20 73 75 6d 20 21 3d 20 73 75 6d 46 .if( sum != sumF
0840: 72 69 65 6e 64 73 5b 69 5d 20 29 0a 09 09 09 09 riends[i] ).....
0850: 72 65 74 75 72 6e 20 22 49 4d 50 4f 53 53 49 42 return "IMPOSSIB
0860: 4c 45 22 3b 0a 09 09 7d 0a 0a 09 09 72 65 74 75 LE";...}....retu
0870: 72 6e 20 69 73 47 72 61 70 68 69 63 61 6c 28 41 rn isGraphical(A
0880: 29 20 3f 20 22 50 4f 53 53 49 42 4c 45 22 20 3a ) ? "POSSIBLE" :
0890: 20 22 49 4d 50 4f 53 53 49 42 4c 45 22 3b 0a 09 "IMPOSSIBLE";..
08a0: 7d 0a 7d 3b 0a }.};.