Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

CazadorDivino's blog

By CazadorDivino, history, 3 years ago, In English

Hello, someone knows how can I prove the solution to this problem by induction?

Author: Manuel Blum, Awards Turing Award (1995).

  1. [Manuel Blum] Imagine a jar containing a number of white balls and black balls. Suppose also that you have an unlimited supply of white balls out of the jar. Now repeat the following procedure as long as it makes sense: remove two balls from the jar; if the two have the same color, put a white ball in the jar; if the two have different colors, put a black ball in the jar. What color is the last ball left in the jar?
int n = size(A);
	while(n>1){
		a = getball(A);
		b = getball(A);
		if(a == b)
			setball(white);
		else
			setball(black);
		n = update(A);
	}
	return A[1];

Read more »

 
 
 
 
  • Vote: I like it
  • +8
  • Vote: I do not like it

By CazadorDivino, history, 3 years ago, In English

Bazout's Identity For three or more integers

Bézout's identity can be extended to more than two integers: if

gcd ( a1 , a2 , … , an ) = d

then there are integers x1 , x2 , … , xn such that

d = a1*x 1 + a2*x2 + ⋯ + an*xn

has the following properties:

  • d is the smallest positive integer of this form
  • every number of this form is a multiple of d

But... Why x_i < 0 does not affect the calculation to problem (Div. 2) — E, someone can explain me.

Tutorial: Here some xi<0, But Natasha can add for each par a sufficiently large number, multiple k, that xi became greater than zero, the balance from dividing the amount of tax on k from this will not change.

#include<bits/stdc++.h>

using namespace std;

int gcd(int a,int b)
{
    if(a<b)
        swap(a,b);
    return (b==0)?a:gcd(b,a%b);
}

int main()
{
    int n,k;
    scanf("%d%d",&n,&k);
    int g=0;
    for(int i=0;i<n;i++)
    {
        int t;
        scanf("%d",&t);
        g=gcd(g,t);
    }
    set<int> ans;
    for(long long i=0,s=0;i<k;i++,s+=g)
        ans.insert(s%k);
    printf("%d\n",ans.size());
    for(set<int>::iterator i=ans.begin();i!=ans.end();i++)
        printf("%d ",*i);
}

Read more »

Tags gcd
 
 
 
 
  • Vote: I like it
  • +17
  • Vote: I do not like it

By CazadorDivino, history, 4 years ago, In English

Hi, can anyone help me figure out why the system test gives a different answer to my computer for this code?. Codeforces Round #425 (Div. 2), Problem B.

#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
#include <vector>
using namespace std;

bool vali(string test, string s, int alf[300]){
	int j = 0, i = 0;
	if((int)s.size() == (int)test.size() + 1)
		for(; j < (int)s.size(); j++){
			if(s[j] == '*'){ continue;}
			else if((s[j] == test[i]) || (s[j] == '?' && alf[(int)test[i]] == 1) ){
				i++;
				continue;
			}
			else
				return false;
		}
	else if((int)s.size() == (int)test.size()){
		for(; j < (int)s.size(); j++){
		if(s[j] == '*'){ i++; continue;}
		else if((s[j] == test[i]) || (s[j] == '?' && alf[(int)test[i]] == 1) ){
			i++;
			continue;
		}
		else
			return false;
		}
	}
	if(i == (int)test.size() && j  == (int)s.size()) return true;
	return false;
}

int main(){
	string cad; cin>>cad;
	int alf[300];
	for(int i = 0; i < (int)cad.size(); i++) alf[i] = 0;
	for(int i = 0; i < (int)cad.size(); i++)
		alf[(int)cad[i]]++;
	string s; cin>>s;
	int n; cin>>n;
	string test;
	bool flag = true; 
	vector<string> ans;
	for(int i = 0; i< n; i++){
		cin>>test;
		flag = vali(test, s, alf);
		if(flag) ans.push_back("YES");
		else ans.push_back("NO");	
	}
	for(int i = 0; i< n; i++)
		cout<<ans[i]<<endl;
	return 0;
}

Thanks!

Read more »

 
 
 
 
  • Vote: I like it
  • -13
  • Vote: I do not like it

By CazadorDivino, history, 5 years ago, In English

I understand the code, but why min(cc[u], k + k — cc[u]), this is magic for me. Anyone can help me. Thanks.

inline void dfs(int u, int p) {
	cout<< "dfs("<< u<<","<<p<<")"<<endl;
    rep (i, 0, adj[u].size()) {
        int v = adj[u][i];
        if (v != p) {
            dfs(v, u);
            cc[u] += cc[v];
        }
    }
    ans += min(cc[u], k + k - cc[u]);
   
}

int main() {
    cin >> n >> k;
    rep (i, 0, k + k) {
        int u;
        cin >> u;
        cc[u]++;
    }
    rep (i, 1, n) {
        int u, v;
        cin >> u >> v;
        adj[u].PB(v);
        adj[v].PB(u);
    }
    dfs(1, 0);
    cout << ans << endl;
    return 0;
}

Read more »

Tags dfs
 
 
 
 
  • Vote: I like it
  • +3
  • Vote: I do not like it

By CazadorDivino, history, 5 years ago, In English

In this problem, what is the meaning of "as well as the reversal of the bus, take place immediately and this time can be neglected." in this problem. I can two possibilities. 1, back the bus to collect pupils does not last any (immediate). 2, turn the car back nothing lasts for (immediate), but the movement to pick up a pupil (bakc) is counted in time.

Thanks for clearing my doubt.

I'm trying to understand the problem's solution.

int main() {
    int n, k;
    D l, v1, v2;
    cin >> n >> l >> v1 >> v2 >> k;
    
    
    int b = (n + k - 1) / k;
    cout<< "("<< n<< "+"<< k <<"- 1)"<< "/"<< k<< "= "<< b<< endl;
    double den = (2 * (b - 1) * v1 / (v1 + v2)) + 1;
    cout<<"(2 * ("<<b <<"- 1) * "<<v1 <<"/ ("<<v1 <<"+"<< v2<<")) +"<< 1 << "=" << den<<endl;
    double x = l / den;
    cout<< l <<"/ "<<den<<"="<< x<< endl;
    double ans = x / v2 + (l - x) / v1;
    cout<< x <<"/"<< v2 <<"+" <<"("<<l <<"-"<< x<<") / "<<v1 << "="<< ans<< endl;
    printf("%0.9f\n", ans);
    return 0;
}

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By CazadorDivino, history, 5 years ago, In English
int count(int N, int K){
	dp[0][0] = 1;
	for(int i = 0; i < N; i++){
		for(int j = 0; j <= K; j++){
			for( int a = 0; a <= i; a++){
				print(N,K);
				if(j+a*(i-a) > K || dp[i][j] == 0){ continue;}
				
				dp[i+1][j+a*(i-a)] += dp[i][j];
				dp[i+1][j+a*(i-a)] %= MOD;
				
			}
			
		}
	}
	return dp[N][K];
}

Help me with dis dp code, I can't undestand. https://community.topcoder.com/stat?c=problem_statement&pm=14304

Read more »

 
 
 
 
  • Vote: I like it
  • +2
  • Vote: I do not like it

By CazadorDivino, history, 6 years ago, In English

In the last codeforces 307 div 2, problem D. One solutione is below, What that mean

  if (((k >> i) & 1) == 0) res = res * fib % mod;
            else
                res = res * (pow2 - fib) % mod;

in this code.

long pow2 = fastPower(2, n);
        long fib = fibonacci(n + 1);
        long res = 1;
        for (int i = 0; i < l; i++)
            if (((k >> i) & 1) == 0) res = res * fib % mod;
            else
                res = res * (pow2 - fib) % mod;
        if (res < 0) res += mod;
        System.out.println(res);

Read more »

 
 
 
 
  • Vote: I like it
  • +3
  • Vote: I do not like it

By CazadorDivino, 7 years ago, In English

I was solving TCO 2015 and saw this code, someone knows it for?

public static int getMask(int n){
    	return n != 0 ? 1 << n % 10 | getMask(n / 10) : 0;
    }

Read more »

 
 
 
 
  • Vote: I like it
  • +17
  • Vote: I do not like it

By CazadorDivino, 7 years ago, In English

Why Arrays.sort(Integer) is more fast that Arrays.sort(int) ?(JAVA)

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By CazadorDivino, 7 years ago, In English
Tags dp
 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it