Задача
Вася придумал новую игру. Для игры требуется полоска из трёх стоящих в ряд клеток, фишки $n$ различных видов и непрозрачный мешок.
В начале игры одинаковое количество фишек каждого вида помещается в мешок. Игра заключается в том, что игрок вытаскивает из мешка фишки одну за другой и помещает эти фишки в клетки полоски в том порядке, в котором он их вытащил. Игра считается выигранной, если на каких-нибудь двух соседних клетках оказались одинаковые фишки.
Сыграв несколько раз, иногда выигрывая и иногда проигрывая, Вася задумался над вопросом, насколько он везучий человек. А именно, насколько частота его выигрышей больше или меньше средней.
Чтобы оценить среднюю частоту выигрышей, Вася решил найти такую величину: количество выигрышных вариантов заполнения полоски разделить на количество всех вариантов заполнения полоски. Количество всех вариантов заполнения полоски Вася нашёл самостоятельно (получилось $n^3$), а вот для нахождения количества выигрышных вариантов он обратился к своему знакомому, лучше разбирающемуся в математике и программировании, т.е. к Вам.
Входные данные
В первой строке входных данных находится число ($1 \leq n \leq 10$)— количество видов фишек.
Выходные данные
Выведите одно число — количество выигрышных способов заполнить полоску из трёх клеток такими фишками.
Тесты
| Входные данные | Выходные данные |
| [latex]2[/latex] | [latex]6[/latex] |
| [latex]3[/latex] | [latex]15[/latex] |
| [latex]5[/latex] | [latex]45[/latex] |
| [latex]7[/latex] | [latex]91[/latex] |
| [latex]9[/latex] | [latex]153[/latex] |
Код программы
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
import java.util.*; import java.lang.*; import java.io.*; import java.util.Scanner; class Main { public static void main (String[] args) throws java.lang.Exception { Scanner in = new Scanner(System.in); int n; n = in.nextInt(); System.out.print(2 * n * n - n); } } |
Решение задачи
При проигрышных вариантах на выбранной полоске из трех позиций на первое место мы можем поставить [latex]n[/latex] вариантов фишек, а на вторую позицию [latex]n[/latex] — [latex]1[/latex],так как мы можем поставить все варианты кроме того вида, что использовали ранее, аналогично с третьей позицией. Теперь вычтем из кол-ва всех вариантов заполнения [latex]n^3[/latex] кол-во проигрышных [latex]n\cdot(n-1)^2[/latex] и получим кол-во выигрышных способов заполнить полоску. Все варианты могут быть выигрышными только в том случае, если у нас 1 вариант фишек.
Ссылки
Условие задачи на e-olymp.com.
Код решения на ideone.com.