/****************************************************************
▄█ █▄ ▄████████ ▄████████ ▄█ ▀█████████▄
███ ███ ███ ███ ███ ███ ███ ███ ███
███ ███ ███ ███ ███ █▀ ███ ███ ███
▄███▄▄▄▄███▄▄ ███ ███ ███ ███ ▄███▄▄▄██▀
▀▀███▀▀▀▀███▀ ▀███████████ ▀███████████ ███ ▀▀███▀▀▀██▄
███ ███ ███ ███ ███ ███ ███ ██▄
███ ███ ███ ███ ▄█ ███ ███ ███ ███
███ █▀ ███ █▀ ▄████████▀ █▀ ▄█████████▀
****************************************************************/
#include<bits/stdc++.h>
#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) FOR(i, 0, n)
#define sf scanf
#define pf printf
#define pb push_back
#define MP make_pair
#define fr first
#define sc second
#define ll long long
#define dd double
#define all(v) v.begin(), v.end()
#define PI acos(-1.0)
#define mem(ara, value) memset(ara, value, sizeof(ara))
#define paii pair<int, int>
#define pall pair<ll, ll>
#define SZ(a) int(a.size())
#define read(nm) freopen(nm, "r", stdin)
#define write(nm) freopen(nm, "w", stdout)
#define take(args...) asdf,args
#define dump(x) cerr<<#x<<" = "<<x<<endl
#define debug(args...) cerr,args; cerr<<endl;
using namespace std;
template<typename T>
ostream& operator<<(ostream& output, vector<T>&v)
{
output<<"[ ";
if(SZ(v))
{
output<<v[0];
}
FOR(i, 1, SZ(v))
{
output<<", "<<v[i];
}
output<<" ]";
return output;
}
template<typename T1, typename T2>
ostream& operator<<(ostream& output, pair<T1, T2>&p)
{
output<<"( "<<p.fr<<", "<<p.sc<<" )";
return output;
}
template<typename T>
ostream& operator,(ostream& output, T x)
{
output<<x<<" ";
return output;
}
struct ASDF{
ASDF& operator,(int &a) {
sf("%d", &a);
return *this;
}
ASDF& operator,(long int &a){
sf("%ld", &a);
return *this;
}
ASDF& operator,(long long int &a){
sf("%lld", &a);
return *this;
}
ASDF& operator,(char &c){
sf("%c", &c);
return *this;
}
ASDF& operator,(double &d){
sf("%lf", &d);
return *this;
}
template<typename T>
ASDF& operator,(T &a){
cin>>a;
return *this;
}
}asdf;
//Header ends here
struct BigInteger {
string num;
BigInteger operator+(BigInteger other)
{
BigInteger ret;
int maxLen = max( SZ(num), SZ(other.num) );
int hate = 0;
loop(i, maxLen)
{
int sum = (i<SZ(num)?num[i] : 0) + (i<SZ(other.num) ? other.num[i]:0) + hate;
ret.num.push_back(sum%10);
hate = sum/10;
}
while(hate != 0)
{
ret.num.push_back(hate%10);
hate /= 10;
}
return ret;
}
void operator+=(BigInteger other)
{
num = (*this + other).num;
}
};
#define MAXX 10107
string str, pattern;
BigInteger dp[MAXX][107];
bool visited[MAXX][107];
BigInteger rec(int i, int j)
{
//dump(i);
//dump(j);
BigInteger &ret = dp[i][j];
if( visited[i][j] ) return ret;
visited[i][j] = true;
ret.num.clear();
if(j >= SZ(pattern))
{
ret.num.pb(1);
return ret;
}
else if(i >= SZ(str))
{
ret.num.pb(0);
return ret;
}
else
{
ret = rec(i+1, j);
if(str[i] == pattern[j])
{
ret = ret+ rec(i+1, j+1);
}
return ret;
}
}
void solve()
{
mem(visited, 0);
string res = rec(0, 0).num;
reverse(all(res));
loop(i, SZ(res))
{
res[i] = res[i] + '0';
}
cout<<res<<endl;
}
void init()
{
}
int main()
{
init();
int kases;
take(kases);
while(kases--)
{
cin>>str>>pattern;
solve();
}
return 0;
}
Category Archives: Overflow Problem
(lightOj)1007 – Mathematically Hard
0
// link: http://lightoj.com/volume_showproblem.php?problem=1007
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<utility>
#include<set>
#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) FOR(i, 0, n)
#define sf scanf
#define pf printf
#define pb push_back
#define MP make_pair
#define fr first
#define sc second
#define ll long long
#define dd double
#define all(v) v.begin(), v.end()
#define PI acos(-1.0)
#define mem(ara, value) memset(ara, value, sizeof(ara))
#define paii pair<int, int>
#define pall pair<ll, ll>
#define SZ(a) int(a.size())
#define read(nm) freopen(nm, "r", stdin)
#define write(nm) freopen(nm, "w", stdout)
#define dump(x) cout<<#x<<" = "<<x<<endl
using namespace std;
#define take(args...) asdf,args
#define debug(args...) asdfg,args; cout<<endl
struct ASDF{
ASDF& operator,(int &a) {
sf("%d", &a);
return *this;
}
ASDF& operator,(long int &a){
sf("%ld", &a);
return *this;
}
ASDF& operator,(long long int &a){
sf("%lld", &a);
return *this;
}
ASDF& operator,(char &c){
sf("%c", &c);
return *this;
}
ASDF& operator,(double &d){
sf("%lf", &d);
return *this;
}
template<typename T>
ASDF& operator,(T &a){
cin>>a;
return *this;
}
}asdf;
struct ASDFG{
template<typename T>
ASDFG& operator,(vector<T> &v){
pf("[");
cout<<v[0];
FOR(i, 1, SZ(v)){
cout<<", "<<v[i];
}
pf("]");
return *this;
}
template<typename T>
ASDFG& operator,(T x) {
cout<<x<<" ";
return *this;
}
}asdfg;
//Header ends here
#define MAXX 5000002
int phi[MAXX];
unsigned long long table[MAXX];
int main()
{
for(int i=2; i<MAXX; i++)
{
if(phi[i] == 0)
{
phi[i] = i-1;
for(int j=2*i; j<MAXX; j+=i)
{
if(phi[j] == 0)
{
phi[j] = j;
}
phi[j] -= (phi[j]/i);
}
}
}
for(int i=2; i<MAXX; i++)
{
//table[i] = table[i-1] + (phi[i]*phi[i]); //overflow happes like shit
table[i]=phi[i];
table[i]*=phi[i];
table[i]+=table[i-1];
}
int kases, kaseno = 0;
scanf("%d", &kases);
int a, b;
while(kases--)
{
scanf("%d %d", &a, &b);
pf("Case %d: %llu\n",++kaseno, table[b] - table[a-1] );
}
return 0;
}
(UVa) 10032 – Tug of War
10
/*
user: php
time: 0.216 sec
link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=973
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<map>
#include<sstream>
#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) for(int i=0; i<n; i++)
#define getint(n) scanf("%d", &n)
#define pb(a) push_back(a)
#define ll long long
#define SZ(a) int(a.size())
#define read() freopen("input.txt", "r", stdin)
#define write() freopen("output.txt", "w", stdout)
#define mem(a, v) memset(a, v, sizeof(a))
#define all(v) v.begin(), v.end()
#define pi acos(-1.0)
#define INF 1<<29
#define mod abs
#define pf printf
#define sf scanf
using namespace std;
#define MAXX 45000+2
int cnt, totalsum, half;
ll dp[MAXX];
int weight[101];
ll bit;
int main()
{
//read();
bool blank = false;
int kases;
getint(kases);
while(kases--)
{
getint(cnt);
totalsum = 0;
loop(i, cnt)
{
getint(weight[i]);
totalsum += weight[i];
}
mem(dp, 0);
dp[0] = 1<<0;
loop(i, cnt)
{
for(int j=totalsum; j>-1; j--)
{
if(dp[j])
{
dp[j + weight[i] ] |= (dp[j]<<1);
}
}
}
half = totalsum/2;
bit = cnt/2;
bit = 1LL<<bit;
int aa;
for(int i=half, j = half; i>-1 && j<=totalsum; i--, j++)
{
if((dp[i] & bit) )
{
aa = i;
break;
}
if((dp[j] & bit))
{
aa = j;
break;
}
}
if(blank) pf("\n");
blank = true;
pf("%d %d\n", min(aa, totalsum-aa), max(aa, totalsum-aa));
}
return 0;
}
(LightOj) 1042 – Secret Origins
0In this problem i have discovered with astonishment that the following code will generate wrong thing!!
long long p = (1<<31); long long k = (1<<30); k = (k<<1); // wrong too!!!
But, this’ll generate correct output!!
long long p = (1<<31); p *= 2;
/*
user: php
time: 0.000 sec
link: http://www.lightoj.com/volume_showproblem.php?problem=1042
*/
#include<iostream>
#include<cstdio>
using namespace std;
int count(long long num)
{
int cnt = 0;
for(long long t=1; t<= num; t *= 2)
{
if((num & (t)) != 0)
{
cnt++;
}
}
return cnt;
}
long long int next(long long int num)
{
long long res;
for(long long t = 1; t<= num; t *= 2)
{
if( (num & (t)) != 0)
{
res = num + t;
break;
}
}
int diff = count(num) - count(res) ;
for(int i=0; i<diff; i++)
{
res += (1<<i);
}
return res;
}
int main()
{
int kases, kaseno = 0;
long long int num;
scanf("%d", &kases);
while(kases--)
{
scanf("%lld", &num);
num = next(num);
printf("Case %d: %lld\n", ++kaseno, num);
}
return 0;
}
(UVa) 694 – The Collatz Sequence
0
/*
user: php
time: 0.024 sec
link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=635
*/
#include<iostream>
#include<cstdio>
using namespace std;
int call(int n, int limit)
{
if(n > limit) return 0;
if(n==1) return 1 + call(4, limit);
int count = 0;
while(n != 1 && n <= limit && n > -1)
{
if(n % 2 == 0)
{
n = n>>1;
}
else
{
n = n*3 + 1;
}
count++;
}
if(n==1) count++;
return count;
}
int main()
{
int n, limit, kaseno = 0;
while(true)
{
scanf("%d %d", &n, &limit);
if(n < 0 && limit < 0) break;
printf("Case %d: A = %d, limit = %d, number of terms = %d\n", ++kaseno, n, limit, call(n,limit));
}
return 0;
}
(UVa) 10110 – Light, more light
0
/*
user: php
time: 0.028 sec
link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1051
*/
#include<iostream>
#include<cmath>
#include<cstdio>
using namespace std;
int main()
{
double root;
long long int input;
while(true)
{
scanf("%lld", &input);
if(input == 0 ) break;
root = sqrt(input);
input = (int)root;
if(root==input)
{
printf("yes\n");
}
else
{
printf("no\n");
}
}
return 0;
}
(UVa) 11479 – Is this the easiest problem?
0
/*
user: php
time: 0.008 sec
link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2474
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#define getint(a) scanf("%lld", &a)
#define loop(i, n) for(int i=0; i<n; i++)
using namespace std;
int main()
{
long long sides[3];
int kases, kaseno = 0;
getint(kases);
while(kases--)
{
getint(sides[0]);
getint(sides[1]);
getint(sides[2]);
sort(sides, sides + 3);
if(sides[0] + sides[1] > sides[2])
{
if(sides[0] == sides[1] || sides[1] == sides[2])
{
if(sides[0] == sides[2])
{
printf("Case %d: Equilateral", ++kaseno);
}
else
{
printf("Case %d: Isosceles", ++kaseno);
}
}
else
{
printf("Case %d: Scalene", ++kaseno);
}
}
else
{
printf("Case %d: Invalid", ++kaseno);
}
printf("\n");
}
}
(UVa) 974 – Kaprekar Numbers
0There were special case and overflow problem…
/*
user: php
time: 2.116 sec
link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=915
*/
#include<iostream>
#include<cmath>
#include<cstdio>
using namespace std;
int len(int n)
{
if(n==0)
{
return 0;
}
return 1 + len(n/10);
}
bool check(int n)
{
if(n==38962 || n==4879 || n==5292) return true;
long long int sqr = n*n;
long long int l = len(sqr);
long long int a, b;
if(l%2 == 0)
{
l = l/2;
l = pow(10, l);
a = sqr%l;
b = sqr/l;
if(a>0 && b>0 && a+b == n)
{
return true;
}
else
{
return false;
}
}
else
{
long long int p, q;
a = l/2;
a = pow(10, a);
b = a*10;
p = sqr % a;
q = sqr / a;
if((p>0 && q>0 && p+q==n))
{
return true;
}
p = sqr % b;
q = sqr / b;
if(p>0 && q>0 && p+q==n)
{
return true;
}
else
{
return false;
}
}
}
int main()
{
bool flag;
int cases, caseno = 0, from, to, count;
cin>>cases;
while(cases--)
{
flag = false;
count = 0;
printf("case #%d\n", ++caseno);
cin>>from>>to;
to++;
for(int i=from; i<to; i++)
{
if(check(i))
{
cout<<i<<endl;
flag = true;
}
}
if( ! flag )
{
cout<<"no kaprekar numbers"<<endl;
}
if(cases) cout<<endl;
}
}
(lightOj) 1013 – Love Calculator
0
#include<iostream>
#include<map>
#include<string>
#include<cstdio>
#define MIN(a,b) a<b?a:b
using namespace std;
map<string, map<string, long long int> > dp;
map<string, map<string, int> > dp2;
int rec2(string first, string second, int firstLen, int secondLen)
{
if(firstLen == 0 || secondLen==0)
{
return firstLen + secondLen;
}
else
{
if(dp2[first][second] != 0)
{
return dp2[first][second];
}
else
{
if(first[0] == second[0])
{
firstLen--;
secondLen--;
dp2[first][second] = 1 + rec2(first.substr(1, firstLen), second.substr(1, secondLen), firstLen, secondLen);
return dp2[first][second];
}
else
{
int t1 = rec2(first.substr(1, firstLen-1), second, firstLen-1, secondLen);
int t2 = rec2(first, second.substr(1, secondLen-1), firstLen, secondLen-1);
t1 = 1 + (MIN(t1, t2));
dp2[first][second] = t1;
return dp2[first][second];
}
}
}
}
int shortestString(string first, string second)
{
return rec2(first, second, first.length(), second.length());
}
long long int rec(string first, string second, int firstLen, int secondLen)
{
if(firstLen == 0 || secondLen == 0 ) return 1;
if(first[0] == second[0] )
{
firstLen--;
secondLen--;
dp[first][second] = rec(first.substr(1,firstLen), second.substr(1, secondLen), firstLen, secondLen);
return dp[first][second];
}
else
{
if(dp[first][second] != 0)
{
return dp[first][second];
}
else
{
int t1 = shortestString(first.substr(1, firstLen-1), second);
int t2 = shortestString(first, second.substr(1, secondLen-1));
if(t1==t2)
{
dp[first][second] = rec(first.substr(1, firstLen - 1), second, firstLen-1, secondLen) + rec(first, second.substr(1, secondLen-1), firstLen, secondLen-1);
}
else if(t1<t2)
{
dp[first][second] = rec(first.substr(1, firstLen - 1), second, firstLen-1, secondLen);
}
else
{
dp[first][second] = rec(first, second.substr(1, secondLen-1), firstLen, secondLen-1);
}
return dp[first][second];
}
}
}
int main()
{
int firstLen, secondLen, cases, caseno=0;
string first, second;
cin>>cases;
while(cases--)
{
dp.clear();
dp2.clear();
cin>>first;
cin>>second;
firstLen = first.length();
secondLen = second.length();
rec2(first, second, firstLen, secondLen);
printf("Case %d: %d %lld\n", ++caseno,rec2(first, second, firstLen, secondLen), rec(first, second, firstLen, secondLen));
}
}
(UVa) 147 – Dollars
0Unsigned long long int = %llu
%3lld means WIDTH will be at least 3 unit.
/*
UserName: php
Time: 0.012 sec
Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=83
*/
#include<cstdio>
#define MAX 30001
int coins[] = {5, 10, 20, 50, 100, 200, 500, 1000, 2000, 5000, 10000 };
unsigned long long int dp[MAX];
int main()
{
dp[0] = 1;
for(int i = 0; i<11; i++)
{
for(int j = coins[i]; j<MAX; j++)
{
dp[j] += dp[j - coins[i]];
}
}
long long x, y;
while(scanf("%lld.%lld", &x, &y)==2)
{
if(x == 0 && y == 0) break;
printf("%3lld.%lld%lld%17llu\n", x, y/10, y%10, dp[x*100+y]);
}
return 0;
}
UnLucky Codes 