Конечные автоматы

Однажды известный профессор обнаружил описания k конечных автоматов. По его мнению, нетривиальность конечного автомата, имеющего n состояний и m переходов, можно описать целым числом d = 19m + (n + 239)*(n + 366) / 2 . Чем больше d, тем больший интерес для науки представляет изучение его свойств.

Помогите профессору вычислить нетривиальность имеющихся у него автоматов.

Входные данные

Первая строка входных данных содержит целое число k (1 ≤ k ≤ 10000) – количество конечных автоматов. Следующие k строк содержат по два целых числа ni (0 ≤ ni ≤ 1000) и mi (0 ≤ mi ≤ 26ni2) – число состояний и переходов i-го автомата.

Выходные данные

На выходе должы получить данные из k строк. На i-й строке выходного файла выведите одно число – нетривиальность i-го автомата.

Решение:

Задача предельно простая при должном понимании что нам нужно знать, а что нужно забыть.

  1. Видел много вопросов о том, что такое нетривиальность. Сразу забыли про это. В задаче нет такого вопроса, следовательно отвечать на него мы не должны.
  2. Конечные автоматы - забыли. По той же самой причине.
  3. У нас есть уравнение, результат вычисления которой мы должны выводить: d = 19m + (n + 239)*(n + 366) / 2
  4. В этом уравнении при вычислении d помним, что 19m в программировании - это 19 * m

Код решения:

#include <iostream>

main(){
	int k, n, m, d;
	// Получаем количество данных k
	std::cin >> k;
	// Считываем данные k раз
	for (int i = 0; i < k; ++i){
		std::cin >> n >> m;
		// Вычисляем
		d = 19 * m + (n + 239)*(n + 366) / 2;
		// Выводим
		std::cout << d << "\n";
	}
}

Будем считать, что задачу мы решили. Но возникает желание немного поработать над кодом. Ведь по сути тут много лишнего. Что можно с ним сделать?

  1. for (int i = 0; i < k; ++i) мы можем легко поменять на while(k--). Тогда мы избавляемся от лишней переменной i. По сути освобождаем 4 байта памяти ))
  2. d = 19 * m + (n + 239)*(n + 366) / 2; мы можем легко убрать, заменив строку кода std::cout << d << "\n"; на std::cout << 19 * m + (n + 239)*(n + 366) / 2 << "\n"; От нас же не требуется выводить данные только тогда, когда все входные получим? Нет. И эта простая операция избавит нас от переменной d и лишней операции присвоения в цикле. Т.е. программа будет работать на O(n) быстрее...

В итоге мы получаем красивый короткий код

#include <iostream>

main(){
	int k, n, m;
	std::cin >> k;
	while (k--){
		std::cin >> n >> m;
		std::cout << 19 * m + (n + 239)*(n + 366) / 2 << "\n";
	}
}