Problem

A high school decided to go on a field trip for two nights and three days. There are three types of rooms in the hotel where students can stay. The capacity of the room (the number of beds in the room) are given, and it is assumed that the number of rooms are unlimited. The students are assigned to these rooms, but we do not want to have any empty beds in all assigned rooms.

For example, if the three types (capacity) of the room are five (type1), nine(type2), or twelve(type3), and the entire student is 113, you can book four type1, five type2, and four type3 rooms without an empty bed in any room. However, if the room types are like three, six, and nine for type 1, 2, and 3 respectively, and the whole student is 112, it is impossible to assign a room without an empty bed.

Write a program that determines if room assignments are possible so that there are no empty beds in all assigned rooms when there are three numbers representing the capacity of the three types of room and one number representing the total number of students. It is allowed to use only one type or two types of rooms without using all three types of rooms.

Input and output should be through a text file. The file name should be “input.txt” and “output.txt”

Input file & Output file Format

A = capacity of room type 1

B = capacity of room type 2

C = capacity of room type 3

N = Total number of students

T = number of test case

S = 1 or 0

Input file

A B C N

A B C N

.

.

.

Output file

S

S

.

.

.

Example

Input file

5 9 12 113

3 6 9 112

Output file

1

0

Solution

So, this sounds very familiar to that change problem, doesn't it? Let's use some dynamic programming to solve this! What does it mean for 113 to fit in rooms with 5 beds, 9 beds and 12 beds? Note that we have infinite number of rooms. We can fill 4 rooms with 5 beds, 5 rooms with 9 beds, and 4 rooms with 12 beds for a total of 4x5+5x9+4x12 = 113! Since all beds are filled we write a 1. Now, let's break down the problem into smaller pieces. What does it mean to fill rooms with 113 students? What about 108 (113 - 5), 104 (113 - 9), or 101 (113 - 12) students? We can grab all the students and say "If we use one room of 5 we still have 108, can we fill those? What if instead we use a room of 9?". See the pattern? I calculated if rooms from 0 to the number of students were fillable. For the previous example, we can check if 108 is fillable, if so, then 113 is also fillable since it's 5 away, and we can use a room of 5 capacity.

import java.io.File;
import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.Scanner;

public class Main {
    static int canFit(int capacity1, int capacity2, int capacity3, int students) {
        int[] capacities = {capacity1, capacity2, capacity3};
        int[] savedValues = new int[students + 1];

        // Base case
        savedValues[0] = 1;

        for (int i = 1; i <= students; i++) {
            for (int c = 0, coinsLength = capacities.length; c < coinsLength; c++) {
                int capacity = capacities[c];
                if (capacity <= i) {
                    // take away the current capacity
                    int diff = savedValues[i - capacity];
                    if (diff != 0) {
                        // difference exists, so therefore this is possible
                        savedValues[i] = 1;
                        break;
                    }
                }
            }
        }
        return savedValues[students];
    }

    public static void main(String[] args) throws IOException {
        Scanner s = new Scanner(new File("input.txt"));

        FileWriter fw = new FileWriter("output.txt");
        PrintWriter pw = new PrintWriter(fw);

        while (s.hasNextLine()) {
            int capacity1 = s.nextInt();
            int capacity2 = s.nextInt();
            int capacity3 = s.nextInt();

            int students = s.nextInt();

            pw.println(canFit(capacity1, capacity2, capacity3, students));
        }

        s.close();
        pw.close();
    }
}

Disclaimer: Don't copy paste the code if you're going to submit! Change it to be yours! I am not responsible if you get in any trouble. This post is only meant for me to come back to later when practicing. It is not in my control to if anyone comes and copies it. Have a good day.