|
|
Problem can be reduced to edges in complete graph: Given no. of edges, what is the max no. of vertices in a complete graph? n = 3 1 2 0 0 2 3 0 0 0 3 1 0 n = 6 1 2 3 0 0 0 3 4 5 0 0 0 0 5 6 1 0 0 0 0 6 2 4 0 n = 10 1 2 3 4 0 0 0 0 4 5 6 7 0 0 0 0 0 7 8 9 1 0 0 0 0 0 9 10 2 5 0 0 0 0 0 10 3 6 8 0 n = 15 1 2 3 4 5 0 0 0 0 0 5 6 7 8 9 0 0 0 0 0 0 9 10 11 12 1 0 0 0 0 0 0 12 13 14 2 6 0 0 0 0 0 0 14 15 3 7 10 0 0 0 0 0 0 15 4 8 11 13 0 n = 21 1 2 3 4 5 6 0 0 0 0 0 0 6 7 8 9 10 11 0 0 0 0 0 0 0 11 12 13 14 15 1 0 0 0 0 0 0 0 15 16 17 18 2 7 0 0 0 0 0 0 0 18 19 20 3 8 12 0 0 0 0 0 0 0 20 21 4 9 13 16 0 0 0 0 0 0 0 21 5 10 14 17 19 0 n = 36 1 2 3 4 5 6 7 8 0 0 0 0 0 0 0 0 8 9 10 11 12 13 14 15 0 0 0 0 0 0 0 0 0 15 16 17 18 19 20 21 1 0 0 0 0 0 0 0 0 0 21 22 23 24 25 26 2 9 0 0 0 0 0 0 0 0 0 26 27 28 29 30 3 10 16 0 0 0 0 0 0 0 0 0 30 31 32 33 4 11 17 22 0 0 0 0 0 0 0 0 0 33 34 35 5 12 18 23 27 0 0 0 0 0 0 0 0 0 35 36 6 13 19 24 28 31 0 0 0 0 0 0 0 0 0 36 7 14 20 25 29 32 34 0 why? n=10 1 2 2 3 3 4 4 5 5 6 6 7 7 8 9 10 1 10 ---- 9>6 is it wrong, why? Edited by author 18.04.2009 00:35 Edited by author 26.11.2010 13:52 Probably easier to grasp: n=10 5 4 1 2 3 4 4 1 5 6 7 4 2 5 8 9 4 3 6 8 10 4 4 7 9 10 n=15 6 5 1 2 3 4 5 5 1 6 7 8 9 5 2 6 10 11 12 5 3 7 10 13 14 5 4 8 11 13 15 5 5 9 12 14 15 sorry for my poor English.. I've got WA many times because of this... this is untrue, it will truncate Is the order in which the colors of flags are specified, or the order in which flags are printed important? 3 1 2 4 3 1 3 4 2 2 3 Is it wrong? No, it's a right answer. So which one we will choose to display? n = 4 answer : 4 2 1 2 2 1 4 2 2 3 2 3 4 no. 1 2 & 3 4 does not have a common color my opinion answer: 4 3 1 2 3 3 1 2 4 3 1 3 4 3 2 3 4 The right answer for n=4 is k=3 3 3 1 2 3 3 1 2 4 2 3 4 Previous answer << 4 3 1 2 3 3 1 2 4 3 1 3 4 3 2 3 4 >> is wrong because the 1st colour is used 3 times. Because my proposed answer is k=3, so the answer in problemset is right. Authors did not use the 4th colour because they can make 3 flags with 3 colours. It is only their choice. Smilodon_am, MegaThanks You! ЗЫ: коварное условие :) PS: insidious conditions :) "he doesn't want any colour to occur in three or more flags" read whole problem ;) The sample output is wrong, it should be : 4 3 1 2 3 3 2 1 4 3 1 3 4 3 2 3 4 You are wrong! Color 3 is in 3 flags. Why aren't they are: 4 2 1 2 2 1 4 2 2 3 2 3 4 Read the task attentively. The 1st and 4th flag have no common color. Can't it be: 4 2 1 4 2 1 3 2 2 3 2 2 4 ??? Edited by author 14.03.2009 14:13 Sorry understood my mistake No, becouse any two flags must have one joint colour. So flags 1 4 and 2 3 are incorrect. Edited by author 14.03.2009 14:08 For Example: 3 2 1 2 3 1 3 4 3 2 3 4 Люди как я понял у нас в этой задаче надо найт и кол-во комбинаций?!! |
|
|