Задача С++ Определение "счастливого" билета

[vanyasmart]

Блин. Зашел в нет посмотреть правильный ответ к этой задачи, нашел этот форум и не удержался, чтобы не ответить.

Правильный ответ 55251. Но если считать билет с номером - 000 000, то ответ - 55252.

Вот решение придуманное моим другом во время участия в одной олимпиаде:

var
M:array [0..27] of Word;
I,J,K:Byte;
S:Word;
begin
FillChar(M,SizeOf(M),0);
S:=0;
for I:=0 to 9 do
for J:=0 to 9 do
for K:=0 to 9 do
Inc(M[I+J+K]);
for I:=0 to 27 do
S:=S+M[I]*M[I];
Writeln('S=',S);
Readln
end.

У меня другой вариант, но он сейчас не на компе с которого я пишу. Выложу потом.


Мой вариант собснноговоря (2 цикла по 999 итераций + массив из 27 элементов):

#include<conio.h>
#include<iostream>

int main(void)
{
/* Вариант 1 */

/* int arr[27],k=0;
for(int i=0;i<27;++i)arr[i]=0;

for(int i=1;i<=999;++i)++arr[i/100+i%100/10+i%10-1];
for(int i=1;i<=999;++i)k+=arr[i/100+i%100/10+i%10-1];*/


/* Вариант 2 */

int arr[28],k=0;
for(int i=0;i<28;++i)arr[i]=0;

for(int i=0;i<=9;++i)for(int j=0;j<=9;++j)for(int l=0;l<=9;++l)++arr[i+j+l];
arr[0]=0;
for(int i=0;i<=9;++i)for(int j=0;j<=9;++j)for(int l=0;l<=9;++l)k+=arr[i+j+l];
std::cout<<k;
getch();
return 0;
}

[coNsept]

//---------------------------------------------------------------------------
#include <vcl.h>
#pragma hdrstop
//---------------------------------------------------------------------------
#include <windows.h>
#include <stdio.h>
#include <conio.h> // clrscr();
//---------------------------------------------------------------------------
int CheckLuckTickLoop(LARGE_INTEGER &iDifTime);
int CheckLuckTickCombinatorics(LARGE_INTEGER &iDifTime);
//---------------------------------------------------------------------------

//---------------------------------------------------------------------------
// Решение в лоб: 1'000'000 итераций.
//---------------------------------------------------------------------------
int CheckLuckTickLoop(LARGE_INTEGER &iDifTime)
{
	int iResult = 0;
	// ----
	int d1, d2, d3, d4, d5, d6;
	// ----
	LARGE_INTEGER iStart, iStop;
	QueryPerformanceCounter(&iStart);
	// ----
	for(d1 = 0; d1 <= 9; d1++)
		for(d2 = 0; d2 <= 9; d2++)
			for(d3 = 0; d3 <= 9; d3++)
				for(d4 = 0; d4 <= 9; d4++)
					for(d5 = 0; d5 <= 9; d5++)
						for(d6 = 0; d6 <= 9; d6++)
							if(d1 + d2 + d3 == d4 + d5 + d6) iResult++;
	// ----
	QueryPerformanceCounter(&iStop);
	iDifTime.QuadPart = iStop.QuadPart - iStart.QuadPart;
	// ----
	return iResult;
}
//---------------------------------------------------------------------------

//---------------------------------------------------------------------------
// Решение через комбинаторику: 1'000 итераций. (Оптимизация в 1'000 раз)
//---------------------------------------------------------------------------
int CheckLuckTickCombinatorics(LARGE_INTEGER &iDifTime)
{
	int iResult = 0;
	// ----
	int i, j, z;
	byte buf[28];
	memset(&buf, 0, sizeof(buf));
	// ----
	LARGE_INTEGER iStart, iStop;
	QueryPerformanceCounter(&iStart);
	// ----
	for(i = 0; i <= 9; i++)
		for(j = 0; j <= 9; j++)
			for(z = 0; z <= 9; z++)
				buf[i + j + z] += 1;
	// ----
	for(i = 0; i < 28; i++) iResult += buf[i] * buf[i];
	// ----
	QueryPerformanceCounter(&iStop);
	iDifTime.QuadPart = iStop.QuadPart - iStart.QuadPart;
	// ----
	return iResult;
}
//---------------------------------------------------------------------------

void main()
{
	clrscr();
	// ----
	int iRes = 0;
	LARGE_INTEGER iDifTime;
	// ----
	iRes = CheckLuckTickLoop(iDifTime);
	printf("\CheckLuckTickLoop = %d; Time: %d\n\n", iRes, iDifTime);
	// ----
	iRes = CheckLuckTickCombinatorics(iDifTime);
	printf("\CheckLuckTickCombinatorics = %d; Time: %d\n\n", iRes, iDifTime);
	// ----
	system("Pause");
}
//---------------------------------------------------------------------------

Credit: S@nek