Why at the input sample the answer for 4 100 7 is no problem link http://codeforces.com/contest/94/problem/D

# | User | Rating |
---|---|---|

1 | Benq | 3797 |

2 | tourist | 3723 |

3 | Radewoosh | 3720 |

4 | ecnerwala | 3579 |

5 | ksun48 | 3463 |

6 | Um_nik | 3457 |

7 | maroonrk | 3446 |

8 | jiangly | 3432 |

9 | Petr | 3370 |

10 | scott_wu | 3350 |

# | User | Contrib. |
---|---|---|

1 | 1-gon | 208 |

2 | awoo | 184 |

2 | rng_58 | 184 |

4 | Errichto | 182 |

5 | SecondThread | 177 |

6 | maroonrk | 176 |

6 | Radewoosh | 176 |

6 | -is-this-fft- | 176 |

9 | Um_nik | 173 |

10 | antontrygubO_o | 169 |

Why at the input sample the answer for 4 100 7 is no problem link http://codeforces.com/contest/94/problem/D

↑

↓

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/22/2021 08:43:49 (h1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Similar to the idea mentioned in the tutorial, the

primal problemto fillmcups evenly usingnbottles, where each bottle containswunits, and each bottle is to be poured in at most2different cups, is equivalent to the equivalentdual problemwhen each bottle contains exactlymunits, and all the poured amounts are integer numbers. In the dual problem, the capacity of each cup is exactlynunits. The amounts of the primal problem are then simply computed as the amounts computed in the dual problem times the scale factorw/m.In test 1 [

n=2,w=500,m=3], the scale factor is166.666667, and the given solution is equivalent to the following solution of the dual problem.1 2

2 2

2 1 1 1

In test 2 [

n=4,w=100,m=5], the scale factor is20, and the given solution is equivalent to the following solution of the dual problem.3 1 4 3

1 4

4 2 2 2

3 4

2 3 1 1

In test 3 [

n=4,w=100,m=7], it is impossible in the dual problem to pour any bottle in one cup only, since the bottle sizemis larger than the cup capacityn. All the 2-cups integer partitions 1+6, 2+5, and 3+4 of one bottle are also impossible. In the first two partitions, the second part is larger than the cup capacity. In the third partition, pouring the first part in some cup would leave a 1-unit space in such cup. This space cannot be filled from another bottle, as it would leave 6 units in such bottle that cannot be poured in one cup only.In test 4 [

n=5,w=500,m=2], the scale factor is250, and the given solution is equivalent to the following solution of the dual problem.4 1 5 2 2 2

3 2 1 2 4 1

Finally, it should be noted that the dual problem is equivalent to finding a matrix

Awithnrows that represent the bottles,mcolumns that represent the cups, and positive integer elements that represent the amount poured from bottleiin cupj. The following are the constraints that the sought matrixAsatisfies:The sum of all elements in each row is exactly

m.The sum of all elements in each column is exactly

n.Each row contains either one or two non-zero elements only.

Hope that this explanation is sound and helpful enough.

thanks alot

With pleasure.

The following is a C++17 implementation of the greedy algorithm based on the integer dual problem. 36085263