akhauriyash/Code-Regression huggingface dataset:
//?¢??????????????????????????????£??????????????¨?????°???????????°?°????
#include<iostream>
using namespace std;

int N;
int n[200], d[200];

class Pos {
public:
	int x, y;
	bool known;
	Pos() {known = false;}
	Pos(int x, int y) {
		this->x = x;
		this->y = y;
		known = true;
	}
	Pos operator+(const Pos &r) {
		return Pos(x + r.x, y + r.y);
	}
}pos[200];

int main() {
	int i, j;
	while (cin >> N) {
		if (!N) {
			break;
		}
		for (i = 0; i < N-1; i++) {
			cin >> n[i] >> d[i];
		}
		pos[0] = Pos(0, 0);
		
		int dy[4] = {0, 1, 0, -1};
		int dx[4] = {-1, 0, 1, 0};
		for (i = 0; i < N-1; i++) {
			for (j = 0; j < N-1; j++) {
				if (!pos[j+1].known && pos[n[j]].known) {
					pos[j+1] = pos[n[j]] + Pos(dx[d[j]], dy[d[j]]);
					//cout << j+1 << " " << pos[j+1].x << " " << pos[j+1].y << endl;
				}
			}
		}
		
		int INF = 50000;
		int xmin = INF, xmax = -INF, ymin = INF, ymax = -INF;
		for (i = 0; i < N; i++) {
			xmin = min(xmin, pos[i].x);
			xmax = max(xmax, pos[i].x);
			ymin = min(ymin, pos[i].y);
			ymax = max(ymax, pos[i].y);
			pos[i].known = false;
		}
		cout << (xmax - xmin + 1) << " " << (ymax - ymin +1) << endl;
	}
	return 0;
}

Measured memory_bytes: 1164
#include <bits/stdc++.h>
#include <array>
using namespace std;
using ULL = unsigned long long;
using UL = unsigned;
using LL = long long;
#define rep(i, n) for(UL i = 0; i < (n); i++)

struct Problem {

	void Solve() {
		string S; cin >> S;
		if (S.size() != 26) {
			bool f[26] = {};
			rep(i, S.size()) { f[S[i] - 'a'] = true; }
			rep(i, 26) { if (!f[i]) { S.push_back('a' + i); cout << S << endl; return; } }
		}
		char c = 'a' - 1;
		bool f[26] = {};
		while(S.size()) {
			if (S.back() < c) {
				for (int i = 25; i > S.back() - 'a'; i--) { if (f[i]) { c = 'a' + i; } }
				S.back() = c;
				cout << S << endl; return;
			}
			c = S.back();
			f[c - 'a'] = true;
			S.pop_back();
		}
		cout << -1 << endl;
	}


	Problem();
};
int main() {
	unique_ptr<Problem> p(new Problem());
	p->Solve();
	return 0;
}
Problem::Problem() {
	cout << fixed << setprecision(10);
}

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

int main()
{
  int k,n;
  cin>>k>>n;
  int arr[n];
  int sum=0;
  for(int i=0;i<n;i++)
  {
  	cin>>arr[i];
  	sum+=arr[i];
  }
  string ans="No";
  if(sum>=k)
  {
  	ans="Yes";
  }
  cout<<ans<<endl;
  
}

Measured memory_bytes: 640
#include <iostream>
#include <vector>
#include <tuple>
#include <fstream>
#include <stdio.h>
#include <algorithm>
#include <string>
#include <cmath>
#include <functional>
using namespace std;


int main() {

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

  int k, a, b;
  cin >> k >> b >> a;

  int tb = b / k + 1;

  if (b%k == 0) {
    cout << "OK" << endl;
  } else if (tb * k <= a) {
    cout << "OK" << endl;
  } else {
    cout << "NG" << endl;
  }

}


Measured memory_bytes: 3624
def Q3(lst):
    import numpy as np
    N = len(lst)
    lst = np.array(lst)
    num4 = len(lst[np.where(lst % 4 == 0)])  # 4の倍数の個数
    num2 = len(lst[np.where((lst % 4 != 0) & (lst % 2 == 0))])  # 4の倍数でない2の倍数
    numOther = len(lst[np.where((lst % 4 != 0) & (lst % 2 != 0))])

    if num2 == 0:
        if numOther <= num4 + 1:
            return 'Yes'
        else:
            return 'No'
    else:
        if numOther <= num4:
            return 'Yes'
        else:
            return 'No'

n = int(input())
l = [int(i) for i in input().split()] 
print(Q3(l))

Measured memory_bytes: 18824
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <functional>
#include <map>
#include <iomanip>
#include <math.h> 
#include <stack>
#include <queue>
#include <bitset>
#include <cstdlib>
#include <tuple>
#include <cctype>
#include <ctype.h>
#include <set>
#include <sstream>
#include <time.h>
using namespace std;
//#define int long long
#define rep(i,s,n) for(int i = s;i<n;i++)
#define repe(i,s,n) for(int i = s;i<=n;i++)
#define rrep(i,s,n) for(int i = (n)-1;i>=(s);i--)
#define all(v) (v).begin(),(v).end()
#define pb push_back
#define fi first
#define se second
#define chmin(a,b) a=min((a),(b))
#define chmax(a,b) a=max((a),(b))
#define l1 list[index]
#define l2 list[index - 1]
#define l3 list[index + 1]
#define iif(i,j) ((i<0 && j<0) || (i>0 && j>0)) ? true : false 
typedef long long ll;
typedef pair<int, int>pint;
typedef vector<int>vint;
typedef vector<pint>vpint;
typedef pair<pint, int> P1;
typedef pair<int, pint> P2;
typedef pair<pint, pint> PP;
static const ll maxLL = (ll)1 << 62;
const ll MOD = 1000000007;
const ll INF = 1e18;
const double PI = 3.14159265359;
int ca[12] = { 31,28,31,30,31,30,31,31,30,31,30,31 };


signed main() {
	int n, k;
	vector<int>list;
	int maxn = 0;

	for (int i = 0; i < 3; i++) {
		int num;
		cin >> num;
		list.push_back(num);
	}

	sort(list.begin(), list.end());

	cout << list[0] + list[1] << endl;


	getchar();
	getchar();
	return 0;
}

Measured memory_bytes: 256
import sys
input = sys.stdin.readline
class BIT:
    """
    Binary Index Tree
    ###1-origin####

    add :L[i]+=x
    sum: sum(L[:l])
    range_sum : sum(L[l:r])

    #material http://hos.ac/slides/20140319_bit.pdf
    """

    def __init__(self, N, init_val=0):
        self.init_val = init_val
        self.size = N
        self.L = [init_val]*(N+1)

    def sum(self, r):
        """
        sum[,r)
        calc sum from L[0] to L[r-1]
        """
        ret = self.init_val
        while r > 0:
            ret += self.L[r]
            r -= r & (-r)

        return ret

    def range_sum(self, l, r):
        
        """
        idx周りが怪しい?
        sum[l,r)
        calc sum from L[l] to L[r-1]
        """
        return self.sum(r-1)-self.sum(l-1)

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

    def bisect(self,k:float)->int:
        """ binary search on BIT
        get index x s.t self.sum(,)>=k

        RETURN:
            res:index of x
        """
        k+=1 #convert k into 1-index

        res=0
        N=1
        while N<self.size:
            N*=2

        i=N//2
        while i>0:
            if(res+i<self.size and self.L[res+i]<k): #move to rignt on tree
                k-=self.L[res+i]
                res+=i
            #else move to left
            i//=2
        return res+1



N,Q = map(int,input().split())
C=list(map(int,input().split()))
pos=[]
for i in range(Q):
    l,r = map(int,input().split())
    pos.append([l,r,i])


pos=sorted(pos,key=lambda x:x[1])

last_appeared=[0]*(N+1)

B = BIT(N,0)

ans=[-1]*Q

cur_r=1
for l,r,i in pos:
    while cur_r<=r:
        last = last_appeared[C[cur_r-1]]
        if last==0:#first add
            B.add(cur_r,1)
        else:
            B.add(last,-1)
            B.add(cur_r,1)

        last_appeared[C[cur_r-1]]=cur_r #lastの更新
        cur_r+=1

    assert l>=1
    ans[i]=B.sum(r)-B.sum(l-1)


print("\n".join(map(str,ans)))


Measured memory_bytes: 226392
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;

typedef long long ll;

int main(){

	int N;
	cin >> N;
	int status = 0;
	std::vector<ll> A(N);
	int count =0;
	for (int i = 0; i < N; i++)
	{
		cin >> A[i];
	}

	while(status == 0){
		for (int i = 0; i < N; i++)
		{
			if(A[i] % 2 == 1){
				status = 1;
				break;
			}
			A[i] = A[i]/2;
		}
		count += 1;
	}
	cout << count-1 << endl;
	return 0;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
    public static void Main()
    {
        string[] input = Console.ReadLine().Split();
        int H = int.Parse(input[0]);
        int A = int.Parse(input[1]);
        int ans = 0;
        if (H % A == 0) ans = H / A;
        else { ans = H / A + 1; }
        Console.WriteLine(ans);
    }
}

Measured memory_bytes: 13140
#include <iostream>
using namespace std;
long a[1<<17],n,k,i,j,x,c,res;
main(){
  cin>>n>>k;
  for(i=0;i<n;++i)cin>>a[i];
  for(i=40;i>=0;--i){
    c=0;
    for(j=0;j<n;++j)c+=(a[j]>>i)&1;
    if(2*c<n&&(x|(1L<<i))<=k)x|=1L<<i;
  }
  res;
  for(i=0;i<n;++i)res+=x^a[i];
  cout<<res<<endl;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define ll long long
template <typename T>
bool PN(T x){ if (x <= 1) return false; if (x == 2) return true; for (int i = 2; i < sqrt(x) + 1; i++) if (x % i == 0) return false; return true;}
const ll MOD = 1e9+7;
long long Comb(int n, int i){long long ans = 1; if(i>n || i < 0) return 0; if(i == 0 || i == n) return 1; else {for(int j = 1; j <= i; ++j){
      ans *=(n+1-j);
      ans /= j;
      ans %= MOD;} }return ans;}


void solve(){
    ll a; cin >> a;
    string s; cin >> s;
    ll b = stol(s.erase(s.size()-3, 1));
    ll ans = a * b;
    cout << ans /100 << endl;

}

int main(void){
    solve();
    return 0;
}


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

int main(void)
{
    int w, n;
    char c;
    int data[30][2];
    cin >> w >> n;
    for (int i = 0; i < n; ++i)
        cin >> data[i][0] >> c >>  data[i][1];

    for (int i = 1; i <= w; ++i) {
        int num = i;
        for (int j = n - 1; 0 <= j; --j) {
            if (data[j][0] == num)
                num = data[j][1];
            else if (data[j][1] == num)
                num = data[j][0];
        }
        cout << num << endl;
    }

    return 0;
}


Measured memory_bytes: 3060
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <climits>
#include <vector>
#include <map>
#include <set>
#include <list>
#include <stack>
#include <queue>
#include <algorithm>
#include <iostream>
#include <string>

#define REP(i,n) for(long long i=0;i<n;++i)
#define REPR(i,n) for(long long i=n;i>=0;--i)
#define REPI(itr,v) for(auto itr=v.begin();itr!=v.end();++itr)
#define REPIR(itr,v) for(auto itr=v.rbegin();itr!=v.rend();++itr)
#define FOR(i,a,b) for(long long i=a;i<b;++i)
#define SORT(v,n) sort(v, v+n)
#define SORTV(v) sort(v.begin(), v.end())
#define ALL(v) v.begin(),v.end()
#define llong long long
#define INF 999999999
#define SUR 1000000007
#define pb push_back
#define pf push_front
#define MP make_pair
#define SV(v) {for(long long sitr=0;sitr<v.size();++sitr){cin>>v[sitr];}}

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

using namespace std;

typedef pair<int,int> pii;

#define MAX 250000
bool prime[MAX];

int main(){

  REP(i,MAX){
    prime[i] = true;
  }
  prime[0] = false;
  prime[1] = false;

  for(int i = 2; i * i < MAX; ++i){
    if(prime[i]){
      for(int j = 2; i * j < MAX; ++j){
        prime[i*j] = false;
      }
    }
  }
  

  while(true){
    int n;
    cin >> n;
    
    if(n == 0) break;

    int ans = 0;
    for(int i = n+1; i <= 2 * n; ++i){
      if(prime[i]) ans++;
    }
    cout << ans << endl;
  }
  return 0;
}




Measured memory_bytes: 3324
a=int(input())
if a<10:
  print(a)
if 10<=a<100:
  print(9)
if 100<=a<1000:
  print(9+a-99)
if 1000<=a<10000:
  print(909)
if 10000<=a<100000:
  print(909+a-9999)
if a==100000:
  print(90909)

Measured memory_bytes: 9060
#include<bits/stdc++.h>
// Begin Header {{{
#define all(x) (x).begin(), (x).end()
#define lli long long int
#define rep(i,n) for(lli i=0; i<n; i++)
#define loop(i, j, n) for(lli i=j; i<n; i++)
#define Max(a, b) ((a) > (b) ? (a) : (b))
#define Min(a, b) ((a) < (b) ? (a) : (b))
constexpr int INF  = 0x3f3f3f3f;
const long long mod=1e9+7;
const double PI = acos(-1);
//Function
lli combi(lli n, lli r)
{
	if(r==0 || r==n) return 1;
	else return combi(n-1,r) + combi(n-1,r-1);
}
lli sigma1(lli n){return n*(n+1)/2;}
lli sigma2(lli s, lli n){return sigma1(n) - sigma1(s -1);}
using namespace std;
// }}} End Header

int main()
{
	double a, b, h, m;
	cin >> a >> b >> h >> m;
	double gosa  = (m/60.0)*30.0;
	double kakudo = (double)abs(30*h+gosa - 6*m);
	double sita = (kakudo / 180.000)*PI;
	double ans = sqrt(a*a+b*b-2*a*b*cos(sita));
	cout << fixed << setprecision(15) << ans << endl;
	return 0;
}


Measured memory_bytes: 4184
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;
using ll = long long;

int main(){
    ll n;
    cin >> n;
    vector<ll> a(n);
    for(ll i=0;i<n;i++) cin >> a[i];
    sort(a.begin(),a.end());
    for(ll j=a[1];;j--){
        if(a[0]%j==0||a[1]%j==0){
            int cnt=0;
            bool flag=true;
            for(ll i=0;i<n;i++){
                if(a[i]%j!=0){
                    cnt++;
                    if(cnt>=2){
                        flag=false;
                        break;
                    }
                }
            }
            if(flag==true){
                cout << j << endl;
                return 0;
            }
        }
    }
    return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector> 
#include <cstring>
#include <queue>
#include <ctime>
#include <set>
#include <map>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,int> pli;
const ll INF = 10e16;
const int maxN = 310;
char a[maxN*2][maxN*2]; 
int b[maxN*2][maxN*2];

int main()
{
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%s",a[i]+1);
	}
	
	for(int i = n+1; i <= 2*n;i++)
	{
		for(int j = n+1;j<=2*n;j++)
		{
			a[i][j] = a[i-n][j-n];
		}
	}
	for(int i = n+1; i <= 2*n;i++)
	{
		for(int j = 1;j<=n;j++)
		{
			a[i][j] = a[i-n][j];
		}
	}
	for(int i = 1; i <= n;i++)
	{
		for(int j = n+1;j<=2*n;j++)
		{
			a[i][j] = a[i][j-n];
		}
	}
	for(int i = 2*n;i>=1;i--)
	{
		for(int j = 2*n;j>=1;j--)
		{
			int cnt = 1;
			int x = i;
			int y = j;
			while((y-cnt >= 1) && (x-cnt >=1))
			{
				if(a[x][y-cnt] == a[x-cnt][y])
					cnt++;
				else
					break;
			}
			b[i][j] = cnt-1;
		} 
	}
	int ans = 0;
	for(int i = 2*n-1;i>=1;i--)
	{
		for(int j = 2*n-1;j>=1;j--)
		{
			int flag = 0;
			for(int k=0;k<n;k++)
			{
				if(b[i-k][j-k] < (n-(k+1)))
				{
					flag = 1;
					break;
				}
			}
			if (flag == 0)
				ans ++;
		}
	}
	printf("%d\n",ans);

	return 0;
}

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

int main(){
  int H ,W , K;
  cin >> H >> W >> K;
  
  vector<string>S(H);
  rep(i,H) cin >> S[i];
  int ans = 0;
  rep(is,1<<H)rep(js,1<<W) {
    int cnt = 0;
    rep(i,H)rep(j,W) {
      if(is>>i&1)continue;
      if(js>>j&1)continue;
      if(S[i][j] == '#')cnt++;
    }
    if(cnt == K)ans++;
  }
  cout << ans << endl;
  
}

Measured memory_bytes: 3628
#include"stdio.h"
#include"iostream"
#include"vector"

#define V_MAX 50
using namespace std;

long long w[10000], N, W,M,a[51],b[51], rec,ans;
bool use_v[V_MAX], use_e[V_MAX+1][V_MAX];
long long max(long long x, long long y){
	if (x > y)return x;
	return y;

}

int min(int x, int y){
	if (x > y)return y;
	return x;
}

void dfs(int v){
	use_v[v] = true;
	for (int i = 0; i < N; i++){
		if (use_e[v][i]){
			if (!use_v[i]){
				dfs(i);
			}
		}
	}
	return;
}


int main(){
	cin >> N >> M;
	for (int i = 0; i <= N; i++){
		use_v[i]=false;
	}
	for (int i = 0; i < M; i++){
		cin >> a[i] >> b[i];
		a[i]--;
		b[i]--;
		use_e[a[i]][b[i]]=use_e[b[i]][a[i]]=true;
	}
	ans = 0;
	for (int k = 0; k < M; k++){
		use_e[a[k]][b[k]] = use_e[b[k]][a[k]] = false;
		for (int j = 0; j < N; j++) use_v[j] = false;
		dfs(0);
		for (int j = 0; j < N; j++){
			if (!use_v[j]){
				ans++;
				break;
			}
		}
		use_e[a[k]][b[k]] = use_e[b[k]][a[k]] = true;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#pragma GCC optimization ("Ofast")
#pragma GCC optimization ("unroll-loops")
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=1;i<n;i++)
#define rev(i,n) for(int i=n-1;i>=0;i--)
#define all(v) v.begin(),v.end()
#define P pair<int,int>
#define len(s) (int)s.size()
 
template<class T> inline bool chmin(T &a, T b){
	if(a>b){a=b;return true;}
	return false;
}
template<class T> inline bool chmax(T &a, T b){
	if(a<b){a=b;return true;}
	return false;
}
constexpr int mod = 1e9+7;
constexpr long long inf = 3e18;

int N;
int A[200005],B[200005];
signed main(){
	cin.tie(0);ios::sync_with_stdio(false);
	cin>>N;
	rep(i,N)cin>>A[i];
	rep(i,N)cin>>B[i];
	reverse(B,B+N);
	int cur=0;
	while(cur<N){
		int i=cur;
		while(A[i]==B[i])i++;
		if(i-cur>N/2){
			cout<<"No\n";return 0;
		}
		if(i==cur){
			cur++;continue;
		}
		int now=0,now2=cur;
		while(now<N&&now2<i){
			if(now==cur)now=i;
			if(B[now]==B[now2]){now++;continue;}
			if(A[now]==B[now2]){now++;continue;}
			swap(B[now++],B[now2++]);
		}
		if(now2!=i){
			cout<<"No\n";return 0;
		}
		break;
	}
	cout<<"Yes\n";
	rep(i,N)cout<<B[i]<<" ";
	cout<<"\n";
}

Measured memory_bytes: 6768
#include <cstdio>
#include <cstring>

using namespace std;
const int maxn = 1000000000;
struct node
{
    int wy;
    int by;
    char name[20];
}e[1005];

int main()
{
    int n = 0, q = 0;
    int num = 0;
    while (scanf("%d%d", &n, &q) == 2)
    {
        if (n == 0 & q == 0) break;
        for (int i=0; i<n; i++) scanf("%s%d%d", e[i].name, &e[i].by, &e[i].wy);
        while (q--)
        {
            scanf("%d", &num);
            int min = maxn, ans = 0, count = 0;
            for (int i=0; i<n; i++)
            {
                ans = e[i].wy-num;
                if (ans >= 0 && ans <= min)
                {
                    min = ans;
                    count = i;
                }
            }
            ans = e[count].by-min;
            if (ans>0) printf("%s %d\n", e[count].name, ans);
            else printf("Unknown\n");
        }
    }
    return 0;
}

Measured memory_bytes: 1072
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
#include <queue>

using namespace std;

typedef long long ll;
typedef pair<int, int> P;

int main(){
    int N, K;
    cin >> N >> K;
    
    ll res = 0;
    for(int b = 1; b <= N; ++b){
        int t1 = N / b;
        int t2 = N % b;
        res += t1 * max(0, b - K) + max(0, t2 - K + 1);
    }
    if(K == 0)      res -= N;
    
    cout << res << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
 int main() {
   int a,b;
   cin>>a>>b;
   if(b==1) {
     cout<<0;
     return 0;
   }
   else {
   int sum=a,k=1;
   while(sum<b) {
     sum+=a-1;
     ++k;
   }
     cout<<k;
     return 0;
   }
}

Measured memory_bytes: 256
n=input()
x=[]
for i in range(len(n)):
    x.append(int(n[i]))
if x[0]>=x[1] and x[0]>=x[2]:
    for i in range(3):
        print(x[0], end='')
else:
    for i in range(3):
        print(x[0]+1, end='')

Measured memory_bytes: 3060
#include <bits//stdc++.h>
using namespace std;
int in(void){int x;cin>>x;return x;}
#define rep(i,a,b) for(int i=int(a);i<int(b);i++)
#define ll long long int
long long int dx[4]={1,0,-1,0};
long long int dy[4]={0,1,0,-1};
int D[2]={1,-1};
int main() {
  int x;
  cin>>x;
  int num[10000000];
  int check;
  int main=0;
  rep(i,0,x){
    cin>>check;
    if(num[check]==1)main++;
    num[check]=1;
  }
  cout<<x-main;
return 0;
}


Measured memory_bytes: 2304
#include<bits/stdc++.h>
using namespace std;
#define  ft  ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define  ll  long long
const int N=2e5+2;
ll a[N];
int main()
{
    ft
    ll t,i,j,n,m,x,s=0;
    cin>>n;
    for(i=0;i<n;i++)
    {
        cin>>a[i];
        a[i]-=(i+1);
    }
    sort(a,a+n);
    x=a[n/2];
    for(i=0;i<n;i++)
    {
        s+=abs(a[i]-x);
    }
    cout<<s<<"\n";
    return 0;
}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
#define F first
#define S second
#define pb push_back
using namespace std;
const int maxn=434567;
const int M=1000000007;
typedef long long ll;
typedef pair<int,ll> pi;
void add(ll &x,ll y){x+=y;if(x>=M)x-=M;}
int n,h,p[maxn];
vector<pi> v[2];
ll ans,cnt[2][maxn];
void ins(int x,ll val,int o){
    while (x){
        val=val*x%M;
        add(cnt[o][x],val);
        x>>=1;
    }
}
ll dfs2(int x){
    if (!cnt[0][x]||!cnt[1][x]) return 0;
    ll ret=(cnt[0][x*2]*cnt[1][x*2+1]+cnt[1][x*2]*cnt[0][x*2+1])%M*x%M;
    add(ret,dfs2(x*2));
    add(ret,dfs2(x*2+1));
    return ret;
}
void dfs(int x,ll val,int o){
    val=val*x%M;
    if (x>=n){
        v[o].pb((pi){p[x-n]+n,val});
        return;
    }
    dfs(x*2,val,o);
    dfs(x*2+1,val,o);
}
ll solve(int x){
    v[0].clear(); v[1].clear();
    dfs(x*2,1,0);
    dfs(x*2+1,1,1);
    for (auto x:v[0]) ins(x.F,x.S,0);
    for (auto x:v[1]) ins(x.F,x.S,1);
    ll ret=dfs2(1);
    for (auto x:v[0]) ins(x.F,M-x.S,0);
    for (auto x:v[1]) ins(x.F,M-x.S,1);
    return ret;
}
int main(){
    cin >> h; n=1<<(h-1);
    for (int i=0;i<n;i++){
        cin >> p[i];
        p[i]--;
    }
    for (int i=1;i<n;i++) ans=(ans+solve(i)*i)%M;
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 10132
t = int(input())

def calc(x):
    if x not in dp:
        divs = [5, 3, 2]
        costs = [c, b, a]
        values = lambda div, cost: [calc((x + i) // div) + cost + (sign * x) % div * d for i, sign in [(0, 1), (div - 1, -1)]]
        dp[x] = min(*[value for div, cost in zip(divs, costs) for value in values(div, cost)], x * d)
    return dp[x]

for _ in range(t):
    n, a, b, c, d = map(int, input().split())
    dp = {0: 0, 1: d}
    print(calc(n))


Measured memory_bytes: 85400
#include<bits/stdc++.h>
#define Fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define pi acos(-1)
typedef long long ll;
using namespace std;

int main()
{
    Fast;
    ll n,m,i,j,k,ans;
    string s;
    cin>>s;
    for(int i=0;i<s.size();i++)
    {
        if(s[i]=='7')
        {
            cout<<"Yes"<<endl;
            return 0;
        }
    }
    cout<<"No"<<endl;
}


Measured memory_bytes: 3656
def vacation(n, cost):
    res = [[0]*3 for i in range(n)]
    for i in range(3):
        res[0][i] = cost[0][i]
    for d in range(1, n):
        for a in range(3):
            res[d][a] = cost[d][a]
            for pa in range(3):
                if pa != a:
                    res[d][a] = max(res[d][a], res[d-1][pa]+cost[d][a])
    return max(res[-1])

def main():
    n = int(input())
    cost = [[0, 0, 0]]*n
    for i in range(n):
        cost[i] = list(map(int, input().split()))

    print(vacation(n, cost))

if __name__ == "__main__":
    main()

Measured memory_bytes: 47368
import java.util.*;
public class Main {
	public static void main(String[] args) {
		Scanner stdIn = new Scanner(System.in);
		int n = stdIn.nextInt();
		int[] a = new int[n];
		
		double sum = 0;
		for(int i = 0; i < n; i++){
			a[i] = stdIn.nextInt();
			sum += 1.0/a[i];
		}
		System.out.println(1/sum);
		
		
		
	}

}


Measured memory_bytes: 21844
#include <iostream>
#include <map>
#define MOD 1000000007

using namespace std;
using ll = long long;

int n;
map<int,int> res;

ll ans = 1;
void prime_factor(int n){
    for(int i = 2; i * i <= n; i++){
        while(n % i == 0){
            ++res[i];
            n /= i;
        }
    }
    if(n != 1) res[n]++;
}

int main(){
    cin >> n;
    for(int j = 2; j <= n;j++){
        prime_factor(j);
    }

    for(auto e:res){
        ans = ans * (e.second + 1) % MOD;
    }

    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
h,w = map(int,input().split())
s = [list(input()) for _ in range(h)]
dp = [[h*w]*w for _ in range(h)]
if s[0][0] == "#":
  dp[0][0] = 1
else:
  dp[0][0] = 0
for i in range(h):
  for j in range(w):
    if i < h-1:
      if s[i][j]=="." and s[i+1][j]=="#":
        dp[i+1][j] = min(dp[i+1][j],dp[i][j]+1)
      else:
        dp[i+1][j] = min(dp[i+1][j],dp[i][j])
    if j < w-1:
      if s[i][j]=="." and s[i][j+1]=="#":
        dp[i][j+1] = min(dp[i][j+1],dp[i][j]+1)
      else:
        dp[i][j+1] = min(dp[i][j+1],dp[i][j])
print(dp[h-1][w-1])

Measured memory_bytes: 3188
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>


using namespace std;
using namespace __gnu_pbds;


#define LL long long
#define N 100005
#define MOD 1000000007
#define dd double
#define rep(i, n) for(int i = 0; i < n; i++)
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep1(i,b) for(int i=1;i<=b;i++)
#define pb push_back
#define mp make_pair
#define clr(x) x.clear()
#define sz(x) ((int)(x).size())
#define F first
#define S second
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>ordered_set;

int main() {

ios_base::sync_with_stdio(false);
cin.tie(NULL);
	
	int t=1;
	//cin>>t;
	while(t--){
		unsigned long long a,b,c;
		cin>>a>>b>>c;
		if(a+b>c)
			{
				cout<<"No";
				return 0;
	}
		unsigned long long  x = c-(a+b);
		unsigned  long long  y= a*b;
		y*=4;
		if(y<x*x)
			cout<<"Yes";
		else
			cout<<"No";
	}



return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#define _USE_MATH_DEFINES
#include <math.h>
#include <iomanip>
#include <stdio.h>
#include <numeric>
#include <cmath>
#include <limits>
#include <bitset> 
#include <iterator> 
#include <map>
#include <queue>
#include <set>
#define rep(i,n) for(ll i=0;i<(n); ++i)
#define log(i,n) log(n)/log(i);
using namespace std;
typedef long long ll;


int main()
{
	ll cnt0 = 0,cnt1 = 0;
	string s;
	cin >> s;
	cnt0 = count(s.begin(), s.end(), '0');
	cnt1 = count(s.begin(), s.end(), '1');
	cout << min(cnt0,cnt1) * 2 << endl;
}



Measured memory_bytes: 512
from collections import deque
n,m = map(int,input().split())

graph = [[] for _ in range(n)]

for _ in range(m):
    a,b = map(int,input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
    
#部屋から1までの距離(深さ)
dist = [-100 for _ in range(n)]
dist[0] = 0

#幅優先探索でdistを更新
#pに今いる位置を格納
p = deque()
p.append(0)

while len(p) > 0:
    now = p.pop()
    for i in graph[now]:
        if dist[i] != -100:
            continue
        p.appendleft(i)
        dist[i] = now
        
print('Yes')
for i in range(1,n):
    print(dist[i]+1)

Measured memory_bytes: 34208
####################
####################
####################
####################
from heapq import*
i=input
for s in[0]*int(i()):
 n,x,*y=int(i()),[]
 for _ in'_'*n:k,l,r=t=[*map(int,i().split())];x+=[t]*(l>=r);y+=[[n-k,r,l]]*(l<r)
 for x in x,y:
  x.sort();h=[]
  for k,l,r in x:
   if k:s+=l;heappush(h,l-r)
   else:s+=r
   if len(h)>k:s-=heappop(h)
 print(s)

Measured memory_bytes: 50624
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

ans = 0
for bi in range(n-1, -1, -1):
    for ai in [bi+1, bi]:
        temp = a[ai] if a[ai] <= b[bi] else b[bi]
        ans += temp
        b[bi] -= temp
        a[ai] -= temp

print(ans)

Measured memory_bytes: 18476
#include <bits/stdc++.h>
#include "unistd.h"
using namespace std;
#define FOR(i,a,b) for(int i=(a),i##formax=(b);i<i##formax;i++)
#define FORR(i,a,b) for(int i=(a),i##formax=(b);i>=i##formax;i--)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define pcnt __builtin_popcount
#define sz(x) (int)(x).size()
#define maxs(x,y) x=max(x,y)
#define mins(x,y) x=min(x,y)
#define show(x) cout<<#x<<" = "<<x<<endl;
#define all(a) (a.begin()),(a.end())
#define each(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)
#define perm(c) sort(all(c));for(bool c##p=1;c##p;c##p=next_permutation(all(c)))
#define bitComb(a,n,k) for(int a##x,a##y,a=(1<<k)-1;a<(1<<n);a##x=a&-a,a##y=a+a##x,a=(((a&~a##y)/a##x)>>1)|a##y)
#define bit(n) (1LL<<(n))
#define randInt(l,r) (uniform_int_distribution<ll>(l,r)(rnd))
#define randDouble(l,r) (uniform_real_distribution<double>(l,r)(rnd))
#define dout(d) printf("%.12f\n",d)

typedef long long ll;
typedef __int128_t lll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
template<class T>using V=vector<T>;
template<class T>using VV=V<V<T>>;
template<class T,class Y>ostream& operator<<(ostream&o,const pair<T,Y>&p){return o<<"("<<p.fi<<","<<p.se<<")";}
template<class T>ostream& operator<<(ostream&o,V<T>&v){for(T&t:v)o<<t<<",";return o<<endl;}
template<typename A,size_t N,typename T>void Fill(A (&array)[N],const T&v){fill((T*)array,(T*)(array+N),v);}
template<typename T>void uniq(V<T>&v){sort(all(v));v.erase(unique(all(v)), v.end());}
lll gcd(lll a,lll b,lll &x,lll &y){if(!b){x=1;y=0;return a;}lll d=gcd(b,a%b,y,x);y-=a/b*x;return d;}
ll modInv(ll a,ll m){lll x,y;gcd(a,m,x,y);return (x%m+m)%m;}
ll modPow(lll a,lll n,ll m){if(!a)return a;lll p=1;for(;n>0;n>>=1,a=a*a%m)if(n&1)p=p*a%m;return(ll)p;}
bool isPrime(ll n){if(n<2||n%2==0)return n==2;lll t=n-1,d=t/(t&-t);for(lll a:{2,325,9375,28178,450775,9780504,1795265022})if(a%n){for(t=d,a=modPow(a,t,n);t!=n-1&&a!=1&&a!=n-1;a=a*a%n,t=t*2%n);if(a!=n-1&&t%2==0)return 0;}return 1;}
//V<ll>fac,rfac;void setFac(int n,int mod){fac=rfac=V<ll>(++n);fac[0]=1;FOR(i,1,n)fac[i]=fac[i-1]*i%mod;rfac[n-1]=modInv(fac[n-1],mod);FORR(i,n-1,1)rfac[i-1]=rfac[i]*i%mod;}
const int IINF = 1e9+6;
const ll LINF = 1e18;
const int MOD = 1e9+7;
const double PI = acos(-1);
const double EPS = 1e-10;
static random_device rd;
static mt19937 rnd(rd());

void RE(){cout<<1/0;}
void TLE(){sleep(100);}
void WA(){cout<<char(0);exit(0);}

const int N = 1e5;
int n, m;
priority_queue<int> q;
main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cin >> n >> m;
  FOR(i, 0, n){
    int a;
    cin >> a;
    q.push(a);
  }
  FOR(_, 0, m){
    int a = q.top(); q.pop();
    q.push(a>>1);
  }
  ll ans = 0;
  while(!q.empty()){
    ans += q.top();
    q.pop();
  }
  cout << ans << endl;
}

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

int main(){
  int i;
  int num, ans=1000;
  string S;
  cin >> S;
  for(i=0;i<S.size()-2;i++){
    num = 100* (S[i]-'0') + 10* (S[i+1]-'0') + (S[i+2]-'0');
    ans = min(ans, abs(num - 753));
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int N = Integer.parseInt(sc.next());
        int[] Bi = new int[N-1];
        for (int i = 0; i < N-1; i++) {

            Bi[i] = Integer.parseInt(sc.next());
        }
        sc.close();

        //最大値は10^5*101なのでintで十分かと
        int ans = 0;

        ans += Bi[0] + Bi[N-2];

        for (int i = 1; i < N-1; i++) {

            ans += Math.min(Bi[i-1], Bi[i]);
        }

        System.out.println(ans);
    }
}

Measured memory_bytes: 22612
#include<bits/stdc++.h>
using namespace std;
int min(int a,int b)
{
    if(a<b)
        return a;
    else 
        return b;
}
int main()
{   int n,k;
    cin>>n>>k;
    int arr[n],mini,mino;
    int i,j;
    for(i=0;i<n;i++)
        cin>>arr[i];
    int dp[n];
    for(i=0;i<n;i++)
    {
        if(i==0)
            {
                dp[i]=0;
                
            }
        else if(i==1)
        {
            dp[i]=abs(arr[i]-arr[i-1]);
        }
        else
        {   for(j=1;j<=k;j++)
            {   if(j>i)
                    break;
                mini=dp[i-j]+abs(arr[i]-arr[i-j]);
                if(j==1)
                mino=mini;
                if(mini<mino)
                mino=mini;
            }
            dp[i]=mino;
        }
    }
    cout<<dp[n-1];
    return 0;
}

Measured memory_bytes: 1152
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
//#define ll 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 (a>b) { a=b; return 1; } return 0; }
#define rep(i, n) REP(i, 0, n)
#define rep_rev(i, n) for (int (i) = (int)(n) - 1 ; (i) >= 0 ; --(i))
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for(int i = x; i < n; i++)
#define all(x) (x).begin(),(x).end()
ll t1,t2,t3;
const ll mod = 998244353;
const int INF = 1e9;
const ll INFLONG = 1e18;

int main(){
  ll n;
  cin >> n;
  n--;
  ll keta = 1;
  t1 = n;
  t2 = 26;
  while(t1 >= t2){
    t1 -= t2;
    keta++;
    t2 *= 26;
  }
  string s;
  rep(i,keta){
    s += 'a';
  }
  //cout << s << " " << t1 << endl;
  rep_rev(i,keta){
    t2 = t1 % 26;
    t1 /= 26;
    s[i] += t2;
  }
  cout << s << endl;
}

Measured memory_bytes: 3628
#include <iostream>
#include <string>
#include <vector>
#include <stdio.h>
#include <algorithm>
#define _USE_MATH_DEFINES
#include <cmath>
#include <numeric>
#include <iomanip>
#include <deque>
#include <tuple>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <sstream>
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/multiprecision/cpp_dec_float.hpp>

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define all(x) (x).begin(), (x).end()
#define F first
#define S second
#define pb push_back
#define pf push_front

namespace mp = boost::multiprecision;
using cpp_int = mp::cpp_int;
using ll = long long;
using namespace std;

ll M = 1000000007;
template <class T>
void print(const T &value)
{
	std::cout << value << std::endl;
}
int GCD(int x, int y)
{
	return x ? GCD(y % x, x) : y;
}
ll p[51],a[51];
ll f(ll n, ll x){
	if(n==0){
		if(x<=0)return 0;
		else return 1;
	}else if(x<=1+a[n-1]){
		return f(n-1,x-1);
	}else{
		return p[n-1]+1+f(n-1,x-2-a[n-1]);
	}
}
int main()
{
	ll n ,x;
	cin>>n>>x;
	p[0]=1;
	a[0]=1;
	FOR(i,1,51){
		p[i]=(ll)p[i-1]*2+1;
		a[i]=(ll)a[i-1]*2+3;
	}

	cout<<f(n,x)<<endl;
}


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

int main(void) {
  int a, b, c, i, j = 0;
  cin >> a >> b >> c;

  for(i=a;i<=b;i++) {
    if(c%i==0)
    j++;
  }
  cout << j << endl;
  return 0;
}


Measured memory_bytes: 3092
#define _USE_MATH_DEFINES
#include<iostream>
#include<string>
#include<queue>
#include<cmath>
#include<map>
#include<set>
#include<list>
#include<iomanip>
#include<vector>
#include<random>
#include<functional>
#include<algorithm>
#include<stack>
#include<cstdio>
#include<bitset>
#include<unordered_map>
#include<climits>
#include<fstream>
using namespace std;
///////////////////library zone!!!!!!!!!!!!!!!!!!!!!!!!!!!!
typedef long long ll;
typedef long double ld;
#define all(a) (a).begin(),(a).end()
const ll Mod = 1000000007;
const ll mod = 998244353;
struct H {
	ll x, y;
	bool operator<(const H &b) const {
		if (x != b.x) return x < b.x;
		return y < b.y;
	}
	bool operator>(const H &b) const {
		if (x != b.x) return x > b.x;
		return y > b.y;
	}
	bool operator==(const H &b) const { return x == b.x&&y == b.y; }
	bool operator!=(const H &b) const { return (*this) != b; }
};
struct P {
	ll pos, cost;
	bool operator<(const P &b) const { return cost < b.cost; }
	bool operator>(const P &b) const { return cost > b.cost; }
};
struct B {
	ll to, cost;
};
struct E {
	ll from, to, cost;
	bool operator<(const E &b) const { return cost < b.cost; }
	bool operator>(const E &b) const { return cost > b.cost; }
};
template<typename T, typename U>
void chmin(T &a, U b) {
	if (a > b) a = b;
}
template<typename T, typename U>
void chmax(T &a, U b) {
	if (a < b) a = b;
}
template<typename T>
T max_0(T a) {
	if (a < 0) return 0;
	return a;
}
template<typename T>
T min_0(T a) {
	if (a > 0) return 0;
	return a;
}
ll read() {
	ll u;
	ll k = scanf("%lld", &u);
	return u;
}
ll gcd(ll i, ll j) {
	if (i > j) swap(i, j);
	if (i == 0) return j;
	return gcd(j%i, i);
}
ll mod_pow(ll x, ll n, ll p) {
	ll res = 1;
	while (n > 0) {
		if (n & 1) res = res * x % p;
		x = x * x % p;
		n >>= 1;
	}
	return res;
}//x^n%p
const ll Inf = 3023372036854775807;
const int inf = 1500000000;
#define int long long
//----------------------------------------------------
string s, p;
signed main() {
	cin >> s >> p;
	for (int i = 0; i < s.size(); i++) {
		string h = "";
		for (int j = 0; j < p.size(); j++) {
			h += s[(i + j) % s.size()];
		}
		if (h == p) {
			cout << "Yes\n";
			return 0;
		}
	}
	cout << "No\n";
}


Measured memory_bytes: 3208
N = int(input())
F = 0
ans = 10 ** 10
i = 1
while i * i <= N:
  A = i
  if N % A == 0:
    B = N // A
    F = max(len(str(A)), len(str(B)))
    ans = min(ans, F)
  i += 1 
print(ans)

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

int main() {
	
  long n,W;
  cin>>n;
  cin>>W;
  long val[n],wt[n],dp[n][W+1];
  for(long i=0;i<n;i++){
    cin>>wt[i];
    
    cin>>val[i];}
  for(long i=0;i<n;i++){
    for(long w=0;w<=W;w++){
      if(w==0) dp[i][w]=0;
      else if(i==0){
        if (wt[0]<=w) dp[i][w]=val[i];
        else dp[i][w]=0;
      }
      else{
      dp[i][w]=(wt[i]<=w)? max(dp[i-1][w],val[i]+dp[i-1][w-wt[i]]) : dp[i-1][w];
      }
    }
  }
  cout<<dp[n-1][W];
}

Measured memory_bytes: 78336
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
	ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int N,X,T,t=0,n; cin>>N>>X>>T;
    n=N;
    while(n!=0)
    {
    	if(n-X<0){
        	n=0;t+=T;}
     	else if(n-X>=0){
        	n=n-X;t+=T;}
    }
  	cout<<t;
}

Measured memory_bytes: 3648
unittest
{
	assert( [ "3", "2 3 1" ].parse.expand.solve == 5 );
	assert( [ "5", "1 2 3 4 5" ].parse.expand.solve == 30 );
	assert( [ "8", "8 2 7 3 4 5 6 1" ].parse.expand.solve == 136 );
}



import std.container;
import std.conv;
import std.range;
import std.stdio;
import std.typecons;

void main()
{
	stdin.byLineCopy.parse.expand.solve.writeln;
}

auto parse( Range )( Range input )
if( isInputRange!Range && is( ElementType!Range == string ) )
{
	input.popFront;
	auto ps = input.front.split.to!( long[] );
	return tuple( ps );
}

auto solve( long[] ps )
{
	// 添字と中身を逆にした配列を作成
	auto pis = new long[ 1 + ps.length ];
	pis[ 0 ] = long.min;
	foreach( i, p; ps )
	{
		pis[ p ] = i;
	}
	
	// 大きい順で処理
	auto ans = 0L;
	auto rbt = redBlackTree( -1L, pis.back, ps.length.signed );		// pより大きい値の添字をrbtに入れて二分検索できるようにする
	pis.popBack;
	for( auto p = pis.length.signed - 1; 0 < p; p-- )
	{
		// pより大きい値が1つだけ含まれる範囲を検索して、p×範囲のパターン数を計算
		auto pi = pis.back;
		pis.popBack;
		
		auto lis = rbt.lowerBound( pi ).retro.take( 2 ).array;
		auto ris = rbt.upperBound( pi ).take( 2 ).array;
		if( 1 < lis.length ) ans += p * ( ris[ 0 ] - pi       ) * ( lis[ 0 ] - lis[ 1 ] );
		if( 1 < ris.length ) ans += p * ( ris[ 1 ] - ris[ 0 ] ) * ( pi       - lis[ 0 ] );
		rbt.insert( pi );
	}
	return ans;
}


Measured memory_bytes: 23752
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//typedef pair<ll, ll> P;
typedef pair<int, int> i_i;

#define reps(i,s,n) for(int i = s; i < n; i++)
#define rep(i,n) reps(i,0,n)
#define REP(i,n) reps(i,0,n)
#define ALL(v) v.begin(), v.end()
#define SZ(x) ((int)(x).size())

const double PI  = acos(-1.0);
const double EPS = 1e-9;
const ll INF = 1e9+10;
const ll mod = 1e9+7;
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; }
#define print(x) cerr << #x << " is " << x << endl;
//#define print(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl; 

int main() {
    int N, P;
    string S;
    cin >> N >> P;
    cin >> S;
    reverse(ALL(S));

    ll ans = 0;
    if (P == 2 || P == 5){
        rep(i, N){
            if ((S[i] - '0') % P == 0){
                ans += N - i;
            }
        }
        cout << ans;
        return 0;
    }
    int kmod;
    int lower = 0;
    map<int, int> m;
    m[0]++;
    rep(i, N){
        if (i == 0){
            kmod = 1;
        } else {
            kmod = (kmod * 10)%P;
        }
        lower = (lower+ (S[i] - '0') *  kmod)%P;
        ans += m[lower];
        m[lower]++;
    }
    cout << ans;
    return 0;
}


Measured memory_bytes: 900
#include <iostream>
#include <cassert>

using namespace std;

const int L = 1;
const int W = 2;
const int D = 0;

int fnK(int& cnt_a, int& cnt_b, string a, string b)
{
  assert(a[0] == 'k');
  if (b[0] == 'k') {
    if (cnt_a == cnt_b) {
      cnt_a = cnt_b;
      return D;
    }
    if (cnt_a == 0) {      
      return L;
    }
    if (cnt_b == 0) {
      return W;
    }
    return cnt_a > cnt_b ? W : L;
  }
  if (b[0] == 't') {
    ++cnt_b;
    return cnt_a ? W : L;
    
  }
  if (b[0] == 'm') {
    if (cnt_a == 5) return W;
    return cnt_a ? D : L;
  }
  assert(false);
}

int fnM(int& cnt_a, int& cnt_b, string a, string b)
{
  assert(a[0] == 'm');
  if (b[0] == 'k') {
    if (cnt_b == 5) return L;
    if (cnt_b == 0) return W;
    return D;
  }
  if (b[0] == 't') {
    ++cnt_b;
    return D;
  }
  if (b[0] == 'm') {
    return D;
  }
  assert(false);
}

int fnT(int& cnt_a, int& cnt_b, string a, string b)
{
  assert(a[0] == 't');
  if (b[0] == 'k') {
    if (cnt_b) return L;
    if (cnt_b == 0) return W;
    return W;
  }
  if (b[0] == 'm') {
    ++cnt_a;
    return D;
  }
  if (b[0] == 't') {
    ++cnt_a;
    ++cnt_b;
    return D;
  }
  assert(false);
}

int main(void)
{
  int n;
  while (cin >> n) {
    string a[n];
    string b[n];
    for (int i = 0;i < n; ++i) {
      cin >> a[i];
    }
    for (int i = 0;i < n; ++i) {
      cin >> b[i];
    }
    int cnt_a = 0;
    int cnt_b = 0;
    int f = 0;
    for (int i = 0; i < n && !f; ++i) {
      // cout << cnt_a << ' ' << a[i] << endl;
      // cout << cnt_b << ' ' << b[i] << endl;
      if (a[i][0] == 'k') {
	f = fnK(cnt_a, cnt_b, a[i], b[i]);
      }
      if (a[i][0] == 't') {
	f = fnT(cnt_a, cnt_b, a[i], b[i]);
      }
      if (a[i][0] == 'm') {
	f = fnM(cnt_a, cnt_b, a[i], b[i]);
      }
      
      if (a[i][0] == 'k') cnt_a = 0;
      if (b[i][0] == 'k') cnt_b = 0;
      // if (!f) cout << "turn " << i << " is end" << endl;
    }
    switch (f) {
    case 0:
      cout << "Hikiwake-kun" << endl;
      // cerr << "Hikiwake-kun" << endl;
      break;
    case 1:
      cout << "Nakajima-kun" << endl;
      // cerr << "Nakajima-kun" << endl;
      break;
    case 2:
      cout << "Isono-kun" << endl;
      // cerr << "Isono-kun" << endl;
      break;
    }
    // cout << endl;
  }
  return 0;
}

Measured memory_bytes: 1220
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,k,n) for(int i = (k); i < (n); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(a) a.begin(), a.end()
#define MS(m,v) memset(m,v,sizeof(m))
#define D10 fixed<<setprecision(10)
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int, int> pii;
const int MOD = 1000000007;
const int INF = MOD + 1;
const ld EPS = 1e-12;
template<class T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<class T> T &chmax(T &a, const T &b) { return a = max(a, b); }

/*--------------------template--------------------*/

int solve(string s, string t)
{
	if (s == t) return 0;
	int p = INF;
	REP(i, s.size())
	{
		if (s[i] != t[i])
		{
			chmin(p, i);
		}
	}
	int r = t[p] - s[p];
	int res = INF;
	FOR(i, 1, s.size() - p + 1)
	{
		string u = s;
		REP(j, i)
		{
			u[p + j] += r;
			if (u[p + j] > '9') u[p + j] -= 10;
			if (u[p + j] < '0') u[p + j] += 10;
		}
		chmin(res, solve(u, t) + 1);
	}
	return res;
}

int main()
{
	int n;
	while (cin >> n, n)
	{
		string s, t; cin >> s >> t;
		cout << solve(s, t) << endl;
	}
	return 0;
}

Measured memory_bytes: 3160
N, W = map(int, input().split())
w, v = [0]*N, [0]*N
for i in range(N):
    w[i], v[i] = map(int,input().split())
Vmax = max(v)*N+1
Wmax = max(w)*N+1
dp = [[Wmax] * (Vmax) for _ in range(N + 1)]
ans = int(0)
dp[0][0] = int(0)

for i in range(N):
    for j in range(Vmax):
        if j-v[i]>=0:
            dp[i+1][j] = min(dp[i][j-v[i]]+w[i],dp[i+1][j])
        dp[i+1][j] = min(dp[i+1][j],dp[i][j])

for j in range(Vmax):
    if 0<=dp[N][j]<=W:
        ans = max(ans,j)

print(ans)

Measured memory_bytes: 120940
k = int(input())
aaa = [0] * k
aaa[0] = 7 % k
for i in range(1, k):
    aaa[i] = (aaa[i - 1] * 10 + 7) % k
ans = -1
for j in range(k):
    if aaa[j] == 0:
        ans = j + 1
        break
print(ans)


Measured memory_bytes: 48444
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
from math import floor, sqrt, factorial, hypot, log  # log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter, defaultdict, deque
from itertools import accumulate, permutations, combinations, product, combinations_with_replacement
from bisect import bisect_left, bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint


def ceil(a, b): return (a + b - 1) // b


inf = float('inf')
mod = 10 ** 9 + 7


def pprint(*A):
    for a in A:     print(*a, sep='\n')


def INT_(n): return int(n) - 1


def MI(): return map(int, input().split())


def MF(): return map(float, input().split())


def MI_(): return map(INT_, input().split())


def LI(): return list(MI())


def LI_(): return [int(x) - 1 for x in input().split()]


def LF(): return list(MF())


def LIN(n: int): return [I() for _ in range(n)]


def LLIN(n: int): return [LI() for _ in range(n)]


def LLIN_(n: int): return [LI_() for _ in range(n)]


def LLI(): return [list(map(int, l.split())) for l in input()]


def I(): return int(input())


def F(): return float(input())


def ST(): return input().replace('\n', '')


def main():
    N, M, K = MI()
    A = LI()
    B = LI()
    ans = 0
    total = 0
    anow = -1
    for a in A:
        if a + total <= K:
            ans += 1
            total += a
            anow += 1
        else:
            break
    maxans = ans
    for b in B:
        total += b
        isOver = False
        while total > K:
            if anow == -1:
                isOver = True
                break
            total -= A[anow]
            anow -= 1
            ans -= 1
        if isOver:
            break
        ans += 1
        maxans = max(maxans, ans)
    print(maxans)

if __name__ == '__main__':
    main()

Measured memory_bytes: 120712
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef pair<P,ll> Pll;
typedef pair<P,P> PP;
#define rep(i,a,n) for(ll i = a;i < n;i++)
#define repr(i,a,n) for(ll i = n-1;i >= a;i--)
#define LINF (ll)1e17
#define INF (int)1e9
#define MOD (ll)1e9+7
#define sMOD 1e5
#define fs first
#define sc second

ll gcd(ll a,ll b){
	if(!b) return a;
	return gcd(b,a%b);
	
}

void YNout(bool check){
	if(check)cout << "Yes" << endl;
	else cout << "No" << endl;
	
	return;
}

void Yayout(bool check){
	if(check) cout << "Yay!" << endl;
	else cout << ":(" << endl;
	
	return;
}

/*
template <typename T>
void vecout(vector<T>& vecout_vec){
	
	rep(i,0,vecout_vec.size()){
		cout << vecout_vec.at(i) << endl;
	}
	
	return ;
}

template <typename T>
void vecin(vector<T>& vecin_vec, ll n){
	
	ll temp ;
	
	rep(i,0,n){
		cin >> temp;
		vecin_vec.push_back(temp);
		
	}
}

template <typename T>
void in(T& literal_in, T& literal_in2, ...){
	cin >> literal_in;
	in(literal_in2, ...);
	
	return;
}

template <typename T>
void in(T& literal_in){
	
	cin >> literal_in;
	
	return;
}

template <typename T>
void out(T& literal_out, T& literal_out2, ...){
	cout << literal_out << endl;
	out(literal_out2, ...);
	
	return;
}

template <typename T>
void out(T& literal_out){
	
	cout << literal_out << endl;
	
	return;
}
*/
signed main(){
	ll A[3];
	
	cin >> A[0] >> A[1] >> A[2];
	
	sort(A,A+3);
	
	cout << A[0] + A[1] << endl;
	
	
	
	return 0;
}


Measured memory_bytes: 764
#include <bits/stdc++.h>
#define rep(i, a, n) for(int i = a; i < n; i++)
#define repb(i, a, b) for(int i = a; i >= b; i--)
#define all(a) a.begin(), a.end()
#define o(a) cout << a << endl
#define int long long
#define fi first
#define se second
using namespace std;
typedef pair<int, int> P;

signed main(){
    int n, m, a;
    while(1){
        cin >> n >> m >> a;
        if(n + m + a == 0) break;
        vector<int> d(n);
        a--;
        rep(i, 0, n) d[i] = i;
        vector<pair<int, P> > e(m); 
        rep(i, 0, m){
            int h, p, q;
            cin >> h >> p >> q;
            p--; q--;            
            e[i].first = h;
            e[i].second.first = p;
            e[i].second.second = q;
        }
        sort(all(e));
        rep(i, 0, m){
            swap(d[e[i].second.first], d[e[i].second.second]);
        }
        cout << d[a] + 1 << endl;
    }
}

Measured memory_bytes: 2988
ac=0
wa=0
tle=0
re=0
for _ in range(int(input())):
  a=input()
  if(a=="AC"):
   	ac+=1
  elif(a=="WA"):
    wa+=1
  elif(a=="TLE"):
    tle+=1
  else:
    re+=1
print("AC x",ac)
print("WA x",wa)
print("TLE x",tle)
print("RE x",re)

Measured memory_bytes: 9064
import java.util.Arrays;
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int[] arr = new int[3];
		arr[0] = sc.nextInt();
		arr[1] = sc.nextInt();
		arr[2] = sc.nextInt();
		Arrays.sort(arr);
		System.out.println(((arr[2] * 10) + arr[1]) + arr[0]);
	}
}

Measured memory_bytes: 23764