IOI – 2007 (Computer Olympiad)

It's only fair to share...Share on FacebookShare on Google+Tweet about this on TwitterShare on LinkedInDigg thisShare on RedditPin on PinterestPrint this pageEmail this to someone

I just found some past IOI online screening test questions and my answers. Though to share the answers here, because it might help somone out there.

These were my answers for IOI 2007 online screening test. All the answers are written using C++ (MinGW Compiler).

What is IOI:

The International Olympiad in Informatics (IOI) is one of the most recognized computer science competitions in the world. The competition tasks are of algorithmic nature; however, the contestants have to show such basic IT skills as problem analysis, design of algorithms and data structures, programming and testing. The winners of the IOI belong to the best young computer scientists in the world.

The primary goal of the IOI is to stimulate interest in informatics (computing science) and information technology. Another important goal is to bring together exceptionally talented students from various countries and to have them share scientific and cultural experiences.

http://www.ioi.lk/

INDEX

Q1 : Airport

Q2 : Diff

Q3 : Fight

Q4 : Police

Q5 : Prime

Q6 : Roads

Download ALL problems and solutions

Q1 : Airport

Question:

Infoland is a tiny island located somewhere in the pacific ocean. It is in the shape of a square, with each side being of length L. It’s top left corner is locate at the coordinates (X, Y) and the bottom right corner is located at (X+L, Y+L).

At the moment, the islanders have for their use N existing airports, some of which might be located outside the island. All these airports are located on grid points.

Since these airports are all rather old, the inhabitants want to build a new, modern airport. Like the old airports, the new one must be located on a grid point. In addition, the new airport must be located so that the sum S of the distances from the other airports to the new one is as low as possible.

Due to security reasons, aircraft can only fly parallel to the X and Y axes. Therefore when flying from one airport located at (X1,Y1) to another airport located at (X2,Y2), the total distance travelled will be abs(X1 – X2) – abs(Y1 – Y2).

For example, when flying from an Airport located at (4,5) to another located at (5,3) the total distance travelled will be abs(4 – 5) + abs(5 – 3) = 1 + 2 = 3.

You don’t need to find out where the new airport should be located (or at least, you don’t need to output that value). Instead, you have to find the value of S when the airport is built at that location.

Note that the new airport must be built inside the island and it can be built even upon one of the existing airports ( in which case the distance from the old airport to the new one would considered to be zero).

Constraints

1 ≤ L ≤ 10

0 ≤ X,Y ≤ 50

0 ≤ N ≤ 20

Input

Read your input from the standard input (keyboard)

    • The first line will contain X, Y, L and N (in that order).
      This will be followed by N lines, each containing two integers x, y: the x and y coordinates of one of the airports.

Output

Print your output to the standard output (screen)

 

  • You should print one line, containing the value of  T.

 

Sample Input   Sample Output
2 3 2 40 04 35 5

3 4 12

Solution (Click “Show Source” link)

/********************************************************/<br />/*                    IOI - Airport                     */<br />/*              By Ayoma Gayan Wijethunga               */<br />/*                 ayomapro@gmail.com                   */<br />/*                     037-2248519                      */<br />/*                                                      */<br />/*         Compiled with     Dev-C++  (4.9.9.2)         */<br />/*                  Compiler - Mingw                    */<br />/********************************************************/<br /><br />using namespace std;<br />#include<iostream><br /><br />int main()<br />{<br />    //variable that contains "x,y,l and n"<br />	int x;<br />    int y;<br />    int L;<br />    int n;<br /><br />	//array that contains "x Values of all existing airports"<br />	int* xP;<br /><br />    //array that contains "y Values of all existing airports"<br />	int* yP;<br /><br />    //array that will contain distance from all existing ariport, to each point of island<br />	int* pointToPoint;<br /><br />	    //read 'x' , 'y' , 'l' and 'n' from the user<br />    	cin>>x;<br />		cin>>y;<br />		cin>>L;<br />		cin>>n;<br /><br />		//seting the length of "xPort" and "yPort" (Described Above), acording to the Number Of Existing Airports<br />		//have used "n-1" because array begins with 0th eliment<br />		xP=new int[n];<br />		yP=new int[n];<br /><br />        pointToPoint=new int[((L+1)*(L+1))]; //seting the length of "pointToPoint" (Described Above), acording to the Length of Island<br /><br />		for(int getXYCount=0;getXYCount<n;getXYCount++)<br />		{<br />			//read locations of each existing airport<br />			cin>>xP[getXYCount];<br />			cin>>yP[getXYCount];<br />		}<br /><br />		//setting the Y and X of 1st location that can be selected to build the new airport ('bottem left' point of the island)<br />		int yMover=y;<br />		int xMover=x;<br /><br />		//variables that will contain total distance to existing airports from the selected check point<br />		int xVal=0;<br />		int yVal=0;<br /><br />		int valueCount=0;		//variable that counts the number of points checked<br /><br />      //below loop is used to nevigate through the Y asise<br />     	for(yMover;yMover<=(y+L);yMover++)<br />		{<br />			xMover=x;//to set starting X point for each Y in the loop<br /><br />			//below loop is used to nevigate through the X asise<br />			for(xMover;xMover<=(x+L);xMover++)<br />			{<br />                //setting xVal and yVal (Described Above) to zero, so that program can capture new values to it<br />				xVal=0;<br />				yVal=0;<br /><br />				for(int xPCheck=0;xPCheck<n;xPCheck++)<br />				{<br />				   //check X distance to each existing airport, fromm the current check point<br />					if((xP[xPCheck]-xMover)<0)<br />					{<br />  						//if the distance is a (-) value, program converts it into a (+) value<br />						//and adds it to 'total X distance' (xVal)<br />						xVal=xVal+((-1)*(xP[xPCheck]-xMover));<br />					}<br />					if((xP[xPCheck]-xMover)>0)<br />					{<br />						//if the distance is (+) value<br />						//program adds it to 'total X distance' (xVal), directly<br />						xVal=xVal+(xP[xPCheck]-xMover);<br />					}<br />						//cout<<"X:"<<(xP[xPCheck]-xMover)<<endl;<br />				}<br />				for(int yPCheck=0;yPCheck<n;yPCheck++)<br />				{<br />					//check Y distance to each existing airport, fromm the current check point<br />					if((yP[yPCheck]-yMover)<0)<br />					{<br />						yVal=yVal+((-1)*(yP[yPCheck]-yMover));<br /><br />					}<br />					if((yP[yPCheck]-yMover)>0)<br />					{<br />						yVal=yVal+(yP[yPCheck]-yMover);<br /><br />					}<br />						//cout<<"Y:"<<(yP[yPCheck]-yMover)<<endl;<br />				}<br />				//adds "Total Distance" ('total X distance'(xVal) + 'total Y distance'(yVal)), for current check point to the "pointToPoint" array<br />	            pointToPoint[valueCount]=xVal+yVal;<br /><br />				valueCount++;<br />				//when all the X points of current Y , is checked, this loop will end.<br />				//after that program starts checking X points of the next Y row<br />			}<br /><br />		}<br /><br />		int disMin;<br />        disMin=pointToPoint[0];<br /><br />		//below loop will go through all "Total Distances" calculated for every check point<br />		//at the end "disMin" will contain the minimum distance out of all distances<br /><br />		for(int distMinCount=0;distMinCount<((L+1)*(L+1));distMinCount++)<br />		{<br /><br />			if(pointToPoint[distMinCount]<disMin)<br />			{<br />				disMin=pointToPoint[distMinCount];<br />			}<br />		}<br />		cout<<disMin; //prints the minimum distance<br />    //int aaa;<br />	//cin>>aaa;<br />	return 0;<br />}<br />

Q2 – Diff

Question :

Prof. Calculus., an expert on inequalities, is working in a project involving rather large positive integers and frequently needs to know the difference between two such numbers. Being ignorant of the modern day computing techniques, he cannot himself devise a computer program for that. So, he wants you to write an efficient program to find the difference between two  given integers N and M.

Constraints

1 ≤ N, M ≤ 101000

 

Input

Read your input from the standard input (keyboard)

  • The First and only line contains N and M (in that order).

Output

Print your output to the standard output (screen)

  • You should print one line containing the difference between N and M.

Sample Input

1100000000000000000 1160000000000000000

Sample Output

60000000000000000

Solution (Click “Show Source” link)

<br />/********************************************************/<br />/*                     IOI - DIFF                       */<br />/*              By Ayoma Gayan Wijethunga               */<br />/*                 ayomapro@gmail.com                   */<br />/*                     037-2248519                      */<br />/*                                                      */<br />/*         Compiled with     Dev-C++  (4.9.9.2)         */<br />/*                  Compiler - Mingw                    */<br />/********************************************************/<br /><br />using namespace std;<br />#include<iostream><br /><br />int main()<br />{<br /><br />	/*<br />		**IMPORTANT**<br /><br />		10^1   --> 10   --> has 2 numbers<br />		10^2   --> 100  --> has 3 numbers<br />		10^3   --> 1000 --> has 4 numbers<br />		.........<br />		10^1000 --> has ( 1000 + 1 ) numbers<br />	*/<br /><br />	//To store 10^1000, arrays will requare 1001 eliments<br /><br />	char a[1001]; //char array that will contain the number1<br />	char b[1001]; //char array that will contain the number2<br />	int n1[1001]; //intiger array that will contain the number1<br />	int n2[1001];//intiger array that will contain the number2<br /><br />	int ans[1001]; //intiger array that will contain the answer<br /><br />	/*<br />	  **IMPORTANT**<br /><br />	  Intiger can hold only upto ((10^31)-1).<br /><br />	  So we cannot use it to store values like (10^1000)<br />	  Because of that, this program creates a char array with 101 elements and<br />	  takes each number of given values to each eliment of the array<br />	*/<br /><br />	cin>>a;<br />	cin>>b;<br /><br />	int numCount=0;<br />	while(a[numCount]!='\0')<br />	{<br /> 		//count the number of elements in char array, ""a""<br />		numCount++;<br />	}<br /><br />	int numCount1=0;<br />	while(b[numCount1]!='\0')<br />	{<br />		//count the number of elements in char array, ""b""<br />		numCount1++;<br />	}<br /><br />	/*if "b" has more elements than "a", it means that<br />	"b" (1st number) is greater than "a" (2nd number)<br /><br />	if so this function will shift "a" to "b"'s position<br />	and "b" to "a"'s position*/<br /><br />	if(numCount<numCount1)<br />	{<br />		char temp[1001];<br />		for(int shift=0;shift<numCount1;shift++)<br />		{<br />			temp[shift]=a[shift];<br />			a[shift]=b[shift];<br />			b[shift]=temp[shift];<br /><br />		}<br />		/*next  three lines will shift number of elements counted before<br />		  numCount into numCount1's position and numCount1 into numCount's position<br />		  because numbers have been shifted too */<br /><br />		int tempNumCount=numCount;<br />		numCount=numCount1;<br />		numCount1=tempNumCount;<br /><br />	}<br /><br />    //used to copy "char" arrays (a,b) into the "int" arrays (n1,n2)<br />	for(int c=0;c<numCount;c++)<br />	{<br />        //to copy "a" to "n1"<br />		n1=int(a-48);<br /><br />		/*<br />		    int(a-48)<br /><br />			returns intiger value of i{ Ascii Code of (a) - 48  }<br /><br />			eg:-<br /><br />			 if a was 5<br /><br />			 output = int(Ascii(5)-48)<br />			        = int(53-48)<br />					= 5<br /><br />		*/<br />	}<br />	for(int d=0;d<numCount1;d++)<br />	{<br />		//To copy "b" to "n2"<br />		//Techniqe is same as above code<br />		n2[d]=int(b[d]-48);<br />	}<br /><br />	//if element count  of both numbers are equal, program has to check for the largest value<br />	char chkNMax[1001];<br />	if(numCount==numCount1)<br />	{<br />		for(int chkN=0;chkN<numCount;chkN++)<br />		{<br />            //this loop will compare the values of both numbers from the beginig to the end<br /><br />			if(n1[chkN]==n2[chkN])<br />			{<br />				chkNMax[chkN]='E';<br />			}<br />			else if(n1[chkN]>n2[chkN])<br />			{<br />				chkNMax[chkN]='F';<br />			}<br />			else<br />			{<br />				chkNMax[chkN]='S';<br />			}<br />		}<br /><br />		//chkNMax is having a pattern built with "E" (Equal) ,"F" (Fist is Larger) and "S" (Secod is Larger)<br /><br />		for(int expNMax=0;expNMax<numCount;expNMax++)<br />		{<br />			//check the previously built pattern<br />			/*<br />				eg:<br /><br />					1285     1285<br />					1274     1275<br />					----     ----<br />					EELS     EESS<br />					====     ====<br /><br />					while checking the loop from the begining, if program found "E" value, program cannot<br />					decide which value is the largest, so program will continue checking<br /><br />					when it detects a "L" FOR HHE 1st TIME, program will goto the "if" statement labeled "**NUMBER 1**"<br />					when it detects a "L" FOR THE 1st TIME, program will goto the "if" statement labeled "**NUMBER 2**"<br /><br />			*/<br /><br />			//cout<<chkNMax[expNMax]<<endl;<br />			if (chkNMax[expNMax]=='F')<br />			{<br />                //**NUMBER 1**<br /><br />				break;<br />				//if first value was larger then the "n1" is larger than "n2"<br />				//there is no need to change any value,, so just break the loop<br />				//please read the below lines also to get a better understanding about this<br /><br />			}<br /><br />			else if(chkNMax[expNMax]=='S')<br />			{<br />				//**NUMBER 2**<br /><br />				//if second value was larger then the "n2" is larger than "n1"<br />				//inverse the values of char arrays<br /><br />				char temp1[1001];<br />				for(int shift1=0;shift1<numCount1;shift1++)<br />				{<br />					temp1[shift1]=a[shift1];<br />					a[shift1]=b[shift1];<br />					b[shift1]=temp1[shift1];<br /><br />				}<br /><br />				//inverse the values of numCount<br />				//(have described above)<br /><br />				int tempNumCount1=numCount;<br />				numCount=numCount1;<br />				numCount1=tempNumCount1;<br /><br />				//coppy char array to the int array<br />				//have described above<br /><br />				for(int c=0;c<numCount;c++)<br />				{<br />					n1=int(a-48);<br />				}<br />				for(int d=0;d<numCount1;d++)<br />				{<br />					n2[d]=int(b[d]-48);<br />				}<br />                //now "n1" is larger than "n2" for sure,, so just break the loop<br />				break;<br />			}<br />			else if(chkNMax[expNMax]=='E')<br />			{<br />					//if the values are equal, program has to check next cupple of values to decide<br />					//which value is larger. So loop will continue to check the next value, without making any changes.<br />			}<br />		}<br /><br />	}<br /><br />		/*if "a" has more elements than "b",<br /><br />				  eg:<br /><br />					1258<br />					123<br />					----<br /><br />		  it is dificult to compart two values. so this function arranges the values in propper order<br />		*/<br /><br />	if (numCount>numCount1)<br />	{<br />		int an1=numCount; //duplicate of numCount<br />		int an2=numCount1; //duplicate of numCount1<br />		int dropCount=1;<br />		int equChk=0;<br />		for(;an2>equChk;) //Loop until both numbers get same number of elements<br />		{<br />			//shift the last value of intNun2 to the position under intNun1's last position<br />			n2[an1-dropCount]=n2[an2-dropCount];<br />			dropCount++;<br />			equChk++;<br />		}<br />			/*<br />				now above example values will look like this<br /><br />				1258<br />				1123<br />				----<br /><br />			*/<br /><br />		//this loop will look for leftouts and empty elements in array intNun2, and fill them with zero(s)<br />		for(int toZero=0;(numCount-numCount1)>toZero;toZero++)<br />		{<br />			n2[toZero]=0;<br />		}<br />		/*<br />			now above example values will look like this<br /><br />				1258<br />				0123<br />				----<br />		*/<br /><br />		//numbers have completly shifted and arranged<br />	}<br /><br />	int ansCount=0;<br />	int doneCount=0;<br />	int skipCount=0;<br /><br />	for(int g=numCount-1;g>=0;g--)<br />	{<br />		//start substracting from the end of both numbers<br /><br />		if(n1[g]>=n2[g])<br />		{<br /> 			//if "n1" is larger or equal to "n2" program can directly substract "n1" from "n2".<br />			//It stores the answer into the array, ans (from the begining of the array)<br />			//So answer will be written to the array in reverse order (for now).<br /><br />			ans[ansCount]=n1[g]-n2[g];<br />			ansCount++; //increase the count of answers calculater completly<br />		}<br />		if(n1[g]<n2[g])<br />		{<br /> 			//if "n1" is smaller<br />			for(int m=(numCount-doneCount)-2;m>=0;m--)<br />			{<br /><br />				if(n1[m]!=0)<br />				{<br />					/*<br />							  eg:<br /><br />								  12576<br />								  00069<br />								  -----<br /><br />						normally in substract we bring substract 1 from 7, and add 10 to 6 to do the ferther calculation<br />						same as that<br />					*/<br /><br />					n1[m]=n1[m]-1;<br />					n1[m+(1+skipCount)]=n1[m+(1+skipCount)]+10;<br /><br />					ans[ansCount]=n1[g]-n2[g];<br />					ansCount++;<br /><br />					for(int red=skipCount;red>0;red--)<br />					{<br /> 							/*if skipCount is more than zero, it means that program has found<br />							  zero values in the right side while trying to do the above described process<br />							  (see the else part below for more information)<br /><br />								so program will set all those zeros found to 9<br /><br />								eg<br /><br />								1 2 0 0 6        into        1 1 9 9 (16)<br />								0 0 0 6 9                    0 0 0 6  9<br />							*/<br /><br />						n1[m+red]=9;<br />					}<br />					m=m+skipCount;<br />					skipCount=0; //sets skipCout to zero for further use<br />					break;<br />				}<br />				else<br />				{<br />						/*<br />						if program found zero, when it tries to substract one from the right side value<br /><br />							  eg:<br /><br />								  12006<br />								  00069<br />								  -----<br /><br />						program will increase skipCount by one and it'll continue looking for a value not equal to<br />						zero. If it could find, program will go to the above "if" statement<br />						*/<br />					skipCount++;<br />				}<br />			}<br /><br />		}<br />		doneCount++;<br />	}<br />		int foundFirstNum=0;<br />		// this loop prints the values in array "ans" in reverse order,<br />		// because the ansers were store in reverse order too.<br />		for(int resultCount=ansCount-1;resultCount>=0;resultCount--)<br />		{<br /> 			//followin "if" is used to locate the begining of values in the answer<br />			//otherwise it will print zeros infront of the answer, if there were any.<br />			if((ans[resultCount]==0)&&(foundFirstNum==0))<br />			{<br />			}<br />			else<br />			{<br />				foundFirstNum=1;<br />				cout<<ans[resultCount];<br />			}<br />		}<br />		//if difference between two numbers was 0<br />        if(foundFirstNum==0)<br />        {<br />           cout<<"0";<br />        }<br />       // int asddd;<br />       // cin>>asddd;<br />	return 0;<br />}<br /><br />

Q3 – Fight

Question :

A long time ago, in a galaxy not so far away, there was a planet where the people were always fighting over the land. Since there were no laws and (obviously) no police, when a pair of people fought each other, it was the relative strength of the combatants that decided the outcome of a fight. In fact (just like in real life) the stronger person always won such fights. These fights over land are continuing to the present day.

There are N persons living on the planet, each of whom is identified by a distinct ID number from 1 to N. In addition, each person has a strength S, with no two people having the same strength.

There are M fights going on. Given the strengths of all the people and the ID numbers of the pairs engaged in a fight, write a program to determine the winner of each fight.

Constraints

2 ≤ N ≤ 1000

1 ≤ M ≤ 1000

1 ≤ S ≤ 2000

Input

Read your input from the standard input (keyboard)

    • The first line would contain N and M (in that order).
    • This will be followed by N numbers, one on each line, giving the strengths S of the persons, in numerical order of their ID numbers.
    • Finally, M pairs of integers, corresponding to the ID numbers of the pairs fighting each other, will be entered with each pair being on a separate line.

Output

Print your output to the standard output (screen)

    • You should print M lines, each containing the ID number of the winner of the corresponding fight (in the same order as given in the input).
Sample Input   Sample Output
6 41850335075

520

21

1 2

3 5

5 1

3 4 1513

Solution (Click “Show Source” link)

<br />/********************************************************/<br />/*                     IOI - Fight                      */<br />/*              By Ayoma Gayan Wijethunga               */<br />/*                 ayomapro@gmail.com                   */<br />/*                     037-2248519                      */<br />/*                                                      */<br />/*         Compiled with     Dev-C++  (4.9.9.2)         */<br />/*                  Compiler - Mingw                    */<br />/********************************************************/<br /><br />using namespace std;<br />#include<iostream><br />class fight<br />{<br />	public:<br /><br />	int n;  //variable that contains "Number of Persons" (N)<br />	int m;  //variable that contains "Number of Fights" (M)<br /><br />	int* s;  //variable that contains "Strenghts of Each Person"<br />	int* f1; //variable that contains "1st One's ID of Each Fighting Cupple"<br />	int* f2; //variable that contains "2nd One's ID of Each Fighting Cupple"<br /><br />	void accept()<br />	{<br />		cin>>n; //read "Number of Persons" (N) from the user into variable "n"<br />		cin>>m; //read "Number of Fights" (M) from the user into variable "m"<br /><br />		s=new int[n]; //seting the size of "s" array according to the "Number of Persons" (N)<br />		f1=new int[m]; //seting the size of "f1" array according to the "Number of Fights" (M)<br />    	f2=new int[m];   //seting the size of "f2" array according to the "Number of Fights" (M)<br /><br />		for(int feedCountS=0;feedCountS<n;feedCountS++)<br />		{<br />			cin>>s[feedCountS]; 	//read "Strenghts of Each Person" into variable array, "s"<br />			//cout<<"a-"<<s[feedCountS]<<endl;<br /><br />		}<br /><br />		for(int feedCountF=0;feedCountF<m;feedCountF++)<br />		{<br />			cin>>f1[feedCountF]; //read "1st One's ID of Each Fighting Cupple" into array "f1"<br />			cin>>f2[feedCountF]; //read "2nd One's ID of Each Fighting Cupple" into array "f2"<br />			//cout<<"b-"<<f1[feedCountF]<<f2[feedCountF]<<endl;<br />		}<br /><br />	}<br />	void checkWinner()<br />	{<br />		for(int fightCount=0;fightCount<m;fightCount++)<br />		{<br />			//search the stronger person of Each Fighting Cupple<br />			//fightCount will reach form 0 to M (Number of fights)<br />			//cout<<"in 1st loop"<<endl;<br /><br />			if(  s[f1[fightCount]-1]  >  s[f2[fightCount]-1]  )<br />			{<br />				/*f1[fightCount] will give the "1st One's ID of Each Fighting Cupple"<br />				  f1[fightCount]-1 is used because integer array begins from 0<br />				  s(f1[fightCount]-1) will give the strength of 1st Fighter<br /><br />				  same as that s(f2[fightCount]-1)  will give 2nd Fighters Strength<br /><br />				  "if" statement will compare those two strengths, and print the winneing persons ID<br />				 */<br /><br />				//if the 1st fighter is stronger, program will execute this part<br /><br />				 //cout<<"1-"<<fightCount<<","<<f1[fightCount]-1<<","<<s[f1[fightCount]-1]<<endl;<br />				 //cout<<"2-"<<fightCount<<","<<f2[fightCount]-1<<","<<s[f2[fightCount]-1]<<endl;<br /><br />				if(fightCount!=(m-1))<br />				{<br />					cout<<f1[fightCount]<<endl;<br />				}<br />				else<br />				{<br />					cout<<f1[fightCount];<br />				}<br /><br />			}<br />			else<br />			{<br />				// cout<<"3-"<<fightCount<<","<<f1[fightCount]-1<<","<<s[f1[fightCount]-1]<<endl;<br />				 //cout<<"4-"<<fightCount<<","<<f2[fightCount]-1<<","<<s[f2[fightCount]-1]<<endl;<br /><br />				 if(fightCount!=(m-1))<br />				{<br /><br />					cout<<f2[fightCount]<<endl;<br />				}<br />				else<br />				{<br /><br />					cout<<f2[fightCount];<br />				}<br />			}<br />		}<br />	}<br /><br />};<br />int main()<br />{<br />	fight fightObj;<br /><br />	fightObj.accept();<br />	fightObj.checkWinner();<br /><br />	return 0;<br />}<br /><br />

Q4 – Police

Question :

Recently, crime has become a headache for the people on a planet far away from the earth. Therefore, they want to form a police force. Initially they would like to recruit  the oldest five persons to the force.

In that strange planet inhabitants can live up to 10000 years and in addition, no two of them  happen to be of the same age. Each person in the planet has a  unique(different) ID  number which lies between 1 and  N (N being the total number of persons).

Since there are so many people in that planet, they are finding it very difficult to determine the five oldest persons. You need to help them by writing a program to do this.

Constraints

1 ≤ N ≤ 10000

 

Input

Read your input from the standard input (keyboard).

    • The first line of the input will contain N.
    • This will be followed by N lines, each containing the age of a person. The ages will be given in ascending order of the ID numbers.

Output

Print your output to the standard output (screen).

 

  • You should print five lines, with each line containing the ID number of a person selected. The ID numbers should be given in decreasing order of the ages.

 

Sample Input   Sample Output
1010320100

50

11

15

25

60

75 410958

Solution (Click “Show Source” link)

<br />/********************************************************/<br />/*                    IOI - Police                      */<br />/*              By Ayoma Gayan Wijethunga               */<br />/*                 ayomapro@gmail.com                   */<br />/*                     037-2248519                      */<br />/*                                                      */<br />/*         Compiled with     Dev-C++  (4.9.9.2)         */<br />/*                  Compiler - Mingw                    */<br />/********************************************************/<br /><br />using namespace std;<br />#include<iostream><br />class police<br />{<br />	public:<br /><br />	int n;		//variable that contains "Number of Persons" (N)<br />	int* age;	//variable that contains "Each Persons Age"<br /><br />	int* duplicate; //variable that stores a "duplicate" of intiger array "age"<br /><br />	void accept()<br />	{<br />		cin>>n;		//read "Number of Persons" (N) from the user into variable "n"<br /><br />        //Check weather values are in the Constraints given<br />        if((n<1)||(n>10000))<br />        {<br />         cout<<"Values are out of Constraints. Cannot continue";<br />         exit(0);<br />        }<br /><br />		age=new int[n-1];			//seting the size of "age" array according to the "Number of Persons" (N)<br />		duplicate=new int[n-1]; 	//seting the size of "duplicates" array according to the "Number of Persons" (N)<br /><br />		for(int getAgeCount=0;getAgeCount<n;getAgeCount++)<br />		{<br />			cin>>age[getAgeCount];	//read "Age of Each Person" into array, "age"<br />		}<br />	}<br />	void createDuplicate()<br />	{<br />		//create a duplicate of array, "age"<br />		for(int dupCount=0;dupCount<n;dupCount++)<br />		{<br />			duplicate[dupCount]=age[dupCount];<br />		}<br />	}<br />	void ageSorter()<br />	{<br />		//sort the ages in the "duplicate" in decreasing order<br /><br />		int sorterCount=0;<br />		while(sorterCount<n-1)<br />		{<br />			int temp;<br />			if(duplicate[sorterCount]<duplicate[sorterCount+1]) 	//if 1st value is smaller than 2nd<br />			{<br />					temp=duplicate[sorterCount]; 					//assigning value of "duplicate" to temp<br /><br />					duplicate[sorterCount]=duplicate[sorterCount+1]; //shift the 2nd value to the 1st value's position<br />					duplicate[sorterCount+1]=temp;					 //shift temp's valu into 2nd value's position<br />					sorterCount=0;<br />					continue;<br /><br />					/*break the loop without increasign the "sorterCount"<br />					so loop will check values from the begining again*/<br />			}<br />			sorterCount++;<br /><br />			//exit from the loop, if duplicate array is completly in "decreasing order"<br />		}<br />	}<br />	void grabLargestFive()<br />	{<br />		/*get the top 5 from sorted, "duplicate" array,<br />		  search for the top 5 ages in, unsorted "age" array<br />		  and print their ID to the screen*/<br /><br />		for(int grabCount=0;grabCount<5;grabCount++)<br />		{<br />			for (int ageFinderCount=0;ageFinderCount<n;ageFinderCount++)<br />			{<br />				if(grabCount!=4)<br />				{<br />					/*if this is not 5th person (4th eliment of the loop)<br />					line break will placed by using "endl"*/<br />					if(duplicate[grabCount]==age[ageFinderCount])<br />					{<br /><br />						cout<<ageFinderCount+1<<endl;<br />					}<br />				}<br />				else<br />				{<br />					/*if this is 5th person (4th eliment of the loop)<br />					line break will NOT placed, because,<br />					if so program prints "m+1" lines*/<br /><br />					if(duplicate[grabCount]==age[ageFinderCount])<br />					{<br />						cout<<ageFinderCount+1;<br />					}<br />				}<br />			}<br />		}<br />	}<br /><br />};<br />int main()<br />{<br />	police policeObj;	//Create an Object for "police" Class<br /><br />	policeObj.accept();				//Execute accept() method of "policeObj" Object<br />	policeObj.createDuplicate();	//Execute createDuplicate() method of "policeObj" Object<br />	policeObj.ageSorter();			//Execute ageSorter() method of "policeObj" Object<br />	policeObj.grabLargestFive();	//Execute grabLargestFive() method of "policeObj" Object<br /><br />	return 0;<br />}<br /><br />

05 – Prime

Question:

Prof. Calculus (the expert on inequalities) has failed to solve the  research problem that he was working on recently. So, he has now shifted to another problem, that of  investigating patterns of prime factors and he wants you to develop a computer program to calculate all the prime numbers which are  factors of a given integer N.

If a certain prime is a repeated factor of N (for example 20 = 2 x 2 x 5) you should only print it once.

Constraints

1 ≤ N ≤ 1000

Input

Read your input from the standard input (keyboard).

 

  • The first line of the input will contain N.

 

Output

Print your output to the standard output (screen).

    • The first line should give M:  the number of prime factors of N.
    • The next M lines should give the prime factors in ascending order.
Sample Input   Sample Output
60   3235

Solution (Click “Show Source” link)

<br />/********************************************************/<br />/*                     IOI - Prime                      */<br />/*              By Ayoma Gayan Wijethunga               */<br />/*                 ayomapro@gmail.com                   */<br />/*                     037-2248519                      */<br />/*                                                      */<br />/*         Compiled with     Dev-C++  (4.9.9.2)         */<br />/*                  Compiler - Mingw                    */<br />/********************************************************/<br /><br />using namespace std;<br />#include<iostream><br />class prime<br />{<br />	public:<br /><br />	int n;		//variable that contains "Number" (N)<br />	int* pri;	//variable that contains a list of "Prime Numbers"<br /><br />	int* res;	//variable that contains "The List Of Prime Factors" of the given number<br /><br />	int priCount;<br />	int priActualCount;<br /><br />	int resCount;<br /><br />	void accept()<br />	{<br />		cin>>n;			//read "Number" (N) from the user into variable "n"<br /><br />        //Check weather values are in the Constraints given<br />        if((n<1)||(n>1000))<br />        {<br />         cout<<"Values are out of Constraints. Cannot continue";<br />         exit(0);<br />        }<br /><br />		pri=new int[n];	//seting the size of "pri" array according to the "Number" (N)<br />						//Because largest prime factor for number "n" will be, number "n" itself,<br />	}<br />	void listPrimeNums()<br />	{<br />		//creates a list of all prime numbers between 0 and n (including "n" if it's a prime number)<br /><br />		priCount=0;<br />		priActualCount=0;<br /><br />		for(int listPrimeN1=2;listPrimeN1<=n;listPrimeN1++)<br />		{<br />			//check weather each listPrimeN1 value is a prime number<br /><br />			for(int listPrimeN2=2;listPrimeN2<10;listPrimeN2++)//loop from 2 to 9<br />			{<br />				if( ((listPrimeN1%listPrimeN2) != 0) && (listPrimeN1!=listPrimeN2) )<br />				{<br />					//if listPrimeN1 and listPrimeN2 is not same and<br />					//listPrimeN1 =! listPrimeN2 loop will increace "priCount" by one<br /><br />					//if listPrimeN1 is a prime number,, it shuldn't be devided by any other value from 2 to 9<br />					//(excluding the same value)<br /><br />					/*in the first round this will do following<br /><br />						2/2 --> ignored by "if"<br />						2/3 --> increace "priCount"<br />						2/4 --> increace "priCount"<br />						2/5 --> increace "priCount"<br />						2/6 --> increace "priCount"<br />						2/7 --> increace "priCount"<br />						2/8 --> increace "priCount"<br />						2/9 --> increace "priCount"<br /><br />					*/<br /><br />					priCount++;<br />				}<br />			}<br /><br />			if((priCount==7)&&(listPrimeN1<10))<br />			{<br /><br />				//if the value program is going to check is less than 10, that number will be<br />				//devided by the same number. (As in above example).<br /><br />				//so if the value program is going to check is less than 10<br />				//and if it is a prime number,, the "priCount" must have value "7"<br /><br />				pri[priActualCount]=listPrimeN1; //adding listPrimeN1 to the prime number list id it is a prime number<br />				priActualCount++;				 //increase the found primary number count<br /><br />				priCount=0;						//setting "priCount" to zero. so it can be used to check the next listPrimeN1<br /><br />			}<br />			else if((priCount==8)&&(listPrimeN1>=10))<br />			{<br /><br />				//if the value program is going to check is greater than or equal to 10, that number will<br />				//NOT be devided by the same number.<br /><br />				//and if it is a prime number,, the "priCount" must have value "8"<br /><br />				pri[priActualCount]=listPrimeN1;	//adding listPrimeN1 to the prime number list id it is a prime number<br />				priActualCount++;					//increase the found primary number count<br /><br />				priCount=0;		//setting "priCount" to zero. so it can be used to check the next listPrimeN1<br />			}<br />			else<br />			{<br />				//it means that listPrimeN1 is not a prime number<br />				//so program will NOT add that value to the prime number list<br /><br />				priCount=0;		//setting "priCount" to zero. so it can be used to check the next listPrimeN1<br />			}<br /><br />			//Loop will end after repeating for 'n' number of times<br />			//at the end of the loop array "pri" will contain all the prime values from 1 to "n"<br />			//(including 'n' , if it is a prime number)<br />		}<br />	}<br /><br />	void checkNumForPrimeFactors()<br />	{<br />		//check the given number "n", for primary factors<br /><br />		res=new int[priActualCount];	//seting the size of "res" array (result list) according to the "Number of Primes Found"<br /><br />		resCount=0;						//number of primary factors found<br />		for(int checkCount=0;checkCount<priActualCount;checkCount++)<br />		{<br />			if((n%pri[checkCount])==0)<br />			{<br />				//devides given number from each "prime" number found<br />				//if the reminder is equal to zero. that prime number is a factor of, given number<br /><br />				res[resCount]=pri[checkCount];	//add prime number to the "result list" if it's a factor of given number<br />				resCount++;						//increase number of primary factors found<br />			}<br />		}<br />	}<br /><br />	void display()<br />	{<br />		cout<<resCount;			//display the number of prime factors in the "result list"<br />		for(int displayCount=0;displayCount<resCount;displayCount++)<br />		{<br />			//display each prime factor in "result list"<br />			cout<<endl<<res[displayCount];<br />		}<br /><br />	}<br /><br />};<br />int main()<br />{<br /><br />	prime primeObj;				//Create an Object for "prime" Class<br /><br />	primeObj.accept();			//Execute accept() method of "primeObj" Object<br />	primeObj.listPrimeNums();	//Execute listPrimeNums() method of "primeObj" Object<br />	primeObj.checkNumForPrimeFactors();	//Execute checkNumForPrimeFactors() method of "primeObj" Object<br />	primeObj.display();			//Execute display() method of "primeObj" Object<br /><br />	return 0;<br />}<br /><br />

Q6 – Roads

Question :

The  people of a small developing country want to build a highway that runs through their country in a straight line from east to west. In addition, once this is done, they will build small roads going out from their factories to the highway. These small roads will run in a direction perpendicular to that of the highway.

All the factories are placed at grid points and the highway should also be placed along a  grid line.

The highway should be constructed so that the sum of the distances from the highway to all factories is as low as possible.

You are not required to find the best possible position for the highway, but you are required to find the sum of the distances when the highway is built at the best position.

You must follow  the following rules:

 

  • If a small road from a factory (A) to the highway goes through another factory (B) then there is no need to consider another road from B to the highway.
  • The highway itself may pass through any number of factories (in which case the distance from the factory to the highway is considered as being zero).
  • Two shopping malls or factories may have the same location.

 

There are N factories in total.

Constraints

1 ≤ N ≤ 1000

0 ≤ x and y coordinates of a factory ≤ 100

Input

Read your input from the standard input (keyboard).

 

  • The first and only line of the input will contain N.
  • This will be followed by N lines, each giving respectively  x and y, the grid coordinates of a factory.

 

Output

Print your output to the standard output (screen).

 

  • The first line and only line should give the sum of the distances when the highway is built at the best position.

 

Sample Input   Sample Output
54 82 13 21 9

5 5 14

Solution (Click “Show Source” link)


<br />/********************************************************/<br />/*                    IOI - Roads                       */<br />/*              By Ayoma Gayan Wijethunga               */<br />/*                 ayomapro@gmail.com                   */<br />/*                     037-2248519                      */<br />/*                                                      */<br />/*         Compiled with     Dev-C++  (4.9.9.2)         */<br />/*                  Compiler - Mingw                    */<br />/********************************************************/<br /><br />using namespace std;<br /><br />#include<iostream><br />class roads<br />{<br />	public:<br /><br />	int n;		//variable that contains "n" (Number of factories)<br />	int* x;		//variable that contains X value of each factory<br />	int* y;		//variable that contains Y value of each factory<br /><br />	int* dist;	//total distance from all factories to the highway ((for each Y))<br /><br />	int yMax;	//Maximum value of Y<br /><br />	int* sameX;	//Y values of factories having same X values<br /><br />	int* operatedX; //X values that has been trapped,to have multipal factories<br /><br />	void accept()<br />	{<br />		cin>>n;	//accept the n (number of factories)<br /><br />        //Check weather values are in the Constraints given<br />        if((n<1)||(n>1000))<br />        {<br />         cout<<"Values are out of Constraints. Cannot continue";<br />         exit(0);<br />        }<br /><br />		x=new int[n]; //set the length of X array according to the n (number of factories)<br />		y=new int[n]; //set the length of Y array according to the n (number of factories)<br /><br />		for(int get=0;get<n;get++)<br />		{<br />			//accept x and y of each factory<br />			cin>>x[get];<br />			cin>>y[get];<br />		}<br /><br />		sameX=new int[n];<br /><br />		dist=new int[n];<br />	}<br /><br />	void getYMax()<br />	{<br />		//This method is used to obtain the given larges Y value<br />		yMax=y[0];<br />		for(int yMaxCount=0;yMaxCount<n;yMaxCount++)<br />		{<br />			if(y[yMaxCount]>yMax)<br />			{<br />				yMax=y[yMaxCount];<br />			}<br />		}<br />	}<br /><br />	void calculateForEachY()<br />	{<br />		for(int hw=0;hw<=yMax;hw++)<br />		{<br /><br />			//check the best position for the highway (hw)<br />			//by retrieve the distance to all factories from each Y<br /><br />			dist[hw]=0;<br /><br />			int sameXMover=0;<br />			int sameXCount=0;<br /><br />            operatedX=new int[n];<br /><br />			int sameLargestY=0;<br />			int sameSmallestY=0;<br /><br />			int xOkCount=0;<br />			int opXCount=0;<br /><br />			int brk=0;	//used to break Loops when requared<br />			int yu=0;<br /><br />			for(int yDis=0;yDis<n;yDis++)//this loop acts on each factory<br />			{<br /><br />				if(yu>0)<br />				{<br /><br />					for(int opXChk=0;opXChk<(yu);opXChk++)<br />					{<br />							if(x[yDis]==operatedX[opXChk])<br />							{<br />								//if current X has been trapped as a line containing more than one factories<br />								//the current loop will break and go to, "if" statement below<br />								brk=1;<br />								break;<br />							}<br />					}<br />				}<br />				if(brk==1)<br />				{<br />					//used to skip the containt below and to repeat the loop again for the next facctory<br />					brk=0;<br />					continue;<br />				}<br /><br />				xOkCount=0;<br />				sameXCount=0;<br /><br />				//check weather there is any other factory having same X<br />				for(int chkX1=0;chkX1<n;chkX1++)<br />				{<br />					//current factory's X will get compared with X of each factory(except the same factory)<br /><br />					if((x[yDis]!=x[chkX1])&&(yDis!=chkX1))<br />					{<br />						xOkCount++; //increased if X of current factory is not equal to the X of second factory<br />					}<br />					if((x[yDis]==x[chkX1])&&(yDis!=chkX1))<br />					{<br />						//if there is any other factory having same X<br />						//the current factory's X will get stored in "sameX[sameXCount]"<br />						//and the other factories X will get stored in sameX[sameXCount+1]<br /><br />						sameX[sameXCount]=y[yDis];<br />						sameX[sameXCount+1]=y[chkX1];<br /><br />						sameXCount=sameXCount+2;<br />					}<br />				}<br /><br />				//if X of current factory is not equal to the X of any factory<br />				if(xOkCount>=(n-1))<br />				{<br /><br />					if((y[yDis]-hw)>0)<br />					{<br />						//if distance is a (+) value, program adds it to the dist[hw]  (total distance from factories to currenly selected Y)<br />						dist[hw]=(dist[hw])+(y[yDis]-hw);<br /><br />					}<br />					else if((y[yDis]-hw)<0)<br />					{<br />						//if distance is a (-) value, it'll be converted in to a (+) value. Then<br />						//program adds it to the dist[hw]  (total distance from factories to currenly selected Y)<br />						dist[hw]=(dist[hw])+((-1)*(y[yDis]-hw));<br /><br />					}<br />					else<br />					{<br />						//if factory is in the currenly selected Y. Distance to that factory is "0"<br />						dist[hw]=(dist[hw]);<br /><br />					}<br /><br />					//ignore the below content and start the loop agarin for the new factory<br />					continue;<br />				}<br /><br />				//if X of current factory is euqal to some other's X(s)<br />				if(xOkCount<(n-1))<br />				{<br />					int equals=(((sameXCount))/2);  //number of equal factries, current factory has (considering only X)<br /><br />							// get the largest Y value, between all the factories that has same X value<br />							sameLargestY=sameX[0];<br />							for(int sameLargestYCount=0;sameLargestYCount<(sameXCount);sameLargestYCount++)<br />							{<br />								if(sameX[sameLargestYCount]>sameLargestY)<br />								{<br />									sameLargestY=sameX[sameLargestYCount];<br />								}<br />							}<br /><br />							// get the smallest Y value, between all the factories that has same X value<br />							sameSmallestY=sameX[0];<br />							for(int sameSmallestYCount=0;sameSmallestYCount<(sameXCount);sameSmallestYCount++)<br />							{<br />								if(sameX[sameSmallestYCount]<sameSmallestY)<br />								{<br />									sameSmallestY=sameX[sameSmallestYCount];<br />								}<br />							}<br /><br />							//if factories are located on the same side of the highway<br />							if(((sameLargestY-hw)>0) && ((sameSmallestY-hw)>0))<br />							{<br />								//only add the distance to the LargestY<br />								dist[hw]=dist[hw]+(sameLargestY-hw);<br /><br />							}<br />							if(((sameLargestY-hw)<0) && ((sameSmallestY-hw)<0))<br />							{<br />								//only add the distance to the SmallestY<br />								dist[hw]=dist[hw]+((-1)*(sameSmallestY-hw));<br /><br />							}<br /><br />							//if factories are located on each side of the highway<br />							if(((sameLargestY-hw)>0) && ((sameSmallestY-hw)<0))<br />							{<br />								//adds both distances (to SmallestY and to LargestY)<br />								dist[hw]=dist[hw]+(-1)*(sameSmallestY-hw)+(sameLargestY-hw);<br /><br />							}<br /><br />							//if LargestY is located on the highway (current Y)<br />							if(((sameLargestY-hw)==0) && ((sameSmallestY-hw)<0))<br />							{<br />								//adds only the distance to SmallestY<br />								dist[hw]=dist[hw]+(-1)*(sameSmallestY-hw);<br /><br />							}<br /><br />							//if SmallestY is located on the highway (current Y)<br />							if(((sameLargestY-hw)>0) && ((sameSmallestY-hw)==0))<br />							{<br />								//adds only the distance to LargestY<br />								dist[hw]=dist[hw]+(sameLargestY-hw);<br /><br />							}<br /><br />						if(equals>0)<br />						{<br />							//creates a list of X values that has been trapped as a line containing multipal factories.<br />							//Total distance to the highway for that X is catculated,so other factories shuld get ignored<br />							operatedX[yu]=(x[yDis]);<br />							yu++;<br /><br />						}<br /><br />				}<br /><br />			}<br />			//distance form all factories to current Y has been calculeted.<br />			//Program shifts to the next Y value and check the total distance again, until loop comes to the Largest Y<br /><br />		}<br />	}<br /><br />	void getMinDistance()<br />	{<br />		//this  method will find the array "dist" for the smallest value<br /><br />		int disMin=dist[0];<br />		for(int distMinCount=0;distMinCount<=yMax;distMinCount++)<br />		{<br /><br />			if(dist[distMinCount]<disMin)<br />			{<br />				disMin=dist[distMinCount];<br /><br />			}<br />		}<br />		cout<<disMin; //print the value<br /><br />	}<br />};<br />int main()<br />{<br />	roads roadsObj; //create the object for the class<br /><br />	roadsObj.accept();<br />	roadsObj.getYMax();<br />	roadsObj.calculateForEachY();<br />	roadsObj.getMinDistance();<br /><br />	///***please go to the related function, for more information ***///<br /><br />	return 0;<br />}<br /><br />

Download ALL problems and solutions

It's only fair to share...Share on FacebookShare on Google+Tweet about this on TwitterShare on LinkedInDigg thisShare on RedditPin on PinterestPrint this pageEmail this to someone

Leave a Reply

Your email address will not be published.

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">