Like this:

So this week is practice week, because in 4-5 days GCJ Round 2 will take place. The level of problems will be higher and it will be a tough round because out of 2400 competitors only 1000 will remain in game (which is 41%).

So I start this practice week with simulating Round 1 Sub Round 3 of GCJ. After doing the set I realized it was a nice set and slightly easier then SubRound 2 and SubRound 1. I was able to do all 3 problems perfectly in 1:27 hours(if I were in contest this would’ve place me 15th). I liked  all 3 problems. But I think  B was the most crazy one, even thou I coded A + B in half an  hour, and C took me longer.

Let’s talk about B before I finish this post.So after reading it quickly it clicked in my mind that this is DP. If you read the problem you will know what I will be talking about. Quickly I calculated how many DP states are there so I got 2 * 3 * 5 * 7 * length. And for large input length was <= 40. So it was just perfect. Ok here is the recurrence I used. DP[length][two][three][five][seven] = how many are there if I used first length digits, and I have modulo 2 = two, modulo 3 = three, modulo 5 = five, modulo 7 = seven. Ok I will end this post leaving my source code here to see it (P.S: Wednesday is my 19th Birthday )

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;
typedef unsigned long long LL;

void go();

LL DP[44][2][3][5][7];

int main()
{
freopen("file.in", "r", stdin);
freopen("file.out", "w", stdout);
int T;
scanf("%d", &T);
while (T--) go();
//fclose(stdin);
//getchar();
return 0;
}

int Case = 0;
int f(string s, int M) {
int ret = 0;
int i;
for (i = 0; i < s.size(); ++i) ret = (ret * 10 + s[i] - '0') % M;

return ret;
}
void go() {
//clean
int v[4];
int i;
for (i = 0; i < 44; ++i) for (v[0] = 0; v[0] < 2; ++v[0])
for (v[1] = 0; v[1] < 3; ++v[1])
for (v[2] = 0; v[2] < 5; ++v[2])
for (v[3] = 0; v[3] < 7; ++v[3]) DP[i][v[0]][v[1]][v[2]][v[3]] = 0;
DP[0][0][0][0][0] = 1;
string s;
cin >> s;
int n = s.size();

int j, k;
for (i = 1; i <= n; ++i)
for (j = 1; j <= i; ++j) {
//afla module
int m[4];
m[0] = f(s.substr(j-1, i - j + 1), 2);
m[1] = f(s.substr(j-1, i - j + 1), 3);
m[2] = f(s.substr(j-1, i - j + 1), 5);
m[3] = f(s.substr(j-1, i - j + 1), 7);
//+ sau -
for (v[0] = 0; v[0] < 2; ++v[0])
for (v[1] = 0; v[1] < 3; ++v[1])
for (v[2] = 0; v[2] < 5; ++v[2])
for (v[3] = 0; v[3] < 7; ++v[3])       {
//add with m
int sum[4];
for (k = 0; k < 4; ++k) sum[k] = (v[k] + m[k]);
sum[0]%=2; sum[1]%=3; sum[2]%=5; sum[3]%=7;
DP[i][sum[0]][sum[1]][sum[2]][sum[3]] += DP[j-1][v[0]][v[1]][v[2]][v[3]];

for (k = 0; k < 4; ++k) sum[k] = (v[k] - m[k]);
sum[0]+=2000; sum[1]+=3000; sum[2]+=5000; sum[3]+=7000;
sum[0]%=2; sum[1]%=3; sum[2]%=5; sum[3]%=7;
DP[i][sum[0]][sum[1]][sum[2]][sum[3]] += DP[j-1][v[0]][v[1]][v[2]][v[3]];
}
}
LL total = 0;
for (v[0] = 0; v[0] < 2; ++v[0])
for (v[1] = 0; v[1] < 3; ++v[1])
for (v[2] = 0; v[2] < 5; ++v[2])
for (v[3] = 0; v[3] < 7; ++v[3]) if (v[0] * v[1] * v[2] * v[3] == 0) total+=DP[n][v[0]][v[1]][v[2]][v[3]];
printf("Case #%d: ", ++Case);
cout << total / LL(2) << '\n';

}

Advertisement