Цікава задачка «Нещасливий квиток»

imageДумаю всім з дитинства знайома задача про щасливому квитку. Однак найчастіше поїздка в автобусі займає набагато більше часу, ніж час, витрачений на підсумовування перших і останніх трьох цифр.

І щоб розважити себе до кінця поїздки, я винайшов концепт «Нещасливого квитка». Квитка, у якого ні одне число з множини значень, отриманого за допомогою перших трьох цифр, не збігається ні з одним числом з безлічі значень, отриманого за допомогою останніх трьох цифр. Подробиці в умові задачі.

Умова задачі

Знайти всі значення з 6 цифр, для яких ні одне із значень множини, отриманого з перших трьох цифр, не збігається ні з одним значенням множини з останніх трьох цифр.

Безліч значень для кожної тріади потрібно отримати:

  • Застосовуючи перестановку чисел у межах тріади
  • Виконуючи арифметичні дії між цифрами: +, -, *, /
  • Використовуючи дужки.
  • Застосовуючи в якості значень множини тільки цілі числа
ПрикладКвиток: 983060

Безліч значень тріади: 983 [96, 33, 2, 3, 35, 99, 4, 69, 5, 75, 11, 45, 14, 15, 48, 51, 19, 20, 216, 24]
Безліч значень тріади: 060 [0, 6]

Загального значення немає — це нещасливий квиток.

p.s. Опускаю негативні значення, так як для кожного від'ємного значення знайдеться таке ж позитивне
Таким чином, якщо ви до кінця поїздки не змогли знайти загальне число для перших і останніх трьох цифр, використовуючи дії з умови, значить вам трапився нещасливий квиток! Чи у вас не дуже з математикою.

Мій варіант рішення задачіВикладати весь код не бачу сенсу, постараюся пояснити головне.

Список всіх комбінацій з трьох цифр — 1000 штук. Набір, в який будуть складатися знайдені квитки.

List<Combination> combinations = new ArrayList<>(1000);
Set<String> tickets = new HashSet<>();

Для кожного числа з множини значень однієї комбінації, перевіряємо чи є таке число у множині значень іншої комбінацій.

Поки загальне значення не знайдено, додаємо рядок, що означає наш квиток, в набір.
Як тільки значення знайдеться, видаляємо квиток з набору і переходимо до наступного порівнянні.

for (Combination comb1 : combinations)
{
for (Combination comb2 : combinations)
{
for (Integer x : comb1.getValues())
{
if (comb2.getValues().contains(x))
{
tickets.remove(comb1.toString() + comb2.toString());
break;
}
else
{
tickets.add(comb1.toString() + comb2.toString());
}
}
}
}

Наводжу метод, який обчислює множину значень для кожної комбінації:
(Метод виконується для кожної перестановки 3 цифр комбінації)

private void countValues(int a, int b, int c)
{
//Sum
addValue(a + b + c);
addValue(a + b - c);
addValue(a + b * c);
addValue((a + b) * c);

if (c != 0 && b % c == 0) {addValue(a + b / c);}
if (c != 0 && (a + b) % c == 0) { addValue((a + b) / c); }

//Subtraction
addValue(a - b + c);
addValue(a - b - c);
addValue(a - b * c);
addValue((a - b) * c);

if (c != 0 && b % c == 0) {addValue(a - b / c);}
if (c != 0 && (a - b) % c == 0) {addValue((a - b) / c);}

//Multiplication
addValue(a * b + c);
addValue(a * b - c);
addValue(a * (b - c));
addValue(a * b * c);

if (c != 0)
{
double x = (double)a * (double)b / (double)c;

if (isInteger(x)) { addValue((int)x); }
}

if (c != 0)
{
double x = (double)a * (double)b / (double)c;

if (isInteger(x)) { addValue((int)x); }
}

//Division

if (b != 0 && a % b == 0) { addValue(a / b + c); }
if (b + c != 0 && a % (b + c) == 0) { addValue(a / (b + c)); }

if (b != 0 && a % b == 0) { addValue(a / b - c); }
if (b - c != 0 && a % (b - c) == 0) { addValue(a / (b - c)); }

if (b != 0)
{
double x = (double)a / (double)b * (double)c;

if (isInteger(x)) { addValue((int)x); }
}

if (b != 0 && c != 0)
{
double x = (double)a / (double)b / (double)c;

if (isInteger(x)) { addValue((int)x); }
}
}

Разом: 23088 квитків.

Щасливий квиток: кожен 18
Нещасливий квиток: кожен 43

Спасибі за увагу!
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.