DZone Snippets: cpp code

A solution for the "Carmichael Numbers" problem

jmftrindade (Joana M. F. da Trindade) — Thu, 24 Apr 2008 23:16:02 GMT

A solution for the "Carmichael Numbers" problem.

Problem description:
http://icpcres.ecs.baylor.edu/onlinejudge/external/100/10006.html

Author: Joana Matos Fonseca da Trindade
Date: 2008.04.24



/* 

 * Solution for "Carmichael Numbers" problem.

 * UVa ID: 10006

 */

#include 

#include 



#define MAXPRIME 65001



using namespace std;



/*

 * Modular exponentiation algorithm. Returns b^e mod m.

 */

unsigned long long fast_mod_pow(unsigned long long b, unsigned long long e, unsigned long long m) {

    unsigned long long r = 1;

    while (e > 0) {

        if ((e & 1) == 1) {

	    r = (r * b) % m;

        }

        e >>= 1;

        b = (b * b) % m;

    }

    return r;

}



/* 

 * Generates all prime numbers up to MAXPRIME. Based on

 * the Sieve of Eratosthenes.

 */

void gen_primes(bool p[]) {

    p[0] = p[1] = false;

	

    /* 

     * starting at number 2 and going to the upper limit, mark 

     * all numbers as potential primes 

     */  

    for (int i=2; i        p[i] = true;

    }

	

    int m = floor(sqrt(MAXPRIME));

    int n;

    /* 

     * mark all multiples of a prime as non-primes. this has to be done for primes 

     * only up to the square root, since every number in the array has at least 

     * one factor smaller than the square root of the limit. 

     */

    for (int i=2; i        if (p[i]) {

       	    n = MAXPRIME / i;

	    for (int j=2; j<=n; j++) {

	        p[i * j] = false;

	    }

	}

    }

}



/* generates all carmichael numbers up to the given limit by performing the fermat test */

void gen_carmi(bool c[], bool p[]) {



    /* initialize carmichael numbers array with false */

    memset(c, 0, MAXPRIME * sizeof(bool));

	

    /* 

     * starting from the first non-prime, mark all 

     * odd numbers as potential carmichael numbers 

     */

    for (int i=9; i	c[i] = true;

    }

	

    /* 

     * again, for all odd numbers, we exclude the primes and perform

     * the fermat test for 2 <= a <= n-1.

     */

    for (int n=9; n	/* VERY IMPORTANT! check first if this number is prime, otherwise we get TLE */

	if (p[n]) {

	    c[n] = false;

	    continue;

	}

	for (int a=2; a<=n-1; a++) {

	    if (fast_mod_pow(a,n,n) != a) {

	        c[n] = false;

		break;

	    } 

	}	

    }

}



/* main */

int main() {

    unsigned long long n; /* number */

    unsigned long long a; /* a of the fermat test */

    bool prime[MAXPRIME]; /* prime numbers array */

    bool carmi[MAXPRIME]; /* carmichael numbers array */

	

    gen_primes(prime);

    gen_carmi(carmi, prime);

	

    while (cin >> n && (n != 0)) {	

        if (carmi[n]) {

            cout << "The number " << n << " is a Carmichael number." << endl;

        } else {

            cout << n << " is normal." << endl;

        }

    }

    return 0;

}

A solution for the "Binomial Showdown" problem

jmftrindade (Joana M. F. da Trindade) — Mon, 14 Apr 2008 01:43:03 GMT

A solution for the "Binomial Showdown" problem.

Problem description:
http://acm.uva.es/p/v5/530.html

Author: Joana Matos Fonseca da Trindade
Date: 2008.04.11



/*

 * Solution for the "Binomial Showdown" problem.

 * UVa ID: 530

 */



#include 



using namespace std;



/* main */

int main() {

    int n, k;

    unsigned long long r; /* result */



    while(cin >> n >> k && ((n != 0) || (k != 0))) {

        /* init result */

        r = 1;



        /* if k is more than half of n, then use the complement */

        if(k > (n / 2)) {

            k = n - k;

        }



        /*         

         * C(n,k) = n! / (k!(n-k)!) =

         * (n)(n-1)(...)(n-k+1) / 2*3*4*(...)*k

         */ 

        for (int i=0; i            r = r * (n - i);   /* (n)(n-1)(...)(n-k+1) */

            r = r / (1 + i);   /* 2*3*4*(...)*k */

        }

        cout << r << endl;

    }

}

A solution for the "Reverse and Add" problem

jmftrindade (Joana M. F. da Trindade) — Mon, 14 Apr 2008 01:38:45 GMT

A solution for the "Reverse and Add" problem.

Problem description:
http://icpcres.ecs.baylor.edu/onlinejudge/external/100/10018.html

Author: Joana Matos Fonseca da Trindade
Date: 2008.04.14



/*

 * Solution for the "Reverse and Add" problem.

 * UVa ID: 10018

 */

#include 



#define NDIGITS 100



using namespace std;



/* returns the reversed number */

unsigned long long reverse(unsigned long long number) {

	unsigned long long m = 0; /* reversed number */

	int digits[NDIGITS]; /* digits array */

	int pos = 0, power = 1;

	

	/* init */

	for (int i=0; i		digits[i] = 0;

	}

	

	/* retrieve all digits */

	while (number > 0) {

		digits[pos++] = number % 10;

		number = number / 10;

	}



	/* multiply the reversed digits by the powers of ten */

	for (int i=pos-1; i>=0; i--) {

		m += power * digits[i];

		power *= 10;

	}

	

	return m;

}



/* main */

int main() {

	int nc; /* number of cases */

	int m; /* minimum number of iterations */

	unsigned long long n; /* number */

	

	cin >> nc;

	

	/* reverse and add.. */

	for (int i=0; i		cin >> n;

		m = 0;

		while (true) {

			if (reverse(n) == n) {

				break;

			} else {

				n += reverse(n);

				m++;

			}

		}

		cout << m << " " << n << endl;

	}

	

	return 0;

}

A solution for the "Primary Arithmetic" problem

jmftrindade (Joana M. F. da Trindade) — Mon, 14 Apr 2008 01:21:01 GMT

A solution for the "Primary Arithmetic" problem.

Problem description:
http://icpcres.ecs.baylor.edu/onlinejudge/external/100/10035.html

Author: Joana Matos Fonseca da Trindade
Date: 2008.04.04



/**

 * Solution for the "Primary Arithmetic" problem.

 * UVa ID: 10035

 */ 

#include  

#include  



using namespace std; 



int main() {

    unsigned long long n1; /* 1st number */ 

    unsigned long long n2; /* 2nd number */ 

    int carry = 0; /* carry */ 

    int sum = 0; /* temporary sum */ 

    int count = 0; /* carry counter */ 



    while(cin >> n1 >> n2 && ((n1 > 0) || (n2 > 0))) { 

        carry = 0; 

	count = 0; 

	sum = 0; 



	/* while there's still something.. */ 

	while ((n1 > 0) || (n2 > 0)) { 

	    /* sum the two right-most digits */ 

	    sum = carry + (n1 % 10) + (n2 % 10); 



	    if (sum >= 10) { 

		count++; 

	    } 

			

	    /* get the carry by dividing the sum of the two digits */ 

	    carry = sum / 10; 



	    /* 'reduce' the numbers by ten, to update the right-most digits */ 

	    n1 /= 10; 

            n2 /= 10; 

	} 

		

	if (count == 0) { 

            cout << "No carry operation." << endl; 

	} else if (count == 1) { 

	    cout << "1 carry operation." << endl; 

	} else { 

            cout << count << " carry operations." << endl; 

        } 

    } 



    return 0;

}

A solution for the "Shoemaker" problem

jmftrindade (Joana M. F. da Trindade) — Mon, 14 Apr 2008 01:02:22 GMT

A solution for the "Shoemaker" problem.

Problem description:
http://icpcres.ecs.baylor.edu/onlinejudge/external/100/10026.html

Author: Joana Matos Fonseca da Trindade
Date: 2008.04.06



/* 

 * Solution for "Shoemaker" problem.

 * UVa ID: 10026

 */

#include 



#define NJOBS 1000



using namespace std;



int jobs[NJOBS]; /* jobs */

double p[NJOBS]; /* priority */



/* main */

int main() {

    int nc;	/* number of cases */

	int nj; /* number of jobs */

	int ct;	/* completion time */

	int dp; /* daily penalty */

	

    cin >> nc;

	

	/* for each test case.. */

    for (int i=0; i		cin >> nj;

		

		/* init input */

		for (int i=0; i			cin >> ct >> dp;

			jobs[i] = i;

			/* priority is daily penalty divided by completion time (minimal fine) */

			p[i] = double(dp) / ct;

		}

		

		int j, k, tmp;

		

		/* sort jobs by priority */

		for (int i=0; i			for (j=i+1, k=i; j				if( (p[jobs[j]] > p[jobs[k]]) || ((p[jobs[j]] == p[jobs[k]]) && (jobs[j] < jobs[k])) ) {

					k=j;

				}

			}

			tmp = jobs[i]; 

			jobs[i] = jobs[k]; 

			jobs[k] = tmp;

		}

		

		/* output */

		for (int i=0; i			if(i > 0) { 

				cout << " ";

			}

			cout << jobs[i] + 1;

		}

		cout << endl;

		if (i < nc-1) {

			cout << endl;

		}

    }

	

    return 0;

}

A solution for the "Stack 'em Up" problem

jmftrindade (Joana M. F. da Trindade) — Mon, 14 Apr 2008 00:29:21 GMT

A solution for the "Stack 'em Up" problem.

Problem description:
http://icpcres.ecs.baylor.edu/onlinejudge/external/102/10205.html

Author: Joana Matos Fonseca da Trindade
Date: 2008.04.05



/* 

 * Solution for "Stack 'em Up" problem.

 * UVa ID: 10205

 */

#include 



#define NVALUES 13

#define NSUITS 4

#define NCARDS 52

#define NSHUFFLES 100

#define WSIZE 9



using namespace std;



char values[NVALUES][WSIZE] = {"2", "3", "4", "5", "6", "7", "8", "9", "10", "Jack", "Queen", "King", "Ace"};

char suits[NSUITS][WSIZE] = {"Clubs", "Diamonds", "Hearts", "Spades"};

int shuffles[NSHUFFLES][NCARDS];

int deck[NCARDS];



/* read all dealer shuffles */

void read_shuffles(int n_shuff) {

	for(int i=0; i		for (int j=0; j			cin >> shuffles[i][j];

		}

	}

}



/* shuffle the deck with one of the known shuffles */

void shuffle_deck(int s_id) {

	int tmpdeck[NCARDS];

	for (int i=0; i		tmpdeck[i] = deck[shuffles[s_id][i] - 1];

	}

	for (int i=0; i		deck[i] = tmpdeck[i];

	}

}



/* main */

int main (int argc, const char *argv[]) {

	int nc; /* number of cases */

	int ns;	/* number of shuffles */

	int s; /* current shuffle */

		

	cin >> nc;

		

	for (int i=0; i		cin >> ns;

			

		/* initialize deck */

		for (int p=0; p			deck[p] = p;

		}

		

		/* read list of known shuffles */

		read_shuffles(ns);

		

		/* shuffle deck */

		for (int j=0; j			cin >> s;

			shuffle_deck(s - 1);

		}



		/* print deck */

		for (int k=0; k			cout << values[deck[k] % NVALUES] << " of " << suits[deck[k] / NVALUES] << endl;

		}

		if (i < (nc - 1)) {

			cout << endl;

		}

	}

	

}

A solution for the "Hartals" problem

jmftrindade (Joana M. F. da Trindade) — Mon, 14 Apr 2008 00:21:58 GMT

A solution for the "Hartals" problem.

Problem description:
http://icpcres.ecs.baylor.edu/onlinejudge/external/100/10050.html

Author: Joana Matos Fonseca da Trindade
Date: 2008.04.06



/* 

 * Solution for the "Hartals" problem.

 * UVa ID: 10050

 */

#include 

 

#define NDAYS 3651

 

using namespace std;



/* simulation time (in days) */

int st[NDAYS]; 

 

/* main */

int main (int argc, const char *argv[]) {

	int nc; /* number of cases */

	int nd; /* number of days */

	int np; /* number of political parties */

	int h; /* current hartal number */

	int dl;	/* days lost */

	

	cin >> nc;

	

	/* for each case.. */

	for (int i=0; i		cin >> nd;

		cin >> np;		

		

		/* initialize simulation table */

		for (int j=0; j<=nd; j++) {

			st[j] = 0;

		}

		dl = 0; /* init days lost counter */

		

		/* update with hartal for each party */

		for (int j=0; j			cin >> h;

			for (int k=1; k*h-1<=nd; k++) {

				st[k*h-1] = 1; /* set lost day flag */

			}

		}

		

		/* calculate number of days lost */

		for (int j=0; j			/* if it's not a friday or a saturday */

			if ((j%7 != 5) && (j%7 != 6) && (st[j] == 1)) {

				dl++;

			}

		}

		cout << dl << endl;

	}

	

}

Automated GNU Makefile

scvalex (Alexandru Scvortov) — Wed, 02 May 2007 17:43:36 GMT

A simple automated GNU Makefile to build and link c/c++/asm projects. All the variables that need to be tweaked are located at the begining:
PROGNAME: the name of the executable to be built
CC: the C compiler
CPP: the C++ compiler
ASM: the assambler
LD: the linker

This searches for all *.c, *.cpp and *.s files and compiles them into objects. It then links all the files into a single executable.

The strip rule is used to strip all unwanted symbols from the resulting executable. This usually results in a significant (think 40%) size optimisation.



$(VERBOSE).SILENT:



PROGNAME = prog



CC = gcc

CC += -c

CPP = g++

CPP += -c

ASM = nasm

ASM += -f elf -d ELF_TYPE

LD = g++



OBJFILES = $(patsubst %.c,%.o,$(wildcard *.c))

OBJFILES += $(patsubst %.s,%.o,$(wildcard *.s))

OBJFILES += $(patsubst %.cpp,%.o,$(wildcard *.cpp))



all: $(PROGNAME)



clean:

	@echo "Cleaning object files"

	@echo "    rm -f     *.o"

	rm -f *.o

	@echo "Cleaning backups"

	@echo "    rm -f     *~"

	rm -f *~

	@echo "Removing programme"

	@echo "    rm -f     "$(PROGNAME)

	rm -f $(PROGNAME)



%.o: %.s

	@echo "Assambling "$@

	@echo "    ASM       "$<

	$(ASM) $<



%.o: %.c

	@echo "Compiling "$@

	@echo "    CC        "$<

	$(CC) $<



%.o: %.cpp

	@echo "Compiling "$@

	@echo "    CPP       "$<

	$(CPP) $<



$(PROGNAME): $(OBJFILES)

	@echo "Linking "$@

	@echo "    LD        -o "$(PROGNAME)"        "$(OBJFILES)

	$(LD) -o $(PROGNAME) $(OBJFILES)



strip: $(PROGNAME)

	@echo "Stripping "$(PROGNAME)

	echo -n "Size of "$(PROGNAME)" before strip is "

	ls -sh $(PROGNAME) | cut -d' ' -f1

	@echo "    strip     "$(PROGNAME)

	strip $(PROGNAME)

	echo -n "Size of "$(PROGNAME)" after strip is "

	ls -sh $(PROGNAME) | cut -d' ' -f1



nothing:

	@echo "Nothing to do; quitting  :("

	@echo "HINT: Try make all"

Calling a S60 Python function from Symbian C++

frumioj (John Kemp) — Thu, 12 Apr 2007 00:38:10 GMT

Calls the Python function 'foo' in the module 'Bar'.
A string value is passed to the Python function, and a string value is returned



    TInt retVal(KErrNone);



    // Create a Python interpreter

    CSPyInterpreter* it = CSPyInterpreter::NewInterpreterL();

    CleanupStack::PushL(it);



    // Save state of any current Python interpreter, and acquire the

    // interpreter lock

    PyEval_RestoreThread(PYTHON_TLS->thread_state);



    char *module_name = "Bar" ;

    char *foo = "foo" ;

    char *response = NULL ;



    TInt32 r_len = 0 ;



    PyObject *pModule = PyImport_ImportModule(module_name) ;



    if ( pModule != NULL )

    {

    LOG_WRITE_L("CSenPythonSession::loaded ServiceConnection");



    PyObject *module_dict = PyModule_GetDict(pModule);

    PyObject *expression = PyDict_GetItemString(module_dict, pre_handler);

    PyObject *arglist = Py_BuildValue("(s#)", aString.Ptr(),aString.Length()) ;



    PyObject *result = PyEval_CallObject(expression, arglist);



    response = PyString_AsString( result ) ;



    r_len = strlen( response ) ;

    }



    // Make a Symbian descriptor pointer to the char * response

    TPtrC8 symResponse((TUint8*)response, r_len ) ;



    // Clean-up, and restore thread state



    PyEval_SaveThread();

    CleanupStack::PopAndDestroy(it);

Most elementary Win-API "Hello, 'ere I am' code

stayefeh (Sascha Tayefeh) — Sat, 07 Apr 2007 18:11:39 GMT

This does nothing but opening a window for 5 seconds. No MFC, no C#, no resources, no whatsoever...



#include 

#include



HWND NewWindow(

			   LPCTSTR str_Title,

			   int int_XPos, 

			   int int_YPos, 

			   int int_Width, 

			   int int_Height);



LRESULT CALLBACK OurWindowProcedure(

									HWND han_Wind,

									UINT uint_Message,

									WPARAM parameter1,

									LPARAM parameter2);



int WINAPI WinMain(

				   HINSTANCE hInstance,

				   HINSTANCE hPreviousInstance,

				   LPSTR lpcmdline,

				   int nCmdShow

				   )

	{

	HWND han_Window = NewWindow(_T("DirectX C++ Tutorial"),100,100,500,500);

	Sleep(5000);

	DestroyWindow(han_Window);

	return 0;

	}





HWND NewWindow(

			   LPCTSTR str_Title,

			   int int_XPos, 

			   int int_YPos, 

			   int int_Width, 

			   int int_Height)

	{



	WNDCLASSEX wnd_Structure;



	wnd_Structure.cbSize = sizeof(WNDCLASSEX);

	wnd_Structure.style = CS_HREDRAW | CS_VREDRAW;

	wnd_Structure.lpfnWndProc = OurWindowProcedure;

	wnd_Structure.cbClsExtra = 0;

	wnd_Structure.cbWndExtra = 0;

	wnd_Structure.hInstance = GetModuleHandle(NULL);

	wnd_Structure.hIcon = NULL;

	wnd_Structure.hCursor = NULL;

	wnd_Structure.hbrBackground = GetSysColorBrush(COLOR_BTNFACE);

	wnd_Structure.lpszMenuName = NULL;

	wnd_Structure.lpszClassName = _T("WindowClassName");

	wnd_Structure.hIconSm = LoadIcon(NULL,IDI_APPLICATION);



	RegisterClassEx(&wnd_Structure);



	return CreateWindowEx(

		WS_EX_CONTROLPARENT, 

		_T("WindowClassName"), 

		str_Title, WS_OVERLAPPED | WS_CAPTION | WS_SYSMENU | WS_MINIMIZEBOX | WS_VISIBLE,

		int_XPos, 

		int_YPos, 

		int_Width, 

		int_Height, 

		NULL, 

		NULL, 

		GetModuleHandle(NULL),

		NULL);

	}



LRESULT CALLBACK OurWindowProcedure(HWND han_Wind,UINT uint_Message,WPARAM parameter1,LPARAM parameter2)

	{

	return DefWindowProc(han_Wind,uint_Message,parameter1,parameter2);

	}