Skip to Content
CTRL K

Powered Addition

Editorial oficial 

Explicación

Lo primero que hay que notar es que podemos obtener el número mínimo de segundos haciendo el mínimo indispensable para que la secuencia sea creciente. Si tenemos un número menor que su predecesor, no hay razón para hacer que ese número sea mayor que el que lo antecede.

Con eso resuelto, sabemos cuánto debemos sumar a cada número. Para obtener el número mínimo de segundos en total para hacer la secuencia no decreciente, podemos tomar los pisos del logaritmo en base 2 de cada número y sumar 1.

Implementación

Complejidad temporal: O(n)\mathcal{O}(n) por cada caso de prueba.

#include <algorithm>
#include <cmath>
#include <iostream>
#include <vector>
 
using std::cout;
using std::endl;
using std::vector;
 
int main() {
	int test_num;
	std::cin >> test_num;
	for (int t = 0; t < test_num; t++) {
		int size;
		std::cin >> size;
		vector<int> arr(size);
		for (int &i : arr) { std::cin >> i; }
 
		vector<int> target{arr[0]};
		vector<int> to_add;
		for (int i = 1; i < size; i++) {
			if (target.back() > arr[i]) {
				to_add.push_back(target.back() - arr[i]);
				target.push_back(target.back());
			} else {
				target.push_back(arr[i]);
			}
		}
 
		int min_time = 0;
		for (int a : to_add) { min_time = std::max(min_time, (int)log2(a) + 1); }
		cout << min_time << endl;
	}
}
import java.io.*;
import java.util.*;
 
public class PoweredAddition {
	public static void main(String[] args) {
		Kattio io = new Kattio();
		int testNum = io.nextInt();
		for (int t = 0; t < testNum; t++) {
			int size = io.nextInt();
			int[] arr = new int[size];
			for (int i = 0; i < size; i++) { arr[i] = io.nextInt(); }
 
			List<Integer> target = new ArrayList<>();
			target.add(arr[0]);
			List<Integer> toAdd = new ArrayList<>();
			for (int i = 1; i < size; i++) {
				if (target.get(target.size() - 1) > arr[i]) {
					toAdd.add(target.get(target.size() - 1) - arr[i]);
					target.add(target.get(target.size() - 1));
				} else {
					target.add(arr[i]);
				}
			}
 
			int minTime = 0;
			for (int a : toAdd) {
				minTime = Math.max(minTime, (int)(Math.log(a) / Math.log(2)) + 1);
			}
			System.out.println(minTime);
		}
	}
 
	// CodeSnip{Kattio}
}
from math import log2
 
for _ in range(int(input())):
	size = int(input())
	arr = [int(i) for i in input().split()]
	assert len(arr) == size
 
	target = [arr[0]]
	to_add = []
	for i in range(1, size):
		if target[-1] > arr[i]:
			to_add.append(target[-1] - arr[i])
			target.append(target[-1])
		else:
			target.append(arr[i])
 
	min_time = 0
	for a in to_add:
		min_time = max(min_time, int(log2(a)) + 1)
 
	print(min_time)
Fundamentos