POSAO - Jobs

no tags 

Little Domagoj has hands full of work. His jobs are organized in NxN matrix such that each cell represents one job. He can start doing job at cell (x,y) if and only if jobs at cells (x,y-1) and (x-1,y) are done(if they exist). 

On the picture required jobs are shown for gray cells. 

Domagoj has K computers which he will use for doing jobs. One computer is able to do at most one job in one second. Also, all computers need not to be used all the time. Help Domagoj and organize order in which computers will do jobs in least possible time.


In the first line there are two integers N and K (1 ≤ N≤ 109)


Print least possible time in which all jobs can be done.


3 2
5 1
4 4

hide comments
more_practice: 2016-06-27 17:32:21

worst wording

Archangel: 2014-10-23 10:28:14

can someone explain the problem to me, Its said that one computer can perform at most one job in one second then obviously for nxn we would need nxn seconds? please help me on this.

demon: 2013-12-04 09:12:06

getting internal error. Something wrong with the server?


Last edit: 2013-12-04 09:14:30
Unknown: 2013-08-20 08:58:20

Please provide some tricky test cases..

P_Quantum: 2013-08-18 12:01:01

Nice One... :) simple logic .. :P

devil: 2013-06-11 10:13:07

donot forget to take the case when k > n

:C++:: 2012-12-18 13:58:55

Why i m getting WA after 10 test cases
pls help.. my submission id is 8293151

a b : 2012-10-04 07:43:02

any tricky case got wrng ans after 10th judge.........

Last edit: 2012-10-04 07:43:26
DEVANSH PARASHAR: 2012-10-01 20:48:18

@abdul baset al-joudy your explanation seems to be contradictory it is surely incorrect plz check the first case 3 2 is 6

Abdul Baset Al-Joudy: 2012-07-28 13:16:35

@David Moran You can't fill the first row first, because for instance the job at 1, 2 needs the job at 1, 1 to be done before it, not simultaneously.

Added by:Ivan Katanic
Time limit:0.187s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Croatian Junior Olympiad in Informatics, Matija Osrecki