February 2016 – Live with passion

Fair Work Load [Top Coder]

Asif NaeemFebruary 25, 2016

This problem was used for: (@ Top coder) Single Round Match 169 Round 1 – Division I, Level Two Single Round Match 169 Round 1 – Division II, Level Three Problem Link

class FairWorkload{
	public:
	int getMostWork(vector<int> folder,int worker)
	{
		int n = folder.size();
		int lw = *max_element(folder.begin(),folder.end());
		int hi = accumulate(folder.begin(),folder.end(),0);
		int mid_load;
		int req_workers=1;
		int cur_load;
		if(worker==1)
		return hi;
		while(lw<hi)
		{
			mid_load = (lw+hi)/2;
			cur_load=0;
			req_workers=1;
			for(int i=0;i<n;i++)
			{
				if(cur_load+folder[i]<=mid_load)
				{
					cur_load += folder[i];
				}
				else
				{
					cur_load=folder[i];
					req_workers += 1;
				}
			}
			if(req_workers<=worker)
			hi = mid_load;
			else if(req_workers>worker)
			lw=mid_load+1;
		}
		return hi;
	}
};

class FairWorkload{

public:

int getMostWork(vector<int> folder,int worker)

{

int n = folder.size();

int lw = *max_element(folder.begin(),folder.end());

int hi = accumulate(folder.begin(),folder.end(),0);

int mid_load;

int req_workers=1;

int cur_load;

if(worker==1)

return hi;

while(lw<hi)

{

mid_load = (lw+hi)/2;

cur_load=0;

req_workers=1;

for(int i=0;i<n;i++)

{

if(cur_load+folder[i]<=mid_load)

{

cur_load += folder[i];

}

else

{

cur_load=folder[i];

req_workers += 1;

}

if(req_workers<=worker)

hi = mid_load;

else if(req_workers>worker)

lw=mid_load+1;

}

return hi;

}

};

Total solution to run and test as a single program.

#include <iostream>
#include <cstdio>
#include <vector>
#include <numeric>
#include <algorithm>

using namespace std;

vector<int> folder;

class FairWorkload{
	public:
	int getMostWork(vector<int> folder,int worker)
	{
		int n = folder.size();
		int lw = *max_element(folder.begin(),folder.end());
		int hi = accumulate(folder.begin(),folder.end(),0);
		int mid_load;
		int req_workers=1;
		int cur_load;
		if(worker==1)
		return hi;
		while(lw<hi)
		{
			mid_load = (lw+hi)/2;
			cur_load=0;
			req_workers=1;
			for(int i=0;i<n;i++)
			{
				if(cur_load+folder[i]<=mid_load)
				{
					cur_load += folder[i];
				}
				else
				{
					cur_load=folder[i];
					req_workers += 1;
				}
			}
			if(req_workers<=worker)
			hi = mid_load;
			else if(req_workers>worker)
			lw=mid_load+1;
		}
		return hi;
	}
};
int main()
{
	int a,workers,n;
	while(1)
	{
		cout<<"enter no of file cabinets: ";
		cin>>n;
		folder.clear();
		for(int i=0;i<n;i++)
		{
			cin>>a;
			folder.push_back(a);

		}
		cin>>workers;
		FairWorkload fair;
		cout<<fair.getMostWork(folder,workers)<<"\n";
	}
	return 0;
}

#include <iostream>

#include <cstdio>

#include <vector>

#include <numeric>

#include <algorithm>

using namespace std;

vector<int> folder;

class FairWorkload{

public:

int getMostWork(vector<int> folder,int worker)

{

int n = folder.size();

int lw = *max_element(folder.begin(),folder.end());

int hi = accumulate(folder.begin(),folder.end(),0);

int mid_load;

int req_workers=1;

int cur_load;

if(worker==1)

return hi;

while(lw<hi)

{

mid_load = (lw+hi)/2;

cur_load=0;

req_workers=1;

for(int i=0;i<n;i++)

{

if(cur_load+folder[i]<=mid_load)

{

cur_load += folder[i];

}

else

{

cur_load=folder[i];

req_workers += 1;

}

if(req_workers<=worker)

hi = mid_load;

else if(req_workers>worker)

lw=mid_load+1;

}

return hi;

}

};

int main()

{

int a,workers,n;

while(1)

{

cout<<"enter no of file cabinets: ";

cin>>n;

folder.clear();

for(int i=0;i<n;i++)

{

cin>>a;

folder.push_back(a);

}

cin>>workers;

FairWorkload fair;

cout<<fair.getMostWork(folder,workers)<<"\n";

}

return 0;

}

880

Asif NaeemFebruary 25, 2016

#include <iostream>
#include <cstdio>
#define ul unsigned long long
#define INT_MX 2147483641

using namespace std;


ul binsearch(ul n,ul lw,ul hi)
{
	ul mid;
	ul tmp,tmp1,tmp2;
	while(lw<hi)
	{
		mid=(lw+hi)/2;
		tmp = (mid*(mid+1))/2;
		if(tmp<=n)
			lw=mid+1;
		else if(tmp>n)
			hi=mid;
	}
	return hi;
}
int main()
{
	ul n;
	ul diff,hi,lw;
	ul neumenator,denominator;
	while(cin>>n)
	{
		hi = binsearch(n,0,INT_MX);
		diff = n-(hi*(hi-1))/2;
		if(diff==0)
		{
			printf("%llu/%llu\n",1,hi-1);
		}
		else
		{
			printf("%llu/%llu\n",hi-(diff-1),diff);
		}
	}
	return 0;
}

#include <iostream>

#include <cstdio>

#define ul unsigned long long

#define INT_MX 2147483641

using namespace std;

ul binsearch(ul n,ul lw,ul hi)

{

ul mid;

ul tmp,tmp1,tmp2;

while(lw<hi)

{

mid=(lw+hi)/2;

tmp = (mid*(mid+1))/2;

if(tmp<=n)

lw=mid+1;

else if(tmp>n)

hi=mid;

}

return hi;

}

int main()

{

ul n;

ul diff,hi,lw;

ul neumenator,denominator;

while(cin>>n)

{

hi = binsearch(n,0,INT_MX);

diff = n-(hi*(hi-1))/2;

if(diff==0)

{

printf("%llu/%llu\n",1,hi-1);

}

else

{

printf("%llu/%llu\n",hi-(diff-1),diff);

}

return 0;

}

10494

Asif NaeemFebruary 24, 2016

#include <iostream>
#include <cstdio>
#include <cstring>
//#include <fstream>

#define ul unsigned long long

using namespace std;

int quotient[10005];
ul remainder;

int main()
{
	char num[10005];
	char op[2];
	int div;
	int pos;
	int j,k;
	//ofstream out;
	//out.open("out_10494.txt");
	while(scanf("%s%s%d",num,op,&div)!=EOF)
	{
		k=0;
		remainder=0;
		for(int i=0;i<strlen(num);i++)
		{
			quotient[k] = 0;
			remainder = remainder*10+(num[i]-'0');
			quotient[k] = remainder/div;
			remainder = remainder%div;
			k+=1;
		}
		if(op[0]=='/')
		{
			for(pos=0;pos<k && quotient[pos]==0 ;pos++)
				;
			if(pos==k)
				printf("0\n");
				//out<<"0\n";
			else
			{
				while(pos<k)
					printf("%d",quotient[pos]),
					//out<<quotient[pos],
					pos+=1;
				printf("\n");
				//out<<"\n";
			}
		}
		else if(op[0]=='%')
		{
			printf("%llu\n",remainder);
			//out<<remainder<<"\n";
		}
	}
	//out.close();
	return 0;
}

#include <iostream>

#include <cstdio>

#include <cstring>

//#include <fstream>

#define ul unsigned long long

using namespace std;

int quotient[10005];

ul remainder;

int main()

{

char num[10005];

char op[2];

int div;

int pos;

int j,k;

//ofstream out;

//out.open("out_10494.txt");

while(scanf("%s%s%d",num,op,&div)!=EOF)

{

k=0;

remainder=0;

for(int i=0;i<strlen(num);i++)

{

quotient[k] = 0;

remainder = remainder*10+(num[i]-'0');

quotient[k] = remainder/div;

remainder = remainder%div;

k+=1;

}

if(op[0]=='/')

{

for(pos=0;pos<k && quotient[pos]==0 ;pos++)

;

if(pos==k)

printf("0\n");

//out<<"0\n";

else

{

while(pos<k)

printf("%d",quotient[pos]),

//out<<quotient[pos],

pos+=1;

printf("\n");

//out<<"\n";

}

else if(op[0]=='%')

{

printf("%llu\n",remainder);

//out<<remainder<<"\n";

}

//out.close();

return 0;

}

10611

Asif NaeemFebruary 24, 2016

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

int arr[50005];

int binSearch(int num,int lw,int hi)
{
	int mid;
	while(lw<hi)
	{
		mid = (hi+lw)/2;

		if(num<arr[mid])
			hi = mid;
		else if(num>=arr[mid])
			lw = mid+1;

	}
	return hi;
}

int main()
{
	int N,Q,a;
	int len,qry,idx;
	while(scanf("%d",&N)!=EOF)
	{
		scanf("%d",&arr[0]);
		len = 1;
		for(int i=1;i<N;i++)
		{
			scanf("%d",&a);
			if(a!=arr[len-1])
			{
				arr[len]=a;
				len +=1;
			}
		}
		scanf("%d",&Q);
		for(int i=0;i<Q;i++)
		{
			scanf("%d",&qry);
			if(qry<arr[0])
			{
				printf("X %d\n",arr[0]);
			}
			else if(qry==arr[0])
			{
				printf("X");
				if(len>1)
				printf(" %d\n",arr[1]);
				else
				printf("X\n");
			}
			else if(qry==arr[len-1])
                        {
                                printf("%d X\n",arr[len-2]);
                        }
			else if(qry>arr[len-1])
			{
				printf("%d X\n",arr[len-1]);
			}
			else
			{
				idx = binSearch(qry,0,len-1);
				if(arr[idx-1]==qry)
				{
					if(idx>=2)
					printf("%d %d\n",arr[idx-2],arr[idx]);
					else
					printf("X %d\n",arr[idx]);
				}
				else if(arr[idx-1]!=qry)
					printf("%d %d\n",arr[idx-1],arr[idx]);
			}
		}

	}
	return 0;
}

#include <iostream>

#include <cstdio>

#include <cstring>

using namespace std;

int arr[50005];

int binSearch(int num,int lw,int hi)

{

int mid;

while(lw<hi)

{

mid = (hi+lw)/2;

if(num<arr[mid])

hi = mid;

else if(num>=arr[mid])

lw = mid+1;

}

return hi;

}

int main()

{

int N,Q,a;

int len,qry,idx;

while(scanf("%d",&N)!=EOF)

{

scanf("%d",&arr[0]);

len = 1;

for(int i=1;i<N;i++)

{

scanf("%d",&a);

if(a!=arr[len-1])

{

arr[len]=a;

len +=1;

}

scanf("%d",&Q);

for(int i=0;i<Q;i++)

{

scanf("%d",&qry);

if(qry<arr[0])

{

printf("X %d\n",arr[0]);

}

else if(qry==arr[0])

{

printf("X");

if(len>1)

printf(" %d\n",arr[1]);

else

printf("X\n");

}

else if(qry==arr[len-1])

{

printf("%d X\n",arr[len-2]);

}

else if(qry>arr[len-1])

{

printf("%d X\n",arr[len-1]);

}

else

{

idx = binSearch(qry,0,len-1);

if(arr[idx-1]==qry)

{

if(idx>=2)

printf("%d %d\n",arr[idx-2],arr[idx]);

else

printf("X %d\n",arr[idx]);

}

else if(arr[idx-1]!=qry)

printf("%d %d\n",arr[idx-1],arr[idx]);

}

return 0;

}

Month: February 2016

Fair Work Load [Top Coder]

880

10494

10611

Archives

Categories