Задача D: Системы счисления Сегодня Егор в школе проходил системы счисления, ему дали следующее определение представление числа в системе счисления:
Представлением целого положительного числа n в k-ичной системе счисления (k ≥ 2) называется последовательность целых неотрицательных чисел a1, ..., as такая, что ai ≤ k - 1 для всех i = 1...s и a1 ≠ 0, а также as + as - 1 · k + as - 2 · k2 + ... + a1 · ks - 1 = n.
Например, представлением числа 6 в двоичной системе счисления является последовательность 1, 1, 0, т.к. 0 + 1 · 2 + 1 · 4 = 6, а представлением числа 120 в одиннадцатиричной системе счисления является последовательность 10, 10, т.к. 10 + 10 · 11 = 120.
Можно показать, что любое целое положительное число n представимо единственным образом в k-ичной системе счисления для любого k ≥ 2.
Егор считает красивыми последовательности, которые заканчиваются ровно на два нуля. Сегодня в учебнике он наткнулся на целое положительное число n, и он захотел получить из него как можно больше красивых последовательностей, переводя n в различные системы счисления. Ему стало интересно, сколько различных красивых последовательностей он сможет получить?
Однако, так как число n очень большое, без программирования ему не обойтись. К сожалению, программировать он не умеет, поэтому обратился за к вам. Напишите программу, которая по заданному n считает количество различных красивых последовательностей, которые из него можно получить.
Формат входных данных
В единственной строке входных данных находится единственное целое число n (1 ≤ n ≤ 1018) – число, которое увидел Егор, идя из школы.
Обращаем внимание, что входные данные в этой задаче могут не поместиться в 32-битный целочисленный тип данных вашего языка, рекомендуется использовать 64-битный тип данных (long long, int64_t языка С++, int64 языка Free Pascal, long языка Java и т.д.)
Формат результата
Выведите единственное число – ответ на задачу.
В первом тесте единственные системы счисления, в которых у числа 8 есть нули на конце – двоичная и четверичная, но в двоичной оно заканчивается на 3 нуля, а в четверичной на 1, так что ни та, ни другая не подходит.
Во втором тесте можно получить последовательность 1, 1, 0, 0, переведя 12 в двоичную систему счисления.
В третьем тесте можно получить последовательность 1, 1, 0, 0, 1, 0, 0, переведя 100 в двоичную систему счисления, последовательность 4, 0, 0, переведя 100 в пятиричную систему счисления и последовательность 1, 0, 0, переведя 100 в десятичную систему счисления. Обратите внимание, что 101-ричная система счисления не подходит для числа 100, т.к. 100 представляется в 101-ричной системе счисления как последовательность из одного числа 100, последний элемент этой последовательности равен 100, а не 0.
#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>
#include <cmath>
int main()
{
int
sum(0), count(0),
A, B;
std::cin >> A >> B;
std::vector<int> vec;
std::copy(std::istream_iterator<int>(std::cin), std::istream_iterator<int>(), std::back_inserter(vec));
for(auto it = vec.begin(); it != vec.end(); it++)
{
if(A < *it && B > *it && (std::distance(vec.begin(), it) % 4) == 0)
sum += pow(*it, 2);
}
std::cout << "Количество нулей: " << std::count(vec.begin(), vec.end(), 0) << std::endl;
std::cout << "Сумма квадратов чисел: " << sum << std::endl;
}
1) И так, нам надо, что в слове всего 4 буквы и у нас есть 6 букв.
Поделим решение на две части: в первой части посчитаем все варианты, в которых буква Г стоит на первом месте, а во второй - где Г стоит на последнем.
Первая часть
Если буква Г стоит на первом месте, то у нас остается 3 "ячейки" под буквы (так как в слове 4 буквы и первая уже дана). В каждую из этих ячеек может стать любая из данных букв, КРОМЕ Г, так как сказано, что она встречается только один раз и она уже встретилась. То есть всего букв 5 и 3 ячейки. 5 вариантов букв во вторую * 5 вариантов в третью * 5 вариантов в четвертую = 125 вариантов. То есть всего есть 125 вариантов расстановки, если Г стоит на первом месте.
Вторая часть
Тут все абсолютно аналогично! Только Г стоит не на первом, а на последнем месте, и мы разбираем не вторую, третью и четвертую ячейки, а первую, вторую и третью. Тут тоже будет 125 вариантов.
То есть всех вариантов 125 + 125 = 250. Не так много слов однако.
2) Решение схоже с первой задачей. нам дано, что есть 3 буквы в слове и 6 букв на выбор. Но Я встречается или на первой, или на третьей позиции, или вообще не встречается.
Сначала посчитаем все случаи, когда Я не встретится вообще. Тогда нам надо 3 ячейки под буквы и 5 букв выбор, то есть 5 * 5 * 5 = 125 вариантов (без Я).
Теперь рассмотрим варианты с Я:
Первый
Я стоит на первой позиции. Тогда во второй и в третьей ячейке есть по 5 вариантов(так как букв 5), то есть 5 * 5 = 25 вариантов.
Второй
Я стоит на третьей позиции, тогда в первой и во второй ячейке есть по 5 вариантов, то есть всего 5 * 5 = 25 вариантов.
Всего будет 25 + 25 + 125 вариантов = 175 вариантов.
Это, в общем - то, и ответ.