← CSES Better

Vegetables

ZCO · 2024 · Zonal Computing Olympiad · Problem 1

Open official problem ↗
Ask AI

Open a hint-first prompt in a new AI chat. Grok may ask you to confirm before sending.

Open Claude Desktop

optimization · greedy · queries

The organizer’s problem statement is available at the official source link.

upgrade cost

Spend upgrades where water use drops most

Vegetable i needs Ai units at Bi water per unit; an upgrade lowers either factor by one, and each query limits upgrades.

State table
Plot iWaterOne-step saving
iA_i * B_ireduce A_i -> save B_i
iA_i * B_ireduce B_i -> save A_i
  1. 1

    Compare marginal savings

    Start with total water equal to the sum of Ai×Bi.
  2. 2

    Spend within budget

    Compare each possible one-step reduction, whose benefit depends on the current other factor.
  3. 3

    Minimize water use

    For every budget X, minimize total water using at most X upgrades.
Tools
1
2
3
4
5
6
7
8
9
10
11
12
Draft saved locally
|12 lines, 156 chars

Run output

Run your code to see output.