There are \(M \times N\) \((1 \le M, N \le 15)\)square tiles. Each tile can be flipped and the color of tile can change between black(1) and white(0).

When you flip a tile, 4 adjacent tiles will also be flipped. Note that the four adjacent flipped tiles will NOT cause their adjacent tiles to flip.

Given a configuration, find the minimum number of flips so that all square tiles become white. If having the minimum number is the same, choose the least lexicographical one¹.

Sometimes we need to access Chinese content, like Youku Video, Netease Music (Cloud Music) and QQ music. It is very annoying to get “Can Only Be Streamed in Mainland China” or similar messages. Being tired of that, fortunately I have got a VPS from Aliyun and I build a proxy server using Shadowsocks on it and everything works smoothly now.

VPS

You need to have a VPS with Chinese IP address, there are tons of choices, like Aliyun(Alibaba Cloud) and Tencent Cloud etc.

A set of \(N\) \((10 \le N \le 100)\) lamps, numbered from 1 to N.

Four types of button:

Given \(C\) (number of button presses, \(0 \le C \le 10000\)) and final state of some of the lamps, find all possible distinct configuration.

There are one cow from each \(N\) (\(1 \le N \le 1000\)) farms want to go to the number X farm to have a party, hurrah! One cow from each farm need to go to the party and go back. There are \(M\) (\(1 \le M \le 100,000\)) weighted (represents time) one-direction roads connects pairs of roads. Cows are smart though, they want to go via the shortest path. The question is, what is the longest time the cow will take.

Given an array with size \(N \times N (N \le 100)\), find the maximum value of its subarray.

Link: Problem on UVa

Solutions

First thought is to brute force - find all possible subarrays then the time complexity will be \(O(N^6)\). TLE for sure.

Then comes up with an algorithm that takes \(O(N^4)\), which is enough to AC.

However, it can be \(O(N^3)\), see solution 2.

Solution 1

We build a sum array which is the sum of the numbers in rectangle area with the top-left of the array and bottom-right node \(i, j)\).

Find \(n\)th \( (1 \le n \le 5842)\) number whose only prime factors are 2, 3, 5 or 7.

Link: https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=384

Solutions

Solution 1

Kind of brute force, using STL set and vector to list all humble numbers. Using long long to avoiding overflow.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

#include<iostream>
#include<vector>
#include<set>
using namespace std;
typedef long long ll;
const int t[] = { 2, 3, 5, 7};
set<ll> s;

int main(void) {
	s.insert(1);
	set<ll>::iterator i = s.begin();
	while(s.size() < 6600) {
		for (int j = 0; j < 4; j++)
			s.insert((*i)*t[j]);
		i++;
	}
	vector<ll> v(s.begin(), s.end());

	int n;
	string s;
	while (cin >> n) {
		if (n == 0) break;
		if (n % 100 == 11 || n % 100 == 12 || n % 100 == 13) s = "th";
		else if (n % 10 == 1) s = "st";
		else if (n % 10 == 2) s = "nd";
		else if (n % 10 == 3) s = "rd";
		else s = "th";
		cout << "The " << n << s << " humble number is " << v[n-1] << ".\n";
	}
	return 0;
}

Solution2

We have: