11742 - Social Constraints

All about problems in Volume 117. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
mmfrb
New poster
Posts: 13
Joined: Thu Aug 30, 2012 3:21 pm

11742 - Social Constraints

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

Code: Select all

#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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11742 - Social Constrants

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

For input

Code: Select all

4 2
0 1 -2
0 1 3
0 0
AC output 12
Check input and AC output for thousands of problems on uDebug!

laituanksa245
New poster
Posts: 20
Joined: Tue Jan 10, 2012 4:23 pm
Location: Vietnam

WA

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11742 - Social Constrants

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

Input:

Code: Select all

8 16
0 3 -6
5 6 -4
2 7 -2
3 6 1
0 3 -7
3 7 2
3 4 2
0 6 2
0 1 -7
1 2 -2
2 3 3
0 3 -6
2 4 7
3 6 -1
1 2 -3
4 5 -5
6 17
2 4 -4
4 5 -4
0 1 -4
1 3 -3
2 3 4
0 1 -5
1 3 -2
3 4 -4
0 4 5
3 4 5
0 1 4
1 3 -2
0 1 4
0 3 3
0 1 3
0 5 -3
0 2 -5
6 9
4 5 -2
2 4 -2
3 4 3
1 4 3
4 5 5
0 3 1
0 2 2
0 4 -1
2 5 5
1 0
7 3
0 1 2
0 1 2
0 1 1
7 4
0 5 -5
0 1 -5
0 6 5
5 6 2
5 5
0 1 -3
0 1 3
0 3 -3
0 2 1
1 3 4
2 4
0 1 -1
0 1 1
0 1 1
0 1 -1
4 5
0 3 2
0 2 -3
0 1 -2
2 3 2
0 2 3
1 0
5 8
3 4 4
2 4 3
0 3 -4
1 3 -4
1 4 3
1 2 -3
0 1 4
1 2 -3
3 15
0 1 -1
0 1 1
0 1 2
0 2 1
1 2 -1
0 2 -2
0 1 -2
0 1 -1
0 1 -2
1 2 1
0 1 2
0 1 1
0 2 -2
0 1 -2
0 1 2
7 15
0 2 -1
3 6 1
0 1 3
2 4 6
1 3 6
2 5 5
1 5 5
0 6 3
4 5 6
1 4 -1
3 4 -6
2 4 2
3 5 2
0 3 -1
0 2 6
5 4
2 3 1
1 3 2
0 2 1
1 4 -4
4 12
0 2 1
1 2 -2
0 2 -3
0 3 3
0 1 -2
0 1 3
1 2 2
1 2 1
0 2 -2
2 3 1
0 3 -3
2 3 3
4 6
0 2 3
1 3 -3
1 2 3
1 2 -2
0 2 -3
1 3 -1
3 2
0 2 1
1 2 2
1 0
4 11
1 2 -2
0 1 2
1 3 -2
0 1 1
0 2 1
0 3 3
0 2 1
0 3 -2
1 2 3
0 1 -1
0 1 1
2 2
0 1 1
0 1 -1
7 12
1 6 -5
4 5 1
0 1 -3
0 2 5
0 3 3
0 1 1
1 3 -6
2 3 6
1 5 2
1 6 -3
2 4 -5
0 1 -4
5 9
2 4 -2
1 4 -4
1 4 1
0 1 4
0 4 4
0 3 2
0 1 3
0 1 -1
0 1 3
4 12
0 2 -2
0 3 -2
0 2 -2
0 1 2
0 1 -2
0 1 1
0 1 1
0 3 -2
2 3 -2
0 3 -1
0 1 -3
0 3 1
7 10
2 3 -2
3 6 -4
0 1 1
0 2 4
0 3 4
0 2 -1
1 5 3
3 4 2
0 5 4
2 4 -2
6 16
0 2 1
0 2 1
1 2 -1
1 4 -5
1 5 4
1 2 5
3 4 -1
1 3 -1
0 4 1
2 5 -1
2 3 -4
3 4 -3
1 2 5
2 3 -4
0 4 -1
0 1 -2
7 0
2 15
0 1 1
0 1 -1
0 1 -1
0 1 -1
0 1 1
0 1 1
0 1 -1
0 1 1
0 1 1
0 1 1
0 1 1
0 1 -1
0 1 1
0 1 1
0 1 -1
5 15
3 4 -3
0 3 -1
0 1 -2
1 4 1
1 4 -3
0 3 -3
1 3 2
2 3 -4
0 1 -3
2 3 4
1 3 4
0 2 -4
1 2 1
2 3 4
0 4 1
2 20
0 1 1
0 1 1
0 1 -1
0 1 -1
0 1 -1
0 1 -1
0 1 1
0 1 1
0 1 1
0 1 1
0 1 -1
0 1 1
0 1 -1
0 1 1
0 1 -1
0 1 -1
0 1 -1
0 1 1
0 1 1
0 1 -1
7 6
1 2 5
0 1 1
3 4 3
2 3 -2
5 6 5
2 3 -6
1 0
8 18
2 4 -1
2 3 -5
3 4 2
4 5 6
4 7 -3
2 3 -2
5 6 -7
0 3 -1
0 1 -4
2 6 4
0 1 -6
0 2 -6
1 7 -6
4 6 5
0 4 4
5 6 -1
0 1 -6
3 5 -6
5 11
0 3 1
1 2 -4
0 1 3
0 1 -4
2 3 -1
0 2 -3
2 3 -2
0 1 -1
1 3 1
2 3 -4
0 1 2
7 4
5 6 4
3 6 4
2 6 -4
0 5 -6
1 0
8 3
2 4 -7
0 2 -1
4 5 -6
2 19
0 1 -1
0 1 -1
0 1 1
0 1 -1
0 1 1
0 1 1
0 1 -1
0 1 -1
0 1 -1
0 1 -1
0 1 1
0 1 -1
0 1 1
0 1 -1
0 1 1
0 1 -1
0 1 -1
0 1 1
0 1 -1
7 7
4 5 -5
1 3 -4
1 4 5
0 5 2
1 3 -5
0 1 -1
1 3 -4
5 12
1 4 3
0 2 -3
0 1 4
1 3 2
0 1 -4
1 3 2
0 1 2
0 2 1
3 4 -1
3 4 -3
0 1 4
2 3 -1
7 7
1 2 -4
0 1 1
0 1 2
0 1 1
0 3 -5
0 4 -4
3 6 -6
7 17
1 5 3
2 4 6
2 3 4
4 5 -3
0 1 -3
1 2 -4
0 1 1
0 3 -3
1 2 -1
3 4 5
0 5 2
0 3 6
5 6 -6
0 2 2
3 4 5
4 6 -5
0 2 3
4 13
0 1 3
0 2 -3
0 1 -3
0 1 2
0 2 2
1 2 3
1 2 -3
0 2 1
0 2 -2
0 1 3
0 2 2
2 3 -3
1 2 -3
6 11
0 1 4
3 5 2
1 3 3
1 3 -1
1 4 4
1 3 5
0 3 -4
1 5 -4
1 4 1
0 2 4
1 3 -3
5 3
0 1 2
1 2 3
3 4 -1
2 15
0 1 -1
0 1 1
0 1 -1
0 1 -1
0 1 1
0 1 1
0 1 1
0 1 1
0 1 -1
0 1 -1
0 1 1
0 1 1
0 1 -1
0 1 -1
0 1 1
5 3
1 2 1
2 4 -3
0 1 -4
4 1
1 2 -1
6 12
0 2 -4
0 4 4
0 4 -4
0 1 1
0 2 1
1 3 -1
1 5 4
0 1 -1
3 5 2
0 2 -4
3 4 2
2 4 5
7 8
2 3 2
3 5 1
0 4 -1
2 3 -3
0 5 1
0 4 3
5 6 -6
0 1 1
2 4
0 1 1
0 1 1
0 1 1
0 1 1
3 14
0 2 -2
0 2 -1
0 1 2
1 2 1
0 1 1
1 2 -1
0 1 2
0 1 1
1 2 1
0 1 -2
0 2 -2
1 2 -2
1 2 2
0 1 2
2 0
5 14
0 2 -2
0 3 -4
0 1 1
0 1 -4
0 3 1
0 3 3
3 4 3
2 4 -4
2 3 -4
1 3 -1
0 2 2
0 4 2
1 4 -4
1 2 -2
2 16
0 1 -1
0 1 -1
0 1 -1
0 1 -1
0 1 -1
0 1 1
0 1 1
0 1 1
0 1 1
0 1 -1
0 1 -1
0 1 -1
0 1 -1
0 1 1
0 1 1
0 1 1
2 5
0 1 1
0 1 1
0 1 -1
0 1 -1
0 1 1
6 7
2 3 1
1 2 -2
1 2 3
4 5 4
0 2 -3
1 3 -1
1 4 2
4 15
0 1 2
2 3 -2
0 3 -3
0 1 3
2 3 -1
0 2 -3
0 1 -1
1 2 -1
0 2 2
0 3 -3
0 2 -1
0 1 -3
0 3 -2
1 2 -1
0 1 -2
4 2
1 2 -3
1 3 2
4 3
0 1 -2
0 2 -3
0 2 -3
4 17
2 3 -2
0 2 -1
1 2 1
0 2 1
0 1 1
0 1 3
1 2 3
0 2 2
0 1 -2
0 1 2
0 1 1
1 2 3
2 3 -1
1 2 -3
0 1 3
0 1 -3
1 2 -3
1 0
4 0
8 1
1 2 1
5 1
1 2 -1
5 1
1 4 -4
2 9
0 1 1
0 1 -1
0 1 1
0 1 -1
0 1 -1
0 1 -1
0 1 1
0 1 -1
0 1 1
7 19
3 4 4
0 5 -6
3 5 5
0 6 3
1 5 6
1 4 -4
3 5 2
3 4 -1
0 5 5
0 1 -6
1 3 4
0 5 -3
2 4 -4
0 6 3
0 3 4
0 5 -4
1 4 4
1 2 6
2 6 5
6 16
2 4 -5
0 2 -1
0 2 -2
0 3 -5
1 2 4
2 3 -5
1 2 -1
4 5 1
0 1 4
3 4 -2
0 3 -4
0 1 5
3 4 3
4 5 -4
0 1 4
0 5 -5
6 11
0 4 -4
2 3 -4
1 3 -2
1 2 -1
4 5 1
1 2 5
3 5 3
3 4 -5
2 3 5
0 1 1
0 4 4
8 11
2 4 -5
0 2 3
0 7 7
1 2 -4
6 7 3
4 7 3
0 1 2
2 3 2
3 5 -5
0 4 -5
1 5 -7
1 0
5 3
1 2 -4
0 2 -1
1 2 -4
8 0
1 0
3 11
0 2 2
0 1 2
0 1 -2
1 2 2
1 2 1
0 1 1
0 1 -1
0 2 -2
1 2 1
0 1 1
0 1 -2
6 8
0 2 3
2 3 1
3 5 5
0 2 5
4 5 -2
2 4 4
1 5 1
1 2 1
6 5
0 1 1
0 2 -1
0 4 -2
3 4 4
1 2 2
5 13
0 1 -1
1 3 -1
0 1 1
0 1 3
0 2 2
0 1 3
0 2 -3
1 2 4
0 1 -1
0 4 -3
3 4 4
1 4 -1
1 2 1
2 14
0 1 1
0 1 -1
0 1 1
0 1 1
0 1 1
0 1 -1
0 1 -1
0 1 -1
0 1 1
0 1 -1
0 1 1
0 1 -1
0 1 -1
0 1 -1
7 5
0 3 -3
2 6 -4
0 2 -4
2 4 3
1 3 -5
8 14
4 5 3
1 3 2
1 5 7
0 1 6
4 6 -4
2 6 7
2 5 -6
6 7 -7
2 7 2
0 2 1
3 5 -4
0 1 5
2 3 -5
0 2 3
7 5
3 6 1
1 2 -3
2 5 1
1 5 1
1 3 6
3 4
0 1 -1
0 1 -2
0 1 1
1 2 -1
5 13
2 3 -4
0 1 -4
0 1 4
0 2 -2
1 3 4
0 4 4
0 2 4
0 3 4
3 4 2
0 1 4
2 3 1
1 4 2
0 3 3
2 14
0 1 -1
0 1 -1
0 1 -1
0 1 1
0 1 1
0 1 -1
0 1 -1
0 1 -1
0 1 1
0 1 -1
0 1 -1
0 1 -1
0 1 -1
0 1 -1
2 3
0 1 -1
0 1 -1
0 1 1
7 8
0 1 -4
4 5 -5
2 6 -3
1 2 1
1 3 3
1 4 -1
1 2 3
0 1 1
3 1
1 2 2
6 8
0 5 3
2 3 2
0 1 5
0 2 3
0 1 -1
0 1 1
0 2 3
3 4 4
8 1
0 3 -1
8 7
3 4 -1
3 6 4
3 6 1
0 3 -3
1 4 -4
3 5 7
1 5 -1
7 17
3 6 4
1 2 -3
1 3 -4
0 2 1
4 5 -3
0 1 2
0 3 -6
0 1 3
2 4 -3
2 4 3
0 1 1
4 6 -5
2 5 -1
0 1 -4
1 2 3
1 2 -3
2 4 -1
5 18
0 2 4
0 2 4
0 1 -3
0 2 2
0 4 1
1 2 3
1 2 4
1 2 2
0 4 -3
0 1 3
0 2 4
1 2 -3
0 2 4
0 2 -1
0 2 2
2 4 3
0 3 -4
1 3 -4
7 16
3 4 1
3 6 -6
0 1 1
1 3 4
4 6 4
1 6 6
0 6 5
1 3 3
0 4 -1
1 4 -2
5 6 6
0 4 -5
0 5 -6
0 1 2
1 2 3
0 5 5
1 0
1 0
1 0
3 19
0 2 -1
1 2 1
0 2 -2
0 1 1
0 1 -1
0 1 -1
1 2 2
1 2 -1
0 2 -2
1 2 -2
0 2 1
0 1 -1
0 2 1
0 2 -1
0 1 2
0 1 1
1 2 -2
0 1 1
0 1 -2
7 15
2 4 3
1 2 3
0 1 3
2 4 6
2 4 -5
0 2 5
0 5 5
0 2 -5
0 3 -5
1 5 -6
3 5 6
0 5 -4
3 4 -1
1 5 -2
0 1 2
5 17
0 1 -3
0 3 -3
0 1 1
0 4 -1
2 3 1
0 2 -1
1 3 1
0 2 1
0 1 2
2 3 -2
1 2 1
0 2 -2
1 2 -4
3 4 1
0 4 -1
0 1 3
3 4 -1
0 0
AC output:

Code: Select all

0
0
22
1
1440
36
2
2
2
1
0
0
6
2
0
0
4
1
2
2
0
0
0
74
0
5040
2
0
2
56
1
0
0
12
1
240
2
16
0
0
0
0
2
76
2
0
24
0
0
2
0
2
0
2
2
36
0
4
2
0
1
24
10080
120
12
2
0
0
0
0
1
12
40320
1
0
8
96
0
2
8
0
0
0
0
2
2
0
6
66
40320
2136
0
0
0
1
1
1
0
0
0
Check input and AC output for thousands of problems on uDebug!

gaborg
New poster
Posts: 1
Joined: Thu Dec 05, 2013 6:27 pm

Re: 11742 - Social Constrants

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
Learning poster
Posts: 96
Joined: Tue Apr 23, 2013 12:54 pm

Re: 11742 - Social Constraints

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11742 - Social Constraints

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

0 ? m ? 20
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 117 (11700-11799)”