Codeforces Round #186 (Div. 2)

Problem A. Ilya and Bank Account

In order to solve this problems I have created an Array ‘v’ of digits. With this Array ‘v’ is possible to create the values ‘a’ (doesn’t use v[v.size()-1]) and ‘b’ (doesn’t use v[v.size()-2]). The solution is the maximum value of both.

int main() {
	int n, a, b;
	scanf("%d", &n);
	if(n < 0) {
		n = -n;
		vector<int> v;
		while(n) {
			v.push_back(n%10);
			n /= 10;
		}
		reverse(v.begin(), v.end());
		a = b = 0;
		for(int j=0; j<v.size() ;j++) {
			if(j != v.size()-1)
				a = a*10 + v[j];
			if(v.size() >= 2 && j != v.size()-2)
				b = b*10 + v[j];
		}
		printf("%dn", max(-a, -b) );
	}
	else printf("%dn", n);
}

Problem B. Ilya and Queries

[latexpage]The answer to the query $l, r$ is the number(total quantity) of pairs $[s_i, s_{i+1}]$ that $s_i$ = $s_{i+1}$ when $l <= i <= r$.

First we need to convert this problem to ones and zeros, in our Array v will be 1 if $s_i = s_{i-1}$, with that we have the next equation to solve the problem:

begin{equation}$res = sum_{i=l}^{r}{v_i}$ (v_i = 1 If $s_i$ is equal to $s_{i-1}$)end{equation}

Adding $sum_{i=0}^{l-1}{v_i}$ in the last equation we can obtain:

begin{equation}$res + sum_{i=0}^{l-1}{v_i} = sum_{i=l}^{r}{v_i}  + sum_{i=0}^{l-1}{v_i}$end{equation}

begin{equation}$res + sum_{i=0}^{l-1}{v_i} = sum_{i=0}^{r}{v_i}$end{equation}

And now we need to subtract $sum_{i=0}^{l-1}{v_i}$ in the equation in order to solve the problem, the next equation solve this problem and it’s more easy to implement.

begin{equation}$res = sum_{i=0}^{r}{v_i} – sum_{i=0}^{l-1}{v_i}$end{equation}

string s;
int v[100001];

int main() {
	int m, x, y, r;
	cin>>s;
	char ch = s[0];
	for(int i=1; i<s.size() ;i++) {
		v[i+1] = v[i] + int(s[i] == ch);
		ch = s[i];
	}
	scanf("%d", &m);
	for(int i=0; i<m ;i++) {
		scanf("%d %d", &x, &y);
		r = v[y] - v[x];
		printf("%dn", r);
	}
}

Problem C. Ilya and Matrix

int main() {
	int n;
	scanf("%d", &n);
	vector<int> v(n);
	for(int i=0; i<n ;i++)
		scanf("%d", &v[i]);
	if(n == 1) cout << v[0] << endl;
	else {
		int m = 1, aux = 4;
		while(aux != n) {
			m++;
			aux *= 4;
		}
		m++;
		sort(v.rbegin(), v.rend());
		int it = 0, act = 1;
		LL res = 0;
		while(m > 0 && it < int(v.size()) ) {
			if(it == act) {
				m--;
				act *= 4;
			}
			res += LL(v[it++]) * LL(m);
		}
		cout << res << endl;
	}
}

 

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión /  Cambiar )

Google photo

Estás comentando usando tu cuenta de Google. Cerrar sesión /  Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión /  Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión /  Cambiar )

Conectando a %s