← CSES Better

1 Road Trips and Museums - INOI 2018

INOI · 2018 · Indian National Olympiad in Informatics · ROADTRIP

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

graphs · connected-components · game · greedy

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

alternating component picks

Alternate between largest and smallest unvisited components

A road trip visits an entire connected component. Lavanya chooses a component with the most museums; Nikhil chooses one with the fewest. They alternate for K months.

component totals: c1 <= c2 <= ... <= cNLavanya: take largestNikhil: take smallestalternate for K trips
  1. 1

    Build component totals

    Find connected road components and sum the museums in each component.
  2. 2

    Alternate choices

    Lavanya picks the unvisited component with the most museums; Nikhil picks the unvisited component with the fewest.
  3. 3

    Complete K trips

    Add the selected totals in turn. If fewer than K components remain, output -1.
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.