Click here to Skip to main content
Rate this: bad
good
Please Sign up or sign in to vote.
See more: C++ C Java Perl Python
Module the answer by 1007...........what does this statement mean?I am getting a answer but final answer is determined by this statement????
 
i am getting a number>=0 and that number is answer but probblem states Module the answer by 1007
 
here is problem:
There are n variables and m requirements. Requirements are represented as (x <= y), which means the x-th variable must be smaller or equal to the y-th variable. Assign nonnegative numbers smaller than 10 to each variable. Please calculate how many different assignments that match all requirements. Two assignments are different if and only if at least one variable is assigned different number in these two assignment. Module the answer by 1007.
 
Input Format:
First line of the input contains two integers n and m. Then following m lines each containing 2 space-seperated integers x and y, which means a requirement (x <= y).
 
Output Format:
Output the answer in one line.
 
Constraints:
0 < n < 14
0 < m < 200
0 <= x, y < n
 
Sample Input:
6 7
1 3
0 1
2 4
0 4
2 5
3 4
0 2
 
Sample Output: 1000
 
EDIT: added more information from a comment below - lewax00
Posted 12-Apr-12 7:39am
Edited 12-Apr-12 8:57am
lewax0046.1K
v3
Comments
Chuck O'Toole at 12-Apr-12 13:48pm
   
The messasge would make much more sense if we knew what issued it. You tagged this with every known language (hyperbole intended).
Rate this: bad
good
Please Sign up or sign in to vote.

Solution 1

that statement doesn't mean anything.
 
are you sure it doesn't say "Modulate the answer by 1007" ?
  Permalink  
Comments
SALIL GAURAV at 12-Apr-12 13:58pm
   
it is "Module the answer by 1007"
SALIL GAURAV at 12-Apr-12 14:00pm
   
i am getting a number>=0 and that number is answer but probblem states Module the answer by 1007
Chris Losinger at 12-Apr-12 14:12pm
   
"Module" is not an English verb. You can't "module" anything.
 
you can modulate a number: x = x % 1007;
Rate this: bad
good
Please Sign up or sign in to vote.

Solution 2

Shot in the dark here..but I assume it meant modulo not module, in that case that would be the operation used to find the remainder from division, in many languages "%" is used for this, so in your case something along the lines of
someNumber % 1007
That's the best I can offer with what litte information you gave.
  Permalink  
Comments
SALIL GAURAV at 12-Apr-12 14:06pm
   
thanks.....but it's not modulo.......because i have tried modulo and it's not satisfying the answer
lewax00 at 12-Apr-12 14:21pm
   
Then I'd recheck the rest of your program, because that's the most sense I can make of it. If you posted more information (for example, your code and the complete problem) we may be able to help your further.
SALIL GAURAV at 12-Apr-12 14:34pm
   
here is problem:
 
There are n variables and m requirements. Requirements are represented as (x <= y), which means the x-th variable must be smaller or equal to the y-th variable. Assign nonnegative numbers smaller than 10 to each variable. Please calculate how many different assignments that match all requirements. Two assignments are different if and only if at least one variable is assigned different number in these two assignment. Module the answer by 1007.
 

Input Format:
First line of the input contains two integers n and m.
Then following m lines each containing 2 space-seperated integers x and y, which means a requirement (x <= y).

Output Format:
Output the answer in one line.

Constraints:
0 < n < 14
0 < m < 200
0 <= x, y < n

Sample Input:
6 7
1 3
0 1
2 4
0 4
2 5
3 4
0 2

Sample Output:
1000
johny10151981 at 12-Apr-12 21:38pm
   
You need to explain what is Module the answer by 1007, because i found only 19 matches, or may be i didnt understand the problem
Rate this: bad
good
Please Sign up or sign in to vote.

Solution 3

Brute force approach (let the computer calculate the problem as stated) for the sample data results in:
count = 25168 % 1007 = 1000
Hence, I dare to state that "Module" means modulo.
Cheers
Andi
 
PS: The code (a quick and dense hack to get going):
static int Loop(int x, List<int> v, Func<bool> check)
{
    if (x == 0) return check() ? 1 : 0;
    int pos = v.Count() - x;
    return Enumerable.Range(0, 10)
           .Aggregate(0, (r, i) =>
               { v[pos] = i; return r += Loop(x - 1, v, check); });
}
 
static void CheckProblem(int n, params Tuple<int, int>[] req)
{
    List<int> v = new List<int>(new int[n]);
    int count = Loop(n, v, ()=>
                   req.Aggregate(true, (r, p) => r && v[p.Item1] <= v[p.Item2]));
    Console.WriteLine("count = {0} % 1007 = {1}", count, count % 1007);
}
 
static void Main(string[] args)
{
    Func<int, int, Tuple<int, int>> r = (a, b) => new Tuple<int, int>(a, b);
    CheckProblem(6, r(1,3), r(0,1), r(2,4), r(0,4), r(2,5), r(3,4), r(0,2));
}
  Permalink  
v3
Comments
SALIL GAURAV at 13-Apr-12 3:40am
   
thanks....but this is a sample test case......it must satisfy other test cases also.....
Andreas Gieriet at 13-Apr-12 4:20am
   
Uups: I did it in C# and not in C/C++/Perl/... Sorry.
But the question about modulo is solved, I think, and you have sample data (count = 25168) to check your solution against.
 
In C#, you simply need to read in values for n and the requirements pairs and finally pass the data to the CheckProblem(n, reqList) function.
 
Cheers
Andi
Andreas Gieriet at 13-Apr-12 5:15am
   
See my C++ solution#5.
Cheers
Andi
Rate this: bad
good
Please Sign up or sign in to vote.

Solution 4

here is my code to above problem:.....
#include<stdio.h>
#include<stdlib.h>
typedef struct com
{
    int a;
    int b;
}com;
int comp(com *a,int m)//this function checks the repeated pair and count them
{
    int i=0;
    int j=0;
    int c=0;
    for(j=0;j<m-1;j++)
    {
    for(i=1;i<=m-1-j;i++)
    {
        if(a[j].a==a[j+i].a&&a[j].b==a[j+i].b&&a[j].a!=-1&&a[j].b!=-1)
        {
            c=c+1;
            a[i+j].a=-1;
            a[i+j].b=-1;
 
                }
                }
                }
              //printf("%d",c);
    return c;
}
void main()
{
    int n,m;
    com *a,*d;
    int i;
    int c=0,r;
 
    scanf("%d %d",&n,&m);
    a=(com *) malloc(sizeof(com)*m);
    d=(com *) malloc(sizeof(com)*m);
    for(i=0;i<m;i++)
    {
        scanf("%d %d",&a[i].a,&a[i].b);
        d[i].a=a[i].a;
        d[i].b=a[i].b;
        if(a[i].a<=a[i].b&&a[i].b<n&&a[i].a>=0)
        {
            c=c+1;
            }
    }
    r=comp(d,m);
 

     c=c-r;//it is the no of distinct pair
         printf("%d",1007-(c%1007));//a try for final answer but this does not satisfy other test cases

}
  Permalink  
Comments
Andreas Gieriet at 13-Apr-12 4:29am
   
Does this solve your problem or is this a request to help solving it?
Rate this: bad
good
Please Sign up or sign in to vote.

Solution 5

Now the C++ version of Solution#3 above:
#include <iostream>
#include <vector>
#include <cassert>

using namespace std;
 
class Requirements
{
private:
	class Req
	{
	public:
		Req(): _x(0), _y(0) {}
		Req(int x, int y): _x(x), _y(y) {}
		int x() { return _x; }
		int y() { return _y; }
	private:
		int _x;
		int _y;
	};
 
	vector<Req> _req;
	size_t _n;
	size_t _m;
public:
	Requirements(size_t n, size_t m): _req(), _n(n), _m(m) {	}
	bool Add(int x, int y)
	{
		assert(_req.size() < _m);
		if (x < 0) return false;
		if (y < 0) return false;
		if (x >= int(_n)) return false;
		if (y >= int(_n)) return false;
		if (x >= y) return false;
		_req.push_back(Req(x,y));
		return true;
	}
	bool Check(vector<int>& v)
	{
		assert(v.size() == _n);
		for(size_t i = 0; i < _m; ++i)
		{
			if (v[_req[i].x()] > v[_req[i].y()]) return false;
		}
		return true;
	}
};
 
class Values
{
private:
	vector<int> _v;
	Requirements& _req;
public:
	Values(size_t n, Requirements& req): _v(n), _req(req) {}
	int Loop(int i)
	{
		if (i == 0) return _req.Check(_v) ? 1 : 0;
		int count = 0;
		size_t pos = _v.size() - i;
		for(int k = 0; k < 10; ++k)
		{
			_v[pos] = k;
			count += Loop(i-1);
		}
		return count;
	}
};
 
int main()
{
	size_t n, m;
	cout << "please enter: n m: ";
	cin >> n >> m;
	
	Requirements req(n, m);
	Values v(n, req);
 
	for(size_t i = 0; i < m; ++i)
	{
		int a,b;
		cout << "please enter req #" << i+1 << " (x <= y): x y: ";
		cin >> a >> b;
		req.Add(a,b);
	}
	int count = v.Loop(n);
	cout << "count = " << count << " % 1007 = " << (count % 1007) << "\n";
}
 
Output:
count = 25168 % 1007 = 1000
 
Cheers
Andi
  Permalink  

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

  Print Answers RSS
0 OriginalGriff 6,649
1 Sergey Alexandrovich Kryukov 6,270
2 CPallini 5,190
3 George Jonsson 3,574
4 Gihan Liyanage 2,522


Advertise | Privacy | Mobile
Web03 | 2.8.140916.1 | Last Updated 13 Apr 2012
Copyright © CodeProject, 1999-2014
All Rights Reserved. Terms of Service
Layout: fixed | fluid

CodeProject, 503-250 Ferrand Drive Toronto Ontario, M3C 3G8 Canada +1 416-849-8900 x 100