/*
user: php
link: http://acm.timus.ru/problem.aspx?space=1&num=1009
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<map>
#include<sstream>
#include<utility>
#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 dd double
#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
#define mp make_pair
#define paii pair<int, int>
#define padd pair<dd, dd>
#define pall pair<ll, ll>
#define fr first
#define sc second
using namespace std;
#define MAXX 17
#define type int
int N, k;
type dp[MAXX];
type sp_dp[MAXX];
type sp_rec(int n);
type rec(int n)
{
type &ret = dp[n];
if(ret != -1) return ret;
return ret = rec(n-1)*k + sp_rec(n-1);
}
type sp_rec(int n)
{
type &ret = sp_dp[n];
if(ret != -1) return ret;
ret = rec(n-1) * k;
return ret;
}
int main()
{
cin>>N>>k;
k--;
mem(dp, -1);
mem(sp_dp, -1);
dp[1] = sp_dp[1] = k;
cout<<rec(N);
return 0;
}
Category Archives: Timus
(timus) 1078. Segments
0
/*
link: http://acm.timus.ru/problem.aspx?space=1&num=1078
*/
#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
#define MAXX 22
#define MAXX 10002
using namespace std;
struct DATA{
int id, left, right;
};
bool comp(DATA a, DATA b)
{
if(a.left < b.left)
{
return true;
}
else if(a.left == b.left)
{
return a.right < b.right;
}
else
{
return false;
}
}
int cnt;
DATA ara[MAXX];
int LisLen = 0;
int L[MAXX];
void NlogK()
{
int temp = cnt+1;
int I[temp];
I[0] = INF;
FOR(i, 1, temp)
{
I[i] = -INF;
}
int left, u, right, mid;
loop(i, cnt)
{
u = ara[i].right;
left = 0;
right = LisLen;
while( left <= right )
{
mid = (left + right)/2;
if(I[mid] > u)
{
left = mid+1;
}
else
{
right = mid - 1;
}
}
I[left] = u;
L[i] = left;
LisLen = max(LisLen, left);
}
}
int main()
{
getint(cnt);
loop(i, cnt)
{
ara[i].id = i;
getint(ara[i].left); getint(ara[i].right);
}
sort(ara, ara+cnt, comp);
NlogK();
cout<<LisLen<<endl;
int last_taken = -INF;
for(int i=cnt-1; i>-1; i--)
{
if(L[i] == LisLen && ara[i].right > last_taken)
{
pf("%d", ara[i].id + 1);
LisLen--;
if(LisLen) pf(" ");
}
}
pf("\n");
}
(timus) 1073. Square Country
0
/*
link: http://acm.timus.ru/problem.aspx?space=1&num=1073
*/
#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 1000000
#define mod abs
#define pf printf
#define sf scanf
#define MAXX 60002
using namespace std;
int dp[MAXX];
int rec(int remain)
{
int &ret = dp[remain];
if(ret != -1) return ret;
int root = sqrt(remain);
ret = INF;
for(int i=1; i<=root; i++)
{
ret = min(ret, rec(remain - i*i));
}
return ++ret;
}
using namespace std;
int main()
{
int target;
getint(target);
mem(dp, -1);
dp[0] = 0;
cout<<rec(target)<<endl;
}
(Timus) 1319. Hotel
0
/*
user: php
time: 0.015 sec
link: http://acm.timus.ru/problem.aspx?space=1&num=1319
*/
#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(a) (a>0?a:-a)
#define pf printf
#define sf scanf
using namespace std;
int grid[101][101];
int main()
{
int n;
cin>>n;
int till;
int i;
till = (n *(n+1))/2 + 1;
int r = 0, c = 0;
for(i=1; i<till; i++ )
{
grid[r][c] = i;
if(c == 0)
{
c = r + 1;
r = 0;
}
else
{
c--;
r++;
}
}
till--;
r = 0;
c = 0;
for(i = n*n; i>till; i--)
{
grid[n - r - 1][n - c - 1] = i;
if(c == 0)
{
c = r + 1;
r = 0;
}
else
{
c--;
r++;
}
}
loop(i, n)
{
pf("%d", grid[i][n-1]);
for(int j=n-2; j>-1; j--)
{
pf(" %d", grid[i][j]);
}
pf("\n");
}
return 0;
}
(Timus) 1044. Lucky Tickets. Easy!
0
/*
user: php
time: 0.015 sec
link: http://acm.timus.ru/problem.aspx?space=1&num=1044
*/
#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(a) (a>0?a:-a)
#define pf printf
#define sf scanf
using namespace std;
int cnt[37];
ll res[4];
int main()
{
res[0] = 10;
res[1] = 670;
res[2] = 0;
loop(i, 10)
{
loop(j, 10)
{
loop(k, 10)
{
cnt[i+j+k]++;
}
}
}
loop(i, 28)
{
res[2] += cnt[i]*cnt[i];
}
res[3] = 0;
loop(i, 37) cnt[i] = 0;
loop(i, 10)
loop(j, 10)
loop(k, 10)
loop(q, 10)
cnt[i+j+k+q]++;
loop(i, 37)
{
res[3] += cnt[i]*cnt[i];
}
int n;
cin>>n;
n = n/2 - 1;
cout<<res[n]<<endl;
return 0;
}
(Timus) 1029. Ministry
0
/*
user: php
time: 0.093 sec
link: http://acm.timus.ru/problem.aspx?space=1&num=1029
*/
#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 10000000000
#define mod(a) (a>0?a:-a)
#define pf printf
#define sf scanf
using namespace std;
struct DATA{
int r, c;
void set(int i, int j)
{
r = i;
c = j;
}
};
ll dp[101][501][2][2];
ll cost[101][501];
DATA path[101][501];
int rows, columns;
ll rec(int r, int c, bool leftused, bool rightused)
{
ll &ret = dp[r][c][leftused][rightused];
if(ret != -1) return ret;
if(r == rows-1) return ret = cost[r][c];
ret = rec(r+1, c, 0, 0);
if(leftused == 0 && rightused == 0)
path[r][c].set(r+1, c);
if(rightused == 0 && c+1 < columns )
{
if(rec(r, c+1, 1, 0) < ret)
{
ret = dp[r][c+1][1][0];
if(leftused == 0)
path[r][c].set(r, c+1);
}
}
if(leftused == 0 && 0 < c )
{
if(rec(r, c-1, 0, 1 ) < ret )
{
ret = dp[r][c-1][0][1];
if(rightused == 0)
path[r][c].set(r, c-1);
}
}
ret += cost[r][c];
return ret;
}
int main()
{
ll mincost;
mem(dp, -1);
mem(path, -1);
cin>>rows>>columns;
loop(i, rows)
{
loop(j, columns)
{
cin>>cost[i][j];
}
}
mincost = INF;
DATA start;
start.r = 0;
loop(i, columns)
{
if(rec(0, i, 0, 0) < mincost)
{
start.c = i;
mincost = dp[0][i][0][0];
}
}
while(start.r != rows-1)
{
cout<<start.c+1<<" ";
start.set(path[start.r][start.c].r, path[start.r][start.c].c);
}
cout<<start.c + 1<<endl;
return 0;
}
(Timus) 1017. Staircases
1
/*
user: php
time: --
link: http://acm.timus.ru/problem.aspx?space=1&num=1017
*/
#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(a) (a>0?a:-a)
#define pf printf
#define sf scanf
using namespace std;
ll dp[501];
int main()
{
dp[0] = 1;
int maxpos = 0;
int sum;
for(int i=1; i<501; i++)
{
for(int j=maxpos; j>-1; j--)
{
sum = j + i;
if(sum < 501)
{
dp[sum] += dp[j];
maxpos = max(maxpos, sum);
}
}
}
int n;
cin>>n;
cout<<dp[n] - 1<<endl;
return 0;
}
UnLucky Codes 