| ENG RUS | Timus Online Judge |
Discussion of Problem 1040. Airline CompanyMyrcella If you get WA #5 (and hints for the question // Problem 1040. Airline Company 13 Sep 2018 17:33 I think of "N<=50" as "N,M<=50". Actually M<=N*(N-1)/2. It's a stupid mistake but it took me so much time to check out TAT (btw, the point to solve the question is GCD(x,x+1)=1, it can be proved that the answer is always "YES". kiko A possible test data. [1] // Problem 1040. Airline Company 10 Feb 2011 20:05 4 4 1 2 2 3 3 1 1 4 One possible answer is: YES 1 2 3 4 dangminhhieu78 Re: A possible test data. // Problem 1040. Airline Company 22 May 2015 17:17 Thank you a lot, this problem took me so much time Vladislav The graph can be not connected ?! [1] // Problem 1040. Airline Company 4 Nov 2011 14:08 When I make my algo work for not connected graphs, i got AC. (I changed dfs(0) to for(int i=0;i<n;++i)if(!lev[i])dfs(i); ) Sandro (USU) Re: The graph can be not connected ?! // Problem 1040. Airline Company 5 Nov 2011 12:40 The graph is connected. Macarie No subject // Problem 1040. Airline Company 22 Jul 2011 22:35 This problem is from IMO 1991 (problem 1, day 2) http://www.artofproblemsolving.com/Wiki/index.php/1991_IMO_Problems/Problem_4 lshain ~.~! M >= 50 :0 // Problem 1040. Airline Company 14 Jun 2011 15:44 hoan connected or not? // Problem 1040. Airline Company 10 Oct 2010 00:22 i got AC but my code is correct when is graph is connect, who can solve this when the graph is arbitary? plz give me your code. (sorry for bad english) :D Phan Hoài Nam (HUFLIT) The trick is here : gcd ( x , x + 1 ) = 1 // Problem 1040. Airline Company 9 Oct 2010 00:04 This problem is so easy ^^! bobchennan Is 1,2,4,6,5,3 also right?????????? [2] // Problem 1040. Airline Company 3 May 2009 09:55 Who can tell me? I have WA1. Thanks a lot. Edited by author 03.05.2009 09:55 Edited by author 03.05.2009 09:56 Edited by moderator 13.05.2009 01:51 Kurpilyansky Eugene (USU) Re: Is 1,2,4,6,5,3 also right?????????? [1] // Problem 1040. Airline Company 3 May 2009 23:25 "If there are several flights that depart from one airport then the greatest common divisor of their flight numbers should be equal to 1." input 6 6 1 2 2 3 2 4 4 3 5 6 4 5 output 1 2 4 6 5 3 This output isn't correct because for second flight (2, 3) gcd is equal to 2 != 1. Edited by moderator 13.05.2009 01:52 MAK Re: Is 1,2,4,6,5,3 also right?????????? // Problem 1040. Airline Company 22 Jul 2010 09:52 O_o "If there are several FLIGHTS that depart from one AIRPORT then the greatest common divisor of their flight numbers should be equal to 1." Why did you calculate gcd for the second flight? Output is a numbers of flights, not numbers of flights. May be you should do this for the second airport. However gcd of the flight numbers of the second airport is gcd(1,2,4) = 1. P.S. I think output is not right because gcd of the flight numbers from the airport #3 is equal to 2. Edited by author 22.07.2010 10:00 Vladimir Yakovlev (USU) Problem 1140 "Airline company" has been rejudged (+) // Problem 1040. Airline Company 28 Dec 2008 02:34 Bad test #13 has been corrected, solutions that had troubles with this test have been rejudged. 23 authors have got AC. xdex is there good solution of the problem (not backtracking or heuristics)?(-) [2] // Problem 1040. Airline Company 8 Apr 2003 03:55 Denis Koshman Re: is there good solution of the problem (not backtracking or heuristics)?(-) [1] // Problem 1040. Airline Company 30 Jul 2008 15:55 Yes. Get a chain, paint it CUR...CUR+X. That's not everything, but a good start to get fair AC in 0.001 sec. Piratek-(akaDK) Re: is there good solution of the problem (not backtracking or heuristics)?(-) // Problem 1040. Airline Company 15 Sep 2008 19:46 I can find any polynomial algorithm but use some logics(AC). Can somebody tell normal algorithm. My mail piratic@mail.ru [FoH]^^richman^^ I think it is Hamilton way [1] // Problem 1040. Airline Company 24 May 2008 19:15 find the way from one to all airports and each airport can be passed one time Edited by author 24.05.2008 19:16 Vedernikoff Sergey Re: I think it is Hamilton way // Problem 1040. Airline Company 26 May 2008 19:55 No, just think a bit - and you'll find more beautiful solution... ahyangyi_newid We can construct the answer from the input in O(nm) time [8] // Problem 1040. Airline Company 23 Apr 2004 07:31 Sorry, my english is too poor to describe my algo. But here is a little tips: For any neighbor positive integers a & b: GCD(a,b)=1 I.E. GCD(1,2)=1 GCD(2,3)=1 GCD(3,4)=1 GCD(4,5)=1 GCD(5,6)=1 GCD(6,7)=1 GCD(7,8)=1 GCD(8,9)=1 GCD(9,10)=1 ...... Maigo Akisame (maigoakisame@yahoo.com.cn) Your algo won't work for disconnected graphs(+) [6] // Problem 1040. Airline Company 28 Oct 2004 15:22 See this: 6 6 1 2 2 3 3 1 4 5 5 6 6 4 The answer is NO currently unnamed... Re: Your algo won't work for disconnected graphs(+) [3] // Problem 1040. Airline Company 25 Oct 2005 17:01 But there are no data like this... I got AC although my program always prints "YES"... wefgef No subject [2] // Problem 1040. Airline Company 2 Jun 2006 22:16 is there an algo wich works in O(n+m) for disconnected graphs too? Burunduk1 Re: No subject [1] // Problem 1040. Airline Company 2 Jun 2006 22:24 I think no. For exmaple, sometimes answer is NO and strategy 1,2,3,4... doesn't work. When statements were incorrect (it was not said that graph is connected) I and some my friends tried to solve it... but we couldn't find even polynomial solution. So I think no. GaLL [Tyumen SU] Re: No subject // Problem 1040. Airline Company 3 Jun 2006 00:27 If graph is connected ( current statement ), problem can be solved by dividing graph into chains ( like in #1441 ), chains are: k,k+1,...,l . This solution is absolutely correct. davidsun Re: Your algo won't work for disconnected graphs(+) [1] // Problem 1040. Airline Company 12 Aug 2006 07:43 No, I think the answer is 3 4 1 2 6 5 jimdtc Re: Your algo won't work for disconnected graphs(+) // Problem 1040. Airline Company 3 Feb 2008 18:30 Sorry,I think your answer is wrong. See the node 5:the number of one egde is 2,another is 6,gcd(2,6)=2<>1 2-8 Re: We can construct the answer from the input in O(nm) time // Problem 1040. Airline Company 2 Feb 2005 17:26 I think we can get the answer in O(n+m)... Just use the method you mentioned... Each node has two arcs which numbered x and x+1... Nguyen Viet Bang Wrong Sample input and Output ? Please help me . [2] // Problem 1040. Airline Company 19 Jun 2002 15:03 Please consider the Sample input and output : The 1st flight ( connects 1 and 2 ) and the 2-nd flight ( 2-3) are flights that depart from one airport ( airport 2 ) ( The flight are 2 directions flight ) . But the sample output indicates that their numbers are 4 and 2 , so their greatest common divisor can't be 1 as the problem description ! I don't know if I wrong . I got WA too . Please explain for me Thanks a lot ! . Vlad Veselov Re: Wrong Sample input and Output ? Please help me . [1] // Problem 1040. Airline Company 16 Apr 2004 21:33 You must calculate greatest common divisor of all flights, that departs from one airport. For airport 2 this numbers are 2,3,4 and there greatest common divisor is 1. reason supreme Re: Wrong Sample input and Output ? Please help me . // Problem 1040. Airline Company 1 Feb 2008 05:07 thank you very much! Dmitry "Logam" Kobelev HOW COME? [1] // Problem 1040. Airline Company 3 Jan 2008 22:31 Why cant we just output first M prime numbers??? WA1 #include<stdio.h> #include<math.h> void main() {int n,h; bool f; scanf("%i%i",&n,&n); printf("YES\n1"); for(int i=2,j=1;j<n;i++) {h=(int)sqrt((float)i); f=0; for(int k=2;k<=h;k++) if((i%k)==0) {f=1;break;} if(!f){printf(" %i",i);j++;} } } elmariachi1414 (TNU) Re: HOW COME? // Problem 1040. Airline Company 14 Jan 2008 15:18 Because numbers must be [1..M] Oracle WHY WA#1???(+) // Problem 1040. Airline Company 28 Sep 2007 01:10 AC!!!!! Edited by author 06.08.2008 18:53 Sandro (USU) Problem 1140 "Airline company" has been rejudged (+) [2] // Problem 1040. Airline Company 25 Oct 2006 12:00 Validator was updated and some new tests were added. Many authors got WA and TL because their heuristics failed new tests. Try to find new tricky tests if your heuristics still has AC. Kit (Vologda SPU) Re: Problem 1140 "Airline company" has been rejudged (+) [1] // Problem 1040. Airline Company 26 Oct 2006 16:52 Does your solution can pass ALL kinds of tests under this constraints? Vladimir Yakovlev (USU) Yes (-) // Problem 1040. Airline Company 26 Oct 2006 18:55 davidsun What's the answer of this input? [1] // Problem 1040. Airline Company 12 Aug 2006 07:38 6 5 1 2 2 4 4 3 5 6 3 2 Is the answer YES 4 1 2 5 3 right? davidsun Re: What's the answer of this input? // Problem 1040. Airline Company 13 Aug 2006 14:12 I've got AC. The problem is very strange. I initial the numbers(give every edge a number), and got AC at last. It took me a long time! :) Test 6 is wrong! [4] // Problem 1040. Airline Company 18 Apr 2006 01:39 The graph is not connected. Walrus Yes, test 6 is incorrect! [3] // Problem 1040. Airline Company 19 Apr 2006 22:14 GaLL [Tyumen SU] Re: Yes, test 6 is incorrect! [2] // Problem 1040. Airline Company 19 Apr 2006 22:34 Incorrect.Sine dubitatibus. Vladimir Yakovlev (USU) yes, test is incorrect. it will be corrected asap [1] // Problem 1040. Airline Company 20 Apr 2006 13:19 Vladimir Yakovlev (USU) Fixed (+) // Problem 1040. Airline Company 26 May 2006 00:33 some submissions since 20-Feb-2006 have been rejudged and got AC Edited by author 26.05.2006 01:31 Christos Mantoulidis Test 6 // Problem 1040. Airline Company 19 Mar 2006 15:50 Can someone post test 6? Thanks Burunduk1 2Admins (!) tests are incorrect [4] // Problem 1040. Airline Company 24 Dec 2005 10:58 Please, explain me why answer is always YES? It's right only for connected graphs! For example: 6 6 1 2 2 3 3 1 4 5 5 6 6 4 Answer is NO. Yaroslavtsev Grigory (SpbSPU) Re: 2Admins (!) tests are incorrect [1] // Problem 1040. Airline Company 24 Dec 2005 22:35 Oh, what a trick! I was very much confused seeing > 400 people who solved this problem. I'm really annoyed beacuse in this case the problem is O(n + m) using a simple idea gcd(n,n + 1) = 1. But if the graph can be disconnected everything is much worse!!! KingPin Re: 2Admins (!) tests are incorrect // Problem 1040. Airline Company 25 Dec 2005 03:43 Graph can be disonnected. Sample is. But testset is weak... Why am I not surprised :) My always "YES" program got AC. Burunduk1 2Admins: Please, fix this problem! [1] // Problem 1040. Airline Company 28 Dec 2005 20:07 With such tests the problem is much easier than it is. Please, change tests or statements! Vladimir Yakovlev (USU) Fixed (+) // Problem 1040. Airline Company 19 Feb 2006 23:41 Graph is always connected now. Statements and tests are updated. So, the solution always exists.
|