Cod sursa(job #137051)

Utilizator floringh06Florin Ghesu floringh06 Data 16 februarie 2008 20:07:04
Problema Loto Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.17 kb
#include <cstdio>
#include <algorithm>

using namespace std;

#define FIN "loto.in"
#define FOUT "loto.out"
#define MAX_N 105

typedef struct
{
        int x, y, z;
        int s;
} structure;

int A[MAX_N];
structure B[MAX_N*MAX_N*MAX_N];
int N, S, i, j, k;

struct cmp{  
              bool operator () (const structure &a, const structure &b) const  
              {  
                   if (a.s < b.s) return 1; 
                   return 0;  
              }  
          };  


        int main ()
        {
            freopen (FIN, "r", stdin);
            freopen (FOUT, "w", stdout);
            
            scanf ("%d %d", &N, &S);
            for (i = 1; i <= N; ++i)
                scanf ("%d", A + i);
                
            int nd = 0;
            for (i = 1; i <= N; ++i)
                for (j = 1; j <= N; ++j)
                    for (k = 1; k <= N; ++k)
                    {
                        ++nd;
                        B[nd].s = A[i] + A[j] + A[k], B[nd].x = A[i], B[nd].y = A[j], B[nd].z = A[k];
                    }
            
            sort (B + 1, B + nd + 1, cmp());
            
            for (i = 1; i <= nd; ++i)
                printf ("%d %d %d %d\n", B[i].x, B[i].y, B[i].z, B[i].s);
            
            for (i = 1; i <= nd; ++i)
                if (B[i].s < S - B[i].s)
                {
                           int li = i; int lf = nd;
                           int m;
                           while (li <= lf)
                           {
                                 m = (li + lf) >> 1;
                                 if (B[m].s == S - B[i].s) break;
                                 if (B[m].s < S - B[i].s) li = m + 1;
                                    else lf = m - 1;
                           }
                           
                           if (B[m].s == S - B[i].s) 
                           {
                                      printf ("%d %d %d %d %d %d", B[m].x, B[m].y, B[m].z, B[i].x, B[i].y, B[i].z);
                                      return 0;
                           }
                }
            
            return 0;
        }