9002. Любитель шоколада

Азиз очень любит есть шоколад. Поскольку шоколад очень вреден для зубов, отец не разрешает ему есть много шоколада. В этот раз ему удалось убедить отца и получить разрешение кушать каждый день по одному шоколаду. Азиз любит два вида шоколада. Один из них весит a грамм, другой b грамм. Отец Азиза разрешил ему каждый день кушать по одному шоколаду в течение n дней, но с условием что нельзя кушать один и тот же шоколад два дня подряд. Теперь Азиза волнует только один вопрос. Как сделать так, чтобы в течение n дней он смог бы съесть максимальное количество (в граммах) шоколада.

Помогите ему в этом.

Вход. В одной строке заданы три целых числа n, a и b (1 ≤ n, a, b ≤ 10⁹) .

Выход. Выведите максимальное количество шоколада (в граммах), которое Азиз сможет употребить в течение n дней.

Пример входа 1	Пример выхода 1
1 10 8	10
Пример входа 2	Пример выхода 2
3 1 2	5

РЕШЕНИЕ

жадные алгоритмы

Анализ алгоритма

Если количество дней n четно, то Азиз может есть шоколад либо в порядке a b a b … a b, либо в порядке b a b … a b a. Однако в обоих случаях он съест (a + b) * n / 2 грамм шоколада.

При нечетном n Азиз может употреблять шоколад в одном из следующих порядков: a b a b … a, либо b a b … a b. В первом случае он съест n / 2 * b + (n + 1) / 2 * a грамм шоколада, во втором случае n / 2 * a + (n + 1) / 2 * b грамм. Осталось выбрать в каком из этих вариантов масса шоколада больше.

Действительно, в последовательности a b a b … a длины n (n нечетно) находится букв а и букв b.

Реализация алгоритма

Читаем входные данные.

scanf("%lld %lld %lld", &n, &a, &b);

Вычисляем ответ если количество дней n четно.

if (n % 2 == 0)

res = n / 2 * (a + b);

else

Вычисляем ответ если количество дней n нечетно.

{

x = n / 2 * a + ((n + 1) / 2 * b);

y = n / 2 * b + ((n + 1) / 2 * a);

res = (x > y) ? x : y;

}

Выводим ответ.

printf("%lld\n", res);

Java реализация

import java.util.*;

class Main

{

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

Читаем входные данные.

long n = con.nextLong();

long a = con.nextLong();

long b = con.nextLong();

long res = 0;

Вычисляем ответ если количество дней n четно.

if (n % 2 == 0)

res = n / 2 * (a + b);

Вычисляем ответ если количество дней n нечетно.

else

{

long x = n / 2 * a + ((n + 1) / 2 * b);

long y = n / 2 * b + ((n + 1) / 2 * a);

res = (x > y) ? x : y;

}

Выводим ответ.

System.out.println(res);

con.close();

}

}

Python реализация

Читаем входные данные.

n, a, b = map(int, input().split())

res = 0

Вычисляем ответ если количество дней n четно.

if n % 2 == 0:

res = n // 2 * (a + b)

Вычисляем ответ если количество дней n нечетно.

else:

x = n // 2 * a + ((n + 1) // 2 * b)

y = n // 2 * b + ((n + 1) // 2 * a)

if x > y:

res = x

else:

res = y

Выводим ответ.

print(res)