#include #include #define MAXVILLAGES 10000 #define MAXQUERIES 100 typedef int Tprvok[3]; typedef Tprvok Tpole[MAXQUERIES]; typedef int Tvil[MAXVILLAGES][MAXVILLAGES]; typedef Tvil *Pvil; void sort(Tpole pole,int zac,int kon,int dest) { int i=zac; int j=kon; int x=pole[(zac+kon)/2][dest]; Tprvok q; do { while (pole[i][dest]x) j--; if (ij)); if (zaci) sort(pole,i,kon,dest); } int find(Tpole pole,int N,int value) { int i=0; int j=N-1; do{ int x=(i+j)/2; if (value==pole[i][0]){ return i; }else if (value==pole[j][0]){ return j; }else if (value==pole[x][0]){ return x; }else if (value>pole[x][0]){ i=x; }else{ j=x; } }while((j-i)>1); return (-1); } int browse(Pvil vil,Tpole pole,int used[],int Nvil,int Npole,int v,int p,int r,int min,int max) { int index; for (int i=0;(i0)||(i==0));i++){ if (((*vil)[v][i]!=0)&&(used[i]==0)){ p+=(*vil)[v][i]; if (p<=max) { if (p>=min) index=find(pole,Npole,p); else index=-1; if ((index!=-1)&&(pole[index][2]==0)){ r--; pole[index][2]=1; } used[i]=1; r=browse(vil,pole,used,Nvil,Npole,i,p,r,min,max); used[i]=0; } p-=(*vil)[v][i]; } } return r; } int main() { int N; //matica ci maju spolocnu hodnotu Pvil villages = (Pvil)malloc(sizeof(Tvil)); int used[MAXVILLAGES]; //ceny jednotlivych jazd Tpole queries; int queryNr=0; scanf("%i",&N); //vynulovanie for (int i=0;i0);i++){ count=browse(villages,queries,used,N,queryNr,i,0,count,0,queries[queryNr-1][0]); } sort(queries,0,queryNr-1,1); for (int i=0;i