Skip to content

Instantly share code, notes, and snippets.

@euyuil
Last active January 28, 2020 01:42
Show Gist options
  • Save euyuil/9072831 to your computer and use it in GitHub Desktop.
Save euyuil/9072831 to your computer and use it in GitHub Desktop.
Codeforces Round #230 (Div. 2): solved A, B and D during the contest and C afterwards (http://codeforces.com/contest/393).
// Problem A - Nineteen
// http://codeforces.com/contest/393/problem/A
#include <string>
#include <cstdlib>
#include <iostream>
#include <algorithm>
int cnt[256];
using namespace std;
int main()
{
string word;
cin >> word;
for (int i = 0; i < word.size(); ++i)
++cnt[word[i]];
int ans = cnt['i'];
ans = min(ans, cnt['t']);
ans = min(ans, (cnt['n'] - 1) / 2);
ans = min(ans, cnt['e'] / 3);
cout << ans << endl;
return EXIT_SUCCESS;
}
// Problem B - Three matrices
// http://codeforces.com/contest/393/problem/B
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 222;
int n;
double mat[N][N];
int main()
{
cin >> n;
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
cin >> mat[i][j];
// Print matrix A
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < n; ++j)
{
if (i == j)
cout << mat[i][j];
else
cout << (mat[i][j] + mat[j][i]) / 2.0;
if (j < n - 1)
cout << ' ';
else
cout << endl;
}
}
// Print matrix B
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < n; ++j)
{
if (i == j)
cout << '0';
else
cout << (mat[i][j] - mat[j][i]) / 2.0;
if (j < n - 1)
cout << ' ';
else
cout << endl;
}
}
return EXIT_SUCCESS;
}
// Problem C - Blocked Points
// http://codeforces.com/contest/393/problem/C
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
long long n, n2, ix, iy, t, d, ans = 0;
cin >> n;
if (n >= 1)
{
n2 = n * n;
iy = n;
for (long long i = 0; i <= n; ++i)
{
t = n2 - i * i;
for (ix = iy; ix >= 0; --ix)
if (ix * ix <= t)
break;
// clog << i << ':' << ix << endl;
d = iy - ix;
if (d <= 1)
ans += 1;
else
ans += d;
iy = ix;
}
ans -= 1;
ans *= 4;
cout << ans << endl;
}
else
{
cout << 1 << endl;
}
return EXIT_SUCCESS;
}
// Problem D - Tower of Hanoi
// http://codeforces.com/contest/393/problem/D
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 44;
int mat[3][3];
long long dp[N][3][3];
inline void relax(int k)
{
for (int b = 0; b < 3; ++b)
{
for (int a = 0; a < 3; ++a)
{
if (a == b)
continue;
for (int c = 0; c < 3; ++c)
{
if (a == c || b == c)
continue;
dp[k][a][c] = min(dp[k][a][c], dp[k][a][b] + dp[k][b][c]);
}
}
}
}
long long calc(int n)
{
if (n == 0)
return 0;
// This statement was not deleted during the contest so it got WA.
// But after removing this, the solution got passed.
// if (n == 1)
// return mat[0][2];
for (int i = 0; i < 3; ++i)
for (int j = 0; j < 3; ++j)
dp[1][i][j] = mat[i][j];
relax(1);
for (int k = 2; k <= n; ++k)
{
for (int i = 0; i < 3; ++i)
{
for (int j = 0; j < 3; ++j)
{
if (i == j)
continue;
// From a through b to c
int a = i, c = j, b = 3 - i - j;
long long ans1 = dp[k-1][a][b] + mat[a][c] + dp[k-1][b][c];
long long ans2 = dp[k-1][a][c] + mat[a][b]
+ dp[k-1][c][a] + mat[b][c] + dp[k-1][a][c];
dp[k][a][c] = min(ans1, ans2);
}
}
relax(k);
}
// for (int k = 0; k <= n; ++k)
// {
// for (int i = 0; i < 3; ++i)
// for (int j = 0; j < 3; ++j)
// clog << dp[k][i][j] << ' ';
// clog << endl;
// }
return dp[n][0][2];
}
int main()
{
int n;
for (int i = 0; i < 3; ++i)
for (int j = 0; j < 3; ++j)
cin >> mat[i][j];
cin >> n;
cout << calc(n) << endl;
return EXIT_SUCCESS;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment