Prima tură are N căruțe, deci o secvență e transportabilă dacă suma ei se împarte la N; cea mai lungă se află din resturile prefixelor mod N. Transportul complet se face în runde: cu M grămezi rămase, transportăm o submulțime cu suma divizibilă cu M (garantat de principiul cutiei).
Vezi enunțul oficialÎncearcă întâi singur! Indiciile elimină din satisfacția rezolvării.
Cheia ambelor cerințe e aceeași: dacă ai căruțe egale, poți încărca un grup de grămezi doar dacă suma lor se împarte exact la (altfel n-ai cum să dai fiecărei căruțe aceeași cantitate). Întrebarea „suma se împarte la ?” se traduce instant în limbajul resturilor: lucrăm cu sumele de prefix și ne uităm doar la restul lor împărțit la .
Conectează-te ca să marchezi problemele rezolvate.