UVa 10082 WERTYU Solution in C++

Things to learn:

• Usage of map STL

Complete Code:

#include <cstdio>
#include<map>
using namespace std;

int main() {
	char c;
	map<char, char> t;
	t[' '] =	' ';
	t['\n'] =	'\n';
	t['1'] =	'`';
	t['2'] =	'1';
	t['3'] =	'2';
	t['4'] =	'3';
	t['5'] =	'4';
	t['6'] =	'5';
	t['7'] =	'6';
	t['8'] =	'7';
	t['9'] =	'8';
	t['0'] =	'9';
	t['-'] =	'0';
	t['='] =	'-';
	t['W'] =	'Q';
	t['E'] =	'W';
	t['R'] =	'E';
	t['T'] =	'R';
	t['Y'] =	'T';
	t['U'] =	'Y';
	t['I'] =	'U';
	t['O'] =	'I';
	t['P'] =	'O';
	t['['] =	'P';
	t[']'] =	'[';
	t['\\'] =	']';
	t['S'] =	'A';
	t['D'] =	'S';
	t['F'] =	'D';
	t['G'] =	'F';
	t['H'] =	'G';
	t['J'] =	'H';
	t['K'] =	'J';
	t['L'] =	'K';
	t[';'] =	'L';
	t['\''] =	';';
	t['X'] =	'Z';
	t['C'] =	'X';
	t['V'] =	'C';
	t['B'] =	'V';
	t['N'] =	'B';
	t['M'] =	'N';
	t[','] =	'M';
	t['.'] =	',';
	t['/'] =	'.';
	while ((c=getchar()) != EOF) {
		putchar(t[c]);
	}
	return 0;
}

Sample Input:

O S, GOMR YPFSU/

Sample Output:

I AM FINE TODAY.

Runtime: 0.019s

UVa 941 Permutations Solution in C++

To find the n-th permutation of the given string in C++, with string length less than 20. This code doesn’t handle repetitive characters.

Things to learn:

• Solving the problem without populating permutations 😉
• Dealing with Local and Global Variable
• Caching of factorials

Complete Code:

#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;

vector<bool> base;
int len;
char* str;

char next(long long x){
	long long j = 0, k = 0;
	for(int i = 0; i<len; i++){
		if(base[i]) j++;
		if(i-j==x) break;
	}
	base[j+x] = true;
	return str[j+x];
}


int main(){

	long long fact[20];
	fact[0] = 1;
	for(int i = 1; i<20; i++){
		fact[i]=i*fact[i-1];
	}

	int T;
	scanf("%d", &T);
	for(int t = 0; t<T; t++){
		str = new char[21];
		scanf("%s", str);
		len = strlen(str);
		sort(str, str+len);
		base  = vector<bool> (len, false);

		long long N;
		scanf("%lld", &N);

		int fac;
		for(fac = 0; fac<19; fac++){
			if(N<fact[fac+1]) break;
		}
		long long d, r = N, j = 0;
		for(int k = 0; k< len-fac-1; k++){
			putchar(next(0));
			j++;
		}
		while(r!=0){
			d = r/fact[fac];
			putchar(next(d));
			r = r - d*fact[fac--];
			j++;
		}
		for(long long k = 0; k<len-j; k++){
			putchar(next(0));
		}
		putchar('\n');
	}
}

Sample Input:

3
abc
3
abcde
119
abcdefghijklmnopqrst
120

Sample Output:

bca
edcba
abcdefghijklmnpoqrst

Runtime: 0.082s

UVa 837 Light and Transparencies Solution in C++

Things to learn:

• Way of thinking 🙂

Complete Code:

#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>

using namespace std;

struct segment{
	double r, x1, x2, y1, y2;
};

bool segmentcomparator(const segment& a, const segment& b){
	return a.x1 < b.x1;
}

int main(){
	int n, nl, counter;
	segment tmp;
	vector<segment> v;
	vector<double> x;
	scanf("%d", &n);
	while(n--){
		v.clear(); x.clear();
		scanf("%d", &nl);
		while(nl--){
			scanf("%lf %lf %lf %lf %lf", 
				&tmp.x1, &tmp.y1, &tmp.x2, &tmp.y2, &tmp.r);
			x.push_back(tmp.x1);
			x.push_back(tmp.x2);
			if(tmp.x1>tmp.x2){
				swap(tmp.x1, tmp.x2);
				swap(tmp.y1, tmp.y2);
			}
			v.push_back(tmp);
		}
		sort(x.begin(), x.end());
		sort(v.begin(), v.end(), segmentcomparator);
		printf("%d\n", x.size()+1);
		for(int i=0; i<x.size(); i++){
			if(i==0){
				printf("-inf %.3f 1.000\n", x[i]);
				continue;
			}
			double result = 1.0;
			for(int j = 0; j<v.size(); j++){
				if(v[j].x1 <= x[i-1] && v[j].x2 >= x[i])
					result *= v[j].r;
			}
			printf("%.3f %.3f %.3f\n", x[i-1], x[i], result);
			if (i == x.size()-1) {
				printf("%.3f +inf 1.000\n", x[i]);
			}
		}
		if(n!=0) printf("\n");
	}
	return 0;
}

Sample Input:

1

3
2.0 2.0 9.0 2.0 0.9
13.5 2.0 4.0 8.5 0.7
17.0 10.0 7.0 8.5 0.8

Sample Output:

7
-inf 2.000 1.000
2.000 4.000 0.900
4.000 7.000 0.630
7.000 9.000 0.504
9.000 13.500 0.560
13.500 17.000 0.800
17.000 +inf 1.000

Time Taken: 0.009s

UVa 739 Soundex Indexing Solution in C++

Things to learn:

• I/O in C++
• C Strings

Complete Code:

#include<cstdio>
#include<cstring>

int soundexcode (char x)
{
    char array0 [] = "AEIOUYWH";
    char array1 [] = "BPFV";
    char array2 [] = "CSKGJQXZ";
	if (strchr(array0, x))		return 0;
	if (strchr(array1, x))		return 1;
    if (strchr(array2, x))		return 2;
    if ( x == 'D' || x == 'T')	return 3;
    if ( x == 'L')				return 4;
    if ( x == 'M' || x == 'N')	return 5;
    if ( x == 'R')				return 6;
}

int main ()
{
    printf ("         NAME                     SOUNDEX CODE\n");
    char name [25];
    while(gets(name))
    {
        char output [25];
        output [0] = name [0];
        output [1] = output [2] = output [3] = '0';
        int code = soundexcode (name [0]);
        int index = 1;
        int length = strlen (name);
        for ( int i = 1; i < length; i++ )
        {
            int temp_code = soundexcode (name [i]);
            if(temp_code != code && temp_code != 0)
				output[index++] = temp_code + '0';
            if(temp_code != code) code = temp_code;
        }

        printf ("%9s%s", "", name);
        for ( int i = 0; i < 25 - length; i++ ) printf (" ");
        printf ("%c%c%c%c\n", output [0], output [1], 
			output [2], output [3]);
    }
    printf ("                   END OF OUTPUT\n");
    return 0;
}

Sample Input:

LEE
KUHNE
EBELL
EBELSON
SCHAEFER
SCHAAK

Sample Output:

         NAME                     SOUNDEX CODE
         LEE                      L000
         KUHNE                    K500
         EBELL                    E140
         EBELSON                  E142
         SCHAEFER                 S160
         SCHAAK                   S200
                   END OF OUTPUT

Runtime: 0.049s

Snakes and Ladders: The Quickest Way Up HackerRank Solution in C++

The trick here is to have an edge from every vertex to subsequent 6 vertices with edge weight 1 and the edges for snakes and ladders are of weight 0.
Things to learn:

• Dijkstra’s Shortest Path Algorithm
• Implementation of Min Priority Queue using STL

Complete Code:

#include<cstdio>
#include<vector>
#include<queue>
using namespace std;

const int INF = 2000000000;
typedef pair<int,int> PII;

#define V 101
#define min(x, y) (x<y?x:y)
#define max(x, y) (x>y?x:y)

int main(){
	int T, L, S;
	scanf("%d", &T);
	
	for(int t = 0; t<T; t++){
		vector<vector<PII> > edges(V);
		scanf("%d,%d", &L, &S);
		PII edge;
		for(int l = 0; l<L; l++){
			scanf("%d,%d", &edge.first, &edge.second);
			edges[edge.first].push_back (make_pair (0, edge.second));
		}
		for(int s = 0; s<S; s++){
			scanf("%d,%d", &edge.first, &edge.second);
			edges[edge.first].push_back (make_pair (0, edge.second));
		}
		for(int v = 1; v<V; v++){
			for(int i = 1; i<=6; i++){
				if(i+v>=V) break;
				else{
					edges[v].push_back(make_pair(1, v+i));
				}
			}
		}



		priority_queue<PII, vector<PII>, greater<PII> > Q;
		vector<int> distTo(V, INF), edgeTo(V, -1);
		// Source Vertex Entry
		Q.push(make_pair (0, 1));
		distTo[1] = 0;
		while(!Q.empty()){
			PII p = Q.top();
			// Sink Vertex Check
			if (p.second == 100) break;
			Q.pop();
			int here = p.second;
			for (vector<PII>::iterator it=edges[here].begin(); 
					it!=edges[here].end(); it++){
				if (distTo[here] + it->first < distTo[it->second]){
					distTo[it->second] = distTo[here] + it->first;
					edgeTo[it->second] = here;
					Q.push (make_pair (distTo[it->second], it->second));
				}
			}
		}
		printf("%d\n", distTo[100]);
	}

	return 0;
}

Sample Input:

3
3,7
32,62 42,68 12,98
95,13 97,25 93,37 79,27 75,19 49,47 67,17
5,8
32,62 44,66 22,58 34,60 2,90
85,7 63,31 87,13 75,11 89,33 57,5 71,15 55,25
4,9
8,52 6,80 26,42 2,72
51,19 39,11 37,29 81,3 59,5 79,23 53,7 43,33 77,21

Sample Output:

3
3
5

Runtime: 0.02s

UVa 661 Blowing Fuses Solution in C++

Things to learn:

• Nothing 😦

Complete Code:

#include <cstdio>
#include <cstring>
using namespace std;
 
int main(){
    int n,m,c;
    int testCase = 1;
    while(scanf("%d %d %d",&n,&m,&c), n || m || c){
		
		bool state[n+1];
		int consumption[n+1];

		for(int i=1;i<=n;i++) state[i] = false;
		for(int i=1;i<=n;i++) scanf("%d", &consumption[i]);

		int max = 0, runningPower = 0;

		for(int i=1;i<=m;i++){
			
			int temp; scanf("%d", &temp);

			if(state[temp]==false){
				state[temp] = true;
				runningPower += consumption[temp];
				if(runningPower > max)max = runningPower;
			}
			else if(state[temp]==true){
				state[temp] = false;
				runningPower -= consumption[temp];
			}
		}

		printf("Sequence %d\n",testCase++);
		if(max > c){ 
			printf("Fuse was blown.\n\n");
		}
		else {
			printf("Fuse was not blown.\n");
			printf("Maximal power consumption was %d amperes.\n\n",max);
		}
    }
    return 0;
}

Sample Input:

2 2 10
5
7
1
2
3 6 10
2
5
7
2
1
2
3
1
3
0 0 0

Sample Output:

Sequence 1
Fuse was blown.

Sequence 2
Fuse was not blown.
Maximal power consumption was 9 amperes.

Runtime: 0.013s

UVa 573 The Snail Solution in C++

Things to learn:

• Nothing 😦

Complete Code:

#include <cstdio>
using namespace std;

int main() {
	int h, u, d, f;
	while (scanf("%d %d %d %d", &h, &u, &d, &f), h || u || d || f) {
		double currU = u;
		double distMin = u * (f / 100.0);
		double currH = 0;
		int currDay = 0;

		while(true) {
			currDay++; currH += currU;
			if (currH > h){printf("success on day ");break;}
			currH -= d;
			if (currH < 0){printf("failure on day ");break;}
			currU -= distMin;
			if (currU < 0) currU = 0;
		}
		printf("%d\n",currDay);
	}

	return 0;
}

Sample Input:

6 3 1 10
10 2 1 50
50 5 3 14
50 6 4 1
50 6 3 1
1 1 1 1
0 0 0 0

Sample Output:

success on day 3
failure on day 4
failure on day 7
failure on day 68
success on day 20
failure on day 2

Runtime: 0.016s

UVa 483 Word Scramble Solution in C++

Things to learn:

• I/O in C++
• Stack STL in C++

Complete Code:

#include<cstdio>
#include<stack>

using namespace std;

stack<char> s;

int main(){
	char c;
	while((c=getchar())!=EOF){
		if(c==' '||c=='\n'){
			while(s.size()!=0){
				putchar(s.top());
				s.pop();
			}
			putchar(c);
		} else{
			s.push(c);
		}
	}	
	return 0;
}

Sample Input:

I love you.
You love me.
We're a happy family.

Sample Output:

I evol .uoy
uoY evol .em
er'eW a yppah .ylimaf

Runtime: 0.009s

UVa 349 Mapmaker Solution in C++

Things to learn:

• I/O in C++
• Solving problem with struct
• Vector and its iterator

Complete Code:

#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;

typedef struct{
	char name[11];
	int B;
	int CD;
	int D;
	int U[11], L[11], C[11];
} array;

vector<array> arrvec;
vector<array>::iterator arr;

int main(){
	int N, R;
	scanf("%d %d", &N, &R);
	for(int n=0; n<N; n++){
		array tmp;
		scanf("%s %d %d %d", tmp.name, &tmp.B, &tmp.CD, &tmp.D);
		for(int d = 1; d <= tmp.D; d++){
			scanf("%d %d", &tmp.L[d], &tmp.U[d]);
		}
		tmp.C[tmp.D] = tmp.CD;
		for(int d = tmp.D-1; d>0; d--){
			tmp.C[d] = (tmp.U[d+1] - tmp.L[d+1] + 1)*tmp.C[d+1];
		}
		tmp.C[0] = tmp.B;
		for(int d = 1; d <= tmp.D; d++){
			tmp.C[0]=tmp.C[0]-tmp.C[d]*tmp.L[d];
		}
		tmp.L[0] = 1; tmp.U[0] = 1;
		arrvec.push_back(tmp);
	}

	for(int r = 0; r<R; r++){
		int reference, coord;
		char name[11];
		scanf("%s", name);
		for(arr = arrvec.begin(); arr!=arrvec.end(); arr++){
			if(strcmp(name, (*arr).name) == 0){
				reference = (*arr).C[0];
				break;
			}
		}
		printf("%s[", name);
		scanf("%d", &coord);
		printf("%d", coord);
		reference+= (coord) * (*arr).C[1];
		for(int d = 2; d <= (*arr).D; d++){
			scanf("%d", &coord);
			printf(", %d", coord);
			reference+= (coord) * (*arr).C[d];
		}
		printf("] = %d\n", reference);
	}
	return 0;
}

Sample Input:

3 4
ONE       1500 2 2 0 3 1 5
TWO       2000 4 3 1 4 0 5 5 10
THREE     3000 1 1 1 9
ONE       2 4
THREE     7
TWO       2 0 6
TWO       3 3 9

Sample Output:

ONE[2, 4] = 1526
THREE[7] = 3006
TWO[2, 0, 6] = 2148
TWO[3, 3, 9] = 2376

Runtime: 0.019s

UVa 100 Solution in c++

Complete Code:

#include<cstdio>

int main(){
	int i, j;
	while(scanf("%d %d", &i, &j)==2){
		//original order of i and j
		int ti = i, tj = j;
		//swapping i and j if i greater than j
		if(i>j){i=i+j;j=i-j;i=i-j;}
		int max = 0;
		while(i<=j){
			unsigned int count = 1, n = i;
			while(n!=1){
				if(n%2==1) n = 3*n+1;
				else n>>=1;
				count++;
			}
			if(max<count) max=count;
			i++;
		}
		printf("%d %d %d\n", ti, tj, max);
	}
	return 0;
}

Sample Input:

5 5
1 10
100 200
201 210
900 1000
1000 900
999999 999990

Sample Output:

5 5 6
1 10 20
100 200 125
201 210 89
900 1000 174
1000 900 174
999999 999990 259

Run Time: 0.532s