## Cut Tiles

### Problem

Enzo is doing renovation for his new house. The most difficult part is to buy exactly the right number of tiles. He wants**N**tiles of different sizes. Of course they have to be cut from the tiles he bought. All the required tiles are square. The lengths of side of the tiles are

**2**,

^{S1}**2**, ...,

^{S2}**2**. He can only buy a lot of tiles sized

^{SN}**M***

**M**, and he decides to only cut tiles parallel to their sides for convenience. How many tiles does he need to buy?

### Input

The first line of the input gives the number of test cases:**T**.

**T**lines follow. Each line start with the number

**N**and

**M**, indicating the number of required tiles and the size of the big tiles Enzo can buy.

**N**numbers follow:

**S**,

_{1}**S**, ...

_{2}**S**, showing the sizes of the required tiles.

_{N}### Output

For each test case, output one line containing "Case #x: y", where x is the test case number (starting from 1) and y is the number of the big tiles Enzo need to buy.
The solution for the problem is written in Java

import java.io.File; import java.util.Arrays; import java.util.Comparator; import java.util.Scanner; public class CutTiles { Scanner in; int T, N, M; Integer[] S; int solve() { byte limit = (byte) Math.floor(Math.log(M)/Math.log(2)); int tiles = 1, newN = 0; double eaten = 0; N = in.nextInt(); M = in.nextInt(); S = new Integer[N]; for (int i=0; i<N; i++) { S[i] = in.nextInt(); assert S[i] <= limit; } Arrays.sort(S, new Comparator<Integer>() { public int compare(Integer a, Integer b) { return b-a; } }); for (int i=0; i<N; i++) { long powS = (long) Math.pow(2, S[i]); long sqs = (M / powS) * (M / powS); if (sqs - eaten/powS/powS < 1) { if (newN == 0) tiles++; S[newN++] = S[i]; } else eaten += powS * powS; if (i == N-1 && newN > 0) { N = newN; eaten = newN = 0; i = -1; } } return tiles; } void input() { in = new Scanner(System.in); T = in.nextInt(); for (int test=1; test<=T; test++) { System.out.print("Case #"+test+": "); System.out.println(solve()); } } public static void main(String[] args) { new CutTiles().input(); } }

The complexity of the program is

**O(no. of tiles required * N)**

## No comments:

## Post a Comment