Cod sursa(job #3287072)

Utilizator lucky1992Ion Ion lucky1992 Data 15 martie 2025 11:18:51
Problema Numarare triunghiuri Scor 100
Compilator java Status done
Runda Arhiva de probleme Marime 2.17 kb
import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

  public static class MyScanner implements Closeable {
    BufferedReader br;
    StringTokenizer st;

    public MyScanner(String file) throws FileNotFoundException {
      br = new BufferedReader(new InputStreamReader(new FileInputStream(file)), 1 << 16);
    }

    String next() {
      while (st == null || !st.hasMoreElements()) {
        try {
          st = new StringTokenizer(br.readLine());
        } catch (IOException e) {
          e.printStackTrace();
        }
      }
      return st.nextToken();
    }

    int nextInt() {
      return Integer.parseInt(next());
    }

    long nextLong() {
      return Long.parseLong(next());
    }

    double nextDouble() {
      return Double.parseDouble(next());
    }

    String nextLine(){
      String str = "";
      try {
        str = br.readLine();
      } catch (IOException e) {
        e.printStackTrace();
      }
      return str;
    }

    @Override
    public void close() throws IOException {
      br.close();
    }
  }

  public static int binarySearch(int[] v, int low, int high, int target) {
    int mid;
    while (low <= high) {
      mid = low + high >>> 1;
      if (v[mid] <= target && (mid + 1 > high || target < v[mid + 1])) {
        return mid;
      } else if (v[mid] <= target) {
        low = mid + 1;
      } else {
        high = mid - 1;
      }
    }

    return low - 1;
  }

  public static void main(String[] args) throws IOException {

    try (MyScanner scanner = new MyScanner("nrtri.in");
         PrintWriter pw = new PrintWriter(new FileOutputStream("nrtri.out"))) {

      int N = scanner.nextInt();
      int[] v = new int[N+1];

      for (int i = 1; i <= N; i++) {
        v[i] = scanner.nextInt();
      }

      Arrays.sort(v, 1, N + 1);
      int count = 0;

      for (int a = 1; a <= N; a++) {
        for (int b = a + 1; b <= N - 1; b++) {
          int t = v[a] + v[b];
          int r = binarySearch(v, b + 1, N, t); //Arrays.binarySearch(v, b + 1, N+1, t);
//          if (r < 0) {
//            r = -r - 2;
//          }
          count += r - b;
        }
      }

      pw.println(count);
    }
  }
}