akhauriyash/Code-Regression huggingface dataset:
from collections import defaultdict


class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i


n, m = map(int, input().split())
aa = list(map(int, input().split()))
counter = defaultdict(list)

bit = Bit(m + 1)
ans_1 = 0
for a, b in zip(aa, aa[1:]):
    counter[b].append(a)
    bit.add(a + 1, 1)
    bit.add(b, -1)
    if a > b:
        bit.add(1, 1)
        ans_1 += b
    else:
        ans_1 += b - a

ans_prev = ans_1
ans_min = ans_1
for x in range(2, m + 1):
    ans_x = ans_prev
    px = x - 1
    if px in counter:
        ans_x += sum((px - a) % m - 1 for a in counter[px])
    ans_x -= bit.sum(px)
    ans_min = min(ans_min, ans_x)
    ans_prev = ans_x
print(ans_min)


Measured memory_bytes: 20192
#include <iostream>
#include <vector>
#include <set>
#include <queue>
#include <climits>
#include <tuple>
#include <algorithm>
struct entry {
    std::vector<long long>::iterator a, b, c;
};
struct compare1 {
    bool operator()(const entry &x, const entry &y) const {
        return *x.a + *x.b + *x.c < *y.a + *y.b + *y.c;
    }
};
struct compare2 {
    bool operator()(const entry &x, const entry &y) const {
        return std::tie(x.a, x.b, x.c) < std::tie(y.a, y.b, y.c);
    }
};
int main() {
    int x, y, z, k;
    std::cin >> x >> y >> z >> k;
    std::vector<long long> a(x), b(y), c(z);
    for (auto &ai: a) std::cin >> ai;
    for (auto &bi: b) std::cin >> bi;
    for (auto &ci: c) std::cin >> ci;
    std::sort(a.begin(), a.end(), std::greater<>());
    std::sort(b.begin(), b.end(), std::greater<>());
    std::sort(c.begin(), c.end(), std::greater<>());
    a.push_back(LLONG_MIN / 3);
    b.push_back(LLONG_MIN / 3);
    c.push_back(LLONG_MIN / 3);
    std::priority_queue<entry, std::vector<entry>, compare1> q;
    q.push({ a.begin(), b.begin(), c.begin() });
    std::set<entry, compare2> s;
    for (int i = 0; i < k; i++) {
        entry e = q.top();
        q.pop();
        if (!s.insert(e).second) {
            i--;
            continue;
        }
        std::cout << (*e.a + *e.b + *e.c) << std::endl;
        q.push({ e.a + 1, e.b, e.c });
        q.push({ e.a, e.b + 1, e.c });
        q.push({ e.a, e.b, e.c + 1 });
    }
}


Measured memory_bytes: 640
#include<iostream>
#include<algorithm>
#include <cassert>
#include<string>
#include<vector>
#include <utility>
#include <math.h>
#include<cmath>
#include<map>
#include <limits>
# include <iomanip>
#define INF 1000000009;

using namespace std;
int gcd(int a, int b) {
	while (a % b != 0) {
		int c = 0;
		c = a % b;
		a = b;
		b = c;
	}
	return  b;
}
int kaizyo(int a) {
	long long ans = 1;
	for (int i = a; i > 0; i--) {
		ans *= i;
		ans = ans % 1000000007;
		//cout << ans << endl;
	}
	ans = ans % 1000000007;
	return ans;
}

	
	int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };
	


int main() {
	long long a = 0, b = 0,c=0,ans=1000;
	cin >> a;
	b = a;
	for (long long i = 1; i <= sqrt(a); i++) {
		if (a % i == 0) {
			if (i > a / i) {
				break;
			}
			b = a/i;
			c = 0;
			for (int j = 0; b > 0; j++) {
				b = b / 10;
				c++;
			}
			ans = min(ans, c);
		}
	}
	cout << ans << endl;
	return 0;
}


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

int main()
{

	int n,a,b;
	scanf("%d %d %d",&n,&a,&b);
	int ans = 0;
	int x;
	for(int i = 1; i <= n; ++i)
	{
		scanf("%d",&x);
		if(x < a) ans++;
		else if(x >= b) ans++;
	}
	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 384
#include<stdio.h>

int main(){
	int n,i,j;
	scanf("%d",&n);
	for(i=0;i<=25;i++){
		for(j=0;j<14;j++){
			if(n==i*4+j*7){
				puts("Yes");
				return 0;
			}
		}
	}
	puts("No");
	return 0;
}


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

const int N = 55;

int n, k, a[N];
vector<int> r;

int main(){
    scanf("%d%d", &n, &k);
    for(int i = 1; i <= n; i++) scanf("%d", a + i);
    for(int i = 0, p = -1; i <= k; i++){
        int t = -1;
        for(int j = 1; j <= n; j++) if(j != p) if(t < 0 || a[t] > a[j]) t = j;
        if(a[t] == 0){ puts("-1"); return 0; }
        for(int j = 1; j <= n; j++) if(j != t && j != p){ r.push_back(j); a[j]--; }
        r.push_back(t); a[t]--;
        p = t;
    }
    printf("%d\n", r.size());
    for(int i : r) printf("%d ", i); puts("");
}

Measured memory_bytes: 256
#include <stdio.h>

void swap(int,int);
int gcd(int,int);

int main() {
  int x,y,g;
  scanf("%d%d",&x,&y);
  g = gcd(x,y);
  printf("%d\n",g);
  return 0;
}

int gcd(int x,int y){
  int d;
  while (y>0) {
    d = x%y;
    x = y;
    y = d;
  }
  return x;
}

void swap(int a,int b){
  int temp;
  temp = a;
  a = b;
  b = temp;
}

Measured memory_bytes: 592
#include <bits/stdc++.h>
using namespace std;
int main(){
  int N;cin >> N;
  int a[N];for(int i = 0; N > i; i++)cin>>a[i];
  int dp[N+1];
  dp[0] = 0;
  dp[1] = abs(a[1] - a[0]);
  
  for(int i = 2; N > i; i++){
    dp[i] = min( dp[i-2]+abs(a[i-2]-a[i]) , dp[i-1]+abs(a[i-1]-a[i]) );
  }
  cout << dp[N-1] << endl;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;

int main() {
  string s, t;
  cin >> s >> t;
  int ans = 0;
  rep(i, 3) if (s[i] == t[i]) ans++;
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<stdio.h>
//#include <bits/stdc++.h>
#include<vector>
#include<float.h>
#include<iomanip>
#include<algorithm>
#include<string>
#include<cstring>
#include<math.h>
#include<cmath>
#include<sstream>
#include<set>
#include<map>
#include<queue>
#include <cassert>
#include <cmath>
#include<cstdint>

#define INF 1e9
#define rep(i,n)for(int i=0;(i)<(int)(n);i++)
#define REP(i,a,b)for(int i=(int)(a);(i)<=(int)(b);i++)
#define VEC(type, c, n) std::vector<type> c(n);for(auto& i:c)std::cin>>i;
#define vec(type,n) vector<type>(n)
#define vvec(m,n) vector<vector<int>> (int(m),vector<int>(n))
#define ALL(a)  (a).begin(),(a).end()


using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
using P = pair<ll, ll>;



//Combination MOD
const ll MOD = INF + 7;

ll mpow(ll x, ll n){
    ll ans = 1;
    while(n != 0){
        if(n & 1)ans = ans * x % MOD;
        x = x * x % MOD;
        n = n >> 1;
    }
    return ans;
}


int main(){
    ll n;
    cin >> n;
    ll res = 0;
    for(ll i = sqrt(n) + 100; i > 0; i--){
        if(n % i == 0){
            ll j = n / i;
            string s = to_string(i), t = to_string(j);
            res = max(s.size(), t.size());
          cout << res << endl;
          return 0;
        }
    }

}


Measured memory_bytes: 256
#include <stdio.h>

int main(void)
{
  int N, T;
  int min = 1001;
  scanf("%d%d", &N, &T);
  for(int i = 0; i < N; i++){
  	int c, t;
    scanf("%d%d", &c, &t);
    if(t <= T && c < min) min = c;
  }
  if(1000 < min) printf("TLE\n");
  else printf("%d\n", min); 
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=(2e5)+10;
int n;
ll ans,a[maxn];
int main() {
	//freopen("1.txt","r",stdin);
	scanf("%d",&n);
	for (int i=1;i<=n;i++) {
		scanf("%lld",&a[i]);
		a[i]-=i;
	}
	sort(a+1,a+(n+1));
	for (int i=1;i<=n;i++)
		ans+=abs(a[(n+1)/2]-a[i]);
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 1792
N,M = map(int,input().split())
L = []
for i in range(N):
  L.append(list(input().split()))
A = []
S = 0
sub = 0
opt = ['+','-']
for i in opt:
  for j in opt:
    for k in opt:
      A = []
      sub = 0
      for p in range(N):
        A.append(eval(i+L[p][0]+j+L[p][1]+k+L[p][2]))
        A.sort()
      for l in range(M):
        sub += A[N-l-1]        
      if S <= sub:
        S = sub
print(S)          

Measured memory_bytes: 3316
A, B, C, K = map(int, input().split())

v = [1, 0, -1]
val = 0
for idx, i in enumerate([A, B, C]):
    val += v[idx] * i
    if K - i <= 0:
        print(val - v[idx] * (i - K))
        break
    else:
        K -= i

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

int main()
{
    ll a,b,k;
    cin>>a>>b>>k;
    if(k > a){
        k =  k - a;
        a = 0;
        b = k>b ? 0 : b-k; 
    }
    else{
        a -= k;
    }
    cout<<a<<" "<<b<<endl;
}

Measured memory_bytes: 256
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define maxn 200005

int n,k;
int a[maxn],v[maxn],cnt[maxn];

inline int read(){
	int x=0,f=1; char ch=getchar();
	for (;ch<'0'||ch>'9';ch=getchar()) if (ch=='-') f=-1;
	for (;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x*f;
}

int main(){
	n=read(),k=read();
	for (int i=1;i<=n;i++) v[i]=a[i]=read();
	sort(v+1,v+n+1); int tmp=unique(v+1,v+n+1)-v-1;
	if (tmp<=k){puts("0"); return 0;}
	for (int i=1;i<=n;i++) a[i]=lower_bound(v+1,v+tmp+1,a[i])-v;
	for (int i=1;i<=n;i++) ++cnt[a[i]];
	sort(cnt+1,cnt+tmp+1); int ans=0;
	for (int i=1;i<=tmp-k;i++) ans+=cnt[i];
	cout<<ans<<endl;
	return 0;
}


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

using namespace std;

#define X first
#define Y second
#define mp make_pair
#define pb push_back
#define Debug(...) fprintf(stderr, __VA_ARGS__)

typedef long long LL;
typedef long double LD;
typedef unsigned int uint;
typedef pair <int, int> pii;
typedef unsigned long long uLL;

template <typename T> inline void Read(T &x) {
  char c = getchar();
  bool f = false;
  for (x = 0; !isdigit(c); c = getchar()) {
    if (c == '-') {
      f = true;
    }
  }
  for (; isdigit(c); c = getchar()) {
    x = x * 10 + c - '0';
  }
  if (f) {
    x = -x;
  }
}

template <typename T> inline bool CheckMax(T &a, const T &b) {
  return a < b ? a = b, true : false;
}

template <typename T> inline bool CheckMin(T &a, const T &b) {
  return a > b ? a = b, true : false;
}

const int N = 100005;

priority_queue <pair <LL, int>> q;
int n, m, a[N], f[N], p[N];
vector <int> v[N];
LL ans;

inline int F(int x) {
  while (x != f[x]) {
    x = f[x] = f[f[x]];
  }
  return x;
}

int main() {
#ifdef wxh010910
  freopen("d.in", "r", stdin);
#endif
  Read(n), Read(m);
  for (int i = 0; i < n; ++i) {
    Read(a[i]), f[i] = i;
  }
  for (int i = 0, x, y; i < m; ++i) {
    Read(x), Read(y);
    f[F(x)] = F(y);
  }
  int c = 0;
  for (int i = 0; i < n; ++i) {
    if (F(i) == i) {
      ++c;
    }
    v[F(i)].pb(i);
  }
  if (2 * (c - 1) > n) {
    puts("Impossible");
  } else if (c == 1) {
    puts("0");
  } else {
    a[n] = 1 << 30;
    for (int i = 0; i < n; ++i) {
      if (F(i) == i) {
        sort(v[i].begin(), v[i].end(), [&](const int &x, const int &y) {
            return a[x] < a[y];
            });
        v[i].pb(n), p[i] = 1, ans += a[v[i][0]], q.push(mp(-a[v[i][1]], i));
      }
    }
    for (c -= 2; c; --c) {
      pair <LL, int> x = q.top();
      q.pop();
      ans -= x.X, ++p[x.Y], q.push(mp(-a[v[x.Y][p[x.Y]]], x.Y));
    }
    printf("%lld\n", ans);
  }
#ifdef wxh010910
  Debug("My Time: %.3lfms\n", (double)clock() / CLOCKS_PER_SEC);
#endif
  return 0;
}


Measured memory_bytes: 6536
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define int long long
#define inf 1000000007
#define LINF 100000000000000007LL
#define ll long long
using namespace std;
signed main(){
	int a,b;
	cin>>a>>b;
	cout<<max(0LL,a-2*b)<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>
int main()
{   char s1[20];
 while(scanf("%s",s1)!=EOF)
 {
  int t=0,s=0,i;

   int l=strlen(s1);
   for( i=1;i<l;i++)
   {
       if((i==1||i==l-1)&&s1[i]=='C')
            {   s=-1;
                break;
            }
         if(s1[i]=='C'&&i>=2&&i<=l-2)
                 t++;
        if(s1[i]=='B'||s1[i]=='A'||(s1[i]>='D'&&s1[i]<='Z'))
              {
                 s=-1;
                 break;
              }

   }
   if(s==-1)
    printf("WA\n");
   else if(s1[0]=='A'&&t==1)
    printf("AC\n");
    else
    printf("WA\n");

 }
    return 0;
}


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

if a < 0 < b:
    print("Zero")
elif 0 < a < b:
    print("Positive")
elif a < b < 0:
    if (b - a + 1) % 2 == 0:
        print("Positive")
    else:
        print("Negative")


Measured memory_bytes: 2940
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int MaxN = 2e5 + 5;
 
int main() {
	LL n, k;
	scanf("%lld %lld", &n, &k);
	LL sum = 0;
	for(LL i = 1; i <= n; i++) {
		if(n / i > 0) {
			sum += (n/i) * max(0LL, (i - k));
			if(n % i >= k) sum += n % i - k + 1;
		}
		else sum += max(0LL, n%k - k + 1);
	}
	if(k == 0) sum = n * n;
	printf("%lld\n", sum);
	return 0;
}

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

using namespace std;
typedef long long ll;

#define FAST ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define mp make_pair
#define pb push_back
#define lp(i,s,f) for(ll i = s; i < ll(f); i++)
#define inF freopen("input.in", "r", stdin);
#define outF freopen("output.in", "w", stdout);
#define endl '\n'
#define MOD 1000000007
#define mm(arr) memset(arr, 0, sizeof(arr))

string mat[7];
int n, m, k;
vector< vector<bool > > vec;
vector< vector<bool > > vec2;
void color1(bool rows[], int ind1){
    if(ind1 == n){
        vector<bool> aa;
        for(int i = 0; i < n; i++){
            aa.pb(rows[i]);
        }
        vec.pb(aa);
        return;
    }
    color1(rows, ind1 + 1);
    rows[ind1] = 1;
    color1(rows, ind1 + 1);
    rows[ind1] = 0;
}
void color2(bool cols[], int ind1){
    if(ind1 == m){
        vector<bool> aa;
        for(int i = 0; i < m; i++){
            aa.pb(cols[i]);
        }
        vec2.pb(aa);
        return;
    }
    color2(cols, ind1 + 1);
    cols[ind1] = 1;
    color2(cols, ind1 + 1);
    cols[ind1] = 0;
}
int main(){
    FAST
    cin >> n >> m >> k;
    for(int i = 0; i < n; i++){
        cin >> mat[i];
    }
    bool done1[n + 1], done2[m + 1];
    mm(done1); mm(done2);
    color1(done1, 0); color2(done2, 0);
    int ans = 0;
    for(int i = 0; i < vec.size(); i++){
        for(int j = 0; j < vec2.size(); j++){
            int cnt = 0;
            for(int a = 0; a < n; a++){
                if(vec[i][a])continue;
                for(int b = 0; b < m; b++){
                    if(vec2[j][b])continue;
                    if(mat[a][b] == '#')cnt++;
                }
            }
            if(cnt == k)ans++;
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3640
#include<stdio.h>
#define N 100000
void bubbleSort(int a[], int array_size)
{
	int i, j, temp;
	int k;
	int cnt=0;
	for (i=0; i<(array_size - 1);i++) {
    		for (j=(array_size-1);j>i;j--) {
      		if(a[j-1]>a[j]) {
        			temp=a[j-1];
       			a[j-1] = a[j];
        			a[j]=temp;
        			cnt++;
        		}
        	}
        }

	for(k=0; k<array_size-1;k++){
		printf("%d ",a[k]);
	}
	for(k=array_size-1; k<array_size;k++){
		printf("%d\n",a[k]);
	}
        printf("%d\n",cnt);
}

int main()
{
	int i,j,n;
	int a[N];
	
	scanf("%d",&n);
	
	for(i=0;i<n;i++){
		scanf("%d",&a[i]);
	}
	
	bubbleSort(a,n);

  return 0;
}


Measured memory_bytes: 2092
#include<stdio.h>
#include<stdlib.h>
#define MAX 500000
#define NIL NULL
struct t{
  int val;
  struct t *parent,*left,*right;
};
typedef struct t * T;
int n;
T root=NIL;

void insert(int u){
  T next,look,z;
  z=(T)malloc(sizeof(struct t));
  z->val=u;
  z->parent=z->left=z->right=NIL;
  next=root;
  look=NIL;
  while(next!=NIL){
    look=next;
    if(z->val > look->val) next=look->right;
    else next=look->left;
  }
  z->parent=look;

  if(z->parent==NIL) root=z;
  else if(z->val > look->val) look->right=z;
  else look->left=z;

}
T find(int u){
  T look=root;
  while(look!=NIL){
    if(look->val==u) return look;
    if(look->val > u) look=look->left;
    else look=look->right;
  }
  return NIL;
}
T getMinimum(T u){
  while(u->left!=NIL){
    u=u->left;
  }
  return u;
}
T getSuccessor(T x){
  T y;
  if(x->right!=NIL) return getMinimum(x->right);

  y=x->parent;
  while(y!=NIL&&x==y->right){
    x=y;
    y=y->parent;
  }
}

void delete(int key){
  T del=find(key),x,y;
  if(del->left==NIL||del->right==NIL) y=del;
  else y=getSuccessor(del);

  if(y->right!=NIL) x=y->right;
  else x=y->left;

  if(x!=NIL) x->parent=y->parent;

  if(y->parent==NIL) root=x;
  else if(y->parent->left==y) y->parent->left=x;
  else  y->parent->right=x;

  if(y!=NIL) del->val=y->val;
}
void preorder(T u){
  if(u==NIL) return;
  printf(" %d",u->val);
  preorder(u->left);
  preorder(u->right);
}
void inorder(T u){
  if(u==NIL) return;
  inorder(u->left);
  printf(" %d",u->val);
  inorder(u->right);
}
int main(){
  int i,u;
  char com[10];
  scanf("%d",&n);
  //for(i=0;i<n;i++) tree[i].p=tree[i].l=tree[i].r=NIL;

  for(i=0;i<n;i++){
    scanf("%s",com);
    if(com[0]=='i'){
      scanf("%d",&u);
      insert(u);
    }else if(com[0]=='f'){
      scanf("%d",&u);
      if(find(u)!=NIL) printf("yes\n");
      else printf("no\n");
    }else if(com[0]=='d'){
      scanf("%d",&u);
      delete(u);
    }else{
       inorder(root);
       printf("\n");
       preorder(root);
       printf("\n");
     }
  }
  return 0;
}



Measured memory_bytes: 20524
#include<iostream>
#include<string>
using namespace std;
int main()
{
  long d,t,s;
  cin>>d>>t>>s;
  long D;
  D=t*s;
  if (D>=d)
  {
    cout<<"Yes"<<endl;
  }
  else
  {
    cout<<"No"<<endl;
  }
  return 0;
}

Measured memory_bytes: 3632
#import sys
#import numpy as np
#import math
#import itertools
#from fractions import Fraction
#import itertools
from collections import deque
#import heapq
#from fractions  import gcd
#input=sys.stdin.readline
#import bisect

n=int(input())
a=list(map(int,input().split()))
r=[0]*(n+1)
s=sum(a)
q=0
s=2
ans=10**9
for i in range(n):
    r[i+1]=r[i]+a[i]
for l in range(2,n-1):
    for i in range(q,l):
        if a[i]>r[l]-2*r[i]:
            q=i
            break
    for i in range(s,n):
        if a[i]>(r[-1]-r[l])-2*(r[i]-r[l]):
            s=i
            break
    M=max(r[q],r[l]-r[q],r[-1]-r[l]-(r[-1]-r[s]),r[-1]-r[s])
    m=min(r[q],r[l]-r[q],r[-1]-r[l]-(r[-1]-r[s]),r[-1]-r[s])
   
    ans=min(ans,(M-m))
print(ans)

Measured memory_bytes: 112632
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,k,a=1;
  cin>>n>>k;
  for(int i=0;i<n;i++){
    if(a*2>a+k){
      a+=k;
    }else{
      a*=2;
    }
  }
    cout<<a<<endl;
    return 0;
  }


Measured memory_bytes: 256
// Last Change: 02/03/2019 21:09:06.
#include <algorithm>
#include <array>
#include <bitset>
#include <cmath>
#include <cstdlib>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <memory>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

using namespace std;
using ll = long long;

void LoopUntilZeroInpput() {
  int hogegegege = 0;
  while (cin >> hogegegege && hogegegege != 0) {
  }
}

int main() {
  int T, X;
  double ans;
  cin >> T >> X;
  T = T * 10000;
  ans = T / X;
  ans = ans / 10000;
  cout << ans << endl;
}


Measured memory_bytes: 256
# ==================================================-
# 高速素因数分解
# """2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr


n=int(input())
soinnsuu=factorization(n)

def get_times(n):
    if n<3:
        return 1
    elif n<6:
        return 2
    elif n<10:
        return 3
    elif n<15:
        return 4
    elif n<21:
        return 5
    elif n<28:
        return 6
    elif n<36:
        return 7
    elif n<45:
        return 8
    else:
        return 9
ans=0
for i in soinnsuu:
    sisuu=i[1]
    ans+=get_times(sisuu)
if n==1:
    print(0)
else:
    print(ans)

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

int main(){
  int N, M;
  cin >> N >> M;
  vector<int> A(M);
  vector<vector<int>> C(M);
  for(int i = 0; i < M; ++i){
    cin >> A[i];
    int b;
    cin >> b;
    for(int j = 0; j < b; ++j){
      int c;
      cin >> c;
      --c;
      C[i].push_back(c);
    }
  }
  constexpr int INF = 1e9;
  vector<int> dp((1<<N), INF);
  dp[0] = 0;
  for(int i = 0; i < M; ++i){
    vector<int> dp_ = dp;
    int bit = 0;
    for(auto c : C[i]) bit |= (1<<c);
    for(int j = 0; j < (1<<N); ++j){
      dp_[j|bit] = min(dp_[j|bit], dp[j]+A[i]);
    }
    swap(dp,dp_);
  }
  if(dp.back() >= INF){
    cout << -1 << endl;
    return 0;
  }
  cout << dp.back() << endl;
}


Measured memory_bytes: 384
// inputに入力データ全体が入る
function Main(input) {
    // 1行目がinput[0], 2行目がinput[1], …に入る
    input = input.split("\n");
    // tmp0 = input[0].split(" ");
    tmp1 = input[1].split(" ");

    n = Number(input[0])
    p = tmp1.map(Number)

    var ans = 0
    var before_p = p[0]

    for(var i=1; i<n-1; i++)
    {
      after_p = p[i+1]
      if((before_p < p[i] && p[i] < after_p) || (before_p > p[i] && p[i] > after_p)){
        ans++
      }
      before_p = p[i]
    }
    console.log(ans)
}
  //*この行以降は編集しないでください（標準入出力から一度に読み込み、Mainを呼び出します）
Main(require("fs").readFileSync("/dev/stdin", "utf8"));
// Main("AAAA\n");

Measured memory_bytes: 7372
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);
#define bs binary_search
#define pb push_back
#define F first 
#define S second 
#define M 1000000007
#define lc "\n"
ll power(ll x,ll y,ll p)  
{  
    ll res=1; 
    x=x%p; 
    while(y>0)  
    {  
        if(y&1) res=(res*x)%p;  
        x=(x*x)%p;  
    }  
    return res;  
} 
int main() 
{
    fastio
    string s; cin>>s; int k=0;
    if(s[2]==s[3]&&s[4]==s[5]) cout<<"Yes";
    else cout<<"No";
	return 0;
}

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

typedef long long ll;
const int Maxn=1e5;
const ll Mod=1000000007;

int N,K;
vector<int> G[Maxn+5];
void addedge(int u,int v) {
	G[u].push_back(v);
	G[v].push_back(u);
}

long long ans;

long long DFS(int u,int fa,int dep) {
	int tmp=K-min(dep,2);
	for(int i=0;i<(int)G[u].size();i++) {
		int v=G[u][i];
		if(v==fa)continue;
		if(DFS(v,u,dep+1)==0)
			return 0;
		ans=ans*tmp%Mod;
		tmp--;
	}
	return ans;
}

int main() {
	#ifdef LOACL
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
	#endif
	scanf("%d %d",&N,&K);
	for(int i=1;i<N;i++) {
		int u,v;
		scanf("%d %d",&u,&v);
		addedge(u,v);
	}
	ans=K;
	printf("%lld\n",DFS(1,-1,1));
	return 0;
}


Measured memory_bytes: 13244
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>

using namespace std;

int gcd(int x , int y){
    if(y>x){
        swap(x,y);
    }
    
    int z = x % y;
    
    if(z != 0){
        return( gcd(y , z) );
    } else {
        return(y);
    }
}

signed main(){
    int n , ans=0;
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            for(int k=1;k<=n;k++){
                ans += gcd ( i , gcd(j , k));       
            }
        }
    }
    
    cout<< ans << endl;
    return(0);
}

Measured memory_bytes: 3624
#include<bits/stdc++.h>
using namespace std;
int N;
int sff(int j,int i) {
	int d = 1;
	int r = 0;
	bool ch[3];
	fill(ch, ch + 3, false);
	while (i > 0) {
		int a = j % 3;
		if (a == 0) {
			r += 3*d;
			ch[0] = true;
		}
		else if (a == 1) {
			r += 5*d;
			ch[1] = true;
		}
		else {
			r += 7*d;
			ch[2] = true;
		}
		d *= 10;
		j /= 3;
		i--;
	}
	if (ch[0] && ch[1] && ch[2]&&r<=N) {
		return 1;
	}
	else return 0;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> N;
	int ans = 0;
	for (int i = 3; i < 10; i++) {
		for (int j = 0; j < pow(3, i); j++) {
			ans += sff(j, i);
		}
	}
	cout << ans;
}

Measured memory_bytes: 384
#include<iostream>
using namespace std;
int main(){
  int n,i,j,ans=0;
  cin >> n;
  for(i=1;i<=n;i=i+2){
    int count=0;
    for(j=1;j<=i;j++){
      if(i%j==0){
        count++;
      }
    }
    if(count==8){
      ans++;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 3544
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
  int n, k;
  cin >> n >> k;

  vector<int> h(n);
  for (int i = 0; i < n; i++) {
    cin >> h[i];
  }
  sort(h.begin(), h.end(), greater<int>());

  long long ans = 0;
  for (int i = 0; i < n; i++) {
    if (i < k) {
      // ans++;
    } else {
      ans += h[i];
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 1024
program main

  implicit none
  integer :: a(3,3), n
  integer, allocatable :: b(:) 

  integer :: i,j,k
  integer :: aa(3,3) = 0
  
  read(*,*) a(1,:)
  read(*,*) a(2,:)
  read(*,*) a(3,:)
  read(*,*) n
  allocate( b(n) )
  do i = 1, n
    read(*,*) b(i)
  end do

  do k = 1, 10
    do i = 1, 3
      do j = 1, 3
        if( a(i,j) == b(k) ) aa(i,j) = 1
      end do
    end do
  end do
  
  k = 0
  if( sum( aa(1,:) ) == 3 ) k = k + 1
  if( sum( aa(2,:) ) == 3 ) k = k + 1
  if( sum( aa(3,:) ) == 3 ) k = k + 1
  if( sum( aa(:,1) ) == 3 ) k = k + 1
  if( sum( aa(:,2) ) == 3 ) k = k + 1
  if( sum( aa(:,3) ) == 3 ) k = k + 1
  if( ( aa(1,1) + aa(2,2) + aa(3,3) ) == 3 ) k = k + 1
  if( ( aa(1,3) + aa(2,2) + aa(3,1) ) == 3 ) k = k + 1
  
  if ( k > 0 ) then
    print*, "Yes"
  else
    print*, "No"
  end if
  
 
end program main


Measured memory_bytes: 768
using System;
using System.Collections.Generic;
using System.Linq;
using static System.Console;
using static System.Convert;
using static System.Math;
using Pair = System.Tuple<int, int>;
using Edge = System.Tuple<int, int, long>;
//using Debug;
//using static System.Globalization.CultureInfo;

class Program
{
    static void Main(string[] args)
    {
        var num = Input.num;
        var str = ReadLine();
        var b = str.Count(c => c == 'B');
        var r = str.Count(c => c == 'R');
        WriteLine(r > b ? "Yes" : "No");
    }
}

public class Input
{
    public static string read => ReadLine();
    public  static int[] ar => Array.ConvertAll(read.Split(' '), int.Parse);
    public  static int num => ToInt32(read);
    public static long[] arL => Array.ConvertAll(read.Split(' '), long.Parse);
    public  static long numL => ToInt64(read);
    public static char[][] gred(int h) 
        => Enumerable.Repeat(0, h).Select(v => read.ToCharArray()).ToArray();
    public static int[][] twodim(int num)
        => Enumerable.Repeat(0, num).Select(v => ar).ToArray();
    public static long[][] twodimL(int num)
        => Enumerable.Repeat(0, num).Select(v => arL).ToArray();
    public const long Inf = (long)1e18;
    public const double eps = 1e-6;
    public  const string Alfa = "abcdefghijklmnopqrstuvwxyz";
    public  const int MOD = 1000000007;
}

Measured memory_bytes: 13268
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define INF 2e9
#define ALL(v) (v).begin(), (v).end()
using namespace std;
typedef long long ll;
int GCD(int a,int b){return b?GCD(b,a%b):a;}
int LCM(int a,int b){return (a*b)/GCD(a,b);}
int abs(int x){return x>0?x:-x;}
 
//const int dx[] = {1, 0, -1, 0, 1, -1, -1, 1};
//const int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};

int main()
{
	string s;
	cin >> s;

	int ans = 0;
	int cnt = 0;

	REP(i, (int)s.size()){
		if (s[i] == 'A' or s[i] == 'C' or s[i] == 'G' or s[i] == 'T'){
			cnt++;
			ans = max(ans, cnt);
		}
		else cnt = 0;
	}

	cout << ans << endl;


}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <cassert>
#include <limits>
#include <numeric>
#include <type_traits>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <functional>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <complex>
#include <climits>

using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<string> vs;
typedef pair<ll, ll> P;
#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
#define REP(i,n)  FOR(i,0,n)

ll gcd(ll a, ll b) {
  while (a && b) {
    if (a >= b) a %= b;
    else b %= a;
  }
  return a + b;
}
ll ketasum(ll n) { //桁の数字全ての和を返す 例: 112 -> 4
	ll sum=0;
	if (n<0) return 0;
	while (n>0) {
		sum += n%10;
		n /= 10;
	}
	return sum;
}

typedef pair<ll, ll> pair_t;

bool comp(const pair_t &a, const pair_t &b) {
        return a.first < b.first;
}

void sort2vectors(vector<ll> &av, vector<ll> &bv)
{ // ふたつの配列をまとめてそーと A[2,1] B[3,4] -> 1,4 2,3
        ll n = av.size();
        vector<pair_t> p(n);
        vector<ll> av2(n), bv2(n);
        for (ll i = 0; i < n; i++)
                p[i] = make_pair(av[i], bv[i]);
        sort(p.begin(), p.end(), comp);
        for (ll i = 0; i < n; i++) {
                av2[i] = p[i].first;
                bv2[i] = p[i].second;
        }
        av = av2;
        bv = bv2;
}
ll facctorialMethod(ll k){ //階乗
	ll s;
	if(k > 1){
		s = k*facctorialMethod(k-1);
	} else {
		s = 1;
	}
	return s;
}
vl primes(ll n){
	vl x(n);
	REP(i, n){
		x[i] = 0;
	}
	for(ll i = 2; i < sqrt(n) + 2; i++){
		while(n % i == 0){
			n /= i;
			x[i-1] += 1;
		}
	}
	if(n > 1){
		x[n-1] += 1;
	}
	return x;
}
const ll mod = 1000000007;
const ll INF = 1<<29;

// 変数定義start(vectorはresizeしようね)
ll N;
vl A;
// 変数定義end

void solve(){
	cin >> N;
	A.resize(N);
	REP(i, N){
		cin >> A[i];
	}
	ll count = 0;
	ll mini;
	for(ll i = 0; i < N; i++){
		mini = i;
		for(ll j = i; j < N; j++){
			if(A[j] < A[mini]){
				mini = j;
			}
		}
		swap(A[i], A[mini]);
		if(i != mini){
			count++;
		}
	}
	REP(i, N){
		if(i < N-1){
			cout << A[i] << " ";
		} else {
			cout << A[i] << endl;
		}
	}
	cout << count << endl;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	solve();
}



Measured memory_bytes: 3180
#include<bits/stdc++.h>
 
using namespace std;
 
using   ll=long long;
using   ld=long double;
 
#define fast           ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define endl           "\n"
#define int            long long 
#define pb             push_back
#define mp             make_pair
#define vll            vector<ll>
#define ff              first
#define ss              second
#define pll            pair<ll,ll>
#define ALL(v)         v.begin(),v.end()
#define ALLR(v)        v.rbegin(),v.rend()
#define pii            3.14159265358979323

void solve()
{
	ll n;
	
	cin>>n;
	
	map<pair<ll,ll>,ll> cn;
	
	for(int i=1;i<=n;i++)
	{
		string s=to_string(i);
		
		ll l=s[0]-'0';
		ll r=s[s.size()-1]-'0';
		
		cn[{l,r}]++;
	}
	
	ll ans=0;
	
	for(auto m:cn)
	{
		ll l=m.ff.ff;
		ll r=m.ff.ss;
		
		ans+=m.ss*(cn[{r,l}]);
	}
	
	cout<<ans;
}
 
signed main()
{
 
    fast;
 
    ll t;
    
    t=1;
    
    //cin>>t;
    
    while(t--)
    {
        solve();
    }
 
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define x first
#define y second
#define mp make_pair
#define pb push_back
#define kk 1000000007
int n,m,k,a,b,c,tmp,cc[300005];
vector<int > ee;
map<int ,int > mm;
int main(){
	scanf("%d",&n);
	for (int i=0;i<n;i++) scanf("%d",&cc[i]);
	for (int i=0;i<n;i++) ee.pb(cc[i]);
	sort(cc,cc+n);
	for (int i=0;i<n;i++){
		mm[cc[i]] = i;
	}
	for (int i=0;i<n;i++){
		if (mm[ee[i]]%2 != i%2) tmp++;
	}
	printf("%d\n",tmp/2);
	return 0;
}

Measured memory_bytes: 8916
S = input()
result = 0
for i in range(len(S)):
    head = S[i:]
    for j in range(len(head)):
        tail = head[:j + 1]
        if len(list(filter(lambda x: x not in "ACGT", tail))) == 0:
            result = len(tail) if len(tail) > result else result
print(result)


Measured memory_bytes: 2940
/*
By Tianyi Chen. All rights reserved.
Date: 2017-03-12
*/
#include<bits/stdc++.h>
using namespace std;
int n,ans,a[100000];int64_t psum[100000];
int main() {
 scanf("%d",&n);for(int i=0;i<n;++i)scanf("%d",a+i);sort(a,a+n);
 *psum=*a;
 for(int i=1;i<n;++i)psum[i]=psum[i-1]+a[i];
 for(int i=0;i<n;++i) {
  auto et=upper_bound(a,a+n,2*a[i]);
  if(et==a+n) {
   ++ans;continue;
  }
  int64_t v=psum[et-1-a];
  while(v<a[n-1]) {
   auto net=upper_bound(a,a+n,2*v);
   if(net==a+n)break;
   if(net==et)goto nx;
   v=psum[net-1-a];
   et=net;
  }
  ++ans;
 nx:;
 }
 printf("%d\n",ans);
}

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

const int MAX_N = 1e5 + 5;

char s[MAX_N];

int main() {
	scanf(" %s", &s);

	int cnt_g = 0, cnt_p = 0, score = 0;
	for(int i = 0; i < strlen(s); i++) {
		if(s[i] == 'g') {
			if(cnt_g > cnt_p) {
				score++;
				cnt_p++;
			}
			else {
				cnt_g++;
			}
		}
		else if(s[i] == 'p') {
			if(cnt_g > cnt_p) {
				cnt_p++;
			}
			else {
				score--;
				cnt_g++;
			}
		}
	}

	printf("%d\n", score);
	return 0;
}


Measured memory_bytes: 384
#include <iostream>
#include <string>
#include <vector>
#include <queue>
using namespace std;

int m[26];
vector<int> used;
priority_queue<int> pq;
int main() {
	int N, K; cin >> N >> K;
	string P;
	for(int i=0; i<N; ++i){
	    cin >> P;
	    ++m[P[0]-'A'];
	}
	for(int i=0; i<26; ++i) pq.push(m[i]);
	int ans;
	bool f=true;
	for(ans=-1; f; ++ans){
	    for(int i=0; i<K; ++i){
	        if(pq.top()<1){
	            f=false;
	            break;
	        }
	        else{
	            used.push_back(pq.top());
	            pq.pop();
	        }
	    }
	    if(f){
	        for(int i=K-1; i>=0; --i){
	            pq.push(used[i]-1);
	            used.pop_back();
	        }
	    }
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
N=int(input())
s=input().split()
result=1
if '0' in s:
  print(0)
else:
  for i in range (N):
    result=result*int(s[i])
    if result> 10**18:
      print(-1)
      break
    elif i==N-1 and result<=10**18:
      print(result)



Measured memory_bytes: 19484
from math import sin, cos, radians

N = int(input())

p1 = (0, 0)
p2 = (100, 0)
th = radians(60)

def koch(n, a, b):
    global th

    if n == 0:
        return
    
    s = ((2 * a[0] + 1 * b[0]) / 3, (2 * a[1] + 1 * b[1]) / 3)
    t = ((1 * a[0] + 2 * b[0]) / 3, (1 * a[1] + 2 * b[1]) / 3)
    u = ((t[0] - s[0]) * cos(th) - (t[1] - s[1]) * sin(th) + s[0],
         (t[0] - s[0]) * sin(th) + (t[1] - s[1]) * cos(th) + s[1])

    koch(n - 1, a, s)
    print(*s)
    koch(n - 1, s, u)
    print(*u)
    koch(n - 1, u, t)
    print(*t)
    koch(n - 1, t, b)

print(*p1)
koch(N, p1, p2)
print(*p2)


Measured memory_bytes: 5776
// C - Step
#include <bits/stdc++.h>
using namespace std;

int main(){
	int N; cin>>N;
	int64_t s = 0, h = 0, a;
	for(int i=0; i<N; ++i){
		cin>>a;
		s += (h = max(h, a)) - a;
	}
	cout<< s <<endl;
}


Measured memory_bytes: 3612
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)

int main() {
  int n;
  cin >> n;
  vector<int> vec(n);
  rep(i, n){
    cin >> vec.at(i);
  }

  int high=0;
  int sum = 0;
  rep(i,n){
    if (vec.at(i) >= high){
      sum ++;
      high = max(high,vec.at(i));
    }
  }
  
  cout << sum << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const int MOD=1000000007;

int main() {
  string s;
  cin >> s;
  int size=s.size();
  ll ans=0;
  stack<int> st;
  for(int i=0;i<size;i++){
    if(s.at(i)=='B'){
      st.push(i);
    }
  }
  if(st.size()==0){
    cout << 0 << endl;
    return 0;
  }
  int stsize=st.size();
  for(int i=0;i<stsize;i++){
    ans=ans+size-i-1-st.top();
    st.pop();
  }
  cout << ans << endl;
}

Measured memory_bytes: 4300
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <string>
 
int main()
{
    int a, b;

    std::cin >> a >> b;

    if(b % a == 0){
        std::cout << a + b;
    }
    else {
        std::cout << b - a;
    }

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define INTF 1000000007

int main()
{
 int n;
 cin >> n;
 vector<double> p(n,0);

 for(int i=0; i<n; i++)
    cin >> p[i];

  vector<vector<double>> dp(n+1, vector<double>(n+1, 0.0));
  dp[0][0] = 1;

  for(int i=1; i<=n; i++)
  {
    for(int j=0; j<=i; j++)
    {
      dp[i][j+1] += dp[i-1][j]*(p[i-1]);
      dp[i][j] += dp[i-1][j]*(1.0 - p[i-1]); 
    }
  }

  double ans = 0.0;
  for(int i=n/2+1; i<=n; i++)
    ans = (ans+dp[n][i]);

  cout<<setprecision(10) <<ans;
  return 0;
}


Measured memory_bytes: 70656
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <climits>
#include <cstring>

#define rep(i, m, n) for(int i=int(m);i<int(n);i++)
#define all(c) begin(c),end(c)

template<typename T1, typename T2>
inline void chmin(T1 &a, T2 b) { if (a > b) a = b; }

template<typename T1, typename T2>
inline void chmax(T1 &a, T2 b) { if (a < b) a = b; }

typedef long long int ll;
using ll = long long int;
using ull = long long unsigned int;
using Int = long long int;
using namespace std;
#define INF (1 << 30) - 1
#define INFl (ll)5e15
#define DEBUG 0
#define dump(x)  cerr << #x << " = " << (x) << endl
#define MOD 1000000007


//edit
class Solve {
public:
    Int N, A, B;

    Int left(Int A, Int B) {
        Int ret = (A - 1);
        A -= ret;
        B -= ret;
        if (abs(B - A) % 2) {
            ret++;
            B--;
        }
        Int add = (B - A) / 2;
        ret += add;
        return ret;
    }

    Int right(Int A, Int B) {
        Int ret = (N - B);
        A += ret;
        B += ret;
        if (abs(B - A) % 2) {
            ret++;
            A++;
        }
        Int add = (B - A) / 2;
        ret += add;
        return ret;
    }

    void solve() {
        cin >> N >> A >> B;
        Int kouho = -1;
        if (abs(A - B) % 2 == 0) {
            kouho = abs(A - B) / 2;
        }

//        Int tmp = max(A - 1, B - 1);
        if (kouho == -1) {
            kouho = left(A, B);
        } else {
            chmin(kouho, left(A, B));
        }
//        tmp = max(N - A, N - B);
        chmin(kouho, right(A, B));
        cout << kouho << endl;

    }
};


int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);

    Solve().solve();


    return 0;
}


Measured memory_bytes: 888
#include<bits/stdc++.h>
#define rep(i,n) for(int i = 0;i<n;i++)
using namespace std;
typedef pair<int,int> P;
typedef long long ll;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0;}
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0;}

const int mod = 2019;
int main() {
    ll n,p;
    cin >> n >> p;
    string s;
    cin >> s;
    ll ans = 0;
    if(p==2 || p==5) {
        rep(i,n) if((s[n-1-i]-'0')%p == 0) ans += n-i; 
        cout << ans << endl;
        return 0;   
    }
    ll cur = 0;
    ll fac = 1;
    map<ll,ll> mp;
    mp[0] = 1;
    rep(i,n) {
        cur += (s[n-1-i]-'0')*fac;
        cur = cur%p;
        mp[cur]++;
        fac = fac*10%p;
    }
    rep(i,p) ans += mp[i]*(mp[i]-1)/2;
    cout << ans << endl;
}
    




Measured memory_bytes: 4056
#include <stdio.h>

int main(){
  int x, y, z;

  scanf("%d%d",&x,&y);

  if(x < y){
    z = x;
    x = y;
    y = z;
  }
  
  for(z = x % y ; z != 0 ; z = x % y){
    x = y;
    y = z;
  }

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

  return 0;

}



Measured memory_bytes: 2140
import sys
n=int(input())
if n==2:
  print(1)
  sys.exit()
l=[n]
for i in range(2,int(n**0.5)+1):
  if n%i==0:
    l.append(i)
l=list(set(l))
L=[]
for j in range(len(l)):
  x=n
  k=l[j]
  while x%k==0:
    x=x//k
  if x%k==1:
    L.append(l[j])

l2=[n-1]
for i in range(2,int((n-1)**0.5)+1):
  if (n-1)%i==0:
    l2.append(i)
    l2.append((n-1)//i)
l2=list(set(l2))
l2.sort()

print(len(L+l2))

Measured memory_bytes: 40428
import sys
sys.setrecursionlimit(200000)
n,k = map(int,input().split())
a = list(map(int,input().split()))
ans = 0
if a[0] != 1:
  a[0] = 1
  ans += 1
b = [[]for i in range(n)]
for i in range(1,n):
  b[a[i]-1].append(i)
huka = 0
kyo = [float("inf")] * n
z =[[]for i in range(n)]
def dfs(x,y):
  kyo[x] = y
  z[y].append(x)
  for i in b[x]:
    dfs(i,y+1)
dfs(0,0)
def dfs2(x,y):
  if kyo[x] <=k-y:
    return
  if y == k-1 and x != 0:
    kyo[x] = 0
    global ans
    ans += 1
    return
  kyo[x] = 0
  dfs2(a[x]-1,y+1)
for i in range(n-1,k,-1):
  for j in z[i]:
    dfs2(j,0)
print(ans)

Measured memory_bytes: 126032
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef vector<pair<int, int> > vpii;
typedef pair<int, int> pii;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
typedef vector<ll> vll;
#define INF 0x3f3f3f3f
#define MOD 1000000007LL
#define INV  500000004LL
#define EPSILON 0.00001
#define f first
#define s second
#define pb push_back
#define mp make_pair
 
#define FOR(i, a, b) for (ll i=(a); i<=(signed)(b); i++)
#define F0R(i, a) for (ll i=0; i<(signed)(a); i++)
#define RFOR(i, a, b) for (int i=(a); i >= b; i--)

#define MN 200005
int n, k;
int p[MN];
set<int> hmph;

int okst[MN];
int oknd[MN];
int stks[MN];

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

    cin >> n >> k;
    F0R(i, n){
        cin >> p[i];
        if(i < k){
            hmph.insert(p[i]);
        }
    }
    FOR(i, k, n-1){
        int st = i-k;
        if(*hmph.begin() == p[st]){
            okst[st] = true;
            //cout << st << " okst\n";
        }
        hmph.erase(p[st]); hmph.insert(p[i]);
        if(*--hmph.end() == p[i]){
            oknd[i] = true;
            //cout << i << " oknd\n";
        }
    }
    stks[0] = 1;
    FOR(i, 1, n-1){
        if(p[i] > p[i-1]) stks[i] = stks[i-1]+1;
        else stks[i] = 1;
    }

    int ans = 1;
    bool bruh = false;
    if(stks[k-1] >= k){
        ans = 0;
        bruh = true;
    }
    FOR(i, 1, n-k){
        if(stks[i+k-1] >= k){
            bruh = true;
        } else if(okst[i-1]&&oknd[i+k-1]){

        } else{
            ++ans;
        }
    }
    if(bruh) ++ans;
    
    cout << ans << "\n";

    return 0;
}


Measured memory_bytes: 11264
n, m, X, Y = map(int, input().split())
x = list(map(int, input().split()))
y = list(map(int, input().split()))

flag = 0

x.sort()
y.sort()

if X >= Y:
    flag = 1
else:
    flag = 1
    for i in range(X+1, Y+1):
        if x[n-1] < i and i <= y[0]:
            flag = 0
            break


if flag:
    print("War")
else:
    print("No War")


Measured memory_bytes: 3064
N,M=input().split()
N,M=int(N),int(M)
A=input().split()
A=[int(n) for n in A]

BC=[[0]*2]*M
for i in range(M):
    b,c=input().split()
    BC[i]=[int(b),int(c)]

BC.sort(key=lambda x:x[1],reverse=True)
A.sort(reverse=True)
#print(A)

sum=0
itr1=0
itr2=0
count=0
while(count<N):
    if itr2<len(BC) and A[itr1]<BC[itr2][1]:
        for _ in range(BC[itr2][0]):
            sum+=BC[itr2][1]
            #print(sum)
            count+=1
            if count>=N:
                break
            i+=1
        itr2+=1

    else:
        sum+=A[itr1]
        itr1+=1
        #print(sum)
        count+=1
        i+=1

print(sum)

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

using namespace std;

int main() {
    int k, a, b;
    cin >> k >> a >> b;
    bool c = false;

    for (; a <= b; a++) {
        if (a % k == 0) {
            c = true;
            break;
        }
    }

    if (c) {
        cout << "OK" << endl;
    } else {
        cout << "NG" << endl;
    }

    return 0;
}


Measured memory_bytes: 3632
def resolve():
    from collections import deque
    n, Q = [int(i) for i in input().split()]
    ans = [deque() for _ in range(n)]
    for _ in range(Q):
        q = [int(i) for i in input().split()]
        if q[0] == 0:
            ans[q[1]].append(q[2])
        elif q[0] == 1:
            print(*ans[q[1]])
        else:
            ans[q[1]].clear()


resolve()



Measured memory_bytes: 30972
// ABC163B - Homework

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

int main() {
	int N, M;
	cin >> N >> M;
	int sum = 0;
	for (int i = 0; i < M; i++) {
		int t;
		cin >> t;
		sum += t;
	}

	if (sum <= N) {
		cout << N - sum << endl;
	} else {
		cout << -1 << endl;
	}

	return 0;
}


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

#define rep(i, n) for(int i=0; i < n; i++)
#define reps(i, n) for(int i=1; i <= n; i++)
#define INF 1e9
#define ALL(v) v.begin(), v.end()

using namespace std;
using ll=long long;

long mod=1e9+7;


int main() {
  int n;cin>>n;
  vector<int> p(n);
  int sum=0;
  rep(i,n){cin>>p[i];sum+=p[i];}
  int av1=sum/n;
  int av2=sum/n+1;
  int ans1=0,ans2=0;
  rep(i,n){
    ans1+=(av1-p[i])*(av1-p[i]);
    ans2+=(av2-p[i])*(av2-p[i]);
  }
  cout<<min(ans1,ans2);
}



Measured memory_bytes: 256
import copy


def main():
    # n: 頂点数
    # w: 辺の数
    n, w = map(int, input().split())
    # v -> v ; cost: 0
    d = [[False] * n for i in range(n)]

    # d[u][v] : 辺u-vのコスト(if not: inf)
    e = []
    for i in range(w):
        # edge: u -> v ; cost : z
        u, v = map(lambda x: int(x) - 1, input().split())
        e.append([u, v])
        # 無向グラフを想定
        d[u][v] = True
        d[v][u] = True

    def dfs(graph, visited, x):
        if visited[x]:
            return
        visited[x] = True
        for i in range(n):
            if graph[x][i]:
                dfs(graph, visited, i)

    ans = 0
    for (u, v) in e:
        graph = copy.deepcopy(d)
        graph[u][v] = False
        graph[v][u] = False
        for i in range(n):
            visited = [False for _ in range(n)]
            dfs(graph, visited, i)
            if not all(visited):
                ans += 1
                break
    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 3552
#include<bits/stdc++.h>
using namespace std;
#define ALL(x) x.begin(),x.end()
#define rep(i,n) for(int i=0;i<(n);i++)
#define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl;
#define INF 1000000000
#define mod 1000000007
using ll=long long;
const ll LINF=1001002003004005006ll;
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
// ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}
template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return true;}return false;}

signed main(){
    cin.tie(0);
    ios::sync_with_stdio(0);
    
    string s;cin>>s;
    if(s=="ARC") cout<<"ABC"<<endl;
    else cout<<"ARC"<<endl;
    return 0;
}


Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;
using ll=long long;

int main() {
  string s, t; cin>>s>>t;
  int N=s.size();
  int M=t.size();
  vector<char> S(N);
  vector<char> T(M);
  for(int i=0; i<N; i++) S[i]=s[i];
  for(int i=0; i<M; i++) T[i]=t[i];
  sort(S.begin(), S.end());
  sort(T.begin(), T.end());
  reverse(T.begin(), T.end());
  string X;
  string Y;
  for(int i=0; i<N; i++) X+=S[i]; //sの小さい方
  for(int i=0; i<M; i++) Y+=T[i];
  if(X<Y) cout<<"Yes"<<endl;
  else cout<<"No"<<endl;
}
  


Measured memory_bytes: 256
import statistics
import math
n,l = map(int,input().split())	
t = []
for i in range(l,n+l):
	t.append(i)

if 0 in t:
	print(sum(t))
else:
	if t[0] <0:
		t.pop()
		print(sum(t))

	else:
		t.pop(0)
		#print(t)
		print(sum(t))

Measured memory_bytes: 5148