An array A consisting of N integers is given. A triplet (P, Q, R) is triangular if it is possible to build a triangle with sides of lengths A[P], A[Q] and A[R]. In other words, triplet (P, Q, R) is triangular if 0 ≤ P < Q < R < N and:
- A[P] + A[Q] > A[R],
- A[Q] + A[R] > A[P],
- A[R] + A[P] > A[Q].
For example, consider array A such that:
A[0] = 10 A[1] = 2 A[2] = 5 A[3] = 1 A[4] = 8 A[5] = 12There are four triangular triplets that can be constructed from elements of this array, namely (0, 2, 4), (0, 2, 5), (0, 4, 5), and (2, 4, 5).
Write a function:
int solution(int A[], int N);
that, given an array A consisting of N integers, returns the number of triangular triplets in this array.
For example, given array A such that:
A[0] = 10 A[1] = 2 A[2] = 5 A[3] = 1 A[4] = 8 A[5] = 12the function should return 4, as explained above.
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [0..1,000];
- each element of array A is an integer within the range [1..1,000,000,000].
// you can write to stdout for debugging purposes, e.g.
// printf("this is a debug message\n");
#include <stdlib.h>
int compare(const void*a,const void*b){
return (*(int*)a>*(int*)b)?1:(*(int*)a<*(int*)b)?-1:0;
}
int comb(int n,int r){
if(n==r||r==0) return 1;
return (comb(n-1,r-1)+comb(n-1,r));
}
int solution(int A[], int N) {
// write your code in C99 (gcc 6.2.0)
int ret=0;
if(N<3) return 0;
qsort(A,N,sizeof(int),compare);
if(A[0]==A[N-1]) return comb(N,N-3);
for(int a=0;a<N-2;a++){
//if(A[a]>=(A[b]+A[c])) break;
for(int b=a+1;b<N-1;b++){
//if(A[b]>=(A[a]+A[c])) break;
for(int c=b+1;c<N;c++){
if(A[c]>=(A[a]+A[b])) break;
ret++;
}
}
}
return ret;
}
// you can write to stdout for debugging purposes, e.g.
// printf("this is a debug message\n");
#include <stdlib.h>
int compare(const void*a,const void*b){
return (*(int*)a>*(int*)b)?1:(*(int*)a<*(int*)b)?-1:0;
}
int solution(int A[], int N) {
// write your code in C99 (gcc 6.2.0)
int ret=0;
if(N<3) return 0;
qsort(A,N,sizeof(int),compare);
for(int a=0;a<N-2;a++){
//if(A[a]>=(A[b]+A[c])) break;
for(int b=a+1;b<N-1;b++){
//if(A[b]>=(A[a]+A[c])) break;
for(int c=b+1;c<N;c++){
if(A[c]>=(A[a]+A[b])) break;
ret++;
}
}
}
return ret;
}
// you can write to stdout for debugging purposes, e.g.
// printf("this is a debug message\n");
#include <stdlib.h>
int compare(const void*a,const void*b){
return (*(int*)a>*(int*)b)?1:(*(int*)a<*(int*)b)?-1:0;
}
int solution(int A[], int N) {
// write your code in C99 (gcc 6.2.0)
int ret=0;
if(N<3) return 0;
qsort(A,N,sizeof(int),compare);
for(int a=0;a<N-2;a++){
//if(A[a]>=(A[b]+A[c])) break;
for(int b=a+1;b<N-1;b++){
if(A[b]>=(A[a]+A[c])) break;
for(int c=b+1;c<N;c++){
if(A[c]>=(A[a]+A[b])) break;
ret++;
}
}
}
return ret;
}
// you can write to stdout for debugging purposes, e.g.
// printf("this is a debug message\n");
#include <stdlib.h>
int compare(const void*a,const void*b){
return (*(int*)a>*(int*)b)?1:(*(int*)a<*(int*)b)?-1:0;
}
int solution(int A[], int N) {
// write your code in C99 (gcc 6.2.0)
int ret=0;
if(N<3) return 0;
qsort(A,N,sizeof(int),compare);
for(int a=0;a<N-2;a++){
//if(A[a]>=(A[b]+A[c])) break;
for(int b=a+1;b<N-1;b++){
if(A[b]>=(A[a]+A[N-1])) break;
for(int c=b+1;c<N;c++){
if(A[c]>=(A[a]+A[b])) break;
ret++;
}
}
}
return ret;
}
// you can write to stdout for debugging purposes, e.g.
// printf("this is a debug message\n");
#include <stdlib.h>
int compare(const void*a,const void*b){
return (*(int*)a>*(int*)b)?1:(*(int*)a<*(int*)b)?-1:0;
}
int solution(int A[], int N) {
// write your code in C99 (gcc 6.2.0)
int ret=0;
if(N<3) return 0;
qsort(A,N,sizeof(int),compare);
for(int a=0;a<N-2;a++){
//if(A[a]>=(A[b]+A[c])) break;
for(int b=a+1;b<N-1;b++){
/if(A[b]>=(A[a]+A[N-1])) break;
for(int c=b+1;c<N;c++){
if(A[c]>=(A[a]+A[b])) break;
ret++;
}
}
}
return ret;
}
// you can write to stdout for debugging purposes, e.g.
// printf("this is a debug message\n");
#include <stdlib.h>
int compare(const void*a,const void*b){
return (*(int*)a>*(int*)b)?1:(*(int*)a<*(int*)b)?-1:0;
}
int solution(int A[], int N) {
// write your code in C99 (gcc 6.2.0)
int ret=0;
if(N<3) return 0;
qsort(A,N,sizeof(int),compare);
if(A[0]==A[N-1]){
}
for(int a=0;a<N-2;a++){
//if(A[a]>=(A[b]+A[c])) break;
for(int b=a+1;b<N-1;b++){
//if(A[b]>=(A[a]+A[N-1])) break;
for(int c=b+1;c<N;c++){
if(A[c]>=(A[a]+A[b])) break;
ret++;
}
}
}
return ret;
}
// you can write to stdout for debugging purposes, e.g.
// printf("this is a debug message\n");
#include <stdlib.h>
int compare(const void*a,const void*b){
return (*(int*)a>*(int*)b)?1:(*(int*)a<*(int*)b)?-1:0;
}
int solution(int A[], int N) {
// write your code in C99 (gcc 6.2.0)
int ret=0;
if(N<3) return 0;
qsort(A,N,sizeof(int),compare);
if(A[0]==A[N-1]){
ret=
}
for(int a=0;a<N-2;a++){
//if(A[a]>=(A[b]+A[c])) break;
for(int b=a+1;b<N-1;b++){
//if(A[b]>=(A[a]+A[N-1])) break;
for(int c=b+1;c<N;c++){
if(A[c]>=(A[a]+A[b])) break;
ret++;
}
}
}
return ret;
}
// you can write to stdout for debugging purposes, e.g.
// printf("this is a debug message\n");
#include <stdlib.h>
int compare(const void*a,const void*b){
return (*(int*)a>*(int*)b)?1:(*(int*)a<*(int*)b)?-1:0;
}
int solution(int A[], int N) {
// write your code in C99 (gcc 6.2.0)
int ret=0;
if(N<3) return 0;
qsort(A,N,sizeof(int),compare);
if(A[0]==A[N-1]){
ret=N
}
for(int a=0;a<N-2;a++){
//if(A[a]>=(A[b]+A[c])) break;
for(int b=a+1;b<N-1;b++){
//if(A[b]>=(A[a]+A[N-1])) break;
for(int c=b+1;c<N;c++){
if(A[c]>=(A[a]+A[b])) break;
ret++;
}
}
}
return ret;
}
// you can write to stdout for debugging purposes, e.g.
// printf("this is a debug message\n");
#include <stdlib.h>
int compare(const void*a,const void*b){
return (*(int*)a>*(int*)b)?1:(*(int*)a<*(int*)b)?-1:0;
}
int solution(int A[], int N) {
// write your code in C99 (gcc 6.2.0)
int ret=0;
if(N<3) return 0;
qsort(A,N,sizeof(int),compare);
if(A[0]==A[N-1]){
for(int a=0;a<N-2;a++){
for(int b=a+1;b<N-1;b++){
for(int c=b+1;c<N;c++){
ret++;
}
}
}
}
for(int a=0;a<N-2;a++){
//if(A[a]>=(A[b]+A[c])) break;
for(int b=a+1;b<N-1;b++){
//if(A[b]>=(A[a]+A[N-1])) break;
for(int c=b+1;c<N;c++){
if(A[c]>=(A[a]+A[b])) break;
ret++;
}
}
}
return ret;
}
// you can write to stdout for debugging purposes, e.g.
// printf("this is a debug message\n");
#include <stdlib.h>
int compare(const void*a,const void*b){
return (*(int*)a>*(int*)b)?1:(*(int*)a<*(int*)b)?-1:0;
}
int solution(int A[], int N) {
// write your code in C99 (gcc 6.2.0)
int ret=0;
if(N<3) return 0;
qsort(A,N,sizeof(int),compare);
if(A[0]==A[N-1]){
for(int a=0;a<N-2;a++){
for(int b=a+1;b<N-1;b++){
ret+=N-b+1
for(int c=b+1;c<N;c++){
ret++;
}
}
}
}
for(int a=0;a<N-2;a++){
//if(A[a]>=(A[b]+A[c])) break;
for(int b=a+1;b<N-1;b++){
//if(A[b]>=(A[a]+A[N-1])) break;
for(int c=b+1;c<N;c++){
if(A[c]>=(A[a]+A[b])) break;
ret++;
}
}
}
return ret;
}
// you can write to stdout for debugging purposes, e.g.
// printf("this is a debug message\n");
#include <stdlib.h>
int compare(const void*a,const void*b){
return (*(int*)a>*(int*)b)?1:(*(int*)a<*(int*)b)?-1:0;
}
int solution(int A[], int N) {
// write your code in C99 (gcc 6.2.0)
int ret=0;
if(N<3) return 0;
qsort(A,N,sizeof(int),compare);
if(A[0]==A[N-1]){
for(int a=0;a<N-2;a++){
for(int b=a+1;b<N-1;b++){
ret+=N-b+1;
}
}
}
for(int a=0;a<N-2;a++){
//if(A[a]>=(A[b]+A[c])) break;
for(int b=a+1;b<N-1;b++){
//if(A[b]>=(A[a]+A[N-1])) break;
for(int c=b+1;c<N;c++){
if(A[c]>=(A[a]+A[b])) break;
ret++;
}
}
}
return ret;
}
// you can write to stdout for debugging purposes, e.g.
// printf("this is a debug message\n");
#include <stdlib.h>
int compare(const void*a,const void*b){
return (*(int*)a>*(int*)b)?1:(*(int*)a<*(int*)b)?-1:0;
}
int solution(int A[], int N) {
// write your code in C99 (gcc 6.2.0)
int ret=0;
if(N<3) return 0;
qsort(A,N,sizeof(int),compare);
if(A[0]==A[N-1]){
for(int a=0;a<N-2;a++){
for(int b=a+1;b<N-1;b++){
ret+=N-b+1;
}
}
return ret;
}
for(int a=0;a<N-2;a++){
//if(A[a]>=(A[b]+A[c])) break;
for(int b=a+1;b<N-1;b++){
//if(A[b]>=(A[a]+A[N-1])) break;
for(int c=b+1;c<N;c++){
if(A[c]>=(A[a]+A[b])) break;
ret++;
}
}
}
return ret;
}
// you can write to stdout for debugging purposes, e.g.
// printf("this is a debug message\n");
#include <stdlib.h>
int compare(const void*a,const void*b){
return (*(int*)a>*(int*)b)?1:(*(int*)a<*(int*)b)?-1:0;
}
int solution(int A[], int N) {
// write your code in C99 (gcc 6.2.0)
int ret=0;
if(N<3) return 0;
qsort(A,N,sizeof(int),compare);
if(A[0]==A[N-1]){
for(int a=0;a<N-2;a++){
for(int b=a+1;b<N-1;b++){
ret+=N-b+1;
}
}
return ret;
}
for(int a=0;a<N-2;a++){
//if(A[a]>=(A[b]+A[c])) break;
for(int b=a+1;b<N-1;b++){
//if(A[b]>=(A[a]+A[N-1])) break;
for(int c=b+1;c<N;c++){
if(A[c]>=(A[a]+A[b])) break;
ret++;
}
}
}
return ret;
}
[1, 1, 1, 1, 1, 1, 1]
// you can write to stdout for debugging purposes, e.g.
// printf("this is a debug message\n");
#include <stdlib.h>
int compare(const void*a,const void*b){
return (*(int*)a>*(int*)b)?1:(*(int*)a<*(int*)b)?-1:0;
}
int solution(int A[], int N) {
// write your code in C99 (gcc 6.2.0)
int ret=0;
if(N<3) return 0;
qsort(A,N,sizeof(int),compare);
#if 0
if(A[0]==A[N-1]){
for(int a=0;a<N-2;a++){
for(int b=a+1;b<N-1;b++){
ret+=N-b+1;
}
}
return ret;
}
#endif
for(int a=0;a<N-2;a++){
//if(A[a]>=(A[b]+A[c])) break;
for(int b=a+1;b<N-1;b++){
//if(A[b]>=(A[a]+A[N-1])) break;
for(int c=b+1;c<N;c++){
if(A[c]>=(A[a]+A[b])) break;
ret++;
}
}
}
return ret;
}
[1, 1, 1, 1, 1, 1, 1]
// you can write to stdout for debugging purposes, e.g.
// printf("this is a debug message\n");
#include <stdlib.h>
int compare(const void*a,const void*b){
return (*(int*)a>*(int*)b)?1:(*(int*)a<*(int*)b)?-1:0;
}
int solution(int A[], int N) {
// write your code in C99 (gcc 6.2.0)
int ret=0;
if(N<3) return 0;
qsort(A,N,sizeof(int),compare);
#if 0
if(A[0]==A[N-1]){
for(int a=0;a<N-2;a++){
for(int b=a+1;b<N-1;b++){
ret+=N-b;
}
}
return ret;
}
#endif
for(int a=0;a<N-2;a++){
//if(A[a]>=(A[b]+A[c])) break;
for(int b=a+1;b<N-1;b++){
//if(A[b]>=(A[a]+A[N-1])) break;
for(int c=b+1;c<N;c++){
if(A[c]>=(A[a]+A[b])) break;
ret++;
}
}
}
return ret;
}
// you can write to stdout for debugging purposes, e.g.
// printf("this is a debug message\n");
#include <stdlib.h>
int compare(const void*a,const void*b){
return (*(int*)a>*(int*)b)?1:(*(int*)a<*(int*)b)?-1:0;
}
int solution(int A[], int N) {
// write your code in C99 (gcc 6.2.0)
int ret=0;
if(N<3) return 0;
qsort(A,N,sizeof(int),compare);
#if 1
if(A[0]==A[N-1]){
for(int a=0;a<N-2;a++){
for(int b=a+1;b<N-1;b++){
ret+=N-b;
}
}
return ret;
}
#endif
for(int a=0;a<N-2;a++){
//if(A[a]>=(A[b]+A[c])) break;
for(int b=a+1;b<N-1;b++){
//if(A[b]>=(A[a]+A[N-1])) break;
for(int c=b+1;c<N;c++){
if(A[c]>=(A[a]+A[b])) break;
ret++;
}
}
}
return ret;
}
[1, 1, 1, 1, 1, 1, 1]
// you can write to stdout for debugging purposes, e.g.
// printf("this is a debug message\n");
#include <stdlib.h>
int compare(const void*a,const void*b){
return (*(int*)a>*(int*)b)?1:(*(int*)a<*(int*)b)?-1:0;
}
int solution(int A[], int N) {
// write your code in C99 (gcc 6.2.0)
int ret=0;
if(N<3) return 0;
qsort(A,N,sizeof(int),compare);
#if 1
if(A[0]==A[N-1]){
for(int a=0;a<N-2;a++){
for(int b=a+1;b<N-1;b++){
ret+=N-b-1;
}
}
return ret;
}
#endif
for(int a=0;a<N-2;a++){
//if(A[a]>=(A[b]+A[c])) break;
for(int b=a+1;b<N-1;b++){
//if(A[b]>=(A[a]+A[N-1])) break;
for(int c=b+1;c<N;c++){
if(A[c]>=(A[a]+A[b])) break;
ret++;
}
}
}
return ret;
}
[1, 1, 1, 1, 1, 1, 1]
// you can write to stdout for debugging purposes, e.g.
// printf("this is a debug message\n");
#include <stdlib.h>
int compare(const void*a,const void*b){
return (*(int*)a>*(int*)b)?1:(*(int*)a<*(int*)b)?-1:0;
}
int solution(int A[], int N) {
// write your code in C99 (gcc 6.2.0)
int ret=0;
if(N<3) return 0;
qsort(A,N,sizeof(int),compare);
#if 1
if(A[0]==A[N-1]){
for(int a=0;a<N-2;a++){
for(int b=a+1;b<N-1;b++){
ret+=N-(b+1);
}
}
return ret;
}
#endif
for(int a=0;a<N-2;a++){
//if(A[a]>=(A[b]+A[c])) break;
for(int b=a+1;b<N-1;b++){
//if(A[b]>=(A[a]+A[N-1])) break;
for(int c=b+1;c<N;c++){
if(A[c]>=(A[a]+A[b])) break;
ret++;
}
}
}
return ret;
}
// you can write to stdout for debugging purposes, e.g.
// printf("this is a debug message\n");
#include <stdlib.h>
int compare(const void*a,const void*b){
return (*(int*)a>*(int*)b)?1:(*(int*)a<*(int*)b)?-1:0;
}
int solution(int A[], int N) {
// write your code in C99 (gcc 6.2.0)
int ret=0;
if(N<3) return 0;
qsort(A,N,sizeof(int),compare);
#if 1
if(A[0]==A[N-1]){
for(int a=0;a<N-2;a++){
for(int b=a+1;b<N-1;b++){
ret+=N-(b+1);
}
}
return ret;
}
#endif
for(int a=0;a<N-2;a++){
//if(A[a]>=(A[b]+A[c])) break;
for(int b=a+1;b<N-1;b++){
//if(A[b]>=(A[a]+A[N-1])) break;
for(int c=b+1;c<N;c++){
if(A[c]>=(A[a]+A[b])) break;
ret++;
}
}
}
return ret;
}
[1, 1, 1, 1, 1, 1, 1]
// you can write to stdout for debugging purposes, e.g.
// printf("this is a debug message\n");
#include <stdlib.h>
int compare(const void*a,const void*b){
return (*(int*)a>*(int*)b)?1:(*(int*)a<*(int*)b)?-1:0;
}
int solution(int A[], int N) {
// write your code in C99 (gcc 6.2.0)
int ret=0;
if(N<3) return 0;
qsort(A,N,sizeof(int),compare);
#if 1
if(A[0]==A[N-1]){
for(int a=0;a<N-2;a++){
for(int b=a+1;b<N-1;b++){
int
ret+=N-(b+1);
}
}
return ret;
}
#endif
for(int a=0;a<N-2;a++){
//if(A[a]>=(A[b]+A[c])) break;
for(int b=a+1;b<N-1;b++){
//if(A[b]>=(A[a]+A[N-1])) break;
for(int c=b+1;c<N;c++){
if(A[c]>=(A[a]+A[b])) break;
ret++;
}
}
}
return ret;
}
// you can write to stdout for debugging purposes, e.g.
// printf("this is a debug message\n");
#include <stdlib.h>
int compare(const void*a,const void*b){
return (*(int*)a>*(int*)b)?1:(*(int*)a<*(int*)b)?-1:0;
}
int solution(int A[], int N) {
// write your code in C99 (gcc 6.2.0)
int ret=0;
if(N<3) return 0;
qsort(A,N,sizeof(int),compare);
#if 1
if(A[0]==A[N-1]){
for(int a=0;a<N-2;a++){
for(int b=a+1;b<N-1;b++){
int add=N-(b+1);
printf("add %d\n",add);
ret+=add;
}
}
return ret;
}
#endif
for(int a=0;a<N-2;a++){
//if(A[a]>=(A[b]+A[c])) break;
for(int b=a+1;b<N-1;b++){
//if(A[b]>=(A[a]+A[N-1])) break;
for(int c=b+1;c<N;c++){
if(A[c]>=(A[a]+A[b])) break;
ret++;
}
}
}
return ret;
}
[1, 1, 1, 1, 1, 1, 1]
function result: 35
add 5 add 4 add 3 add 2 add 1 add 4 add 3 add 2 add 1 add 3 add 2 add 1 add 2 add 1 add 1
// you can write to stdout for debugging purposes, e.g.
// printf("this is a debug message\n");
#include <stdlib.h>
int compare(const void*a,const void*b){
return (*(int*)a>*(int*)b)?1:(*(int*)a<*(int*)b)?-1:0;
}
int solution(int A[], int N) {
// write your code in C99 (gcc 6.2.0)
int ret=0;
if(N<3) return 0;
qsort(A,N,sizeof(int),compare);
#if 1
if(A[0]==A[N-1]){
for(int a=0;a<N-2;a++){
for(int b=a+1;b<N-1;b++){
int add=N-(b+1);
printf("%d:add %d\n",add);
ret+=add;
}
}
return ret;
}
#endif
for(int a=0;a<N-2;a++){
//if(A[a]>=(A[b]+A[c])) break;
for(int b=a+1;b<N-1;b++){
//if(A[b]>=(A[a]+A[N-1])) break;
for(int c=b+1;c<N;c++){
if(A[c]>=(A[a]+A[b])) break;
ret++;
}
}
}
return ret;
}
// you can write to stdout for debugging purposes, e.g.
// printf("this is a debug message\n");
#include <stdlib.h>
int compare(const void*a,const void*b){
return (*(int*)a>*(int*)b)?1:(*(int*)a<*(int*)b)?-1:0;
}
int solution(int A[], int N) {
// write your code in C99 (gcc 6.2.0)
int ret=0;
if(N<3) return 0;
qsort(A,N,sizeof(int),compare);
#if 1
if(A[0]==A[N-1]){
for(int a=0;a<N-2;a++){
for(int b=a+1;b<N-1;b++){
int add=N-(b+1);
printf("%d[%d]:add %d\n",b,N,add);
ret+=add;
}
}
return ret;
}
#endif
for(int a=0;a<N-2;a++){
//if(A[a]>=(A[b]+A[c])) break;
for(int b=a+1;b<N-1;b++){
//if(A[b]>=(A[a]+A[N-1])) break;
for(int c=b+1;c<N;c++){
if(A[c]>=(A[a]+A[b])) break;
ret++;
}
}
}
return ret;
}
[1, 1, 1, 1, 1, 1, 1]
function result: 35
1[7]:add 5 2[7]:add 4 3[7]:add 3 4[7]:add 2 5[7]:add 1 2[7]:add 4 3[7]:add 3 4[7]:add 2 5[7]:add 1 3[7]:add 3 4[7]:add 2 5[7]:add 1 4[7]:add 2 5[7]:add 1 5[7]:add 1
// you can write to stdout for debugging purposes, e.g.
// printf("this is a debug message\n");
#include <stdlib.h>
int compare(const void*a,const void*b){
return (*(int*)a>*(int*)b)?1:(*(int*)a<*(int*)b)?-1:0;
}
int solution(int A[], int N) {
// write your code in C99 (gcc 6.2.0)
int ret=0;
if(N<3) return 0;
qsort(A,N,sizeof(int),compare);
#if 1
if(A[0]==A[N-1]){
for(int a=0;a<N-2;a++){
for(int b=a+1;b<N-1;b++){
int add=N-(b+1);
printf("%D:%d[%d]:add %d\n",b,N,add);
ret+=add;
}
}
return ret;
}
#endif
for(int a=0;a<N-2;a++){
//if(A[a]>=(A[b]+A[c])) break;
for(int b=a+1;b<N-1;b++){
//if(A[b]>=(A[a]+A[N-1])) break;
for(int c=b+1;c<N;c++){
if(A[c]>=(A[a]+A[b])) break;
ret++;
}
}
}
return ret;
}
// you can write to stdout for debugging purposes, e.g.
// printf("this is a debug message\n");
#include <stdlib.h>
int compare(const void*a,const void*b){
return (*(int*)a>*(int*)b)?1:(*(int*)a<*(int*)b)?-1:0;
}
int solution(int A[], int N) {
// write your code in C99 (gcc 6.2.0)
int ret=0;
if(N<3) return 0;
qsort(A,N,sizeof(int),compare);
#if 1
if(A[0]==A[N-1]){
for(int a=0;a<N-2;a++){
for(int b=a+1;b<N-1;b++){
int add=N-(b+1);
printf("%d:%d[%d]:add %d\n",a,b,N,add);
ret+=add;
}
}
return ret;
}
#endif
for(int a=0;a<N-2;a++){
//if(A[a]>=(A[b]+A[c])) break;
for(int b=a+1;b<N-1;b++){
//if(A[b]>=(A[a]+A[N-1])) break;
for(int c=b+1;c<N;c++){
if(A[c]>=(A[a]+A[b])) break;
ret++;
}
}
}
return ret;
}
[1, 1, 1, 1, 1, 1, 1]
function result: 35
0:1[7]:add 5 0:2[7]:add 4 0:3[7]:add 3 0:4[7]:add 2 0:5[7]:add 1 1:2[7]:add 4 1:3[7]:add 3 1:4[7]:add 2 1:5[7]:add 1 2:3[7]:add 3 2:4[7]:add 2 2:5[7]:add 1 3:4[7]:add 2 3:5[7]:add 1 4:5[7]:add 1
// you can write to stdout for debugging purposes, e.g.
// printf("this is a debug message\n");
#include <stdlib.h>
int compare(const void*a,const void*b){
return (*(int*)a>*(int*)b)?1:(*(int*)a<*(int*)b)?-1:0;
}
int solution(int A[], int N) {
// write your code in C99 (gcc 6.2.0)
int ret=0;
if(N<3) return 0;
qsort(A,N,sizeof(int),compare);
#if 1
if(A[0]==A[N-1]){
for(int a=0;a<N-2;a++){
ret
for(int b=a+1;b<N-1;b++){
int add=N-(b+1);
printf("%d:%d[%d]:add %d\n",a,b,N,add);
ret+=add;
}
}
return ret;
}
#endif
for(int a=0;a<N-2;a++){
//if(A[a]>=(A[b]+A[c])) break;
for(int b=a+1;b<N-1;b++){
//if(A[b]>=(A[a]+A[N-1])) break;
for(int c=b+1;c<N;c++){
if(A[c]>=(A[a]+A[b])) break;
ret++;
}
}
}
return ret;
}
// you can write to stdout for debugging purposes, e.g.
// printf("this is a debug message\n");
#include <stdlib.h>
int compare(const void*a,const void*b){
return (*(int*)a>*(int*)b)?1:(*(int*)a<*(int*)b)?-1:0;
}
int solution(int A[], int N) {
// write your code in C99 (gcc 6.2.0)
int ret=0;
if(N<3) return 0;
qsort(A,N,sizeof(int),compare);
#if 1
if(A[0]==A[N-1]){
for(int a=0;a<N-2;a++){
ret+=(N-2)*(N-1)/2;
for(int b=a+1;b<N-1;b++){
int add=N-(b+1);
printf("%d:%d[%d]:add %d\n",a,b,N,add);
ret+=add;
}
}
return ret;
}
#endif
for(int a=0;a<N-2;a++){
//if(A[a]>=(A[b]+A[c])) break;
for(int b=a+1;b<N-1;b++){
//if(A[b]>=(A[a]+A[N-1])) break;
for(int c=b+1;c<N;c++){
if(A[c]>=(A[a]+A[b])) break;
ret++;
}
}
}
return ret;
}
// you can write to stdout for debugging purposes, e.g.
// printf("this is a debug message\n");
#include <stdlib.h>
int compare(const void*a,const void*b){
return (*(int*)a>*(int*)b)?1:(*(int*)a<*(int*)b)?-1:0;
}
int solution(int A[], int N) {
// write your code in C99 (gcc 6.2.0)
int ret=0;
if(N<3) return 0;
qsort(A,N,sizeof(int),compare);
#if 1
if(A[0]==A[N-1]){
for(int a=0;a<N-2;a++){
ret+=(N-2)*(N-1)/2;
#if 0
for(int b=a+1;b<N-1;b++){
int add=N-(b+1);
printf("%d:%d[%d]:add %d\n",a,b,N,add);
ret+=add;
}
#endif
}
return ret;
}
#endif
for(int a=0;a<N-2;a++){
//if(A[a]>=(A[b]+A[c])) break;
for(int b=a+1;b<N-1;b++){
//if(A[b]>=(A[a]+A[N-1])) break;
for(int c=b+1;c<N;c++){
if(A[c]>=(A[a]+A[b])) break;
ret++;
}
}
}
return ret;
}
[1, 1, 1, 1, 1, 1, 1]
// you can write to stdout for debugging purposes, e.g.
// printf("this is a debug message\n");
#include <stdlib.h>
int compare(const void*a,const void*b){
return (*(int*)a>*(int*)b)?1:(*(int*)a<*(int*)b)?-1:0;
}
int solution(int A[], int N) {
// write your code in C99 (gcc 6.2.0)
int ret=0;
if(N<3) return 0;
qsort(A,N,sizeof(int),compare);
#if 1
if(A[0]==A[N-1]){
for(int a=0;a<N-2;a++){
#if 0
ret+=(N-2)*(N-1)/2;
#else
for(int b=a+1;b<N-1;b++){
int add=N-(b+1);
printf("%d:%d[%d]:add %d\n",a,b,N,add);
ret+=add;
}
#endif
}
return ret;
}
#endif
for(int a=0;a<N-2;a++){
//if(A[a]>=(A[b]+A[c])) break;
for(int b=a+1;b<N-1;b++){
//if(A[b]>=(A[a]+A[N-1])) break;
for(int c=b+1;c<N;c++){
if(A[c]>=(A[a]+A[b])) break;
ret++;
}
}
}
return ret;
}
[1, 1, 1, 1, 1, 1, 1]
function result: 35
0:1[7]:add 5 0:2[7]:add 4 0:3[7]:add 3 0:4[7]:add 2 0:5[7]:add 1 1:2[7]:add 4 1:3[7]:add 3 1:4[7]:add 2 1:5[7]:add 1 2:3[7]:add 3 2:4[7]:add 2 2:5[7]:add 1 3:4[7]:add 2 3:5[7]:add 1 4:5[7]:add 1
// you can write to stdout for debugging purposes, e.g.
// printf("this is a debug message\n");
#include <stdlib.h>
int compare(const void*a,const void*b){
return (*(int*)a>*(int*)b)?1:(*(int*)a<*(int*)b)?-1:0;
}
int solution(int A[], int N) {
// write your code in C99 (gcc 6.2.0)
int ret=0;
if(N<3) return 0;
qsort(A,N,sizeof(int),compare);
#if 1
if(A[0]==A[N-1]){
for(int a=0;a<N-2;a++){
#if 0
ret+=(N-2)*(N-1)/2;
#else
for(int b=a+1;b<N-1;b++){
int add=N-(b+1);
printf("%d:%d[%d]:add %d\n",a,b,N,add);
ret+=add;
}
#endif
}
return ret;
}
#endif
for(int a=0;a<N-2;a++){
//if(A[a]>=(A[b]+A[c])) break;
for(int b=a+1;b<N-1;b++){
//if(A[b]>=(A[a]+A[N-1])) break;
for(int c=b+1;c<N;c++){
if(A[c]>=(A[a]+A[b])) break;
ret++;
}
}
}
return ret;
}
// you can write to stdout for debugging purposes, e.g.
// printf("this is a debug message\n");
#include <stdlib.h>
int compare(const void*a,const void*b){
return (*(int*)a>*(int*)b)?1:(*(int*)a<*(int*)b)?-1:0;
}
int solution(int A[], int N) {
// write your code in C99 (gcc 6.2.0)
int ret=0;
if(N<3) return 0;
qsort(A,N,sizeof(int),compare);
#if 1
if(A[0]==A[N-1]){
for(int a=0;a<N-2;a++){
#if 0
int add=(N-2)*(N-1)/2;
printf("%d:%d[%d]:add %d\n",a,b,N,add);
ret+=add;
#else
for(int b=a+1;b<N-1;b++){
int add=N-(b+1);
printf("%d:%d[%d]:add %d\n",a,b,N,add);
ret+=add;
}
#endif
}
return ret;
}
#endif
for(int a=0;a<N-2;a++){
//if(A[a]>=(A[b]+A[c])) break;
for(int b=a+1;b<N-1;b++){
//if(A[b]>=(A[a]+A[N-1])) break;
for(int c=b+1;c<N;c++){
if(A[c]>=(A[a]+A[b])) break;
ret++;
}
}
}
return ret;
}
// you can write to stdout for debugging purposes, e.g.
// printf("this is a debug message\n");
#include <stdlib.h>
int compare(const void*a,const void*b){
return (*(int*)a>*(int*)b)?1:(*(int*)a<*(int*)b)?-1:0;
}
int solution(int A[], int N) {
// write your code in C99 (gcc 6.2.0)
int ret=0;
if(N<3) return 0;
qsort(A,N,sizeof(int),compare);
#if 1
if(A[0]==A[N-1]){
for(int a=0;a<N-2;a++){
#if 1
int add=(N-2)*(N-1)/2;
printf("%d[%d]:add %d\n",a,N,add);
ret+=add;
#else
for(int b=a+1;b<N-1;b++){
int add=N-(b+1);
printf("%d:%d[%d]:add %d\n",a,b,N,add);
ret+=add;
}
#endif
}
return ret;
}
#endif
for(int a=0;a<N-2;a++){
//if(A[a]>=(A[b]+A[c])) break;
for(int b=a+1;b<N-1;b++){
//if(A[b]>=(A[a]+A[N-1])) break;
for(int c=b+1;c<N;c++){
if(A[c]>=(A[a]+A[b])) break;
ret++;
}
}
}
return ret;
}
[1, 1, 1, 1, 1, 1, 1]
function result: 75
0[7]:add 15 1[7]:add 15 2[7]:add 15 3[7]:add 15 4[7]:add 15
// you can write to stdout for debugging purposes, e.g.
// printf("this is a debug message\n");
#include <stdlib.h>
int compare(const void*a,const void*b){
return (*(int*)a>*(int*)b)?1:(*(int*)a<*(int*)b)?-1:0;
}
int solution(int A[], int N) {
// write your code in C99 (gcc 6.2.0)
int ret=0;
if(N<3) return 0;
qsort(A,N,sizeof(int),compare);
#if 1
if(A[0]==A[N-1]){
for(int a=0;a<N-2;a++){
#if 1
int add=(N-a-2)*(N-a-1)/2;
printf("%d[%d]:add %d\n",a,N,add);
ret+=add;
#else
for(int b=a+1;b<N-1;b++){
int add=N-(b+1);
printf("%d:%d[%d]:add %d\n",a,b,N,add);
ret+=add;
}
#endif
}
return ret;
}
#endif
for(int a=0;a<N-2;a++){
//if(A[a]>=(A[b]+A[c])) break;
for(int b=a+1;b<N-1;b++){
//if(A[b]>=(A[a]+A[N-1])) break;
for(int c=b+1;c<N;c++){
if(A[c]>=(A[a]+A[b])) break;
ret++;
}
}
}
return ret;
}
[1, 1, 1, 1, 1, 1, 1]
function result: 35
0[7]:add 15 1[7]:add 10 2[7]:add 6 3[7]:add 3 4[7]:add 1
// you can write to stdout for debugging purposes, e.g.
// printf("this is a debug message\n");
#include <stdlib.h>
int compare(const void*a,const void*b){
return (*(int*)a>*(int*)b)?1:(*(int*)a<*(int*)b)?-1:0;
}
int solution(int A[], int N) {
// write your code in C99 (gcc 6.2.0)
int ret=0;
if(N<3) return 0;
qsort(A,N,sizeof(int),compare);
#if 1
if(A[0]==A[N-1]){
for(int a=0;a<N-2;a++){
#if 1
int add=(N-a-2)*(N-a-1)/2;
ret+=add;
#else
for(int b=a+1;b<N-1;b++){
int add=N-(b+1);
printf("%d:%d[%d]:add %d\n",a,b,N,add);
ret+=add;
}
#endif
}
return ret;
}
#endif
for(int a=0;a<N-2;a++){
//if(A[a]>=(A[b]+A[c])) break;
for(int b=a+1;b<N-1;b++){
//if(A[b]>=(A[a]+A[N-1])) break;
for(int c=b+1;c<N;c++){
if(A[c]>=(A[a]+A[b])) break;
ret++;
}
}
}
return ret;
}
// you can write to stdout for debugging purposes, e.g.
// printf("this is a debug message\n");
#include <stdlib.h>
int compare(const void*a,const void*b){
return (*(int*)a>*(int*)b)?1:(*(int*)a<*(int*)b)?-1:0;
}
int solution(int A[], int N) {
// write your code in C99 (gcc 6.2.0)
int ret=0;
if(N<3) return 0;
qsort(A,N,sizeof(int),compare);
#if 1
if(A[0]==A[N-1]){
for(int a=0;a<N-2;a++){
#if 1
int add=(N-a-2)*(N-a-1)/2;
// printf("%d[%d]:add %d\n",a,N,add);
ret+=add;
#else
for(int b=a+1;b<N-1;b++){
int add=N-(b+1);
printf("%d:%d[%d]:add %d\n",a,b,N,add);
ret+=add;
}
#endif
}
return ret;
}
#endif
for(int a=0;a<N-2;a++){
//if(A[a]>=(A[b]+A[c])) break;
for(int b=a+1;b<N-1;b++){
//if(A[b]>=(A[a]+A[N-1])) break;
for(int c=b+1;c<N;c++){
if(A[c]>=(A[a]+A[b])) break;
ret++;
}
}
}
return ret;
}
[1, 1, 1, 1, 1, 1, 1]
// you can write to stdout for debugging purposes, e.g.
// printf("this is a debug message\n");
#include <stdlib.h>
int compare(const void*a,const void*b){
return (*(int*)a>*(int*)b)?1:(*(int*)a<*(int*)b)?-1:0;
}
int solution(int A[], int N) {
// write your code in C99 (gcc 6.2.0)
int ret=0;
if(N<3) return 0;
qsort(A,N,sizeof(int),compare);
#if 1
if(A[0]==A[N-1]){
for(int a=0;a<N-2;a++){
#if 1
int add=(N-a-2)*(N-a-1)/2;
// printf("%d[%d]:add %d\n",a,N,add);
ret+=add;
#else
for(int b=a+1;b<N-1;b++){
int add=N-(b+1);
printf("%d:%d[%d]:add %d\n",a,b,N,add);
ret+=add;
}
#endif
}
return ret;
}
#endif
for(int a=0;a<N-2;a++){
//if(A[a]>=(A[b]+A[c])) break;
for(int b=a+1;b<N-1;b++){
//if(A[b]>=(A[a]+A[N-1])) break;
for(int c=b+1;c<N;c++){
if(A[c]>=(A[a]+A[b])) break;
ret++;
}
}
}
return ret;
}
[1, 1, 1, 1, 1, 1, 1]
// you can write to stdout for debugging purposes, e.g.
// printf("this is a debug message\n");
#include <stdlib.h>
int compare(const void*a,const void*b){
return (*(int*)a>*(int*)b)?1:(*(int*)a<*(int*)b)?-1:0;
}
int solution(int A[], int N) {
// write your code in C99 (gcc 6.2.0)
int ret=0;
if(N<3) return 0;
qsort(A,N,sizeof(int),compare);
#if 1
if(A[0]==A[N-1]){
for(int a=0;a<N-2;a++){
#if 1
int add=(N-a-2)*(N-a-1)/2;
// printf("%d[%d]:add %d\n",a,N,add);
ret+=add;
#else
for(int b=a+1;b<N-1;b++){
int add=N-(b+1);
printf("%d:%d[%d]:add %d\n",a,b,N,add);
ret+=add;
}
#endif
}
return ret;
}
#endif
for(int a=0;a<N-2;a++){
//if(A[a]>=(A[b]+A[c])) break;
for(int b=a+1;b<N-1;b++){
//if(A[b]>=(A[a]+A[N-1])) break;
for(int c=b+1;c<N;c++){
if(A[c]>=(A[a]+A[b])) break;
ret++;
}
}
}
return ret;
}
The solution obtained perfect score.