Beginning with problem solving: Medium problems

Medium Problems

Her is the list for medium problems:

1.   UVa 00119 - Greedy Gift Givers (simulate give and receive process)

2.   UVa 00573 - The Snail * (simulation, beware of boundary cases!)

3.   UVa 00661 - Blowing Fuses (simulation)

4.   UVa 10141 - Request for Proposal * (solvable with one linear scan)

5.   UVa 10324 - Zeros and Ones (simplify using 1D array: change counter)

6.   UVa 10424 - Love Calculator (just do as asked)

7.   UVa 10919 - Prerequisites? (process the requirements as the input is read)

8.   UVa 11507 - Bender B. Rodriguez ... * (simulation, if-else)

9.   UVa 11586 - Train Tracks (TLE if brute force, find the pattern)

10. UVa 11661 - Burger Time? (linear scan)

11. UVa 11683 - Laser Sculpture (one linear pass is enough)

12. UVa 11687 - Digits (simulation; straightforward)

13. UVa 11956 - Brain**** (simulation; ignore ‘.’)

14. UVa 12478 - Hardest Problem ... (try one of the eight names)

15. IOI 2009 - Garage (simulation)

16. IOI 2009 - POI (sort)

Here is the link to all these questions: https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=609

Solution and hint to some problems:

Uva 00119- Greedy Gift Givers

I created a class of persons, which represents each person. In this class we keep track of the amount he spent, he received and also the amount he saved from his "giving budget", in case the amount he can give each person was less than his budget.

Rest is just execution of what is said in the problem. We have used the map stl container which can be learned here: https://rishabhjainiitbhu.blogspot.com/2019/07/c-stl-maps.html

Here is the code:

//Uva 00119-Greedy Gift Givers
	#include <bits/stdc++.h>
	using namespace std;
	class persons{
	private:
	string name;
	int spent;
	int networth;
	int left;
	public:
	persons(){
	spent = 0;
	networth=0;
	left=0;
	}
	void setName(string a){
	name = a;
	}
	void totalSpent(int a){
	spent += a;
	}
	void Addnetworth(int a){
	networth += a;
	}
	int netGain(){
	return networth-spent+left;
	}
	void Addleft(int a){
	left += a;
	}
	};
	int main(int argc, char const *argv[]) {
	int N;
	int temp=1;
	while (scanf("%d", &N)==1) {
	////////////////Test cases
	string names;
	map<string, persons> m;
	vector<string> orderednames;
	for (int i = 0; i < N; i++) {
	cin>>names;
	orderednames.push_back(names);
	persons p;
	p.setName(names);
	m.emplace(pair<string, persons> (names, p));
	}
	int totalspending;
	int to;
	for (int i = 0; i < N; i++) {
	cin>>names;
	scanf("%d", &totalspending);
	scanf("%d", &to);
	if(to>0){
	int perperson = totalspending/to;
	int left = totalspending - (perperson*to);
	m[names].totalSpent(totalspending);
	m[names].Addleft(left);
	while (to--) {
	cin>>names;
	m[names].Addnetworth(perperson);
	}
	}else{
	m[names].totalSpent(0);
	m[names].Addleft(0);
	}
	}
	if(temp++>1)
	cout<<'\n';
	for (size_t i = 0; i < N; i++) {
	string name = orderednames[i];
	cout<<name<<" "<<m[name].netGain()<<endl;
	}
	}
	return 0;
	}

Uva 00573: The snail.

The program is simple you just need to read simulate what the problem is saying. Note: I made a mistake, read the question carefully and note that boundary conditions.

int main(int argc, char const *argv[]) {
	float height, day1, slide, fat;
	while (scanf("%f %f %f %f", &height, &day1, &slide, &fat) == 4 && height!=0) {
	float currentheight = 0;
	int days = 0;
	float fatr = fat/100 * day1;
	float effectiveheight = day1;
	//for day1
	while (true) {
	days++;
	///The day
	currentheight = currentheight + effectiveheight;
	if(currentheight>height){
	break;
	}
	//The night
	currentheight = currentheight - slide;
	if(currentheight<0)
	break;
	effectiveheight = effectiveheight - fatr;
	if(effectiveheight<0)
	effectiveheight=0;
	}
	if(currentheight>height)
	printf("%s", "success on day ");
	else if(currentheight<0)
	printf("%s", "failure on day ");
	printf("%d\n", days);
	}
	return 0;
	}

Uva 0061: The blowing fuses.

The problem is simple. Keep an array to store the consumption of each bulb and an extra array to store if the bulb is on or not.

//Uva 0061 The blowing fuses
	int main(int argc, char const *argv[]) {
	int n, m, c;
	int sequence = 1;
	while (scanf("%d %d %d", &n, &m, &c)!=EOF) {
	if((n==0 && m==0&& c==0))
	break;
	int map[n];
	int temp;
	bool success = true;
	bool situation[n] = {false};
	int curcons = 0;
	int max = 0;
	for (size_t i = 0; i < n; i++) {
	scanf("%d", &map[i]);
	}
	for (size_t i = 0; i < m; i++) {
	scanf("%d", &temp);
	if(situation[temp-1]==false){
	situation[temp-1] = true;
	curcons += map[temp-1];
	}else{
	curcons -= map[temp-1];
	situation[temp-1] = false;
	}
	if(curcons>c){
	success = false;
	}else{
	if(max<curcons)
	max = curcons;
	}
	}
	if(success==false){
	printf("Sequence %d\n", sequence);
	printf("Fuse was blown.\n\n");
	}else{
	printf("Sequence %d\n", sequence);
	printf("Fuse was not blown.\n");
	printf("Maximal power consumption was %d amperes.\n\n", max);
	}
	sequence++;
	}
	return 0;
	}

UVA 10324 Zeros and ones

A simple question, nothing new to learn.

int main(int argc, char const *argv[]) {
	char s[1000005];
	long long int n;
	int t=1;
	while (scanf("%s %lld\n", s, &n)==2) {
	printf("Case %d:\n",t);
	t++;
	while (n--) {
	long long int i, j;
	scanf("%lld %lld", &i, &j);
	long long int max = std::max(i, j);
	long long int min = std::min(i, j);
	bool valid = true;
	for (size_t i = min; i < max; i++) {
	if(s[i]!=s[i+1])
	valid =false;
	}
	if(valid)
	printf("Yes\n");
	else
	printf("No\n");
	}
	}
	return 0;
	}

Uva 10424: Love Calculator

It is a combination of more than one problems.

Given a string, trim all non-alphabet characters out of it. 

Given a string with alphabets, where each alphabet is associated with an integer, get the sum of values associated with each character in it.

Given a number, find the sum of its digits, repeat this step till single-digit number is left.

string trim(string name){
	string result = "";
	for(char ch: name){
	if((ch<=90&&ch>=65)||(ch<=122&&ch>=97))
	result += ch;
	}
	return result;
	}
	float calcSum(string a){
	int sum = 0;
	for(char ch: a){
	if(ch<=90&&ch>=65)
	sum += ch - 'A'+1;
	if((ch<=122&&ch>=97))
	sum += ch - 'a' +1;
	}
	return sum;
	}
	float calcDigitSum(int a){
	if(a<10)
	return a;
	return calcDigitSum(a/10) + (a%10);
	}
	float oneDigit(int a){
	if(a<10)
	return a;
	return oneDigit(calcDigitSum(a));
	}
	int main(int argc, char const *argv[]) {
	string name1;
	string name2;
	while (getline(cin, name1), getline(cin, name2), name1!=""&&name2!="") {
	name1 = trim(name1);
	name2 = trim(name2);
	float sum0 = calcSum(name1);
	float sum1 = calcSum(name2);
	sum0 = oneDigit(sum0);
	sum1 = oneDigit(sum1);
	float percent = (sum0>sum1)?sum1/sum0:sum0/sum1;
	printf("%.2f %%\n", percent*100);
	}
	return 0;
	}

Uva 11586: Train Tracks

Brute force will give TLE. You need to find a pattern. Here the pattern is that the number of male joints and female joints should be equal. Why? Think over it.

//Uva 11586 Train Tracks
	int main(int argc, char const *argv[]) {
	int t;
	scanf("%d\n", &t);
	while (t--) {
	string s;
	while (getline(cin, s) && s!="") {
	int males=0;
	int females = 0;
	for(char ch: s){
	if(ch=='M')
	males++;
	if(ch=='F')
	females++;
	}
	if(males==females && (males>1 && females>1))
	printf("%s\n", "LOOP");
	else
	printf("%s\n", "NO LOOP");
	}
	}
	return 0;
	}