Задача А.
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m;
map<int, int> mp;
mp[1] = 2;
scanf("%d %d", &n, &m);
for (int i = 0; i < n; ++i) {
int x;
scanf("%d", &x);
++mp[x];
}
int bst = 0, id;
for (auto& cur : mp) {
if (cur.second > bst) {
bst = cur.second;
id = cur.first;
}
}
printf("%d\n", id);
return 0;
}
Задача В.
#include <bits/stdc++.h>
using namespace std;
int n, m, t;
vector<int> a;
int main() {
scanf("%d %d %d", &n, &m, &t);
a.resize(m);
for (int i = 0; i < m; ++i) {
int x, y;
scanf("%d %d", &x, &y);
x = (x - 1 + y * t) % n;
x = (x + n) % n;
a[i] = x;
}
sort(a.begin(), a.end());
for (auto& pos : a) {
printf("%d ", pos + 1);
}
printf("\n");
return 0;
}
Задача С.
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <cmath>
#include <map>
#include <fstream>
#include <stack>
#include <set>
#include <iomanip>
#include <queue>
#include <map>
#include <functional>
#include <list>
#include <sstream>
#include <ctime>
#include <climits>
#include <bitset>
#include <list>
#include <cassert>
#include <complex>
using namespace std;
/* Constants begin */
const long long inf = 2e18 + 7;
const long long mod = 1e9 + 7;
const double eps = 1e-12;
const double PI = 2*acos(0.0);
const double E = 2.71828;
/* Constants end */
/* Defines begin */
#define pb push_back
#define mp make_pair
#define ll long long
#define ull unsigned long long
#define double long double
#define F first
#define S second
#define all(a) (a).begin(),(a).end()
#define forn(i,n) for (int (i)=0; (i)<(n); ++(i))
#define random (rand()<<16|rand())
#define sqr(x) (x)*(x)
#define base complex<double>
#define sz(a) (int)(a).size()
/* Defines end */
int n, m;
int arr[2005][2005];
int sm[2005][2005];
int cnt[100005];
#define bt (1 << 16)
#define sz (64)
int num = 2065 / sz;
void prepare() {
for (int i = 0; i < bt; ++i) {
cnt[i] = __builtin_popcount(i);
}
}
int cnt_bits(ull x) {
int res = 0;
for (int i = 0; i < 4; ++i) {
res += cnt[x % bt];
x /= bt;
}
return res;
}
struct bits {
ull a[2065 / sz];
int ones = 0;
bits() {memset(a, 0, sizeof a); ones = 0;}
void copy(const bits &x) {
for (int i = 0; i < num; ++i) {
a[i] = x.a[i];
}
}
void setbit(int x) {
a[x / sz] |= 1ULL << (x % sz);
if (x <= m) ++ones;
}
void merge(const bits &x) {
ones = 0;
for (int i = 0; i < num; ++i) {
a[i] ^= x.a[i];
ones += cnt_bits(a[i]);
}
}
} r[2005];
void read() {
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
scanf("%d", &arr[i][j]);
arr[i][j] %= 2;
}
}
}
void solve() {
for (int i = 1; i <= n; ++i) {
int now = 0;
for (int j = 1; j <= m; ++j) {
now ^= arr[i][j];
if (now) r[i].setbit(j);
}
}
bits w;
long long res = 0;
for (int x = 1; x <= n; ++x) {
w = bits();
for (int y = x; y <= n; ++y) {
w.merge(r[y]);
int zeroes = m + 1 - w.ones;
int ones = w.ones;
res += ones * (ones - 1) + zeroes * (zeroes - 1);
}
}
res /= 2;
cout << res << "\n";
}
int main(void) {
#ifdef nobik
freopen("input.txt", "rt", stdin);
freopen("output.txt", "wt", stdout);
#endif
prepare();
read();
solve();
return 0;
}
Задача D.
#include <bits/stdc++.h>
using namespace std;
const int N = 15;
const int mod = 1e9+7;
int sz = 10;
int mt[N][N] = {
{1, 0, 0, 0, 2, 2, 2, 1, 1, 1},
{0, 0, 1, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 1, 0, 0, 0, 0, 0, 0},
{0, 1, 1, 1, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 1, 0, 0, 0},
{0, 0, 0, 0, 1, 0, 1, 0, 1, 0},
{0, 0, 0, 0, 0, 1, 1, 0, 0, 1},
{0, 0, 0, 0, 0, 0, 0, 0, 1, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 1},
{0, 0, 0, 0, 2, 2, 2, 1, 1, 1}
};
int result[N][N], c[N][N], d[N][N];
void mul(int a[N][N], int b[N][N]) {
for (int i = 0; i < sz; ++i)
for (int j = 0; j < sz; ++j) {
c[i][j] = a[i][j];
d[i][j] = b[i][j];
a[i][j] = 0;
}
for (int i = 0; i < sz; ++i)
for (int j = 0; j < sz; ++j)
for (int k = 0; k < sz; ++k)
a[i][j] = (a[i][j] + 1LL * c[i][k] * d[k][j]) % mod;
}
int solve(long long n) {
if (n == 1) {
return 9;
}
if (n == 2) {
return 13;
}
n -= 3;
if (n < 0) {
return 0;
}
for (int i = 0; i < sz; ++i)
result[i][i] = 1;
while (n > 0) {
if (n & 1)
mul(result, mt);
mul(mt, mt);
n /= 2;
}
int rs = 1;
rs = (rs + 1LL * result[0][0] * 13) % mod;
rs = (rs + 1LL * result[0][1] * 3) % mod;
rs = (rs + 1LL * result[0][2] * 2) % mod;
rs = (rs + 1LL * result[0][3] * 1) % mod;
rs = (rs + 1LL * result[0][4] * 6) % mod;
rs = (rs + 1LL * result[0][5] * 3) % mod;
rs = (rs + 1LL * result[0][6] * 2) % mod;
rs = (rs + 1LL * result[0][7] * 9) % mod;
rs = (rs + 1LL * result[0][8] * 4) % mod;
rs = (rs + 1LL * result[0][9] * 1) % mod;
return rs;
}
int main() {
long long n;
cin >> n;
cout << solve(n) << endl;
return 0;
}
Задача Е.
#pragma comment(linker,"/STACK:100000000000,100000000000")
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <cmath>
#include <map>
#include <stack>
#include <set>
#include <iomanip>
#include <queue>
#include <map>
#include <functional>
#include <list>
#include <sstream>
#include <ctime>
#include <climits>
#include <bitset>
#include <list>
#include <cassert>
#include <complex>
using namespace std;
/* Constants begin */
const long long inf = 2e18 + 7;
const long long mod = 1e9+9;
const double eps = 1e-9;
const double PI = 2*acos(0.0);
const double E = 2.71828;
/* Constants end */
/* Defines begin */
#define pb push_back
#define mp make_pair
#define ll long long
#define double long double
#define F first
#define S second
#define all(a) (a).begin(),(a).end()
#define forn(i,n) for (int (i)=0; (i)<(n); ++(i))
#define random (rand()<<16|rand())
#define sqr(x) (x)*(x)
#define base complex<double>
/* Defines end */
ll Brute(ll k, bool bad[25][25]){ // stupid Brute
ll cur = 1;
ll num = 0;
while(true){
int a[25], sz = 0;
ll x = cur;
while(x){
a[sz++] = x % 10;
x /= 10;
}
reverse(a, a + sz);
bool ok = true;
for(int i = 1; i < sz; ++i){
if(bad[a[i - 1]][a[i]]){
ok = false;
break;
}
}
num += ok;
if(num == k){
return cur;
}
++cur;
}
}
ll FastBrute(ll k, bool bad[25][25]){ // not so stupid, but Brute
ll pw[25] = {};
pw[0] = 1;
for(int i = 1; i <= 18; ++i){
pw[i] = pw[i - 1] * 10;
}
ll cur = 1;
ll num = 0;
while(true){
int a[25], sz = 0;
ll x = cur;
while(x){
a[sz++] = x % 10;
x /= 10;
}
reverse(a, a + sz);
bool ok = true;
int where = -1;
for(int i = 1; i < sz; ++i){
if(bad[a[i - 1]][a[i]]){
ok = false;
where = i;
break;
}
}
if(!ok){
cur += pw[sz - where - 1];
continue;
}
num += ok;
if(num == k){
return cur;
}
++cur;
}
}
ll cnt_good(ll x, bool bad[25][25]){
ll f[25][20][2][2] = {};
++x;
int a[25], sz = 1;
while(x){
a[sz++] = x % 10;
x /= 10;
}
reverse(a, a + sz);
f[0][0][0][0] = 1;
for(int i = 1; i <= sz; ++i){
for(int last = 0; last <= 9; ++last){
for(int type = 0; type <= 1; ++type){
for(int wasLower = 0; wasLower <= 1; ++wasLower){
if(!f[i - 1][last][type][wasLower]) continue;
for(int cur = 0; cur <= 9; ++cur){
if(type && bad[last][cur]) continue;
if(!wasLower && cur > a[i - 1]) continue;
int ntype = type | (cur > 0);
int nwasLower = wasLower | (cur < a[i - 1]);
f[i][cur][ntype][nwasLower] += f[i - 1][last][type][wasLower];
}
}
}
}
}
ll res = 0;
forn(i, 10) res += f[sz - 1][i][1][1];
return res;
}
ll Dynamic(ll k, bool bad[25][25]){ // correct solution
ll l = 0, r = (ll)(5e18) + 1;
while(r - l > 1){
ll m = l + (r - l) / 2;
if(cnt_good(m, bad) >= k) r = m; else
l = m;
}
if(r > (ll)(5e18)) r = -1;
return r;
}
void Solve(){ // Solution
int n; cin >> n;
bool bad[25][25] = {};
forn(i, n){
int x, y; cin >> x >> y;
bad[x][y] = true;
}
ll k; cin >> k;
// ll bres = Brute(k, bad);
// ll fbres = FastBrute(k, bad);
ll res = Dynamic(k, bad);
//assert(res == bres && res == fbres);
cout << res << "\n";
}
int main(void){
#ifdef nobik
freopen("input.txt", "rt", stdin);
freopen("output.txt", "wt", stdout);
#endif
ios::sync_with_stdio(false);
cin.tie(NULL);
int t; cin >> t;
forn(i, t){
Solve(); // Main Solutions
}
return 0;
}