bobo was given a long sequence of integers
The first line of the input contains an integer
For each test case, the first line contains an integer
(
For each test case, print a single integer which denotes the result.
1
2
1 2
Case #1: 0
import java.io.*; | |
import java.math.*; | |
import java.util.*; | |
public class Brute { | |
public void run() { | |
try { | |
int testCount = reader.nextInt(); | |
for (int t = 1; t <= testCount; ++ t) { | |
int n = reader.nextInt(); | |
int[] a = new int[n]; | |
for (int i = 0; i < n; ++ i) { | |
a[i] = reader.nextInt(); | |
} | |
int result = 0; | |
for (int i = 0; i < n; ++ i) { | |
int sum = 0; | |
for (int j = i; j < n; ++ j) { | |
sum += a[j]; | |
result ^= sum; | |
} | |
} | |
writer.println(String.format("Case #%d: %d", t, result)); | |
} | |
} catch (IOException ex) { | |
assert false; | |
} | |
writer.close(); | |
} | |
Brute() { | |
reader = new InputReader(System.in); | |
writer = new PrintWriter(System.out); | |
} | |
public static void main(String[] args) { | |
new Brute().run(); | |
} | |
private void debug(Object...os) { | |
System.err.println(Arrays.deepToString(os)); | |
} | |
private InputReader reader; | |
private PrintWriter writer; | |
} | |
class InputReader { | |
InputReader(InputStream in) { | |
reader = new BufferedReader(new InputStreamReader(in)); | |
tokenizer = new StringTokenizer(""); | |
} | |
private String next() throws IOException { | |
while (!tokenizer.hasMoreTokens()) { | |
tokenizer = new StringTokenizer(reader.readLine()); | |
} | |
return tokenizer.nextToken(); | |
} | |
public Integer nextInt() throws IOException { | |
return Integer.parseInt(next()); | |
} | |
private BufferedReader reader; | |
private StringTokenizer tokenizer; | |
} |
from random import seed, randint, shuffle | |
ns = [] | |
for i in xrange(20): | |
ns.append(100) | |
for i in xrange(6): | |
ns.append(1000) | |
for i in xrange(4): | |
ns.append(100000) | |
if __name__ == "__main__": | |
seed(0) | |
print len(ns) | |
for n in ns: | |
print n | |
splits = [0] | |
for i in xrange(n): | |
splits.append(randint(0, 10 ** 6)) | |
splits.sort() | |
a = [] | |
for i in xrange(n): | |
a.append(splits[i + 1] - splits[i]) | |
shuffle(a) | |
print " ".join(map(str, a)) |
import java.io.*; | |
import java.math.*; | |
import java.util.*; | |
public class Main { | |
public void run() { | |
try { | |
int testCount = reader.nextInt(); | |
for (int t = 1; t <= testCount; ++ t) { | |
int n = reader.nextInt(); | |
assert 1 <= n && n <= 100000; | |
int[] a = new int[n + 1]; | |
int sum = 0; | |
for (int i = 0; i < n; ++ i) { | |
a[i] = reader.nextInt(); | |
assert a[i] >= 0; | |
sum += a[i]; | |
} | |
assert sum <= 1000000; | |
for (int i = n - 1; i >= 0; -- i) { | |
a[i] += a[i + 1]; | |
} | |
int result = 0; | |
for (int k = 0; 1 << k <= sum; ++ k) { | |
int total = 0; | |
int[] values = new int[n + 1]; | |
for (int i = 0; i <= n; ++ i) { | |
values[i] = a[i] % (1 << k + 1); | |
} | |
Arrays.sort(values); | |
int[] count = new int[n + 1]; | |
for (int i = n; i >= 0; -- i) { | |
int s = a[i] % (1 << k + 1); | |
for (int j = binarySearch(values, s); j <= n; j += ~j & j + 1) { | |
count[j] ++; | |
} | |
total += query(values, count, s - (1 << k)); | |
total += query(values, count, s + (1 << k)); | |
total -= query(values, count, s); | |
} | |
result |= (total & 1) << k; | |
} | |
writer.println(String.format("Case #%d: %d", t, result)); | |
} | |
} catch (IOException ex) { | |
assert false; | |
} | |
writer.close(); | |
} | |
int binarySearch(int[] list, int item) { | |
int low = -1; | |
int high = list.length - 1; | |
while (low < high) { | |
int middle = low + high + 1 >> 1; | |
if (list[middle] <= item) { | |
low = middle; | |
} else { | |
high = middle - 1; | |
} | |
} | |
return low; | |
} | |
int query(int[] values, int[] count, int item) { | |
int result = 0; | |
for (int i = binarySearch(values, item); i >= 0; i -= ~i & i + 1) { | |
result += count[i]; | |
} | |
return result; | |
} | |
Main() { | |
reader = new InputReader(System.in); | |
writer = new PrintWriter(System.out); | |
} | |
public static void main(String[] args) { | |
new Main().run(); | |
} | |
private void debug(Object...os) { | |
System.err.println(Arrays.deepToString(os)); | |
} | |
private InputReader reader; | |
private PrintWriter writer; | |
} | |
class InputReader { | |
InputReader(InputStream in) { | |
reader = new BufferedReader(new InputStreamReader(in)); | |
tokenizer = new StringTokenizer(""); | |
} | |
private String next() throws IOException { | |
while (!tokenizer.hasMoreTokens()) { | |
tokenizer = new StringTokenizer(reader.readLine()); | |
} | |
return tokenizer.nextToken(); | |
} | |
public Integer nextInt() throws IOException { | |
return Integer.parseInt(next()); | |
} | |
private BufferedReader reader; | |
private StringTokenizer tokenizer; | |
} |
bobo was given a long sequence of integers
The first line of the input contains an integer
For each test case, the first line contains an integer
(
For each test case, print a single integer which denotes the result.
1
2
1 2
Case #1: 0