Задача 4: Станция
На трёх путях сортировочной станции стоят вагоны с абрикосами (А), бананами (Б) и вишней (В) так, как это показано на рисунке.
Машинист тепловоза (Т) может за один раз прицепить к тепловозу один или несколько вагонов с какого-нибудь пути, передвинуть их на правый путь, после чего передвинуть их на любой левый путь. Например, если тепловоз заберет 2 вагона с пути номер 3 на путь номер 1, то после такого действия распределение вагонов по путям будет таким.
А В Б А В
Б В А
Б
Соответствующую команду перемещения будем записывать так.
2 3 1
Что означает, что необходимо передвинуть 2 вагона с пути номер 3 на путь номер 1. Первое число обозначает количество перемещаемых вагонов, второе число – номер пути, с которого нужно забрать вагоны, третье число – номер пути, на который нужно передвинуть вагоны.
Разработайте алгоритм действий машиниста, необходимых для того, чтобы сформировать на каждом из путей составы с одинаковыми фруктами (не важно, на каком именно пути). Алгоритм оформите в виде последовательности команд, записанных в отдельных строках. Каждая команда имеет указанный выше вид: сначала записано число передвигаемых вагонов, потом номер пути с которого передвигаются вагоны, затем номер пути, на который передвигаются вагоны.
Например, следующая запись:
2 3 1
1 2 3
означает «передвинуть 2 вагона с пути 3 на путь 1, затем передвинуть 1 вагон с пути 2 на путь 3».
Чем меньше команд будет в вашем алгоритме, тем большее количество вы получите.
(см. объяснение)
Объяснение:
Пункт A:
Пусть во второй куче x камней. Тогда стратегия примет вид:
(8; x)⇒(8; 3x)
По условию 8+3x≥68 ⇒ x≥20.
Так как нам нужно найти минимальное значение, то берем число 20.
Пункт Б:
Здесь многие рекомендуют просто подбирать. Но если вы все время боитесь, что найдете подходящее значение S, а оно не окажется минимальное, попробуйте предложенный ниже вариант.
Напишем программу на языке Python 3:
def f(x, y, p):
if x + y >= 68 and p == 4:
return True
elif x + y < 68 and p < 4:
if p % 2 > 0:
return f(x + 2, y, p + 1) or f(x, y + 2, p + 1) or f(3 * x, y, p + 1) or f(x, 3 * y, p + 1)
else:
return f(x + 2, y, p + 1) and f(x, y + 2, p + 1) and f(3 * x, y, p + 1) and f(x, 3 * y, p + 1)
else:
return False
for i in range(1, 60):
if f(8, i, 1):
print(i)
Результатом ее работы будет число 19, поэтому его берем в ответ. Для самоконтроля, найденное число должно быть меньше 20, так как в противном случае Петя выиграет своим первым ходом.
Пункт В:
def f(x, y, p):
if x + y >= 68 and (p == 5 or p == 3):
return True
elif x + y < 68 and p < 5:
if p % 2 > 0:
return f(x + 2, y, p + 1) and f(x, y + 2, p + 1) and f(3 * x, y, p + 1) and f(x, 3 * y, p + 1)
else:
return f(x + 2, y, p + 1) or f(x, y + 2, p + 1) or f(3 * x, y, p + 1) or f(x, 3 * y, p + 1)
else:
return False
for i in range(1, 60):
if f(8, i, 1):
print(i)
Результатом работы программы будут два числа: 17 и 18. В ответ берем число 17.
Задание выполнено!
На самом деле изначально здесь была другая задача. Вот ее условие:
C4. Построить из строки следующую анаграмму
Ограничение времени 1 секунда
Ограничение памяти 64Mb
Ввод стандартный ввод или input.txt
Вывод стандартный вывод или output.txt
Для данного слова (последовательности строчных латинских букв) выведите следующее за ним (в лексикографическом порядке) слово, которое может быть получено из данного перестановкой букв (анаграмму). Если данное слово уже является последним среди всех своих анаграмм, то необходимо вывести первую возможную (в лексикографическом порядке) анаграмму.
Формат ввода
Задана последовательность слов, по одному слову в строке. Длина одного слова не превышает 50 символов.
Формат вывода
Необходимо вывести результат для каждого полученного на вход слова.
Ниже программный код:
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main() {
string word;
char for_sort[51];
int count_for_sort, min_def, min_def_index;
while (cin >> word) {
count_for_sort = 0;
min_def = 98;
min_def_index = 51;
for (int i = word.size() - 1; i >= 0; i--) {
for_sort[count_for_sort] = word[i];
count_for_sort++;
if (word[i] < word[i + 1])
break;
}
int shift = 0;
if (word[word.size() - count_for_sort] < word[word.size() - count_for_sort + 1]) {
for (int i = 0; i < count_for_sort; i++)
if (for_sort[i] - word[word.size() - count_for_sort] > 0 &&
for_sort[i] - word[word.size() - count_for_sort] < min_def) {
min_def = for_sort[i] - word[word.size() - count_for_sort];
min_def_index = i;
}
swap(for_sort[0], for_sort[min_def_index]);
shift = 1;
}
sort(for_sort + shift, for_sort + count_for_sort);
for (int i = word.size() - count_for_sort; i < word.size(); i++)
word[i] = for_sort[i - word.size() + count_for_sort)];
cout << word << endl;
word.clear();
}
return 0;
}