№ 3 Пирамидки Ограничение по времени: 1 секунда Ограничение по памяти: 256 мегабайт Ваня…
- User
№ 3
Пирамидки
Ограничение по времени: 1 секунда
Ограничение по памяти: 256 мегабайт
Ваня хочет построить из кубиков и пирамидок. Он собирает пирамидки следующим
образом:
-
Изначально в каждой пирамидке имеется по аз кубиков в первом ряду.
-
В каждой второй пирамидке, т.е. номер которой делится на 2, к ним добавляется по аз кубиков во второй ряд.
-
В каждой четвёртой пирамидке, т.е. номер которой делится на 4, добавляется по аз кубиков в третий ряд.
-
В каждой восьмой пирамидке, т.е. номер которой делится на 8, добавляется по ад кубиков в четвёртый ряд.
И так далее.
Выразим условие более формально: в каждой пирамидке, номер которой делится
на (2-1)-ую степень числа 2, к исходному числу кубиков а₁ добавляется по а; кубиков
в і ряд. Помогите Ване определить количество кубиков, которое ему нужно для построения
всех пирамидок.
Формат входных данных
Первая строка входных данных содержит число п (1 ≤ n ≤ 109) которые хочет построить Ваня. количество пирамидок,
Вторая строка входных данных содержит число k (1 ≤ k ≤ 30) количество рядов,
для которых известно, сколько в них будет кубиков. Гарантируется, что в каждой пирамидке не более чем к рядов.
Каждая из следующих к строк содержит а (1 ≤ a ≤ 10º) количество кубиков в і-м ряде пирамидки. Количество кубиков, требующихся для каждого следующего слоя, не убывает.
Формат выходных данных
В единственной строке выведите число количество кубиков, которые нужны Ване для постройки всех пирамидок.
Обратите внимание, что ответ в этой задаче может превышать возможное значение
32-битной целочисленной переменной, поэтому необходимо использовать 64-битные
целочисленные типы данных (тип int64 в языке Pascal, тип long long в C++, тип long в Java и С#).
Система оценки
Решения, правильно работающие при п≤ 15, а ≤ 100, будут оцениваться в 20 баллов. Решения, правильно работающие при п≤ 105, будут оцениваться в 50 баллов.
Замечание
Рассмотрим первый пример. Пирамидки с нечётными номерами 1, 3, 5 имеют по одному ряду и состоят из 1 кубика. Пирамидки с номерами 2, 6 имеют по два ряда и состоят из 1 + 3 кубиков. Пирамидка с номером 4 имеет 3 ряда и состоит из 1+3+8 кубиков. В сумме Ване потребуется 1+(1+3)+1+(1+3+8)+1+(1+ 3) = 23 кубика. Пирамидки изображены на рисунке. Пример: Ввод: 6 3 1 3 8 Вывод: 23
Ввод: 8 4 2 5 8 11 Вывод: 63
-
- Assistant
To solve this problem, we need to calculate the total number of cubes Vanya requires to build all the pyramids. The approach involves summing cubes for each layer across all pyramids, with the condition that each layer is added based on the pyramid number's divisibility by powers of 2.
Step-by-Step Reasoning:
-
Understanding the Pyramid Structure:
- Each pyramid has a base layer with
a1cubes. - The second layer with
a2cubes is added only to pyramids numbered with multiples of 2. - The third layer with
a3cubes is added to pyramids numbered with multiples of 4, and so on.
- Each pyramid has a base layer with
-
General Approach:
- For each layer
i, determine how many pyramids have that layer. This can be calculated asfloor(n / 2^(i-1)), wherenis the total number of pyramids. - Multiply the number of pyramids that have layer
iby the number of cubesaiin that layer. - Sum these values across all layers to get the total number of cubes required.
- For each layer
-
Edge Considerations:
- The number of layers
kcan be up to 30, which corresponds to checking divisibility by powers of 2 up to2^29. - Ensure that intermediate calculations do not exceed the limits of 64-bit integers, as the final result can be very large.
- The number of layers
-
Implementation:
- Iterate through each layer from 1 to
k. - For each layer, calculate the divisor
2^(i-1). - If the divisor exceeds
n, no pyramids have that layer. - Otherwise, calculate how many pyramids have that layer and multiply by the number of cubes in that layer.
- Accumulate the result to get the total number of cubes.
- Iterate through each layer from 1 to
Example:
For the first example:
- There are 6 pyramids and 3 layers with
a1 = 1,a2 = 3,a3 = 8. - Calculate cubes for each layer:
- Layer 1:
6 * 1 = 6 - Layer 2:
3 * 3 = 9 - Layer 3:
1 * 8 = 8
- Layer 1:
- Total cubes:
6 + 9 + 8 = 23
Final Solution:
#include <bits/stdc++.h> using namespace std; typedef long long ll; int main(){ ios::sync_with_stdio(false); cin.tie(0); ll n; cin >> n; int k; cin >> k; vector<ll> a(k); for(int i=0;i<k;i++) cin >> a[i]; ll total =0; for(int i=1;i<=k;i++){ if(i-1 >= 60){ // 2^(i-1) would overflow long long break; } ll d = 1LL << (i-1); if(d > n) continue; ll m = n / d; total += a[i-1] * m; } cout << total; } -