Submission #855097


Source Code Expand

Copy
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.NoSuchElementException;

public class Main {
	private static void solve() {
		int n = nei();
		int a = nei();
		int[] x = new int[n];
		for (int i = 0; i < n; i++) {
			x[i] = nei();
		}
		if (n > 16) {
			out(1919810);
			return;
		}
		int max = (1 << n) - 1;
		long res = 0;
		for (int i = 1; i <= max; i++) {
			int bit = 1;
			int sum = 0;
			int num = 0;
			for (int j = 0; j < n; j++) {
				if ((i & bit) != 0) {
					sum += x[j];
					num++;
				}
				bit <<= 1;
			}
			if (sum == a * num)
				res++;
		}
		out(res);
	}

	static BigInteger combination(int a, int b, BigInteger mod) {
		BigInteger q = BigInteger.ONE;
		BigInteger p = BigInteger.ONE;
		for (int i = a - b + 1; i <= a; i++) {
			q = q.multiply(BigInteger.valueOf(i)).mod(mod);
		}
		for (int j = 1; j <= b; j++) {
			p = p.multiply(BigInteger.valueOf(j)).mod(mod);
		}
		return q.multiply(p.modInverse(mod)).mod(mod);
	}

	static int abs(int x) {
		return x < 0 ? -x : x;
	}

	static int gcd(int x, int y) {
		if (x < y) {
			x ^= y;
			y ^= x;
			x ^= y;
		}
		int z = x % y;
		if (z == 0)
			return y;
		return gcd(y, z);
	}

	static int clamp(int a, int min, int max) {
		return a < min ? min : a > max ? max : a;
	}

	static int max(int a, int b) {
		return a > b ? a : b;
	}

	static int min(int a, int b) {
		return a < b ? a : b;
	}

	static long max(long a, long b) {
		return a > b ? a : b;
	}

	static long min(long a, long b) {
		return a < b ? a : b;
	}

	static void out(String val) {
		IO.out(val);
	}

	static void out(int val) {
		IO.out(String.valueOf(val));
	}

	static void out(long val) {
		IO.out(String.valueOf(val));
	}

	static void out(char val) {
		IO.out(String.valueOf(val));
	}

	static void out(float val) {
		IO.out(String.valueOf(val));
	}

	static void out(double val) {
		IO.out(String.valueOf(val));
	}

	static void out(boolean val) {
		IO.out(String.valueOf(val));
	}

	static String next() {
		return IO.next();
	}

	static int nei() {
		return IO.nextInt();
	}

	static long nel() {
		return IO.nextLong();
	}

	static int parseInt(String val) {
		return Integer.parseInt(val);
	}

	static int parseInt(char val) {
		return Integer.parseInt(String.valueOf(val));
	}

	static long parseLong(String val) {
		return Long.parseLong(val);
	}

	public static void main(String[] args) {
		solve();
		IO.flush();
	}
}

final class UnionFind {
	int[] data;

	UnionFind(int n) {
		data = new int[n];
		for (int i = 0; i < n; i++) {
			data[i] = -1;
		}
	}

	boolean union(int x, int y) {
		x = root(x);
		y = root(y);
		if (x == y)
			return false;
		if (data[y] < data[x]) {
			x ^= y;
			y ^= x;
			x ^= y;
		}
		data[x] += data[y];
		data[y] = x;
		return true;
	}

	boolean find(int x, int y) {
		return root(x) == root(y);
	}

	int root(int x) {
		return data[x] < 0 ? x : (data[x] = root(data[x]));
	}

	int size(int x) {
		return -data[root(x)];
	}
}

final class IO {
	private static final InputStream in = System.in;
	private static final PrintWriter out = new PrintWriter(System.out, false);
	private static final byte[] buffer = new byte[1024];
	private static int ptr = 0;
	private static int len = 0;

	private static boolean hasNextByte() {
		if (ptr < len)
			return true;
		ptr = 0;
		try {
			len = in.read(buffer);
		} catch (IOException e) {
			e.printStackTrace();
		}
		return len > 0;
	}

	private static int readByte() {
		if (hasNextByte())
			return buffer[ptr++];
		else
			return -1;
	}

	static boolean hasNext() {
		byte c;
		while (hasNextByte() && ((c = buffer[ptr]) < '!' || c > '~'))
			ptr++;
		return hasNextByte();
	}

	static String next() {
		if (!hasNext())
			throw new NoSuchElementException();
		StringBuilder sb = new StringBuilder();
		int b = readByte();
		while (b >= '!' && b <= '~') {
			sb.append((char) b);
			b = readByte();
		}
		return sb.toString();
	}

	static long nextLong() {
		if (!hasNext())
			throw new NoSuchElementException();
		long n = 0;
		int sign = 1;
		int b = readByte();
		if (b == '-') {
			sign = -1;
			b = readByte();
		}
		if (b < '0' || '9' < b)
			throw new NumberFormatException();
		while (true) {
			if ('0' <= b && b <= '9')
				n = n * 10 + b - '0';
			else if (b == -1 || b < '!' || b > '~')
				return n * sign;
			else
				throw new NumberFormatException();
			b = readByte();
		}
	}

	static int nextInt() {
		if (!hasNext())
			throw new NoSuchElementException();
		int n = 0;
		int sign = 1;
		int b = readByte();
		if (b == '-') {
			sign = -1;
			b = readByte();
		}
		if (b < '0' || '9' < b)
			throw new NumberFormatException();
		while (true) {
			if ('0' <= b && b <= '9')
				n = n * 10 + b - '0';
			else if (b == -1 || b < '!' || b > '~')
				return n * sign;
			else
				throw new NumberFormatException();
			b = readByte();
		}
	}

	static void out(String val) {
		out.println(val);
	}

	static void flush() {
		out.flush();
	}
}

Submission Info

Submission Time
Task C - Tak and Cards
User saharan
Language Java8 (OpenJDK 1.8.0)
Score 200
Code Size 5241 Byte
Status WA
Exec Time 501 ms
Memory 8404 KB

Judge Result

Set Name Sample Subtask1 All
Score / Max Score 0 / 0 200 / 200 0 / 100
Status
AC × 3
WA × 1
AC × 12
AC × 12
WA × 12
Set Name Test Cases
Sample example_01.txt, example_02.txt, example_03.txt, example_04.txt
Subtask1 example_01.txt, example_02.txt, example_03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt
All example_01.txt, example_02.txt, example_03.txt, example_04.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt
Case Name Status Exec Time Memory
example_01.txt AC 150 ms 8020 KB
example_02.txt AC 153 ms 7892 KB
example_03.txt AC 154 ms 7892 KB
example_04.txt WA 501 ms 7892 KB
subtask1_01.txt AC 177 ms 8148 KB
subtask1_02.txt AC 166 ms 8276 KB
subtask1_03.txt AC 170 ms 8276 KB
subtask1_04.txt AC 182 ms 8404 KB
subtask1_05.txt AC 166 ms 8276 KB
subtask1_06.txt AC 158 ms 7892 KB
subtask1_07.txt AC 144 ms 8020 KB
subtask1_08.txt AC 166 ms 8276 KB
subtask1_09.txt AC 162 ms 8276 KB
subtask2_01.txt WA 162 ms 7888 KB
subtask2_02.txt WA 153 ms 8016 KB
subtask2_03.txt WA 150 ms 7892 KB
subtask2_04.txt WA 154 ms 7892 KB
subtask2_05.txt WA 153 ms 7892 KB
subtask2_06.txt WA 150 ms 7892 KB
subtask2_07.txt WA 150 ms 7892 KB
subtask2_08.txt WA 150 ms 7892 KB
subtask2_09.txt WA 154 ms 8016 KB
subtask2_10.txt WA 153 ms 7884 KB
subtask2_11.txt WA 161 ms 7888 KB