10141 - Request for Proposal
Moderator: Board moderators
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 10141 - Request for Proposal
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!
Re:
For everyone who is coming here due to getting TLE, this comment really helped me out
, or c/c++ users using , this means using (in order - suggestion) ,
In other words, make sure you are using a method that reads an entire line to read the proposal name. For java users usingTariq 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...
Code: Select all
Stringtokenizer
Code: Select all
cin >> / scanf("%s)
Code: Select all
BufferedReader.readLine()
Code: Select all
getline(istreamObj, string) / scanf("%[^\n]")
Re: 10141 - Request for Proposal
Hi, I keep getting a Runtime Error for the following code:
Any ideas?
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());
}
}
}
Check.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.
Any ideas?
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 10141 - Request for Proposal
The name of the proposal may have spaces.
Check input and AC output for thousands of problems on uDebug!
Re: 10141 - Request for Proposal
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());
}
}
}
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 10141 - Request for Proposal
Try reading line by line.
Maybe a proposal name has multiple spaces.
Maybe a proposal name has multiple spaces.
Check input and AC output for thousands of problems on uDebug!
-
- New poster
- Posts: 8
- Joined: Fri Feb 28, 2014 9:21 am
Re: 10141 - Request for Proposal
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.
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 10141 - Request for Proposal
Input:Correct output:
Code: Select all
1 2
engine
Chevrolet
20000.00 1
engine
Cadillac
70000.00 1
engine
0 0
Code: Select all
RFP #1
Chevrolet
Check input and AC output for thousands of problems on uDebug!
Re: 10141 - Request for Proposal
Thanks, its rididulous but now ACbrianfry713 wrote:Leave a blank line between the output for each pair of RFPs. Don't print an extra blank line at the end.
-
- New poster
- Posts: 10
- Joined: Sat Oct 11, 2014 2:47 pm
Re: 10141 - Request for Proposal
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());
}
}
Re: 10141 - Request for Proposal
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.
Any kind of help would be greatly appreciated. Thanks for your time.
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;
}
}
Re: 10141 - Request for Proposal
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
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
Re: 10141 - Request for Proposal
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.
"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.
-
- New poster
- Posts: 5
- Joined: Thu May 11, 2017 5:06 pm
Re: 10141 - Request for Proposal
Hi all,
I am getting WA, but I checked my input with uDebug; and it passes.
Any corner cases that I didn't handle?
Thanks.
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];
}
}
Thanks.
-
- New poster
- Posts: 1
- Joined: Tue Feb 05, 2013 2:18 pm
Re: 10141 - Request for Proposal
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. ![:(](./images/smilies/icon_frown.gif)
![:(](./images/smilies/icon_frown.gif)