## 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

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

### 11742 - Social Constraints

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

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

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

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

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

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

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