akhauriyash/Code-Regression huggingface dataset:
#pragma region template
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using vld = vector<ld>;
using vvld = vector<vld>;
using vvvld = vector<vvld>;
using vs = vector<string>;
using pll = pair<ll, ll>;
using vp = vector<pll>;
template <typename T>
using pqrev = priority_queue<T, vector<T>, greater<T>>;
#define rep(i, n) for (ll i = 0, i##_end = (n); i < i##_end; i++)
#define repb(i, n) for (ll i = (n)-1; i >= 0; i--)
#define repr(i, a, b) for (ll i = (a), i##_end = (b); i < i##_end; i++)
#define reprb(i, a, b) for (ll i = (b)-1, i##_end = (a); i >= i##_end; i--)
#define ALL(a) (a).begin(), (a).end()
#define SZ(x) ((ll)(x).size())
//*
constexpr ll MOD = 1e9 + 7;
/*/
constexpr ll MOD = 998244353;
//*/
constexpr ll INF = 1e+18;
constexpr ld EPS = 1e-12L;
constexpr ld PI = 3.14159265358979323846L;
constexpr ll GCD(ll a, ll b) { return b ? GCD(b, a % b) : a; }
constexpr ll LCM(ll a, ll b) { return a / GCD(a, b) * b; }
template <typename S, typename T>
constexpr bool chmax(S &a, const T &b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
template <typename S, typename T>
constexpr bool chmin(S &a, const T &b) {
  if (b < a) {
    a = b;
    return 1;
  }
  return 0;
}
#ifdef OJ_LOCAL
#include "dump.hpp"
#else
#define dump(...) ((void)0)
#endif
template <typename T>
bool print_(const T &a) {
  cout << a;
  return true;
}
template <typename T>
bool print_(const vector<T> &vec) {
  for (auto &a : vec) {
    cout << a;
    if (&a != &vec.back()) {
      cout << " ";
    }
  }
  return false;
}
template <typename T>
bool print_(const vector<vector<T>> &vv) {
  for (auto &v : vv) {
    for (auto &a : v) {
      cout << a;
      if (&a != &v.back()) {
        cout << " ";
      }
    }
    if (&v != &vv.back()) {
      cout << "\n";
    }
  }
  return false;
}
void print() { cout << "\n"; }
template <typename Head, typename... Tail>
void print(Head &&head, Tail &&... tail) {
  bool f = print_(head);
  if (sizeof...(tail) != 0) {
    cout << (f ? " " : "\n");
  }
  print(forward<Tail>(tail)...);
}
#pragma endregion

void Pr(bool f){
  cout << (f ? "Yes" : "No") << "\n";
  exit(0);
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(20);
  ll n, k;
  cin >> n >> k;
  vll a(n, 0);
  rep(i, k){
    ll d;
    cin >> d;
    rep(j, d){
      ll A;
      cin >> A;
      A--;
      a[A]++;
    }
  }
  ll ans = 0;
  rep(i, n){
    ans += a[i] == 0;
  }
  print(ans);
}


Measured memory_bytes: 3640
#include<stdio.h>

int main(){
	char a[200000];
	scanf("%s",&a);
	
	long long sum = 0;
	
	int i = 0;
	
	while(a[i]){
		sum += (int)a[i] - 48;
		
		i++;
	}
	
	if(sum%9 == 0)
		printf("Yes");
	else
		printf("No");
	
}


// 9 8 7 6 5 4 3 2 1 

Measured memory_bytes: 1904
#include <iostream>
#include <vector>
using namespace std;
int solve(const vector<int> l, const int a, const int b, const int c) {
    int n = l.size();
    int best = 1 << 30;
    for (int mask = 0; mask < (1 << (2*n)); ++mask) {
        vector<int> v(4), w(4);
        int m = mask;
        for (int i = 0; i < n; ++i) {
            int j = m % 4;
            m /= 4;
            v[j] += 1;
            w[j] += l[i];
        }
        if ((v[0] > 0) && (v[1] > 0) && (v[2] > 0)) {
            int cur = 10 * (v[0] + v[1] + v[2] - 3);
            cur += abs(w[0] - a) + abs(w[1] - b) + abs(w[2] - c);
            if (best > cur) {
                best = cur;
            }
        }
    }
    return best;
}
int main() {
    int n, a, b, c;
    cin >> n >> a >> b >> c;
    vector<int> l(n);
    for (int i = 0; i < n; ++i) {
        cin >> l[i];
    }
    cout << solve(l, a, b, c) << endl;
    return 0;
}

Measured memory_bytes: 256
a, b = map(int, input().split())

ans = 0
for i in range(a, b + 1):
    si = str(i)
    l = len(si)
    check = True
    for j in range(l // 2):
        if si[j] != si[(-j - 1)]:
            check = False
            break
    if check:
        ans += 1
print(ans)


Measured memory_bytes: 9128
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(),a.end()
#define sz(x) (int)(x).size()
#define uni(x) x.erase(unique(rng(x)),x.end())
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define newline puts("")
#define v(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
typedef set<int> S;
typedef queue<int> Q;
typedef queue<P> QP;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;
const int MOD = 1000000007;
  
int main() {
  int N;
  cin >> N;
  vi t(N);
  v(string) s(N);
  rep(i,N) {
    cin >> s[i] >> t[i];
  }
  string x;
  cin >> x;
  int sum = 0;
  bool o = false;
  rep(i,N) {
    if(!o && s[i] != x) continue;
    if(s[i]==x) {
      o = true;
      continue;
    }
    sum += t[i];
  }
  cout << sum << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
ll n,a,b,c;
string s[100005];
char ans[100005];
int main(void){
    cin>>n>>a>>b>>c;
    for(int i=0;i<n;i++){
        cin>>s[i];
    }
    for(int i=0;i<n-1;i++){
        if(s[i]=="AB"){
            if(a==0&&b==0){
                cout<<"No"<<endl;
                return 0;
            }else{
                if(a<b){
                    ans[i]='A';
                    a++; b--;
                }else if(a>b){
                    ans[i]='B';
                    b++; a--;
                }else{
                    if(s[i+1]=="AB"){
                        ans[i]='A';
                        a++; b--;
                    }else if(s[i+1]=="BC"){
                        ans[i]='B';
                        b++; a--;
                    }else{
                        ans[i]='A';
                        a++; b--;
                    }
                }
            }
        }else if(s[i]=="BC"){
            if(b==0&&c==0){
                cout<<"No"<<endl;
                return 0;
            }else{
                if(b<c){
                    ans[i]='B';
                    b++; c--;
                }else if(b>c){
                    ans[i]='C';
                    c++; b--;
                }else{
                    if(s[i+1]=="BC"){
                        ans[i]='B';
                        b++; c--;
                    }else if(s[i+1]=="AB"){
                        ans[i]='B';
                        b++; c--;
                    }else{
                        ans[i]='C';
                        c++; b--;
                    }
                }
            }
        }else{
            if(c==0&&a==0){
                cout<<"No"<<endl;
                return 0;
            }else{
                if(c<a){
                    ans[i]='C';
                    c++; a--;
                }else if(c>a){
                    ans[i]='A';
                    a++; c--;
                }else{
                    if(s[i+1]=="CA"){
                        ans[i]='A';
                        a++; c--;
                    }else if(s[i+1]=="BC"){
                        ans[i]='C';
                        c++; a--;
                    }else{
                        ans[i]='A';
                        a++; c--;
                    }
                }
            }
        }
        //cout<<a<<" "<<b<<" "<<c<<endl;
    }
    if(s[n-1]=="AB"){
        if(a==0&&b==0){
            cout<<"No"<<endl;
            return 0;
        }else if(a<b){
            ans[n-1]='A';
        }else{
            ans[n-1]='B';
        }
    }else if(s[n-1]=="BC"){
        if(b==0&&c==0){
            cout<<"No"<<endl;
            return 0;
        }else if(b<c){
            ans[n-1]='B';
        }else{
            ans[n-1]='C';
        }
    }else{
        if(c==0&&a==0){
            cout<<"No"<<endl;
            return 0;
        }else if(c<a){
            ans[n-1]='C';
        }else{
            ans[n-1]='A';
        }
    }
    cout<<"Yes"<<endl;
    for(int i=0;i<n;i++){
        cout<<ans[i]<<endl;
    }
    
}


Measured memory_bytes: 6788
#include <bits/stdc++.h>

using namespace std;

const int N = 2048;
int s = 0, n, a[N];
bitset<N*N> dp;

signed main(){
	cin >> n;
	for(int i=0;i<n;++i) cin >> a[i], s += a[i];
	dp[0] = 1;
	for(int i=0;i<n;++i)
		dp = dp | (dp << a[i]);
	for(int i=(s+1)/2;i<=s;++i) if(dp[i]) return cout << i, 0;
	
}

Measured memory_bytes: 5176
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) (x).begin(),(x).end()
using namespace std;
const int INF=1e9,MOD=1e9+7;

int main(){
	int n; cin>>n;
	long long ans=pow(3,n);
	long long mi=1;
	rep(i,n){
		int a; cin>>a;
		if(a%2==0) mi*=2;
	}
	cout<<ans-mi<<endl;
}


Measured memory_bytes: 640
#include "bits/stdc++.h"
using namespace std;
using ll = long long;

#define REP(i,n) for(ll i=0;i<ll(n);i++)
//#define REP(n) for(int i=0;i<ll(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=ll(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=ll(b);i--)

int main() {
	int num, a, b, c, d;
	a = b = c = d = 0;
	string s, t;

	cin >> a >> b >> c;
	num = a / b;
	if (a % b!=0){
		num++;
	}
	num *= c;

	cout << num << endl;
}
 

Measured memory_bytes: 3624
#include<bits/stdc++.h>

#ifdef _PRINTDEBUG
  #include "lib/printdebug.hpp"
#else
  #define printdebug(...) 1
#endif
#define MOD_1_000_000_007 (1000000007LL)
#define LINF (1LL<<60)
#define rep(i, n)   for (long long i = 0; i <  (long long)(n); i++)
#define rep1(i, n)  for (long long i = 1; i <  (long long)(n); i++)
#define rep2(i, n)  for (long long i = 2; i <  (long long)(n); i++)
#define rep0c(i, n) for (long long i = 0; i <= (long long)(n); i++)
#define rep1c(i, n) for (long long i = 1; i <= (long long)(n); i++)
#define rep2c(i, n) for (long long i = 2; i <= (long long)(n); i++)
#define repc0(n, i) for (long long i = (long long)(n); i >= 0; i--)
#define repc1(n, i) for (long long i = (long long)(n); i >= 1; i--)
#define repc2(n, i) for (long long i = (long long)(n); i >= 2; i--)
#define REP(i, n, m) for (long long i = (long long)(n); i < (long long)(m); i++)

namespace solver {
  using namespace std;
  typedef long long ll;

  ll N, K;

  void init() {
    scanf("%lld %lld", &N, &K);
  }

  void solve() {
    ll ans = 0;
    REP(i, K, N+2) {
      ll left = (i-1)*i/2;
      left %= MOD_1_000_000_007;
      ll right = ((N-i+1)+N)*i/2;
      right %= MOD_1_000_000_007;
      ans += right + MOD_1_000_000_007 - left + 1;
      ans %= MOD_1_000_000_007;
      printdebug(i, left, right, ans);
    }
    cout << ans << endl;
  }
}

int main() {
  solver::init();
  solver::solve();
  return 0;
}

Measured memory_bytes: 3688
#include <cstdio>
#include <vector>
#define R second.second
#define Z(i,a,b,c)v.insert(v.begin()+i,make_pair(a,make_pair(b,c)))
using namespace std;
main(){
	int W,Q,d,w,i;char s[2];
	for(;scanf("%d%d",&W,&Q),W;puts("END")){//some case Q==0
		vector<pair<int,pair<int,int> > >v;
		for(Z(0,-2,0,0),Z(1,-1,W,0);Q;Q--)
			if(scanf("%s",s),*s-'w'){
				for(scanf("%d%d",&d,&w),i=0;~v[i].first;i++)if(v[i+1].second.first-v[i].R>=w){Z(i+1,d,v[i].R,v[i].R+w);printf("%d\n",v[i].R);break;}
				if(v[i].first==-1)puts("impossible");
			}else for(scanf("%d",&d),i=0;i<v.size();i++)if(v[i].first==d)v.erase(v.begin()+i);
	}}

Measured memory_bytes: 1044
#include <bits/stdc++.h>

using namespace std;

bool is_odd(int n) {
  int cnt = 0;
  while (n != 0) {
    cnt++;
    n /= 10;
  }
  return cnt % 2 != 0;
}

int main() {
  int n;
  cin >> n;
  int ans = 0;
  for (int i = 1; i <= n; i++) {
    ans += is_odd(i);
  }
  cout << ans << '\n';
  return 0;
}


Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define all(x) x.begin(),x.end()

void solve()
{
 int n;
 cin>>n;
 vector<pair<int,int> >v;
 for(int i=0;i<n;i++){
    int a,b;
    cin>>a>>b;
    v.push_back({a,b});
 }
       int f=0;
   for(int i=0;i<v.size()-2;i++){
    if(v[i].first==v[i].second&&v[i+1].first==v[i+1].second&&v[i+2].first==v[i+2].second){f=1;break;}
 }
 if(f){cout<<"Yes"<<endl;}
 else cout<<"No"<<endl;
}

int main()
{
 ios_base::sync_with_stdio(0);
 cin.tie(0);cout.tie(0);

        solve();

    return 0;
}



Measured memory_bytes: 3640
n,m=map(int,input().split())
ab=[list(map(int,input().split())) for i in range(n)]
ab.sort()

ans=0
for i in range(n):
    if ab[i][1]<=m:
        ans+=ab[i][0]*ab[i][1]
        m-=ab[i][1]
    else:
        ans+=ab[i][0]*m
        break
print(ans)


Measured memory_bytes: 27756
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<queue>
#include<stack>
#include<string>
#include<string.h>
#include<math.h>
using namespace std;
const int maxn=3e2+7;
typedef long long ll;
const int INF=1e9;
int c[300][300],dis[300][300],n,visited[300],dfn[300];
vector<int> v[300];
int dfs(int prex,int x,int num)
{
	visited[x]=1;
	dfn[x]=num;
	int len=v[x].size();
	for(int i=0;i<len;i++)
	{
		if(v[x][i]==prex)
			continue;
		if(visited[v[x][i]])
		{
			if((num-dfn[v[x][i]])%2==0)
				return 0;
		}
		if(visited[v[x][i]]==0&&dfs(x,v[x][i],num+1)==0)
			return 0;
	}
	return 1;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			if(i==j)
				dis[i][j]=0;
			else
				dis[i][j]=INF;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
		{
			scanf("%1d",&c[i][j]);
			if(c[i][j]==1)
			{
				v[i].push_back(j);
				v[j].push_back(i);
			}
		}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			if(i==j)
				dis[i][j]=0;
			else if(c[i][j]==1)
				dis[i][j]=1,dis[j][i]=1;
			else if(c[i][j]==0)
				dis[i][j]=dis[j][i]=INF;
	for(int k=1;k<=n;k++)
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
	if(dfs(-1,1,1)==0)
		printf("-1\n");
	else
	{
		int ans=0;
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				if(dis[i][j]<INF)
					ans=max(ans,dis[i][j]);
		printf("%d\n",ans+1);
	}
	return 0;
}

Measured memory_bytes: 1152
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {

	static Queue<Integer> q = new LinkedList<Integer>();

	static void Divisor(int M){
		for(int i=1; i<Math.sqrt(M); i++) {
			if(M%i!=0)	continue;
			q.add(i);
			q.add(M/i);
		}
		if(M%Math.sqrt(M) == 0)	q.add((int) Math.sqrt(M));
	}

    public static void main(String[] args) throws Exception {
    	try(Scanner sc = new Scanner(System.in)) {

    		int N = sc.nextInt();
    		int M = sc.nextInt();
    		Divisor(M);
    		int max = 0;
    		while(!q.isEmpty()) {
    			int s = q.remove();
    			if(M%s == 0 && M/s >= N) {
    				max = Math.max(max, s);
    			}
    		}
    		System.out.println(max);

    	}
    }
}



Measured memory_bytes: 23764
#include <bits/stdc++.h>
using namespace std;

int main(){
  int N;
  cin >> N;
  float cnt = 0;
  
  for (int i = 1; i < N + 1; i++){
    if (i % 2 == 1) cnt++;    
  }
  
  float ans = cnt / (float)N;
  
  cout << ans;
  
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double db;
typedef pair<int,int> pii;
typedef vector<int> vi;
#define de(x) cout << #x << "=" << x << endl
#define rep(i,a,b) for(int i=a;i<(b);++i)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define fi first
#define se second
const int N = 1e5+5;
int nu[150];
int main()
{
	int a,b,c;
	int n,y;
	scanf("%d%d",&n,&y);
	if(y%1000!=0) printf("-1 -1 -1");
	else
	{
		y/=1000;
		for(int i=0;i<=n;i++)
		{
			for(int j=0;j<=n-i;j++)
			{
				if(i*10+j*5+n-i-j==y)
				{
					printf("%d %d %d",i,j,n-i-j);return 0;
				}
			}
		}
		printf("-1 -1 -1");
	}
	
	return 0;
} 

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int dx[]={1,0,-1,0,1,-1,-1,1};
const int dy[]={0,1,0,-1,1,1,-1,-1};
const int INF = 1<<30;
const long long LINF = 1e18;
const int EPS = 1e-8;
#define PB push_back
#define mk make_pair
#define fr first
#define sc second
#define ll long long
#define reps(i,j,k) for(int i = (j); i < (k); i++)
#define rep(i,j) reps(i,0,j)
#define MOD 1000000007
typedef pair<int,int> Pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
int M,N,manj[10024];
Pii box[512];
int dp[512][10024];
int main(){
	scanf("%d%d",&M,&N);
	int sum[10024] = {};
	rep(i,M){
		scanf("%d",&manj[i]);
	}

	sort(manj,manj+M);reverse(manj,manj+M);
	sum[0] = 0;
	reps(i,1,M+1){
		sum[i] += manj[i-1] + sum[i-1];
	}

	/*rep(i,M+1){
		printf("%d ",sum[i]);
	}
	puts("");*/

	rep(i,N){
		int c,e;
		scanf("%d%d",&c,&e);
		box[i].fr = c;
		box[i].sc = e;
	}

	rep(i,N+1){
		rep(j,M+1){
			dp[i][j] = INF;
			if(j == 0){
				dp[i][j] = 0;
			}
		}
	}

	reps(i,1,N+1){
		rep(j,M+1){
			dp[i][j] = min(dp[i-1][j],dp[i-1][max(0,j-box[i-1].fr)]+box[i-1].sc);
		}
	}
	/*puts("*********************");
	rep(i,N+1){
		rep(j,M+1){
			if(dp[i][j] == INF){
				printf("INF ");
			}else{
				printf("%d ",dp[i][j]);
			}
		}
		puts("");
	}*/

	int ans = 0;

	rep(i,M+1){
		ans = max(ans,sum[i]-dp[N][i]);
	}

	printf("%d\n",ans);

	return 0;
}

Measured memory_bytes: 20904
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(s,i, n) for (int i = (int)s; i < (int)(n); i++)
#define pb push_back
typedef long long ll;

#define max_n 3001
#define INF 1e15

ll  f(int i, int j, int N, vector<ll> &a, vector<vector<ll>> &dp){
    if (dp[i][j] != INF) return dp[i][j];

    int turn = N - (j - i);
    ll d;
    if (turn % 2 == 0) {
        d = max(f(i + 1, j, N, a, dp) + a[i], f(i, j - 1, N, a, dp) + a[j - 1]);
    }
    if (turn % 2 == 1) {
        d = min(-a[i] + f(i + 1, j, N, a, dp), -a[j - 1] + f(i, j - 1, N, a, dp));
    }

    return dp[i][j] = d;
}

int main(){
    int n;
    cin>>n;
    vector<ll> a(n);
    rep(i,n)cin>>a[i];

    vector<vector<ll>> dp(n+1, vector<ll>(n+1,INF));
    for (int i = 0; i <= n; i++) dp[i][i] = 0;
    f(0, n, n, a, dp);
    cout << dp[0][n] << endl;

    return 0;
}

Measured memory_bytes: 71040
#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
#include <utility>
#include <bitset>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstdio>
#include <string.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define forn(i,a,b) for(int i=a;i<=b;i++)
#define INF 2147483647
#define LLINF 9223372036854775807
using namespace std;
int main(){
	int n;
	cin>>n;
	long long cnt=0;
	for(long long i=1;i<=n;i++){
		if(i%3&&i%5)cnt+=i;
	}
	cout<<cnt<<endl;
	return 0;
} 

Measured memory_bytes: 3144
N = int(input())

A = map(int, input().split())

ones = [0] * 60
m = 10 ** 9 + 7

for Ai in A:
    for digit in range(len(bin(Ai)) - 2):
        ones[digit] += ((Ai >> digit) & 1)

res = 0
for i, num in enumerate(ones):
    res += (1 << i) * num * (N - num)

print(res % m)


Measured memory_bytes: 122968
#include<bits/stdc++.h>
using namespace std;
#define int long long

#ifdef LOCAL_DEBUG
  #include "LOCAL_DEBUG.hpp"
#endif

const int MOD = 1e9 + 7;
int mod_pow(int n,int p,int MOD){ // a/n ≡ a*n^(p-2) nとpは互いに素
  int r = 1;
  for(; p > 0; p >>= 1){
    if(p & 1LL) r = (r * n) % MOD;
    n = (n * n) % MOD;
  }
  return r; // r = n^p % MOD
}

signed main(){

  int n,k; cin >> n >> k;
  vector<int> a(n);
  for(int i = 0; i < n; i++){
    cin >> a[i];
  }

  int p = 0;
  for(int i = 0; i < n; i++){
    for(int j = i+1; j < n; j++){
      if(a[i] > a[j]) p++;
    }
  }

  int cnt = 0;
  for(int i = 0; i < n; i++){
    for(int j = 0; j < n; j++){
      if(a[i] > a[j]) cnt++;
    }
  }

  int d = ((k-2)*cnt + MOD)%MOD;
  int ans = (2*cnt + d)%MOD * (k-1) % MOD * mod_pow(2,MOD-2,MOD);
  cout << (ans%MOD + (p*k)%MOD) % MOD << endl;

  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <set>
#include <vector>
#include <utility>

using namespace std;

#define FOR(i,n) for(int i=0; i<n; i++)
#define FOR2(i, z, n) for(int i=z; i<n; i++)

int main() {
  int change, nbr_coins;
  cin >> change >> nbr_coins;

  set<int> coins_set;
  FOR(i, nbr_coins) {
    int coin;
    cin >> coin;
    coins_set.insert(coin);
  }

  vector<int> changes_list(change);

  changes_list[0] = 1;

  FOR2(i, 1, change) {
    if (coins_set.find(i + 1) != coins_set.end()) {
      changes_list[i] = 1;
    } else {
      int min_coins_nbr = 100000;
      for (int j = 0, y = i - 1; j <= y; j++, y--) {
        if (changes_list[j] + changes_list[y] < min_coins_nbr) {
          min_coins_nbr = changes_list[j] + changes_list[y];
        }
      }
      changes_list[i] = min_coins_nbr;
    }
  }

  cout << changes_list[change - 1] << endl;
}


Measured memory_bytes: 3200
#include<stdio.h>

int main(){
	int money=100000, week;
	int i;
	scanf("%d",&week);
	for(i=0;i<week;i++){
		money*=1.05;
		if(money%1000>0){
			money-=money%1000;
			money+=1000;
		}
	}
	printf("%d\n",money);
	return 0;
}

Measured memory_bytes: 592
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define MOD 1000000007
#define PI 3.141592653589793

int main(){
    int n;
    cin >> n;
    set<int> d;
    while(n--){
        int x;
        cin >> x;
        d.insert(x);
    }
    cout << d.size() << endl;
}

Measured memory_bytes: 256
#include<stdio.h>

struct Card{
  char suit;
  char value;
};

void bubble(struct Card A[], int n){
  int l, j;
  struct Card t;
  for ( l = 0; l < n; l++ ){
    for ( j = n-1; j >= l+1; j-- ){
      if ( A[j].value < A[j-1].value ){
	t = A[j]; A[j] = A[j-1]; A[j-1] = t;
      }
    }
  }
}

void selection(struct Card A[], int n){
  int i, p, mini;
  struct Card t;
  for ( i = 0; i < n; i++ ){
    mini = i;
    for ( p = i; p < n; p++ ){
      if ( A[p].value < A[mini].value ) mini = p;
    }
    t = A[i]; A[i] = A[mini]; A[mini] = t;
  }
}

void print(struct Card A[], int n){
  int f;
  for ( f = 0; f < n; f++ ){
    if ( f ) printf(" ");
    printf("%c%c", A[f].suit, A[f].value);
  }
  printf("\n");
}

int isStable(struct Card C1[], struct Card C2[], int n){
  int b;
  for ( b = 0; b < n; b++ ){
    if ( C1[b].suit != C2[b].suit ) return 0;
  }
  return 1;
}

int main(){
  struct Card C1[101], C2[101];
  int n, i;
  char ch;

  scanf("%d\n", &n);
  for ( i = 0; i < n; i++ ){
    scanf("%c%c ", &C1[i].suit, &C1[i].value);
  }

  for ( i = 0; i < n; i++ ) C2[i] = C1[i];

  bubble(C1, n);
  selection(C2, n);

  print(C1, n);
  printf("Stable\n");
  print(C2, n);
  if ( isStable(C1, C2, n) ){
    printf("Stable\n");
  } else {
    printf("Not stable\n");
  }

  return 0;
}



Measured memory_bytes: 2112
/*author : Yashvardhan
Saturday, June 27, 2020
5:31 PM
*/

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

#define int ll
#define pb push_back
#define vi vector<int>
#define pi pair<int,int>
#define vpi vector<pi>
#define ff first
#define ss second
#define mp make_pair
#define endl '\n'
#define all(a) a.begin(), a.end()
#define initialise(a, x) memset(a, x, sizeof(a))
#define rev(Y) reverse(all(Y))

#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define _CRT_SECURE_NO_WARNINGS

#ifdef __APPLE__
#define debug(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){cerr << name << " : " << arg1 << endl;}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
	const char* comma = strchr(names + 1, ',');
	cerr.write(names, comma - names) << " : " << arg1 << "  ";
	__f(comma + 1, args...);}
#else
#define debug(...)
#endif

template <typename T> ostream& operator << (ostream& os,const vector<T>& v){for(int i=0;i<v.size();++i) os<<v[i]<<" ";return os;} 
template <typename T> ostream& operator << (ostream& os,const set<T>& v){for(auto it:v) os<<it<<" ";return os;} 
template <typename T, typename S> ostream& operator << (ostream& os, const pair<T,S>& v) {os<<v.ff<<" "<<v.ss;return os;}

const int mod = 1e9 + 7;
const int inf = 2e18;
const int ninf = -2e18;

int takemod(int a){return ((a%mod)+mod)%mod;}

int pow(int a, int b, int m)
{
	int ans = 1;
	a %= m;
	while (b)
	{
		if (b & 1)
			ans = (ans * a) % m;
		b /= 2;
		a = (a * a) % m;
	}
	return ans;
}

int modinv(int a){return takemod( pow( takemod(a), mod-2,mod ) );}


signed main()
{

	ios_base::sync_with_stdio(false);
	cin.tie(0);

	#ifdef __APPLE__
		freopen("input.txt","r",stdin);
		freopen("output.txt","w",stdout);
		freopen("error.txt","w",stderr);
	#endif

	time_t t1, t2;
	t1 = clock();
	
	string s,t;
	cin >> s >> t;
	
	int n = s.size();

	int ans = 0;
	for(int i = 0; i < n; i++){
		if(s[i] != t[i]) ans++;
	}
	cout << ans << endl;
	

	t2 = clock();
	cerr << endl << t2-t1 << endl;
	
	return 0;
}



Measured memory_bytes: 3800
// Created by arvybhatt

#include <bits/stdc++.h>
#define fast ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define F first
#define S second
#define p_b push_back
#define m_p make_pair
#define rep(i,n) for(int i=0;i<(n);++i)
#define repA(i,a,n) for(int i=a;i<=(n);++i)
#define repD(i,a,n) for(int i=a;i>=(n);--i)

using namespace std;
using ll = long long;

ll power(ll x, ll y) { ll temp; if( y == 0) return 1; temp = power(x, y/2); if (y%2 == 0) return temp*temp; else return x*temp*temp; } 

int main()
{
    fast;
    ll x;cin>>x;
    ll s=100;
    ll i=1;
    ll count=0;
    while(s<x)
    {
    	s+=(floor((double)s/100));
    	count++;
    }
    cout<<count;



    

}






Measured memory_bytes: 3640
#include <bits/stdc++.h>
using namespace std;

int main()
{
    int N;
    cin >> N;
    vector<int> X(N);
    for (int &x : X)
    {
        cin >> x;
    }
    int ans = 50 * 50 * N;
    for (int P = 1; P <= 100; P++)
    {
        int sum = 0;
        for (int x : X)
        {
            sum += (x - P) * (x - P);
        }
        if (sum < ans)
        {
            ans = sum;
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <iterator>
#include <climits>
#include <unordered_map>
#include <functional>
#include <queue>

#define rep(i, n) for(int i = 0, end = (int)(n); i < end; i++)

#define p2(a, b) cout << a << "\t" << b << endl
#define p3(a, b, c) cout << a << "\t" << b << "\t" << c << endl

using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;

inline int ctoi(char c) {
    return (int)(c -'0');
}

// ----------------------------------------------------------

int main() {
    string a,b,c;
    cin >> a >> b >> c;
    cout << a[0] << b[1] << c[2] << endl;
    return 0;
}


Measured memory_bytes: 256
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "unordered_map"
#include "unordered_set"
#include "iomanip"
#include "cmath"
#include "random"
#include "bitset"
#include "cstdio"
#include "numeric"
#include "cassert"

using namespace std;

const long long int MOD = 1000000007;
//const int MOD = 998244353;
//const long long int MOD = 998244353;

long long int N, M, K, H, W, L, R;
//long long int N, M, K, H, W, L, R;


int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> N;
	cin >> M;
	vector<long long int>dp(N + 1);
	dp[0] = 1;
	for (int i = 0; i < M; i++) {
		cin >> K;
		dp[K] = MOD;
	}
	for (int i = 1; i <= N; i++) {
		if (dp[i] == MOD)continue;
		dp[i] += dp[i - 1];
		if (i > 1) {
			dp[i] += dp[i - 2];
			dp[i] %= MOD;
		}
	}
	cout << dp.back() << endl;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;

#define int long long
int32_t main()
{
    int n,x,y;
    cin>>n>>x>>y;
    
    int fin=y-x-1;
    int ans[2001]={0};
    
    for(int i=1;i<n;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
            if(i<=x && j>=y)
                ans[j-i-fin]++;
            else
                ans[min(j-i,(abs(i-x)+abs(j-y)+1))]++;
        }
    }
    for(int i=1;i<n;i++)
        cout<<ans[i]<<"\n";
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;

#define int long long
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
signed main(){
	int a;
	string b;
	cin >> a >> b;

	b[0] -= '0';
	b[2] -= '0';
	b[3] -= '0';
	int c = b[0] * 100 + b[2] * 10 + b[3]; 

	int ans = a * c;
	ans /= 100;

	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 3628
#include <bits/stdc++.h>
using namespace std;

int main() {
  int n;
  cin >> n;
  float v[n];
  for(int i = 0; i < n; i++){
    cin >> v[i];
  }
  
  sort(v, v+n);
  
  float item = v[0];
  for(int i = 1; i < n; i++){
    item = (item + v[i])/2;
  }
  cout << item << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
using vl = vector<ll>;

/* short */
#define pb push_back
#define mp make_pair
#define Fi first
#define Se second
#define ALL(v) begin(v), end(v)
#define RALL(v) rbegin(v), rend(v)

/* REPmacro */
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define FORR(i, a, b) for(int i = (a); i >= (b); i--)
#define REP(i, n) for(int i = 0; i < (n); i++)
#define FOREACH(x, a) for(auto x : a)

/* exchange */
#define CHMIN(a, b) (a) = min((ll)(a), (ll)(b))
#define CHMAX(a, b) (a) = max((ll)(a), (ll)(b))

/* function */
#define IN(x) cin >> x
#define DEBUG(x) cerr << (x) << " "
#define LN() cerr << "\n"
#define PRINT(x) cout << (x) << endl
#define BR cout << endl

/* const */
const int ARRAY = 100005;
const int INF = 1001001001; // 10^9
const ll LINF = 1001001001001001001; // 10^18
const int MOD = 1e9 + 7;

ll N = 0;
ll t;
ll ret = 0;

void input() {
  IN(N);
}

void solve() {
  for (ll i = 9; i >= 1; i--) {
    if (N % i == 0) {
      ll p = N/i;
      if (p < 10) {
        PRINT("Yes");
        return;
      }
    }
  }
  PRINT("No");
}

int main(void){
  input();
  solve();
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;


int main(){
    string S, T;
    cin >> S >> T;
    bool ans=true;
    if(S.size() != T.size()-1) ans=false;
    for(int i=0; i<S.size(); i++){
        if(S[i] != T[i]) ans=false;
    }
    if(ans) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 3624
#include<bits/stdc++.h>
using namespace std;

int main(){
    int s;
    cin >> s;
    int first = s / 100;
    int last = s % 100;
    bool YYMM = false;
    bool MMYY = false;
    
    if (last < 13 && last > 0) {
        YYMM = true;
    }
    if (first < 13 && first > 0) {
        MMYY = true;
    }
    if (YYMM && MMYY) {
        cout << "AMBIGUOUS" << endl;
    }else if(YYMM && !MMYY){
        cout << "YYMM" << endl;
    }else if(MMYY && !YYMM){
        cout << "MMYY" << endl;
    }else{
        cout << "NA" << endl;
    }
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
//INSERT ABOVE HERE
signed main(){
  Int n;
  cin>>n;
  vector<Int> v(n);
  iota(v.begin(),v.end(),1);
  do{
    for(Int i=0;i<n;i++){
      if(i) cout<<" ";
      cout<<v[i];
    }
    cout<<endl;
  }while(next_permutation(v.begin(),v.end()));
  return 0;
}



Measured memory_bytes: 3092
#include<bits/stdc++.h>
using namespace std;
#define FAST ios_base::sync_with_stdio(false);cin.tie(NULL);
#define time_taken_start int begtime = clock();
#define time_taken_end int endtime = clock(); \
cerr << "\n\n" << "Time elapsed: " << \
(endtime - begtime)*1000/CLOCKS_PER_SEC << " ms\n\n"; \
return 0;
#define ll long long int
#define ull unsigned long long int
#define ld long double
#define mod 1000000007
#define inf 1000000000000000007
#define eps 0.000000000001
#define pi acosl(-1)
#define pdd pair<ld,ld>
#define pll pair<ll,ll>
#define ff first
#define ss second
#define vpl vector<pll>
#define vll vector<ll>
#define mseti multiset <ll>
#define msetd multiset <ll,greater<ll>>
#define pb push_back
#define pf push_front
#define lb lower_bound
#define ub upper_bound 
#define stp fixed<<setprecision(20)
#define endl '\n'
map<ll,ll> val;
ll a[200009];
ll n,k;
int main()
{
	FAST
	#ifdef ayk_16
    freopen("input.txt","rt",stdin);
	freopen("output.txt","wt",stdout);
	#endif
	cin>>n>>k;
	ll x;
	ll sum=0;
	val[0]++;
	ll ans=0;
	if(k==1)
	{
		cout<<0;
		return 0;
	}
	for(ll i=1;i<=n;i++)
	{
		cin>>x;
		sum+=x;
		sum--;
		sum+=k;
		sum%=k;
		a[i]=sum;
		ans+=val[sum];
		val[sum]++;
		if(i>=k-1)
			val[a[i-k+1]]--;
	}
	cout<<ans;
}

Measured memory_bytes: 14336
Module AtCoder166
  
    Sub Main(args As String())

        Dim arr As String() = Split(Console.ReadLine())
        Dim Sunuke_Count As Integer = CInt(arr(0))
        Dim Kashi_Count As Integer = CInt(arr(1))

        'スヌケ番号のリスト
        Dim suneke_List As List(Of Integer) = New List(Of Integer)()
        For i As Integer = 1 To Sunuke_Count
            suneke_List.Add(i)
        Next

        For i As Integer = 1 To Kashi_Count
            Dim hold_Sunuke_count As Integer = CInt(Console.ReadLine())
            Dim hold_Sunuke_num As String() = Split(Console.ReadLine())
            For j As Integer = 1 To hold_Sunuke_count
                Dim targetSunukeNum As Integer = CInt(hold_Sunuke_num(j - 1))
                If suneke_List.Contains(targetSunukeNum) = True Then suneke_List.Remove(targetSunukeNum)
                If suneke_List.Count = 0 Then Exit For
            Next
            If suneke_List.Count = 0 Then Exit For
        Next

        Console.WriteLine(suneke_List.Count.ToString())

    End Sub

End Module

Measured memory_bytes: 28684
import java.io.IOException;
import java.io.InputStream;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

public class Main {
  public static void main(String[] args) throws IOException {
    new Main().execute(System.in);
//    ByteArrayOutputStream os = new ByteArrayOutputStream();
//    os.write(("15\n" +
//        "18\n" +
//        "26\n" +
//        "35\n" +
//        "36\n" +
//        "20").getBytes());
//    InputStream is = new ByteArrayInputStream(os.toByteArray());
//    new Main().execute(is);
  }

  public void execute(InputStream in) {
    Scanner sc = new Scanner(in);
    List<Integer> list = Arrays.asList(
        sc.nextInt(),
        sc.nextInt(),
        sc.nextInt(),
        sc.nextInt(),
        sc.nextInt()
    );
    int k = sc.nextInt();

    for (int i = 0; i < list.size() - 1; i++) {
      int a = list.get(i);
      for (int j = 1; j < list.size(); j++) {
        int b = list.get(j);

        if (b - a > k) {
          System.out.println(":(");
          return;
        }
      }
    }
    System.out.println("Yay!");
  }
}


Measured memory_bytes: 21844
import sys

def main():
    n,m,k = map(int,input().split())
    ab = [list(map(int,input().split())) for _ in range(m)]
    cd = [list(map(int,input().split())) for _ in range(k)]

    class UnionFind():
        def __init__(self, n):
            self.n = n
            self.parents = [-1] * n

        def find(self, x):
            if self.parents[x] < 0:
                return x
            else:
                self.parents[x] = self.find(self.parents[x])
                return self.parents[x]

        def union(self, x, y):
            x = self.find(x)
            y = self.find(y)

            if x == y:
                return

            if self.parents[x] > self.parents[y]:
                x, y = y, x

            self.parents[x] += self.parents[y]
            self.parents[y] = x

        def size(self, x):
            return -self.parents[self.find(x)]

        def same(self, x, y):
            return self.find(x) == self.find(y)

        def members(self, x):
            root = self.find(x)
            return [i for i in range(self.n) if self.find(i) == root]

        def roots(self):
            return [i for i, x in enumerate(self.parents) if x < 0]

        def group_count(self):
            return len(self.roots())

        def all_group_members(self):
            return {r: self.members(r) for r in self.roots()}

        def __str__(self):
            return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

    uf = UnionFind(n)
    ans = [0]*n
    cnt = [0]*n

    for a,b in ab:
        uf.union(a-1, b-1)
        cnt[a-1] += 1
        cnt[b-1] += 1

    for i in range(n):
        ans[i] = uf.size(i)

    for c,d in cd:
        if uf.same(c-1, d-1):
            ans[c-1] -= 1
            ans[d-1] -= 1

    for i in range(n):
        print(ans[i] - cnt[i] - 1, end = ' ')

if __name__ == '__main__':
    main()


Measured memory_bytes: 119640
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;

namespace AtCoder
{
    class Program
    {
        private static string Read() { return Console.ReadLine(); }
        private static int ReadInt() { return int.Parse(Read()); }
        private static long ReadLong() { return long.Parse(Read()); }
        private static double ReadDouble() { return double.Parse(Read()); }
        private static int[] ReadInts() { return Array.ConvertAll(Read().Split(), int.Parse); }
        private static long[] ReadLongs() { return Array.ConvertAll(Read().Split(), long.Parse); }
        private static double[] ReadDoubles() { return Array.ConvertAll(Read().Split(), double.Parse); }

        static int Solve(int N, int D, int[][] X)
        {
            int ans = 0;
            for (int i = 0; i < N; ++i)
            {
                for (int j = i + 1; j < N; ++j)
                {
                    int d = 0;
                    for (int k = 0; k < D; ++k)
                    {
                        int x = X[i][k] - X[j][k];
                        d += x * x;
                    }
                    int s = (int)Math.Sqrt(d);
                    if (s * s == d) { ++ans; }
                }
            }
            return ans;
        }

        static void Main(string[] args)
        {
            var V = ReadInts();
            int N = V[0], D = V[1];
            var X = new int[N][];
            for (int i = 0; i < N; ++i) { X[i] = ReadInts(); }
            Console.WriteLine(Solve(N, D, X));
        }
    }
}


Measured memory_bytes: 13268
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cassert>
#define int long long
#define double long double
using namespace std;
typedef pair<int, int> P;
 
int sx, sy, gx, gy;
int n;
int x[200000], y[200000];
vector<P> p;
int dp[200002];		//dp[length] = min(max)
const double PAI = 3.141592653589793238;
 
signed main()
{
	int i;
	
	cin >> sx >> sy >> gx >> gy;
	cin >> n;
	for (i = 0; i < n; i++) cin >> x[i] >> y[i];
	
	if (sx > gx) { swap(sx, gx); swap(sy, gy); }
	if (sy > gy) {
		sy *= -1;
		gy *= -1;
		for (i = 0; i < n; i++) { y[i] *= -1; }
	}
	
	for (i = 0; i < n; i++) {
		if (sx <= x[i] && x[i] <= gx && sy <= y[i] && y[i] <= gy) {
			p.push_back(P(x[i], y[i]));
		}
	}
	sort(p.begin(), p.end());
	
	//LIS
	int INF = 1145141919810;
	for (i = 0; i <= n + 1; i++) dp[i] = INF;
	dp[0] = -INF;
	for (i = 0; i < p.size(); i++) {
		dp[upper_bound(dp, dp + n + 1, p[i].second) - dp] = p[i].second;
	}
	for (i = n; i > 0; i--) {
		if (dp[i] < INF) break;
	}
	
	//LISの長さ
	int Count = i;
	
	//場合分け
	double ans;
	
	if (min(gx - sx, gy - sy) + 1 > Count) {
		ans = (gy - sy + gx - sx) * 100 - (double)Count * (20.0 - PAI * 5.0);
	}
	else {
		ans = (gy - sy + gx - sx) * 100 - (Count - 1.0) * (20 - PAI * 5) + (PAI * 10 - 20);
	}
	
	printf("%.20Lf\n", ans);
	return 0;
}

Measured memory_bytes: 9584
#include<bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof a) ;
#define vi vector<int>
#define ull unsigned long long
#define ll long long 
#define db double 
#define ldb long double
#define fl float
#define rep(i,a,b) for(int i=a;i<b;i++)
#define lrep(i,a,b) for(ll i=a;i<b;i++)
//#define mod 1000000007
#define mpr make_pair
#define pb push_back
#define fr first
#define sn second
#define bpp(x) __builtin_popcountll(x)
const ldb PI = 3.14159265358979323846264338327950288419716939937510582097494459230781640628620899863;
const int INF = 1e9+7;
bool ok(string &s ,int l ,int r)
{
while(s[l]==s[r]) l++,r--;
return l>=r; 
}/*
ll por(ll a,int b)
{
ll res=1,M=998244353;
while(b)
{
if(b&1)
res=(res*a)%M;
a=(a*a)%M;
b/=2;
}
return res;
}
void rev(vector<int>&arr,int l,int r)
{
    for(;l<r;l++,r--) swap(arr[l],arr[r]);
}
*/
int prime[]={2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89,97,101,103};
int add(int a,int b) // integer range
{
long x=a+b;
if(x>=INF)
x-=INF;
return x;
}
/*
goto e;


e:
;
*/
void solve()
{
ll n,x,ct=0; cin>>n;
lrep(i,2,sqrt(n)+1)
{
if(n%i==0)
{
	x=n/i;
	while(x%i==0)
	x/=i;
	if(x%i==1)
	ct++;
}
else if(n%i==1)
{
if((i*i)+1==n)
ct++;
else
ct+=2;
}
}
ct+=min(2ll,n-2);
cout<<ct;
return;
}
int main()
{
ios_base::sync_with_stdio(0);
	cin.tie(0);
	int t=1;
//	cin>>t;
while(t--)
{
solve();
}
return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int N;
    cin >> N;
    vector<long long> A(N);
    for (int i = 0; i < N; i++)
        cin >> A[i];

    for (int i = 1; i < N; i++)
        A[i] += A[i - 1];

    long long sum = A[N - 1];
    long long res = 1LL << 60;
    for (int i = 0; i < N - 1; i++) {
        long long diff = abs(sum - 2 * A[i]);
        res = min(res, diff);
    }
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
#define rep(i, n) for(int i=0; i<int(n); i++)
#define ALL(a) (a).begin(), (a).end()
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int MAX = 200002;

long long fac[MAX], finv[MAX], inv[MAX];

void pre_comb(void){
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;
	for(int i=2; i<MAX; i++){
		fac[i] = fac[i-1] * i % mod;
		inv[i] = mod - inv[mod%i] * (mod/i) % mod;
		finv[i] = finv[i-1] * inv[i] % mod;
	}
}

long long comb(int n, int k){
	if(n < k) return 0;
	if(n < 0 || k < 0) return 0;
	return fac[n] * (finv[k] * finv[n-k] % mod) % mod;
}

ll mpow(ll x, ll r){
	if(r == 1) return x;
	if(r % 2 == 0){
		ll aa = mpow(x, r/2);
		return aa*aa%mod;
	}else{
		ll aa = mpow(x, r/2);
		return (aa*aa%mod)*x%mod;
	}
}

int main(){
	pre_comb();
	int B, W;
	cin >> B >> W;
	ll sum1[B+W], sum2[B+W], sum3[B+W], two[B+W+1];
	rep(i, B+W+1){
		if(i==0) two[i] = 1;
		else two[i] = two[i-1] * 500000004 % mod;
	}
	rep(i, B+W){
		if(i==0){
			if(W==1) sum2[i] = 500000004;
			else sum2[i] = 0;
			sum1[i] = 0;
			sum3[i] = 0;
		}else{
			if(i+1 >= B && i < B+W-1){
				sum1[i] = sum1[i-1] + comb(i-1, B-2)*two[i+1]%mod;
			}else{
				sum1[i] = sum1[i-1];
			}
			if(i+1 >= W && i < B+W-1){
				sum2[i] = sum2[i-1] + comb(i, W-1)*two[i+1]%mod;
			}else{
				sum2[i] = sum2[i-1];
			}
			if(i >= W && i < B+W-1){
				sum3[i] = sum3[i-1] + comb(i-1, W-1)*two[i+1]%mod;
			}else{
				sum3[i] = sum3[i-1];
			}
		}
	}
	rep(i, B+W){
		ll ans = 0;
		if(i > 0) ans = (ans + sum2[i-1]) % mod;
		ans = (ans + sum3[B+W-1] - sum3[i]) % mod;
		if(i < B+W-1) ans = (ans + sum1[B+W-1] - sum1[i]) % mod;
		if(i+1 >= B && i < B+W-1) ans = (ans + comb(i, B-1)*two[i+1] % mod) % mod;
		cout << ans << endl;
	}
	return 0;
}


Measured memory_bytes: 13184
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i < (n); i++)
using namespace std;
using ll = long long;
int main(){
  int a, b, c;
  cin >> a;
  cin >> b;
  cin >> c;
  if ((a==b) & (b==c)){
    cout << "No" << endl;
  }
  else if ((a==b)||(b==c)||(a==c)){
    cout << "Yes" << endl;
  }
  else{
    cout << "No" << endl;
  }
}

Measured memory_bytes: 384
#include<string>
#include<iostream>
#include<algorithm>
#include<set>
#include<math.h>
#include<vector>
#include<sstream>
#include<queue>
#include<functional>
#include<bitset>
#include<cstdio>
#include<iomanip>
#include<map>
#include<unordered_map>
#include<unordered_set>
#include <string.h>
using ll = long long;

#define rep(i, n) for(ll i = 0; i < (int)(n); i++)
#define reps(i,x) for(ll i=1;i<=(int)(x);i++)
#define rrep(i,x) for(ll i=((int)(x)-1);i>=0;i--)
#define rreps(i,x) for(ll i=((int)(x) - 1 * 100);i>0;i--)
#define all(x) (x).begin(),(x).end()
#define m0(x) memset(x,0,sizeof(x))
#define vll vector<ll>
#define vi vector<int>
#define mp make_pair
#define vpll vector<pair<ll,ll>>
#define vpi vector<pair<int,int>>
using namespace std;
ll n;
int main() {
	ll x;
	cin >> x;
	n = 1;
	int i = 2;
	while (n < x) {
		n += i++;
	}
	cout << i  - 1<< endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;

int main() {
  int ans;
  vector<int> vec(5);
  for (int i = 0; i < 5; i++) {
    cin >> vec.at(i);
  }
  for (int i = 0; i < 5; i++) {
    if (vec.at(i) == 0) cout << 1 + i << endl;
  }
}



Measured memory_bytes: 3596
#include<stdio.h>

 int main(void){

  int a,b,d,r;

double f;


 scanf("%d %d",&a,&b);

 d = a/b;

 r = a%b;

 f =(double)a/(double)b;

   printf("%d %d %lf\n",d,r,f);

 return 0;

}

Measured memory_bytes: 636
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <set>
#include <cmath>
using namespace std;
int main(void){
    // Your code here!
    set<int> st;
    int a, b, c;
    cin>>a>>b>>c;
    
    st.insert(a);
    st.insert(b);
    st.insert(c);
    
    cout<<st.size()<<endl;
}


Measured memory_bytes: 256
#[allow(unused_macros)]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };

    ($next:expr, mut $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, [ $t:tt ]) => {
        {
            let len = read_value!($next, usize);
            (0..len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
        }
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, bytes) => {
        read_value!($next, String).into_bytes()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    input! {
        x: i64,
    }
    let m = x % 100;
    let d = x / 100;
    let ans = if m <= d * 5 { 1 } else { 0 };
    println!("{}", ans);
}


Measured memory_bytes: 4352