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];

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);
}

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!

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;
}

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;
}

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

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);

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;
    }

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

I like Dp problem here a good web page http://20bits.com/article/introduction-to-dynamic-programming