//Описание добавить не вышло на сайт, посему - в файле
#include "stdafx.h" #include <conio.h>
void swap(short &a, short &b) { short c = a; a = b;
b = c; }
void sort(short &a, short &b, short &c) { short min = a, max = c; if (min > b) min = b; if (min > c) min = c; if (max < a) max = a; if (max < b) max = b; b = a + b + c - min - max; a = min; c = max; }
if ((a1 == a2) && (b1 == b2) && (c1 == c2)) printf("Boxes are equal"); else if ((a1 <= a2) && (b1 <= b2) && (c1 <= c2)) printf_s("The first box is smaller than the second one"); else if ((a2 <= a1) && (b2 <= b1) && (c2 <= c1)) printf_s("The first box is larger than the second one"); else printf_s("Boxes are incomparable");
Лемма. Если на каком-то шаге все куски одинаковой массы m, то можно путём указанных операций сделать так, чтобы все куски стали массой m/2. Доказательство. На первом шаге съедаем кусок массы m и разрезаем другой кусок массы m. Получится 8 кусков массы m и 2 куска массы m/2. Теперь 8 раз съедаем куски m/2 и распиливаем куски массы m.
Перейдём к собственно решению. Понятно, что Саша не мог съесть весь сыр. Поэтому, поскольку он съел целое число граммов сыра, он мог съесть не более, чем 360 - 1 = 359 граммов. Покажем, как он это мог сделать.
Пусть изначально головка сыра была разрезана так: 5 кусков по 512/9 г, 2 куска по 256/9 г, 1 кусок 128/9 г, 1 кусок 32/9 г, 1 кусок 8/9 г (легко проверить, что сумма всех масс равна 360).
Сначала съедим куски массой 8/9, 32/9, 128/9 и распилим три куска по 512/9 г. Останется 2 куска по 512/9 и 8 кусков по 256/9. Затем дважды съедим куски по 256/9 и разрежем оставшиеся куски по 512/9. После этого будет 10 кусков по 256/9.
Уменьшим размер каждого куска в 256 раз (воспользуемся 8 раз процессом, описанным в лемме). Тогда останутся 10 кусков массой 1/9 г. Съедаем один кусок и распиливаем любой оставшийся кусок. Несъеденная масса 9 * 1/9 = 1 г, значил, съел Саша 360 - 1 = 359 г сыра.
#include "stdafx.h"
#include <conio.h>
void swap(short &a, short &b) {
short c = a;
a = b;
b = c;
}
void sort(short &a, short &b, short &c)
{
short min = a,
max = c;
if (min > b) min = b;
if (min > c) min = c;
if (max < a) max = a;
if (max < b) max = b;
b = a + b + c - min - max;
a = min;
c = max;
}
int main()
{
short a1, b1, c1, a2, b2, c2;
scanf_s("%hd %hd %hd", &a1, &b1, &c1);
scanf_s("%hd %hd %hd", &a2, &b2, &c2);
sort(a1, b1, c1);
sort(a2, b2, c2);
if ((a1 == a2) && (b1 == b2) && (c1 == c2))
printf("Boxes are equal");
else
if ((a1 <= a2) && (b1 <= b2) && (c1 <= c2))
printf_s("The first box is smaller than the second one");
else
if ((a2 <= a1) && (b2 <= b1) && (c2 <= c1))
printf_s("The first box is larger than the second one");
else
printf_s("Boxes are incomparable");
_getch();
return 0;
}