Сможете объяснить решение олимпиадной задачи?

Question

[Виталий К.]

Доброго дня!
Очень прошу объяснения от умных и находчивых "олимпиадников" по задаче с прошедшей олимпиады.

Условия задачи:
Артем создает интерактивный сенсор для игры в кости. Сенсор встроен в стол и может считать
суммарное число точек на гранях всех брошенных костей, прилегающих к сенсору (то есть, на
нижних гранях). Позже Артем понял, что для игры нужно считать сумму не на нижних, а на
верхних гранях. Артем хочет написать программу, которая по сумме на нижних гранях сможет
находить количество различных возможных сумм на верхних гранях. Но так как Артем не силен в
программировании, он поручает эту задачу вам.
Сенсор выдает число s равное суммарному числу точек на нижних гранях игральных костей.
Все бросаемые кости шестигранные и удовлетворяют условию правильной игральной кости, то есть
сумма точек на противоположных гранях кубика равна семи (1 и 6, 2 и 5, 3 и 4). Вам необходимо
найти количество возможных сумм на верхних гранях кубиков.

Формат входных данных:
В первой строке входного файла задано число s сумма на нижних гранях костей.
Формат выходных данных:
Выведите одно число: количество различных всевозможных сумм на верхних гранях косте

Примеры:
Input: 2 | Output: 2
Input: 4 | Output: 4

Решение на C++:

#include <fstream>
using namespace std;

int main() {
	ifstream fin("sensor.in");
	ofstream fout("sensor.out");
	int s, ans;
	fin >> s;
	ans = s - (s + 5) / 6 + 1; // (1)
	fout << ans << endl;
}

Код - версия решения от жюри.

Суть вопроса сводится к объяснению формулы (1). Буду благодарен за любое объяснение и в особенности за доходчивое.

Comments

[AtomKrieg]

Что у вас в тегах делает C++ и программирование. Это обычная формула математическая.

Answer 1

[Александр Ручкин]

Задача сводится к выяснению того, сколькими кубиками (не способами, а именно кубиками) может быть задана исходная сумма (нижних граней).
Например, 1 может быть задано только 1-м кубиком, ответ - 1
2 может быть задано как 1-м, так и 2-мя кубиками, ответ - 2
3 может быть задано 1-м, 2-мя или 3-мя кубиками, ответ - 3.
Рассмотрим 4. Может быть задано от 1-го до 4-х кубиками. Т.е. ответ - 4. Рассмотрим случай 2-х кубиков. Это могут быть комбинации 2 + 2 или 1 + 3, но оба они дадут одну и ту же сумму верхних граней: 6 + 6 - (2+2) или 6 + 6 - (1+3), что явно одно и то же.
У разных же количеств кубиков сумма разная, так как разное кол-во 6-к (самых больших чисел).

Итак, надо выяснить, сколькими кубиками можно задать сумму s. Понятно, что если s ≤ 6, то любым кол-вом от 1 до s. Но если s > 6, то одним кубиком уже не задать. Если s > 12 (6 * 2), то не задать уже и двумя.
Т.е. если s > 6, надо вычесть 1, если s > 12, надо вычесть 2, если s > 18, то вычесть 3.
Или, иначе говоря, если s > 6k, надо вычесть k. k можно посчитать как (s - 1) / 6 (целочисленное деление). Как только s становится больше 6k, то есть становится 6k + 1, получаем (6k + 1 - 1) / 6 = k. Если же s = 6k, то (6k - 1) / 6 = k - 1, что нам и надо.
Т.о. результат: s - (s - 1) / 6, что эквивалентно вашей формуле, так как
(s + 5) / 6 = (s - 1) / 6 - 1
(s + 5) / 6 - 1 = (s - 1) / 6

Comments

[Виталий К.]

Спасибо за разъяснение!) Очень доступно и понятно. Ваша формула корректна, хотя для меня не совсем ясно почему (s + 5) / 6 = (s - 1 ) / 6 - 1 . Если быть точнее, мне не ясно, как они (жюри) к этой формуле пришли, когда ваша выводится естественным образом. Если сможете уточнить мне этот момент - буду вам очень признателен!

[Александр Ручкин]

Went2Play: не могу сказать за жюри, но полагаю, что они решили не отнимать от s единицу, а прибавить 5. Когда надо целочисленно выразить k, это не важно, просто в их случае пришлось ещё единицей скомпенсировать.

[Виталий К.]

Александр Ручкин: Ну что же, в любом случае благодарю за подробное объяснение задачи!)

[Сергей Сергей]

s — максимальное количество кубиков для получения суммы (из единиц),
(s + 5)/6 — минимальное количество кубиков для получения суммы,
1 — балансировочная единица для случая s==1;
я бы так подумал за жюри.
хехе.

[Александр Ручкин]

Сергей Сергей: кстати да, скорее всего так
ибо если у нас минимальное значение x, а максимальное - y, то всего значений: y - x + 1