Tutorial
Tutorial is loading...
Solution (Vovuh)
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int n;
string s;
cin >> n >> s;
for (int i = 1; i < int(s.size()); ++i) {
if (s[i] < s[i - 1]) {
cout << "YES" << endl;
cout << i << " " << i + 1 << endl;
return 0;
}
}
cout << "NO" << endl;
return 0;
}
1155B - Game with Telephone Numbers
Tutorial
Tutorial is loading...
Solution (Roms)
#include<bits/stdc++.h>
using namespace std;
int n;
string s;
int main(){
cin >> n >> s;
int cnt1 = (n - 11) / 2;
int cnt2 = cnt1;
string res = "";
for(int i = 0; i < n; ++i){
if(s[i] == '8'){
if(cnt1 > 0) --cnt1;
else res += s[i];
}
else{
if(cnt2 > 0) --cnt2;
else res += s[i];
}
}
if(res[0] == '8') cout << "YES\n";
else cout << "NO\n";
return 0;
}
1155C - Alarm Clocks Everywhere
Tutorial
Tutorial is loading...
Solution (Vovuh)
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int n, m;
cin >> n >> m;
vector<long long> x(n), p(m);
for (int i = 0; i < n; ++i) {
cin >> x[i];
}
for (int i = 0; i < m; ++i) {
cin >> p[i];
}
long long g = x[1] - x[0];
for (int i = 2; i < n; ++i) {
g = __gcd(g, x[i] - x[i - 1]);
}
for (int i = 0; i < m; ++i) {
if (g % p[i] == 0) {
cout << "YES" << endl;
cout << x[0] << " " << i + 1 << endl;
return 0;
}
}
cout << "NO" << endl;
return 0;
}
Tutorial
Tutorial is loading...
Solution (PikMike)
#include <bits/stdc++.h>
using namespace std;
#define forn(i, n) for(int i = 0; i < int(n); i++)
typedef long long li;
const int N = 300 * 1000 + 13;
const li INF64 = 1e18;
int n, x;
int a[N];
li dp[N][3][3];
int main() {
scanf("%d%d", &n, &x);
forn(i, n) scanf("%d", &a[i]);
forn(i, n + 1) forn(j, 3) forn(k, 3)
dp[i][j][k] = -INF64;
dp[0][0][0] = 0;
forn(i, n + 1) forn(j, 3) forn(k, 3){
if (k < 2)
dp[i][j][k + 1] = max(dp[i][j][k + 1], dp[i][j][k]);
if (j < 2)
dp[i][j + 1][k] = max(dp[i][j + 1][k], dp[i][j][k]);
if (i < n)
dp[i + 1][j][k] = max(dp[i + 1][j][k], dp[i][j][k] + (j == 1 ? a[i] : 0) * li(k == 1 ? x : 1));
}
printf("%lld\n", dp[n][2][2]);
}
Tutorial
Tutorial is loading...
Solution (adedalic)
#include<bits/stdc++.h>
using namespace std;
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())
#define x first
#define y second
typedef long long li;
typedef long double ld;
typedef pair<int, int> pt;
const int MOD = 1000 * 1000 + 3;
int norm(int a) {
while(a >= MOD) a -= MOD;
while(a < 0) a += MOD;
return a;
}
int mul(int a, int b) {
return int(a * 1ll * b % MOD);
}
int binPow(int a, int k) {
int ans = 1;
while(k > 0) {
if(k & 1)
ans = mul(ans, a);
a = mul(a, a);
k >>= 1;
}
return ans;
}
int inv(int a) {
return binPow(a, MOD - 2);
}
int k = 10;
vector<int> f;
int main() {
f.resize(k + 1);
fore(i, 0, sz(f)) {
cout << "? " << i << endl;
cout.flush();
cin >> f[i];
}
vector< vector<int> > mat(sz(f), vector<int>(sz(f) + 1));
fore(i, 0, sz(mat)) {
mat[i][0] = 1;
mat[i][sz(f)] = f[i];
fore(j, 1, sz(mat[i]) - 1)
mat[i][j] = mul(mat[i][j - 1], i);
}
/*
fore(i, 0, sz(mat)) {
fore(j, 0, sz(mat[i]))
cerr << mat[i][j] << " ";
cerr << endl;
}
*/
fore(j, 0, sz(mat)) {
int nid = -1;
fore(i, j, sz(mat)) {
if(mat[i][j] != 0) {
nid = i;
break;
}
}
if(nid == -1)
continue;
swap(mat[j], mat[nid]);
fore(i, 0, sz(mat)) {
if(i == j) continue;
int cf = mul(mat[i][j], inv(mat[j][j]));
fore(cj, j, sz(mat[i]))
mat[i][cj] = norm(mat[i][cj] - mul(cf, mat[j][cj]));
}
}
vector<int> a(sz(f), 0);
fore(i, 0, sz(a)) {
if(mat[i][i] == 0)
continue;
a[i] = mul(mat[i][sz(a)], inv(mat[i][i]));
}
fore(x0, 0, MOD) {
int val = 0;
for(int i = sz(a) - 1; i >= 0; i--)
val = norm(mul(val, x0) + a[i]);
if(val == 0) {
cout << "! " << x0 << endl;
return 0;
}
}
cout << "! -1" << endl;
return 0;
}
Tutorial
Tutorial is loading...
Solution (BledDest)
#include<bits/stdc++.h>
using namespace std;
const int N = 14;
const int INF = int(1e9);
int dp[1 << N];
int par[1 << N];
int last[1 << N];
pair<int, int> last_pair[1 << N];
int dp2[N][N][1 << N];
int lastv[N][N][1 << N];
vector<int> bits[1 << N];
int n;
int m;
vector<int> g[N];
int main()
{
cin >> n >> m;
for(int i = 0; i < m; i++)
{
int x, y;
cin >> x >> y;
--x;
--y;
g[x].push_back(y);
g[y].push_back(x);
}
for(int i = 0; i < (1 << n); i++)
dp[i] = INF;
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
for(int z = 0; z < (1 << n); z++)
dp2[i][j][z] = INF;
for(int i = 0; i < n; i++)
for(auto x : g[i])
{
dp2[i][x][0] = 1;
lastv[i][x][0] = i;
}
for(int mask = 0; mask < (1 << n); mask++)
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
{
if((mask & (1 << i)) || (mask & (1 << j)) || (i == j) || (dp2[i][j][mask] == INF))
continue;
for(auto z : g[j])
{
if(mask & (1 << z)) continue;
if(z == lastv[i][j][mask]) continue;
int nmask = mask ^ (1 << j);
if(dp2[i][z][nmask] == INF)
{
dp2[i][z][nmask] = 1;
lastv[i][z][nmask] = j;
}
}
}
for(int mask = 0; mask < (1 << n); mask++)
for(int j = 0; j < n; j++)
if(mask & (1 << j))
bits[mask].push_back(j);
dp[1] = 0;
for(int mask = 0; mask < (1 << n); mask++)
for(int addmask = mask; addmask; addmask = (addmask - 1) & mask)
{
int lastmask = mask ^ addmask;
int cnt = __builtin_popcount(addmask) + 1;
if(dp[lastmask] + cnt >= dp[mask])
continue;
bool f = false;
for(auto x : bits[lastmask])
{
for(auto y : bits[lastmask])
{
if(dp2[x][y][addmask] == 1)
{
dp[mask] = dp[lastmask] + cnt;
last_pair[mask] = make_pair(x, y);
last[mask] = addmask;
}
if(f) break;
}
if(f) break;
}
}
if(dp[(1 << n) - 1] == INF)
cout << -1 << endl;
else
{
cout << dp[(1 << n) - 1] << endl;
int cur = (1 << n) - 1;
while(cur != 1)
{
int lst = last[cur];
int x = last_pair[cur].first;
int y = last_pair[cur].second;
cur ^= lst;
while(lst)
{
int ny = lastv[x][y][lst];
cout << y + 1 << " " << ny + 1 << endl;
lst ^= (1 << ny);
y = ny;
}
cout << x + 1 << " " << y + 1 << endl;
}
}
}