C++ Код | Ivelin Pavlov

За нуждите на ЦЕРН даден масив от данни, които те обработват, трябва да бъде сортиран. За
съжаление в ЦЕРН всички са твърде заети, за да напишат алгоритъм за сортиране, защото
последният им опит е излязал извън контрол и ако не бъдат взети спешни мерки, Земята ще бъде
погълната от черна дупка. Можете ли да помогнете на ЦЕРН?
За да може ЦЕРН да се възползва от алгоритъма ви, те ще ви зададат цяло число N < 10000, брой
на числа, които трябва да се сортират, последвано от редица от цели числа всяко от които е по-
малко от 10000000. Вие трябва за техните нужди да сортирате масива лексикогравски. Това става
като сравняваме първите цифри и ако при едното цифрата е по-малка, то е по-малко. Ако са
равни продължаваме със следващите цифри. Ако на някое от числата цифрите му се изчерпат
преди тези на другото по описания алгоритъм, тогава то е по-малкото (например 190 е по-голямо
от 1000).
Изхода от програмата ви трябва да е сортираните числа като всяко се принтира на отделен ред.

Вход:
5
190
1000
5
11
22

Изход:
1000
11
190
22
5

#include <iostream>
using namespace std;
int a[10000];

int intlength(int a) {
	if(a==0) return 1;
    int i=0;
    while(a>0) {
   	 a = a/10;
   	 i++;
    }
    return i;
}
int e(int a) {
	if(a<=0) return 1;
	int b = 1;
	for(int i=0;i<a;i++) {
		b = b*10;
	}
	return b;
}
bool leksikogravskaProverkaPoGolqmo(int a, int b) {
    int alen = intlength(a);
    int blen = intlength(b);
	int i = 1;
	bool ss= false;
	int tmpa,tmpb;
    while(alen>0 && !ss) { 
		tmpa = (a % e(alen))/e(alen-1);
		tmpb = (b % e(blen))/e(blen-1);
		if(blen<1) tmpb=-1;
		if(tmpa>tmpb) {
			ss = !ss;
			return 1;
		} else if(tmpa<tmpb) {
			return 0;
		}
		alen--;
		blen--;
		i++;
    }
    return 0;
}

void quicksort(int arr[],int left,int right) {
	int length = sizeof(arr);
	int i=left,j=right;
	int pivot = arr[(left+right)/2];

	while(i<=j) {
		while(!leksikogravskaProverkaPoGolqmo(arr[i],pivot) && arr[i]!=pivot)
			i++;
		while(leksikogravskaProverkaPoGolqmo(arr[j],pivot))
			j--;
		if(i<=j) {
			swap(arr[i],arr[j]);
			j--;
			i++;
		}
	}
	if(left<j)
		quicksort(arr,left,j);
	if(i<right)
		quicksort(arr,i,right);
}

int main() {
	int count;
	cin>>count;
	for(int i=0; i< count; i++) {
		cin>>a[i];
	}
	quicksort(a,0,count-1);
	for(int i=0;i<count;i++) {
		
		cout<<a[i];cout<<endl;
	}
}

ЗАДАЧА – Островландия

Известният мореплавател Станчо използвал своите хакерски умения и се сдобил с карта на Островландия. За съжаление обаче съкровището не било отбелязано с голям червен Х, ами просто било казано, че то се намира на най- големия остров. Картата била представена под формата на голям хексагон (правилен шестоъгълник), който е съставен от много на брой по малки хексагони. Страната на картата (големият хексагон) се състои от N хексагона. Всяка клетка в картата има стойност – нула или единица, в която нулите са вода, а единиците – суша. Съответно островите били съседни клетки от единици (като две клетки ще наричаме съседни, ако имат обща стена). Вашата задача е по дадена карта на Островландия да изведете големината на най- големия остров (в брой клетки). Най-големият остров на примера по-долу е отбелязан със зелени 1-ци.

Вход
От първия ред на стандартния вход програмата прочита едно число: 1 <= N <= 1000, представляващ броят на хексагоните стоящи на едната страна на картата. Следват 2 * N – 1 реда, всеки на който има последователности от нули и единици, описващи даден ред на картата.

Изход
На един ред на стандартния изход да се извежда едно число – големината на най-големия остров.

ПРИМЕРЕН ВХОД
5
1 0 0 1 1
1 0 1 0 1 0
1 0 0 0 1 0 1
1 0 0 0 1 1 1 0
0 1 0 1 1 0 0 1 1
0 0 0 0 0 1 1 0
1 1 0 0 0 0 0
1 1 0 1 1 0
1 0 1 0 1

ПРИМЕРЕН ИЗХОД
14

#include 
using namespace std;
bool island[2000][2000];
bool visitIsland[2000][2000];

int islandLength(int row, int col, int base) {
	visitIsland[row][col] = 1;
	int length = 1;
	if (row > 0) {
		if (row <= base-1) {
			if (col > 0) {
				if (row == base-1) {
					if (island[row+1][col-1] == 1 
						&& visitIsland[row+1][col-1] == 0) //dolu lqvo 1
						length += islandLength(row+1, col-1, base);
				}
				if (island[row-1][col-1] == 1 
					&& visitIsland[row-1][col-1] == 0) //gore lqvo
					length += islandLength(row-1, col-1, base);
				if (island[row][col-1] == 1 
					&& visitIsland[row][col-1] == 0) //lqvo 1
					length += islandLength(row, col-1, base);

			}
			if (col < base + row - 1) {
				if (row == base-1) {
					if(island[row+1][col] == 1 
						&& visitIsland[row+1][col] == 0) //dolu dqsno 1
						length += islandLength(row+1, col, base);
				}
				if (island[row-1][col] == 1 
					&& visitIsland[row-1][col] == 0) //gore dqsno
					length += islandLength(row-1, col, base);
				if (island[row][col+1] == 1 
					&& visitIsland[row][col+1] == 0) //dqsno 1
					length += islandLength(row, col+1, base);
			}
			if (row < base -1) {
				if (island[row+1][col] == 1 
					&& visitIsland[row+1][col] == 0) //dolu lqvo 2
					length += islandLength(row+1, col, base);
				if (island[row+1][col+1] == 1 
					&& visitIsland[row+1][col+1] == 0) //dolu dqsno 2
					length += islandLength(row+1, col+1, base);
			}
		} else {
			if (island[row-1][col] == 1 
				&& visitIsland[row-1][col] == 0) //gore lqvo 3
				length += islandLength(row-1, col, base);
			if (island[row-1][col+1] == 1 
				&& visitIsland[row-1][col+1] == 0) //gore dqsno 3
				length += islandLength(row-1, col+1, base);
			if (col < 3*base - row - 3) {
				if (row < 2*base - 1) {
					if (island[row+1][col] == 1 
						&& visitIsland[row+1][col] == 0) //dolu dqsno 2
						length += islandLength(row+1, col, base);
				}
				if (island[row][col+1] == 1 
					&& visitIsland[row][col+1] == 0) //dqsno 2
					length += islandLength(row, col+1, base);
			}
			if (col > 0) {
				if (row < 2*base - 1) {
					if (island[row+1][col-1] == 1 
						&& visitIsland[row+1][col-1] == 0) //dolu lqvo 3
						length += islandLength(row+1, col-1, base);
				}
				if (island[row][col-1] == 1 
					&& visitIsland[row][col-1] == 0) //lqvo 2
					length += islandLength(row, col-1, base);
			}
		}

	} else {
		if(col > 0) {
			if(island[row][col-1] == 1 
				&& visitIsland[row][col-1] == 0) //lqvo 3
				length += islandLength(row, col-1, base);
		}
		if(col < base + row - 1) {
			if(island[row][col+1] == 1
				&& visitIsland[row][col+1] == 0) //dqsno 3
				length += islandLength(row, col+1, base);
		}
		if (island[row+1][col] == 1 
			&& visitIsland[row+1][col] == 0) //dolu lqvo 3
			length += islandLength(row+1, col, base);
		if (island[row+1][col+1] == 1 
			&& visitIsland[row+1][col+1] == 0) //dolu dqsno 3
			length += islandLength(row+1, col+1, base);
	}
	return length;
}

int main() {
	int count;
	int lnLength;
	cin >> count;
	
	for (int i = 0; i < count; i++) {
		for (int j = 0; j < count + i; j++) {
			cin >> island[i][j];
			visitIsland[i][j] = 0;
		}
	}
	for (int i = count; i < 2 * count - 1; i++) {
		for (int j = 0; j < 3 * count - i-2; j++) {
			cin >> island[i][j];
			visitIsland[i][j] = 0;
		}
	}


	int bigest = 0;
	int temp;
	for (int i = 0; i < count; i++) {
		for (int j = 0; j < count + i; j++) {
			if (island[i][j] == 1 && visitIsland[i][j] == 0) {
				temp = islandLength(i,j,count);
				if (temp > bigest) {
					bigest = temp;
				}
			}

		}
	}
	for (int i = count; i < 2 * count - 1; i++) {
		for (int j = 0; j < 3 * count - i-2; j++) {
			if (island[i][j] == 1 && visitIsland[i][j] == 0) {
				temp = islandLength(i,j,count);
				if (temp > bigest) {
					bigest = temp;
				}
			}
		}
	}
	cout << bigest<