akhauriyash/Code-Regression huggingface dataset:
package main

import "fmt"

func main() {

	var str string

	for {
		fmt.Scan(&str)
		if str=="-" {
			break
		}

		var n, m int
		rstr := []rune(str)
		n = len(rstr)
		rstr_temp := make([]rune, n)
		fmt.Scan(&m)

		for i:=0; i<m; i++ {
			
			var h int
			fmt.Scan(&h)
			_ = copy(rstr_temp, rstr)

			for idx:=0; idx<n; idx++ {
				rstr[idx] = rstr_temp[(idx+h)%n]
			}
		}
		fmt.Println(string(rstr))
	}
}


Measured memory_bytes: 1120
from collections import deque

k=int(input())
d=deque(range(1,10))

for i in range(k):
  x=d.popleft()
  if x%10!=0:
    d.append(10*x+(x%10)-1)
  d.append(10*x+(x%10))
  if x%10!=9:
    d.append(10*x+(x%10)+1)

print(x)

Measured memory_bytes: 11908
"use strict";

// read lines from stdin
const input = require("fs")
  .readFileSync("/dev/stdin", "utf8").trim();

let ans = 0;
let len = 0;

for (let i = 0; i < input.length; i++) {
  if (input[i] === "A" || input[i] === "T" || input[i] === "C" || input[i] === "G") {
    len++;
  } else {
    if (len > ans) { ans = len; }
    len = 0;
  }
}

console.log(len > ans ? len : ans);


Measured memory_bytes: 21192
#include <bits/stdc++.h>
#include <ext/pb_ds/detail/standard_policies.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long int ll;
typedef unsigned long long int ull;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> o_set; 

#define     int                 ll
#define     pb                  push_back
#define     mp                  make_pair
#define     xx                  first
#define     yy                  second    
#define     all(a)              a.begin(),a.end()
#define     vi                  vector<int>
#define     vpi                 vector<pii>
#define     pii                 pair<int, int>
#define     present(DT, val)    (DT.find(val) != DT.end()) //for set and map
#define     cpresent(DT, val)   (find(all(DT),val) != DT.end()) //vectors
#define     input               "/home/pollution/Desktop/WorkSpace/C++/Files/input.txt"
#define     output              "/home/pollution/Desktop/WorkSpace/C++/Files/output1.txt"
#define     error               "/home/pollution/Desktop/WorkSpace/C++/Files/error.txt"
#define     IO()                ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define     INF                 2e18
#define     MOD                 1000000007
#define     clr(x)              memset(x, 0, sizeof(x))
#define     init(x, a)          memset(x, a, sizeof(x))
#define     out(a)              for (auto i: a) cout<<i<<' '; cout<<'\n'
#define     cpy(a,b)            memcpy(a,b,sizeof(b))
#define     is(a)               to_string(a)
#define     ci(a,c)             a-c
#define     debug(i)            cout<<"point :"<<i<<'\n';
#define     setd(val,n)         cout<<fixed<<setprecision(n)<<val<<'\n'

const int MAXN=2e5+2;
int N,K,C;
string s;
int t1[MAXN];
int t2[MAXN];

void solve(){
    cin>>N>>K>>C;
    cin>>s;
    s="x"+s;
    int work=1;
    int rest=C;
    for(int d=1;d<=N;d++){
        if(s[d]=='o'){
            if(rest>=C && work <= N+1){
                t1[work++]=d;
                rest=0;
            }
            else rest++;
        }
        else rest++;
    }
    work=K;
    rest=C;
    for(int d=N;d>0;d--){
        if(s[d]=='o'){
            if(rest>=C && work>=0){
                t2[work--]=d;
                rest=0;
            }
            else rest++;
        }
        else rest++;
    }
    for(int w=1;w<=K;w++){
        if(t1[w]==t2[w]){
            cout<<t1[w]<<"\n";
        }
    }
}

signed main() { 
    IO();
    
    int t=1;
    // cin>>t;
    while(t--) solve();
    return 0; 
}

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


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int>>; // グラフ型
typedef long long ll;
#define _GLIBCXX_DEBUG




int main() {
  vector<vector<int>> A(3, vector<int>(3));
  vector<vector<int>> ju(3, vector<int>(3));
  
  for(ll i=0; i<3;i++){
    for(ll j= 0 ; j<3; j++){
      cin >> A[i][j];
    }
  }
  ll N;
  cin >> N;

  for(ll i=0; i<N;i++){
    ll tmp;
    cin >> tmp;
    for(ll i=0; i<3;i++){
      for(ll j= 0 ; j<3; j++){
        if(A[i][j] == tmp) ju[i][j] = 1;
      }
    }
  }

  for(ll i=0; i<3;i++){   
    if(ju[i][0] == 1 && ju[i][1] == 1 && ju[i][2] == 1){
      cout << "Yes" << endl;
      return 0;
    }
  }

  for(ll j=0; j<3;j++){   
    if(ju[0][j] == 1 && ju[1][j] == 1 && ju[2][j] == 1){
      cout << "Yes" << endl;
      return 0;
    }
  }

  if(ju[0][0] == 1 && ju[1][1] == 1 && ju[2][2] == 1){
      cout << "Yes" << endl;
      return 0;
  }

  if(ju[0][2] == 1 && ju[1][1] == 1 && ju[2][0] == 1){
      cout << "Yes" << endl;
      return 0;
  }
  

  cout << "No" << endl;
  return 0;
}


Measured memory_bytes: 3580
round = Array.new
round[0] = Hash::new
round[1] = Hash::new
round[2] = Hash::new
final = Hash::new

#get input
for j in 0...3
  for i in 0...8
    input = gets.split(" ")
    round[j][input[0]] = input[1]
  end
end

#ソートのために配列化
r1 = round[0].to_a
r2 = round[1].to_a
r3 = round[2].to_a

#タイムでソート
r1.sort!{|rec1, rec2|  rec1[1]<=>rec2[1]}
r2.sort!{|rec1, rec2|  rec1[1]<=>rec2[1]} 
r3.sort!{|rec1, rec2|  rec1[1]<=>rec2[1]}
  
#各ラウンド上位2位を決勝候補に追加
print(r1[0][0], " ", r1[0][1], "\n")
print(r1[1][0], " ", r1[1][1], "\n")
r1.delete_at(0)
r1.delete_at(0)

print(r2[0][0], " ", r2[0][1], "\n")
print(r2[1][0], " ", r2[1][1], "\n")
r2.delete_at(0)
r2.delete_at(0)

print(r3[0][0], " ", r3[0][1], "\n")
print(r3[1][0], " ", r3[1][1], "\n")
r3.delete_at(0)
r3.delete_at(0)

#残りの配列を結合してソートして上位2位取得
rest = r1.concat(r2).concat(r3)
rest.sort!{|rec1, rec2|  rec1[1]<=>rec2[1]}
print(rest[0][0], " ", rest[0][1], "\n")
print(rest[1][0], " ", rest[1][1], "\n")


Measured memory_bytes: 6868
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD=1e9+7;
const int INF=1e9;

int main(){
    ll k;
    cin>>k;
    ll x=k/50+49;
    int r=k%50;
    cout<<50<<endl;
    for(int i=0;i<50;i++){
        if(i)cout<<" ";
        if(i<r)cout<<x-r+51;
        else cout<<x-r;
    }
    cout<<endl;
}


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

int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  rep(i, n) {
    cin >> a.at(i);
  }
  sort(a.begin(), a.end());
  map<int, int> amap;
  for (int i = 0; i < 100000; i++) {
    amap[i] = 0;
  }
  rep(i, n) {
    amap[a.at(i)]++;
  }
  vector<int> num(100000);
  for (int i = 0; i < 100000; i++) {
    if (i == 0) {
      num.at(0) = amap[0] + amap[1];
    }
    else if (i == 100000 - 1) {
      num.at(i) = amap[i-1] + amap[i];
    }
    else {
      num.at(i) = amap[i-1] + amap[i] + amap[i+1];
    }
  }
  int max = 0;
  for (int i = 0; i < 100000; i++) {
    if (max < num.at(i)) {
      max = num.at(i);
    }
  }
  cout << max << endl;
}     

Measured memory_bytes: 5760
import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

n = int(input())
G = [[-1]*n for i in range(n)]
for i in range(n):
    ai = int(input())
    for j in range(ai):
        x,y = map(int, input().split())
        G[i][x-1] = y

ans = 0
for i in range(1<<n):
    l = [i&(1<<j)!=0 for j in range(n)]
    f = True
    for j in range(n):
        if l[j]:
            if not all(G[j][k] == -1 or l[k] == G[j][k] for k in range(n)):
                f = False
                break
    if f:
        ans = max(ans, sum(l))

print(ans)

Measured memory_bytes: 53592
n = int(input())
"""素因数分解"""
def factrize(n):
    b = 2
    fct = []
    while b*b <= n:
        while n % b == 0:
            n //= b
            #もし素因数を重複させたくないならここを加えてfct.append(b)を消す
            """
            if not b in fct:
                fct.append(b)
            """
            fct.append(b)
        b = b+1
    if n > 1:
        fct.append(n)
    return len(fct) == 1 #TFが帰る


while True:
    if factrize(n):
        break
    else:
        n+=1
print(n)



Measured memory_bytes: 39152
#include <iostream>
#include <algorithm>
#include <cmath>
#include <utility>
using namespace std;

int main(){
    string s;
    cin>>s;
    for(int i=0;i<4;i++){
        cout<<s[i];
    }
    cout<<' ';
    for(int i=4;i<12;i++){
        cout<<s[i];
    }
    cout<<endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5+10;
ll n,k;
ll a[N],b[N];
ll check(ll sum)
{
	ll ans=0;
	for(int i=1;i<=n;i++)
	{
		if(a[i]*b[n-i+1] > sum)
		{
			ll cnt=(sum)/b[n-i+1];
			ans += -cnt+ a[i];
		}
	}
	return ans;
}
int main()
{
	ios::sync_with_stdio(false);
	cin>>n>>k;
	ll sum=0;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		sum+=a[i];
	}
	for(int i=1;i<=n;i++)
	cin>>b[i];
	if(sum<=k)
	{
		cout<<0<<endl;
		return 0;
	}
	sort(a+1,a+n+1);
	sort(b+1,b+n+1);
	ll ans=0;
	for(int i=1;i<=n;i++)
	ans=max(ans,a[i]*b[n-i+1]);
	ll l=1,r=ans+1;
	while(l<r)
	{
		ll mid=(l+r)>>1;
		if(check(mid)>k)
		l=mid+1;
		else
		r=mid;
	}
	cout<<l<<endl;
}

Measured memory_bytes: 3328
#include<bits/stdc++.h>
using namespace std;
int main(){
  int w,h;
  cin>>w>>h;
  int c[10][10];
  for(int i=0;i<10;i++)
    for(int j=0;j<10;j++)
      cin>>c[i][j];
  
  for(int k=0;k<10;k++)
    for(int i=0;i<10;i++)
      for(int j=0;j<10;j++)
	c[i][j]=min(c[i][j],c[i][k]+c[k][j]);
   
  int ans=0;
  for(int i=0;i<h;i++)
    for(int j=0;j<w;j++){
      int a;
      cin>>a;
      if(a>-1)ans+=c[a][1];
    }
  cout<<ans<<endl;
  return 0;
}


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

#define REP(i,n) for (int i=0;i<(n);i++)
#define PII pair<int,int>
#define LL long long

int main(){
  const int INF=100000000;
  int n,m;
  cin>>n>>m;

  int a[1000],b[1000],c[1000];
  int dist[100][100];

  REP(i,m){
    cin>>a[i]>>b[i]>>c[i];
    a[i]--,b[i]--;
  }

  REP(i,n){
    REP(j,n){
      if(i==j){
	dist[i][j]=0;
      }else{
	dist[i][j]=INF;
      }
    }
  }

  REP(i,m){
    dist[a[i]][b[i]]=min(dist[a[i]][b[i]],c[i]);
    dist[b[i]][a[i]]=min(dist[b[i]][a[i]],c[i]);
  }

  //warshall_floyd
  REP(i,n){
    REP(j,n){
      REP(k,n){
	dist[j][k]=min(dist[j][k],dist[j][i]+dist[i][k]);
      }
    }
  }

  //check
  int answer=m;
  REP(i,m){
    bool shortest=false;
    REP(j,n){
      if(dist[j][a[i]]+c[i]==dist[j][b[i]]){
	shortest=true;
	break;
      }
    }
    if(shortest){
      answer-=1;
    }
  }

  cout<<answer<<endl;
    
  
  return 0;
}




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

int main() {
  string S; cin >> S;
  int K; cin >> K;
  int L = S.size();
  // dp[i][j] := 左から i 桁決めて、0 でない数を j 個含む
  vector<vector<long long>> dp0(L+1, vector<long long>(5));
  vector<vector<long long>> dp1(L+1, vector<long long>(5));
  dp0.at(0).at(0) = 1;
  for (int i = 0; i < L; i++) {
    // j = 4, 5, ... からの遷移は不要
    for (int j = 0; j < 4; j++) {
      // 未満フラグが立っていない場合 (dp0[i][j] からの遷移)
      int D = S.at(i) - '0';
      for (int d = 0; d <= D; d++) {
        int nj = j;
        if (d != 0) nj++;
        if (d < D) {  // 未満フラグが立つ
          dp1.at(i+1).at(nj) += dp0.at(i).at(j);
        }
        else {
          dp0.at(i+1).at(nj) += dp0.at(i).at(j);
        }
      }
      // 未満フラグが立っている場合 (dp1[i][j] からの遷移)
      for (int d = 0; d <= 9; d++) {
        int nj = j;
        if (d != 0) nj++;
        dp1.at(i+1).at(nj) += dp1.at(i).at(j);
      }
    }
  }
  cout << dp0.at(L).at(K) + dp1.at(L).at(K) << endl;
}

Measured memory_bytes: 256
/*input
100000
*/
#include <bits/stdc++.h>
using namespace std; 
#define int long long int
#define max(x, y) ((x) > (y) ? (x) :(y))
#define pii pair< int , int> 
#define vi vector<int>
#define REP( i , st , en ) for ( int i =st; i < (int)en; i++)
#define REPD( i , en , st ) for ( int i =en; i >= (int)st; i--)
#define SZ(a) (int)a.size()
#define all(v) v.begin() , v.end()
#define F first
#define S second
#define bitch_i_m_on_fiyaah_yeahhhh ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
const int mod = 998244353;
// const int mod = 1e9+7;
ostream& operator << ( ostream&  o, vector<int> s){for ( int i = 0;  i < (int)s.size() ; i++)o << s[i] << " ";o << "\n";return o;}
void  add( int &a, int b){a = a + b;if ( a< 0 ) a += mod; if ( a> mod ) a-= mod;}
void sub( int &a, int b){a = a - b;if ( a < 0) a += mod;}
int mul( int a , int b){return ((a %mod) * (b %mod) ) %mod;}
int exp( int a , int pow){ return (pow == 0 ? 1 : ( pow & 1  ? mul ( a ,exp( mul(a, a) , pow /2) ) : exp(mul(a ,a) , pow/2)));}
int gcd(int a, int b) { return b ? gcd(b, a%b) : a; }
// const int inf = 1e18;
const int maxn = 6e5 +5;

 
void solve(int test ) 
{	
		int k ;
		cin >>  k;
		queue<int> q;
		REP( i , 1 ,10) q.push(i);
		int x;
		REP( i , 0 ,  k) { 
			 x = q.front();
			q.pop(); 
			if ( x % 10) q.push( 10 * x + ( x % 10)  -1);
			q.push(10 * x + ( x % 10));
			if ( x %  10 != 9) q.push( 10 * x + ( x % 10)  +1);
		}
	cout <<x;
}
signed main(){
	bitch_i_m_on_fiyaah_yeahhhh
	int t =1; 
	// cin >> t;
	for ( int i = 0 ; i < t; i++)
	solve(i+1 );
}

Measured memory_bytes: 1792
#include <iostream>
#include <cmath>
#include <algorithm>
#include <climits>
#include <vector>
#include <iomanip>
#define REP(i,n) for (int i=0;i<(n);i++)
using namespace std;

int main(){
    int n, k;
    double ans = 0;
    cin >> n >> k;
    for(int i = 1; i <= n; ++i){
        double tmp = 1.0 / n;
        int now = i;
        while(now < k){
            now *= 2;
            tmp /= 2;
        }
        ans += tmp;
    }
    cout << setprecision(12) << ans <<endl;
    return 0;

}


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

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
#define mem(a,b) memset(a,b,sizeof(a))
#define shutdown ios::sync_with_stdio(false)
#define MAX 10e18+1000

int main() {
    shutdown;
    int n,a;
    cin>>n>>a;
    cout<<n*n-a<<endl;
    return 0;
}


Measured memory_bytes: 256
n = int(input())
x = [int(i) for i in input().split()]

ans = 0
s = [0]
xs = [0]

for i in x:
    s.append(s[-1]+i)
    xs.append(xs[-1]^i)

def search(start, ok, ng):
    if abs(ok-ng) <= 1:
            return ok
    mid = (ok+ng) // 2
    if s[mid] - s[start] == xs[mid] ^ xs[start]:
        return search(start, mid, ng)
    else:
        return search(start, ok, mid)

for i in range(n+1):
    ans += search(i, i, n+1) - i
print(ans)

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

using namespace std;

int main()
{
  int n;
  cin>>n;
  int cnt=0;
  for(int i=1;i<=n;i++)
    {
      long long x;
      cin>>x;
      if(x%2)
	cnt++;
    }
  if(cnt%2)
    cout<<"NO";
  else
    cout<<"YES";
}

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

using namespace std;

int main() {
#ifdef LOCAL
    freopen("atcoder/input.txt", "r", stdin);
#endif

    int n, k;
    cin >> n >> k;

    long double res = 0;


    for (int i = 0; i < n; ++i) {
        int current = i + 1;
        int power = 1;

        while (current < k) {
            current *= 2;
            power *= 2;
        }

//        cout << power << "\n";

        res += 1 / ((long double)power);
    }

    res /= n;

    cout << setprecision(15) << fixed;
    cout << res << "\n";

    return 0;


}



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int Maxn=1e5+1;
int f[Maxn],p[Maxn];

int findx(int x){
	if(x==f[x])return x;
	f[x]=findx(f[x]);
	return f[x];
}

int main(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>p[i];
		f[i]=i;
	}
	for(int i=1;i<=m;i++){
		int x,y;
		cin>>x>>y;
		if(findx(x)>findx(y))swap(x,y);
		f[f[x]]=f[y];
	}
	int ans=0;
	for(int i=1;i<=n;i++){
		if(findx(i)==findx(p[i]))ans++;
	}
	cout<<ans;
}

Measured memory_bytes: 1024
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string>
#include <iomanip>
#include <math.h>
#include <utility>

using namespace std;

int main(void)
{
    long long N, d[100001], i;

    cin >> N;

    for(i=1; i<=N; i++){
        cin >> d[i];
    }

    sort(d+1, d+N+1);

    cout << d[N/2+1] - d[N/2] << endl;

    return 0;
}

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

#define mp make_pair
#define s second 
#define f first
#define pb push_back


typedef long long ll;
typedef double db;


using namespace std;

const int inf=2e9+312;
const int N=2e5+4578;


int xx[4]={0, 0, 1, -1};
int yy[4]={1, -1, 0 ,0};

int a[N][3], b[N][3];

int main(){
	ios_base :: sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin >> n;
	for(int i=1; i<=n; i++){
		cin >> a[i][1] >> a[i][2] >> a[i][3];
	}
	for(int i=2; i<=n; i++){
		a[i][1]+=max(a[i-1][2], a[i-1][3]);
		a[i][2]+=max(a[i-1][1], a[i-1][3]);
		a[i][3]+=max(a[i-1][2], a[i-1][1]);
	}
	cout << max(a[n][1], max(a[n][2], a[n][3]));
	return 0;
}

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

typedef long long ll;
#define INF INT_MAX
#define MAXN 105
#define MAXW 100005

int N,W;
ll memo[MAXN][MAXW];
bool computed[MAXN][MAXW];
int w[MAXN];
int v[MAXN];

ll maxself(ll a,ll b){
    if(a > b)
        return a;
    return b;
}

void solve()
{
    for(int i = 0 ; i <= W ; i++)
        memo[0][i] = 0;
    for(int i = 1 ; i <= N ; i++){
        for(int c = 0 ; c <= W ; c++){
            ll best = memo[i-1][c];
            if(c >= w[i]){
                best = maxself(best,memo[i-1][c-w[i]] + v[i]);
            }
            memo[i][c] = best;
        }
    }
}

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

    cin >> N >> W;
    for(int i = 1 ; i <= N ; i++){
        cin >> w[i] >> v[i];
    }
    solve();
    cout << memo[N][W] << '\n';

    return 0;
}


Measured memory_bytes: 80128
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define pb push_back
#define mp make_pair

using namespace std;

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

const int MOD = 1000000007;
const int INF = 1000000000;
const ll LINF = 1000000000000000000L;

struct edge {
    int from, to, cost;
};

struct UniTree {
    int *par, *rank;

    UniTree(int n) {
        par = new int[n];
        rank = new int[n];
        for(int i = 0; i < n; i++) {
            par[i] = i;
            rank[i] = 0;
        }
    }

    int root(int x) {
        if(par[x] == x) return x;
        else return par[x] = root(par[x]);
    }

    void merge(int x, int y) {
        x = root(x);
        y = root(y);
        if(x == y) return;
        if(rank[x] < rank[y]) {
            par[x] = y;
        }else {
            par[y] = x;
            if(rank[x] == rank[y]) rank[x]++;
        }
    }
    
    bool same(int x, int y) {
        return root(x) == root(y);
    }
};


bool comp(const edge& e1,const edge& e2) {
    return e1.cost < e2.cost;
}

edge g[100000];

int main() {
    int v, e;
    cin >> v >> e;
    rep(i, e) {
        int s, t, w;
        cin >> s >> t >> w;
        g[i] = {s, t, w};
    }

    int ans = 0;
    sort(g, g + e, comp);
    UniTree uni(v);
    rep(i, e) {
        if(!uni.same(g[i].from, g[i].to)) {
            uni.merge(g[i].from, g[i].to);
            ans += g[i].cost;
        }
    }

    cout << ans << endl;

    return 0;
}



Measured memory_bytes: 4352
//
// Created by Myabu on 2020/01/18.
//

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <map>
#include <utility>
#include <math.h>
#include <stack>
#include <queue>
#include <cstdio>
#include <numeric>

using namespace std;


int main(void){
    string S;
    cin>>S;

    int sum_n = 0;
    for (int i = 0; i < S.length(); ++i) {
        sum_n += S[i] - '0';
    }

    if(stoi(S) % sum_n  == 0){
        cout<<"Yes"<<endl;
    }else{
        cout<<"No"<<endl;
    }


    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define lld long long 
#define pb push_back
#define mk make_pair
using namespace std;

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

	int a=0,b=0;

	for(int i=0;i<s.length();i++)
	{
		if(s[i]=='A')
			a++;

		else
			b++;
	}

	if(a==2 || b==2)
		cout<<"Yes"<<"\n";
	else
		cout<<"No"<<"\n";
	
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  int q,h,s,d,n;
  cin >> q >>h >>s >> d >>n;
  cout << (int64_t)((int64_t)(n/2)*min(min(min(8*q,4*h),2*s),d)+(int64_t)(n%2)*min(min(4*q,2*h),s)) << endl;
}


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

using namespace std;

int main(){
    int n, m;
    cin >> n >> m;
    vector<string> v;
    for(int i = 0; i < n; ++i){
        string tmp; cin >> tmp;
        v.push_back(tmp);
    }
    int arr[n] = {0}, arr1[m] = {0};
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < m; ++j){
            if(v[i][j] == '#'){
                arr[i] = true;
                arr1[j] = true;
            }
        }
    }
    for(int i = 0; i < n; ++i){
        if(!arr[i])continue;
        for(int j = 0; j < m; ++j){
            if(arr1[j]){
                cout << v[i][j];
            }
        }
        cout << endl;
    }
    return 0;

}


Measured memory_bytes: 256
n, k = list(map(int, input().split(' ')))
ass = list(map(int, input().split(' ')))

checker = dict()

for a in ass:
    checker.setdefault(a, 0)
    checker[a] += 1
    
ss = sorted(checker.values())
c = len(ss)
ans = 0

for s in ss:
    if c <= k:
        break
    else:
        ans += s
        c -= 1
print(ans)


Measured memory_bytes: 32188
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <list>
#include <utility>
#include <tuple>
#include <cstdio>
#include <set>
#include <queue>
#include <stack>
#include <deque>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <cctype>
#include <cmath>
#define _GLIBCXX_DEBUG
using namespace std;
const long long INF = 1LL << 60;
int main() {
    int N;
    cin >> N;
    long long ans = 1;
    vector<long long> A(N);
    bool frg = true;
    for(int i=0;i<N;i++){
        cin >> A[i];
        if(A[i]==0){
            ans = 0;
            frg = false;
            break;
        }  
    }
    if(frg){
        for(int i=0;i<N;i++){
            long long limit = 1e18;
            if(A[i] > (limit / ans)){
                ans = -1;
                break;
            }
            ans = ans * A[i]; 
            
        }
    }
    
    cout << ans << endl;
}

Measured memory_bytes: 4024
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> vec(3);
int main() {
	for(auto it = vec.begin(); it != vec.end(); ++it){
		cin>>*it;
	}
	sort(vec.begin() , vec.end());
	reverse(vec.begin() , vec.end());
	cout<<vec[0]*10+vec[1]+vec[2]<<endl;
	return 0;
}

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

#define ll uint64_t
#define lli long long int
#define MAX 1000
#define MOD 1000000007


int main()
{
    ll x, y;
    cin >> x >> y;
    if(x % y == 0)
        cout << -1;
    else 
        cout << x;
    return 0;
}


Measured memory_bytes: 256
a = int(input())
b = int(input())
c = int(input())
d = int(input())
e = int(input())

m = 10
ans = 0
for i in (a, b, c, d, e):
    q, mod = divmod(i, 10)
    if mod == 0:
        ans += i
    else:
        m = min(m, mod)
        ans += (q + 1) * 10
print(ans - 10 + m)


Measured memory_bytes: 9120
n, m = map(int, input().split())
ps = [int(i) - 1 for i in input().split()]
xy = [map(int, input().split()) for _ in range(m)]

dfind = {i: i for i in range(n)}


def find(v):
    visit = []
    while dfind[v] != v:
        visit.append(v)
        v = dfind[v]

    for i in visit:
        dfind[i] = v

    return v


def union(v0, v1):
    g0, g1 = find(v0), find(v1)
    g0, g1 = min(g0, g1), max(g0, g1)

    if g0 != g1:
        dfind[g1] = g0


for x, y in xy:
    union(x - 1, y - 1)


nmatch = 0
for i, p in enumerate(ps):
    if find(i) == find(p):
        nmatch += 1

print(nmatch)


Measured memory_bytes: 66308
n=int(input())
A=[int(i) for i in input().split()]
Ans=[0]*n
for i in range(1,n):
  Ans[i]=A[i-1]*2-Ans[i-1]
d=A[-1]-Ans[-1]//2
for i in range(n):
  if i%2==0:
    Ans[i]+=d
  else:
    Ans[i]-=d
print(*Ans)

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

// definition {{{ 1

// scaning {{{ 2
#define Scd(x) scanf("%d", &x)
#define Scd2(x,y) scanf("%d%d", &x, &y)
#define Scd3(x,y,z) scanf("%d%d%d", &x, &y, &z)

#define Scll(x) scanf("%llu", &x)
#define Scll2(x,y) scanf("%llu%llu", &x, &y)
#define Scll3(x,y,z) scanf("%llu%llu%llu", &x, &y, &z)

#define Scc(c) scanf("%c", &c);
#define Scs(s) scanf("%s", s);
#define Scstr(s) scanf("%s", &s);
// }}} 2

// constants {{{ 2
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
// }}} 2

// systems {{{ 2
#define Rep(x,y) for(int x = 0; x < y; x++)
#define Repe(x,y,z) for(int x = z; x < y; x++)
// }}} 2

// output {{{ 2
#define YesNo(a) (a)?printf("Yes\n"):printf("No\n");
// }}} 2

// }}} 1

int main() {

    int a,b,c;
    Scd3(a,b,c);
    
    priority_queue<int> q;

    q.push(a);
    q.push(b);
    q.push(c);


    int ans = 0;
    ans += q.top() * 10;
    q.pop();
    ans += q.top();
    q.pop();
    ans += q.top();
    q.pop();
    printf ("%d\n",ans );

    return 0;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
 
#define hell                         1000000007
#define hell2                        998244353
#define lcm(a,b)                     (a*b)/__gcd(a,b)
#define ll                           long long
#define vll                          vector<ll>
#define pll                          vector< pair<ll,ll> >
#define pb                           push_back
#define all(v)                       v.begin(),v.end()
#define F                            first
#define S                            second
#define rep(i,a,b)                   for(ll i=a;i<b;i++)
#define ret(x)                       return cout<<x,0;
#define endl                           '\n'
 
const ll MAX=500005;
const ll SQN=330;
const ll LG=22;
const double PI=atan(1)*4;
using namespace std;

ll n,m,q;
vector<pair<pair<ll,ll>,pair<ll,ll> > > v;
vll s;
ll f(ll pos, ll prev) {
	if(pos==n) {
		ll cost=0;
		rep(i,0,q) {
			if(s[v[i].F.S-1]-s[v[i].F.F-1]==v[i].S.F) cost+=v[i].S.S;
		}
		return cost;
	}
	ll ans=0;
	rep(i,max(1LL,prev),m+1) {
		s.pb(i);
		ans=max(ans,f(pos+1,i));
		s.pop_back();
	}
	return ans;
}

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

    cin >> n >> m >> q;
    rep(i,0,q) {
    	ll a,b,c,d;
    	cin >> a >> b >> c >> d;
    	v.pb({{a,b},{c,d}});
    }
    vll ans;
    cout << f(0,0);
}

Measured memory_bytes: 3660
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <bitset>
using namespace std;
int m[505][505],n;
bool allblack(int j){
	for(int i=1;i<=n;i++){
		if (m[i][j]==0)	return false;
	}
	return true;
}
int main(){
	std:ios::sync_with_stdio(false);
	cin>>n;
	for(int i=1;i<=n;i++){
		string temp;cin>>temp;
		for(int j=0;j<n;j++){
			m[i][j+1]=(temp[j]=='#'?1:0);
		}
	}

	bool noblack = true;
	for(int i=1;i<=n;i++){
		
		for(int j=1;j<=n;j++){
			if (m[i][j]==1)	noblack=false;
		}
	}
	if (noblack)	{puts("-1");return 0;}

	int minans=n*n+1000;
	for(int cr=1;cr<=n;cr++){
		int ans=0;

		
		bool mark=false;

		for(int i=1;i<=n;i++){
			if (m[i][cr]==1){mark=true;break;}
		}
		if (!mark){
			ans++;
		}

		for(int j=1;j<=n;j++){
			if (m[cr][j]==0)	ans++;
		}


		for(int j=1;j<=n;j++){
			if (!allblack(j))	ans++;
		}
		minans=min(minans,ans);
	}
	if (minans==n*n+1000)printf("-1\n");
	else printf("%d\n",minans);
	return 0;
}

Measured memory_bytes: 1408
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define pll pair<ll,ll>
#define x first
#define y second
#define f(i,a,b) for(ll i=a;i<b;i++)
#define rof(i,a,b) for(ll i=a;i>b;i--)
ll mod=1e9+7;

//cf dont use unordered map. use simply map<... , ... > m;

//They are Iterator minus v.begin() krna //lower_bound(v.begin(),v.end(),x)-v.begin()  //upper_bound(v.begin(),v.end(),x)-v.begin()
// lower bound tells greater than or equal to // upper bound tells strictly greater than
//int a[1001][1001] //aise global me hi// ll lcm(ll a, ll b){ return a / __gcd(a, b) * b; }
//memset can initialize to 0 or -1 ONLY //memset(str, 't', sizeof(str)); // string //memset(a, 0, sizeof(a));  //1D array    // memset(a,0,sizeof(a[0][0])*n*n); //2D array
// set.insert(),find() //for(auto it=set.begin();....) cout<<*it;   // sort(v.begin(),v.end(),compare)

void solve()
{
    long long int a,x,b,n,ans;cin>>a>>b>>n;
//n

ans=(a*n)/b - a*(n/b); 

f(i,1,sqrt(b-1)+1)
{
	if((b-1)%i==0)
	{
			//check i , b-1/i
		x=i;
		if(x<=n) ans=max(ans,(a*x)/b-a*(x/b));
		//if(ans==4) {cout<<i;break;}
		x=(b-1)/i;
		if(x<=n) ans=max(ans,(a*x)/b-a*(x/b));
		//if(ans==4) {cout<<(b-1)/i;break;}
	}

}
cout<<ans;
}

int main()
{
cout << fixed << setprecision(14);
ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    ll t=1;
    //cin>>t;
    while(t--)
    {
     solve();
    }
}

Measured memory_bytes: 3692
#include<iostream>
using namespace std;
int Rx[111111], Ry[111111], n, m, cnt;
int main() {
	cin >> n >> m; for (int i = 1; i <= n; i++) { Rx[i] = 1; }Ry[1] = 1;
	for (int i = 0; i < m; i++) {
		int a, b; cin >> a >> b;
		if (Ry[a] == 0) { Rx[a]--; Rx[b]++; }
		else {
			if (Rx[a] == 1) { Rx[a]--; Rx[b]++; Ry[a] = 0; Ry[b] = 1; }
			else { Rx[a]--; Rx[b]++; Ry[b] = 1; }
		}
	}
	for (int i = 1; i <= n; i++) { if (Ry[i] >= 1)cnt++; }
	cout << cnt << endl;
	return 0;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
     
    using namespace std;
    int main(){
      
    	int N;
      	cin>>N;
      	if( N % 1000 != 0){
			cout<< 1000 - (N % 1000)<<endl;
		}else{
			cout<<0<<endl;
		} 
      
      return 0;
      
    }


Measured memory_bytes: 3628
#include <iostream>
#include <algorithm>
using namespace std;
int main () {
    int N, M, cnt=0, x[32]={0, };
    cin >> N >> M;
    for (int i=0;i<N;i++){
        int a;
        cin >> a;
        for (int j=0;j<a;j++){
            int b;
            cin >> b;
            x[b-1]++;
        }
    }
    for (int i=0;i<30;i++){
        if (x[i]>=N)
            cnt++;
    }
    cout << cnt;
    return 0;
}

Measured memory_bytes: 256
# -*- coding: utf-8 -*-
"""
Created on Tue Jan 21 16:49:00 2020

@author: matsui
"""

   
def cost(h,N,K):
    dp=[0]*N
    dp[1]=abs(h[0]-h[1])
    for i in range(2,N):
        tmp=[abs(h[i]-h[j])+dp[j] for j in range(max(0,i-K),i)]
        dp[i]=min(tmp)
    return dp[-1]

N,K=map(int,input().split())
h=[int(num) for num in input().split()]

print(cost(h,N,K))

Measured memory_bytes: 13852
#087 B Coins
A =int(input())
B =int(input())
C =int(input())
X =int(input())
ans =0
for i in range(A+1):
    for j in range(B+1):
        for k in range(C+1):
            if 500 * i + 100 * j + 50 * k ==X:      
                ans+=1
print(ans)

Measured memory_bytes: 3060
#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
#define abdelrahman010 ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
typedef long long ll;
using namespace std;
const int N = 1e5 + 5;

int main() {
    abdelrahman010
    string s;
    cin >> s;
    char cur1 = '1' , cur2 = '0';
    int cnt1 = 0 , cnt2 = 0;
    for(auto &i : s) {
        cnt1 += (cur1 != i);
        cnt2 += (cur2 != i);
        if(cur1 == '0')
            cur1 = '1' , cur2 = '0';
        else
            cur1 = '0' , cur2 = '1';
    }
    cout << min(cnt1 , cnt2);
    return 0;
}

Measured memory_bytes: 3792
#include <iostream>
#include <vector>

using namespace std;

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


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

        vector<int> answer(n);
        for (int i = 0; i < n; i++) answer[a[i] - 1] = i + 1;

        for (int i = 0; i < n; i++) cout << answer[i] << " ";
        return (0);
}

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

Al = list(map(int, input().split()))
Bl = list(map(int, input().split()))
Cl = list(map(int, input().split()))


ans = 0
prev = -1
for foodIndex in Al:
    ans += Bl[foodIndex-1]
    if foodIndex == prev + 1:
        ans += Cl[foodIndex-2]
    prev = foodIndex

print(ans)

Measured memory_bytes: 3060
#include <iostream>
#include <vector>
#include <string>
using namespace std;
typedef pair <int,string> P;
vector <int> rep[1001];
string str[1001];
int n;
void saiki(string ten, int ima) {
  for(int i=0;i<rep[ima].size();i++) {
    cout << ten << str[rep[ima][i]] << endl;
    saiki(ten+'.',rep[ima][i]);
  }
}
int main() {
  cin >> n;
  for(int i=1;i<=n;i++) {
    int a;
    cin >>a >> str[i];
    rep[a].push_back(i);
  }
  saiki("",0);
    
  return 0;
}

Measured memory_bytes: 2244
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define rrep(ri,n) for(int ri = (int)(n-1); ri >= 0; ri--)
#define rep2(i,x,n) for(int i = (int)(x); i < (int)(n); i++)
#define repit(itr,x) for(auto itr = x.begin(); itr != x.end(); itr++)
#define rrepit(ritr,x) for(auto ritr = x.rbegin(); ritr != x.rend(); ritr++)
#define ALL(x) x.begin(), x.end()
using ll = long long;
using namespace std;

const int INF = 1001001001;

int main(){
  int n, m;
  cin >> n >> m;
  vector<vector<int>> d(n, vector<int>(n, INF));
  rep(i, n) d.at(i).at(i) = 0;
  vector<tuple<int, int, int>> edge(m);
  rep(i, m){
    int a, b, c;
    cin >> a >> b >> c;
    a--; b--;
    d.at(a).at(b) = c;
    d.at(b).at(a) = c;
    edge.at(i) = make_tuple(a, b, c);
  }
  rep(k, n)rep(i, n)rep(j, n)d.at(i).at(j) = min(d.at(i).at(j), d.at(i).at(k) + d.at(k).at(j));
  // rep(i, n){
  //   rep(j, n){
  //     int o;
  //     if(d.at(i).at(j) == INF) o = -1;
  //     else o = d.at(i).at(j);
  //     cerr << o << " ";
  //   }
  //   cerr << endl;
  // }
  int ans = 0;
  rep(i, m){
    int a, b, c;
    tie(a, b, c) = edge.at(i);
    bool add = true;
    rep(j, n){
      rep(k, n){
        int f = d.at(j).at(k);
        int g = c;
        g += d.at(j).at(a);
        g += d.at(b).at(k);
        // cerr << i << " " << j << " " << k << " " << f << " " << g << endl;
        if(f == g) add = false;
      }
    }
    if(add == true) ans++;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
n = int(input())

Nmax = 55555
f = [-1 for i in range(Nmax)]

for i in range(2,Nmax):
    if f[i]==-1:
        f[i]=True
        for j in range(i+i,Nmax,i):
            f[j] = False

f[0]=False
f[1]=False
lis = []
for i in range(1,6000):
    nu = i*10+1
    if nu<=Nmax and f[nu]==True:
        lis.append(nu)

    if len(lis)>=n:
        break

print(*lis)


Measured memory_bytes: 43376
// https://atcoder.jp/contests/abc163/tasks/abc163_d

use proconio::fastout;
use proconio::input;

const MOD: usize = 1000000007;

#[fastout]
fn main() {
    input! { n: usize, k: usize, }
    let ans = (k..=n + 1).fold(0usize, |acc, i| (acc + i * (1 + n - i) + 1) % MOD);
    println!("{}", ans);
}


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

int main()
{
  int n;
  cin >> n;
  vector<int> a(n);
  int i;
  int count = 0;
  for(i = 0; i < n; i++)
  {
    cin >> a.at(i);
  }
  vector<bool> judge(1000000001, false);
  for(i = 0; i < n; i++)
  {
    if(judge.at(a.at(i)) == false)
    {
      judge.at(a.at(i)) = true;
    }
    else if(judge.at(a.at(i)) == true)
    {
      judge.at(a.at(i)) = false;
    }
  }
  for(i = 0; i <= 1000000000; i++)
  {
    if(judge.at(i) == true) count++;
  }
  cout << count << endl;
}


Measured memory_bytes: 122880
#include <stdio.h>

int main(void){
  int N;
  long double x, sum = 0.0;
  char u[3]; 
  scanf("%d", &N);
  
  for(int i = 0; i < N; i++){
    scanf("%Lf" "%s", &x, u);
    if(u[0] == 'B'){
      sum += x * 380000.0;
    }else {
      sum += x;
    }
  }
  printf("%Lf\n", sum);
  return 0;;
}

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

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

  ll ans = 0;
  for (int i = 0; i < s.length(); i++) {
    if (s.at(i) != t.at(i)) ans++;
  }
  cout << ans << endl;
}


Measured memory_bytes: 3864
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<random>
#include<set>
#include<map>
#include<functional>
using namespace std;
#define int long long
#define inf 1145141919
#define rep(i,n) for(int i=0;i<n;i++)
typedef pair<int, int>P;
typedef pair<int, P> PP;
struct edge { int to, cost; };
int a[101];
signed main() {
	int n, x; cin >> n >> x; rep(i, n)cin >> a[i];
	sort(a, a + n);
	int ans = 0;
	for (int i = 0; i < n;i++) {
		if (x >= a[i]) {
			ans++;
			x -= a[i];
		}
	}
	if (x&&ans == n)ans--;
	cout << ans << endl;
}

Measured memory_bytes: 256
#include <stdio.h>
int main() {
  int n;
  scanf("%d", &n);
  if ((n - 2) % 10 == 0) {
    printf("hon");
  }
  if ((n - 4) % 10 == 0) {
    printf("hon");
  }
  if ((n - 5) % 10 == 0) {
    printf("hon");
  }
  if ((n - 7) % 10 == 0) {
    printf("hon");
  }
  if ((n - 9) % 10 == 0) {
    printf("hon");
  }
  if ((n - 0) % 10 == 0) {
    printf("pon");
  }
  if ((n - 1) % 10 == 0) {
    printf("pon");
  }
  if ((n - 6) % 10 == 0) {
    printf("pon");
  }
  if ((n - 8) % 10 == 0) {
    printf("pon");
  }
  if ((n - 3) % 10 == 0) {
    printf("bon");
  }
  return 0;
}

Measured memory_bytes: 1704
n, m, k = map(int, input().split())
li = []
for t in range(n):
    li.append(list(map(int, input().split())))
price_list = []
for bit in range(1, 2**n):
    index_list = []
    for i in range(n):
        if bit & 1<<i:
            index_list.append(i)

    c = 0
    for t in range(1,m+1):
        s = 0
        for i in index_list:
            s += li[i][t]
        if s >= k:
            c += 1
        else:
            break

    if c == m:
        p = 0
        for i in index_list:
            p += li[i][0]
        price_list.append(p)

if len(price_list):
    print(min(price_list))
else:
    print('-1')
        


Measured memory_bytes: 9136
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxn 105
#define ll long long
#define ld double
#define mod 998244353
using namespace std;
char inp[3][maxn];
int main()
{
	int n;
	scanf("%d", &n);
	for(int i = 0; i < 3; i++)
		scanf("%s", inp[i]);
	int res = 0;
	for(int j = 0; j < n; j++)
	{
		int ns[26];
		memset(ns, 0, sizeof(ns));
		int ans = 0;
		for(int l = 0; l < 3; l++)
			if(!ns[inp[l][j] - 'a'])
				ans++, ns[inp[l][j] - 'a'] = 1;
		res += ans - 1;
	}
	printf("%d\n", res);
	return 0;
}

Measured memory_bytes: 256
import java.util.*;


public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		int m = sc.nextInt();
		int a[] = new int[n+1];
		for(int i = 0; i < m; i++){
		    a[sc.nextInt()] = 1;
    }
		long result = 0;
		long[] dp = new long[n+1];
		for(int i = 1; i < n+1; i++){
		    if(a[i] == 1) dp[i] = 0;
            else if(i == 1)dp[i] = 1;
            else if(i == 2)
                dp[i] = dp[i-1]+1;
            else{
            dp[i] = dp[i-1] + dp[i-2];
            dp[i]%=1000000007;
		    }
    }
		System.out.println(dp[n]);
		
	}
}


Measured memory_bytes: 49080
#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
const int INF=1e9,MOD=1e9+7,ohara=1e6+10;
const ll LINF=1e18;
using namespace std;
    
#define rep(i,n) for(ll (i)=0;(i)<(int)(n);(i)++)
#define rrep(i,a,b) for(ll i=(a);i<(b);i++)
#define rrrep(i,a,b) for(ll i=(a);i>=(b);i--)
#define all(v) (v).begin(), (v).end()
#define Size(n) (n).size()
#define Cout(x) cout<<(x)<<endl
#define doublecout(a) cout<<fixed<<setprecision(15)<<a<<endl;
#define Cerr(x) cerr<<(x)<<endl
#define fi first
#define se second
#define P pair<ll,ll> 
#define m_p make_pair
#define V vector<ll> 
#define U_MAP unordered_map<ll,ll>
#define pq priority_queue<ll>
#define rpq priority_queue<ll,vector<ll>,greater<ll>>
#define p_b push_back
    
ll n,cnt,ans,a,b,c,d,tmp,tmpp,m,h,w,x,y,sum,pos,k,q;
ld doua;
int dy[]={1,0,-1,0};
int dx[]={0,1,0,-1};
//int dy[]={-1,0,1,-1,1,-1,0,1};
//int dx[]={-1,-1,-1,0,0,1,1,1};
string alph("abcdefghijklmnopqrstuvwxyz"),s;
bool fl;
struct edge{int to,cost;};
    
//------ Believe yourself as a genius!!!!!! ------
    
int main(void){
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    
    cin>>s;
    rep(i,Size(s)-1){
        if(s[i]==s[i+1]){
            cout<<i+1<<" "<<i+2<<"\n";
            return 0;
        }
    }
    rep(i,Size(s)-2){
        if(s[i]==s[i+2]){
            cout<<i+1<<" "<<i+3<<"\n";
            return 0;
        }
    }
    cout<<"-1 -1\n";
    return 0;
}

Measured memory_bytes: 512
// lcmとかはg++ -std=c++17 default.cppみたいなかんじで
//vector<vector<ll>> piyo(tate,vector<ll> (yoko));

#include <bits/stdc++.h>
#define mod 1000000007
#define INF 1000000000
#define ll long long
#define ln cout<<endl;
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl
#define double long double
#define REP(i,m,n) for(ll i=(ll)(m);i<(ll)(n);i++)
#define rep(i,n) REP(i,0,n)
using namespace std;
ll target;

int main() {
    cin.tie(0);
   	ios::sync_with_stdio(false);
    //double mini=INF;
    ll maxi=0,f=0,sum=0,mini=INF;
    string str,str1,str2;
    ll i;
    double h;
    ll n,x,m;
    ll a,b,d,c;
    //multiset<pair<string,ll>> s;
    cin>>n;
    vector<ll> v(n);
    vector<ll> w(n);
    rep(i,n) cin>>v[i];
    rep(i,n) w[i]=v[i];
    sort(v.begin(),v.end());
    mini=v[v.size()/2-1];
    maxi=v[v.size()/2];
    rep(i,n){
        if(w[i]<=mini) cout<<maxi<<endl;
        else  cout<<mini<<endl;
    }

    return 0;
}


Measured memory_bytes: 5376
X  = int(input())
a = X // 100
b = X % 100

if X < 100:
    print(0)
    exit()

if b == 0:
    print(1)
    exit()

for n in [5,4,3,2,1,0]:
    if a == 0:
        print(0)
        exit()

    tmp = b // n
    
    b -= min(a, tmp)*n
    a -= min(a, tmp)

    if b == 0:
        print(1)
        exit()


Measured memory_bytes: 3064
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
total = 0
for i in range(n):
    if a[i] > b[i]:
        total += b[i]
    else:
        total += a[i]
        b[i] -= a[i]
        if a[i+1] > b[i]:
            a[i+1] -= b[i]
            total += b[i]
        else:
            total += a[i+1]
            a[i+1] = 0

print(total)


Measured memory_bytes: 18476
#include <stdio.h>
#define N 8

int row[N],col[N],dpos[2*N-1],dneg[2*N-1],board[N][N];
void Q_print(void);
void Q_place(int);

int main(){
  int n,r,c,i,j;
  scanf("%d",&n);
  for(i=0;i<N;i++){
    row[i]=0;
    col[i]=0;
  }
  for(i=0;i<2*N-1;i++){
    dpos[i]=0;
    dneg[i]=0;
  }
  for(i=0;i<n;i++){
    scanf("%d%d",&r,&c);
    board[r][c]=1;
  }
  Q_place(0);
  return 0;
}
	
void Q_place(int i){
  int j,k,flag;
  if(i==N){
    flag=0;
    for(j=0;j<N;j++){
      for(k=0;k<N;k++){
	if(board[j][k]){
	  if(row[j]!=k) flag=1; 
	}
      }
    }
    if(flag) j=N;
    else j=0;
    for(;j<N;j++){
      for(k=0;k<N;k++){
	if(row[j]==k) printf("Q");
	else printf(".");
      }
      printf("\n");
    }
    return;
  }
  for(j=0;j<N;j++){
    if(col[j]==1 ||
       dpos[i+j]==1 ||
       dneg[i-j+N-1]==1) continue;
    row[i]=j;
    col[j]=dpos[i+j]=dneg[i-j+N-1]=1;
    Q_place(i+1);
    row[i]=col[j]=dpos[i+j]=dneg[i-j+N-1]=0;
  }
}

    
    
    
  
  
  
  
    
  



Measured memory_bytes: 2148
#include <string>
#include <queue>
#include <stack>
#include <vector>
#include <sstream>
#include <algorithm>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <list>
#include <cstdio>
#include <iostream>
#include <cmath>
#include <climits>
#include <bitset>
#include <functional>
#include <numeric>
#include <ctime>
#include <cassert>
#include <cstring>
#include <fstream>

using namespace std;
const int MOD = 1e9 + 7;

int invtable[200001];

int power(int n, int p) {
    if (p == 0)
        return 1;
    long long res = 1;
    long long add = n;
    while (p > 0) {
        if (p & 1)
            res = (res * add) % MOD;
        p >>= 1;
        add = add*add%MOD;
    }
    return res;
}

int getinv(int n) {
    if (invtable[n])
        return invtable[n];
    return invtable[n] = power(n, MOD - 2);
}

int comb(int n, int r) {
    long long res = 1;
    for (int i = 1; i <= n; i++)
        res = (res *i) % MOD;
    for (int i = 1; i <= n - r; i++)
        res = (res * getinv(i)) % MOD;
    for (int i = 1; i <= r; i++)
        res = (res * getinv(i)) % MOD;

    return res;
}

int main() {
    int h, w, a, b;
    cin >> h >> w >> a >> b;

    long long res = 0;
    long long base1, base2;
    long long n1 = h - a + b - 1, n2 = w - b + a - 2;
    base1 = comb(n1, h - a - 1);
    base2 = comb(n2, a - 1);
    for (int i = 1; i <= w - b; i++) {
        res = (res + base1*base2) % MOD;
        base1 = (((base1*(n1 + 1)) % MOD)*getinv(n1 - h + a + 2)) % MOD;
        n1++;
        base2 = (((base2*(n2 - a + 1)) % MOD)*getinv(n2)) % MOD;
        n2--;
    }
    cout << res << endl;



    return 0;
}

Measured memory_bytes: 896
using System;
using System.Text;
using System.Linq;
using System.Collections;
using System.Threading.Tasks;
using System.Collections.Generic;
using System.Runtime.InteropServices;
using static System.Console;
using static System.Math;

namespace NotFounds
{
    public class Program
    {
        public static void Main(string[] args)
        {
            new Program().Solve();
        }

        public void Solve()
        {
            MyInputStream cin = new MyInputStream();

            var s = ReadLine();
            var l = s.IndexOf("A");
            var r = s.LastIndexOf("Z");
            WriteLine(r - l + 1);
        }
    }

    public static class MyExtensions
    {
        public static string Reverse(this string sourse)
        {
            char[] chrAry = sourse.ToCharArray();
            Array.Reverse(chrAry);
            return new string(chrAry);
        }
    }

    public class MyInputStream
    {
        private char separator = ' ';
        private Queue<string> inputStream;
        public MyInputStream(char separator = ' ')
        {
            this.separator = separator;
            inputStream = new Queue<string>();
        }

        public string Read()
        {
            if (inputStream.Count != 0) return inputStream.Dequeue();
            string[] tmp = Console.ReadLine().Split(separator);
            for (int i = 0; i < tmp.Length; i++)
            {
                inputStream.Enqueue(tmp[i]);
            }
            return inputStream.Dequeue();
        }
        public string ReadLine() => Console.ReadLine();
        public int ReadInt() => int.Parse(Read());
        public long ReadLong() => long.Parse(Read());
        public double ReadDouble() => double.Parse(Read());
    }

    public class Pair<T1, T2>
    {
        public T1 First;
        public T2 Second;
        public Pair() { First = default(T1); Second = default(T2); }
        public Pair(T1 f, T2 s) { First = f; Second = s; }
        public override string ToString() { return "(" + First + ", " + Second + ")"; }
        public override int GetHashCode() { return First.GetHashCode() ^ Second.GetHashCode(); }
        public override bool Equals(object obj)
        {
            if (ReferenceEquals(this, obj)) return true;
            else if (obj == null) return false;
            var tmp = obj as Pair<T1, T2>;
            return (object)tmp != null && First.Equals(tmp.First) && Second.Equals(tmp.Second);
        }
    }

    #region HashMap
    public class HashMap<K, V> : Dictionary<K, V>
    {
        public HashMap() : base() { }
        public HashMap(int cap) : base(cap) { }
        public HashMap(IDictionary<K, V> dictionary) : base(dictionary) { }
        new public V this[K i]
        {
            get
            {
                V v;
                return TryGetValue(i, out v) ? v : base[i] = default(V);
            }
            set { base[i] = value; }
        }
    }
    #endregion
}


Measured memory_bytes: 14176