C1. Джуджета в гората

В една гора, разделена на N области, живеят голям брой джуджета (но не повече от 1 милион), като всяко от тях обитава една определена област. Джуджетата преминават в друга област само когато това е наложително.

Тъй като често възникват опасности, джуджетата предварително се подготвят за посрещането им. Например, те искат да знаят какъв максимален брой джуджета могат да се съберат в една област, когато това е необходимо.

Известно е, че за придвижване на едно джудже от една област в нейна съседна, е необходима една единица време. Ако в една област има повече от едно джудже, те могат да се придвижват едновременно, т.е. за тяхното придвижване е необходима една единица време.

Напишете програма GNOMES.EXE, с помощта на която джуджетата ще направят необходимите изчисления и ще определят максималния брой джуджета, които могат да се съберат в област с номер К за Т единици време.

Входните данни съдържат описание на гората и разположението на джуджетата в нея. На първия ред е разположено едно цяло число N (5 <= N <= 200) – брой на областите в гората. Следват N реда, като във всеки от тях се задават по няколко цели числа. Първото число в ред i съответства на броя на джуджетата в i-тата област, второто число указва броя на съседните области, а следващите числа са номерата на тези области. Ако е указано, че област с номер i е съседна на област с номер j, не е необходимо да се указва, че област j е съседна на област с номер i, но е допустимо. Последният ред съдържа числата К и Т.

Изходът съдържа едно цяло число – максималният брой джуджета, които могат да достигнат до област К за след най-много Т единици време.

Пример:

Вход:

5

10 2 2 3

2 0

15 2 4 1

7 2 5 3

1 1 4

4 2

Изход:

33

C2. На две

Двама души започват игра с N цели клечки по следните правила:

1. Играчите се редуват на всеки ход;
2. Един ход се състои в следното: играчът, чийто ред е, или разчупва някоя цяла клечка на две части, или взема два компактни елемента;
3. Печели този, който направи последен ход.

С това всичко е казано, но ще обърнем внимание на следните подробности:

- играчът на ход прави само едно от двете действия – или взема, или чупи (ако има какво);

- никое парче не може повече да се чупи – тази операция е допустима само върху цяла клечка;

- парчетата и целите клечки са наречени с общото име “компактни елементи” при вземане.

Ако, например, има четири клечки, първият играч може да направи само едно от следните действия:

- да вземе две клечки: остават два компактни елемента и всеки от тях може да се чупи на следващ ход;

- да счупи една клечка на две: стават пет компактни елемента, три от които (целите клечки) още могат да се чупят;

Ако преди хода Ви има останала само една част от клечка, Вие вече сте загубили, поради невъзможност да направите ход: частта не може повече да се чупи, а един компактен елемент не може да се взема.

Напишете програма TWO.EXE, която определя дали първият играч може да спечели при зададено начално количество клечки, колкото и добре да играе вторият (казваме още “първият играч има печеливша стратегия”). Освен това определете с какъв първи ход може да стане това. Ако има повече от една възможност, изберете коя да е от тях.

От стандартното входно устройство коректно се въвежда един ред с естественото число N<=500.

Изведете на стандартното изходно устройство един ред с:

- числото 0, ако първият играч не може да спечели;

- числото 2, ако печелившият първи ход е “вземане на два компактни елемента”;

- числото -2, ако печелившият първи ход е “чупене на цяла клечка на две”.

-

Пример:

Вход:

4

Изход:

-2

C3. Редица

При зададени цели, положителни числа A, B и C да разгледаме многочлена Ax + By + Cz. С помощта на този многочлен се определя редицата P₁, P₂, P₃,… P_N, …. като се спазват следните правила:

1) За всяко i P_i = Ax + By + Cz, където x, y и z са конкретни, цели, неотрицателни числа и x + y + z > 0;

2) Всяка стойност, която може да бъде получена чрез заместване на x, y и z в многочлена Аx + By + Cz с конкретни цели, положителни числа, се среща като член на редицата.

3) Редицата е монотонно растяща, т.е.:

P₁ < P₂ < P₃ < …. < P_N < …..

Напишете програма ROW.EXE , която по зададени цели, положителни числа A, B и C (1 <= А, B, C <= 100000) и N (1 <= N <= 5000) определя стойността на P_N.

От стандартния вход на един ред постъпват 4 числа, разделени с интервал – стойностите на A, B, C и N.

Програмата трябва да извежда на стандартния изход едно единствено число – намерената стойност на P_N.

Пример:

Вход:

3 5 17 4

Изход:

8

Редицата за примерния вход е:

3, 5, 6, 8, 9, 10, 11 ...