| ENG RUS | Timus Online Judge |
Discussion of Problem 1480. CouponsAram Shatakhtsyan How to solve this problem? [2] // Problem 1480. Coupons 18 Apr 2007 15:11 Someone who solved this problem, give some ideas, please. Denis Koshman Re: How to solve this problem? [1] // Problem 1480. Coupons 24 Jul 2008 14:51 The answer is n^2 + floor(n/2) + 1. Place n^2 in top-left corner and proceed row-by-row, column-by-column. For every cell choose maximal unused value, such that its sum with left and upper numbers is <= that minimal sum. I have no idea why that works. The formula above was found empirically - these are minimal values when this greedy algorithm converges. Edited by author 24.07.2008 15:00 Alexander Samal Re: How to solve this problem? // Problem 1480. Coupons 5 Aug 2010 02:32 Real cheat! With this formula the problem is VERY easy! IMHO, without it - it would take much more time and efforts to get AC. ilyamit Idea [5] // Problem 1480. Coupons 5 Nov 2007 15:38 What is idea for this priblem? I fill matrix for chess: n = 4 0101 1010 0101 1010 0 - smoll number 1 - big number Why my solve is wrong?((( I got WA4. Loky_Yuri [USTU Frogs] Re: Idea [4] // Problem 1480. Coupons 6 Nov 2007 10:54 During the contest our team didn't solve this problem because of the same logic. Now I understand that the same idea but with putting the biggest number in the conner is so simple... AlexF [USTU Frogs] Re: Idea // Problem 1480. Coupons 6 Nov 2007 10:59 Yes, it was really sad( ilyamit Re: Idea [2] // Problem 1480. Coupons 18 Nov 2007 20:51 Thanks! I got AC. Is true idea (for 4): 1 0 1 0 0 1 0 1 1 0 1 0 0 1 0 1 jagatsastry Re: Idea [1] // Problem 1480. Coupons 27 Nov 2007 15:12 Edited by author 27.11.2007 15:37 Edited by author 27.11.2007 15:38 Roman Peshkurov (It-Team) Re: Idea // Problem 1480. Coupons 18 Nov 2009 16:02 i am using BFS with queue Tkach Andriy I have WA#2. Please, help me. [1] // Problem 1480. Coupons 23 Oct 2006 18:18 I think that matrix have some stucture but I don't now this. PSV Re: I have WA#2. Please, help me. // Problem 1480. Coupons 18 Mar 2007 22:37 It is so easy try only with yourself it's always better :) SpaceFlyer How to prove? // Problem 1480. Coupons 11 Oct 2006 06:10
|