Про Всеукраїнську студентську олімпіаду з програмування
Всеукраїнська студентська олімпіада з програмування була організована за ініціативою Вінницького національного технічного університету та проводиться за підтримки Міністерства освіти і науки України, ІТ-компанії «Арт-мастер» та Всеукраїнського благодійного фонду «Асоціація підтримки та розвитку інформаційних технологій» («АПРІТ») Головною метою олімпіади є надання українським студентам можливості продемонструвати свою майстерність у мистецтві розробки алгоритмів і програм на високому міжнародному рівні. З а 10 років проведення олімпіади Україна вийшла на п’яту позицію всесвітнього рейтингу Топкодера (http://www.topcoder.com/stat?c=country_avg_rating). П’ять українських університетів входять сьогодні до топ-50 у всесвітньому рейтингу університетів (при цьому КНУ ім.. Т. Шевченка посідає в ньому п’яту позицію), а п’ять українських студентів до тол-50 в особистому світовому рейтингу. Останні п’ять років українські студенти повністю домінують у світовому півфіналі по південно-східній Європі (у 2009 р. – перші сім місць!), пропустивши за цей час до світового фіналу лише одну не українську команду.
Більш детальну інформацію можна отримати на сайтах:
першості світу з програмування - http://cm.baylor.edu/welcome.icpc
українського чвертьфіналу першості світу –
http://cm.baylor.edu/public....=106838
Всеукраїнської студентської олімпіади з програмування - http://pc-ua.com.ua/

Задача 3. ACM для ГСМ (50 балів)
Зіпсувався якось на одній заправці лічильник бензину. Добре, що хоч відсікач там був (це щоб наповнювати ємність повністю, але не переливати).
Під‘їхав на цю заправку програміст-АСМер. А йому кажуть: «Так і так, заправка несправна, їдь собі на іншу заправку». Тут зауважив АСМер на стійці заправки три пусті каністри. Задумався АСМер, а що якщо першу каністру налити доверху, а потім з неї в другу вилити, а потім з третьої... Може і вдасться відміряти потрібну кількість бензину?
І, як звичайно, задумався він не над частковим випадком задачі, а над загальним формулюванням: скільки різних об‘ємів бензину він зможе відміряти цими каністрами?
Правда, треба враховувати, що на заправці бензин розливати не можна (екологія!). І за вимогою власника заправки переливати бензин можна лише з однієї каністри в іншу, а в бак бензин можна переливати (із всіх каністр або лише з деяких) лише після закінчення всіх переливань бензину в каністри і між ними.
Вхідні дані: В кожному з трьох рядків записане ціле число від 0 до 255 – ємність каністри в літрах.
Вихідні дані: Результатом є єдине число – кількість різних варіантів відповіді на запитання: скільки літрів можна відміряти з допомогою наявних каністр?
Приклад вхідних даних:
0
3
4
Приклад вихідних даних:
6
Підказка: Немає сенсу відміряти 0 літрів, тому це значення враховувати не треба.

Ще, мабуть, можна 1 і 2...

Ніби нічого складного, але не виходить.
Я написав так:
S:=1;
for i:=1 to n do
S:=S*3 - S div 3;
Але не виходить так як у контрольному тесті.

Один мій учень зробив так:
S:=1;
for i:=1 to n do
S:=2*S + 1;
Теж не вийшло як у тесті.

Щось заклинило у голові на такій простій задачі. Допоможіть розібратися.

Я спочатку не розглядав розв’язок Толіного учня, тому зробив своїм методом, як завжди запутаним, але він збігається з результатами учня Бандалака:

2^(n-1)*3+2^(n-1)-1
Математично, можна правда спростити
4*2^(n-1)-1

А учень молодець.