fork download
  1. // http://u...content-available-to-author-only...e.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=393
  2. // Kaushik Acharya
  3. #include <iostream>
  4. #include <fstream>
  5. #include <cstdlib>
  6. #include <tr1/unordered_map>
  7. #include <string>
  8. #include <vector>
  9. #include <stack>
  10. #include <limits>
  11. #include <cassert>
  12.  
  13. bool const READ_FROM_FILE = false;
  14.  
  15. template<typename T>
  16. class Edge
  17. {
  18. public:
  19. Edge(T source, T target)
  20. : source_(source)
  21. , target_(target)
  22. {
  23. }
  24. public:
  25. T source()
  26. {
  27. return source_;
  28. }
  29. T target()
  30. {
  31. return target_;
  32. }
  33. private:
  34. T source_;
  35. T target_;
  36. };
  37. //---------------------
  38. template<typename T, typename C>
  39. class Graph
  40. {
  41. public:
  42. Graph(T nVertex)
  43. : nVertex_(nVertex)
  44. {
  45. adjList_.reserve(nVertex_);
  46. vecVisited_.reserve(nVertex_);
  47. vecFinishTime_.reserve(nVertex_);
  48.  
  49. for (T vtx_i = 0; vtx_i != nVertex_; ++vtx_i)
  50. {
  51. adjList_.push_back(std::vector<T>());
  52. vecVisited_.push_back(false);
  53. //vecFinishTime_.push_back(std::numeric_limits<C>::min());
  54. }
  55. }
  56. public:
  57. //graph properties
  58. void add_cost_incrementally(C cost)
  59. {
  60. vecCost_.push_back(cost); //make sure that this function is called in the order of the vertices
  61. vecFinishTime_.push_back(cost);
  62. }
  63. void add_edge(T src, T tgt)
  64. {
  65. adjList_[src].push_back(tgt);
  66. }
  67.  
  68. C compute_project_finish_time()
  69. {
  70. dfs_loop();
  71. // now we have the vertices in topological order in the stack: stk_
  72. C finishTime = std::numeric_limits<C>::min();
  73. while (!stk_.empty())
  74. {
  75. T vertex = stk_.top();
  76. stk_.pop();
  77. finishTime = std::max(finishTime,vecFinishTime_[vertex]);
  78.  
  79. for (typename std::vector<T>::iterator adjIt = adjList_[vertex].begin(); adjIt != adjList_[vertex].end(); ++adjIt)
  80. {
  81. vecFinishTime_[*adjIt] = std::max(vecFinishTime_[vertex]+vecCost_[*adjIt], vecFinishTime_[*adjIt]);
  82. }
  83. }
  84.  
  85. return finishTime;
  86. }
  87. private:
  88. //graph traversal
  89. void dfs_traversal(T vertex)
  90. {
  91. if (vecVisited_[vertex])
  92. {
  93. return;
  94. }
  95. for (typename std::vector<T>::iterator adjIt = adjList_[vertex].begin(); adjIt != adjList_[vertex].end(); ++adjIt)
  96. {
  97. if (!vecVisited_[*adjIt])
  98. {
  99. dfs_traversal(*adjIt);
  100. }
  101. }
  102. vecVisited_[vertex] = true;
  103. stk_.push(vertex);
  104. }
  105.  
  106. void dfs_loop()
  107. {
  108. for (T vtx_i = 0; vtx_i != nVertex_; ++vtx_i)
  109. {
  110. if (stk_.size() == nVertex_)
  111. {
  112. break;
  113. }
  114. dfs_traversal(vtx_i);
  115. }
  116. }
  117. private:
  118. T nVertex_;
  119. std::vector<std::vector<T> > adjList_;
  120. std::vector<C> vecCost_; //vector to time taken by the tasks
  121. //traversal related
  122. std::vector<bool> vecVisited_;
  123. std::vector<C> vecFinishTime_;
  124. std::stack<T> stk_;
  125. };
  126. //---------------------
  127. void tokenize(const std::string strLine, std::vector<std::string>& vecToken)
  128. {
  129. std::string::size_type beginPos = 0;
  130. std::string::size_type endPos = 0;
  131.  
  132. while (endPos != strLine.npos)
  133. {
  134. beginPos = strLine.find_first_not_of(" ",endPos);
  135. if (beginPos == strLine.npos)
  136. {
  137. break; // to handle trailing spaces
  138. }
  139. endPos = strLine.find_first_of(" ",beginPos);
  140. vecToken.push_back(strLine.substr(beginPos,endPos-beginPos));
  141. }
  142. }
  143.  
  144. void process(std::istream& pFile)
  145. {
  146. typedef unsigned int IType;
  147. typedef unsigned int CType;
  148. typedef std::tr1::unordered_map<char,IType> HashMap;
  149.  
  150. HashMap mapTaskIndex;
  151. std::vector<Edge<char> > vecEdge;
  152. std::vector<CType> vecTaskTime;
  153.  
  154. //Note: we need to pre-allocate the vector because the tasks in (task,cost) may not come sequentially
  155. vecTaskTime.reserve(26);
  156. for (IType i = 0; i != 26; ++i)
  157. {
  158. vecTaskTime.push_back(std::numeric_limits<CType>::max());
  159. }
  160.  
  161. //read input and populate graph
  162. std::string strLine;
  163. while (std::getline(pFile,strLine))
  164. {
  165. if (strLine.empty())
  166. {
  167. break;
  168. }
  169. //Now split the string using space as delimiter
  170. std::vector<std::string> vecToken;
  171. tokenize(strLine,vecToken);
  172.  
  173. //record the task(s) and get the edge(s)
  174. char tgtTask = vecToken[0][0];
  175. CType timeTgtTask = atoi(vecToken[1].c_str());
  176. HashMap::iterator it = mapTaskIndex.find(tgtTask);
  177. if (it == mapTaskIndex.end())
  178. {
  179. // add this task
  180. vecTaskTime[mapTaskIndex.size()] = timeTgtTask;
  181. mapTaskIndex.insert(std::make_pair(tgtTask,mapTaskIndex.size()));
  182. }
  183. else
  184. {
  185. vecTaskTime[mapTaskIndex[tgtTask]] = timeTgtTask;
  186. }
  187.  
  188. //edges(if present)
  189. if (vecToken.size() > 2)
  190. {
  191. for (std::string::size_type char_i = 0; char_i != vecToken[2].size(); ++char_i)
  192. {
  193. char srcTask = vecToken[2][char_i];
  194. it = mapTaskIndex.find(srcTask);
  195. if (it == mapTaskIndex.end())
  196. {
  197. // add this task
  198. mapTaskIndex.insert(std::make_pair(srcTask,mapTaskIndex.size()));
  199. }
  200. Edge<char> edge(srcTask,tgtTask);
  201. vecEdge.push_back(edge);
  202. }
  203. }
  204. }
  205.  
  206. // now populate the graph
  207. Graph<IType,CType> graph(mapTaskIndex.size());
  208. //std::cout << mapTaskIndex['E'] << std::endl;
  209. for (IType i = 0; i != mapTaskIndex.size(); ++i)
  210. {
  211. graph.add_cost_incrementally(vecTaskTime[i]);
  212. }
  213. for (std::vector<Edge<char> >::iterator it = vecEdge.begin(); it != vecEdge.end(); ++it)
  214. {
  215. graph.add_edge(mapTaskIndex[(*it).source()],mapTaskIndex[(*it).target()]);
  216. }
  217.  
  218. CType total_time = graph.compute_project_finish_time();
  219. std::cout << total_time << std::endl;
  220. }
  221.  
  222. int main(int argc, char* argv[])
  223. {
  224. std::ifstream pFile;
  225. if (READ_FROM_FILE)
  226. {
  227. pFile.open("D:/cpp_practise/online_judge/uva/452_project_scheduling_input.txt",std::ios::in);
  228. assert(pFile.is_open() && "input file not opened");
  229. }
  230.  
  231. unsigned int nCase;
  232. std::string strLine;
  233. std::vector<std::string> vecToken;
  234.  
  235. if (READ_FROM_FILE)
  236. {
  237. std::getline(pFile,strLine); // read nCase
  238. tokenize(strLine,vecToken);
  239. nCase = atoi(vecToken[0].c_str());
  240. std::getline(pFile,strLine); // read empty line
  241. }
  242. else
  243. {
  244. std::getline(std::cin,strLine); // read nCase
  245. tokenize(strLine,vecToken);
  246. nCase = atoi(vecToken[0].c_str());
  247. std::getline(std::cin,strLine); // read empty line
  248. }
  249.  
  250. for (unsigned int case_i = 0; case_i != nCase; ++case_i)
  251. {
  252. if (READ_FROM_FILE)
  253. {
  254. process(pFile);
  255. }
  256. else
  257. {
  258. process(std::cin);
  259. }
  260. if (case_i < (nCase-1))
  261. {
  262. std::cout << std::endl;
  263. }
  264. }
  265.  
  266. if (READ_FROM_FILE)
  267. {
  268. pFile.close();
  269. }
  270.  
  271. int gh = 0;
  272. }
  273.  
  274. /*
  275. http://o...content-available-to-author-only...a.es/board/viewtopic.php?f=5&t=6272&p=214193
  276. http://o...content-available-to-author-only...a.es/board/viewtopic.php?f=5&t=6272&p=179019&hilit=452#p179019
  277. http://o...content-available-to-author-only...a.es/board/viewtopic.php?p=214184#p214184 Test Cases
  278. http://stackoverflow.com/questions/9235296/how-to-detect-empty-lines-while-reading-from-istream-object-in-c
  279. */
Success #stdin #stdout 0s 3496KB
stdin
100

A 52 
B 98 A 
C 68 A
D 97
E 9 C
F 37 CDE
G 69 DEF
H 42 E
I 5 CEGH
J 60 BFGI
K 76 CEFGHJ
L 55 ABFHK
M 33 BCDEHJ
N 96 ABCDEFIM
O 33 ABCHIN
P 98 BCGHJLN
Q 11 BEFHKLOP
R 91 ABCDFHIJKMNQ
S 13 CDEKLM
T 57 CDEFLPQS
U 13 ABCFGHIJLMNPQST
V 5 ACFGHJPQRST
W 2 BCDFGHKOQRSTUV
X 93 CDEGJKMOPQRT
Y 94 ABCEHJMPQRSUW
Z 92 BEHILNOPQRTUY

A 76
B 30
C 70
D 34 BC
E 52 ACD
F 82 CDE
G 9 AF
H 99 ACDFG
I 53 ABDEFG
J 2 DH
K 37 AEGHJ
L 14 ADEFHJK
M 6 ADEFGIJL
N 85 BJ
O 79 BGIKLMN
P 9 ACKLNO
Q 83 ACDEHIJLNP
R 9 BCEIJMOPQ
S 14 BCDEJMOR
T 6 BCEFGHKLMQ
U 67 EHIJLNOPQST
V 39 IJKLMNQRSU

A 2
B 37
C 16
D 43 ABC
E 20 AB
F 29 ABC
G 36 ADEF

A 35
B 20
C 72
D 70 BC
E 2 BCD
F 90 ABC
G 77 EF
H 98 BCEF
I 47 ABE
J 7 DHI
K 76 ADFHJ
L 13 ADEFGHK
M 8 ADFI
N 83 ABDFHJL

A 79
B 57
C 87
D 48 AC
E 8 D
F 67 AD
G 90 ACDF
H 54 DFG
I 90 ABDEFGH
J 84 BGHI
K 50 BDEGHI
L 94 ACEGJK
M 63 ABCFGHIK
N 91 ABFKLM
O 77 AEGHL
P 42 HMNO
Q 76 BCEFGIKLNO
R 71 AFIJKQ
S 78 ADEMNOPQR
T 47 DEFGHIJ
U 24 GHIJLMNT
V 93 BDEGHJKLOQSU
W 69 ACFHIKLMORT
X 7 ACEFGIJLMNORSTU
Y 49 CDFGILMNORSTUWX
Z 30 ABCDEGHLMOPSTUVWXY

A 80
B 73 A
C 77 A
D 96 B
E 31 BCD
F 93 CD
G 77 ABDF
H 86 ABDEF
I 33 BCFGH
J 8 ABCEF
K 2 ADFGHJ
L 71 BDEIJK
M 3 DGJL
N 67 BHJL
O 86 BDEGK
P 17 ACFJKLMO
Q 98 EGHJMNOP
R 31 BCHIJKLMNOPQ
S 59 ABCEGHKLMNQ
T 42 ACDEJKLPQR
U 88 ACEFHJMNOR
V 52 ABCDHOPST
W 9 FJKLNORSUV
X 50 CEGHIJKLMNPQRW
Y 54 CDEGHKMOQSUVW

A 48
B 88 A
C 14 AB
D 92 ABC
E 86 ABC
F 93 ADE
G 22 ABDEF
H 15 ACEFG
I 41 ABDEFH
J 3 ACE
K 74 BDJ
L 2 ACDEHIK
M 89 ABCEFIJ
N 97 EGIKLM
O 41 ABFGJN
P 18 ABCDEFGHIJLN
Q 49 BCDIJKLP
R 47 AEFGIJKLMOP
S 60 ACDEHJKLPR
T 34 DEFHJKLQ
U 42 ABCFHKNOPRT
V 65 CFGKLMOPS
W 17 BDFHKNOPQRSTUV
X 45 CDEGNPVW

A 59
B 79 A
C 8
D 5
E 29 AD
F 13 ABCD
G 83 ACDF
H 61 DEG

A 85
B 89 A
C 35 A
D 18 ABC
E 40 D
F 27 AB
G 91 ACDEF
H 67 D

A 58
B 88
C 93
D 37 B
E 55 AD
F 19 ABD
G 93 DE

A 64
B 40 A
C 52
D 32 ABC
E 44 ACD
F 22 D
G 17 ACD
H 51 BCFG
I 98 ACG
J 81 ACDH
K 70 AG
L 89 ABCGH
M 8 IKL
N 86 ADHIJKL
O 16 ACFIM
P 17 EFHLMO
Q 60 ABCDIKLN
R 98 BCEHJKNP
S 59 ACEGHKOPR
T 3 DEGORS

A 21
B 35
C 92
D 9 A

A 30
B 75 A
C 69 B
D 10 AC
E 23 BD
F 71 BD
G 95 ACF
H 98 CDE

A 13
B 79
C 44
D 49
E 96 ACD

A 3
B 44 A
C 21
D 71
E 30 ABD
F 20 AD
G 65 CEF
H 86 ACDEG
I 41 ABCEGH
J 6 ADI
K 87 EGJ
L 5 ABCDEGJK
M 24 AGHIJKL
N 75 ABCDFGHM
O 16 BCDFGIKMN
P 61 CDEIJLNO
Q 24 AFHILMNOP
R 1 BCEFJLNQ

A 47
B 14 A
C 22 AB
D 6 A
E 0 AB
F 72 B
G 2 CEF
H 35 DE
I 16 BEH
J 74
K 99 ACFHI
L 48 ACEFHK
M 74 CFGJK
N 47 CDFGHJLM
O 35 BGIJKLM
P 76 EGIO
Q 71 CHIJN
R 95 BGJNP
S 35 ACEGHKLMP
T 97 CDHJKLPQ

A 75
B 78
C 76 A
D 48 B
E 87 A
F 76 CDE
G 68 DE
H 7 ABDE
I 96 CEH
J 64 CDEH
K 22 BFHIJ
L 37 ABCK
M 64 ACHIKL
N 68 ABFGIJLM
O 96 ABCDEHJKLN
P 81 AGHIJMO

A 89
B 66 A
C 55 AB
D 57 B
E 56 AC
F 1 AD
G 65 ABDEF
H 43 CE
I 50 AF
J 79 BCEFG
K 57 ABDEH
L 1 BEG
M 62 ACEFJL
N 2 BEFGHIJM
O 34 BEGHILMN
P 25 GHIKLMN
Q 9 ABGLMNOP
R 75 ABCDEFGHLP
S 88 IJKMQR
T 9 CEHIKLNOR
U 2 BCDFGHLOPT
V 64 ABDGJLNPRSU
W 32 ABGHMNQSTUV
X 53 ACIJLMPRS
Y 57 ADHJMOQRT
Z 29 ABEFGILNQSTUWX

A 91
B 30
C 27 B
D 64 B
E 33 AD
F 94 C
G 83 BEF
H 17 ABEF
I 51 EFH
J 61 BCDEF
K 19 DEGHI
L 87 CDJ
M 83 CDFHI
N 75 BCDEJM
O 9 BCEFGHKLMN
P 33 ACEFGIJO
Q 25 ADHLMNO
R 57 CDEFHIKL
S 47 CDFGKNPQ
T 86 ABCIMNQR
U 35 GHIJKQ
V 11 DGLMOPQR
W 74 BCFJNOPQRTV
X 95 CDFGKNOQSW
Y 78 AEFGHILNORVWX

A 16
B 31
C 38
D 19 AC

A 65

A 99
B 94 A
C 61 AB
D 56 B
E 41 ABCD
F 18 A
G 72 AC
H 8 ACDE
I 78 BCDF
J 90 BEFI
K 21 CEFGHIJ
L 53 ADEFHIK
M 92 BCDEGJKL
N 76 CDFGIK
O 94 ACDGIJKLM
P 22 DGHIJLNO
Q 22 BCEFGHLMO
R 7 ABCDHJKLNP
S 72 ABCEFGJKOPR
T 69 EFILMNPR
U 82 CJKNPQR
V 39 FJ
W 13 BCDGHIKLNOQRSTU
X 44 AEJKOPQRTUV
Y 6 ABCFHJKLMNOQTV

A 46
B 73
C 33 A
D 38 C
E 8 ABCD
F 6 AE
G 96 AF
H 96 DE
I 33 CDFG
J 88 ABCDEGH
K 79 ABCEFH
L 77 BDHJK
M 19 CGHIL
N 33 H
O 39 ABEFGIJKMN
P 37 CEFGHKN

A 72
B 38
C 85 AB
D 24 A
E 58 ABC
F 37 BD
G 49 CD
H 54 ACD
I 38 FG
J 69 ADEFHI
K 63 CEFGJ
L 20 FIJK
M 29 DFHIKL

A 2
B 71 A

A 12
B 38
C 42 B

A 99
B 53 A
C 22
D 51 C
E 15 D
F 99 CE
G 68 ABDF
H 6 ACE

A 79
B 15 A
C 73 B
D 73 C

A 57
B 22 A
C 84
D 45 C
E 1 CD
F 34 BCDE
G 60 DEF
H 44 CEF
I 29 BCF
J 49 AFI
K 90 BCEFG
L 52 CDGH
M 72 FGIL
N 12 AJK
O 8 EGHMN
P 62 BEHKLMN
Q 77 ACEFGIJK
R 35 FINQ
S 28 CGJNQ
T 54 CFIKLNPQ
U 9 FHKMPQST
V 23 CEGHIJLMOQTU

A 90
B 77 A

A 45
B 92 A
C 64 A
D 58 C
E 95 AB
F 31 ABCE
G 38 AE
H 46 CFG
I 12 ADEFH
J 30 ACFGHI
K 95 CGH
L 38 BFGJK
M 44 ACEGJK
N 41 ABDEFGHIJKLM
O 70 ACEFGHJN
P 60 BCEFGNO
Q 96 BCEFGIJKMP
R 5 ABCEFGHIJKNOPQ
S 69 CDEHIKNPQR
T 90 DGHIJLM
U 25 ABCDEGIMOPQR
V 20 ABCDEGHJLQSU
W 89 ABCHJLMOQSUV

A 46

A 89
B 72 A
C 99 A
D 40 AB
E 69 ABD
F 30 ABCD
G 22 CF
H 8 EF
I 82 BCFGH
J 44 CDEGH
K 59 H
L 49 DIJ
M 37 BEGJ
N 42 BCEHK
O 21 BCDFKN
P 72 BDFIJLM
Q 48 BEFIKLO
R 61 ACFIJKMNPQ
S 44 EKLNOPQR
T 61 ABDIJKLQ
U 62 ABCEGKLRT
V 14 BEFGHIJMOPQSU
W 19 BCGHIJLMNQTV
X 34 CFGHIJMNOSTU
Y 59 ACDGILPQSUX
Z 48 ABCEFGHKLMRUVWXY

A 21
B 59
C 22 B
D 59 AB

A 77

A 25
B 95 A
C 0 AB
D 26 ABC
E 65 D
F 97 ABDE
G 93 AF
H 67 AEG
I 40 DEG
J 67 BDFH

A 90
B 48 A
C 9 A
D 53 ABC
E 89 BC
F 90 ACDE
G 49 DE
H 38 ABDF
I 32 DE
J 94 BDFGHI
K 31 BFGI

A 6
B 7
C 62 B
D 30 A
E 81 AC
F 85 BCDE
G 36 AB
H 94 ABE
I 27 BCE
J 34 ACEH
K 15 ACDEGHJ
L 44 ABCEHJK
M 42 BDFGHJ
N 55 ABDE
O 97 ABDGHLMN
P 95 AEFGHIKL
Q 89 ABELM
R 36 ABCFJMOP
S 6 DGHJKOPQ
T 38 ACEFHIJKLMNOQR
U 8 ABCEGHIJKPT
V 83 ACEFGIJLQRSTU
W 29 ABEJLMNSUV

A 37
B 66 A
C 65 A
D 78 ABC
E 45 ABCD
F 21 AE
G 79 ABCDF
H 88 BCEG
I 29 CEGH
J 46 EI
K 35 ACDIJ
L 61 ABEFK
M 43 ABDEHI
N 84 EGHJLM
O 61 DEFGIJN
P 96 BIJMN
Q 86 AEGHIKLO
R 66 ABEGKLO
S 3 ACEFGKNOQ
T 40 FMNOPS
U 37 BDEFHJKLMNOPST
V 72 BDFGKLMRST
W 18 ABCFHMOSTU
X 41 DEFHJKLMOR
Y 8 ACEFHKLMNOSX

A 51
B 45 A
C 9 AB
D 88 ABC
E 57 B
F 75 AE
G 10 ABCDEF
H 23 EG
I 59 BD
J 77 ACHI
K 94 CEHI
L 16 BCFGH
M 88 ADEH
N 97 BEFJK
O 62 EFLM
P 57 AHLMO
Q 41 BFIJNOP
R 99 ACDFIJLMNOQ
S 31 ACDEHJKP
T 74 CDIJKPQS
U 25 ADGJM
V 75 ACDFGHLNORST
W 81 CIKLMNU
X 5 ABCHIKLMNPTUW

A 14
B 10
C 29 AB
D 34
E 79 CD
F 17 CDE
G 23 CDE
H 19 ACDE
I 40 ABDGH
J 75 ABFGHI
K 32 BDFHJ
L 91 EJK
M 89 ABDFIJK
N 53 EHL
O 41 ABEJL
P 80 BDN
Q 17 BDGJKLMNO
R 54 ABDEGHIJMNOPQ
S 42 ABCGHKOP
T 85 ADFHJKMOP
U 92 CFGHIJKLMNPS
V 8 CGJPQSU
W 24 DEHLMORSUV
X 66 CEFGHIJKLOUW
Y 13 BFIJLNQSTW

A 37
B 60 A
C 31
D 13 AC
E 1 ABD
F 10 C
G 35 A
H 16 ABCDFG
I 77 CFG
J 64 DHI
K 76 BFG
L 85 ABEGJ
M 2 ABCEGH

A 87
B 24 A
C 77
D 44 AC
E 6 C
F 48 ABCD
G 25 EF
H 22 ACDEF
I 47 ABGH
J 13 AE
K 68 BCEFG
L 22 HIJ
M 67 ABCDEFHIJKL
N 84 CDEFGHIJKLM
O 83 BCGILMN
P 46 EFGLNO
Q 11 FGJLO
R 80 CDFIJLNO
S 21 ABDEFHILOPR
T 76 DFLMNOPS

A 79
B 83
C 70 A
D 99 C
E 26 B
F 59 ACD

A 58
B 82
C 47 AB
D 51
E 85 D
F 52 BC
G 38 ACF
H 28 EG
I 90 ABF
J 50 CDEFGI
K 19 BGIJ
L 18 ACGHJK
M 3 BGHJKL
N 17 CDEFGHIJL
O 11 ABEFHKLM
P 61 BCGIK
Q 59 ABEFIJKLN
R 60 ACDEFGHJNOPQ
S 55 BDFHIKLOP
T 60 ABEHLNOP
U 19 ACFGIJMNOQRST
V 53 BDFGHIJLNPS
W 53 ABDEGIJKLOQSTV
X 42 CEFHKLMNPQRSVW
Y 12 CDJOSTWX
Z 57 BCDEFGHKNOPQRSTVY

A 12
B 79
C 39
D 33 B
E 7 BD
F 20 BCDE
G 36 CF
H 61 ABCEF
I 4 CG
J 65 AF
K 69 ACEGHI
L 29 ADGH
M 36 FK
N 81 ABFIJKL
O 22 ACFJM
P 99 ABDEGHJLO

A 55
B 27
C 3 B
D 90 BC
E 27 ABC
F 96 ACE
G 98 ABE
H 48 BCEF
I 69 AEGH
J 44 CDI
K 84 EGHI
L 31 BCDFGHJK
M 70 BEHK
N 61 ADFGIM
O 91 BCEIJM
P 71 CIKNO
Q 20 ACDFGO
R 54 CFHKLMN
S 73 BEFHIKLMNOR
T 89 CGHJLMNOPQS
U 18 ACEFGHIJLMNOPQST
V 74 ACEFGKMOQS
W 48 BCDHJKLNPQRSUV
X 38 ABDEHJKNPQSW
Y 35 ACDEIPQRSTVWX
Z 57 BCFGOSXY

A 57
B 48
C 56
D 3 A
E 28 A
F 52 CE
G 23
H 49 ABDG
I 2 ABCDE
J 34 CDG

A 20
B 42 A

A 87
B 2 A
C 32 B
D 84 ABC
E 8
F 36 ABC
G 1 B
H 2 ACEF
I 49 ABEG
J 35 ABEH
K 72 ADJ
L 32 ABDEFGI
M 78 CDGIJK
N 51 ACDHJLM
O 93 ABCDFGHJMN
P 59 ABCIJMO
Q 76 ABCEFGIJLNOP
R 92 BCEFGMO
S 83 ABCDGHJLMOQ
T 10 BEHIKOPRS
U 48 ADEFMORT
V 67 ABCEFMNOQRTU
W 30 ABCDEGJLMNPQTV
X 38 BCDEFGHKLNOQTUVW
Y 54 AFGLMNOPQSTUX
Z 46 CEFGHJLPRTWY

A 22

A 38
B 71 A
C 95 A
D 89 B

A 1
B 29
C 99
D 53 AB
E 11 BCD
F 65 CD
G 10 BC
H 52 C
I 16 ABCG

A 8
B 46 A
C 48
D 10 B
E 49 C
F 78 D
G 60 B
H 17 BE
I 15 BH
J 17 BCGHI
K 15 ABCDEGIJ
L 4 BCDFGK
M 8 BFGHIJ
N 70 ABFGHKM
O 90 CGIKM
P 79 ABEIKLMNO
Q 61 ABEFGHJMNO
R 56 ABCEGHIJKOPQ
S 87 DGILNQ
T 74 ABCFHJMS
U 32 ADGIJMNPT
V 71 BEJKMPRSTU
W 65 BEJKMNOQRSU
X 39 ACEIJLNOPQTV

A 94
B 19 A
C 35 B
D 26 BC
E 54 BD
F 48 ABC
G 67 ABCDEF
H 9 ABCDG
I 62 BCDG
J 69 ADFH
K 45 BCDEGIJ

A 63
B 26 A

A 35

A 30
B 76 A
C 51 B
D 26 ABC
E 19 BD
F 69 AE
G 32 ABCE
H 8 BCDEG
I 68 DEGH
J 79 BEF
K 11 BFGH
L 0 ADFGHJK

A 71
B 43
C 94 A
D 5

A 89
B 60
C 18 A
D 42 ABC
E 23 B
F 20 ABC
G 68 ACDEF
H 22 CF
I 16 BDEH
J 10 CDEFG
K 50 ABCDEFI
L 82 CEHJK
M 90 CEFHIJ
N 63 BCDEFGHJL
O 69 ABDEGHIKMN
P 62 DEIJLMNO
Q 16 EGHIJLMNOP
R 17 GHIMOP
S 37 AEFKLMNOQR
T 30 ACDGIMPQR
U 53 CDEGHLMNPQR
V 60 CDFILMNPST
W 28 BCDEGHMOPSU

A 47
B 52
C 15 AB
D 17 BC
E 7 AC

A 28
B 42 A
C 58 A
D 9 AC
E 98 ACD
F 33 ABCE
G 66 CDEF
H 3 BCF
I 66 BCDEG
J 49 BDF
K 7 BCDEJ
L 50 ABCHIJK
M 48 ABDEFGIK
N 26 AEGIJLM
O 93 DEFGKLM
P 36 ADIKO
Q 49 ABFGHLMOP
R 48 ADEHIMNOQ
S 93 ABEJKLMNO
T 30 ADGHIJKQRS

A 53
B 8
C 62 AB
D 97 A
E 82 A
F 4 BCDE
G 90 ABDF
H 54 ACDEF
I 80 ADFG
J 94 ACEG
K 41 ACEFGJ
L 36 ADEGJK

A 60
B 15 A
C 67 B
D 85 BC
E 63 A

A 11
B 17
C 8 AB
D 75 B
E 76 BC

A 87
B 4 A
C 17 A
D 37 B
E 97 ABD
F 62 ABD
G 49 AF
H 31 B
I 86 ACG
J 67 ABCDFI
K 82 BDF
L 84 BCEFIK
M 86 ACEFHIJK
N 63 ADGIJK
O 0 ACEGHIKMN
P 20 ACHILNO
Q 52 BCFGHJKLO
R 46 CGHKLMN
S 84 FGHJM
T 20 BCHLMOP
U 50 BFHIJKLPQT
V 78 CEGJLMNQR
W 75 ABCFHJLMNQSV

A 46
B 77
C 51 AB
D 39 A
E 16
F 20 BDE
G 63 ABCEF
H 40 DFG
I 39 CDFG
J 48 ACDGH
K 8 ABCDEFGI
L 13 ABCHK
M 69 ACEHJL
N 88 ABDEIL
O 64 CDFIN
P 51 BDEFHIJKM
Q 25 BDEGHIKL
R 19 ABHILP
S 81 CDEFHIKMOQR
T 18 ACDEGHJKMOPQS
U 20 ADEGHIKMOQRST
V 40 BCNOPRT

A 30
B 7
C 36 B
D 27 ABC
E 33 ACD
F 84 BE
G 71 AB
H 63 BCDFG
I 31 BCDGH
J 73 ABCEGHI
K 33 ABCFGHI
L 57 DEGHIJ

A 24
B 80
C 70 AB
D 0 C
E 94 BCD
F 69 BE
G 40 BDF
H 44 DEF
I 80 ABCEF
J 87 ADGI

A 50
B 49
C 94 AB
D 15
E 55 BD
F 53 ABCD
G 18 ACD
H 66 AB
I 43 ACDEFH
J 71 DE
K 27 BFHI
L 73 CDEFG
M 79 BEFHIJKL
N 88 BCEHIKM
O 63 ABCEHJKLN
P 96 ABIJKL

A 27
B 31
C 17 B
D 23 ABC
E 78 BC
F 27 CE
G 43 CEF
H 76 ABCE

A 47
B 11 A
C 20 AB
D 64 ABC
E 21 D
F 26 BC
G 70 BCDEF
H 97 ABCEFG
I 60 AG
J 75 AEHI
K 54 ACEGHIJ
L 82 CEFIJK
M 15 ABDEHIL
N 81 ABIK
O 59 ABDFGHIJKN
P 85 DGHIJLMN
Q 38 BCDGHIKMOP

A 75
B 46 A
C 39 A
D 90 B
E 49
F 93 ACDE

A 23
B 91
C 17
D 96 ABC
E 79 AD
F 5 AC

A 16
B 1
C 69 A
D 47 B
E 23 ABD
F 87 ABD
G 76 ABC
H 47 BCDF
I 54 CG
J 13 B
K 56 DG
L 82 CDFGHIK
M 78 ABCDEFGHIJL
N 40 IJ
O 29 AEFGHM
P 32 LO
Q 55 BCEGIJLOP
R 42 ABDFGIKLMO
S 91 ADEFKLMPQ
T 20 BCFGMNPS
U 23 BDFGLMOPQRST
V 95 BDFGMNU
W 43 ABCHIKLMNOQRSTU
X 32 FGKLNORST
Y 44 ACEFHIMNRS
Z 35 ABCDFIKNPQXY

A 99
B 51 A
C 83 B
D 76 A
E 21 AD
F 86 CE
G 48 BF
H 19 ADEFG
I 34 BCG
J 11 ACEH
K 30 CDEFIJ
L 74 ABCFHI
M 67 AL
N 89 ABEIM
O 73 ABCFGIJM
P 48 CGJKNO
Q 41 CEGHM
R 56 ADEGIMQ
S 45 ABEFHJKMNR
T 64 GIJKNPRS
U 18 CGILOPQS
V 2 AFILOQRS
W 84 CDEGHKRSV
X 4 BDEGHKMNOPQRTUW

A 58
B 80
C 50 AB
D 7 ABC
E 4 BD
F 53 CDE
G 74 CD
H 69 AG
I 52 ACFG
J 90 ACGI
K 50 ABCDFGIJ
L 45 ABCEGH
M 99 ACDEFIJK
N 66 BDGHIJKLM
O 92 BDHJN
P 59 BCDIJKLN
Q 40 ABEFIJL
R 69 ACDFGHIOPQ
S 45 CEGJLNOR
T 41 ADGHIOPQ
U 75 BCDEHJKNORST
V 51 ADEFHIJNORST

A 35
B 81
C 42 AB
D 3 ABC
E 87 A
F 33 BE
G 43 ACDE
H 55 ABD

A 40
B 11
C 97 B
D 53 AB
E 73 BCD
F 70 CE
G 74 ABCDF
H 94 BEF
I 45 BDFH
J 24 DGHI
K 33 BEFHIJ
L 80 CEGHIK
M 43 CGHIKL
N 34 ACEFHIL
O 31 FGHIMN
P 55 BJKLO
Q 79 BEFKMOP
R 73 CFGHKMNOQ

A 83
B 86 A
C 18 B
D 23 C
E 81 C
F 3 CDE
G 37 ABF
H 8 ACDFG
I 17 BDG
J 94 AEFG
K 49 EFGIJ
L 15 BEFIK
M 15 BEJK
N 44 BCDGIK
O 79 ABCEHIN
P 91 BCDHILM

A 17
B 41 A
C 85
D 3 BC
E 14 ABC
F 21 BDE
G 82 BF
H 66 CDE
I 57 ACGH
J 35 BGI
K 79 BCFGHJ

A 12
B 34 A
C 69 B
D 69 A
E 99 B
F 55 ABE
G 11 ACEF
H 21 ACD

A 27
B 35
C 84 A
D 37 A
E 18 AD
F 69 BC
G 88 ABE
H 48 AG
I 88 ADGH
J 53 BDEGH
K 88 AB
L 72 BDFGHK
M 31 BFIJKL
N 63 ABEJL
O 43 AFGHKMN
P 23 CDFIKLO
Q 55 FGHIKMO
R 84 BCDFGKLMOP
S 65 CDEFHKMNQ
T 69 EFGJLMRS
U 97 BILMOQT
V 17 ADEFGJLMNPQ
W 29 ADEFJKLSTU
X 34 ACFJNPRTUW

A 98
B 85

A 72
B 91 A

A 1
B 79
C 81
D 91 AB
E 83 BCD
F 83 BDE
G 33 ABDEF
H 20 BCDEF
I 33 BCFH
J 98 ABCGHI
K 56 ACDEGI
L 32 CDEFH
M 9 ADFGJK
N 4 ABCEFHI
O 87 ABK
P 13 BDHILNO
Q 74 EGHIJLMO
R 41 ABCFGIM
S 35 ABFHP
T 62 ADHIKMPRS
U 90 AHLRST
V 3 ABCDEPRSU
W 9 BCHJKLOQRTUV

A 53
B 90 A
C 61 AB
D 52 B
E 16 AD
F 49 DE

A 47
B 15
C 84 B
D 0 AC
E 69 A
F 19 ABCD
G 75 AF
H 15 ADFG
I 43 ACEGH
J 68 CDEFHI
K 82 ACEFGI
L 47 BCDEGJ
M 64 BEFGJK
N 83 ABCEFGL

A 61
B 65 A
C 77

A 88
B 92
C 79
D 69 AB
E 58 BC
F 38 C
G 68 BC
H 4 F
I 59 H
J 96 BCDFG
K 90 CEFHI
L 12 EGHJK
M 69 BCHJL
N 98 ABCEFGIJK
O 92 CDGIJKM
P 96 CEFGHJ

A 56
B 22
C 54 A
D 45 AB
E 26 ABD
F 12
G 99 ACDF
H 26 AD
I 24 ADFGH
J 27 ABCDEF
K 39 CEFHIJ
L 13 ACDGHI
M 86 ABDEGHJ
N 93 ABFGIJL
O 63 CEJKLMN
P 75 DGHIJN
Q 19 ACFIJMNOP
R 23 ACDEGIJQ
S 96 DGIMNQR
T 84 BCDGKNPQ
U 68 ADEFGHNQRT
V 13 ABFNPQRTU
W 44 ABDGIKLMNOPRSUV
X 57 ADHIJKLNQRSVW
Y 49 ADFHIJMNOSX

A 98
B 55 A
C 49 A
D 96 AC
E 93 ABC
F 74 ACE
G 38 ACDF
H 96 AEFG
I 81 ABCGH
J 23 BCDEFGI
K 39 BFJ
L 42 CDFHIJK
M 62 BCDHJ
N 83 ADEGHIJKM

A 27
B 94
C 41 B
D 39 BC
E 86 ABD
F 31 ACDE
G 44 ABC
H 9 ADG
I 69 ABCG
J 59 BCDEGI
K 14 ABHI

A 74
B 55
C 51 A
D 33
E 48 BCD
F 34 BC

A 80
B 68 A
C 13 AB
D 18 A
E 15 D
F 29 ABDE
G 15 ACDF
H 32 DEF
I 66 ABFH
J 4 ACDEFGI
K 12 BCFHI
L 11 ABEFGHJK
M 76 CDEGK
N 46 ACGIJK

A 36
B 17
C 12
D 93 AC
E 18 BCD
F 55 AD
G 12 AE
H 64 BDEG
I 21 BCDEFG
J 95 CEG
K 35 ABCDEHI
L 74 ACFHIJK
M 87 EFL
N 77 BFGJLM
O 9 ACEFGH
P 24 ABCDFGHJKLNO
Q 45 BFGIJMP
R 31 ACELMO
S 73 ACDEGHJLNO
T 76 EFGHKMNOQRS

A 39
B 76
C 80
D 79 C
E 25 CD
F 63 AD
G 37 ABCE
H 58 CEG
I 91 ABCDFG

A 14
B 95 A
C 94 B
D 31 B
E 46 D
F 23 B
G 95 AF
H 41 CDEF
I 78 ACDH
J 75 ABDEFI
K 64 ABCFHJ
L 9 ACIJK
M 48 CDFJKL

A 75
B 53 A
C 53
D 14 AC
E 15 BCD
F 97 BC
G 16 BF
H 51 AB
I 46 BDGH
J 39 BDEGH
K 53 ADEFGHIJ
L 3 CEFGI

A 45
stdout
824

733

116

439

1053

885

874

295

323

273

544

92

350

145

592

521

633

787

744

57

65

837

450

425

73

80

255

240

496

167

905

46

745

118

77

535

449

628

931

683

748

298

684

307

673

426

922

137

62

1010

22

198

164

615

418

89

35

350

165

617

84

664

415

227

101

683

557

411

480

500

202

679

304

266

722

774

849

181

808

574

373

211

745

98

163

744

260

449

126

443

748

703

319

173

363

645

313

518

340

45