SHOW:
|
|
- or go back to the newest paste.
| 1 | // Author : Saurav Kalsoor | |
| 2 | - | // Minimize Unique Numbers - JAVA |
| 2 | + | // Count Quadruplets - JAVA |
| 3 | ||
| 4 | import java.util.*; | |
| 5 | ||
| 6 | public class Test {
| |
| 7 | static Scanner sc = new Scanner(System.in); | |
| 8 | public static void main(String[] args) {
| |
| 9 | int n = sc.nextInt(); | |
| 10 | - | int k = sc.nextInt(); |
| 10 | + | int m = sc.nextInt(); |
| 11 | int p = sc.nextInt(); | |
| 12 | - | ArrayList<Integer> arr = new ArrayList<>(); |
| 12 | + | int q = sc.nextInt(); |
| 13 | int target = sc.nextInt(); | |
| 14 | - | arr.add(sc.nextInt()); |
| 14 | + | |
| 15 | ArrayList<Integer> a = new ArrayList<>(); | |
| 16 | ArrayList<Integer> b = new ArrayList<>(); | |
| 17 | - | System.out.println(minimizeUnique(arr, k)); |
| 17 | + | ArrayList<Integer> c = new ArrayList<>(); |
| 18 | ArrayList<Integer> d = new ArrayList<>(); | |
| 19 | ||
| 20 | - | public static int minimizeUnique(ArrayList<Integer> arr, int k){
|
| 20 | + | |
| 21 | - | HashMap<Integer, Integer> count = new HashMap<>(); |
| 21 | + | a.add(sc.nextInt()); |
| 22 | } | |
| 23 | - | for(int num : arr){
|
| 23 | + | |
| 24 | - | count.put(num, count.getOrDefault(num, 0) + 1); |
| 24 | + | for(int i = 0;i < m; i++){
|
| 25 | b.add(sc.nextInt()); | |
| 26 | } | |
| 27 | - | Set<MyPair> st = new TreeSet<>(new Comparator<MyPair>() {
|
| 27 | + | |
| 28 | - | @Override |
| 28 | + | for(int i = 0;i < p; i++){
|
| 29 | - | public int compare(MyPair a, MyPair b) {
|
| 29 | + | c.add(sc.nextInt()); |
| 30 | - | if(a.second == b.second) |
| 30 | + | |
| 31 | - | return a.first - b.first; |
| 31 | + | |
| 32 | - | return a.second - b.second; |
| 32 | + | for(int i = 0;i < q; i++){
|
| 33 | - | } |
| 33 | + | d.add(sc.nextInt()); |
| 34 | - | }); |
| 34 | + | |
| 35 | System.out.println(countQuadruplets(a, b, c, d, target)); | |
| 36 | - | for(Map.Entry<Integer, Integer> x : count.entrySet()){
|
| 36 | + | |
| 37 | - | st.add(new MyPair(x.getKey(), x.getValue()) ); |
| 37 | + | |
| 38 | - | } |
| 38 | + | public static int countQuadruplets(ArrayList<Integer> a, ArrayList<Integer> b, ArrayList<Integer> c, ArrayList<Integer> d, int target) {
|
| 39 | HashMap<Integer, Integer> map = new HashMap<>(); | |
| 40 | - | int res = st.size(); |
| 40 | + | |
| 41 | for (int i : a) {
| |
| 42 | - | for(MyPair x : st){
|
| 42 | + | for (int j : b) {
|
| 43 | - | if(k >= x.second){
|
| 43 | + | if (map.containsKey(i + j)) {
|
| 44 | - | res--; |
| 44 | + | map.put(i + j, map.get(i + j) + 1); |
| 45 | - | k -= x.second; |
| 45 | + | } else |
| 46 | - | }else{
|
| 46 | + | map.put(i + j, 1); |
| 47 | - | break; |
| 47 | + | } |
| 48 | - | } |
| 48 | + | } |
| 49 | ||
| 50 | int count = 0; | |
| 51 | - | return res; |
| 51 | + | |
| 52 | for (int i : c) {
| |
| 53 | for (int j : d) {
| |
| 54 | if (map.containsKey(target - i - j)) {
| |
| 55 | count += map.get(target - i - j); | |
| 56 | - | class MyPair{
|
| 56 | + | } |
| 57 | - | public int first, second; |
| 57 | + | } |
| 58 | } | |
| 59 | - | public MyPair(int first, int second){
|
| 59 | + | |
| 60 | - | this.first = first; |
| 60 | + | return count; |
| 61 | - | this.second = second; |
| 61 | + | |
| 62 | - | } |
| 62 | + | |
| 63 | } | |
| 64 | ||
| 65 | ||
| 66 |