The rule of Binary Lottery is listed as follows:
You can choose m (0 <= m <= 20) distinct numbers to buy ranging from 0 ~ 19, and buying m numbers costs m^2 dollars. Let buying set be the numbers you buy.
The are two kinds of prizes in Binary Lottery : ordinary prize and special prize. Each time the lottery draws, there will be two sets of numbers : ordinary set and special set. Each set contains distinct numbers ranging from 0 ~ 19.
Buying set, ordinary set, and special set are expressed as a 32-bit integer, respectively. Let's say buying set contains a0, a1, ..., am and the integer representing it is A. Then the a0-th, a1-th, ..., am-th bit counted from the rightmost in A are 1 and the rest bits in A are 0. For example if buying set = {1, 2, 7}, then it will be expressed as 134, since 134 = (10000110)_2. Same way is used to represent ordinary set and special set.
For ordinary prize, let k be the number of numbers buying set and ordinary set have in common. The prize you win is k^3 dollars.
For special prize, if the buying set is exactly the same as the special set, then you win sp dollars.
Given the daily result of the Binary Lottery and the numbers you buy, please calculate the money you make every day. The money you make = (the sum of prize you win) - (the money you spend to buy m numbers).
Suggest way of implementing
It is encouraged to split you program in to functions (instead of stuffing everything in main function). The following is just for reference.
Use the link to download code, or you will get some error if you just copy the code below.
(http://140.114.86.238/problem/partial/12442.c/ to download code)
#include <stdio.h> /* TODO: * count number of '1' bit in an integer * @param x : integer to be counted * @return number of '1' in x */ int getOneNum(int x) { } /* TODO: * cost to buy numbers in B * @param B : bit vector of bought numbers * @return (number of ones in B)^2 */ int cost(int B) { } /* TODO: * calulate money win from ordinary prize * @param B : bit vector of bought numbers * @param O : bit vector of ordinary set * @return money win from ordinary prize */ int ordinary(int B, int O) { } /* TODO: * calulate money win from special prize * @param B : bit vector of bought numbers * @param S : bit vector of special set * @param sp : money for special prize * @return money win from special prize */ int special(int B, int S, int sp) { } int main() { int D, B, O, S, sp; scanf("%d", &D); while(D--) { scanf("%d %d %d %d",&B, &O, &S, &sp); // TODO // calculate money win in a day and output } return 0; }
The input is as the following form :
D B_1 O_1 S_1 sp_1 B_2 O_2 S_2 sp_2 ... B_D O_D S_D sp_D
The first line D is an integer, meaning that you are given D days of data.
There are 4 integers on each line, being the data on each day. For i-th line, B_i is the integer representing the numbers you buy, O_i is the ordinary set, S_i is the special set, sp_i is the special prize on that day.
1 <= D <= 1000
0 <= B_i, O_i, S_i < 2^20
0 <= sp_i <= 2000
For each day, output the money you make. Remember to add a new line character in each line.