Problem z zadaniem z olimpiady informatycznej (brak pomysłu)

Question

Dzień dobry,

rozwiązuje sobie zadania z roznych olimpiad informatycznych i natknąłem się na zadanie, którego nie potrafię rozwiązać. Męczyłem się nad nim dosyć długo i nic mi nie przychodzi do głowy. Jeśli ktoś miałby jakiś pomysł to będę bardzo wdzięczny. Zadanie podsyłam tutaj: http://www94.zippyshare.com/v/nknBg25W/file.html

Pozdrawiam serdecznie

Comments

nie dawaj takich linkow, wklej tresc zadania tutaj, albo na jakis serwis gdzie po kliknieciu mozna je przeczytac a nie sciagac cos

---

Wejście i wyjście mi się nie zmieściły, więc wyślę w kolejnej wiadomości

---

A oto wejście i wyjście:

Answer 1

Tu jest moim zdaniem błąd w przykładnie, bo jak niby z 21 ma ułożyć? z treści zadania jasno wynika, że liczba użytych patyczków musi być parzysta.

Anyway, zauważ, że dla n>=12 zachodzi zasada, że ilość patyczków= suma kolejnych potęg liczby 2. Dla drugiej śnieżynki jest to 2 do 2+2do3, dla kolejnej dodajesz 2do4, itd itd. Powtarzaj pętlę tak długo, aż n<= licznikowi, a ten powiększaj w pętli o X potęgę liczby 2 inkrementując X co obieg pętli. Jeśli po wykonaniu pętli licznik==n to mamy liczbę odpowiednią do zbudowania śnieżynek z dokładnie n patyczkow. Ilosc rodzajow + X-1.

Moim zdaniem zadanie jest źle ułożone. Z każdej nieparzystej liczby zostaną patyki.

Comments

w zadaniu jest napisane, że śnieżkę zaczyna układać z dowolnej liczby patyczków (minimum to 2, zatem podstawa może wynosić i 4,8,12 itd.). potem już monotonnie tą podstawę się mnoży przez kolejnę potęge dwójki i dodaje do siebie (x*2^0 + x*2^1 + x*2^2 .... x - podstawa) tak długo, aż ta suma nie jest większa od liczby patyczków, a jeśli w którymś momencie suma jest równa liczbie patyczków, to mamy już właśnie jedną całą śnieżkę. 

mam nawet gotowy kod, który prawidłowo mi rozwiązał to zadanie.

#include<iostream>

using namespace std;

bool SNIEZKA(int maks,int podstawa, int mnoznik)
{
    if (podstawa * 2>maks)
    {
        return false;
    }
    else
    {
        maks -= (podstawa * mnoznik);
        if (maks == 0)
        {
            return true;
        }
        else
        {
            SNIEZKA(maks,podstawa,mnoznik*2);
        }
    }
}
int main ()
{
   int test;
   cin>>test;
   for (int i = 0;i < test;i++)
   {
       int patyczki;
       cin >> patyczki;
       int maks_patyczki = patyczki;
       patyczki/=3;
       int dalej;
       if (maks_patyczki%2==1)
           dalej = 3;
       else
           dalej = 2;

       int wynik = 0;
       for (int j = dalej;j<=patyczki;j+=2)
       {
           bool opcja = SNIEZKA(maks_patyczki,j,1);
           if (opcja == true)
           {
               wynik++;
           }
       }
       cout << wynik <<endl;
   }
}

być może nie koniecznie program się zmieści w limicie pamięci, ale jak pisałem nie zważałem na to. 

---

Tak, ale zawsze muszą być to liczby parzyste, natomiast w przykładach na wejsciu jest liczba 21 a na wyjsciu 2, co jest bledem, bo jest w zadaniu zaznaczone, że nie może być niepełna śnieżynka. z 7 ułożysz jedną śnieżynkę (6) i zostanie 1

---

da się ułożyć dwie pełne różne śnieżki z 21 patyczków. poza tym w zadaniu nie ma napisane że liczba patyczków ma być parzysta