11742 - Social Constraints

mmfrb · Post by **mmfrb** » Tue Sep 25, 2012 4:28 pm

I think it is a silly mistake, since nobody openned this thread before. Why WA? Thanks

#include <cstdio>
#include <algorithm>
#include <map>
#include <iostream>
#include <sstream>
#include <string>

using namespace std;

int n, m, x, y, condition, howMany;
map <string, int> conditions;
int permutArray[8] = {0, 1, 2, 3, 4, 5, 6, 7};

string toString(int x, int y)
{
	ostringstream os;
	os << x; os << y;
	string n_str = os.str();
	return n_str;
}

int findPosition(int a)
{
	int retorno = 0;
	for(int i = 0; i < n; ++i)
	{
		if(permutArray[i] == a)
		{
			retorno = i;
			break;
		}
	}
	return retorno;
}

int abs(int a)
{
	return (a > 0) ? a : (-1)*a;
}



int main()
{
	while(true)
	{
		scanf("%d%d", &n, &m);
		if(n == 0 && m == 0) break;
		howMany = 0;
		conditions.clear();
		while(m--)
		{
			scanf("%d %d %d", &x, &y, &condition);
			conditions[toString(x, y)] = condition;
		}
		do
		{
			bool isValid = true;
			for(map <string, int>::iterator it = conditions.begin(); it != conditions.end(); ++it)
			{
				if((*it).second < 0)
				{
					if(!(abs(findPosition((*it).first[0] - '0') - findPosition((*it).first[1] - '0'))  >= (-1)*(*it).second))
					{
						isValid = false;
						break;
					}
				}
				else
				{
					if(!(abs(findPosition((*it).first[0] - '0') - findPosition((*it).first[1] - '0'))  <= (*it).second))
					{
						isValid = false;
						break;
					}
				}
			}
			if(isValid) howMany++;
		}while(next_permutation(permutArray, permutArray +n));
		printf("%d\n", howMany);
	}
	return 0;
}

brianfry713 · Post by **brianfry713** » Tue Sep 25, 2012 10:05 pm

For input

Code: Select all

AC output 12

laituanksa245 · Post by **laituanksa245** » Sun Sep 30, 2012 1:31 am

What's wrong with my code ? I have tried many test cases but still i can not figure out what is wrong with my code. Help me plz.

Code: Select all

#include <iostream>
using namespace std;
int n,m;
int AtLeast [10][10];
int AtMost [10][10];
bool used [10];
int data[10];
long rs = 0;
int absolute (int a)
{
    if (a < 0)
       return -a;
    return a;
}
void generate (int now)
{
     for (int i = 0; i < n; i++)
     if (used[i] == false)
     {
                 bool test = true;
                 for (int j = 0; j < now; j++)
                 {
                     if (absolute (now-j) > AtMost[i][data[j]] && AtMost[i][data[j]] != -1) 
                     {
                                  test = false;
                                  break;
                     }
                     if (absolute (now-j) < AtLeast[i][data[j]] && AtLeast[i][data[j]] != -1)
                     {
                                  test = false;
                                  break;
                     }
                 }
                 if (test)
                 {
                          data[now]  = i;
                          used[i] = true;
                          if (now == n-1)
                             rs++;
                          else
                              generate (now+1);
                          used[i] = false;
                 }
     }
}
int main ()
{
    int a,b,c;
    while (true)
    {
          cin >> n >> m;
          if (n == 0 && m == 0)
             break;
          for (int i = 0; i < n; i++)
          for (int j = 0; j < n; j++)
          {
              AtLeast[i][j] = -1;
              AtMost[i][j] = -1;
          }
          for (int i = 0; i < m; i++)
          {
              cin >> a >> b >> c;
              if (c < 0)
              {
                 AtLeast[a][b] = -c;
                 AtLeast[b][a] = -c;
              }
              else
              if (c > 0)
              {
                 AtMost[a][b] = c;
                 AtMost[b][a] = c;
              }
          }
          for (int i = 0; i < n; i++)
              used[i] = false;
          rs = 0;
          generate (0);
          cout << rs << "\n";
    }
}

brianfry713 · Post by **brianfry713** » Mon Oct 01, 2012 11:25 pm

Input:

Code: Select all

AC output:

Code: Select all

gaborg · Post by **gaborg** » Thu Dec 05, 2013 6:40 pm

The problem description says

... a line consists of three integers a,b,c satisfying 0 ? a < b < n ...

This is not true. I kept getting WA results until I found out that b < a was possible.

Repon kumar Roy · Post by **Repon kumar Roy** » Thu Sep 18, 2014 8:50 am

Getting TLE

Code: Select all


#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<vector>
#include<map>
#include<queue>
#include<stack>
#include<cstdlib>
#include<algorithm>
#include<set>
#include<iterator>
#include<cassert>
#include <sstream>
using namespace std;


int n,m;

int arr[]={0,1,2,3,4,5,6,7,8};
struct Node {
    int fi, last,dis;
};

Node list[10];

bool check()
{
    int pos[10];
    for(int i=0;i<n;i++){
        pos[arr[i]] = i;
    }
    for (int i=0; i<m; i++) {
        if(list[i].dis> 0 && abs(pos[list[i].fi] - pos[list[i].last]) > list[i].dis) {
            return false;
        }
        else if(list[i].dis<0 && abs(pos[list[i].fi]-pos[list[i].last]) < list[i].dis* -1){
            return false;
        }
    }
    return true;
}
int main()

{
    
    
    int cnt=0,a,b,c;
    while (scanf("%d %d",&n,&m)==2) {
        if(n==0 && m==0) break;
        cnt=0;
        sort(arr, arr + 9);
        for(int k=0;k<m;k++){
            scanf("%d %d %d",&a,&b,&c);
            list[k].fi = a ;
            list[k].last = b;
            list[k].dis = c;
        }
        do {
            if(check()){
                cnt++;
            }
        } while (next_permutation(arr, arr+n));
        
        cout<<cnt<<"\n";
    }
    
    return 0;
    
}

brianfry713 · Post by **brianfry713** » Thu Sep 18, 2014 9:03 pm

0 ? m ? 20

OJ Board

11742 - Social Constraints

11742 - Social Constraints

Re: 11742 - Social Constrants

WA

Re: 11742 - Social Constrants

Re: 11742 - Social Constrants

Re: 11742 - Social Constraints

Re: 11742 - Social Constraints