Finally, ACM-ICPC Asia-Kanpur Site First Round Online Contest has come to an end…..Must say, it was real fun!!!!!

Lets have a look at the contest problems and their optimal solutions. Some of the solutions are from those teams which managed a good rank at the end of the contest. Congratulations to them!!!! 😀

My team **Gibberish** managed an AIR of 26 and 1^{st} in BIT Mersa. But unless and until the results are declared I won’t be at peace. 😛

**Problem 1: Arithmancy**

Hermione Granger, the most talented witch of her generation, likes to solve various types of mathematical problems in the Arithmancy class. Today, the professor has given her the following task:

Find the number of fractions a/b such that-

1. **gcd(a, b) = 1**

2. **0 < a/b < 1**

3. **a * b = (n!) ^ (n!)**

Where **“n!”** denotes the factorial of n and “^” denotes power, **i.e. (2!) ^ (2!) = 4**.

She is quite confident that she can solve it for **n <= 10,000,000 (i.e. 10^7)**, but then she remembers that she has to study some case history so that she can help Hagrid to win the case of Buckbeak. So, she wants your help to solve the problem.

*Input*

There will be one line for each test case containing the number **n (1 <= n <= 10,000,000)**. Input will be terminated by EOF. There will be around **20,000** test cases.

*Output*

For each case, print the number of fractions in a separate line. This number may be very large, so print the answer modulo **10,007**.

*Example*

*Input:*

1

2

*Output:*

0

1

Time limit: 5s

Source limit: 50000

Solution by **Team Gibberish**

using namespace std;
#include <iostream>
#include <cstdio>
#include <vector>
# define MAX 10000001
# define MOD 10007
vector<bool> prime(MAX,true);
int sum[MAX];
void sieve()
{
int i,j,p;
prime[1]=false;
for(i=3;(i*i)<MAX;i+=2)
{
if(!prime[i]) continue;
for(j=i*i;j<MAX;j+=(i<<1))
prime[j]=false;
}
sum[0]=sum[1]=0;sum[2]=1;
p=1;
for(i=3;i<MAX;i++)
{
if(!(i&1))
{
sum[i]=p;
continue;
}
if(prime[i])
{
p++;
sum[i]=p;
}
else sum[i]=p;
}
}
int sq(int x)
{
return (x*x)%MOD;
}
int pow(int x)
{
if(!x) return 1;
if(x&1) return (2*pow(x-1))%MOD;
return sq(pow(x/2));
}
int main()
{
sieve();
int num,cnt,i;
while(scanf("%d",&num)!=EOF)
{
cnt=sum[num];
if(cnt!=0) cnt=pow(cnt-1);
printf("%d\n",cnt);
}
return 0;
}

**Problem 2: Calender**

We know that there are so many calendar systems. For example, Bangla, Christ, Arabic, Chinese etc. This problem is about Decimal calendar. There are 3 months in this calendar. First month is “Hundreds”. There are 300 days in this month. Second month is “Tens”. There are 60 days in this month. And this followed by the last month “Ones” having 5 or 6 days depending on whether this is leap year or not. A Decimal year spans a full Christ calendar. That is 1st Hundreds in Decimal Calendar is 1st January in Christi Calendar. Similarly, 31st December of Christ Calendar is 5th or 6th day of Decimal calendar (depending on whether it is leap year or not).

A year in Decimal calendar is leap year if the corresponding Christ year is leap year. For example, the Decimal year corresponding to 2000 Christ year is leap year but 2001 is not, and again 1900 is not leap year too. A year in Christ calendar is leap year if the year is divisible by 400 or divisible by 4 but not by 100.

You are given a day in Christ calendar in DD-MMM-YYYY format (DD stands for day, MMM stands for first three letters (in CAPS) of the month and YYYY stands for the year). You are to give the date in Decimal Calendar format.

*Input*

First line contains number of test case. Every test case consists of a date in Christ Calendar format in each line.

*Output*

You are to output the case number and the date in Decimal Calendar format. Output the date and the month in the Decimal Calendar.

*Example*

*Input:*

3

01-JAN-1900

10-JAN-1900

16-DEC-1900

*Output:*

Case 1: 1 Hundreds

Case 2: 10 Hundreds

Case 3: 50 Tens

*Note*

First three letters for the months are:

JAN, FEB, MAR, APR, MAY, JUN, JUL, AUG, SEP, OCT, NOV, DEC.

Time limit: 5s

Source limit: 50000

Solution By **Team Gibberish**

#include<iostream>
#include<cstdio>
#include<string>
using namespace std;
int main()
{
int n,k=1,day,year,mon,l,date;
string s,month;
cin>>n;
int cal[][12]={ {0,31,59,90,120,151,181,212,243,273,304,334},
{0,31,60,91,121,152,182,213,244,274,305,335} };
while(n--)
{
cin>>s;
month="";
day=(s[0]-'0')*10 + (s[1]-'0');
month= month + s[3]+s[4]+s[5];
year=(s[7]-'0')*1000 + (s[8]-'0')*100 + (s[9]-'0')*10 + (s[10]-'0');
if(month=="JAN") mon=1;
else if(month=="FEB" ) mon=2;
else if(month=="MAR" ) mon=3;
else if(month=="APR") mon=4;
else if(month=="MAY" ) mon=5;
else if(month=="JUN" ) mon=6;
else if(month=="JUL" ) mon=7;
else if(month=="AUG" ) mon=8;
else if(month=="SEP" ) mon=9;
else if(month=="OCT" )mon=10;
else if(month=="NOV" ) mon=11;
else if(month=="DEC") mon=12;
l=0;
if(year%25==0)
{
if(year%16==0)
l=1;
else
l=0;
}
else if(year%4==0)
l=1;
else
l=0;
date = day+cal[l][mon-1];
if(date<=300)
cout<<"Case "<<k++<<": "<<date<<" "<<"Hundreds\n" ;
else
{
date-=300;
if(date<=60)
cout<<"Case "<<k++<<": "<<date<<" "<<"Tens\n";
else
{
date-=60;
cout<<"Case "<<k++<<": "<<date<<" "<<"Ones\n";
}
}
}
return 0;
}

**Problem 3: CricInfo**

I guess the most visited site of the past 3 months is www.cricinfo.com. First World Cup Cricket, then Australia tour to Bangladesh and now IPL T20. I believe there are lots of cricket fans among you. So I do not need to describe the game rule. But for the purpose of this problem here is short description of scoring. Any rule out of this problem description is not applicable for this problem.

For this problem we will use only the following outcomes in a ball:

Possible Outcome in a Ball |
Runs |
Is the Ball valid? |

. (dot) |
0 |
Yes |

1 |
1 |
Yes |

2 |
2 |
Yes |

3 |
3 |
Yes |

4 |
4 |
Yes |

6 |
6 |
Yes |

Wd |
1 |
No |

1Wd |
2 |
No |

2Wd |
3 |
No |

4Wd |
5 |
No |

Nb |
1 |
No |

1Nb |
2 |
No |

4Nb |
5 |
No |

6Nb |
7 |
No |

W |
0 |
Yes |

(**Wd** stands for **Wide**, **Nb** for **No Ball** and **W** for **Wicket**)

In cricinfo we always watch the score card. In cricket an over consists of **6 valid balls**. A score card of an over may look like below:

In this over there were **1** wicket and **9** runs. In the last over of second innings of a match, a team requires N runs to win. You are to output number of ways of the outcome of the over. Note that, as you are watching second innings of the match, so it may be possible that he can score **N** runs in first 4 balls and win the match. That means, it is not necessary to play an entire over to score **N** runs. Also suppose you do not know how many wickets are already gone. So it may also be possible that after a few wicket falls they are all out. Also note that, if a team scores greater or equal to **N** runs the team wins and does not play any ball.

*Input*

First line contains number of test case **T (T <= 10000)**. For each test a line contains **N (1 <= N <= 10000)**.

*Output*

For every test case, output the case number and number of ways of outcome of the **last** over where the team needs N runs to win. As the answer can be very big, so output in mod **10000007**.

*Example*

*Input:*

1

1

*Output:*

Case 1: 946

Time limit: 5s

Source limit: 50000

Solution by **Team XCoders**

# include<stdio.h>
int run[15]={0,1,2,3,4,6,1,2,3,5,1,2,5,7,0};
int ball[15]={1,1,1,1,1,1,0,0,0,0,0,0,0,0,1};
long count,n;
long a[10000][7]={0};
void fun(long rnew,int bnew)
{
long nb,nr,i,bn,rn,c;
c=0;
for(i=0;i<15;i++)
{
bn=bnew-ball[i];
rn=rnew-run[i];
if(bn>=0)
{
if(i==14) c++;
if(rn<=0) c++;
else
{
if(bn>0) c=c+a[rn][bn];
else c++;
}
}
}
a[rnew][bnew]=c%10000007;
}
int main()
{
int i,j,t,b,r;
scanf("%d",&t);
for(i=1;i<10001;i++)
{
for(j=1;j<7;j++)
fun(i,j);
}
for(i=0;i<t;i++)
{
scanf("%ld",&n);
printf("Case %d: %ld\n",i+1,a[n][6]);
}
return 0;
}

**Problem 4: Mr and Mrs Ant**

Mr. and Mrs. Ant are very hungry. So, they want to collect food as much as they can. They can search for foods simultaneously. To do so, they start from their house and collect all foods together and meet in some place (not necessarily their house). Finally, they eat together.

The world of Mr. and Mrs. Ant is a two dimensional grid. Each cell is either the **home**, or **free**, or **blocked**, or contains a **food**. Two cells are adjacent if they share an edge. In each **second**, they can move from one cell to another cell simultaneously. One can decide to not to move in some step, while other may move. One cell can be visited many times. Both of them can move into the same cell also.

In this problem, the grid is given by an R x C matrix represented by following characters:

Character Meaning Remarks

H |
Home of Mr. and Mrs. Ant |
Occurs exactly once |

F |
A food item |
Occurs at least once, at most 8 times |

. (dot) |
Free (passable) cell |
– |

# (hash) |
Blocked Cell |
– |

Given the grid information, give the minimum amount of time that must be needed for them to collect all the foods and then meet.

*Input*

The first line of input will contain **T (T <= 30)** denoting the number of cases. Each case starts with two integers **R** and **C (2 <= R, C <= 12)**. Then, **R** lines follow giving the grid.

*Output*

For each case, print the case number, the minimum amount of time (in **seconds**) that must be needed for them to collect all the foods and meet. If it is impossible to collect all the food items, output **-1** (negative one) instead.

*Example*

*Input:*

2

2 3

H#.

.#F

2 6

F#F..#

..H#.F

*Output:*

Case 1: -1

Case 2: 8

Time limit: 5s

Source limit: 50000

Solution by **Team Pandoras Box**

# include <cstdio>
# include <algorithm>
using namespace std;
char maze[12][13];
int dist[12][12][12][12];
int neigh[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
int arr[8];
int coord[9][2];
int main()
{
int T;
scanf("%d",&T);
for(int t=0;t<T;t++)
{
int R,C;
scanf("%d%d",&R,&C);
for(int i=0;i<R;i++)
scanf("%s",maze[i]);
int cnt=1;
for(int i=0;i<R;i++)
for(int j=0;j<C;j++)
{
for(int k=0;k<R;k++)
for(int l=0;l<C;l++)
dist[i][j][k][l]=1000000;
if(maze[i][j]!='#') dist[i][j][i][j]=0;
if(maze[i][j]=='H') {coord[0][0]=i;coord[0][1]=j;}
else if(maze[i][j]=='F') {coord[cnt][0]=i;coord[cnt++][1]=j;}
}
for(int chaathu=0;chaathu<144;chaathu++)
for(int i=0;i<R;i++)
for(int j=0;j<C;j++)
{
for(int q=0;q<4;q++)
{
int k=i+neigh[q][0],l=j+neigh[q][1];
if(k>=0&&k<R&&l>=0&&l<C&&maze[k][l]!='#')
for(int m=0;m<R;m++)
for(int n=0;n<C;n++)
if(dist[m][n][k][l]>dist[m][n][i][j])
dist[m][n][k][l]=dist[m][n][i][j]+1;
}
}
cnt--;
for(int i=0;i<cnt;i++)
arr[i]=i+1;
int mindist=1000000;
do
{
int start=0,disttot=0;
for(int i=0;i<cnt;start=arr[i++])
disttot+=dist[coord[start][0]][coord[start][1]][coord[arr[i]][0]][coord[arr[i]][1]];
disttot+=dist[coord[start][0]][coord[start][1]][coord[0][0]][coord[0][1]];
disttot>>=1;
if(mindist>disttot)mindist=disttot;
}while(next_permutation(arr,arr+cnt));
printf("Case %d: %d\n",t+1,mindist>10000?-1:mindist);
}
return 0;
}

### Like this:

Like Loading...