akhauriyash/Code-Regression huggingface dataset:
n = gets.to_i
ps = gets.split.map(&:to_i)

answer = 0

(0...n).each do |i|
  next if ps[i] != i + 1

  answer += 1
  ps[i], ps[i + 1] = ps[i + 1], ps[i]
end

answer += 1 if ps[n - 1] == n

puts answer


Measured memory_bytes: 21904
#include <algorithm>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <math.h>
#include <string>
#include <cmath>
//#include <vector>
//#include <time.h>
#include <queue>
//#include <stack>
//#include <map>
//#include <set>
using namespace std;
typedef long long ll;
typedef long double ld;
int a[10000];
int main()
{
    int n;
    cin>>n;
    a[n]++;
    cin>>n;
    a[n]++;
    cin>>n;
    a[n]++;
    if(a[5]==2&&a[7]==1)
        cout<<"YES";
    else
        cout<<"NO";
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
using ll = long long;
using p = pair<int,int>;
int cnt_five=0,cnt_seven=0;
void judge(int n){
    if(n==5)cnt_five++;
    else if(n==7)cnt_seven++;
}
int main(int argc, const char * argv[]) {



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

    int a,b,c;
    cin>>a>>b>>c;
    judge(a);
    judge(b);
    judge(c);
    if(cnt_five==2&&cnt_seven==1)cout<<"YES"<<endl;
    else cout<<"NO"<<endl;

    return 0;
}


Measured memory_bytes: 3636
#include <cstdio>
#define scanf __builtin_scanf

const long mod=1e9+7;
long dp[100010], f[100010];

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

    dp[0]=1;
    for(int i=0; i<n; ++i) {
        if (!f[i+1]) (dp[i+1]+=dp[i])%=mod;
        if (!f[i+2]) (dp[i+2]+=dp[i])%=mod;
    }
    printf("%ld\n", dp[n]);
}


Measured memory_bytes: 1664
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;

namespace ConsoleApplication2 {
    class Program {
        static void Main(string[] args) {

            TextReader input = Console.In;

            string str = "";

            while((str = input.ReadLine()) != null) {
                // スペースで区切る
                string[] works = str.Split(' ');
                // 6 個でない場合
                if (works.Length != 6) {
                    continue;
                }
                double a, b, c, d, e, f;
                if (!double.TryParse(works[0], out a)) {
                    continue;
                }
                if (!double.TryParse(works[1], out b)) {
                    continue;
                }
                if (!double.TryParse(works[2], out c)) {
                    continue;
                }
                if (!double.TryParse(works[3], out d)) {
                    continue;
                }
                if (!double.TryParse(works[4], out e)) {
                    continue;
                }
                if (!double.TryParse(works[5], out f)) {
                    continue;
                }
                double x = (b * f - e * c) / (b * d - e * a);
                double y = (a * f - c * d) / (a * e - b * d);
                Console.WriteLine(x.ToString("0.000") + " " + y.ToString("0.000"));
            }
        }
    }
}

Measured memory_bytes: 5832
#!/usr/bin/env python3

import sys
input=sys.stdin.readline

n,q=map(int,input().split())
left=n
up=n
ans=(n-2)*(n-2)
fixed_yoko=[0]*(n+1)
fixed_tate=[0]*(n+1)
post_process=[]
for _ in range(q):
    t,x=map(int,input().split())
    if t==1:
        if x>left:
            post_process.append((t,x))
        else:
            fixed_yoko[left]+=-up
            fixed_yoko[x+1]+=up
            ans-=up-2
            left=x
    elif t==2:
        if x>up:
            post_process.append((t,x))
        else:
            fixed_tate[up]+=-left
            fixed_tate[x+1]+=left
            ans-=left-2
            up=x
for i in range(1,n+1):
    fixed_yoko[i]+=fixed_yoko[i-1]
    fixed_tate[i]+=fixed_tate[i-1]
for t,x in post_process:
    if t==1:
        ans-=fixed_yoko[x]-2
    elif t==2:
        ans-=fixed_tate[x]-2
print(ans)

Measured memory_bytes: 86196
n = gets.to_i
a = gets.split().map(&:to_i).sort
b = gets.split().map(&:to_i).sort
c = gets.split().map(&:to_i).sort

ans = 0

b.each do |i|
  small = a.bsearch_index { |x| x >= i } 
  big = c.bsearch_index { |x| x > i }
  ans += (small ? small : a.size) * (big ? n - big : 0)
end

puts ans

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

#define rep(i,n) for(int (i) = 0;(i) < (n);(i)++)
using namespace std;

int main(){
  	int n,m,memo = 0,ans = 0;
  
  	cin >> n;
  	string s[n];
  	rep(i,n) cin >> s[i];
  
  	cin >> m;
  	string t[m];
  	rep(i,m) cin >> t[i];
  
  	rep(i,n){
      memo = 0;
      rep(j,n){
        if(s[i] == s[j]){
          memo++;
        }
      }
      rep(j,m){
        if(s[i] == t[j]){
          memo--;
        }
      }
  
  	 ans = max(memo,ans);
    }

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

Measured memory_bytes: 256
import java.util.*;
import java.util.stream.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int mod = (int)1e9 + 7;
        int n = sc.nextInt();
        if (n == 1) {
            System.out.println(1);
        } else if (n % 2 == 0) {
            System.out.println(0.5);
        } else {
            System.out.println((n/2+1)/(double)n);
        }
    }

}


Measured memory_bytes: 23252
//#include <bits/stdc++.h>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <fstream>
#include <string.h>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <queue>
#include <math.h>
#include <assert.h>
#define ff first
#define ss second
#define ll long long
#define mod 998244353
using namespace std;
int n, m, d[109][109];
char c[109][109];
int main () {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>c[i][j];
    for(int i=n;i>=1;i--) {
        for(int j=m;j>=1;j--) {
            if(c[i][j] == '.') {
                if(i == n) {
                    if(j == m) {
                        d[i][j] = 0;
                        continue;
                    }
                    d[i][j] = d[i][j + 1];
                }
                else {
                    if(j == m) {
                        d[i][j] = d[i + 1][j];
                        continue;
                    }
                    d[i][j] = min(d[i][j + 1], d[i + 1][j]);
                }
            }
            else {
                if(i == n) {
                    if(j == m) {
                        d[i][j] = 1;
                        continue;
                    }
                    if(c[i][j + 1] == '#')
                        d[i][j] = d[i][j + 1];
                    else
                        d[i][j] = d[i][j + 1] + 1;
                }
                else {
                    if(j == m) {
                        if(c[i + 1][j] == '#')
                            d[i][j] = d[i + 1][j];
                        else
                            d[i][j] = d[i + 1][j] + 1;
                        continue;
                    }
                    int val1 = d[i][j + 1];
                    if(c[i][j + 1] == '.')
                        val1++;
                    int val2 = d[i + 1][j];
                    if(c[i + 1][j] == '.')
                        val2++;
                    d[i][j] = min(val1, val2);
                }
            }
        }
    }
    cout<<d[1][1];
}
 
 /*
  a abb bab abc
 6
 q
 bcc
 aza
 abc
 z
 def
  */


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define forx(i,j,n) for(int i=j;i<n;i++)
#define MOD 1000000007
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vi vector<int>
#define vl vector<ll>
#define vii vector<pii>
#define vll vector<pll>
#define vvi vector<vi>
#define vvl vector<vl>
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define fastio ios_base::sync_with_stdio(false)
#define testcase int t; cin>>t
#define inputi(xx) scanf("%d",&xx)
#define inputll(xx) scanf("%lld",&xx)
#define printi(xx) printf("%d",xx)
#define printll(xx) printf("%d",xx)

ll fun(ll a,ll b,ll c){
    ll ans=0;
    ans+=b/c;
    ans-=a/c;
    if(a%c==0) ans++;
    return ans;
}

int main() {
    ll n;
    cin>>n;
    vll a(n);
    forx(i,0,n) cin>>a[i].s>>a[i].f;
    sort(all(a));
    ll tt=0;
    int flg=0;
    forx(i,0,n){
        tt+=a[i].s;
        if(tt>a[i].f)flg=1;
    }
    if(flg==1) cout<<"No";
    else cout<<"Yes";
	return 0;
}

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

int main()
{
  int s[1000000];
  cin >> s[0];
  
  ll ans = 0;
  ll i = 0;
  while(1){
    if(s[i] % 2 == 0){
      s[i+1] = s[i] / 2;
    }else{
      s[i+1] = s[i] * 3 + 1;
    }
    i++;
    for(int j = 0; j < i; j++){
      if(s[j] == s[i]){
        ans = i;
        break;
      }
    }
    if(ans > 0){
      break;
    }
  }//while
  
  cout << ans + 1 << endl;
}

Measured memory_bytes: 3612
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int mod = 1000000007;

int main() {
    ios::sync_with_stdio(false);
    int n, a[100005] = {};
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    sort(a + 1, a + n + 1);
    cout << a[n / 2 + 1] - a[n / 2];
}


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

int main(){
  ll x, y, a, b, c;
  cin >> x >> y >> a >> b >> c;
  vector<ll> p(a), q(b), r(c);
  rep(i,a) cin >> p[i];
  rep(i,b) cin >> q[i];
  rep(i,c) cin >> r[i];
  sort(p.rbegin(),p.rend());
  sort(q.rbegin(),q.rend());
  vi kouho;
  rep(i,x) kouho.push_back(p[i]);
  rep(i,y) kouho.push_back(q[i]);
  rep(i,c) kouho.push_back(r[i]);
  sort(kouho.rbegin(),kouho.rend());
  ll ans=0;
  rep(i,x+y) ans += kouho[i];
  cout << ans << endl;
}


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

int main(){
    string s;

    cin >> s;

    for (int i=0; i < s.length()-1;i++){
        if (s[i]=='A'){
            if (s[i+1]=='C'){
                cout << "Yes"<<endl;
                return 0;
            }
        }
    }
    cout << "No"<<endl;

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
using ll = long long;

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

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

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

    //最小値がQ個あればそれを選び続ければいい
    //2回目の操作で何が変わるか そこを含むとき選択範囲が広くなる？
    //10を基準に、10を取り、10以上のものしか取らないとしたら？
    //10未満のものに印を付け、そこに触れないよう

    vector<int> b(n), c(n);

    int r = 1 << 30;
    for (int j = 0; j < n; j++) {
        int t = a[j + 1];
        int i0 = 0, i1 = 0;
        int l = 0;
        for (int i = 0; i < n + 2; i++) {
            if (a[i] < t) {
                if (i > 0) {
                    i1 = i;
                    int x = i1 - i0;
                    if (x >= k) {
                        for (int i = 0; i < x; i++) {
                            c[i] = a[i0 + i];
                        }
                        sort(c.begin(), c.begin() + x);
                        for (int i = 0; i <= x - k; i++) {
                            b[l++] = c[i];
                        }
                    }
                }
                i0 = i + 1;
            }
        }
        if (l >= q) {
            sort(b.begin(), b.begin() + l);
            r = min(r, b[q - 1] - b[0]);
        }
    }

    cout << r << endl;

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
map<char, int> letters;
string s;
bool flag = true;
int main() {
	cin>>s;
	for(int i = 0; i < s.size(); i++) {
		letters[s[i]]++;
	}
	if(letters.size() != 2)	flag = false;
	else {
		for (auto it=letters.begin(); it!=letters.end(); ++it) {
			if(it -> second != 2) {
				flag = false;
				break;
			}
		}
	}
	puts((flag) ? "Yes" : "No");
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define PI 3.14159265358979323846264338327
#define NUM 1000000007
#define ss second
#define ff first
using namespace std;
vector <int> s[11];
int n,m,k, p[11], cnt[11], x;
set <int> S;
int ans;
void go(int x){
	if (x == n){
		bool ok = true;
		for (int i = 0; ok && i < m; i++)
			if (cnt[i] % 2 != p[i])
				ok = false;
		if (ok) ans++;
	}
	else{
		for (int i = 0;i < (int) s[x].size(); i++)
			cnt[s[x][i]]++;
		go(x + 1);
		for (int i = 0;i < (int) s[x].size(); i++)
			cnt[s[x][i]]--;
		go(x + 1);
	}
}
int main(){
	ios::sync_with_stdio(0);
	cin >> n >> m;
	for (int i = 0; i < m; i++){
		cin >> k;
		for (int j = 0; j < k; j++){
			cin >> x;
			s[x - 1].push_back(i);
		}
	}
	memset(cnt, 0, sizeof(cnt));
	ans = 0;
	for (int i = 0; i < m; i++)
		cin >> p[i];
	go(0);
	cout << ans <<"\n";
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int e[501][501];
void dfs(int l,int r,int col)
{
	if(l==r) return;
	int mid=(l+r)/2;
	for(int i=l;i<=mid;i++)
		for(int j=mid+1;j<=r;j++)
			e[i][j]=col,e[j][i]=col;
	dfs(l,mid,col+1);
	dfs(mid+1,r,col+1);
}
signed main()
{
	int n;
	scanf("%d",&n);
	dfs(1,n,1);
	for(int i=1;i<n;i++)
	{
		for(int j=i+1;j<=n;j++)
			printf("%d ",e[i][j]);
		printf("\n");
	}
    return 0;
}

Measured memory_bytes: 1408
#include <bits/stdc++.h>
#include <math.h>
#define _GLIBCXX_DEBUG
using namespace std;
int main() {
  
  int D,N;
  cin>>D>>N;
  
  if(D==0&&N==100){
    cout<<101<<endl;
  }
  else if(D==1&&N==100){
    cout<<10100<<endl;
  }
  else if(D==2&&N==100){
    cout<<1010000<<endl;
  }
  else{  
  cout<<pow(100,D)*N<<endl;
  }
}


Measured memory_bytes: 3876
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a; i< (int)(b); ++i)
using ll=long long;
using namespace std;
const auto mod=1e9+7;


int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(20);
 
 string s,t; cin >> s >> t;
 cout << t+s << endl;

  
 
}

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

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define MAXN 100001

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

int main() {
    int ans=0;
    string s;
    cin >> s;
    for(int i=0; i<4; i++) {
        if (s[i] == '+') ans ++;
        else ans --;
    }
    cout << ans << endl;

}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String head;
		try {
			head = br.readLine();
		} catch (IOException e) {
			System.err.println("The input is missing. " + e.getMessage());
			return;
		}

        int n;
        try {
        	n= Integer.parseInt(head);
        } catch(NumberFormatException e) {
			System.err.println("The input is in an illegal form. " + e.getMessage());
			return;
        }

        System.out.println(n*n*n);
    }
}

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

int a[500],x,c;
int t[500],u[500];
vector<int> G[500];

void init(){
  for(int i=0;i<500;i++){
    G[i].clear();
    u[i]=0;
  }
}

int main(){
  int Tc;
  cin>>Tc;
  while(Tc--){
    init();
    a[0]=1,x=1;
    cin>>t[1];
    c=1;

    while(1){
      if(x==0){
	int q;
	cin>>q;
	assert(q==0);
	break;
      }
      int p=a[--x],q;

      if(t[p]>0&&t[p]==(int)G[p].size()){
	//cout<<p<<'-'<<endl;
	continue;
      }else{
	//cout<<p<<endl;
      }

      cin>>q;
      if(q==0)break;
      
      if(q>0){
	t[++c]=q;
	G[p].push_back(c);
	G[c].push_back(p);
	a[x++]=p;
	a[x++]=c;
      }else{
	/*
	cout<<p<<' '<<q<<' '<<x<<' '<<a[x+q]<<endl;
	for(int i=0;i<x;i++)cout<<a[i]<<'=';cout<<endl;
	*/
	G[p].push_back(a[x+q]);
	G[a[x+q]].push_back(p);
	if((int)G[p].size()<t[p])a[x++]=p;
      }
    }

    for(int i=1;G[i].size();i++){
      cout<<i;
      sort(G[i].begin(),G[i].end());
      for(int j=0;j<(int)G[i].size();j++)
	cout<<' '<<G[i][j];
      cout<<endl;
    }
  }
  return 0;
}

Measured memory_bytes: 1252
X=int(input())
SUP=2*(10**5)
P=[True for i in range(2*(10**5))]
k=2
while k<SUP:
    if P[k]:
        for x in range(2*k,SUP,k):
            P[x]=False
    k+=1
ans=X
while not P[ans]:
    ans+=1
print(ans)


Measured memory_bytes: 4760
#include <bits/stdc++.h>
#include <algorithm>
#include <functional>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#define DEBUG
#define PI 3.141592653589793238462643383279
 
#define _GLIBCXX_DEBUG
#ifdef DEBUG
#define s(...) show(__VA_ARGS__);
#define sl(...) show(__VA_ARGS__);cout<<endl;
#else
#define s(...)
#define sl(...)
#endif
void show() {}
template <class Head,class... Args>void show(Head t,Args... args){std::cout<<t<<" ";show(args...);}
#define REP(i, n) for(ll i = 0; i < n; i++)
#define REPR(i, n) for(ll i = n; i >= 0; i--)
#define FOR(i, m, n) for(ll i = m; i < n; i++)
#define REP1(i, n) for(ll i = 1; i <= n; i++)
#define REPR1(i, n) for(ll i = n; i >= 1; i--)
#define FOR1(i, m, n) for(ll i = m; i <= n; i++)
const ll INF = LLONG_MAX;
const ull MOD = 1000000007;
#define VEC(type,A,N) vector<type> A(N)
#define VECi(type,A,N,i) vector<type> A(N,i)
#define VEC2(type,A,N,M) vector<vector<type>> A(N,vector<type>(M))
#define VEC2i(type,A,N,M,i) vector<vector<type>> A(N,vector<type>(M,i))
#define ALL(v) v.begin(), v.end()
ll frac(ll k){
    int s = 1;
    for (ll i=1; i<=k; ++i)s *= i;
    return s;
}
ll gcd(ll a, ll b){
   if (a%b==0)return(b);
   else return(gcd(b, a%b));
}
ll lcm(ll a,ll b){
    return a*b/gcd(a,b);
}
ll antidiv(ll N,ll C,ll D){
    return N-floor(N/C)-floor(N/D)+floor(N/lcm(C,D));
}
vector<ll> yakusuu(ll N){
    vector<ll> ret;
    for (ll i = 1; i * i <= N; i++) {
        if (N % i == 0) {
            ret.push_back(i);
            if (i * i != N) ret.push_back(N / i);
        }
    }
    sort(ret.begin(), ret.end());
    return ret;
}
ll digitPoor(ll n)
{
    assert(INT_MAX == 2147483647);
    assert(n >= 0);

    if (n < 10)         return 1;
    if (n < 100)        return 2;
    if (n < 1000)       return 3;
    if (n < 10000)      return 4;
    if (n < 100000)     return 5;
    if (n < 1000000)    return 6;
    if (n < 10000000)   return 7;
    if (n < 100000000)  return 8;
    if (n < 1000000000) return 9;
    return 10;
}
struct p{
  ll x;
  bool end;
};

int main(){
    ll N;
    cin>>N;
    
    map<char,ll> m;
    m['M']=0;
    m['A']=0;
    m['R']=0;
    m['C']=0;
    m['H']=0;
    REP(i,N){
        string t;
        cin>>t;
        m[t[0]]++;
    }
    
    cout<<m['M']*m['A']*m['R']+m['M']*m['A']*m['C']+m['M']*m['A']*m['H']
         +m['M']*m['R']*m['C']+m['M']*m['R']*m['H']
         +m['M']*m['C']*m['H']
         +m['A']*m['R']*m['C']+m['A']*m['R']*m['H']
         +m['A']*m['C']*m['H']
         +m['R']*m['C']*m['H'];
    //cout<<fixed<<setprecision(32)<<m;
    //sort(ALL(C),[](auto& a, auto& b) {return a[2] < b[2];});
    //if(equal(D.begin(), D.end()-1, K.begin()))cout<<"Yes";else cout<<"No";
    cout<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <string>
#include <math.h>
#include <iomanip>
#include <limits>
#include <list>
#include <queue>
#include <tuple>
#include <map>
#include <stack>
#include <set>
using namespace std;
#define MOD (long long int)(1e9+7)
#define ll long long int
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define reps(i,n) for(int i=1; i<=(int)(n); i++)
#define REP(i,n) for(int i=n-1; i>=0; i--)
#define REPS(i,n) for(int i=n; i>0; i--)
#define INF (int)(1123456789)
#define LINF (long long int)(112345678901234567)
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
#define all(v) v.begin(), v.end()

const int N = 1234567;

ll mpow(ll a, ll b){
	if(b==0) return 1;
	else if(b%2==0){ll memo = mpow(a,b/2); return memo*memo%MOD;}
	else return mpow(a,b-1) * a % MOD;
}
ll gcd(ll a, ll b){
	if(b==0) return a;
	else return gcd(b, a%b);
}
vector<ll> kaijo_memo;
ll kaijo(ll n){
	if(kaijo_memo.size() > n) return kaijo_memo[n];
	if(kaijo_memo.size() == 0) kaijo_memo.push_back(1);
	while(kaijo_memo.size() <= n) kaijo_memo.push_back(kaijo_memo[kaijo_memo.size()-1] * kaijo_memo.size() % MOD);
	return kaijo_memo[n];
}
ll nCr(ll n, ll r){
	if(n < r || r < 0) return 0;
	ll ret = 1;
	ret *= kaijo(n); ret %= MOD;
	ret *= mpow(kaijo(r), MOD-2); ret %= MOD;
	ret *= mpow(kaijo(n-r), MOD-2); ret %= MOD;
	return ret;
}

int main(void){
	int s;
	cin>>s;
	int check[N];
	rep(i,N){
		check[i] = 0;
	}
	int m = 1;
	check[s] = 1;
	while(true){
		m++;
		if(s%2 == 0){
			s/=2;
		}else{
			s = s*3+1;
		}
		if(check[s] == 1){
			cout<<m<<endl;
			return 0;
		}else{
			check[s] = 1;
		}
	}

	return 0;
}


Measured memory_bytes: 5120
from itertools import combinations
s = input()
n = int(input())

le = len(s)
tmp = s[:5]

for i in range(le - 4):
    tmp = min(tmp, s[i:i+5])

seed = tuple(combinations(range(min(6, le+1)), 2))
res = set()
for i, j in seed:
    res.add(tmp[i:j])
ans = sorted(res)
print(ans[n - 1])


Measured memory_bytes: 3064
mod = 10**9+7
N = int(input())
a = list(map(int, input().split()))
S = [0]*(N+1)#i~j-1の和はS[j]-S[i]
for i in range(1, N+1):
    S[i] = S[i-1]+a[i-1]
memo = [[-1]*(N+1) for _ in range(N)]
def dp(i, j):
    if memo[i][j]>=0:
        return memo[i][j]
    if j-i == 1:
        memo[i][j] = 0
        return 0
    memo[i][j] = min(dp(i, k)+dp(k, j)+S[j]-S[i]for k in range(i+1, j))
    return memo[i][j]
print(dp(0, N))


    








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


using namespace std;
typedef long long ll;
#define REP(i,n) for(int i=0; i<int(n); i++)
#define FOR(i,m,n) for(int i=int(m); i<int(n); i++)
#define ALL(obj) (obj).begin(),(obj).end()
#define VI vector<int>
#define VLL vector<long long>
#define VVI vector<vector<int>>
#define VVLL vector<vector<long long>>
#define VC vector<char>
#define VS vector<string>
#define VVC vector<vector<char>>
#define fore(i,a) for(auto &i:a)

typedef pair <int, int> P;
template<class T> bool chmax(T &a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T &a, T b) { if (a > b) { a = b; return true; } return false; }
const int  INF = 1 << 30;
const ll INFL = 1LL<<60;
const ll mod = 1000000007;		


int n;
string s;
string t;

void solve(int n) {
	FOR(i, 1, n) {
		if (s[i] == 'o') {
			if (t[i] == 'S') {
				t += t[i - 1];
			}
			else {
				if (t[i - 1] == 'W')t += 'S';
				else t += 'W';
			}
		}
		else {
			if (t[i] == 'W')t += t[i - 1];
			else {
				if (t[i - 1] == 'W')t += 'S';
				else t += 'W';
			}
		}
	}
}

bool check(string u) {
	if (u[0] != u[u.size() - 1])return false;
	if (s[0] == 'o') {
		if (u[0] == 'S') {
			if (u[1] == 'S') {
				if (u[u.size() - 2] == 'S')return true;
				else return false;
			}
			else {
				if (u[u.size() - 2] == 'W')return true;
				else return false;
			}
		}
		else {
			if (u[1] == 'W') {
				if (u[u.size() - 2] == 'S')return true;
				else return false;
			}
			else {
				if (u[u.size() - 2] == 'W')return true;
				return false;
			}
		}
	}
	else{
		if (u[0] == 'S') {
			if (u[1] == 'S') {
				if (u[u.size() - 2] == 'W')return true;
				else return false;
			}
			else {
				if (u[u.size() - 2] == 'S')return true;
				else return false;
			}
		}
		else {
			if (u[1] == 'W') {
				if (u[u.size() - 2] == 'W')return true;
				else return false;
			}
			else {
				if (u[u.size() - 2] == 'S')return true;
				return false;
			}
		}
	}
}

int main() {


	cin >> n;

	cin >> s;

	t = "SS";
	solve(n);
	if (check(t)) {
		cout << t.substr(0, n) << endl;
		return 0;
	}
	t = "SW";
	solve(n);
	if (check(t)) {
		cout << t.substr(0, n) << endl;
		return 0;
	}
	t = "WS";
	solve(n);
	if (check(t)) {
		cout << t.substr(0, n) << endl;
		return 0;
	}
	t = "WW";
	solve(n);
	if (check(t)) {
		cout << t.substr(0, n) << endl;
		return 0;
	}

	cout << -1 << endl;

	return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(ll i = 0, i##_len = (n); i < i##_len; i++)
#define reps(i, s, n) for(ll i = (s), i##_len = (n); i < i##_len; i++)
#define rrep(i, n) for(ll i = (n) - 1; i >= 0; i--)
#define rreps(i, e, n) for(ll i = (n) - 1; i >= (e); i--)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) ((ll)(x).size())
#define len(x) ((ll)(x).length())
#define endl "\n"

ll f(ll bit, ll v) {
    return ((bit & (1LL << v)) != 0);
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    // ifstream in("input.txt");
    // cin.rdbuf(in.rdbuf());
    ll n, m;
    cin >> n >> m;
    vector<vector<ll>> s(m);
    rep(i, m) {
        ll k;
        cin >> k;
        rep(j, k) {
            ll tmp;
            cin >> tmp;
            tmp--;
            s[i].push_back(tmp);
        }
    }
    vector<ll> p(m);
    rep(i, m) cin >> p[i];
    ll ans = 0;
    rep(bit, 1 << n) {
        bool clr = true;
        rep(i, m) {
            ll cnt = 0;
            rep(j, sz(s[i])) {
                if (f(bit, s[i][j])) cnt++;
            }
            if (cnt % 2 != p[i]) {
                clr = false;
                break;
            }
        }
        if (clr) ans++;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
import java.util.Comparator;
import java.util.Scanner;

class Main{




	public static void main(String[] args) {


		Scanner sc = new Scanner(System.in);			//文字の入力
		int n = sc.nextInt();
		long k = sc.nextLong();
		int[] a = new int[n+1];
		long[] b = new long[1000001];
		for(int i = 1;i <= n;i++){
			a[i] = sc.nextInt();
			b[a[i]] += sc.nextInt();				//counter
		}
		int p =1 ;
		
		while(k > 0){

			k -= b[p];
			if(k <= 0){
				break;
			}
			p++;


		}
		System.out.println(p);
	}

}

class MyComparator implements Comparator {

	public int compare(Object obj1, Object obj2) {

		int num1 = (int)obj1;
		int num2 = (int)obj2;

		if(num1 < num2) {
			return 1;
		} else if(num1 > num2) {
			return -1;
		} else{
			return 0;
		}
	}
}




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

#define debug(x) (cerr << #x << " = " << x << endl;)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define FOR(it, b, e) for (typeof(b) it = (b); it != (e); ++it)
#define MSET(c, v) memset(c, v, sizeof(c)

const int INF = 0x3F3F3F3F; 
const int NEGINF = 0xC0C0C0C0;
const int NULO = -1;
const double EPS = 1e-10;

inline int cmp(double x, double y = 0) 
{  
  if(fabs(x - y) < EPS)
    return 0;
  return x > y ? 1 : -1;
}


int main()
{
  ios::sync_with_stdio(0);
  int n;
  cin >> n;

  ll ans = 0;

  for(int i = 1; i <= n; i++)
  {
    if(i % 3 != 0 && i % 5 != 0)
      ans += i;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3624
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pint = pair<int, int>;
using pll = pair<ll, ll>;
using Edge = pair<int, ll>;
using Graph = vector<vector<int>>;
using WeightedGraph = vector<vector<Edge>>;
const ll INF64 = 1LL << 60;
const int INF32 = 1 << 29;
const ll MOD = 1000000007;

const int CASES = 3;

void solve() {
    ll N, M; cin >> N >> M;
    vector<ll> a(N);
    vector<bool> used(N, false);

    bool f = true;
    for(int i = 0; i < M; ++i){
        int s, c; cin >> s >> c;
        if(used[s-1] == true && a[s-1] != c){
            f = false;
            break;
        }
        a[s-1] = c;
        used[s-1] = true;
    }

    if(a[0] == 0 && N != 1){
        if(used[0] == true){
            f = false;
        }
        else{
            a[0] = 1;
        }
    }

    if(f){
        for (int i = 0; i < N; ++i) {
            cout << a[i];
        }
        cout << endl;
    }
    else{
        cout << -1 << endl;
    }
}

int main() {
#ifdef MYLOCAL
    vector<string> filenames {"input1.txt", "input2.txt", "input3.txt", "input4.txt", "input5.txt"};
    cout << "------------\n";
    for(int i = 0; i < CASES; ++i){
        ifstream in(filenames[i]);
        cin.rdbuf(in.rdbuf());
        solve();
        cout << "------------\n";
    }
#else

    solve();

#endif
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <algorithm>
#include <cctype>
#include <cmath>
#include <queue>
#include <map>
#include <numeric>
#include <unordered_map>
#include <iomanip>
#include <functional>
#include <bitset>
#include <complex>

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define repi(i,a,b) for(int i=int(a);i<int(b);i++)
#define all(x) (x).begin(),(x).end()

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

typedef long long ll;

using namespace std;
long long modpow(long long x,long long n,long long mod)
{
  if(n==0)return 1;
  long long res=modpow(x*x%mod,n/2,mod);
  if(n&1)res=res*x%mod;
  return res;
}
long long modinv(long long a,long long mod)//extgcdの方がいいらしい
{
  return modpow(a,mod-2,mod);
}
vector<int>inv;

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n,x;
  int mod=1e9+7;
  cin>>n>>x;
  vector<int>s(n);
  rep(i,n)cin>>s[i];
  sort(all(s),greater<int>());
  inv.resize(n+1);
  repi(i,1,n+1)inv[i]=modinv(i,mod);
  vector<vector<ll>>dp(2,vector<ll>(x+1,0));
  dp[0][x]=1;
  rep(i,n)
  {
    int no=i&1,ne=1-no;
    fill(all(dp[ne]),0);
    rep(j,x+1)
    {
      if(dp[no][j]==0)continue;
      ll t=(ll)dp[no][j]*inv[n-i]%mod;
      int jsi=j%s[i];
      dp[ne][jsi]+=t;
      dp[ne][j]+=t*(n-i-1)%mod;
      if(dp[ne][jsi]>mod)dp[ne][jsi]-=mod;
      if(dp[ne][j]>mod)dp[ne][jsi]-=mod;
    }
  }
  ll res=0;
  int kai=1;
  rep(i,n)kai=(ll)kai*(i+1)%mod;
  rep(i,x+1)
  {
    res+=(ll)kai*dp[n&1][i]%mod*i%mod;
  }
  cout<<res%mod<<endl;


  return 0;

}


Measured memory_bytes: 2560
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <string>
#include <math.h>
#include <stdio.h>
#include <iomanip>
#include <limits>
#include <list>
#include <queue>
#include <tuple>
#include <map>
#include <set>
#include <sstream>
using namespace std;
#define ll long long int
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define reps(i,n) for(int i=1; i<=(int)(n); i++)
#define REP(i,n) for(int i=n-1; i>=0; i--)
#define REPS(i,n) for(int i=n; i>0; i--)
#define FOR(i,a,b) for(int i=a; i<(int)(b); i++)
#define ALL(x) (x).begin(),(x).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define SORT(c) sort(ALL(x))
#define CLR(a) memset((a), 0 ,sizeof(a))
#define PB push_back
#define MP make_pair
#define SP << " " <<
#define chmax(a, b) a = (((a)<(b))?(b):(a))
#define chmin(a, b) a = (((a)<(b))?(a):(b))

const int INF = 1001001001;
const ll MOD = 1e9+7;
const ll LINF = 100100100100100100;
const double EPS = 1e-10;
const double PI  = acos(-1.0);
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;

template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){std::fill((T*)array, (T*)(array+N),val);}

class CompareDist
{
public:
    bool operator()(PLL n1,PLL n2) {
				if(n1.first!=n2.first) return n1.first<n2.first;
				else return n1.second<n2.second;
    }
};

#define lengthof(x) (sizeof(x) / sizeof(*(x)))


__attribute__((constructor))
void initial(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(15);
}

ll mpow(ll a, ll b){
  if(b==0) return 1;
  else if(b%2==0){ll memo = mpow(a,b/2); return memo*memo%MOD;}
  else return mpow(a,b-1) * a % MOD;
}

signed main(){
  int n,a,b; cin>>n>>a>>b;
  int ans = 0;
  reps(j,n){
    int sum = 0;
    int i = j;
    while(i){
      sum += i%10;
      i /= 10;
    }
    if(a<=sum&&sum<=b) ans+=j;
  }
  cout << ans << endl;

  return 0;
}


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


void printAll(int a[],int N){
  rep(i,N-1) printf("%d ",a[i]);
  cout << a[N-1] << endl;
}

void selectionSort(int A[],int N,int& cnt){
  for(int i=0;i<N;i++){
    int min_j = i;

    for(int j=i;j<N;j++){
      if(A[j] < A[min_j])swap(min_j,j);
    }

    if(i != min_j){
      swap(A[i],A[min_j]);
      cnt++;
    }
    //printAll(A,N);
  }
}

int main(){
  int N;
  cin >> N;
  int a[N];
  rep(i,N)cin >> a[i];

  int cnt = 0;
  selectionSort(a,N,cnt);
  
  printAll(a,N);
  cout << cnt << endl;
}


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

signed main(){
	int N,sum=0;cin>>N;
	vector<int> A(N);
	for(int i=0;i<N;i++){
		cin>>A[i];
		if(i!=0)sum+=abs(A[i]-A[i-1]);
	}
	sum+=abs(A[0])+abs(A[N-1]);
	for(int i=0;i<N;i++){
		if(i!=0 and i!=N-1){
			cout<<sum-abs(A[i]-A[i-1])-abs(A[i+1]-A[i])+abs(A[i+1]-A[i-1])<<endl;
		}
		else if (i==0){
			cout<<sum-abs(A[0])-abs(A[1]-A[0])+abs(A[1])<<endl;
		}
		else if(i==N-1){
			cout<<sum-abs(A[N-1])-abs(A[N-2]-A[N-1])+abs(A[N-2])<<endl;
		}
	}
	return 0;
}

Measured memory_bytes: 2048
#ifndef _GLIBCXX_NO_ASSERT
#include <cassert>
#endif
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>

#if __cplusplus >= 201103L
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
#endif

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

#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif




#define int long long
#define rng(i,l,r) for(size_t i=(l);i<(r);++i)
#define rep(i,n) rng(i,0,n)
#define gnr(i,l,r) for(size_t i=(r)-1;i>=(l);i--)
#define per(i,b) gnr(i,0,b)
#define ALL(obj) (obj).begin(), (obj).end()   //1,2,3,...
#define rALL(obj) (obj).rbegin(), (obj).rend()//...,3,2,1

using namespace std;
//using ll = long long;


const int MOD = 1000000007;
const int INF = 1e18;

const int dx4[4] = {1, 0, -1, 0};
const int dy4[4] = {0, 1, 0, -1};
const int dx8[8] = {1,1,0,-1,-1,-1,0,1};
const int dy8[8] = {0,1,1,1,0,-1,-1,-1};

const double pi = acos(-1);



template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }


using Graph = vector<vector<int>>;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
//*max_element(ALL(vector))
//count(ALL(vector),num) -> n




void solve(){
    
    // remove the bottom 3 lines when you submit this code.
    std::ifstream in("sample.txt");
    std::cin.rdbuf(in.rdbuf());

    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int n; cin >> n;
    vector<int> v(n);
    for (int i = 0; i < n; i++) {
        cin >> v[i];
    }
    
    int sum = 0;
    for (int i = 0; i < n; i++) {
        sum += v[i];
    }
    
    cout << *min_element(ALL(v)) << " " << *max_element(ALL(v)) << " " << sum << endl;
}



signed main() {
    solve();
    return 0;
}




Measured memory_bytes: 3216
#include<stdio.h>
#define rep(i,n)for(int i=0;i<(int)(n);i++)
int main(){
    int n,m,x,c[12]={0},a[12][12]={0},y,z[12],b,d=2e9;
    scanf("%d%d%d",&n,&m,&x);
    rep(i,n){
        scanf("%d",&c[i]);
        rep(j,m){
            scanf("%d",&a[i][j]);
        }
    }
    rep(i,2){
        rep(j,2){
            rep(k,2){
                rep(l,2){
                    rep(o,2){
                        rep(p,2){
                            rep(q,2){
                                rep(r,2){
                                    rep(s,2){
                                        rep(t,2){
                                            rep(u,2){
                                                rep(v,2){
    y=i*c[0]+j*c[1]+k*c[2]+l*c[3]+o*c[4]+p*c[5]+q*c[6]+r*c[7]+s*c[8]+t*c[9]+u*c[10]+v*c[11];
    for(b=0;b<m;b++){
        z[b]=i*a[0][b]+j*a[1][b]+k*a[2][b]+l*a[3][b]+o*a[4][b]+p*a[5][b]+q*a[6][b]+r*a[7][b]+s*a[8][b]+t*a[9][b]+u*a[10][b]+v*a[11][b];
        if(z[b]<x)break;
    }
    if(b==m&&y<d)d = y;
    }}}}}}}}}}}}
    if(d==(int)2e9)puts("-1\n");
    else printf("%d\n",d);
    return 0;
}


Measured memory_bytes: 1736
#include <stdio.h>

int main(){
	int m, f, r;
	
	while(1) {
		scanf("%d %d %d", &m, &f, &r);
		if((m == -1) && (f == -1) && (r == -1)) break;
		
		if((m == -1) || (f == -1)) printf("F\n");
		else if( m + f >= 80 ) printf("A\n");
		else if( m + f >= 65 ) printf("B\n");
		else if( m + f >= 50 ) printf("C\n");
		else if( (m + f >= 30) && (r >= 50) ) printf("C\n");
		else if( m + f >= 30 ) printf("D\n");
		else printf("F\n");
	}
	return 0;
}

Measured memory_bytes: 584
import java.util.Scanner;

class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    
    int n = sc.nextInt();
    int[] a = new int[n];
    for(int i=0; i<n; i++){
      int j = sc.nextInt();
      a[j-1] = i;
    }
    
    for(int i=0; i<n; i++){
      System.out.print(a[i]+1+" ");
    }
  }
}

Measured memory_bytes: 62676
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define chmin(x,y) x = min(x,y)
using namespace std;
typedef long long ll;
const int INF = 1001001001;

int main(){
  int n,m,l;
  cin >> n >> m >> l;
  vector<vector<int>> dist(n,vector<int>(n,INF));
  rep(i,m){
    int a,b,c;
    cin >> a >> b >> c;
    a--; b--;
    dist[a][b] = dist[b][a] = c;
  }
  rep(k,n) rep(i,n) rep(j,n) chmin(dist[i][j],dist[i][k]+dist[k][j]);
  vector<vector<int>> dist2(n,vector<int>(n,INF));
  rep(i,n){
    rep(j,n){
      if(dist[i][j]<=l) dist2[i][j] = 1;
    }
  }
  rep(k,n) rep(i,n) rep(j,n) chmin(dist2[i][j],dist2[i][k]+dist2[k][j]);
  int q;
  cin >> q;
  rep(qi,q){
    int s,t;
    cin >> s >> t;
    s--; t--;
    int ans = dist2[s][t]-1;
    if(dist2[s][t]==INF) ans = -1;
    cout << ans << endl;
  }
}


Measured memory_bytes: 1280
#include <stdio.h>

int main(void)
{
	int i;
	int qty;
	char str[21];
	
	/*for(i=0;i<21;i++)
	{
		str[i] = '\0';
	}*/
	
	//gets(str);
	fgets(str,21,stdin);
	
	for(i=0;i<21;i++)
	{
		if(str[i] == '\0')
		{
			qty = i;
		}
	}
	
	for(i=(qty-1);i>=0;i--)
	{
		printf("%c",str[i]);
	}
	
	printf("\n");
	
	return 0;
}


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

const int N = 1e6 + 5;
typedef long long ll;

int n;
ll f[N], mod = 1e9 + 7, inv[N], fac[N], ans;

ll calc(int n, int k) {
	return fac[n]*inv[n - k]%mod*inv[k]%mod;
}

ll fps(ll a, ll b) {
	ll res = 1;
	while(b) {
		if(b&1) res = res*a%mod;
		b /= 2;
		a = a*a%mod;
	}
	return res;
}

int main() {
	cin>>n;
	fac[0] = inv[0] = fac[1] = inv[1] = 1;
	for(int i = 2; i <= n; i++) {
		fac[i] = fac[i - 1]*i%mod;
		inv[i] = fps(fac[i], mod - 2);
	}
	for(int i = (n + 1)/2; i < n; i++)
		f[i] = (calc(i - 1, n - i - 1)*fac[i]%mod*fac[n - i - 1])%mod;
	for(int i = (n + 1)/2; i < n; i++)
		ans = (ans + (f[i] - f[i - 1])*i)%mod;
	cout<<(ans + mod)%mod;
	return 0;
}

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

int main(){
    int N, D;
    cin >> N >> D;
    int cnt=0;
    for (int i=0; i<N; ++i){
        int x,y;
        cin >> x >> y;
        if (pow((float) x, 2.0) + pow((float) y, 2.0) <= pow((float) D, 2.0)) ++cnt;
    }
    cout << cnt;
}

Measured memory_bytes: 3616
#include<iostream>
using namespace std;
int main(){
  int ans[31]={1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2,3,6,10,19,34,62,113,207,381,701,1288,2369,4357,8014,14740};
  while(1){
    cin>>ans[0];
    if(!ans[0])
      return 0;
    cout<<ans[ans[0]]<<endl;
  }
}

Measured memory_bytes: 1160
n = int(input())
A = [*map(int, input().split())] + [0]
yen = 1000
kabu_yen = kabu_n = 0
for i in range(n):
    if A[i] < A[i+1]: # buy
        m = yen // A[i]
        cost = m * A[i]
        yen -= cost
        kabu_yen += cost
        kabu_n += m
    elif A[i] > A[i+1]: # sell
        yen += kabu_n * A[i]
        kabu_yen = kabu_n = 0
print(yen)


Measured memory_bytes: 9124
import java.util.Arrays;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        int[] X = new int[M];
        for(int i = 0; i < M; i++){
            X[i] = sc.nextInt();
        }
        Arrays.sort(X);
        int[] diff = new int[M-1];
        long ans = 0;
        if(N < M){
            for(int i = 0; i < M -1; i++){
                diff[i] = Math.abs(X[i +1] - X[i]);
                ans += diff[i];
            }
            Arrays.sort(diff);
            for(int i = M-2; i > M-2-(N-1); i--){
                ans -= diff[i];
            }
        }

        System.out.println(ans);
        sc.close();
    }

}


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

typedef long long ll;

int main() {
    int N, M, X, A, ans = 0;
    cin >> N >> M >> X;
    rep(i, M) {
        cin >> A;
        if (A < X) ans++;
    }
    cout << min(ans, M - ans) << "\n";
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <array>
#include <deque>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <numeric>
#include <utility>
#include <cmath>
#include <iomanip>

using namespace std;
using ll=long long int;

int main() {
    ll n, k;
    cin >> n >> k;
    vector<pair<int, int>> sushi(n);
    for (auto &e: sushi) cin >> e.first >> e.second;

    sort(sushi.begin(), sushi.end(), greater<>());
    vector<ll> kt, other;
    kt.push_back(sushi[0].second);
    for (int i = 1; i < n; ++i) {
        if (sushi[i].first != sushi[i-1].first) {
            kt.push_back(sushi[i].second);
        } else {
            other.push_back(sushi[i].second);
        }
    }
    sort(kt.begin(), kt.end(), greater<>());
    sort(other.begin(), other.end(), greater<>());

    ll kcnt = min(k, (ll)kt.size());
    ll p = accumulate(kt.begin(), kt.begin() + kcnt, 0LL) + kcnt * kcnt;
    p += accumulate(other.begin(), other.begin() + (k - kcnt), 0LL);
    ll ans = p;
    --kcnt;
    for (; kcnt > 0 && k - kcnt <= other.size(); --kcnt) {
        p -= kt[kcnt] + ((kcnt+1) * (kcnt+1)) - (kcnt * kcnt);
        p += other[k - kcnt - 1];
        ans = max(ans, p);
    }

    cout << ans << endl;


    return 0;
}


Measured memory_bytes: 2168
s = list(input())
k = int(input())
t = list(map(lambda x:ord(x)-ord("a"),s))
 
for i in range(len(t)):
  diff = 26-t[i]
  if diff != 26 and diff <= k: 
    t[i]+=diff
    k-=diff
t[-1]+=k
 
u = "".join(list(map(lambda x:chr((x%26+ord("a"))),t)))
print(u)

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

int main() {
  int N;
  cin >> N;
  int sum = 0;
  vector<int> B(N - 1);
  vector<int> A(N);
  for (int i = 0; i < N - 1; i++) cin >> B.at(i);
  for (int i = 0; i < N; i++) {
    if (i == 0) {
      A.at(0) = B.at(0);
    }
    else if (i == N-1) {
      A.at(i) = B.at(i-1);
    }
    else {
      A.at(i) = min(B.at(i-1), B.at(i));
    }
  }
  for (int i = 0; i < N; i++) sum += A.at(i);
  cout << sum << endl;
}

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

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

using namespace std;

ll dfs(ll cn, int mask, ll n)
{
	ll ret=0;
	if (cn > n) return 0;
	if (mask == 7) ret++;
	ret += dfs(cn*10+3, mask|1, n);
	ret += dfs(cn*10+5, mask|2, n);
	ret += dfs(cn*10+7, mask|4, n);
	return ret;
}

int main()
{
	ll n;
	cin >> n;
	cout << dfs(0, 0, n) << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#include <string.h>
#include <cmath>

using namespace std;
typedef long long i64;
typedef long double ld;
typedef pair<i64,i64> P;
#define rep(i,s,e) for(int (i) = (s);(i) <= (e);++(i))

int n;

int cou[101010];

int main(){
    cin >> n;
    int MIN = 1e9;
    int MAX = 0;
    for(int i = 0;i < n;i++){
        int a;
        cin >> a;
        cou[a]++;
        MIN = min(MIN , a);
        MAX = max(MAX , a);
    }

    if(MAX - MIN >= 2){
        cout << "No" << endl;
    }

    else if(MAX == MIN){
        int x = MIN;
        if(x + 1 == n || 2 * x <= n){
            cout << "Yes" << endl;
        }
        else{
            cout << "No" << endl;
        }
    }

    else if(MAX - MIN == 1){
        int A = cou[MIN];
        int B = cou[MAX];
        if(B >= 2 * (MIN + 1 - A) && MIN + 1 - A > 0){
            cout << "Yes" << endl;
        }
        else{
            cout << "No" << endl;
        }
    }
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
#define pii pair<int, int>
#define eb emplace_back
#define all(v) v.begin(), v.end()
#define rep(i, n) for (int i = 0; i < n; ++i)
#define rep3(i, l, n) for (int i = l; i < n; ++i)
#define chmax(a, b) a = (a >= b ? a : b)
#define chmin(a, b) a = (a <= b ? a : b)
#define out(a) cout << a << endl
#define outa(a, n) rep(_, n) cout << a[_] << " "; cout << endl
#define SZ(v) (int)v.size()
#define inf (int)(1e9+7)
#define abs(x) (x >= 0 ? x : -(x))

int n, m;
vector<int> v[50];
map<int, pii> mp;
bool visited[50];
void dfs(int i, int now) {
    visited[now] = 1;
    rep(j, SZ(v[now])) {
        if (visited[v[now][j]]) continue;
        if (now == mp[i].F && v[now][j] == mp[i].S) continue;
        else if (now == mp[i].S && v[now][j] == mp[i].F) continue;
        dfs(i, v[now][j]);
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    rep(i, m) { int a, b; cin >> a >> b; a--; b--; v[a].eb(b); v[b].eb(a); mp[i] = {a, b}; }
    int ans = 0;
    rep(i, m) {
        fill_n(visited, n, 0);
        dfs(i, 0);
        rep(j, n) if (visited[j] == 0) { ans++; break; }
    }
    out(ans);
}


Measured memory_bytes: 256
//高知能系Vtuberの高井茅乃です。
//Twitter: https://twitter.com/takaichino
//YouTube: https://www.youtube.com/channel/UCTOxnI3eOI_o1HRgzq-LEZw

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

#define INF 1999999999
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define MODA 1000000007 

int main() {
	int ans = 0;
	int tmp;

	//エラトステネスの篩でP_max以下の素数vector primeをつくる
	bool *pr;
	int P_max = 1000000; //10^6くらいまでが現実的か
	pr = (bool*)malloc(sizeof(bool) * P_max);
	REP(i, P_max) {
		pr[i] = i;
	}
	REP(i, P_max + 1) pr[i] = true;
	pr[0] = false;
	pr[1] = false;
	for(int i = 2; i * i <= P_max; i++){ 
		if(pr[i] == true){
			for(int j = 2 * i; j <= P_max; j+=i){
				pr[j] = false;
			}
		}
	}
	vector<int> prime;
	for(int i = 2; i <= P_max; i++){
		if(pr[i]) prime.push_back(i);
	}
	//
	int x;
	cin >> x;
	auto it = lower_bound(prime.begin(), prime.end(), x);
	cout << *it << endl;
}

Measured memory_bytes: 1916