Wielka Przesmycka Reloaded 2011 - omówienie zadań

22.11.2011

B Nobel

W tym zadaniu jesteśmy proszeni o przedstawienie danego $ s $ jako sumy k {\bf różnych} liczb naturalnych z przedziału $ [1,n] $. Zacznijmy od dwóch prostych spostrzeżeń:

  1. najmniejszą liczbą, którą można w ten sposób przedstawić, na pewno jest $ 1+2+\ldots+k=\frac{k(k+1)}{2} $,
  2. największą liczbą, którą można w ten sposób przedstawić, na pewno jest $ n-k+1+n-k+2+\ldots+n=\frac{k(2n-k+1)}{2} $.

Okazuje się, że wszystkie liczby pomiędzy $ \frac{k(k+1)}{2} $ a $ \frac{k(2n-k+1)}{2} $ da się przedstawić jako sumę $ k $ różnych liczb z przedziału $ [1,n] $. Aby rozwiązać zadanie w wersji basic wystarczyło tylko uwierzyć w prawdziwość tego stwierdzenia. Ale oczywiście lepiej było od razu je udowodnić, tym bardziej, że jest to dość łatwe: zakładając, że umiemy w ten sposób przedstawić $ s>\frac{k(k+1)}{2} $, zawsze możemy zmniejszyć jeden z elementów tej reprezentacji aby uzyskać rozkład $ s-1 $. Równie łatwo znaleźć rozkład danego $ s $: jeśli $ s\leq\frac{2(n-1)-k+1}{2} $ zmniejszamy $ n $ o jeden, a w przeciwnym wypadku bierzemy $ n $, zmniejszamy $ s $ o $ n $, a $ n $ o jeden.

Uważny Czytelnik może dostrzec w (odpowiednio mocno powiększonym, w zależności od wady wzroku) logo zawodów kod rozwiązania do wersji basic.

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com