10141 - Request for Proposal

[brianfry713]

Leave a blank line between the output for each pair of RFPs. Don't print an extra blank line at the end.

[Dr. Dre]

For everyone who is coming here due to getting TLE, this comment really helped me out

Problem mentioned: a line naming the proposal (up to 80 characters terminated by end of line). so the proposal name may contain white spaces...

In other words, make sure you are using a method that reads an entire line to read the proposal name. For java users using

Code: Select all

Stringtokenizer

, or c/c++ users using

Code: Select all

cin >> / scanf("%s)

, this means using (in order - suggestion)

Code: Select all

BufferedReader.readLine()

,

Code: Select all

getline(istreamObj, string) / scanf("%[^\n]")

[engj]

Hi, I keep getting a Runtime Error for the following code:

Code: Select all

import java.io.*;
import java.util.*;
class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        Solver solver = new Solver();
        solver.solve(in, out);
    }

    private static class Solver {
        public void solve(InputReader in, PrintWriter out) {
            int k = 1;
            while (true) {
                int n = in.nextInt();
                int nP = in.nextInt();
                if (n == 0 && nP == 0)
                    System.exit(0);
                for (int i = 0; i < n; i++) {
                    in.next();
                    while (in.tokenizer.hasMoreTokens())
                        in.tokenizer.nextToken();
                }
                int bC =  0;
                double bP = Double.MAX_VALUE;
                String bN = "";
                for (int i = 0; i < nP; i++) {
                    String cmp = in.next();
                    double p = in.nextDouble();
                    int c = in.nextInt();
                    if (c > bC || (p < bP && c == bC)) {
                        bC = c;
                        bP = p;
                        bN = cmp;
                    }
                    for (int j = 0; j < c; j++) {
                        in.next();
                        while (in.tokenizer.hasMoreTokens())
                            in.tokenizer.nextToken();
                    }
                }
                if (k != 1)
                    System.out.println();
                System.out.println("RFP #" + k);
                System.out.println(bN);
                k++;
            }
        }
    }

    private static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream));
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    String line = reader.readLine();
                    tokenizer = new StringTokenizer(line);
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public double nextDouble() {
            return Double.parseDouble(next());
        }
    }
}

All programs must begin in a static main method in a Main class.

Check.

Do not use public classes: even Main must be non public to avoid compile error.

Check.

Be sure that your program returns a 0 code to the shell.

Check.

Use buffered I/O to avoid time limit exceeded due to excesive flushing.

Check.

Leave a blank line between the output for each pair of RFPs. Don't print an extra blank line at the end.

Check.




Any ideas?

[brianfry713]

The name of the proposal may have spaces.

[engj]

Thanks Brian, that fixed the Run-time error issue but now I have a WA. I tried all the test cases I could think of.

Code: Select all

import java.io.*;
import java.util.*;
class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        Solver solver = new Solver();
        solver.solve(in, out);
    }

    private static class Solver {
        public void solve(InputReader in, PrintWriter out) {
            int k = 1;
            while (true) {
                int n = in.nextInt();
                int nP = in.nextInt();
                if (n == 0 && nP == 0)
                    System.exit(0);
                for (int i = 0; i < n; i++) {
                    in.next();
                    while (in.tokenizer.hasMoreTokens())
                        in.tokenizer.nextToken();
                }
                int bC =  0;
                double bP = Double.MAX_VALUE;
                String bN = "";
                for (int i = 0; i < nP; i++) {
                    String cmp = in.next();
                    while (in.tokenizer.hasMoreTokens())
                        cmp += " " + in.tokenizer.nextToken();
                    double p = in.nextDouble();
                    int c = in.nextInt();
                    if (c > bC || (p < bP && c == bC)) {
                        bC = c;
                        bP = p;
                        bN = cmp;
                    }
                    for (int j = 0; j < c; j++) {
                        in.next();
                        while (in.tokenizer.hasMoreTokens())
                            in.tokenizer.nextToken();
                    }
                }
                System.out.println();
                System.out.println("RFP #" + k);
                System.out.println(bN);
                k++;
            }
        }
    }

    private static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream));
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    String line = reader.readLine();
                    tokenizer = new StringTokenizer(line);
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public double nextDouble() {
            return Double.parseDouble(next());
        }
    }
}

[brianfry713]

Try reading line by line.
Maybe a proposal name has multiple spaces.

[atanu.barai]

Damm!! Did not notice that!! Now got AC

Code: Select all

Removed After AC
}

[brianfry713]

Input:

Code: Select all

1 2
engine
Chevrolet
20000.00 1
engine
Cadillac
70000.00 1
engine
0 0

Correct output:

Code: Select all

RFP #1
Chevrolet

[CempPS]

Leave a blank line between the output for each pair of RFPs. Don't print an extra blank line at the end.

Thanks, its rididulous but now AC

[milesstevenson]

For some odd reason, my code is getting WA. Is there improper input in uDebug for this problem, also? This code passes on all cases, except for the uDebug generated input, where n is 0. The specs for the problem say 0 < n, though. Any help would be much appreciated.

Code: Select all

import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.io.IOException;
import java.util.StringTokenizer;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 * @author Miles Stevenson
 */
public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputReader in = new InputReader(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		Task10141 solver = new Task10141();
		solver.solve(1, in, out);
		out.close();
	}
}

class Task10141 {
    public void solve(int testNumber, InputReader in, PrintWriter out) {
        int n = in.nextInt(), p = in.nextInt();
        int m = 1;

        while (n!= 0 || p!=0)
        {
            if (m > 1)
                out.println();
            for (int i = 0; i < n; i++) {
                in.nextLine();
            }
            PriorityQueue<Proposal> pq = new PriorityQueue<Proposal>(p, new Comparator<Proposal>() {
                public int compare(Proposal o1, Proposal o2) {
                    if (o1.getCompliance() == o2.getCompliance()) {
                        if (o1.getPrice() == o2.getPrice())
                            return o1.getIndex().compareTo(o2.getIndex());
                        else
                            return o1.getPrice().compareTo(o2.getPrice());
                    }
                    return o2.getCompliance().compareTo(o1.getCompliance());
                }
            });
            for (int i = 0; i < p; i++)
            {
                String name = in.nextLine();
                double price = in.nextDouble();
                int met = in.nextInt();
                pq.add(new Proposal(name, price, met, i));
                for (int j = 0; j < met; j++) {
                    in.nextLine();
                }
            }

            out.println("RFP #" + m);
            out.println(pq.peek().getName());
            m++;
            n = in.nextInt();
            p = in.nextInt();
        }
    }
}

class Proposal {
    private final String p;
    private final Double d;
    private final Integer index;
    private final Double compliance;
    public Proposal(String p, double d, double r, int index)
    {
        this.index = index;
        this.p = p;
        this.d = d;
        this.compliance = r;
    }

    public String getName()
    {
        return p;
    }

    public Integer getIndex() {
        return index;
    }

    public Double getPrice()
    {
        return d;
    }

    public Double getCompliance()
    {
        return compliance;
    }
}

class InputReader {
    private BufferedReader reader;
    private StringTokenizer tokenizer;

    public InputReader(InputStream stream) {
        reader = new BufferedReader(new InputStreamReader(stream));
        tokenizer = null;
    }

    public String nextLine() {
        try {
            return reader.readLine();
        } catch (IOException e) {
            throw new RuntimeException(e);
        }
    }

    public String next() {
        try {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                tokenizer = new StringTokenizer(nextLine());
            }
            return tokenizer.nextToken();
        } catch (NullPointerException e) {
            return null;
        }
    }

    public int nextInt() {
        return Integer.parseInt(next());
    }

    public double nextDouble() {
        return Double.parseDouble(next());
    }
}

[luhego]

Hello everyone,
I am stuck on this problem. I have tried many variations but the response is the same Time Limit.
Here is my current code.

Code: Select all

#include <cstdio>
#include <iostream>
#include <string>

using namespace std;

int main() {
    int n, p, r, curr_r, i, j, k;
    float d, curr_d;
    string toignore, name, curr_name;

    for(i = 1;; i++) {
        scanf("%d %d\n", &n, &p);
        if(n == 0 && p == 0) break;
        if(i > 1) printf("\n");

        for(j = 0; j < n; j++)
            getline(cin, toignore);

        curr_r = 0;
        curr_d = 9999999;
        for(j = 0; j < p; j++) {
            getline(cin, name);
            scanf("%f %d\n", &d, &r);

            for(k = 0; k < r; k++)
                getline(cin, toignore);

            if(r > curr_r) {
                curr_r = r;
                curr_name = name;
                curr_d = d;
            } else if(r == curr_r && d < curr_d) {
                curr_name = name;
                curr_d = d;
            }
        }
        cout<<"RFP #"<<i<<endl;
        cout<<curr_name<<endl;
    }
}

Any kind of help would be greatly appreciated. Thanks for your time.

[zapstar]

For guys working with Xcode, if you try to paste your input onto a file inside Xcode it automatically trims white spaces in the front and the end of the lines... this led me to believe my code was wrong when I pasted my program's output on uDebug for diff. (instead do pbpaste > input.txt and then compare output)

Also it is very important that you should not print an extra newline only for the last line. Better to check such things by running cksum on the output files

[zholnin]

This statement is likely incorrect:

"All requirements are from the RFP requirement list, and no requirements are duplicated."

My input was finally accepted only after I removed checks preventing from counting duplicate features and counting features which are not on requirements list.

So beware.

[steventhai]

Hi all,

I am getting WA, but I checked my input with uDebug; and it passes.

Code: Select all

import java.io.FileInputStream;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;
import java.util.TreeMap;

/**
 * 10141 - Request for Proposal
 */
class RequestForProposal {

    public static void main(String[] args) throws Throwable {
        Scanner scanner = new Scanner(new FileInputStream("RequestForProposal.txt"));
        
        int n = scanner.nextInt(); // num of requirements.
        int rfp = 1;

        while (n != 0) {

            int p = scanner.nextInt(); // number of proposals.

            Set<String> requirements = new HashSet<>();
            scanner.nextLine();
            for (int i = 0; i < n; i++) {
                requirements.add(scanner.nextLine());
            }

            String[] proposalNames = new String[p];
            double[] prices = new double[p];
            int[] metReqs = new int[p];
            for (int i = 0; i < p; i++) {
                proposalNames[i] = scanner.nextLine();
                prices[i] = scanner.nextDouble();
                int r = scanner.nextInt();
                
                scanner.nextLine();

                int met = 0;
                for (int j = 0; j < r; j++) {
                    if (requirements.contains(scanner.nextLine())) {
                        met++;
                    }
                }
                metReqs[i] = met;
            }

            String proposal = process(proposalNames, prices, metReqs);

            // Output.
            if (rfp == 1) {
                System.out.printf("RFP #%d%n%s", rfp++, proposal);
            } else {
                System.out.printf("%n%nRFP #%d%n%s", rfp++, proposal);
            }

            n = scanner.nextInt(); // num of requirements.
        }
        
        scanner.close();
    }

    private static String process(String[] proposalNames, double[] prices, int[] metReqs) {
        
        List<Integer> mets = new ArrayList<>();
        String proposal = "";
        
        int max = metReqs[0];
        int length = metReqs.length;
        mets.add(0);
        for (int i = 1; i < length; i++) {
            if (max < metReqs[i]) {
                mets.clear();
                max = metReqs[i];
                mets.add(i);
            } else if (max == metReqs[i]) {
                mets.add(i);
            }
        }

        double min = prices[mets.get(0)];
        int index = mets.get(0);
        for (int i = 1; i < mets.size();i++) {
            double met = prices[mets.get(i)];
            if (met < min) {
                min = met;
                index = mets.get(i);
            }
        }

        return proposalNames[index];
    }
}

Any corner cases that I didn't handle?

Thanks.

[iqbalnaved]

Anybody solved this problem using Python 3 ? Having issues with trailing spaces getting automatically trimmed by parser. It seems f.readline() removes trailing spaces. Searched for a solution everywhere but cannot seemed to find any.