| Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения |
| hint | So Sui Ming | 1692. Флаги провинций | 23 фев 2024 08:03 | 1 |
hint So Sui Ming 23 фев 2024 08:03 Problem can be reduced to edges in complete graph:
Given no. of edges, what is the max no. of vertices in a complete graph? |
| Some sample answers will help you find the algorithm for this problem :) | Phan Hoai Nam | 1692. Флаги провинций | 4 фев 2014 18:00 | 5 |
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 |
| "(int)x"(C++) will round x to integer on the judge instead of truncate.... | XieZheng | 1692. Флаги провинций | 19 авг 2011 21:10 | 2 |
sorry for my poor English..
I've got WA many times because of this... this is untrue, it will truncate |
| Is the order of colors important?? | Kinshul Verma | 1692. Флаги провинций | 17 мар 2009 11:30 | 2 |
Is the order in which the colors of flags are specified, or the order in which flags are printed important? |
| n = 4, another solution | monkeyvu | 1692. Флаги провинций | 14 мар 2009 17:43 | 4 |
3 1 2 4
3 1 3 4
2 2 3
Is it wrong? So which one we will choose to display? |
| example is wrong ??? n = 4 => k = 4 | Phan Hoai Nam | 1692. Флаги провинций | 14 мар 2009 16:13 | 8 |
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 ;) |
| sample output wrong | Rahul | 1692. Флаги провинций | 14 мар 2009 14:48 | 8 |
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. |
| Can a flag has only one color? | acmore | 1692. Флаги провинций | 14 мар 2009 14:17 | 2 |
Edited by author 14.03.2009 14:08 |
| Is it same that the number of colour used? | Poorman | 1692. Флаги провинций | 14 мар 2009 14:05 | 1 |
For Example:
3
2 1 2
3 1 3 4
3 2 3 4 |
| HELP | Rockman | 1692. Флаги провинций | 14 мар 2009 13:37 | 1 |
HELP Rockman 14 мар 2009 13:37 Люди как я понял у нас в этой задаче надо найт и кол-во комбинаций?!! |
