Програмен код на C/C++

Лексикографско сортиране на числа

За нуждите на ЦЕРН даден масив от данни, които те обработват, трябва да бъде сортиран. За
съжаление в ЦЕРН всички са твърде заети, за да напишат алгоритъм за сортиране, защото
последният им опит е излязал извън контрол и ако не бъдат взети спешни мерки, Земята ще бъде
погълната от черна дупка. Можете ли да помогнете на ЦЕРН?
За да може ЦЕРН да се възползва от алгоритъма ви, те ще ви зададат цяло число 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. Няма коментари.
(will not be published)