Seating Assignment Problem

[sportsguy90]

Hey all. I have been going crazy these past few days trying to figure out this seating assignment problem and was wondering if someone could help me.

Instructions say:


Assume that a group of n students arrives together for class (or a movie) and that exactly n seats are available consectutively in 1 row. Given m preferences on seating, you are to determine how many wants the students can be seated to statisfy the preferences.

Input

The input will come form the keyboard ONLY. The input will consist of multiple test cases. Each test case begins with two integers 0 < n and 0 ≤ m where n is the number of students to be seated, and m is the number of preferences. For simplicity, assume the students are numbered from 0 to n - 1. Then of m lines follow, each describing a preference, where a line consists of three integers a, b, and c satisfying 0 ≤ a < b < n and 0 < |c| < n. If c is positive then teenagers a and b want to sit at most c seats apart. If c is negative, then a and b want to sit at least -c seats apart. The end of input is signaled by a line consisting of n = m = 0.


Output


The output for each test case is a single line containing the number of possible seating arrangements for the group that satisfy all of the input constraints.

Sample Input
3 1
0 1 -2
3 0
0 0


Sample Output
2
6


Here is my code so far:

#include <vector>
#include <algorithm>
#include <string>
#include <iostream>
#include <iterator>
using namespace std;


struct Preference
{
int a;
int b;                     //Struct with three preferences
int c;
};


int main()
{
int a,b,c,students,numpref;
int count = 0;

vector<Preference> prefs;                                //Vector with struct to store preferences
Preference case1;

cout<<"Enter number of students and preferences: ";
cin>>students>>numpref;                                   //Total Number of students and preferences are entered



for(int i = 0; i<=numpref; i++)
{
cin>>case1.a>>case1.b>>case1.c;                           //Keeps looping until user has entered in all preferences

prefs.push_back(case1);                                   //Stores preferences in vector
cout<<endl;
}

vector<int> v2(a);                                       //Second vector created to store list of students

sort(v2.begin(), v2.end());

while(next_permutation(v2.begin(), v2.end()))            //Finds all permutations of student seating
{
                                   
                                   
}


system("PAUSE");
return 0;
}

I know it incomplete but I am stuck mainly trying to figure out how to compare each line of preferences to the correct permutations and then count the result. I thought about taking the position of each element in the vector that the user put as input(for instance: 0,1 in the example) and checking to see if each permutation that was found had 0 and 1 at least 2 seats between them. But that just wouldn't work.