Hello Codeforces, I have a question which I am unable to solve, please help me:
There is 2d Matrix of size h*w representing the city. Each cell can be 0,1,2,3,4 0-> road 1->Tree 2->Garage 3-> warehouse 4-> Airport
There is a truck parked at the Garage, Truck’s task is to go to the warehouse (one or many at a time) , load the goods and unload the truck at the airport. There is no limit on the number of goods a truck can carry.
Also each warehouse has unlimited number of goods .
There is a cost associated with a truck. Cost is (Number of blocks it has moved * (1+Number of goods truck carries)) like To move one block cost is 1 on an empty truck in Cost is 2 if truck has 1 good 3 if the truck has 2 goods. ………. You have to tell how many maximum goods can be unloaded at airport using at max C cost
Constraints Number of test cases — 50 h,w belongs to (2,40) c belongs to (5,2000) There can be at max 13 warehouses Truck cannot pass a tree, if it is at any warehouse truck can or cannot load the goods, similarly if it's at an airport it's not necessary to unload the goods. But starting point is fixed is garage.
Any idea on how to solve it would be great
Binary search on the number of goods. In each iteration of binary search, you can check if an x value is possible by checking that C <= min(dist(garage, warehouse) + (1 + x) * dist(warehouse, airport)). You can keep all pairs of (dist(garage, warehouse), dist(warehouse, airport)) and compute in worst case (13 * 1600), or you can just BFS. Worst case number of operations is 13 * 1600 * log(2000) * 50.
what if the optimal path is like this garage — > warehouse 1 -> warehouse 2 -> airport? then in that case?
garage -> warehouse 2 -> airport would be more optimal in that case, since each warehouse has an unlimited number of goods. It's never optimal to visit more than one warehouse.