Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в три раза. Например, имея кучу из 15 камней, за один ход можно получить кучу из 16 или 45 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче становится не менее 66. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 66 или больше камней. В начальный момент в куче было S камней, 1 ≤ S ≤ 65.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит, описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника.
Найдите два таких значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
— Петя не может выиграть за один ход;
— Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Найденные значения запишите в ответе в порядке возрастания без разделительных знаков.
Решение представлено во вложении.
Язык: Pascal
ответ: переменная c примет значение 10.
Примечание:
div - целая часть от деления.
Ручная прогонка:
1 шаг:
a:=17;
2 шаг:
b:=(a div 10)*10; // 17 = 1 * 10 + 7 => a div 10 = 1; (a div 10) * 10 = 1*10 = 10; Получаем в b значение 10;
3 шаг:
a:=(b*2) + a div 100; // b * 2 = 10 * 2 = 20; a div 100 = 17 div 100 = 0;
a = 20 + 0 = 20; Получаем в a значение 20;
4 шаг:
Проверяем выполнение условий:
(a > b)? - Да, 20 > 10, значит в переменную c записываем значение (a-b). Получаем: c = a - b = 20 - 10 = 10.
ответ: с = 10
/*Работа программы ограничена размерностью int, то есть за переполнением надо следить отдельно. Распознавание возможно и для координат больших ZZ и 702. Реализация основных функций, вс функции перевода из строки в целое число и пример использования приведены ниже. Ввод строки std::string желательно организовывать в виде std::getline(std::cin, str); В функции let_to_number(std::string) пришлось возвращать пару int, а не std::string(из-за условия), поэтому в main необходима проверка на корректное преобразование: пара (0, 0) - некорректное, иначе - корректное.*/
#include <iostream>
#include <string>
std::string numb_to_letter(std::string source);
int str_to_i(std::string);
std::pair<int, int> let_to_number(std::string source);
int main()
{
std::string source1 = "53 12";
std::string source2 = "AA12";
std::cout << numb_to_letter(source1) << std::endl;
std::pair<int, int> a = let_to_number(source2);
if (a.second == 0)
{
std::cout << "Error! Incorrect input\n";
}
else
{
std::cout << a.first << " " << a.second << std::endl;
}
return 0;
}
std::string numb_to_letter(std::string source)
{
const std::size_t pos = source.find(" ");
if (pos == std::string::npos)
{
return "Error! Incorrect input\n";
}
std::string result;
int x = str_to_i(source.substr(0, pos)), y = str_to_i(source.substr(pos + 1));
if (x == 0 || y == 0)
{
return "Error! Incorrect input\n";
}
while (x != 0)
{
result = char(-1 + 'A' + (x % 26 == 0 ? 26 : x % 26)) + result;
x -= (x % 26 == 0 ? 26 : x % 26);
x /= 26;
}
result += std::to_string(y);
return result;
}
int str_to_i(std::string source)
{
int n = 0;
for (auto i = 0; i < static_cast<int>(source.size()); i++)
{
if (!('0' <= source[i] && source[i] <= '9'))
{
return 0;
}
n = n * 10 + source[i] - '0';
}
return n;
}
std::pair<int, int> let_to_number(std::string source)
{
std::string result;
std::size_t pos = 0;
while ('A' <= source[pos] && source[pos] <= 'Z' && pos < source.size())
{
pos++;
}
if (pos == source.size() || pos == 0)
{
return std::pair<int, int> {0, 0};
}
std::string tmp = source.substr(0, pos);
int x = 0;
for (auto i = 0; i < static_cast<int>(tmp.size()); i++)
{
x += (source[i] - 'A' + 1) * static_cast<int>(pow(26, pos - 1 - i));
}
if (source[pos] == ' ')
{
pos++;
}
if (source[pos] == ' ')
{
return std::pair<int, int> {0, 0};
}
int y = str_to_i(source.substr(pos));
return (y == 0 ? std::pair<int, int>{0, 0} : std::pair<int, int>{x, y});
}