akhauriyash/Code-Regression huggingface dataset:
var N = 0
var A = 0

fun main(args: Array<String>) {
    readLine()?.split(" ")?.map {
        it.toInt()
    }?.let {
        N = it[0]
        A = it[1]
    }


    val x = Array(N + 1) { 0 }
    readLine()?.split(" ")?.map {
        it.toInt()
    }?.forEachIndexed { i, n ->
        x[i + 1] = n
    }

    val dp = Array(N + 1) {
        Array(N + 1) {
            Array(N * A + 1) { 0L }
        }
    }
    for (i in 0..N) {
        dp[i][0][0] = 1
    }

    for (i in 1..N) {
        for (j in 1..i) {
            for (k in 1..(N * A)) {
                dp[i][j][k] = if (k < x[i]) {
                    dp[i - 1][j][k]
                } else {
                    dp[i - 1][j][k] + dp[i - 1][j - 1][k - x[i]]
                }
            }
        }
    }

    var ans = 0L
    for (j in 1..N) {
        ans += dp[N][j][j * A]
    }

    println(ans)
}



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

int main() {
int h,w;
int n;
vector <pair<int,int> > p;

scanf("%d%d",&h,&w);
int arr[h][w];
memset(arr,0,sizeof arr);
scanf("%d",&n);
int x;
for(int i=0;i<n;i++){
  scanf("%d",&x);
p.push_back(make_pair(x,i+1));

}
int m=0,cnt=0;
for(int i=0;i<h;i++){
       if(i%2==0){
    for(int j=0;j<w;j++){
        arr[i][j]=p[m].second;
        cnt++;
        if(cnt==p[m].first){
            m++;
            cnt=0;
            }
            //cout<<arr[i][j];
    }
        }
        else{
            for(int j=w-1;j>=0;j--){
          arr[i][j]=p[m].second;
        cnt++;
        if(cnt==p[m].first){
            m++;
            cnt=0;
        }
    }
        }
}
for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            cout<<arr[i][j]<<" ";
        }
        cout<<" "<<endl;

}
	return 0;
}


Measured memory_bytes: 512
#include <iostream>


using namespace std;

int main()
{
int A,B;
scanf("%d%d",&A,&B);
if(A==B){

printf("Draw");
return 0;}
if(A==1)
printf("Alice");
else if(B==1 )
printf("Bob");
else if (B<A)
printf("Alice");
else if (B>A)
printf("Bob");

    return 0;
}

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

using namespace std;

int main()
{
    long long n, m;
    cin >> m >> n;
    long long le = 0, ri = 1e18;
    while (ri - le > 1){
        long long mi = (le + ri) / 2;

        long long mm = max((long long)0, mi - m);
        long long nn = n - mm * 2;
        if (nn >= mi * 2)
            le = mi;
        else
            ri = mi;
    }
    cout << le << '\n';
    return 0;
}


Measured memory_bytes: 384
#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll long long
using namespace std;
typedef long double ld;
#define sp fixed << setprecision(10)

const int MOD=1e9+7;
const int N=3005;
ld dp[N][N];
ld p[N]; 
int check[N];
int n;

/*
ld solve(int l, int x)
{
	ld res = 1;
	if(n - l <= l)
		return 0;
	for (int i = 0; i < n; ++i)
	{
		res *= check[i] ? 1 - p[i] : p[i];
	}
	if(n - l > l)
	{
		for (int i = x; i < n; ++i)
		{
			if(check[i] == 0)
			{	
				check[i] = 1;
				res += solve(l+1, i);
				//cout << res <<"\n";
				check[i] = 0;
			}
		}
	}

	return res;
}

*/

ld solve()
{
	dp[0][0] = 1;
	for (int i = 1; i <= n; ++i)
	{
		for (int j = 0; j <= n; ++j)
		{
			dp[i][j] = (j ? dp[i-1][j-1] * p[i] : 0) + dp[i-1][j]*(1 - p[i]);
		}
	}
	ld res = 0;
	for (int i = 0; i <= n; ++i)
	{
		if (2*i > n)
			res += dp[n][i];
	}
	return res;
}



int main()
{
	IOS;
	cin >> n;
	for (int i = 1; i <= n; ++i)
	{
		cin >> p[i];
	}
	cout << sp << solve();
	return 0;
}


Measured memory_bytes: 141184
#include <iostream>
#include<iomanip>
#include <cmath>
#include <climits>
#include <algorithm>
#include <stdio.h>
#include <vector>
#include <queue>
#include <tuple>
#include <map>
#include <list>
#include <string>
#include <numeric>
#include <utility>
#include <cfloat>
using namespace std;

//long long a[100000];
//long long b[100000];

using namespace std;
 

//int cost[100000][100000];
int main(){
    int n;
    cin >> n;
    if(n == 7 || n == 5 || n == 3){
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;
    }

    return 0;
}

Measured memory_bytes: 256
#include<cstdio>
const int MAXN = 1000000;
const int MOD = int(1E9) + 7;
int pow_mod(int b, int p) {
	int ret = 1;
	while( p ) {
		if( p & 1 ) ret = 1LL*ret*b%MOD;
		b = 1LL*b*b%MOD;
		p >>= 1;
	}
	return ret;
}
int fct[MAXN + 5], ifct[MAXN + 5];
void init() {
	fct[0] = 1;
	for(int i=1;i<=MAXN;i++)
		fct[i] = 1LL*fct[i-1]*i%MOD;
	ifct[MAXN] = pow_mod(fct[MAXN], MOD-2);
	for(int i=MAXN-1;i>=0;i--)
		ifct[i] = 1LL*ifct[i+1]*(i+1)%MOD;
}
int comb(int n, int m) {return 1LL*fct[n]*ifct[m]%MOD*ifct[n-m]%MOD;}
int solve2(int N, int M, int S, int l, int r) {
	int ret = 0;
	if( S - 1LL*M*r < 0 ) return ret;
	else S -= M*r;
	for(int i=0,f=1;i<=N-M&&S>=0;i++,f=1LL*f*(MOD-1)%MOD,S-=l)
		ret = (ret + 1LL*f*comb(S + N, N)%MOD*comb(N - M, i)%MOD)%MOD;
	return 1LL*ret*comb(N, M)%MOD;
}
//A1 + A2 + ... + AN + B = S, A[1...M] >= r, 0 <= A[M+1...N] < l
//A1 + A2 + ... + AN + B = S - M*r, A[1...M] >= 0, 0 <= A[M+1...N] < l
int solve(int N, int M, int S) {
	int ret = comb(S + N, N);
	for(int i=S;i>=1;i--) {
		int del = (solve2(N, M, S, i, i) + MOD - solve2(N, M, S, i, i + 1))%MOD;
		ret = (ret + MOD - del)%MOD;
	}
	return ret;
}
//A1 + A2 + ... + AN + B = S
int main() {
	init(); int N, M, L, R;
	scanf("%d%d%d%d", &N, &M, &L, &R);
	printf("%d\n", (solve(N, M, R) + MOD - solve(N, M, L - 1))%MOD);
}

Measured memory_bytes: 7936
#include<bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int>>;
#define ll long long
#define all(x) (x).begin(),(x).end()
#define rep(i, n) for(ll i = 0; i < n; i++)
const ll INF = 1LL << 60;

int main(){
    int H, W, M; cin >> H >> W >> M;
    unordered_map<int, int> bombh, bombw;
    set<pair<int, int>> st;
    int max1 = 0, max2 = 0;
    rep(i, M){
        int h, w; cin >> h >> w;
        h--;w--;
        st.insert(make_pair(h, w));
        bombh[h]++;
        if(bombh[h] > max1) max1 = bombh[h];
        bombw[w]++;
        if(bombw[w] > max2) max2 = bombw[w];
    }
    // for(auto x: bombh)cout << x.first << x.second << endl;
    // cout << endl;
    // for(auto x:bombw)cout << x.first << x.second << endl;
    
    vector<int> Hkouho, Wkouho;
    for(auto x:bombh){
        if(x.second == max1){
            Hkouho.push_back(x.first);
        }
    }
    for(auto x:bombw){
        if(x.second == max2){
            Wkouho.push_back(x.first);
        }
    }
    // rep(i, Hkouho.size()) cout << Hkouho[i] << " " ;
    // cout << endl;
    // rep(i, Wkouho.size()) cout << Wkouho[i] << " " ;
    // cout << endl;
    int ans = max1 + max2;
    for(auto h: Hkouho){
        for(auto w: Wkouho){
            // bool flag = true;
            // rep(i, M){
            //     if(G[i][0] == h && G[i][1] == w){
            //         flag = false;
            //     }
            // }
            // if(flag == true){
            //     cout << ans << endl;
            //     return 0;
            // }
            pair<int, int> tmp = make_pair(h, w);
            if(st.find(tmp) == st.end()){
                cout << ans << endl;
                return 0;   
            }
        }
    }
    cout << ans - 1 << endl;
}


Measured memory_bytes: 48460
#include<bits/stdc++.h>
#define endl '\n'
#define INF (1 << 21)
const int MOD = 1000000009;
using namespace std;

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n;
  int x[2], y[2], z[2], w[2];
  int ax, ay, az, aw;

  cin >> n;
  while(n != 0){
    for(int i = 0;i < n;i++){
      cin >> x[0] >> y[0] >> z[0] >> w[0];
      cin >> x[1] >> y[1] >> z[1] >> w[1];

      ax = x[0] * x[1] + (-1) * y[0] * y[1] + (-1) * z[0] * z[1] + (-1) * w[0] * w[1];
      
      ay = x[0] * y[1] + y[0] * x[1] + z[0] * w[1] + (-1) * w[0] * z[1];

      az = x[0] * z[1] + (-1) * y[0] * w[1] + z[0] * x[1] + w[0] * y[1];

      aw = x[0] * w[1] + y[0] * z[1] + (-1) * z[0] * y[1] + w[0] * x[1];
      
      cout << ax << ' ' << ay << ' ' << az << ' ' << aw << endl;
    }
    cin >> n;
  }
  return 0;
}




Measured memory_bytes: 3220
fun main(args: Array<String>) {
    fun read() = readLine()!!.split(" ").map(String::toInt)
    val (n, m) = read()
    var s = (1..m).map { it }.toSet()
    repeat(n) { s = s.intersect(read().drop(1)) }
    print(s.size)
}

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

int main() {
	int n,k;
	cin>>n>>k;
	int a[n+1];
	for(int i=0;i<n;i++){
	    cin>>a[i+1];
	}
    vector<int> dp(k+1);
    for(int i=0;i<=k;i++){
        dp[i]=0;
    }
	for(int i=0;i<=k;i++){
	    for(int j=1;j<=n;j++){
	        if(i-a[j]>=0&&dp[i-a[j]]==0){
	            dp[i]=1;
	        }
	    }
	   // for(int j=0;j<=k;j++){
	   //     cout<<dp[j]<<" ";
	   // }
	   // cout<<"\n";
	}
	if(dp[k]==1){
	    cout<<"First\n";
	}else{
	    cout<<"Second\n";
	}
	return 0;
}


Measured memory_bytes: 640
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<iomanip>
#include<iostream>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<vector>
#define rep(i,x,y) for(register int i=(x);i<=(y);++i)
#define dwn(i,x,y) for(register int i=(x);i>=(y);--i)
#define view(u,k) for(int k=fir[u];~k;k=nxt[k])
#define LL long long
#define maxn 200007
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)&&ch!='-')ch=getchar();
    if(ch=='-')f=-1,ch=getchar();
    while(isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
    return x*f;
}
void write(int x)
{
    if(x==0){putchar('0'),putchar('\n');return;}
    int f=0;char ch[20];
    if(x<0)putchar('-'),x=-x;
    while(x)ch[++f]=x%10+'0',x/=10;
    while(f)putchar(ch[f--]);
    putchar('\n');
    return;
}
int n,p[maxn],q[maxn],hd=1,tl,in[maxn],a[maxn];
vector<int >son[maxn];
int main()
{
    n=read();
    rep(i,1,n){p[i]=read();in[p[i]]++;}
    rep(i,1,n)if(!in[i]){q[++tl]=i;}
    while(hd<=tl)
    {
    	int u=q[hd++],li=son[u].size(),now=-1,pos=-1;sort(son[u].begin(),son[u].end());
		while(pos+1<li&&son[u][pos+1]-now<=1)pos++,now=son[u][pos];a[u]=now+1;
    	in[p[u]]--,son[p[u]].push_back(a[u]);
    	if(!in[p[u]])q[++tl]=p[u];
    }
    int nd=0,num=0;
    rep(i,1,n)if(in[i])
    {
    	int li=son[i].size(),now=-1,pos=-1;sort(son[i].begin(),son[i].end());
		while(pos+1<li&&son[i][pos+1]-now<=1)pos++,now=son[i][pos];a[i]=now+1;
		//cout<<i<<" "<<now<<endl;
    	num++;
    }
    rep(i,1,n)if(in[i]&&a[p[i]]<a[i]){nd=p[i];break;}
    //rep(i,1,n)cout<<a[i]<<" ";cout<<endl;
    //cout<<nd<<endl;
    if(!nd)
    {
    	if(!(num&1))puts("POSSIBLE");
    	else puts("IMPOSSIBLE");
    }
    else
    {
    	puts("POSSIBLE");
    }
    return 0;
}

Measured memory_bytes: 11136
s = input()
t = input()
q = int(input())
sl,tl = len(s),len(t)
sa,sb,ta,tb = [0]*(sl+1),[0]*(sl+1),[0]*(tl+1),[0]*(tl+1)
for i in range(sl):
	if s[i]=="A": sa[i+1],sb[i+1] = sa[i]+1,sb[i]
	else: sa[i+1],sb[i+1] = sa[i],sb[i]+1
for i in range(tl):
	if t[i]=="A": ta[i+1],tb[i+1] = ta[i]+1,tb[i]
	else: ta[i+1],tb[i+1] = ta[i],tb[i]+1
for _ in range(q):
	a,b,c,d = (int(i) for i in input().split())
	if (sa[b]-sa[a-1]-sb[b]+sb[a-1]-ta[d]+ta[c-1]+tb[d]-tb[c-1])%3: print("NO")
	else: print("YES")

Measured memory_bytes: 15156
#include <stdio.h>
#include <math.h>

int min(int a, int b) {
	if(a > b) return b;
	return a;
}

int max(int a, int b) {
	if(a > b) return a;
	return b;
}

int main() {
	//char buffer[128];
	//scanf("%s", buffer);
	int A, B, X;
	scanf("%d %d %d", &A, &B, &X);
	if(A == X) {
		printf("YES\n");
		return 0;
	}
	if(A > X) {
		printf("NO\n");
		return 0;
	}

	if(X <= A + B) {
		printf("YES\n");
		return 0;
	}

	printf("NO\n");
	return 0;
}


Measured memory_bytes: 128
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int K = sc.nextInt();

        System.out.println(solve(N, K));

        sc.close();
    }

    static double solve(int N, int K) {
        double result = 0;
        for (int i = 1; i <= N; ++i) {
            double p = 1.0 / N;
            int score = i;
            while (score < K) {
                p /= 2;
                score *= 2;
            }

            result += p;
        }

        return result;
    }
}

Measured memory_bytes: 35860
#include <cstdio>
#include <cmath>
#include <iostream>
#include <vector>
#include <string>
#include <utility>
#include <algorithm>
#include <queue>
using namespace std;
#define FOR(i,a,b) for(ll i=a;i<b;i++)
#define REP(i,n) for(ll i=0;i<n;i++)
#define REPR(i,n) for(ll i=n-1;i>=0;i--)

typedef long long ll;
#define INF 1e18

int main(){
	ll n; cin>>n;
	ll k; cin>>k;
	vector<ll> a(n);
	REP(i,n){
		cin>>a[i];
		a[i]--;
	}
	vector<vector<ll>> next(n,vector<ll>(0));
	for(ll i=0;;i++){
		if(pow(2,i)>k)break;
		REP(j,n){
			next[j].push_back(0);
			if(i==0)next[j][i]=a[j];
			else next[j][i]=next[next[j][i-1]][i-1];
		}
	}/*
	REP(i,(signed)next.size()){
		cout<<"next: ";
		REP(j,(signed)next[i].size()){
			cout<<next[i][j]<<" ";
		}
		cout << endl;
	}*/
	ll cur=0;
	for(ll i=0;;i++){
		if(k<=0)break;
		if(k%2==1){
			cur=next[cur][i];
		}
		k/=2;
	}
	cout<<cur+1<<endl;
	return 0;
}
/*

6 727202214173249351
6 5 2 5 3 2

6 3
6 5 2 5 3 2

*/


Measured memory_bytes: 113688
N=int(input())
H=list(map(int,input().split()))
flg=True
for i in range(N-1):
    if H[i]<H[i+1]:
        H[i+1]-=1
    if H[i]>H[i+1]:
        flg=False
        break
print('Yes' if flg else 'No')

Measured memory_bytes: 14396
import java.util.*;
public class Main{
	public static void main (String args[]){
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
        int count = oddCount(N);
        double result = (double)count/N;
      
      	System.out.println(result);
	}
  
  	public static int oddCount(int N){
      ArrayList<Integer> intList = new ArrayList<Integer>();
      for(int i = 1; i<=N; i++){
      	intList.add(i);
      }
      int count = 0;
      for(int aN : intList){
        if (aN%2==1){
          count++;
        }
      }
      return count;
    }
}

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

using namespace std;

string p[] = {"Sunny", "Cloudy", "Rainy"};

int main() {
  string s; cin >> s;
  set <char> p, q;
  for(int i = 0; i < s.length(); i++) {
    if(i & 1) q.insert(s[i]);
    else p.insert(s[i]);
  }
  for(auto x : p) {
    if(x != 'R' and x != 'U' and x != 'D') {
      puts("No");
      return 0;
    }
  }
  for(auto x : q) {
    if(x != 'L' and x != 'U' and x != 'D') {
      puts("No");
      return 0;
    }
  }
  puts("Yes");
}


Measured memory_bytes: 256
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <deque>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <complex>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <numeric>
#include <utility>
#include <iostream>
#include <algorithm>
#include <functional>
#include <unordered_map>
#include <unordered_set>

using namespace std;

#define INF (1 << 30)
#define INFL (1LL << 62)
#define MOD7 1000000007
#define MOD9 1000000009
#define EPS 1e-10

#define ll long long
#define ull unsigned long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pul pair<ull, ull>
#define all(a) (a).begin(), (a).end()
#define FOR(i,a,b) for (int i=(a);i<(b);++i)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);--i)
#define REP(i,n) for (int i=0;i<(n);++i)
#define RREP(i,n) for (int i=(n)-1;i>=0;--i)

void YES() { cout << "YES" << endl; }
void NO() { cout << "NO" << endl; }
void Yes() { cout << "Yes" << endl; }
void No() { cout << "No" << endl; }
void yes() { cout << "yes" << endl; }
void no() { cout << "no" << endl; }
void digit(int d) { cout << fixed << setprecision(d); }
void IOup() { cin.tie(0); ios::sync_with_stdio(false); }

class UnionFind {
	vector<int> data;
public:

	UnionFind(int size = 0) {
		resize(size);
	}
	void resize(int size) {
		data.resize(size, -1);
	}

	int root(int x) {
		return data[x] < 0 ? x : data[x] = root(data[x]);
	}

	void unite(int x, int y) {
		x = root(x);
		y = root(y);
		if (x == y)
			return;

		if (data[y] < data[x])
			swap(x, y);
		data[x] += data[y];
		data[y] = x;
	}

	bool same(int x, int y) {
		return root(x) == root(y);
	}

	int count() {
		int cnt = 0;
		for (int i = 0, n = data.size(); i < n; ++i) {
			if (i == root(i))
				cnt++;
		}
		return cnt;
	}
};

int main() {
	UnionFind uf;
	int n, m, c, x, y;
	cin >> n >> m;
	uf.resize(n);
	while (m--) {
		cin >> c >> x >> y;
		if (c) {
			cout << uf.same(x, y) << endl;
		}
		else {
			uf.unite(x, y);
		}
	}

	return 0;
}

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

template<class Abel> struct UnionFind{
	vector<int> par;
	vector<int> rank;
	vector<Abel> diff_weight;

	UnionFind(int n = 1,Abel SUM_UNITY = 0){
		init(n,SUM_UNITY);
	}

	void init(int n = 1,Abel SUM_UNITY = 0){
		par.resize(n); rank.resize(n);diff_weight.resize(n);
			for(int i=0;i<n;i++){
				par[i] = i;
				rank[i] = 0;
				diff_weight[i] = 0;
			}
		}
		int root(int x){
			if(par[x] == x)return x;
			else{
				int r = root(par[x]);
				diff_weight[x] += diff_weight[par[x]];
				return par[x] = r;
			}
		}

		Abel weight(int x){
			root(x);
			return diff_weight[x];
		}

		bool issame(int x,int y){
			return root(x)==root(y);
		}

		bool merge(int x, int y, Abel w){
			w += weight(x);w -= weight(y);
			x = root(x);y = root(y);
			if(x == y)return false;
			if(rank[x] < rank[y]){
				swap(x,y);
				w = -w;
			}
			if(rank[x] == rank[y])rank[x]++;
			par[y] = x;
			diff_weight[y] = w;
			return true;
		}
		Abel diff(int x,int y){
			return weight(y)-weight(x);
		}
};

int main(void){
	int N,M;
	cin>>N>>M;
	UnionFind<int> tree(N,0);
	for(int i=0;i<M;i++){
		int l,r,d;
		cin>>l>>r>>d;
		l--;r--;
		if(tree.issame(l,r)){
			int diff = tree.diff(l,r);
			if(diff != d){
				cout<<"No"<<endl;
				return 0;
			}
		}
		else
			tree.merge(l,r,d);
	}
	cout<<"Yes"<<endl;
	return 0;
}


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

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())

int gcd(int a, int b){
    if (b == 0) {
        return a;
    }
    return gcd(b, a%b);
}

ll lcm(ll a, ll b){
    return a * b / gcd(a,b);
}

// n を素因数分解
map<ll, ll> factor(ll n){
    map<ll, ll> mp;
    for (ll i = 2; i*i <= n; i++) {
        while (n % i == 0) {
            mp[i]++;
            n /= i;
        }
    }

    if (n > 1) {
        mp[n]++;
    }

    return mp;
}

int iternum(string str, char c){
    int N = str.size();

    map<char, int> mp;
    for (int i = 0; i < N; i++) {
        mp[str[i]]++;
    }

    if ((int)mp.size() == 1) {
        return 0;
    }

    int ans = 0;
    int kindnum = mp.size();
    do {
        for (int i = 0; i < N-ans-1; i++) {
            if (str[i] == c || str[i+1] == c) {
                str[i] = c;
            }
        }

        mp.clear();
        for (int i = 0; i < N-ans-1; i++) {
            mp[str[i]]++;
        }
        kindnum = mp.size();
        ans++;
    } while (kindnum != 1);

    return ans;
}


void solve(){
    string str;
    cin >> str;

    map<char, int> mp;
    int N = str.size();
    for (int i = 0; i < N; i++) {
        mp[str[i]]++;
    }

    vector<char> kouho;
    for (auto itr = mp.begin(); itr != mp.end(); itr++) {
        kouho.push_back(itr->first);
    }

    int ans = 100;
    for (auto item = kouho.begin(); item != kouho.end(); item++) {
        // cout << iternum(str, *item) << endl;
        ans = min(ans, iternum(str, *item));
    }

    cout << ans << endl;

    return;
}

int main(int argc, char const* argv[])
{
    solve();
    return 0;
}


Measured memory_bytes: 256
var GET=(function(){function f(s){return new g(s);}function g(s){this._s=s.trim().split("\n");this._y=0;}g.prototype.a=function(f){var s=this._s, y=this._y, r;if(typeof s[y]==="string")s[y]=s[y].split(" ").reverse();r=s[y].pop();if(!s[y].length)this._y++;return f?r:+r;};g.prototype.l=function(f){var s=this._s[this._y++].split(" ");return f?s:s.map(a=>+a);};g.prototype.m=function(n,f){var r=this._s.slice(this._y,this._y+=n).map(a=>a.split(" "));return f?r:r.map(a=>a.map(a=>+a));};g.prototype.r=function(n,f){var r=this._s.slice(this._y,this._y+=n);return f?r:r.map(a=>+a);};return f;})();
var o=GET(require("fs").readFileSync("/dev/stdin","utf8"));
function xArray(v){var a=arguments,l=a.length,r="Array(a["+--l+"]).fill(0).map(x=>{return "+v+";})";while(--l)r="Array(a["+l+"]).fill(0).map(x=>"+r+")";return eval(r);}
var mod = 998244353;
function abmod(){for(var a=arguments,r=a[0],i=1;i<a.length;)r=((r>>16)*a[i]%mod*65536+(r&65535)*a[i++])%mod;return r;}
function powmod(a,n){for(var r=1;n;a=abmod(a,a),n>>=1)if(n&1)r=abmod(a,r);return r;}

console.log(main());
function main(){
  var n = o.a();
  var a = o.r(n).sort((a,b)=>a-b);
  var x = a.reduce((a,b)=>a+b);
  var dp = [1];
  for(var i = 0; i < n; i++){
    var dp2 = xArray(0,dp.length+a[i]);
    for(var j = 0; j < dp.length; j++){
      dp2[j] += dp[j] * 2;
      dp2[j+a[i]] += dp[j];
      dp2[j] %= mod;
    }
    dp = dp2;
  }
  var ans = powmod(3,n);
  if(x % 2 === 0)ans += solve(a,n,x/2);
  x = x+1 >> 1;
  for(var j = x; j < dp.length; j++){
    ans -= dp[j] * 3;
  }
  ans %= mod;
  return (ans+mod)%mod;
}

function solve(a,n,x){
  var dp = [1];
  for(var i = 0; i < n; i++){
    var dp2 = xArray(0,dp.length+a[i]);
    for(var j = 0; j < dp.length; j++){
      dp2[j] += dp[j];
      dp2[j+a[i]] += dp[j];
      dp2[j] %= mod;
    }
    dp = dp2;
  }
  return dp[x] * 3;
}

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

int main() {
string s,t;
cin >> s >> t;
int cnt = 0;
rep(i,s.size()){
  if(s.at(i) != t.at(i)) cnt++;
}
cout << cnt << endl;
}


Measured memory_bytes: 3852
#include "bits/stdc++.h"

#define sp <<" "
#define el <<"\n"
#define S second
#define F first
#define mp make_pair
#define pb push_back
#define pf push_front
#define pob pop_back
#define obit __builtin_popcount
#define pof pop_front
#define mod (int)1e9 + 7
#define For(i,a,n) for(i=a;i<n;i++)

using namespace std;

typedef long long ll;
typedef unsigned long long ul;
typedef unsigned short int us;
typedef short int ss;
typedef long double ld;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    /*
#ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
#endif
    //*/
    int n,i;
    cin>>n;
    bool vis[n],pos = true; int ar[n];
    For(i,0,n){
        cin>>ar[i]; 
        ar[i]--;
    }
    memset(vis,false,sizeof(vis));
    int st = 0,x = 0;
    while(x != 1){
        if(vis[x]){
         pos = false; break;
        }
        vis[x] = 1;
        x = ar[x];
        st++;
    }
    if(pos) cout<<st;
    else cout<<-1;
    return 0;
}

Measured memory_bytes: 768
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define lvector vector<ll>
#define cvector vector<char>
#define svector vector<string>
#define lque queue<ll>
#define lpque priority_queue<ll>
#define dlpque priority_queue<ll,lvector,greater<ll>>
#define P pair<ll,ll>
#define ALL(a) a.begin(),a.end()
#define RALL(a) a.rbegin(),a.rend()
#define rep(i,n) for(ll i=0; i<n; ++i)
#define print(a) cout << (a) << endl

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  string t;cin>>t;
  ll ans=0,l=t.length();
  rep(i,l) {
    if(t[i]=='?') t[i]='D';
  }
  print(t);
  return 0;
}

Measured memory_bytes: 3740
'use strict'
function main(inp) {
  inp = inp.trim().split('\n')
  const N = Number(inp.shift())
  inp = inp[0].split(' ').map(n => Number(n));
  let temp = 0
  let max = 0

  for (let i = 1; i < N; i++) {
    if (inp[i] > inp[i - 1]) {
      if (temp > max) max = temp
      temp = 0
    } else {
      temp++
    }
  }
  if (temp > max) max = temp

  console.log(max)
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));


Measured memory_bytes: 21064
#include <bits/stdc++.h>
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <deque>
using namespace std;
#define int long long
#define REP(i,n) for(int i = 0;i < (int)(n);i++)
#define FOR(i,s,n) for(int i = s;i < (int)n;i++)
#define RREP(i,n) for(int i = (int)n-1;i >= 0;i--)
#define RFOR(i,s,n) for(int i = (int)n-1;i >= s;i--)
template<class T>inline bool CHMAX(T&a,T b){if(a<b){a = b;return true;}return false;}
template<class T>inline bool CHMIN(T&a,T b){if(a>b){a = b;return true;}return false;}

signed main(){
	int N;
	cin >> N;
	vector<int>d(N);
	REP(i,N)cin>>d[i];
	sort(d.begin(),d.end());
	RFOR(i,1,13){
		int prev = 0;
		vector<int>cnt;
		cnt.push_back(0);
		REP(j,N){
			if(d[j]-prev<i){
				cnt.push_back(24-d[j]);
			}else{
				cnt.push_back(d[j]);
				prev=d[j];
			}
		}
		sort(cnt.begin(),cnt.end());
		int flg = 24-cnt.back()>=i;
		REP(j,N+1){
			FOR(k,j+1,N+1){
				if(abs(cnt[k]-cnt[j])<i)flg=0;
			}
		}
		if(flg){
			cout<<i<<endl;
			return 0;
		}
	}
	cout<<0<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
#define rep(i,m,n) for(int i=m;i<n;i++)
ll mod=1e9+7;

int main(){
  int n,k;
  cin>>n>>k;
  ll a[n];
  rep(i,0,n) cin>>a[i];
  if(k>=n) cout<<0<<endl;
  else {
    sort(a,a+n);
    ll ans=0;
    rep(i,0,n-k) ans+=a[i];
    cout<<ans<<endl;
  }
}

Measured memory_bytes: 1792
import itertools
import sys
N = int(input())
if N < 3:
  print(0)
  sys.exit()
 
#辺を取得してint型に変換
hen_list = input().split()
for i in range(len(hen_list)):
    hen_list[i] = int(hen_list[i])
 
#組み合わせ
count = 0
for tri in itertools.combinations(hen_list, 3):
    sort_tri = sorted(tri)
    if sort_tri[0] + sort_tri[1] > sort_tri[2]:
        if tri[0] != tri[1] and tri[0] != tri[2] and tri[1] != tri[2]:
            #print(sort_tri)
            count += 1
print(count)

Measured memory_bytes: 9144
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const ll N=1e6+5,inf=1e18,mod=1e9+7;
#define test ll testcases;cin>>testcases; while(testcases--)
#define lp(var,start,end) for (ll var = start; var <end ; ++var)
#define rlp(var,start,end) for(ll var = start; var>=end ; var--)
#define pb push_back
#define mp make_pair
#define pf push_front
#define ff first
#define ss second
#define vll vector<ll>
#define vld vector<ld>
#define pll pair<ll,ll> 
#define pld pair<ld,ld> 
#define vpll vector<pll>
#define vpld vector<pld>
#define all(X) X.begin(),X.end()
#define sz(x) ((ll)((x).size()))
const ld pi=3.141592653589793238;

bool check_prime(ll n)
{
	ll flag=0,i;
	for(i=2;i*i<=n;i++)
	{
		if(n%i==0)
		{
			flag=1;
			break;
		}
	}
	if(n==1)
	{
		return false;
	}
	else if(flag==0 || n==2 || n==3)
	{
		return true;
	}
	else
	{
		return false;
	}
}

ll fastexpo(ll a,ll b,ll MOD) 
{
	ll result=1;
	while(b>0)
	{
		if(b%2==1)
		{
			result=(result*a)%MOD;
		}
		a=(a*a)%MOD;
		b=b/2;
	}
	return result;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll a,b,g;
    cin>>a>>b;
    g=__gcd(a,b);
    cout<<(a*b)/g<<"\n";
	return 0;
}

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

Measured memory_bytes: 256
/****************************
/////  Shubham Singhal
/////  LNMIIT
*****************************/
#include <bits/stdc++.h>
#define ff first
#define ss second
#define mp make_pair
#define pb push_back
#define ppb pop_back
#define pf push_front
#define ppf pop_front
#define eb emplace_back
#define lwr lower_bound
#define upr upper_bound
#define pq priority_queue
#define umap unordered_map
#define rep(i,n) for(i=0; i<n;i++)
#define repp(i,a,n) for(i=a; i<n;i++)
#define precise(x) cout<<fixed<<setprecision(x)
#define all(x) x.begin(),x.end()
#define lcm(a,b) (a*b)/__gcd(a,b)
#define prn(x) cout<<x<<"\n"
#define prn2(x, y) cout<<x<<" "<<y<<"\n"
#define prn3(x, y, z) cout<<x<<" "<<y<<" "<<z<<"\n"
#define prn4(x, y, z, a) cout<<x<<" "<<y<<" "<<z<<" "<<a<<"\n"
#define prnv(x) for(auto i:x) cout<<i<<" "; cout<<"\n"
#define MOD 1000000007

using namespace std;
 
typedef unsigned long long ull;
typedef long long ll;
typedef double ld;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<int, ll> pil;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd; 
typedef vector<int> vi;
typedef vector<long> vl;
typedef vector<char> vc;
typedef vector<ll> vll;
typedef vector<bool> vb;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<pii> vpii;
typedef vector<pil> vpil;
typedef vector<pli> vpli;
typedef vector<pll> vpll;
const long long INF64 = 1'000'000'000'000'000'000ll;
clock_t time_p=clock();
void time()
{
    time_p=clock()-time_p;
    cerr<<"Time Taken : "<<(float)(time_p)/CLOCKS_PER_SEC<<"\n";
}
void doc()
{
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
}
void fast()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
}

int main()
{
	fast();
	ll i,n;
	cin>>n;
	if(n&1)
		cout<<0;
	else
	{
		n/=2;
		ll ans=0;
		for(;n;n/=5)
			ans+=n/5;
		cout<<ans;
	}
}

Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <string>
#include <vector>
#include <utility>
#include <complex>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <deque>
#include <tuple>
#include <bitset>
#include <limits>
#include <algorithm>
#include <array>
#include <random>
#include <complex>
#include <regex>
#include <iomanip>
using namespace std;
typedef long double ld;
typedef long long ll;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define fcout cout << fixed << setprecision(10)
#define rep(i,n)    for(int i=0; i<(int)n; i++)
#define mp(a,b) make_pair(a,b)
#define pb push_back
#define all(x) x.begin(), x.end()
#define F first
#define S second
const ll inf = 1e18;
const ll mod = 1e9 + 7;

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

// mod. m での a の逆元 a^(-1) を計算する。
ll modinv(ll a, ll m) {
    ll b = m, u = 1, v = 0;
    while (b) {
        ll t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}

int main(){
    string s, t;
    cin >> s >> t;
    int flag=1;
    rep(i, s.size()){
        if(s[i] != t[i]) flag = 0;
    }
    string ans = flag ? "Yes" : "No";
    cout << ans << endl;
}



Measured memory_bytes: 3624
#include <bits/stdc++.h>
#define int long long
#define ll long long
#define rep(i,n) for(int i=0;i<n;i++)
#define INF LLONG_MAX/3
#define eps LDBL_EPSILON
#define moder 1000000007
#define pie 3.141592653589793238462643383279
#define P std::pair<int,int>
#define prique priority_queue
using namespace std;
int n,m;
P a[100010];
signed main(){
	cin>>n>>m;
	rep(i,n)cin>>a[i].first>>a[i].second;
	sort(a,a+n);
	int ans=0,now=0;
	rep(i,n){
		if(now+a[i].second<=m){
			ans+=a[i].first*a[i].second;
			now+=a[i].second;
		}
		else{
			ans+=(m-now)*a[i].first;
			cout<<ans<<endl;
			return 0;
		}
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 1792
n, m = map(int, input().split())
#ll,rr = map(int, input().split())
ll = 0
rr = n
for i in range(m):
  l, r = map(int, input().split())
  if ll > r or rr < l:
    ll = 2
    rr = 1
    break
  if ll <= l:
    ll = l
  if r <= rr:
    rr = r

print(rr-ll+1)

Measured memory_bytes: 3060
s = input()
n = len(s)
for i in range((n-1+3)//4):# 切り上げ
    if not(s[i] == s[(n-1)//2-i-1] and s[(n+3)//2 + i-1] ==  s[-i-1] and s[i] == s[-i-1]):
        print('No')
        exit()
print('Yes')

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


int main() {
  int N, L[2010]={0};
  ll ans=0;
  cin >> N;
  for(int i=0; i<N; i++){
    cin >> L[i];
  }
  sort(L,L+N);
  
  for(int i=0; i<N; i++){
    for(int j=i+1; j<N; j++){
      int ue = L[j]-L[i];
      int shita = L[i]+L[j];
      for(int k=j+1; k<N; k++){
        if(ue >= L[k]){continue;}
        if(L[k]<shita){ans++;}else{break;}
      }
    }
  }  
  
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
N, K = [int(v) for v in input().split()]
bins = [0] * (10 ** 5 + 1)
for _ in range(N):
    a, b = [int(v) for v in input().split()]
    bins[a] += b
cnt = 0
for i in range(1, len(bins)):
    cnt += bins[i]
    if cnt >= K:
        print(i)
        exit()

# for debug
print(-1)

Measured memory_bytes: 5740
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(long long i=0;i<(long long)(n);i++)
#define REP(i,k,n) for(long long i=k;i<(long long)(n);i++)
#define all(a) a.begin(),a.end()
#define eb emplace_back
#define lb(v,k) (lower_bound(all(v),k)-v.begin())
#define ub(v,k) (upper_bound(all(v),k)-v.begin())
#define fi first
#define se second
#define pi M_PI
#define PQ(T) priority_queue<T>
#define SPQ(T) priority_queue<T,vector<T>,greater<T>>
using ll=long long;
using P=pair<ll,ll>;
using PP=tuple<ll,ll,ll>;
using S=multiset<ll>;
using vi=vector<ll>;
using vvi=vector<vi>;
using vvvi=vector<vvi>;
const ll inf=1001001001001001;
const int INF=1001001001;
const int mod=1000000007;
const double eps=1e-10;
template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<class T> bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
template<class T> void out(T a){cout<<a<<'\n';}
template<class T> void outp(T a){cout<<'('<<a.fi<<','<<a.se<<')'<<'\n';}
template<class T> void outvp(T v){rep(i,v.size())cout<<'('<<v[i].fi<<','<<v[i].se<<')';cout<<'\n';}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<'\n';}
template<class T> void outvv(T v){rep(i,v.size())outv(v[i]);}
template<class T> bool isin(T x,T l,T r){return (l)<=(x)&&(x)<=(r);}
template<class T> void YesNo(T b){if(b)out("Yes");else out("No");}
void decimal(int x){cout<<fixed<<setprecision(x);}
ll GCD(ll a,ll b){if(b==0) return a; return GCD(b,a%b);}
ll LCM(ll a,ll b){return(a/GCD(a,b))*(b/GCD(a,b))*GCD(a,b);}
ll POW(ll a,ll b){a%=mod;if(b==0)return 1;if(b&1)return a*POW(a,b-1)%mod;ll k=POW(a,b/2);return k*k%mod;}
vi calc(ll x){vi res;while(x>0){res.eb(x%10);x/=10;}reverse(all(res));return res;}

void solve() {
  ll h,w,k;
  cin>>h>>w>>k;
  vector<string> s(h);
  rep(i,h) cin>>s[i];
  vvi v(h,vi(w,0));
  rep(i,h)rep(j,w) v[i][j]=s[i][j]-'0';
  //outvv(v);
  ll ans=inf;
  //bit全探索
  rep(tmp,(1<<h-1)){
    bitset<9> b(tmp);
    vi t;
    rep(i,h-1) if(b.test(i)) t.eb(i);
    t.eb(h-1);
    ll sz=t.size();
    //outv(t);
    bool f=true;
    vvi a(sz,vi(w));
    rep(j,w){
      ll q=0;
      rep(r,sz){
        ll d=0;
        REP(i,q,t[r]+1) d+=v[i][j];
        a[r][j]=d;
        if(d>k) f=false;
        q=t[r]+1;
      }
    }
    //outvv(a);
    if(!f) continue;
    ll p=0;
    vi x(sz,0);
    rep(j,w){
      bool g=true;
      rep(i,sz){
        if(a[i][j]+x[i]>k) g=false;
      }
      if(g){
        rep(i,sz) x[i]+=a[i][j];
      }
      else{
        p++;
        rep(i,sz) x[i]=a[i][j];
      }
      x.resize(sz,0);
    }
    //out(p+sz-1);
    chmin(ans,p+sz-1);
  }
  out(ans);
}

signed main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  solve();
}


Measured memory_bytes: 456
import java.util.*;
 
public class Main
{
  public static void main(String[] args)
  {
    Scanner scan1 = new Scanner(System.in);
    String input = scan1.next();
    String output = "";
    
    for(int i = 0; i < input.length(); i++)
    {
      output += "x";
    }
    
    System.out.println(output);
  }
}

Measured memory_bytes: 22868
# import io
# import sys

# _INPUT = """\
# 1 4 120
# 100 1 1 1 1 1 1 1 1 1 1
# 80 10 10 10 10
# """
# sys.stdin = io.StringIO(_INPUT)

####################################################################
import sys
def p(*_a):
  return
  _s=" ".join(map(str,_a))
  #print(_s)
  sys.stderr.write(_s+"\n")
####################################################################

N,M,K = map(int, input().split())
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]

# 累積和
from itertools import accumulate
A = list(accumulate(a))
B = list(accumulate(b))

p(*A)
p(*B)

from bisect import bisect_right as br

ans = 0
# Aは「位置番号＝冊数」とするので、
# 「Aが0冊」の可能性を考慮し、先頭に[0]を追加
# Bは二分探索するので、挿入位置＝冊数になるから、[0]は追加しなくてOK
# (←挿入位置が先頭になれば、自然と0が戻り値になるから)
A = [0] + A
for a, ka in enumerate(A):
  if ka > K: break

  b = br(B, K - ka) #二分探索を使って、Bの取り得る最大の時間から位置番号(＝冊数)を求める
  ans = max(ans, a + b)


print(ans)


Measured memory_bytes: 50768
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>
using namespace std;
typedef long long ll;
const int N=1e5+11,INF=~0u>>2;
struct Edge{
	int l,r;
}edge[1005];
int n,ans;
int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return f*x;
}
bool cmp(Edge a,Edge b){
	return a.r==b.r?a.r<b.r:a.l<b.l;
}
int main(){
//	freopen("ex.in","r",stdin);
	n=read();
	for(int i=1;i<=n;++i){
		edge[i].l=read();edge[i].r=read();
	}
	sort(edge+1,edge+1+n,cmp);
	int x=edge[1].l,y=edge[1].r;ans+=y-x+1;
	for(int i=2;i<=n;++i){
		if(edge[i].l<=y) ans+=edge[i].r-y,y=edge[i].r;
		else ans+=edge[i].r-edge[i].l+1,x=edge[i].l,y=edge[i].r;
	}
	printf("%d",ans);
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
long long int n;
const long long int mod=1e9+7;
void multiply(vector<vector<long long int> >& a,vector<vector<long long int> >& b)
{
	long long int c[53][53]={0};
	for(long long int i=0;i<n;i++){
		for(long long int j=0;j<n;j++){
			for(long long int k=0;k<n;k++){
				c[i][j]+=(a[i][k]*b[k][j]);
				c[i][j]%=mod;
			}
		}
	}
	for(long long int i=0;i<n;i++){
		for(long long int j=0;j<n;j++){
			a[i][j]=c[i][j];
		}
	}
	return ;
 
}
void find(vector<vector<long long int> >& a,long long int k){
	if(k==1)return;
	vector<vector<long long int> >dp(n,vector<long long int>(n));
	dp=a;
	find(a,k/2);
	multiply(a,a);
	if(k%2==1){
		multiply(a,dp);
	}
	return ;
}
int main()
{
  long long int k;
  cin>>n>>k;
  vector<vector<long long int>> v(n,vector<long long int>(n));
  for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)
      cin>>v[i][j];
  find(v,k);
  	long long int ans=0;
  	for(long long int i=0;i<n;i++){
  		for(long long int j=0;j<n;j++){
  			ans+=v[i][j];
  		}
  	}
  	cout<<((ans)%mod);
}

Measured memory_bytes: 1536
/* {{{ */
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

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

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };
    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };
    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };
    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };
    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}
/* }}} */

pub struct Sieve {
    primes: Vec<u64>,
    tbl: Vec<u64>,
}
impl Sieve {
    pub fn new(n: u64) -> Sieve {
        let sz: usize = (n + 1) as usize;
        let mut primes = Vec::new();
        let mut tbl = vec![0; sz];
        tbl[0] = 0;
        tbl[1] = 0;
        for i in 2..sz {
            if tbl[i] != 0 {
                continue;
            }
            primes.push(i as u64);
            tbl[i] = i as u64;
            let mut j = i * i;
            while j < sz {
                if tbl[j] == 0 {
                    tbl[j] = i as u64;
                }
                j += i;
            }
        }
        Sieve {
            primes: primes,
            tbl: tbl,
        }
    }
    pub fn primes(&self) -> &Vec<u64> {
        &self.primes
    }
    pub fn is_prime(&self, x: u64) -> bool {
        x > 1 && self.tbl[x as usize] == x
    }
    pub fn factorization(&self, x: u64) -> Vec<(u64, u64)> {
        let mut mx = x;
        let mut fl = Vec::new();
        while mx > 1 {
            let fx = self.tbl[mx as usize];
            fl.push(fx);
            mx /= fx;
        }
        if fl.is_empty() {
            return Vec::new();
        }
        let mut res = vec![(fl[0], 0)];
        for p in &fl {
            let l = res.len() - 1;
            let last = res[l];
            if last.0 == *p {
                res[l].1 += 1;
            } else {
                res.push((*p, 1));
            }
        }
        res
    }
}

fn main() {
    input! {
        x: u64
    }
    let s = Sieve::new(100003);
    for i in x.. {
        if s.is_prime(i) {
            println!("{}", i);
            return;
        }
    }
}
/* vim:set foldmethod=marker: */


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

#pragma warning(disable:4996)
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize ("Ofast")
#pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize ("-ffloat-store")

 
using namespace std;
 
#define int long long
#define ll long long
#define vi vector <int>
#define vii vector <pair<int,int> >
#define rep(i,a,b) for (int i=a;i<b;i++)
#define repD(i,a,b) for (int i=a;i>b;i--)
#define pb push_back
#define pii pair <int,int>
#define ff first
#define ss second
#define all(a) a.begin(),a.end()
#define MOD 1000000007
#define PI 3.14159265359
 
#define deb(x) {x}
#ifndef local
	#define deb(x) ;
#endif
///----------------------------------------------------------------------------------

int n,m;
string a,b;
map<char,vi> pos;
double arr[200];
void solve()
{
	cin>>n;rep(i,0,n)cin>>arr[i];
	double ans=0;
	
	rep(i,0,n)ans+=(1.0/arr[i]);
	cout<<fixed<<setprecision(10)<<(1.0/ans);
}

signed main()
{
	ios_base::sync_with_stdio(false);cin.tie(NULL);
 	
 	#ifdef local
    //freopen("input.txt","r",stdin);
    ///freopen("output.txt","w",stdout);
    clock_t qwertyuiop = clock();
    #endif
 
 	int t=1;
    //cin>>t;
    
    rep(a,0,t)
    {
        ///cout<<"Case #"<<a+1<<": ";
        solve();
	}
	
    #ifdef local
    {qwertyuiop = clock() - qwertyuiop;double time_taken = ((double)qwertyuiop)/CLOCKS_PER_SEC;cerr<<fixed<<setprecision(5)<<"\n\nTime Taken : "<<time_taken<<" seconds\n";}
	#endif
}



Measured memory_bytes: 256
import sys
import numpy as np

i = list(map(int, input().split()))
N = i[0]
M = i[1]
ac = np.array([0]*N)
wa = np.array([0]*N)
for i in range(M):
    line = sys.stdin.readline().split()
    p = int(line[0])
    s = line[1]
    if ac[p - 1] == 0:
        if s == 'AC':
            ac[p - 1] = 1
        else:
            wa[p - 1] += 1
    

print(str(sum(ac)) + " " + str(sum(ac * wa)))

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

int main() {
  int N,T;
  cin>>N>>T;
  vector<long> t(N);

  for(int j=0;j<N;j++){
    cin>>t[j];
  }
  long sum=0;
  long now=0;
  for(int i=0;i<N-1;i++){
    now = min(t[i]+T,t[i+1]);
    sum += now - t[i];
    //cout<<sum<<endl;
  }
  cout<<sum+T<<endl;
}


Measured memory_bytes: 1792
N = int(input())
W = [input() for i in range(N)]
S = set(W)
p = 0
if (len(W) != len(S)):
  print('No')
else:
  for k in range(N-1):
    a = W[k]
    b = W[k+1]
    if (a[len(a)-1] == b[0]):
      p += 1
    else:
      p += 0
  if (p == N-1):
    print('Yes')
  else:
    print('No')

Measured memory_bytes: 3064
import java.util.Scanner;

public class Main {

	@SuppressWarnings("resource")
	public static void main(String args[]) {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();

		for (int i = 1; i <= n; i++) {
			long tmp = (long) i * i;
			if (tmp > n) {
				System.out.println((long) (i - 1) * (i - 1));
				return;
			}
		}
		
		System.out.println(1);
	}
}


Measured memory_bytes: 23636
using System;
using System.Linq;

namespace NTL_1_B
{
    class Program
    {
        static ulong mod_pow(ulong x, ulong n)
        {
            if (n == 0) return 1;
            ulong res = mod_pow(x * x % 1000000007, n / 2);
            if (n % 2 == 1) res = res * x % 1000000007;
            return res;
        }
        static void Main(string[] args)
        {
            ulong[] x = Console.ReadLine().Split().Select(ulong.Parse).ToArray();
            Console.WriteLine(mod_pow(x[0], x[1]));
        }
    }
}

Measured memory_bytes: 9508
#include <iostream>
#include <cstdlib>
using namespace std;
int main()
{
    int n,a[100005],dp[100005];
    cin >> n;
    for (int i=1;i<=n;i++)
    {
        cin >> a[i];
    }
    dp[1]=0;
    dp[2]=abs(a[2]-a[1]);
    for (int i=3;i<=n;i++)
    {
        dp[i]=min(dp[i-2]+abs(a[i]-a[i-2]),dp[i-1]+abs(a[i]-a[i-1]));
    }
    cout << dp[n];
}

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

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

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

int gcd(int a,int b)
{
	if(a==0)
		return b;
	else if(b==0)
		return a;
	else return gcd(b,a%b);
}

int lcm(int a,int b)
{
	return (a*b)/gcd(a,b);
}*/

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

    int k;
    cin>>k;
    string s,str;
    cin>>s;
    if(s.length()<=k){cout << s;return 0;}
    else str=s.substr(0,k);
    str+="...";
    cout <<str;
    return 0; 
}


Measured memory_bytes: 3648
def main():
  import sys
  input = sys.stdin.readline
  
  H,W = map(int,input().split())
  S = [list(input()) for _ in range(H)]
  #print(S)
  idx = 0
  for i in range(H):
    for j in range(W):
      if S[i][j] == '.':
        S[i][j] = idx
        idx += 1
  #print(S)
  D = [[float('inf') for _ in range(idx)] for _ in range(idx)]
  for i in range(H):
    for j in range(W):
      if S[i][j] == '#':
        continue
      for dy,dx in [(-1,0),(1,0),(0,-1),(0,1)]:
        if 0 <= i+dy < H and 0 <= j+dx < W and S[i+dy][j+dx] != '#':
          D[S[i][j]][S[i+dy][j+dx]] = 1
          D[S[i+dy][j+dx]][S[i][j]] = 1
  for i in range(idx):
    D[i][i] = 0
  
  for k in range(idx):
    for i in range(idx):
      for j in range(idx):
        D[i][j] = min(D[i][k]+D[k][j],D[i][j])
  #print(D)
  ans = 0
  for d in D:
    ans = max(max(d),ans)
  print(ans)

if __name__ == '__main__':
  main()


Measured memory_bytes: 138552
import copy
from pprint import pprint

N, M, Q = [int(x) for x in input().strip().split(" ")]
ABCD = [[int(x) for x in input().strip().split(" ")] for _ in range(Q)] 

# make A
def make_a_set(len_, min_, max_):
    if len_ == 1:
        return [[v] for v in range(min_, max_ + 1)]
    A = []
    for i in range(min_, max_ + 1):
        sub_a = make_a_set(len_ -1 , i, max_)
        A += [[i] + sub_a_ for sub_a_ in sub_a]
    return A

q_sum_set = []
for A in make_a_set(N, 1, M):
    q = 0
    for a, b, c, d in ABCD:
        a -= 1
        b -= 1
        if A[b] - A[a] == c:
            q += d
    q_sum_set.append(q)
print(max(q_sum_set))

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

typedef long long ll;
typedef pair<int,int> P;
int dx[] = {-1, 1, 0,  0};
int dy[] = { 0, 0, 1, -1};
vector<ll> a(55), p(55);

int gcd(int x, int y) { return (x % y)? gcd(y, x % y): y; }

int main() {
  int n, a, b;
  cin >> n >> a;
  for (int i = 1; i < n; i++) {
    cin >> b;
    a = gcd(a, b);
  }
  cout << a;
  
  return 0;
}


Measured memory_bytes: 256