Задача . E. Serval и музыкальная игра

В первом наборе входных данных \(s_n=4\), \(f(x)\) вычисляется следующим образом:

• \(f(1)=1\)
  • \(\left\lfloor s_n\over 1\right\rfloor=4\), \(\left\lceil s_n\over 1\right\rceil=4\).
  • Можно показать, что \(p_1,p_2\) и \(q_1,q_2\), которые удовлетворяют условиям, не существует.
  • Пусть \(p_3=1\) и \(q_3=0\), тогда \(s_3 = p_3\cdot\left\lfloor s_n\over 1\right\rfloor + q_3\cdot\left\lceil s_n\over 1\right\rceil = 1\cdot 4 + 0\cdot 4 = 4\).
• \(f(2)=2\)
  • \(\left\lfloor s_n\over 2\right\rfloor=2\), \(\left\lceil s_n\over 2\right\rceil=2\).
  • Можно показать, что \(p_1\) и \(q_1\), которые удовлетворяют условиям, не существует.
  • Пусть \(p_2=1\) и \(q_2=0\), тогда \(s_2 = p_2\cdot\left\lfloor s_n\over 2\right\rfloor + q_2\cdot\left\lceil s_n\over 2\right\rceil = 1\cdot 2 + 0\cdot 2 = 2\).
  • Пусть \(p_3=0\) и \(q_3=2\), тогда \(s_3 = p_3\cdot\left\lfloor s_n\over 2\right\rfloor + q_3\cdot\left\lceil s_n\over 2\right\rceil = 0\cdot 2 + 2\cdot 2 = 4\).
• \(f(3)=3\)
  • \(\left\lfloor s_n\over 3\right\rfloor=1\), \(\left\lceil s_n\over 3\right\rceil=2\).
  • Пусть \(p_1=1\) и \(q_1=0\), тогда \(s_1 = p_1\cdot\left\lfloor s_n\over 3\right\rfloor + q_1\cdot\left\lceil s_n\over 3\right\rceil = 1\cdot 1 + 0\cdot 2 = 1\).
  • Пусть \(p_2=0\) и \(q_2=1\), тогда \(s_2 = p_2\cdot\left\lfloor s_n\over 3\right\rfloor + q_2\cdot\left\lceil s_n\over 3\right\rceil = 0\cdot 1 + 1\cdot 2 = 2\).
  • Пусть \(p_3=0\) и \(q_3=2\), тогда \(s_3 = p_3\cdot\left\lfloor s_n\over 3\right\rfloor + q_3\cdot\left\lceil s_n\over 3\right\rceil = 0\cdot 1 + 2\cdot 2 = 4\).
• \(f(4)=3\)
  • \(\left\lfloor s_n\over 4\right\rfloor=1\), \(\left\lceil s_n\over 4\right\rceil=1\).
  • Пусть \(p_1=1\) и \(q_1=0\), тогда \(s_1 = p_1\cdot\left\lfloor s_n\over 4\right\rfloor + q_1\cdot\left\lceil s_n\over 4\right\rceil = 1\cdot 1 + 0\cdot 1 = 1\).
  • Пусть \(p_2=1\) и \(q_2=1\), тогда \(s_2 = p_2\cdot\left\lfloor s_n\over 4\right\rfloor + q_2\cdot\left\lceil s_n\over 4\right\rceil = 1\cdot 1 + 1\cdot 1 = 2\).
  • Пусть \(p_3=2\) и \(q_3=2\), тогда \(s_3 = p_3\cdot\left\lfloor s_n\over 4\right\rfloor + q_3\cdot\left\lceil s_n\over 4\right\rceil = 2\cdot 1 + 2\cdot 1 = 4\).

Таким образом, ответ равен \(\sum_{x=1}^4 x\cdot f(x) = 1\cdot 1 + 2\cdot 2 + 3\cdot 3 + 4\cdot 3 = 26\).

Во втором наборе входных данных:

• \(f(1)=f(2)=f(3)=1\)
• \(f(4)=3\)
• \(f(5)=f(6)=f(7)=f(8)=f(9)=4\)

Например, когда \(x=3\), \(f(3)=1\), потому что существуют \(p_4\) и \(q_4\):

\(\)9 = 1 \cdot\left\lfloor{9\over 3}\right\rfloor + 2 \cdot\left\lceil{9\over 3}\right\rceil\(\)

Можно показать, что невозможно найти \(p_1,p_2,p_3\) и \(q_1,q_2,q_3\), которые удовлетворяют условиям.

Когда \(x=5\), \(f(5)=4\), потому что существуют следующие \(p_i\) и \(q_i\):

\(\)1 = 1 \cdot\left\lfloor{9\over 5}\right\rfloor + 0 \cdot\left\lceil{9\over 5}\right\rceil\(\) \(\)2 = 0 \cdot\left\lfloor{9\over 5}\right\rfloor + 1 \cdot\left\lceil{9\over 5}\right\rceil\(\) \(\)7 = 3 \cdot\left\lfloor{9\over 5}\right\rfloor + 2 \cdot\left\lceil{9\over 5}\right\rceil\(\) \(\)9 = 3 \cdot\left\lfloor{9\over 5}\right\rfloor + 3 \cdot\left\lceil{9\over 5}\right\rceil\(\)

Таким образом, ответ равен \(\sum_{x=1}^9 x\cdot f(x) = 158\).