|
|
| Show all threads Hide all threads Show all messages Hide all messages | | WA 13 | SharpBlade | 1779. The Great Team | 28 Nov 2023 18:09 | 2 | WA 13 SharpBlade 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();
}
} Repalce the conditions i != j with i < j because you print some edges twice.
Sorry for my bad English | | Easy problem. | Gleb_Kazantaev(NNSTU) | 1779. The Great Team | 18 Nov 2014 13:53 | 1 | 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 | | Who can give me some hints? | adrian | 1779. The Great Team | 23 Oct 2011 01:21 | 4 | I thought it for a long time,but I still do not know how to do it. Hint vgu 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. 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 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 | | Вопрос по примеру | LLd_team | 1779. The Great Team | 13 Oct 2011 22:41 | 8 | Разве для 4 студентов будет всего 2 пары?
А чем не устраивает вариант:
3
1 2
2 3
1 4
Тогда 1 и 2 студенты имеют по 2 друга, а 3 и 4 по 1, что в свою очередь подходит под "крах критерия успеха". All three members of the team should have the same number of friends... The problem can has multiple correct answers.
Edited by author 09.10.2010 14:50 Iosif inf-10 : Sən harda oxuyursan? Достаточно и любой одной пары друзей - у них будет по 1, у других по 0. я так понял нужно построить такой граф чтобы любые три вершины имели разную степень.
а в условии сказано что решение можно вывести любое. LLd_team, такой вариант вполне пройдёт. Для удобства, можно составить на бумажке матрицу вида:
1 2 3 4
2 2 1 1
надеюсь, суть матрицы понятна ;)
Собственно программно и нужно постоянно проверять количество людей с одинаковым количеством друзей и "не давать" этому количеству превышать 2 (эмпирически выяснили, что -1 в принципе может и никогда не вернуться). У меня всегда есть ответ))
Пусть кол-во друзей четно. Пусть мы уже добавили 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. | | [DELETED] | Leonid (SLenik) Andrievskiy | 1779. The Great Team | 17 Aug 2011 02:12 | 1 | [DELETED] Leonid (SLenik) Andrievskiy 17 Aug 2011 02:12
Edited by author 17.08.2011 03:47 | | Why answer for N=5??? | VsR | 1779. The Great Team | 14 Oct 2010 02:21 | 4 | thank you
but my program solution for N=5 (Accepted)
6
1 2
1 3
2 3
2 4
3 4
3 5 Сорри англ хромает, УСЛОВИЕ ЗАДАЧИ нормальные составляйте а не байку из склепа в которой ничего не понятно! | | for one who has wa9 | Ibragim Atadjanov (Tashkent U of IT) | 1779. The Great Team | 14 Oct 2010 01:10 | 1 | 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 | | Is the answer right?? | meparter1 | 1779. The Great Team | 9 Oct 2010 16:19 | 1 | 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.
|
|
|
|
