| ENG RUS | Timus Online Judge |
Discussion of Problem 1779. The Great TeamPage 1 Gleb_Kazantaev(NNSTU) Easy problem. // Problem 1779. The Great Team 18 Nov 2014 13:53 Some hint: For n = 4 1 : (1,2), (1,3), (1,4); 2 : (2,1), (2,3); 3 : (3,1), (3,2); 4 : (4,1); 1st have 3 friends, 2nd have 2 friends, 3d have 2 friends, 4fth have 1 friend, so ans is 4 1 2 1 3 1 4 2 3 SharpBlade WA 13 [1] // Problem 1779. The Great Team 2 Jun 2012 23:06 Can anyone say, what is wrong in my solution? public class T1779 { public static void main(String[] args) throws IOException { BufferedReader in=new BufferedReader(new InputStreamReader(System.in)); PrintWriter out=new PrintWriter(System.out); int n=Integer.parseInt(in.readLine()); int sum=0; for(int i=0; i<n/2; i++){ for(int j=n-i-1; j<n; j++){ if(i!=j){ out.println((i+1)+" "+(j+1)); sum++; } } } System.out.println(sum); out.close(); } } Anti Re: WA 13 // Problem 1779. The Great Team 28 Nov 2023 18:09 Repalce the conditions i != j with i < j because you print some edges twice. Sorry for my bad English Leonid (SLenik) Andrievskiy [DELETED] // Problem 1779. The Great Team 17 Aug 2011 02:12 Edited by author 17.08.2011 03:47 Ibragim Atadjanov (Tashkent U of IT) for one who has wa9 // Problem 1779. The Great Team 14 Oct 2010 01:10 I had wa9 many times. Then I decided to find this test and found, fixed my bug and ac. test 9 n = 18 good luck adrian Who can give me some hints? [3] // Problem 1779. The Great Team 9 Oct 2010 18:38 I thought it for a long time,but I still do not know how to do it. vgu Hint [2] // Problem 1779. The Great Team 9 Oct 2010 20:36 1) If we know the degree of the vertices, we can determine: is such graph exist. 2) Write a full search. You will quickly find an answer. You can sent this code and get AC or look at the answer and found a pattern. svr Re: Hint [1] // Problem 1779. The Great Team 9 Oct 2010 22:11 1)Havel-Hakimi algorithm 2) Hypothesis(my): sequence n/2 n/2 ... 3 3 2 2 1 1 0 0 realizable for each n P.S. In timus there is a problem about full search: monkey aplly full search on keyboard. When it create theorem. Edited by author 09.10.2010 22:30 luckysundog Re: Hint // Problem 1779. The Great Team 23 Oct 2011 01:21 svr, your hypothesis is true. It's obvious if we draw the adjacency matrix of these graphs (for even N): N = 4: 0 0 0 1 0 0 1 1 0 1 0 0 1 1 0 0 N = 6: 0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 1 1 1 0 0 1 0 0 0 0 1 1 0 0 0 1 1 1 0 0 0 N = 8: 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 1 1 1 0 0 0 0 1 1 1 1 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 meparter1 Is the answer right?? // Problem 1779. The Great Team 9 Oct 2010 16:19 Sample input 4 output 2 1 3 3 4 the three members is 1 3 4. but the 1st student has one friends and the 3rd student has two friends. VsR Why answer for N=5??? [3] // Problem 1779. The Great Team 9 Oct 2010 15:43 Iosif inf-10 Re: Why answer for N=5??? [2] // Problem 1779. The Great Team 10 Oct 2010 18:41 for N=5 2 1 2 1 3 VsR Re: Why answer for N=5??? [1] // Problem 1779. The Great Team 13 Oct 2010 21:40 thank you but my program solution for N=5 (Accepted) 6 1 2 1 3 2 3 2 4 3 4 3 5 VsR Re: Why answer for N=5??? // Problem 1779. The Great Team 14 Oct 2010 02:21 Сорри англ хромает, УСЛОВИЕ ЗАДАЧИ нормальные составляйте а не байку из склепа в которой ничего не понятно! LLd_team Вопрос по примеру [7] // Problem 1779. The Great Team 9 Oct 2010 14:16 Разве для 4 студентов будет всего 2 пары? А чем не устраивает вариант: 3 1 2 2 3 1 4 Тогда 1 и 2 студенты имеют по 2 друга, а 3 и 4 по 1, что в свою очередь подходит под "крах критерия успеха". Tural Vugar Gulmammadov Re: Вопрос по примеру // Problem 1779. The Great Team 9 Oct 2010 14:41 All three members of the team should have the same number of friends... Iosif inf-10 Re: Вопрос по примеру [1] // Problem 1779. The Great Team 9 Oct 2010 14:48 The problem can has multiple correct answers. Edited by author 09.10.2010 14:50 Tural Vugar Gulmammadov Re: Вопрос по примеру // Problem 1779. The Great Team 9 Oct 2010 15:10 Iosif inf-10 : Sən harda oxuyursan? Anton Chupin Re: Вопрос по примеру [1] // Problem 1779. The Great Team 9 Oct 2010 15:20 Достаточно и любой одной пары друзей - у них будет по 1, у других по 0. rArow Re: Вопрос по примеру // Problem 1779. The Great Team 9 Oct 2010 16:41 я так понял нужно построить такой граф чтобы любые три вершины имели разную степень. а в условии сказано что решение можно вывести любое. Anton Papin Re: Вопрос по примеру [1] // Problem 1779. The Great Team 14 Oct 2010 02:33 LLd_team, такой вариант вполне пройдёт. Для удобства, можно составить на бумажке матрицу вида: 1 2 3 4 2 2 1 1 надеюсь, суть матрицы понятна ;) Собственно программно и нужно постоянно проверять количество людей с одинаковым количеством друзей и "не давать" этому количеству превышать 2 (эмпирически выяснили, что -1 в принципе может и никогда не вернуться). ValenKof Re: Вопрос по примеру // Problem 1779. The Great Team 13 Oct 2011 22:41 У меня всегда есть ответ)) Пусть кол-во друзей четно. Пусть мы уже добавили 2k друзей и их валентности 112233...kk. Давайте соединять 2 новые вершины с уже добавленными, начиная с тех, у кого большая валентность. Получим у новых вершин валентность 11, а у старых 1122..(k-1)(k-1)(k+1)(k+1). Продолжаем процесс пока не получим у новых mm, а у старых 112233...(m-1)(m-1)(m+1)(m+1)..(k+1)(k+1). Если получили, что на каком-то шаге у новых mm, а у старых 1122..(m)(m)(m+2)(m+2)..(k+1)(k+1), то соединяем новые между собой. Если n нечетно, последнюю вершину оставляем одной. Кол-во дуг в графе (n/2) * ((n/2) + 1) / 2. Pages: 1
|