UNISTAM: August 2018

Saturday, August 25, 2018

STABLE MARRIAGE PROBLEM

Problem Description

There are given n men and n women. Each woman ranks all men in order of her preference (her first choice, her second choice, and so on). Similarly, each man sorts all women according to his preference. The goal is to arrange n marriages in such a way that if a man m prefers some woman w more than his wife, and w prefers m more then her husband a new marriage occurs between w and m. If w prefers her husband more, then she stays married to him. This problem always has a solution and your task is to find one.

Input

The first line contains a positive integer t<=100 indicating the number of test cases. Each test case is an instance of the stable marriage problem defined above. The first line of each test case is a positive integer n<=500 (the number of marriages to find). The next n lines are the woman's preferences: ith line contains the number i (which means that this is the list given by the ith woman) and the numbers of men (the first choice of ith woman, the second choice,...). Then, the men's preferences follow in the same format.

Output

For each test case print n lines, where each line contains two numbers m and w, which means that the man number m and the woman number w should get married
CODING ARENA
#include <stdio.h>

int men[10][10];

int women[10][10];

int mmark[10]={0};

int mc[10]={0};

int wc[10]={0};

int inp()

{

int n=0;

int ch=getchar();

while(!(ch>='0'&&ch<='9'))

ch=getchar();

while(ch>='0'&&ch<='9')

n=(n<<3)+(n<<1)+ch-'0',ch=getchar();

return n;

}

int func1(int w,int m,int m1,int n)

{

int i;

for(i=1;i<=n;i++)

{

if(women[w][i]==m)

return 1;

else

if(women[w][i]==m1)

return 0;

}

return 0;

}

void stablemarriage(int n)

{

int i,c;

for(i=0;i<=n;i++)

{

mmark[i]=0;

wc[i]=-1;

}

c=n;

while(c>0)

{

int m;

for(m=1;m<=n;m++)

for(i=1;i<=n&&mmark[m]==0;i++)

{

int w=men[m][i];

if(wc[w]==-1)

{

wc[w]=m;

mmark[m]=1;

c--;

}

else

{

int m1=wc[w];

if(func1(w,m,m1,n))

{

wc[w]=m;

mmark[m]=1;

mmark[m1]=0;

}

}

}

}

}

int main()

{

int n,t,i,j;

t=inp();

while(t--)

{

n=inp();

for(i=1;i<=n;i++)

for(j=0;j<=n;j++)

women[i][j]=inp();

for(i=1;i<=n;i++)

for(j=0;j<=n;j++)

men[i][j]=inp();

stablemarriage(n);

for(i=1;i<=n;i++)

{

mc[wc[i]]=i;

}

for(i=1;i<=n;i++)

printf("%d %d\n",i,mc[i]);

}

return 0;

}

Test Case 1

Input (stdin)

2

4

1 4 3 1 2

2 2 1 3 4

3 1 3 4 2

4 4 3 1 2

1 3 2 4 1

2 2 3 1 4

3 3 1 2 4

4 3 2 4 1

7

1 3 4 2 1 6 7 5

2 6 4 2 3 5 1 7

3 6 3 5 7 2 4 1

4 1 6 3 2 4 7 5

5 1 6 5 3 4 7 2

6 1 7 3 4 5 6 2

7 5 6 2 4 3 7 1

1 4 5 3 7 2 6 1

2 5 6 4 7 3 2 1

3 1 6 5 4 3 7 2

4 3 5 6 7 2 4 1

5 1 7 6 4 3 5 2

6 6 3 7 5 2 4 1

7 1 7 4 2 6 5 3

Expected Output

Test Case 2

Input (stdin)

Expected Output

CLEANING UP

Problem Description

After a long and successful day of preparing food for the banquet, it is time to clean up. There is a list of n jobs to do before the kitchen can be closed for the night. These jobs are indexed from 1 to n.

Most of the cooks have already left and only the Chef and his assistant are left to clean up. Thankfully, some of the cooks took care of some of the jobs before they left so only a subset of the n jobs remain. The Chef and his assistant divide up the remaining jobs in the following manner. The Chef takes the unfinished job with least index, the assistant takes the unfinished job with the second least index, the Chef takes the unfinished job with the third least index, etc. That is, if the unfinished jobs were listed in increasing order of their index then the Chef would take every other one starting with the first job in the list and the assistant would take every other one starting with the second job on in the list.

The cooks logged which jobs they finished before they left. Unfortunately, these jobs were not recorded in any particular order. Given an unsorted list of finished jobs, you are to determine which jobs the Chef must complete and which jobs his assistant must complete before closing the kitchen for the evening.

Input
The first line contains a single integer T 50 indicating the number of test cases to follow. Each test case consists of two lines. The first line contains two numbers n,m satisfying 0 m n 1000. Here, n is the total number of jobs that must be completed before closing and m is the number of jobs that have already been completed. The second line contains a list of m distinct integers between 1 and n. These are the indices of the jobs that have already been completed. Consecutive integers are separated by a single space.

Output
The output for each test case consists of two lines. The first line is a list of the indices of the jobs assigned to the Chef. The second line is a list of the indices of the jobs assigned to his assistant. Both lists must appear in increasing order of indices and consecutive integers should be separated by a single space. If either the Chef or the assistant is not assigned any jobs, then their corresponding line should be blank.
CODING ARENA
#include <stdio.h>

int a[100];

void reset()

{

int i;

for(i=0;i<100;i++)

a[i]=-1;

}

int toggle(int a)

{

if(a==1)

return 0;

else

return 1;

}

int main()

{

int n,i,j,m,t,k;

scanf("%d",&t);

while(t--)

{

reset();

scanf("%d",&n);

scanf("%d",&m);

for(i=1;i<=m;i++)

{

scanf("%d",&j);

a[j]=2;

}

k=1;

for(i=1;i<=n;i++)

{

if(a[i]!=2)

{

a[i]=k;

k=toggle(k);

}

}

for(i=1;i<=n;i++)

{

if(a[i]==1)

printf("%d ",i);

}

printf("\n");

for(i=1;i<=n;i++)

{

if(a[i]==0)

printf("%d ",i);

}

printf("\n");

}

return 0;

}

Test Case 1

Input (stdin)

Expected Output

Test Case 2

Input (stdin)
```
0
```
Expected Output
```
0
```

SHERLOCK HOMES

Problem Description

There is a mysterious temple in Mysteryland. The door of the temple is always closed.It can only be opened by a unique procedure.There are two boxes and N items outside the temple.Sherlock homes visits the temple many times.Each time Sherlock holmes visits the temple,the number of items N outside the door of the temple is changed but each time he anyhow manages to know the cost of those N items.The door of the temple can only be opened if those "N items" are distributed in those two boxes such that the sum of cost of items in one box is equal to the sum of cost of items in other box.Sherlock homes is trying to do such a distribution so as to open the door of the temple.you have to tell whether the door the temple can be opened or not.

INPUT

the first line contain the number of test cases i.e the number of time sherlock homes visits the temple. Next lines contains the description of those test cases.For the first line contain number of items "N".The second line contains cost of those N items.

OUTPUT

output "YES" if the door of the temple can be opened otherwise output "NO".

Constraint:

1 <= testcases <= 10

1 <= N <= 100

1 <= cost <= 100
Explanation
there are three testcases testcase 1:the items can be distributed in the boxes as 4,3,3 ,5,5 so output is YES testcase 2: the items can be distributed in the boxes as 4,1 3,2 so output is YES testcase 3: such a distribution is not possible.
CODING ARENA
#include <stdio.h>

int main()

{

int t,n,i,a[100],b,f=1,sum=0,s=0;

scanf("%d",&t);

while(t>0)

{

scanf("%d",&n);

i=0;

while(i<n)

{

scanf("%d",&a[i]);

i++;

}

i=0;

while(i<n)

{

sum=sum+a[i];

i++;

}

if(sum%2!=0)

{

f=0;

}

else

{

i=0;

b=sum/2;

while(i<n)

{

if(a[i]==b)

{

f=1;

break;

}

else

if(a[i]>b)

{

f=0;

break;

}

else

{

if((s+a[i])<=b)

{

s=s+a[i];

if(s==b)

{

f=1;

break;

}

}

}

i++;

}

}

if(f==0)

{

printf("NO\n");

}

else

{

printf("YES\n");

}

f=1;

sum=0;

s=0;

t--;

}

return 0;

}

Test Case 1

Input (stdin)

Expected Output

YES

YES

NO

Test Case 2

Input (stdin)

2

10

1 1 1 1 1 1 1 1 1 1

3

1 2 1

Expected Output

YES

YES

SUM OF POSITIVE NUMBERS

Problem Description

Write a program to find the sum of positive numbers in an array.

Input Format:
Input consists of n+1 integers. The first integer corresponds to n , the size of the array. The next ?n? integers correspond to the elements in the array. Assume that the maximum value of n is 15.

Output Format:
Refer sample output for details
CODING ARENA
#include <stdio.h>

int main()

{

int num,a[100],sum=0,i;

scanf("%d",&num);

for(i=0;i<num;i++)

scanf("%d",&a[i]);

for(i=0;i<num;i++)

{

if(a[i]>=0)

{

sum=sum+a[i];

}

}

printf("sum=%d",sum);

return 0;

}
Test Case 1

Input (stdin)
```
5

2 3 6 8 -1
```
Expected Output
```
sum=19
```
Test Case 2

Input (stdin)
```
5

-1 -2 -3 -4 -5
```
Expected Output
```
sum=0
```

REPORT AND ADD!!

Problem Description

Lakshmans favourite subject is maths. He is interested to do calculations. His maths teacher ask him to write a code to detect the numbers which are divided by 5 and the output will be the number of dividents and their sum value.

Your task is to help Lakshman to complete the work.
CODING ARENA
#include <stdio.h>

int main()

{

int i,num1,num2,count=0,sum=0;

scanf("%d %d",&num1,&num2);

for(i=num1;i<num2;i++)

{

if(i%5==0)

{

count++;

sum=sum+i;

}

}

printf("%d %d",count,sum);

return 0;

}
Test Case 1

Input (stdin)
```
50 100
```
Expected Output
```
10 725
```
Test Case 2

Input (stdin)
```
19 29
```
Expected Output
```
3 45
```

COIN FLIP

Problem Description

Little Elephant was fond of inventing new games. After a lot of research, Little Elephant came to know that most of the animals in the forest were showing less interest to play the multi-player games.Little Elephant had started to invent single player games, and succeeded in inventing the new single player game named COIN FLIP.

In this game the player will use N coins numbered from 1 to N, and all the coins will be facing in ""Same direction"" (Either Head or Tail),which will be decided by the player before starting of the game.

The player needs to play N rounds.In the k-th round the player will flip the face of the all coins whose number is less than or equal to k. That is, the face of coin i will be reversed, from Head to Tail, or, from Tail to Head, for i k.

Elephant needs to guess the total number of coins showing a particular face after playing N rounds. Elephant really becomes quite fond of this game COIN FLIP, so Elephant plays G times. Please help the Elephant to find out the answer.
Input

The first line of input contains an integer T, denoting the number of test cases. Then T test cases follow.

The first line of each test contains an integer G, denoting the number of games played by Elephant. Each of the following G lines denotes a single game, and contains 3 space separeted integers I, N, Q, where I denotes the initial state of the coins, N denotes the number of coins and rounds, and Q, which is either 1, or 2 as explained below.

Here I=1 means all coins are showing Head in the start of the game, and I=2 means all coins are showing Tail in the start of the game. Q=1 means Elephant needs to guess the total number of coins showing Head in the end of the game, and Q=2 means Elephant needs to guess the total number of coins showing Tail in the end of the game.
Output

For each game, output one integer denoting the total number of coins showing the particular face in the end of the game.
Constraints

1 <= T <= 10
1 <= G <=20000
1 <= N <= 109
1<= I <= 2
1 <= Q<= 2
CODING ARENA
#include <stdio.h>

#include <stdlib.h>

#define gc getchar_unlocked

#define pc putchar_unlocked

inline int scan()

{

register int c=gc();

int x=0;

for(;(c<48||c>57);c=gc());

for(;(c>47&&c<58);c=gc())

{

x=(x<<1)+(x<<3)+c-48;

}

return x;

}

inline void print(int a)

{

char snum[20];

int i=0;

do

{

snum[i++]=a%10+48;

a=a/10;

}

while(a!=0);

i=-1;

while(i>=0)

{

pc(snum[i--]);

pc('\n');

}

}

int main(void)

{

int t,g,i,q,n;

t=scan();

while(t--)

{

g=scan();

while(g--)

{

i=scan();

n=scan();

q=scan();

if((i==q)||(n&1)==0)

{

printf("%d\n",n/2);

}

else if(i!=q)

{

printf("%d\n",(n/2)+1);

}

}

}

return 0;

}
Test Case 1

Input (stdin)
```
1

2

1 5 1

1 5 2
```
Expected Output
```
2

3
```
Test Case 2

Input (stdin)
```
1

3

1 2 1

1 2 2

2 1 1
```
Expected Output
```
1

1

1
```

Saturday, August 25, 2018

STABLE MARRIAGE PROBLEM

Problem Description

CODING ARENA

#include <stdio.h>

int men[10][10];

int women[10][10];

int mmark[10]={0};

int mc[10]={0};

int wc[10]={0};

int inp()

{

int n=0;

int ch=getchar();

while(!(ch>='0'&&ch<='9'))

ch=getchar();

while(ch>='0'&&ch<='9')

n=(n<<3)+(n<<1)+ch-'0',ch=getchar();

return n;

}

int func1(int w,int m,int m1,int n)

{

int i;

for(i=1;i<=n;i++)

{

if(women[w][i]==m)

return 1;

else

if(women[w][i]==m1)

return 0;

}

return 0;

}

void stablemarriage(int n)

{

int i,c;

for(i=0;i<=n;i++)

{

mmark[i]=0;

wc[i]=-1;

}

c=n;

while(c>0)

{

int m;

for(m=1;m<=n;m++)

for(i=1;i<=n&&mmark[m]==0;i++)

{

int w=men[m][i];

if(wc[w]==-1)

{

wc[w]=m;

mmark[m]=1;

c--;

}

else

{

int m1=wc[w];

if(func1(w,m,m1,n))

{

wc[w]=m;

mmark[m]=1;

mmark[m1]=0;

}

}

}

}

}

int main()

{

int n,t,i,j;

t=inp();

while(t--)

{

n=inp();

for(i=1;i<=n;i++)

for(j=0;j<=n;j++)

women[i][j]=inp();

for(i=1;i<=n;i++)

for(j=0;j<=n;j++)