Archive

Archive for August, 2015

[URI ONLINE JUDGE] – 1030– Flavious Josephus Legend

August 31st, 2015 No comments

The Josephus problem is this way known because of the Flavius Josephus legend, a Jewish historian living in the 1st century. According to Josephus’ account of the siege of Yodfat, he and his 40 comrade soldiers were trapped in a cave, the exit of which was blocked by Romans. They chose suicide over capture and decided that they would form a circle and start killing themselves using a step of three. Josephus states that by luck or maybe by the hand of God, he remained the last and gave up to the Romans.”

Input

There are NC (1 ≤ NC ≤ 30 ) test cases. In each input test case there will be a pair of positive integer numbers n (1 ≤ n ≤ 10000 ) and k (1 ≤ k ≤ 1000). The number n represent the quantity of people in the circle, numbered from 1 to n. The number k represents the size of step between two men in the circle.

Follow an example with 5 men and step 2: In this example the remaining element is 3.

The data must be read from standard input.

Output

For each test case we will have a line of output, presenting the in the following format: Case n: m always with a space before n and m.

Sample InputSample Output
3
5 2
6 3
1234 233
Case 1: 3
Case 2: 1
Case 3: 25

my solution:

[code language=”cpp”]

#include <iostream>
#include <vector>

using namespace std;

int josephus(int n, int k){
if (n == 1) return 1;
return ((josephus(n – 1, k) + k – 1) % n) + 1;
}

int main(){
unsigned int k, n;
int c, q;

cin >> q;
c = 0;
while (++c <= q){ cin >> n >> k;
cout << "Case " << c << ": " << josephus(n, k) << endl;
}

return 0;
}

[/code]

Java – Base64 Encode (Mã hóa base64)

August 3rd, 2015 No comments

how to encode a byte array to base64 in java?

[code language=”java”]

<pre>private static final char[] legalChars = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/"
.toCharArray();

/**
* @param data
* @return
*/
public String encode(byte[] data) {
int start = 0;
int len = data.length;
StringBuffer buf = new StringBuffer(data.length * 3 / 2);

int end = len – 3;
int i = start;
int n = 0;

while (i <= end) {
int d = ((((int) data[i]) & 0x0ff) << 16)
| ((((int) data[i + 1]) & 0x0ff) << 8) | (((int) data[i + 2]) & 0x0ff); buf.append(legalChars[(d >> 18) & 63]);
buf.append(legalChars[(d >> 12) & 63]);
buf.append(legalChars[(d >> 6) & 63]);
buf.append(legalChars[d & 63]);

i += 3;

if (n++ >= 14) {
n = 0;
buf.append(" ");
}
}

if (i == start + len – 2) {
int d = ((((int) data[i]) & 0x0ff) << 16)
| ((((int) data[i + 1]) & 255) << 8); buf.append(legalChars[(d >> 18) & 63]);
buf.append(legalChars[(d >> 12) & 63]);
buf.append(legalChars[(d >> 6) & 63]);
buf.append("=");
} else if (i == start + len – 1) {
int d = (((int) data[i]) & 0x0ff) << 16; buf.append(legalChars[(d >> 18) & 63]);
buf.append(legalChars[(d >> 12) & 63]);
buf.append("==");
}

return buf.toString();
}</pre>

[/code]

Categories: Algorithms Tags: