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 1st 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...
