10141 - Request for Proposal

All about problems in Volume 101. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10141 - Request for Proposal

Post by brianfry713 » Tue Nov 05, 2013 1:34 am

Leave a blank line between the output for each pair of RFPs. Don't print an extra blank line at the end.
Check input and AC output for thousands of problems on uDebug!

Dr. Dre
New poster
Posts: 2
Joined: Tue Jan 07, 2014 6:24 am

Re:

Post by Dr. Dre » Tue Jan 07, 2014 6:29 am

For everyone who is coming here due to getting TLE, this comment really helped me out
Tariq Shahriar wrote: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
New poster
Posts: 2
Joined: Tue Feb 11, 2014 6:47 am

Re: 10141 - Request for Proposal

Post by engj » Tue Feb 11, 2014 7:02 am

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10141 - Request for Proposal

Post by brianfry713 » Wed Feb 12, 2014 12:36 am

The name of the proposal may have spaces.
Check input and AC output for thousands of problems on uDebug!

engj
New poster
Posts: 2
Joined: Tue Feb 11, 2014 6:47 am

Re: 10141 - Request for Proposal

Post by engj » Wed Feb 12, 2014 7:20 am

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10141 - Request for Proposal

Post by brianfry713 » Fri Feb 14, 2014 12:51 am

Try reading line by line.
Maybe a proposal name has multiple spaces.
Check input and AC output for thousands of problems on uDebug!

atanu.barai
New poster
Posts: 8
Joined: Fri Feb 28, 2014 9:21 am

Re: 10141 - Request for Proposal

Post by atanu.barai » Mon Mar 24, 2014 9:06 am

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

Code: Select all

Removed After AC
}
Last edited by atanu.barai on Tue Mar 25, 2014 6:07 am, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10141 - Request for Proposal

Post by brianfry713 » Tue Mar 25, 2014 12:38 am

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
Check input and AC output for thousands of problems on uDebug!

CempPS
New poster
Posts: 1
Joined: Tue Aug 05, 2014 7:24 pm

Re: 10141 - Request for Proposal

Post by CempPS » Thu Aug 07, 2014 5:48 am

brianfry713 wrote: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
New poster
Posts: 10
Joined: Sat Oct 11, 2014 2:47 pm

Re: 10141 - Request for Proposal

Post by milesstevenson » Mon Jun 22, 2015 2:24 pm

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
New poster
Posts: 2
Joined: Tue Oct 01, 2013 1:48 am

Re: 10141 - Request for Proposal

Post by luhego » Mon Aug 17, 2015 4:26 pm

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
New poster
Posts: 2
Joined: Wed Apr 27, 2016 4:47 pm

Re: 10141 - Request for Proposal

Post by zapstar » Fri Apr 29, 2016 12:28 am

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
New poster
Posts: 8
Joined: Thu Aug 21, 2014 12:03 am

Re: 10141 - Request for Proposal

Post by zholnin » Wed Dec 28, 2016 9:33 pm

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
New poster
Posts: 5
Joined: Thu May 11, 2017 5:06 pm

Re: 10141 - Request for Proposal

Post by steventhai » Fri May 12, 2017 10:11 pm

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.

Post Reply

Return to “Volume 101 (10100-10199)”

Who is online

Users browsing this forum: No registered users and 1 guest