Language: C++

# Taro's Shopping

Problem URL: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1616

## Problem

You are required to answer some questions.

For each question, you are given $n$ integers $a_1, a_2, \dots, a_n$ and an integer $m$. You are required to find a pair of element $(a_i, a_j)$ where $a_i \not = a_j$, $a_i + a_j \leq m$ and the value of $a_i + a_j$ is maximal.

If there isn't a pair $(a_i, a_j)$ such that $a_i + a_j \leq m$, then output `NONE`. Otherwise, output $a_i + a_j$.

## Solution

We are required to find the largest pair with sum not exceeding $M$.

Let us assume that we have already chosen one item $a_i$, and we need to choose another item. What is the best item that we can choose? Obviously, it is the **largest number not greater than** $m - a_i$.

How can we do this quickly? As we know that sorting the array doesn't affect the answer, we should first sort the array and use binary search to find the best item.

Therefore, we can answer each query by first choosing each item once in $a_1, a_2, \dots, a_n$, then choose the best item available when one item is already chosen.

The time complexity is $O(n \log n)$ for a single question. As $\sum n < 50000$, this is fast enough to pass the problem.

## Code

```cpp
#include <bits/stdc++.h>
using namespace std;
int a[1000];
int main() {
  while (true) {
    int n, m; cin >> n >> m;
    if (n == 0 && m == 0)
    	break;
    for (int i = 0; i < n; i++)
    	cin >> a[i];
   	sort(a, a + n);
    int ans = 0;
    for (int i = 0; i < n; i++) {
      int p = lower_bound(a, a + n, m - a[i]) - a;
      if (a[i] + a[p] >= m)
        p--;
      if (i == p)
        p--;
      if (p < 0) continue;
      if (a[i] + a[p] > ans)
        ans = a[i] + a[p];
    }
    if (ans)
    	cout << ans << endl;
    else
    	cout << "NONE" << endl;
  }
}
```


Compiler output:
a.cc:1:3: error: invalid preprocessing directive #Taro
    1 | # Taro's Shopping
      |   ^~~~
a.cc:1:7: warning: missing terminating ' character
    1 | # Taro's Shopping
      |       ^
a.cc:5:1: error: stray '##' in program
    5 | ## Problem
      | ^~
a.cc:9:58: error: stray '\' in program
    9 | For each question, you are given $n$ integers $a_1, a_2, \dots, a_n$ and an integer $m$. You are required to find a pair of element $(a_i, a_j)$ where $a_i \not = a_j$, $a_i + a_j \leq m$ and the value of $a_i + a_j$ is maximal.
      |                                                          ^
a.cc:9:157: error: stray '\' in program
    9 | For each question, you are given $n$ integers $a_1, a_2, \dots, a_n$ and an integer $m$. You are required to find a pair of element $(a_i, a_j)$ where $a_i \not = a_j$, $a_i + a_j \leq m$ and the value of $a_i + a_j$ is maximal.
      |                                                                                                                                                             ^
a.cc:9:181: error: stray '\' in program
    9 | For each question, you are given $n$ integers $a_1, a_2, \dots, a_n$ and an integer $m$. You are required to find a pair of element $(a_i, a_j)$ where $a_i \not = a_j$, $a_i + a_j \leq m$ and the value of $a_i + a_j$ is maximal.
      |                                                                                                                                                                                     ^
a.cc:11:13: warning: missing terminating ' character
   11 | If there isn't a pair $(a_i, a_j)$ such that $a_i + a_j \leq m$, then output `NONE`. Otherwise, output $a_i + a_j$.
      |             ^
a.cc:11:13: error: missing terminating ' character
   11 | If there isn't a pair $(a_i, a_j)$ such that $a_i + a_j \leq m$, then output `NONE`. Otherwise, output $a_i + a_j$.
      |             ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
a.cc:13:1: error: stray '##' in program
   13 | ## Solution
      | ^~
a.cc:19:68: warning: missing terminating ' character
   19 | How can we do this quickly? As we know that sorting the array doesn't affect the answer, we should first sort the array and use binary search to find the best item.
      |                                                                    ^
a.cc:19:68: error: missing terminating ' character
   19 | How can we do this quickly? As we know that sorting the array doesn't affect the answer, we should first sort the array and use binary search to find the best item.
      |                                                                    ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
a.cc:21:84: error: stray '\' in program
   21 | Therefore, we can answer each query by first choosing each item once in $a_1, a_2, \dots, a_n$, then choose the best item available when one item is already chosen.
      |                                                                                    ^
a.cc:23:29: error: stray '\' in program
   23 | The time complexity is $O(n \log n)$ for a single question. As $\sum n < 50000$, this is fast enough to pass the problem.
      |                             ^
a.cc:23:65: error: stray '\' in program
   23 | The time complexity is $O(n \log n)$ for a single question. As $\sum n < 50000$, this is fast enough to pass the problem.
      |                                                                 ^
a.cc:25:1: error: stray '##' in program
   25 | ## Code
      | ^~
a.cc:27:1: error: stray '`' in program
   27 | ```cpp
      | ^
a.cc:27:2: error: stray '`' in program
   27 | ```cpp
      |  ^
a.cc:27:3: error: stray '`' in program
   27 | ```cpp
      |   ^
a.cc:56:1: error: stray '`' in program
   56 | ```
      | ^
a.cc:56:2: error: stray '`' in program
   56 | ```
      |  ^
a.cc:56:3: error: stray '`' in program
   56 | ```
      |   ^
a.cc:3:1: error: 'Problem' does not name a type
    3 | Problem URL: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1616
      | ^~~~~~~
In file included from /usr/include/c++/14/bits/stl_algobase.h:62,
                 from /usr/include/c++/14/algorithm:60,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:51,
                 from a.cc:28:
/usr/include/c++/14/ext/type_traits.h:164:35: error: 'constexpr const bool __gnu_cxx::__is_null_pointer' redeclared as different kind of entity
  164 |   __is_null_pointer(std::nullptr_t)
      |                                   ^
/usr/include/c++/14/ext/type_traits.h:159:5: note: previous declaration 'template<class _Type> constexpr bool __gnu_cxx::__is_null_pointer(_Type)'
  159 |     __is_null_pointer(_Type)
      |     ^~~~~~~~~~~~~~~~~
/usr/include/c++/14/ext/type_traits.h:164:26: error: 'nullptr_t' is not a member of 'std'; did you mean 'nullptr_t'?
  164 |   __is_null_pointer(std::nullptr_t)
      |                          ^~~~~~~~~
In file included from /usr/include/c++/14/cstddef:50,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:41:
/usr/lib/gcc/x86_64-linux-gnu/14/include/stddef.h:443:29: note: 'nullptr_t' declared here
  443 |   typedef decltype(nullptr) nullptr_t;
      |                             ^~~~~~~~~
In file included from /usr/include/c++/14/bits/stl_pair.h:60,
                 from /usr/include/c++/14/bits/stl_algobase.h:64:
/usr/include/c++/14/type_traits:666:33: error: 'nullptr_t' is not a member of 'std'; did you mean 'nullptr_t'?
  666 |     struct is_null_pointer<std::nullptr_t>
      |                                 ^~~~~~~~~
/usr/lib/gcc/x86_64-linux-gnu/14/include/stddef.h:443:29: note: 'nullptr_t' declared here
  443 |   typedef decltype(nullptr) nullptr_t;
      |                             ^~~~~~~~~
/usr/include/c++/14/type_traits:666:42: error: template argument 1 is invalid
  666 |     struct is_null_pointer<std::nullptr_t>
      |                                          ^
/usr/include/c++/14/type_traits:670:48: error: template argument 1 is invalid
  670 |     struct is_null_pointer<const std::nullptr_t>
      |                                                ^
/usr/include/c++/14/type_traits:674:51: error: template argument 1 is invalid
  674 |     struct is_null_pointer<volatile std::nullptr_t>
      |                                                   ^
/usr/include/c++/14/type_traits:678:57: error: template argument 1 is invalid
  678 |     struct is_null_pointer<const volatile std::nullptr_t>
      |                                                         ^
/usr/include/c++/14/type_traits:1429:37: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
 1429 |     : public integral_constant<std::size_t, alignof(_Tp)>
      |                                     ^~~~~~
/usr/lib/gcc/x86_64-linux-gnu/14/include/stddef.h:214:23: note: 'size_t' declared here
  214 | typedef __SIZE_TYPE__ size_t;
      |                       ^~~~~~
/usr/include/c++/14/type_traits:1429:57: error: template argument 1 is invalid
 1429 |     : public integral_constant<std::size_t, alignof(_Tp)>
      |                                                         ^
/usr/include/c++/14/type_traits:1429:57: note: invalid template non-type parameter
/usr/include/c++/14/type_traits:1438:37: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
 1438 |     : public integral_constant<std::size_t, 0> { };
      |                                     ^~~~~~
/usr/lib/gcc/x86_64-linux-gnu/14/include/stddef.h:214:23: note: 'size_t' declared here
  214 | typedef __SIZE_TYPE__ size_t;
      |                       ^~~~~~
/usr/include/c++/14/type_traits:1438:46: error: template argument 1 is invalid
 1438 |     : public integral_constant<std::size_t, 0> { };
      |                                              ^
/usr/include/c++/14/type_traits:1438:46: note: invalid template non-type parameter
/usr/include/c++/14/type_traits:1440:26: error: 'std::size_t' has not been declared
 1440 |   template<typename _Tp, std::size_t _Size>
      |                          ^~~
/usr/include/c++/14/type_traits:1441:21: error: '_Size' was not declared in this scope
 1441 |     struct rank<_Tp[_Size]>
      |                     ^~~~~
/usr/include/c++/14/type_traits:1441:27: error: template argument 1 is invalid
 1441 |     struct rank<_Tp[_Size]>
      |                           ^
/usr/include/c++/14/type_traits:1442:37: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
 1442 |     : public integral_constant<std::size_t, 1 + rank<_Tp>::value> { };
      |                                     ^~~~~~
/usr/lib/gcc/x86_64-linux-gnu/14/include/stddef.h:214:23: note: 'size_t' declared here
  214 | typedef __SIZE_TYPE__ size_t;
      |                       ^~~~~~
/usr/include/c++/14/type_traits:1442:65: error: template argument 1 is invalid
 1442 |     : public integral_constant<std::size_t, 1 + rank<_Tp>::value> { };
      |                                                                 ^
/usr/include/c++/14/type_traits:1442:65: note: invalid template non-type parameter
/usr/include/c++/14/type_traits:1446:37: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
 1446 |     : public integral_constant<std::size_t, 1 + rank<_Tp>::value> { };
      |                                     ^~~~~~
/usr/lib/gcc/x86_64-linux-gnu/14/include/stddef.h:214:23: note: 'size_t' declared here
  214 | typedef __SIZE_TYPE__ size_t;
      |                       ^~~~~~
/usr/include/c++/14/type_traits:1446:65: error: template argument 1 is invalid
 1446 |     : public integral_constant<std::size_t, 1 + rank<_Tp>::value> { };
      |                                                                 ^
/usr/include/c++/14/type_traits:1446:65: note: invalid template non-type parameter
/usr/include/c++/14/type_traits:2086:26: error: 'std::size_t' has not been declared
 2086 |   template<typename _Tp, std::size_t _Size>
      |                          ^~~
/usr/include/c++/14/type_traits:2087:30: error: '_Size' was not declared in this scope
 2087 |     struct remove_extent<_Tp[_Size]>
      |                              ^~~~~
/usr/include/c++/14/t