Problem

codeforces.com/contest/912/problem/B

Analysis

You can choose k or less than k integers from 1~n, calculate maximum xor result (1) k = 1, You can only choose one integer, so you choose n and get the maximum xor result n (2) k > 1, whatever k is, such as k = 2, or k = 3, ......, or k = n, if n has x bits as binary code, the maximum xor result must be 2 ^ x — 1

本题是求从1~n个数中取小于或等于k个数（比如n = 4, k = 3表示从1~4中取1个数或2个数或3个数），对这些数进行异或求和，求最大的异或求和值。 （1）k = 1时，即从1~n个数中1个数，那么最大的数自然是n。结果为n （2）k > 1时，假如n以二进制表示是x位数，则结果必为2 ^ x - 1

Example 1

n = 4, k = 2 choose 4 and 3, maximum = 4 xor 3 = 7 可以取4和3这两个数，最大异或结果 = 4 xor 3 = 7 = 2 ^ 3 - 1

Example 2

n = 4, k = 3 Choose two numbers, 4 and 3. Or choose three numbers, 4, 1 and 2. maximum = 4 xor 3 = 4 xor 1 xor 2 = 7 可以取4和3这两个数，也可以取4、1、2这三个数。 最大异或结果 = 4 xor 3 = 4 xor 1 xor 2 = 7

Example 3

n = 4, k = 4 Choose two numbers, 4 and 3. Or choose three numbers, 4, 1 and 2. maximum = 7 You can not choose all for numbers, because 4 xor 1 xor 2 xor 3 xor 4 = 3, which is not the maximum result. 可以取4和3，也可以取4、1、2。最大异或结果为7。 但不能取4、1、2、3。因为4 xor 1 xor 2 xor 3 xor 4 = 3，不是最大的结果。

Example 4

n = 6, k = 6 Just choose 1 and 6, maximum = 6 xor 1 = 7 只要在1~6中取6和1两个数就行了，6 xor 1 = 7

Code

Python2

import sys

n, k = map(int, raw_input().split())

if 1 == k:
    print n
    sys.exit(0)

res = 1
while res < n:
    res = res * 2 + 1

print res

C Language

#include <stdio.h>
#include <stdint.h>

int main(void)
{
    int64_t n, k;
    scanf("%I64d %I64d", &n, &k);
    
    if (1 == k) 
	{
        printf("%I64d\n", n);
        
        return 0;
    }
    
    int bit = 0;
    for (; n >> bit; bit++);
    printf("%d", n);
    printf("%d", bit);
    
    printf("%I64d\n", (1LL << bit) - 1);
    
    return 0;
}

[A. New Year and Counting Cards]

Problem Statement

http://mirror.codeforces.com/contest/908/problem/A

Analysis

For letter, only vowel need to know the digit in the other side. For digit, only odd number need to know the letter in the other side.

Code

#include <iostream>
#include <string>
using namespace std;

#define MAX 50

int main()
{
	int cnt = 0;
	string s;
	cin >> s;
	
	for(int i = 0; i < s.length(); i++) 
	{
		if('a' <= s.at(i) <= 'z')
		{
			if('a' == s.at(i)|| 'e' == s.at(i) || 'i' == s.at(i) || 'o' == s.at(i) || 'u' == s.at(i))
			{
				cnt++;
			}
		}
		
		if('0' <= s.at(i) <= '9')
		{
			if('1' == s.at(i) || '3' == s.at(i) || '5' == s.at(i) || '7' == s.at(i) || '9' == s.at(i))
			{
				cnt++;
			}
		}
	}
	
	cout << cnt;
}

[B. New Year and Buggy Bot]

Problem Statement

http://mirror.codeforces.com/contest/908/problem/B

Analysis

(1) Bob forgot to actually assign the directions to digits, so there are 24 mapping relations between directions and digits

(2) For C++, you can use next_permutation() of STL to enumerate all 24 permutations.

Code

#include <bits/stdc++.h>
using namespace std;

enum Dir{DOWN, UP, RIGHT, LEFT};
const int maxn = 50;
char grid[maxn][maxn];
int n, m;						// n for rows, m for columns
int digit[4] = {0, 1, 2, 3};
int startX, startY, exitX, exitY;
string instructions;

int move() 
{
    int row = startX, col = startY;
    
    for (int i = 0; i < instructions.size(); ++i) 
	{
        int d = instructions[i] - '0';
        for (int j = 0; j < 4; ++j) 
		{
            if (d == digit[j]) 
			{
                if (j == DOWN)
                {
                	row++;
				}
                    
                if (j == UP)
                {
                	row--;
				}
				
                if (j == RIGHT)
                {
                	col++;
				}

                if (j == LEFT)
                {
                	col--;
				}
            }
            
            if (row > n || row < 1 || col > m || col < 1)
            {
            	return 0;
			}      
            else if (grid[row][col] == 'E') 
			{
                return 1;
            }
            else if (grid[row][col] == '#')
            {
            	 return 0;
			}   
        }
    }
    
    return 0;
}

int main() 
{
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) 
	{
        for (int j = 1; j <= m; ++j) 
		{
            cin >> grid[i][j];
            if (grid[i][j] == 'S') 
			{
                startX = i;
                startY = j;
            }
            else if (grid[i][j] == 'E') 
			{
                exitX = i;
                exitY = j;
            }
        }
    }
    
    cin >> instructions;
    int res = 0;
    do 
	{
        res += move();
    } while (next_permutation(digit, digit + 4));
    
    cout << res << endl;
    
    return 0;
}

Problem

http://mirror.codeforces.com/contest/909/problem/A

Analysis

According to the problem statements, you need to consider all the characters in the first name, and only the first character in the last name.

(1) Take “harry potter”for example

① You got“hp”

② You got “hap”, which is less than “hp”

③ You got “harp”,which is greater than “hap”

So, the answer is “hap”

(2) Take“ertuyivhfg v”for example

① You got “ev”

② You got “erv”, which is less than “ev”

③ You got “ertv”, which is less than “erv”

④ You got “ertuv”, which is less than “ertv”

⑤ You got “ertuyv”, which is greater than “ertuv”

So, the answer is “ertuv”

Code

#include<iostream>
#include<string>
using namespace std;

int main() 
{
	char first[10], last[10];
	cin >> first;
	cin >> last;
	
	string pre1, pre2, temp, result;
	pre1 = "";
	pre1 += first[0];
	pre2 = "";
	pre2 += last[0];
	result = pre1 + pre2;
	
	for (int i = 1; first[i]; i++) 
	{
		pre1 += first[i];
		temp = pre1 + pre2;
	
		if (temp < result)
		{
			result = temp;
		}
	}
	
	cout << result;
}