This is an easy task - just fix the code written by a new lady programmer! paiza paiza

Show me an efficient algorithm!

I’m writing a program for an e-commerce campaign site. The deadline is the end of the holidays. Although I’m half way through writing the program, the code is now looking quite long, and I get the feeling that it's not very efficient and I cannot make the deadline. To smart hacker out there! Please help me!

Share!

The program to write

You will choose two products to buy from a EC site. Find out the maximum total price of combination of two products. The total price of the two products need to be equal to or less than the specified target price.
→Problem details

The half-written program by the new lady programmer Ms. Noda:

Item_a_b = 4500 // total price of a and b
Item_a_c = 500 // total price of a and c
Item_a_d = 2300 // total price of a and d
Item_b_a = 1240 // total price of b and a
Item_b_c = 5020 // total price of b and c
(Snip)
if Item_a_b == campaign_price
  print “Price of A and B is the target price!”
if Item_a_b == campaign_price -10
  print “Price of A and B is closest to target price by 10 USD !”
if Item_a_c == campaign_price
(Snip) 

Your programming skills will be tested. If your code is good, you could even be promoted!

The new lady programmer, Ms. Noda, has been assigned to your team. Improve her code she's written already. Write more efficient code to show your skills as a programmer and for a chance to be promoted.

Based on the details given in the "Details of your task" section at the bottom of this page, implement an efficient program using your favorite language ( Java, C, C++, C#, PHP, Ruby, Python, Perl ). Your submitted code will be run through multiple tests cases, and the number of correct answers and your code’s execution time will be recorded to assign you a score.

  • Your submitted code will be executed multiple times, with only one test case per run.
  • This problem is public to everyone so it does not have a time limit.
  • You can submit the answer multiple times.
  • You are also welcome to write solutions to public blogs, etc.
得点次第で新人女子の反応が変わる!?/提出コードの順位も分かる!/高得点がでたら友達に自慢しよう!

Workflow

STEP1 Write the code

STEP2 Verify its execution

STEP3 Submit the code

STEP4 You will receive your score!

STEP5 Best answers will be published (requiring registration for paiza)
  • * Of the submitted code(based on performance and readability) good codes will be public with nickname.

The best and worst execution time: CASE1

Let's try! Let's compete for the best performance!

Language

Best time

Worst time

Submissions

Java

0.06 sec

5.95 sec

2989

PHP

0.01 sec

9.80 sec

3258

Ruby

0.01 sec

9.47 sec

2213

Python2

0.08 sec

9.70 sec

2519

Perl

0.01 sec

9.42 sec

1937

C

0.01 sec

2.99 sec

3466

C++

0.01 sec

2.78 sec

3367

C#

0.01 sec

6.00 sec

2470

(2014/01/09 update)

* This is a execution time for test case 1(the same test case for all languages). The execution time may varies a bit on each execution.

The best and worst execution time: CASE2

Let's try! Let's compete for the best performance!

Language

Best time

Worst time

Submissions

Java

0.06 sec

5.94 sec

2989

PHP

0.01 sec

9.05 sec

3258

Ruby

0.01 sec

8.14 sec

2213

Python2

0.08 sec

9.99 sec

2519

Perl

0.01 sec

7.98 sec

1937

C

0.01 sec

2.99 sec

3466

C++

0.01 sec

2.96 sec

3367

C#

0.01 sec

6.00 sec

2470

(2014/01/09 update)

* This is a execution time for test case 2(the same test case for all languages). The execution time may varies a bit on each execution.

The best and worst execution time: CASE3

Let's try! Let's compete for the best performance!

Language

Best time

Worst time

Exam num

Java

0.06 sec

5.94 sec

2989

PHP

0.01 sec

9.93 sec

3258

Ruby

0.01 sec

9.48 sec

2213

Python2

0.08 sec

9.93 sec

2519

Perl

0.01 sec

9.96 sec

1937

C

0.01 sec

2.99 sec

3466

C++

0.01 sec

2.96 sec

3367

C#

0.01 sec

6.00 sec

2470

(2014/01/09 update)

※ This is a execution time for test case 2( For C and C++ languages, N is 2.5 times and D is 4 times larger than those for languages )
The execution time may varies a bit on each execution.

Event Rules

  •  You can participate in this campaign and solve the published problem even without being registered as a paiza member. However, please take note of the following important points:
  • *Important Points*
  • (1) You do not need to register as a member; however, you will need to register your e-mail address. Our company will not use your e-mail address for any purpose other than sending you communications about this campaign.
  • (2) Existing members may also participate in this campaign; however, please note that it will not have any impact on your own skills ranking.
  • (3) The copyright for the submitted code is owned by the participant; however, our company have the right to publish said code freely on the company's web site or on social networking sites. For more details, please refer to our company's Terms and Conditions of Use, Article 5, Clause 2.
  • (4) Our company's systems may not be able to store all submitted codes, so we kindly ask all participants to take appropriate measures such as keeping backups, etc.

Details of your task

センパイのソースコード見てみたい!

You are a programmer for an e-commerce site. This site sells many products including cheap items for as low as 10 USD to expensive items for as high as 100,000 USD. Your company, the operator of this e-commerce site, has decided to run a campaign titled "Combine Them and Get Them for Free” to attract new customers. In this campaign, if you purchase a combination of products with a total amount that is closest to a specified target amount, then you can get them for free. The details are as follows:

  • Every day, an integer value m is set as the campaign's target amount of money.
  • The users of the e-commerce site purchase two items (these items can have the same price but they must always buy two). The total price of that purchase must be equal to or less than the campaign's target amount "m" USD. If the prices of the two chosen products add up to the maximum total amount possible, then the user gets them for free.
    For example, let’s assume the campaign's target amount is 23,150 USD and there are 3 products: a pastry for 12,000 USD, a squid for 17,000 USD, a radish for 11,120 USD. If you combine a pastry and a radish (totaling 23,120 USD), then you would get them for free.
  • Your task is to write a program that takes all product prices and the campaign's target amount of "m" USD for each day of the campaign period as input, and calculates the maximum amount closest to "m" USD based on the rules above.
Let's share!

Input Values

The input variables are passed to the program in the following formats:

N D
p_1
p_2
...
p_N
m_1
m_2
...
m_D

N is the total number of products.
D is the number of days of the campaign. *D=the number of m values (the campaign’s target amount of money).
p_i (1 ≦ i ≦ N) is an integer that represents the price of product i; the program gets N values delimited by new lines.
m_j (1 ≦ j ≦ D) is an integer that represents the campaign’s target amount for the j-th day; the program gets D values delimited by line feeds.
Character strings are passed through from standard input. Please see here for methods of passing values from standard input.

Terms

For Java, C#, Perl, PHP, Python, and Ruby, all test cases fulfill the following conditions:
N (1 ≦ N ≦ 200000) *Number of products
D (1 ≦ D ≦ 75) *Number of days of the campaign
p_i (10 ≦ p_i ≦ 1000000) *Product prices
m_j (10 ≦ m_j ≦ 1000000) *Campaign’s target amount of money

For C and C++, all test cases fulfill the following conditions:
N (1 ≦ N ≦ 500000)  *Number of products
D (1 ≦ D ≦ 300)  *Number of days of the campaign
p_i (10 ≦ p_i ≦ 1000000)  *Product prices
m_j (10 ≦ m_j ≦ 1000000) *Campaign’s target amount

*Some test cases are different for C and C++.

Expected output

Please output the maximum value (the total of two products) that is closest to the campaign’s target amount (m) for each day of the campaign. Each value should be in a separate line, so there should be D lines in total (one for each day of the campaign).
Please add a new line at the end, and do not include any unnecessary characters or empty lines.
Example 1: Input
4 3  // There are 4 products and the campaign runs for 3 days
8000 // Price of product 1
4000 // Price of product 2
9000 // Price of product 3
6000 // Price of product 4
3000 // 1st day’s campaign target amount of money
14000 // 2nd day’s campaign target amount of money
10000 // 3rd day’s campaign target amount of money

*The "//" symbols above denote comments in the code.

Example 1: Output
0 // Output 0 if there’s no combination that comes closest to the 1st day’s campaign target amount (3000)
14000 // The total combined amount of money that comes closest to the 2nd day’s campaign target amount (14000)
10000 // The total combined amount of money that comes closest to the 3rd day’s campaign target amount (10000)

*The "//" symbols above denote comments in the code.

Example 2: Input
5 2
4000
3000
1000
2000
5000
10000
3000
Example 2: Output
9000
3000
Example 3: Input
4 1
1000
3000
7000
8000
10000
Example 3: output
10000

Answer

Please enter and submit the code that solves the problem above using the text box below.
You can use the following languages: Java, PHP, Ruby, Perl, Python, C, C#, and C++.

To find out about methods for reading values from standard input, please refer to the sample codes shown in the pages below:

Let's take the challenge!!Choose your best programming language and write some code!

Select language

Select your best programming language!

Code execution result

Once you submit your code, we will run multiple test cases and we will assign you a score based on the code’s execution time and any bugs encountered during the tests.

Handle name (required)
You can use letters and numbers. This information may be displayed on our site when we publish your codes as sample solutions.
E-mail (required)
Your registered e-mail address will not be used outside of paiza online hackathon.
Once you submit your code, we will e-mail your results page.

Facebook

Twitter

Top of page