akhauriyash/Code-Regression huggingface dataset:
#include <stdio.h>
#define num_element 125
int main(void)
{
	int i,n,m;
	char array[num_element];
	char a[2];
	char b[2];
	char input[2];
	while(1)
	{
		for(i=0;i<num_element;i++)
		{
			array[i] = i;
		}
		scanf("%d",&n);
		if(n == 0)return 0;
		for(i=0;i<n;i++)
		{
			scanf("%s %s",a,b);
			array[a[0]] = b[0];
		}
		scanf("%d",&m);
		for(i=0;i<m;i++)
		{
			scanf("%s",input);
			printf("%c",array[input[0]]);
		}
		printf("\n");
	}
	return 0;
}

Measured memory_bytes: 576
//
// tested with : g++ (GCC) 8.3.0
//

#include <iostream>
using namespace std;

int main() {
    int n;//支払い金額
    int a;//1円玉の数
    cin >> n >> a;

    int result = 0;
    int nokori = n % 500;//500円は無限で最大499円の残り

    if (nokori == 0) {
        //nokoriがないので支払い完了。
        cout << "Yes" << endl;
    }
    else {
        //nokoriがあるので1円で払いたい。
        if (a > 0) {
            //1円がある場合。
            if (nokori / a == 0) {
                //amariよりも1円が上回れば0になるので、YES
                cout << "Yes" << endl;
            }
            else {
                //1円が足りない。
                cout << "No" << endl;
            }
        }
        else {
            //1円がない場合。
            cout << "No" << endl;
        }
    }

    return 0;
}

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

int	main()
{
	int	n, m;
	cin >> n >> m;
	int	c[20];
	int	num_coin[50001];
	for (int i = 0; i <= n; ++i)
		num_coin[i] = -1;
	for (int i = 0; i < m; ++i)
		cin >> c[i];
	int	k;
	int	num_coin_i, num_coin_k;
	num_coin[0] = 0;
	for (int i = 0; i <= n; ++i) {
		num_coin_i = num_coin[i];
		if (num_coin_i == -1) continue;
		for (int j = 0; j < m; ++j) {
			k = i + c[j];
			if (k > n) continue;
			num_coin_k = num_coin_i + 1;
			if (num_coin[k] == -1 || num_coin[k] > num_coin_k) 
				num_coin[k] = num_coin_k;
		}
	}
	cout << num_coin[n] << endl;
}
	



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

using namespace std;

typedef long long ll;

int main() {
    ll L,R;
    cin >> L >> R;
    ll min=100000000000;
    int ans;
    for(ll i=L;i<R;i++){
        for(ll j=i+1;j<=R;j++){
            ans=i*j%2019;
            if(ans<min){
                min=ans;
            }
            if(ans==0){
                cout << min << endl;
                return 0;
            }
        }
    }
    cout << min << endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <iomanip>
#include <numeric>
#include <queue>
#include <cmath>
using namespace std;

void f(int index, vector<int>& visited, const vector<vector<int>>& v, int & res, int c) {
    if (c == visited.size() - 1) {
        res++;
        return;
    }
    for (int i = 1; i <= visited.size(); i++) {
        if (visited[i] == 0 && v[index][i] == 1) {
            visited[i] = 1;
            f(i, visited, v, res, c + 1);
            visited[i] = 0;
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> v(n + 1, vector<int>(n + 1, 0));
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        v[a][b] = 1;
        v[b][a] = 1;
    }
    int res = 0;
    vector<int> visited(n + 1, 0);
        visited[1] = 1;
        f(1, visited, v, res, 1);
        visited[1] = 0;
    
    cout << res << endl;
}


Measured memory_bytes: 3616
package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)

func Scan() string {
	sc.Scan()
	return sc.Text()
}
func iScan() int {
	n, _ := strconv.Atoi(Scan())
	return n
}
func fScan() float64 {
	n, _ := strconv.ParseFloat(Scan(), 64)
	return n
}
func stringToInt(s string) int {
	n, _ := strconv.Atoi(s)
	return n
}
func SScan(n int) []string {
	a := make([]string, n)
	for i := 0; i < n; i++ {
		a[i] = Scan()
	}
	return a
}
func iSScan(n int) []int {
	a := make([]int, n)
	for i := 0; i < n; i++ {
		a[i] = iScan()
	}
	return a
}
func abs(x int) int {
	if x < 0 {
		x = -x
	}
	return x
}
func larger(a, b int) int {
	if a < b {
		return b
	} else {
		return a
	}
}
func smaller(a, b int) int {
	if a > b {
		return b
	} else {
		return a
	}
}
func max(a []int) int {
	x := a[0]
	for i := 0; i < len(a); i++ {
		if x < a[i] {
			x = a[i]
		}
	}
	return x
}
func min(a []int) int {
	x := a[0]
	for i := 0; i < len(a); i++ {
		if x > a[i] {
			x = a[i]
		}
	}
	return x
}
func sum(a []int) int {
	x := 0
	for _, v := range a {
		x += v
	}
	return x
}

var mod int = 1000000007

func main() {
	buf := make([]byte, 0)
	sc.Buffer(buf, mod)
	sc.Split(bufio.ScanWords)
	n := iScan()
	k := iScan()
	h := iSScan(n)
	sort.Ints(h)
	ans := 0
	for i := 0; i < larger(0, n-k); i++ {
		ans += h[i]
	}
	fmt.Println(ans)
}


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

using namespace std;

int main(void) {
    long n;
    cin >> n;
    vector<long> a(3);
    for(auto &x: a) cin >> x;
    vector<long> b(3);
    for(auto &x: b) cin >> x;

    {
        vector<long> dp(n+1);
        for(long i=0; i<n; i++) {
            dp[i+1] = max(dp[i+1], dp[i]+1);
            for(long j=0; j<3; j++)
                if(i+a[j] <= n)
                    dp[i+a[j]] = max(dp[i+a[j]], dp[i] + b[j]);
        }
        n = dp[n];
    }

    {
        vector<long> dp(n+1);
        for(long i=0; i<n; i++) {
            dp[i+1] = max(dp[i+1], dp[i]+1);
            for(long j=0; j<3; j++)
                if(i+b[j] <= n)
                    dp[i+b[j]] = max(dp[i+b[j]], dp[i] + a[j]);
        }
        n = dp[n];
    }

    cout << n << endl;
}


Measured memory_bytes: 195584
#include <stdio.h>
int main (void){
    int i,n,ans=100000;
    scanf("%d",&n);
    for(i=0;i<n;i++){
        ans=ans+ans*0.05;
        if(ans%1000!=0){
            ans=ans/1000;
            ans=ans+1;
            ans=ans*1000;
        }
    }
    printf("%d\n",ans);
return 0;
}

Measured memory_bytes: 588
#include <cmath>
#include <iomanip>
#include <iostream>
#include <list>
#include <queue>
#include <vector>

using namespace std;

int main() {
  int n, m, x;
  cin >> n >> m >> x;
  vector<vector<int>> a(n, vector<int>(m));
  vector<int> c(n), u(n, 0);
  for (int i = 0; i < n; i++) {
    cin >> c[i];
    for (int j = 0; j < m; j++) {
      cin >> a[i][j];
    }
  }
  int ans = 900000000;
  for (int b = 0; b < (1 << n); b++) {
 //   cout<<b<<endl;
    fill(u.begin(), u.begin() + n, 0);
    int cost = 0;
    for (int h = 0; h < n; h++) {
      if ((b & (1 << h)) != 0) {
   //       cout<<b<<"  "<<h<<"  "<<(b & (1 << h))<<endl;
        for (int i = 0; i < m; i++) {
          u[i] += a[h][i];
        }
        cost += c[h];
      }
    }
  //  cout<<cost<<"  j"<<endl;
    bool flag = true;
    for (int i = 0; i < m; i++) {
      if (u[i] < x) {
        flag = false;
      }
    }
    if (flag) {
      ans = min(ans, cost);
    }
  }
  if (ans < 900000000) {
    cout << ans << endl;
  } else {
    cout << -1;
  }
  return 0;
}

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

using namespace std;

#define FOR(i,l,r) for( int i = l; i < r; i++ )

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

Measured memory_bytes: 640
import java.util.*;
class Main
{
    public static void main (String[] args)
    {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt(), b = sc.nextInt(), c = sc.nextInt();
        int ans = 0;
        if(c > a + b) ans = a + b * 2 + 1; 
        else ans = b + c;
        System.out.println(ans);
    }
}

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

int p[300010], t[1400100];

void modify(int ind, int L, int R, int tar, int x) {
    if (L == R) {
        t[ind] = max(t[ind], x);
        return;
    }
    int M = (L+R) >> 1;
    if (tar <= M) modify(ind*2, L, M, tar, x);
    else modify(ind*2+1, M+1, R, tar, x);
    t[ind] = max(t[ind*2], t[ind*2+1]);
}

int query(int ind, int L, int R, int ql, int qr) {
    if (L == ql && R == qr) return t[ind];
    int M = (L+R) >> 1;
    if (qr <= M) return query(ind*2, L, M, ql, qr);
    else if (ql > M) return query(ind*2+1, M+1, R, ql, qr);
    else return max(query(ind*2, L, M, ql, M), query(ind*2+1, M+1, R, M+1, qr));
}

int solve(int x, int k) {
    int l = max(1, x-k), r = min(300000, x+k);
    return query(1, 1, 300000, l, r);
}

int main() {
    cin.tie(0); ios::sync_with_stdio(0);
    int n, k; cin >> n >> k;
    for (int i=0; i<n; i++) cin >> p[i];
    int ans = 0, temp;
    for (int i=0; i<n; i++) {
        temp = solve(p[i], k)+1;
        ans = max(ans, temp);
        modify(1, 1, 300000, p[i], temp);
    }
    cout << ans << endl;
}

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

class Dice{
public:
    int f[6];
    
    Dice(){};
    
    void role(int w,int x,int y,int z){
        int v = f[w];f[w] = f[x];f[x] = f[y];f[y] = f[z];f[z] = v;
    }
    void roleS(){role(0,4,5,1);}
    void roleE(){role(0,3,5,2);}
    void rolear(){role(1,2,4,3);}
    void check(char s){
        if (s == 'S')roleS();
        else if (s == 'E') roleE();
        else if (s == 'W') for(int i = 0; i < 3; i++) roleE();
        else if (s == 'N') for(int i = 0; i < 3; i++) roleS();
    }
    
};

int getRight(Dice d1, int f1, int f2){
    for (int i = 0; i < 6; i++){
        for(int j = 0; j < 4; j++){
            if (d1.f[0] == f1 && d1.f[1] == f2) return d1.f[2];
            d1.rolear();
        }
        if (i % 2 == 0) d1.roleE();
        else d1.roleS();
    }
    return -1;
}

int main(){
    Dice d;
    int n;
    for (int i = 0; i < 6; i++) cin >> d.f[i];
    cin >> n;
    int f1,f2;
    for (int i = 0; i < n; i++){
        cin >> f1 >> f2;
        cout << getRight(d, f1, f2) << endl;
    }
    return 0;
}


Measured memory_bytes: 3092
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );
using namespace std;

struct UnionFind {
    vector<int> par;

    UnionFind(int n) : par(n, -1){}
    void init(int n) {par.assign(n, -1);}

    //再帰的に辿ることで親を調べる
    int root(int x){
        if(par[x] < 0) return x;
        else return par[x] = root(par[x]);
    }

    //親が同じならば同じ集合に属する
    bool same(int x, int y){
        return root(x) == root(y);
    }

    bool merge(int x, int y){
        x = root(x);
        y = root(y);
        if(x == y) return false;
        //新しい要素を加えた時に、rootに対して辺を張る(merge technique)
        if(par[x] > par[y]) swap(x, y);
        par[x] += par[y];
        par[y] = x;
        return true;
    }
    
    //新しいノードを集合に加えた時に、-1をrootに加算するため、
    //rootには、集合に属するノードの数に負符号を付加したものが保存されている。
    int size(int x){
        return -par[root(x)];
    }
};


int main(){
    int n, m;
    cin >> n >> m;
    vector<int> v(n);
    rep(i, n) cin >> v[i];

    UnionFind uf(n+1);
    rep(i, m){
        int x, y;
        cin >> x >> y;
        uf.merge(x, y);
    }

    int ans = 0;
    rep(i, n){
        if(uf.same(i+1, v[i])) ans++;
    }

    cout << ans << endl;
}

Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <cstdio>
#include <queue>

using namespace std;

typedef long long ll;

ll func(ll n)
{
    if(n%2==0)
        return n/2;
    else
        return 3*n+1;
}


int main() {


    ll s;
    cin>>s;

    vector<ll> a;
    a.push_back(0);
    a.push_back(s);

    if(s==1 || s==2 || s==4)
    {
        cout<<4<<endl;
        return 0;
    }

    for(ll i=2; i<1000000+1; i++)
    {
        a.push_back(func(a[i-1]));

        if(a[i]==4)
        {
            cout<<i+3<<endl;
            break;
        }

    }


    return 0;
}

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

int main()
{
    int a;
    bool s=false;
    cin >> a;
    for(int i=1; i<=9; i++)
    {
        for(int j=1; j<=9; j++)
        {
            if(i*j==a)
            {
                cout<<"Yes\n";
                s=true;
                break;
            }
        }
        if(s==1)break;
    }
    if(s==0)
        cout<<"No\n";
    return 0;
}


Measured memory_bytes: 256
#-*-coding:utf-8-*-

def main():
    n, k = map(int, input().split())
    x_list = list(map(int, input().split()))
    ans = float('inf')

    for i in range(n - k + 1):
        if x_list[i] >= 0 and x_list[i+k-1] >= 0:
            ans = min(ans, x_list[i+k-1])
        elif x_list[i] <= 0 and x_list[i+k-1] <= 0:
            ans = min(ans, -x_list[i])
        else:
            ans = min(ans, min(-x_list[i] * 2 + x_list[i+k-1] , -x_list[i] + x_list[i+k-1] * 2))
    print(ans)

if __name__ == '__main__':
    main()

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

int main()
{
int a,b; 
    cin>>a>>b; 
    int f=0; 
    int i;
    for( i=1;i<10000;i++)
    {
        if((int)(floor(i*0.08)==a)&&(int)(floor(i*0.1)==b))
        {
            f=-1; 
            break; 
        }
    }
    if(f==-1)
        cout<<i; 
    else 
        cout<<-1; 
}

Measured memory_bytes: 256
n, k = map(int, raw_input().split())
if k%2:
	print (n/k)**3
else:
	cnt1, cnt2 = 0, 0
	for i in range(1, n + 1):
		if i%k == 0:
			cnt1 += 1
		if i%k == k/2:
			cnt2 += 1
	print cnt1**3 + cnt2**3

Measured memory_bytes: 8964
/*
▄▄▄▄▄▄   ▄▄▄▄                      ▄▄▄▄▄                               
██▀▀▀▀██ ▀▀██                      ██▀▀▀██                             
██    ██   ██    ██    ██  ▄████▄  ██    ██  ▄████▄  ██▄████▄  ▄████▄  
███████    ██    ██    ██ ██▄▄▄▄██ ██    ██ ██▀  ▀██ ██▀   ██ ██▄▄▄▄██ 
██    ██   ██    ██    ██ ██▀▀▀▀▀▀ ██    ██ ██    ██ ██    ██ ██▀▀▀▀▀▀ 
██▄▄▄▄██   ██▄▄▄ ██▄▄▄███ ▀██▄▄▄▄█ ██▄▄▄██  ▀██▄▄██▀ ██    ██ ▀██▄▄▄▄█ 
▀▀▀▀▀▀▀     ▀▀▀▀  ▀▀▀▀ ▀▀   ▀▀▀▀▀  ▀▀▀▀▀      ▀▀▀▀   ▀▀    ▀▀   ▀▀▀▀▀  
*/
# include <cstdio>
# include <iostream>

using namespace std ; 

typedef long long lint ; 
typedef long double ntrl ; 

# define MAXN 100010
# define MAXM 100010
# define INF 0x3f3f3f3f

///global variable///
int n , k , s ; 
// n -> lenth of A[]
// k -> k pairs
// s -> sum of A[]
/////*/

///basic function///
inline lint min ( lint x , lint y ) { return x < y ? x : y ; }
inline lint max ( lint x , lint y ) { return x > y ? x : y ; }
inline void swap ( lint &x , lint &y ) { x ^= y , y ^= x , x ^= y ; }
inline bool isltr ( char x ) { return ( 'A' <= x && x <= 'Z' ) || ( 'a' <= x && x <= 'z' ) ; }
inline bool isnum ( char x ) { return ( '0' <= x && x <= '9') ; }
/////*/

///fast read///
inline lint readlint ( )
{
	lint val = 0 , sign = 1 ; char tmp = getchar ( ) ; 
	while ( ! isnum ( tmp ) ) { if ( tmp == '-' ) { sign = - sign ; } tmp = getchar ( ) ;  } 
	while ( isnum ( tmp ) ) { val = ( val << 1 ) + ( val << 3 ) + tmp - 48 ; tmp = getchar ( ) ; } 
	return val * sign ; 
}
inline char readlter ( ) 
{
	char tmp = getchar ( ) ; 
	while ( ! isltr ( tmp ) )
		tmp = getchar ( ) ; 
	return tmp ; 
}
/////*/

int main ( )
{
	n = readlint ( ) ; 
	k = readlint ( ) ; 
	s = readlint ( ) ; 

	int cnt = 0 ; 

	for ( int i = 1 ; i <= k ; i ++ )
	{
		printf ( "%d " , s ) ; 
	}
	if ( s < 1000000000 )
	{
		for ( int i = k + 1 ; i <= n ; i ++ )
		{
			printf ( "1000000000 " ) ; 
		}
	}
	else
	{
		for ( int i = k + 1 ; i <= n ; i ++ )
		{
			printf ( "1 " ) ; 
		}
	}

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

Measured memory_bytes: 1280
#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
using P = pair<double,ll>;
using um = unordered_map<ll,ll>;
#define fl cout<<flush;
#define endl '\n'
template <typename T> inline void prt(T v){cout<<v<<'\n';}
template <typename T> inline bool chmax(T &a, const T &b){if (a<b){a=b;return 1;}return 0;}
template <typename T> inline bool chmin(T &a, const T &b){if (a>b){a=b;return 1;}return 0;}
const ll INF=1LL<<60;
const ll MOD=1e9+7;
const ll MOD2=998244353;
const ld pi=3.14159265358979323846;
const ld eps=1e-10;

signed main(void){
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);
    ll D;
    cin >> D;
    vector<double> c(27,0);
    for(ll i=0;i<26;++i)cin>>c[i+1];
    vector<vector<double>> S(D+1, vector<double>(27, 0));
    for(ll i=0;i<D;++i)
        for(ll j=0;j<26;++j)cin>>S[i+1][j+1];
    ll Maxscore=-INF;
    vl ans;
    for(double k=10;k<=40;k+=0.2){
        vector<ll> last(27,0);
        ll score=0;
        vector<ll> t(D+1,0);
        for(ll i=1;i<=D;++i){
            set<P> hoge;
            for(ll j=1;j<=26;++j){
                hoge.insert(P(S[i][j]+c[j]*k,j));
            }
            t[i]=(*--hoge.end()).second;
            last[t[i]]=i;
            score+=S[i][t[i]];
            for(ll j=1;j<=26;++j)score-=c[j]*(i-last[j]);
        }
        if(chmax(Maxscore,score))ans=t;
    }
    for(ll i=1;i<=D;++i)prt(ans[i]);

    return 0;
}



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

Measured memory_bytes: 38384
if __name__ == '__main__':
    N = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))

    b_minus_a = [tmp_b - tmp_a for tmp_a, tmp_b in zip(a, b)]

    if 2 * -sum([_ for _ in b_minus_a if _ < 0]) <= sum([_ - 1 for _ in b_minus_a if _ > 1 and _ % 2 == 1]) + sum(
            [_ for _ in b_minus_a if _ > 1 and _ % 2 == 0]):
        print('Yes')
    else:
        print('No')


Measured memory_bytes: 4660
def divide_2(n):
    i = 0
    while 1:
        if n % 2 == 0:
            n /= 2
            i += 1
        else:
            return i

N = int(input())
A = list(map(int,input().split()))

ans = 201
for i in A:
    i_div2 = divide_2(i)
    if i_div2 < ans:
        ans = i_div2

print(ans)

Measured memory_bytes: 3060
#include<bits/stdc++.h>
#define p 1000000007
#define N 200005
using namespace std;
int n,ans;
int C[N],dp[N];
int last[N];
inline void add(int &a,int b){a+=b;if(a>p)a-=p;}
inline void Rd(int &res){
	char c;res=0;
	while(c=getchar(),c<48);
	do res=(res<<3)+(res<<1)+(c^48);
	while(c=getchar(),c>47);
	return;
}
int main(){
	Rd(n);
	for(int i=1;i<=n;i++)Rd(C[i]);
	dp[0]=1;
	for(int i=1;i<=n;i++){
		if(C[i]==C[i-1]){
			dp[i]=dp[i-1];continue;
		}
		if(last[C[i]])add(dp[i],dp[last[C[i]]]);
		add(dp[i],dp[i-1]);
		last[C[i]]=i;
	}
	printf("%d\n",dp[n]);
	return 0;
}

Measured memory_bytes: 2560
import math
N = int(input())
fn_array = [0] * 60000
for x in range(1, 100):
    for y in range(1, x + 1):
        for z in range(1, y + 1):
            n = x ** 2 + y ** 2 + z ** 2 + x * y + y * z + z * x
            if x == y and y == z:
                fn_array[n] += 1
            elif (x == y) and (y != z):
                fn_array[n] += 3
            elif (x != y) and (y == z):
                fn_array[n] += 3
            else:
                fn_array[n] += 6
for n in range(1, N+1):
    print(fn_array[n])


Measured memory_bytes: 9452
#include<iostream>
#include<cstdio>
#include<map>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 100100;
map<string,int> mp;
char name[16];
int pp[maxn];
int main()
{
    int n,p=1;
    scanf("%d",&n);
    long long cnt = 0;
    fill(pp,pp+maxn,1);
    while(n--){
        scanf("%s",name);
        sort(name,name+strlen(name));
        int q = mp[string(name)];
        if(q!=0){
            pp[q]++;
        }
        else mp[string(name)] = p++;
    }
    for(int i=1;i<maxn;i++){
        if(pp[i]>1){
            cnt += (long long)pp[i]*(pp[i]-1)/2;
        }
    }
    mp.clear();
    printf("%lld\n",cnt);
    return 0;
}


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

mod = 10 ** 9 + 7

sx = 0
for i in range(n-1):
    xi = (x[i+1] - x[i]) % mod
    sx += (i + 1) * (n - i - 1) * xi % mod
    sx %= mod

sy = 0

for i in range(m-1):
    yi = (y[i+1] - y[i]) % mod
    sy += (i + 1) * (m - i - 1) * yi % mod
    sy %= mod

print((sx*sy)%mod)



Measured memory_bytes: 24480
#include<bits/stdc++.h>
using namespace std;
int main(){
   	int N;
    cin >> N;
    long long a[N];
  	for(int i = 0; i < N; ++i){
      cin >> a[i];
    }
  	int j = 0;
  	int ans = 0;
  	while(a[j] % 2 == 0){
      a[j] /= 2;
      j++;
      if(j == N){
        j = 0;
        ans++;
      }
    }
   
    cout << ans << endl;
}

Measured memory_bytes: 256
a, b, c = map(int, input().split())
rec = sorted([a, b, c])
if (a % 2 == 0 and b % 2 == 0 and c % 2 == 0) or (a % 2 != 0 and b % 2 != 0 and c % 2 != 0):
    print((rec[2] * 2 - rec[1] - rec[0]) // 2)
elif a % 2 == 0 and b % 2 == 0 and c % 2 != 0:
    a, b = a + 1, b + 1
    rec = sorted([a, b, c])
    print((rec[2] * 2 - rec[1] - rec[0]) // 2 + 1)
elif a % 2 != 0 and b % 2 == 0 and c % 2 == 0:
    c, b = c + 1, b + 1
    rec = sorted([a, b, c])
    print((rec[2] * 2 - rec[1] - rec[0]) // 2 + 1)
elif a % 2 == 0 and b % 2 != 0 and c % 2 == 0:
    a, c = a + 1, c + 1
    rec = sorted([a, b, c])
    print((rec[2] * 2 - rec[1] - rec[0]) // 2 + 1)
elif a % 2 != 0 and b % 2 != 0 and c % 2 == 0:
    a, b = a + 1, b + 1
    rec = sorted([a, b, c])
    print((rec[2] * 2 - rec[1] - rec[0]) // 2 + 1)
elif a % 2 == 0 and b % 2 != 0 and c % 2 != 0:
    c, b = c + 1, b + 1
    rec = sorted([a, b, c])
    print((rec[2] * 2 - rec[1] - rec[0]) // 2 + 1)
elif a % 2 != 0 and b % 2 == 0 and c % 2 != 0:
    a, c = a + 1, c + 1
    rec = sorted([a, b, c])
    print((rec[2] * 2 - rec[1] - rec[0]) // 2 + 1)

Measured memory_bytes: 3192
#include <iostream>
#include <string>
#include <cmath>

using namespace std;

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

    long long int ansa = 0;
    long long int ansb = 0;
    for (long long int i = 0; i < s.size(); i++) {
        if (i % 2 == 0) {
            if (s[i] == '1') {
                ansa++;
            } else {
                ansb++;
            }
        } else {
            if (s[i] == '0') {
                ansa++;
            } else {
                ansb++;
            }
        }
    }

    cout << min(ansa, ansb) << endl;

    return 0;
}

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

using namespace std;

int main()
{
    int n,x,t;
    cin >> n >> x >> t;

    int ans = 0;

    while(n){
        ans += t;
        if (n >= x) n -= x;
        else n = 0;
    }

    cout << ans;

    return 0;
}


Measured memory_bytes: 3620
#include<bits/stdc++.h>
using namespace std;
int main(){
	int n;
	while(cin >> n){
		int p[n];
		int sum=0;
		int time=0;
		for(int i=0;i<n;i++){
			cin >> p[i];
		}
		sort(p,p+n);
		for(int i=0;i<n;i++){
			sum+=time+p[i];
			time+=p[i];
		}


		cout << sum << endl;
	}
}

Measured memory_bytes: 3028
import java.util.Scanner;

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

        if (n < 100) {
            System.out.println(9 - (9 - Math.min(n, 9)));
        } else if (n < 10000) {
            System.out.println(909 - (999 - Math.min(n, 999)));
        } else {
            System.out.println(90909 - (99999 - Math.min(n, 99999)));
        }
    }
}


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

#define int long long
const int INF = 1e18;

signed main() {
  int N;
  cin >> N;

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

  int ma = -INF;
  int sum[2] = {0};
  vector<int> p[2];
  int cntm = 0;  
  for ( int i = 0; i < N; i++ ) {
    ma = max(ma, a[i]);
    if ( a[i] >= 0 ) {
      sum[i%2] += a[i];
      p[i%2].emplace_back(i);
    } else {
      cntm++;
    }
  }  
  
  if ( ma >= 0 ) {
    vector<int> ans;
    if ( sum[0] > sum[1] ) {
      cout << sum[0] << endl;
      int off = 0;
      for ( int i = 0; i < p[0][0]; i++ ) ans.emplace_back(i+1+off), off--;
      for ( int i = N-1; i > (int)p[0][p[0].size()-1]; i-- ) ans.emplace_back(i+1+off);
      for ( int i = 1; i < p[0].size(); i++ ) {
	for ( int j = 0; j < (p[0][i]-p[0][i-1])/2; j++ ) {
	  ans.emplace_back((p[0][i]+p[0][i-1])/2-j+1+off);
	}
	off -= (p[0][i]-p[0][i-1]);
      }
    } else {    
      cout << sum[1] << endl;
      int off = 0;
      for ( int i = 0; i < p[1][0]; i++ ) ans.emplace_back(i+1+off), off--;
      for ( int i = N-1; i > (int)p[1][p[1].size()-1]; i-- ) ans.emplace_back(i+1+off);
      for ( int i = 1; i < p[1].size(); i++ ) {
	for ( int j = 0; j < (p[1][i]-p[1][i-1])/2; j++ ) {
	  ans.emplace_back((p[1][i]+p[1][i-1])/2-j+1+off);
	}
	off -= (p[1][i]-p[1][i-1]);
      }
    }

    cout << ans.size() << endl;
    for ( int i : ans ) cout << i << endl;
  } else {
    cout << ma << endl;
    cout << N-1 << endl;
    int off = 0;
    int i;
    for ( i = 0; a[i]!=ma; i++ )  cout << 1 << endl, off--;
    for ( int j = N-1; j > i; j-- ) cout << j+1+off << endl;
  }
  
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main () {
  int N;
  cin >> N;
  vector<pair<string,int>> data(N), sub(N);
  for(int i = 0; i < N; i++){
    cin >> data.at(i).first >> data.at(i).second;
    data.at(i).second = -data.at(i).second;
    sub.at(i).first = data.at(i).first;
    sub.at(i).second = data.at(i).second;
  }
  sort(data.begin(), data.end());
  for(int i = 0; i < N; i++){
    for(int j = 0; j < N; j++){
      if(data.at(i).first == sub.at(j).first && data.at(i).second == sub.at(j).second){
        cout << j + 1 << endl;
        break;
      }
    }
  }
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
#include<stdio.h>
#include<cstring>
#include<math.h>
#include<map>
#include<bitset>
#include<iomanip>
#include<queue>
using namespace std;

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
using P = pair<int, int>;

long long N;
long long a[100000];



int main() {
  cin >> N;
  long long ans = 1;
  rep(i, N) {
    long long x;
    cin >> x;
    a[i] = x;
    if(x == 0) {
      cout << 0 << endl;
      return 0;
    }
  }

  rep(i, N) {
    // if(ans > 1000000000000000000) {
    //   cout << -1 << endl;
    //   return 0;
    // }
    // if(ans == 1000000000000000000) {
    //   if(a[i] > 1) {
    //     cout << -1 << endl;
    //   }
    // }
    if(1000000000000000000 / ans < a[i]) {
      cout << -1 << endl;
      return 0;
    }
    ans *= a[i];
  }
  cout << ans << endl;
  return 0;
  // 1000000000000000000
}

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

int main() {
  int n;
  cin >> n;
  vector<int> p(n);
  vector<int> q(n);
  rep(i, n) {
    int a;
    cin >> a;
    p[i] = q[i] = a;
  }
  sort(q.begin(), q.end());
  int cnt = 0;
  rep(i, n) {
    if (q[i] != p[i]) cnt++;
  }
  string ans = cnt <= 2 ? "YES" : "NO";
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
from collections import deque
S = input()
Q = int(input())

n = S
mode = 0
operations = []
deq = deque(n)
for i in range(Q):
    operations.append(input().split())
for op in operations:
    if op[0] == "1":
        mode += 1
        mode %= 2
    elif int(op[1]) + mode == 2:
        deq.append(op[2])
    else:
        deq.appendleft(op[2])
if mode == 0:
    print("".join(deq))
else:
    print("".join(reversed(deq)))

Measured memory_bytes: 44660
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.NoSuchElementException;

public class Main {
	int N,A;
	int[] x;
	long[][][] dp;
	public long dfs(int n,int sum,int c){

		if(n == N){
			if(c > 0 && sum % c == 0 && sum / c == A){
				return 1;
			}else{
				return 0;
			}
		}

		if(dp[n][sum][c] != -1)return dp[n][sum][c];

		long ret = 0;
		ret += dfs(n + 1,sum + x[n],c + 1);
		ret += dfs(n + 1,sum,c);
		return dp[n][sum][c] = ret;
	}

	public void solve() {
		N = nextInt();
		A = nextInt();
		x = new int[N];
		for(int i = 0;i < N;i++){
			x[i] = nextInt();
		}
		dp = new long[N + 1][2500 + 1][50 + 1];
		for(int i = 0;i <= N;i++){
			for(int j = 0;j <= 2500;j++){
				for(int k = 0;k <= 50;k++){
					dp[i][j][k] = -1;
				}
			}
		}
		out.println(dfs(0,0,0));
	}

	public static void main(String[] args) {
		out.flush();
		new Main().solve();
		out.close();
	}

	/* Input */
	private static final InputStream in = System.in;
	private static final PrintWriter out = new PrintWriter(System.out);
	private final byte[] buffer = new byte[2048];
	private int p = 0;
	private int buflen = 0;

	private boolean hasNextByte() {
		if (p < buflen)
			return true;
		p = 0;
		try {
			buflen = in.read(buffer);
		} catch (IOException e) {
			e.printStackTrace();
		}
		if (buflen <= 0)
			return false;
		return true;
	}

	public boolean hasNext() {
		while (hasNextByte() && !isPrint(buffer[p])) {
			p++;
		}
		return hasNextByte();
	}

	private boolean isPrint(int ch) {
		if (ch >= '!' && ch <= '~')
			return true;
		return false;
	}

	private int nextByte() {
		if (!hasNextByte())
			return -1;
		return buffer[p++];
	}

	public String next() {
		if (!hasNext())
			throw new NoSuchElementException();
		StringBuilder sb = new StringBuilder();
		int b = -1;
		while (isPrint((b = nextByte()))) {
			sb.appendCodePoint(b);
		}
		return sb.toString();
	}

	public int nextInt() {
		return Integer.parseInt(next());
	}

	public long nextLong() {
		return Long.parseLong(next());
	}

	public double nextDouble() {
		return Double.parseDouble(next());
	}
}

Measured memory_bytes: 77604
#include<iostream>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
int c[200],d[200];
int main(){
	int n,m,k;
	cin>>n>>m;
	rep(i,n*2)c[i]=i+1;
	rep(u,m){
		cin>>k;
		if(k)rep(i,n*2){if(i<k)d[i+2*n-k]=c[i];else d[i-k]=c[i];}
		else rep(i,n*2){if(i<n)d[i*2]=c[i];else d[(i-n)*2+1]=c[i];}
		rep(i,n*2)c[i]=d[i];
	}
	rep(i,n*2)cout<<c[i]<<endl;
	return 0;
}

Measured memory_bytes: 3080
my $s =<>;
chomp $s;
my ($A,$B) = split(/ /,$s);
my $A1 = int($A/0.08);
my $A2 = ($A+0.99)/0.08;
my $B1 = int($B/0.1);
my $B2 = ($B+0.99)/0.1;
#print "$A1 $A2 $B1 $B2 \n";

if($A1<=$B2 && $B1 <=$A1){
    if(int($A1*0.08)!=$A ){$A1++;}
    print "$A1";
}elsif($B1<=$A2 && $A1<=$B1  ){
    if(int($B1*0.1)!=$B ){$B1++;}
    print "$B1";
}else{
    print "-1";
}

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

int main(){
  int64_t n;
  cin>>n;
 vector<int64_t> res;
  for(int64_t i=1;i*i<=n; i++){
  if(n%i==0){
  res.push_back(i);
  if(i!=n/i)res.push_back(n/i);
  }}
   vector<int64_t> res2;
 int64_t  m=n-1;
  for(int64_t i=1;i*i<=m; i++){
  if(m%i==0){
  res2.push_back(i);
  if(i!=m/i)res2.push_back(m/i);
  }}
   vector<int64_t> res3;
for(int64_t i=0;i<res.size();i++){
  int64_t j = res.at(i); 
 int64_t  k=n;
while (j!=1&&1==1) {
if(k!=0&&k%j==0){k=k/j;}
  if(k%j==1){res3.push_back(j);
               break;  }
  if(k==0||k%j>=2){break;}
  }
  
}
  cout<<res2.size()+res3.size()-1<<endl;
}
  
  

Measured memory_bytes: 384
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cstdlib>
#include <map>
#include <math.h>
#include <numeric>
using namespace std;
int main(){
  int S;
  int W;
  cin >> S >> W;
  if(W>=S)cout << "unsafe" << endl;
  else cout << "safe" << endl;
}

Measured memory_bytes: 3636
#include <stdio.h>
#include <stdbool.h>
#define N 8
#define A -1
#define B 1
int row[N],col[N],dpos[2*N-1],dneg[2*N-1];
bool X[N][N];
void kansuu1(){
  int i,j;
  for(i=0;i<N;i++){
    row[i]=A;
    col[i]=A;
  }
  for(i=0;i<2*N-1;i++){
    dpos[i]=A;
    dneg[i]=A;
  }
}
void kansuu2(){
  int i,j;
  for(i=0;i<N;i++){
    for(j=0;j<N;j++){
      if(X[i][j]){
	if(row[i]!=j) return;
      }
    }
  }
  for(i=0;i<N;i++){
    for(j=0;j<N;j++){
      if(row[i]==j) printf("Q");
      else printf(".");
    }
    printf("\n");
  }
}
void kansuu3(int i){
  int j;
  if(i==N){
    kansuu2();return;
  }
  for(j=0;j<N;j++){
    if(B==col[j]||B==dpos[i+j]||B==dneg[i-j+N-1]) continue;
    row[i]=j;
    col[j]=dpos[i+j]=dneg[i-j+N-1]=B;
    kansuu3(i+1);
    row[i]=col[j]=dpos[i+j]=dneg[i-j+N-1]=A;
  }
}
int main(void){
  int i,j,k,r,c;
  kansuu1();
  for(i=0;i<N;i++){
    for(j=0;j<N;j++){
      X[i][j]=false;
    }
  }
  scanf("%d",&k);
  for(i=0;i<k;i++){
    scanf("%d %d",&r,&c);
    X[r][c]=true;
  }
  kansuu3(0);
  return 0;
}
  



Measured memory_bytes: 2108
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>

#define REP(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define ALL(x) (x).begin(), (x).end()
#define SIZE(x) ((int)(x).size())

using namespace std;
typedef long long ll;

const long long MOD = 1000000007;

ll dp[100001][13];
void solve(std::string S){
  dp[0][0] = 1;
  REP(i, S.size() + 1) {
    int digit = S[i] == '?' ? -1 : S[i] - '0';

    REP(j, 13) {
      REP(k, 10) {
        if (digit != -1 && k != digit) continue;

        dp[i + 1][(j * 10 + k) % 13] += dp[i][j];
      }
    }

    REP(j, 13) {
      dp[i + 1][j] %= MOD;
    }
  }

  printf("%lld\n", dp[S.size()][5]);
}

int main(){
  std::string S;
  std::cin >> S;
  solve(S);
  return 0;
}


Measured memory_bytes: 10624
use std::io::*;
use std::str::FromStr;

fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();

    token.parse().ok().expect("failed to parse token")
}

fn gcd(a: u64, b: u64) -> u64 {
    // a > bでユークリッド互除法が進む。
    // a < bの場合、 a % b = aで gcd(b,a)が再帰的にコールされる。
    if b == 0 {
        return a;
    }
    gcd(b, a % b)
}

fn main() {
    let a: u64 = read();
    let b: u64 = read();
    println!("{}", a * b / gcd(a, b));
}


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

using namespace std;
int a, b, c, d;

void do_it(char x, char y, char z) {
  cout << a << x << b << y << c << z << d << "=7\n";
  exit(0);
}
int main() {
  char i, j, k, l;
  cin >> i >> j >> k >> l;
  a = i - '0';
  b = j - '0';
  c = k - '0';
  d = l - '0';
  /// +++ --- +-+ -+- ++- --+ +--, -++
  if (a + b + c + d == 7) {
    do_it('+', '+', '+');
  }
  if (a - b - c - d == 7) {
    do_it('-', '-', '-');
  }
  if (a + b - c + d == 7) {
    do_it('+', '-', '+');
  }
  if (a - b + c - d == 7) {
    do_it('-', '+', '-');
  }
  if (a + b + c - d == 7) {
    do_it('+', '+', '-');
  }
  if (a - b - c + d == 7) {
    do_it('-', '-', '+');
  }
  if (a + b - c - d == 7) {
    do_it('+', '-', '-');
  }
  if (a - b + c + d == 7) {
    do_it('-', '+', '+');
  }
  return 0;
}


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

typedef long long ll;

#define optimize() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define file() freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
#define tt int t; cin>>t; while(t--)
#define nl cout<<"\n";
#define sp cout<<" ";
#define rep(i, a, b) for(long long i=a; i<b; i++)

const int INF = 1e9 + 7;
const int MOD = 1e9 + 7;
double PI = 4*atan(1);

int main()
{
    optimize();

    string s, t;

    cin>> s>> t;

    cout<< (t.substr(0, s.size()) == s? "Yes\n": "No\n");

    return 0;
}




Measured memory_bytes: 3652
import bisect


def main():
    N = int(input())
    L = list(map(int, input().split()))
    L.sort()

    ans = 0
    for i in range(N - 2):
        for j in range(i + 1, N - 1):
            index = bisect.bisect_left(L, L[i] + L[j]) - j - 1
            ans += index

    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 3188
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
typedef long long ll;
typedef long double ld;
const int inf=1e9+7;
const ll longinf=1LL<<60;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
#define F first
#define S second

const int mx=200010;
const ll mod=1e9+7;

 
int main(){  
  int q;
  cin >> q;
  rep(i,q){
    ll ans=0;
    ll a,b; cin >> a >> b;
    if(a>b){swap(a,b);}
    ll sq = (ll)floor((ld)sqrt((ld)(a*b-1)));
    if(a==b || b-a==1 ){cout << (a-1)*2 << endl; continue;}
    ans = (a-1)*2 + 1 + (sq-a)*2;
    if(sq*(sq+1)>a*b-1){ ans--; }
    cout << ans << endl;
  }
  return 0;
}

Measured memory_bytes: 384
it = lambda: list(map(int, input().strip().split()))


def solve():
    n = int(input())
    ok = False
    cnt = 0
    for _ in range(n):
        a, b = it()
        if a == b:
            cnt += 1
            if cnt == 3:
                ok = True
        else:
            cnt = 0
    return 'Yes' if ok else 'No'

if __name__ == '__main__':
    print(solve())

Measured memory_bytes: 9188
#include<stdio.h>

int main()
{
    int a,b,x;

    scanf("%d %d %d",&a,&b,&x);

    if((a+b>x && a==x)||(a+b)>x && a<x)
    {
        printf("YES\n");
    }
    else if(a>x || a+b<x)
    {
        printf("NO\n");
    }


    return 0;
}


Measured memory_bytes: 1628
// lcmとか__builtin_popcountとかはg++ -std=c++17 default.cppみたいなかんじで
// g++ hoge.cpp -std=c++17 -I . でコンパイルできる
// -fsanitize=undefinedでオーバーフロー検出
#include <bits/stdc++.h>
//#include <atcoder/all>
#define mod 1000000007
#define INF LLONG_MAX
#define ll long long
#define ln cout<<endl
#define Yes cout<<"Yes"<<endl
#define NO cout<<"NO"<<endl
#define YES cout<<"YES"<<endl
#define No cout<<"No"<<endl
#define REP(i,m,n) for(ll i=(ll)(m);i<(ll)(n);i++)
#define rep(i,n) REP(i,0,n)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
using namespace std;
//using namespace atcoder;
typedef pair<ll,ll> P;
ll dx[4]={1,0,-1,0};
ll dy[4]={0,1,0,-1};

class mint {
    long long x;
public:
    mint(long long x=0) : x((x%mod+mod)%mod) {}
    mint operator-() const { 
      return mint(-x);
    }
    mint& operator+=(const mint& a) {
        if ((x += a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator-=(const mint& a) {
        if ((x += mod-a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator*=(const  mint& a) {
        (x *= a.x) %= mod;
        return *this;
    }
    mint operator+(const mint& a) const {
        mint res(*this);
        return res+=a;
    }
    mint operator-(const mint& a) const {
        mint res(*this);
        return res-=a;
    }
    mint operator*(const mint& a) const {
        mint res(*this);
        return res*=a;
    }
    mint pow(ll t) const {
        if (!t) return 1;
        mint a = pow(t>>1);
        a *= a;
        if (t&1) a *= *this;
        return a;
    }
    // for prime mod
    mint inv() const {
        return pow(mod-2);
    }
    mint& operator/=(const mint& a) {
        return (*this) *= a.inv();
    }
    mint operator/(const mint& a) const {
        mint res(*this);
        return res/=a;
    }

    friend ostream& operator<<(ostream& os, const mint& m){
        os << m.x;
        return os;
    }
};

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

    ll a,b,c,d,m,n,k,x,y,maxi=0,f=0,mini=INF;
    mint sum=0;
    string str;
    cin>>n;
    mint dp[n+5][n+5];
    rep(i,n){
        dp[0][i]=0;
    }
    rep(i,n){
        dp[1][i]=1;
    }
    for(ll i=2;i<n;i++){
        rep(j,n) dp[i][j]=0;
    }
    if(n<=2){
        cout<<0<<endl;
        return 0;
    }
    ll start=2;
    for(ll i=2;i<n;i++){
        for(ll j=start;j<n;j++){
            dp[i][j]=dp[i-1][j-3]+dp[i][j-1];
        }
        start+=3;
    }
    rep(i,n){
        rep(j,n){
           // cout<<dp[i][j]<<" ";
        }
       // ln;
    }
    rep(i,n){
        sum+=dp[i][n-3];
    }
    cout<<sum<<endl;

    return 0;
}


Measured memory_bytes: 35008
#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,a,b;
  
  cin >> a >> b;
  
  rep(i,3){
  	if(a!=i+1&&b!=i+1){
    	cout << i+1 << endl;
      break;
    }
  }


	return 0;
}

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


def main():
    s = input()
    N = len(s)
    K = int(input())
    X = set()
    for i in range(1,K+1):
        for j in range(N-i+1):
            X.add(s[j:j+i])
    print(sorted(X)[K-1])

if __name__ == "__main__":
    main()


Measured memory_bytes: 4464
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define pb push_back
#define maxm 1e18
#define minm -1e18
#define pr pair<ll,ll>
#define mod 1000000007
#define N 3001
ll dp[N][N];

void add_self(ll &a,ll b)
{
	a=(a+b)%mod;
}

/*O(n^3) - complexity
void solve()
{
	ll n,len,a,b,i;
	cin>>n;
	string cmp;
	cin>>cmp;
	dp[1][1]=1;
	//dp[i][j] -> number of ways to put numbers in
	//prefix of size 'i' such that last number is 'j5'
	
	for(len=2;len<=n;len++)
	{
		for(b=1;b<=len;b++)
		{
			for(a=1;a<=len-1;a++)
			{
				ll real_a=a;
				if(a>=b)
					real_a++;
				if((real_a<b)!=(cmp[len-2]=='<'))	continue;
				add_self(dp[len][b],dp[len-1][a]);
			}
		}
		cout<<"len is "<<len<<endl;
		for(i=1;i<=n;i++)
			cout<<dp[len][i]<<" ";
		cout<<endl;
	}
	ll ans=0;
	for(i=1;i<=n;i++)
		add_self(ans,dp[n][i]);
	cout<<ans<<endl;
}*/

//O(n^2) - complexity
void solve()
{
	ll n,len,a,b,i,l,r;
	cin>>n;
	string cmp;
	cin>>cmp;
	dp[1][1]=1;
	//dp[i][j] -> number of ways to put numbers in
	//prefix of size 'i' such that last number is 'j'
	for(len=2;len<=n;len++)
	{
		ll prefix[n+1];
		prefix[0]=0;
		for(b=1;b<len;b++)
			prefix[b]=(prefix[b-1]+dp[len-1][b]);
		for(b=1;b<=len;b++)
		{
			
			if(cmp[len-2]=='>'){
				l=1,r=b-1;
			}
			else{
				l=b,r=len-1;
			}
			if(l<=r)
				add_self(dp[len][b],(mod-prefix[l-1]+prefix[r]));
		}
	}
	ll ans=0;
	for(i=1;i<=n;i++)
		add_self(ans,dp[n][i]);
	cout<<ans<<endl;
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);
    	ll t=1;
	//cin>>t;
	while(t--)
	{
		solve();
	}
	return 0;
}

Measured memory_bytes: 68992
#include <stdio.h>
#include <string>
#include <iostream>
#include <iomanip>
#include <map>
#include <algorithm>
#include <vector>
#include <math.h>
#define MOD 1000000007
using namespace std;

int main(void){
    int n,count=0;
    cin >> n;
    vector<int> flower(n);
    for(int i=0; i<n; i++){
        cin >> flower[i];
    }
    for(int i=0; i<n; i++){
        while(flower[i]>0){
            count++;
            for(int j=i; j<n; j++){
                if(flower[j]>0)flower[j]--;
                else break;
            }
        }
    }
    cout << count << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
using namespace std;
using ll = long long;
using ld = long double;

int main(){
  ios_base::sync_with_stdio(false);cin.tie(0);
  int N;
  cin >> N;
  vector<int> ans(N,0);
  for(int i=0;i<N-1;i++){
    int a;
    cin >> a;
    a--;
    ans.at(a)++;
  }

  for(int i=0;i<N;i++)  cout << ans.at(i) << endl;

  return 0;
}

Measured memory_bytes: 3992
#define y1 askjdkasldjlkasd
#include <bits/stdc++.h>
#undef y1

using namespace std;

#define pb push_back
#define mp make_pair
#define fi(a, b) for(int i=a; i<=b; i++)
#define fj(a, b) for(int j=a; j<=b; j++)
#define fo(a, b) for(int o=a; o<=b; o++)
#define fdi(a, b) for(int i=a; i>=b; i--)
#define fdj(a, b) for(int j=a; j>=b; j--)
#define fdo(a, b) for(int o=a; o>=b; o--)
#define sz(x) (int)x.size()

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
typedef vector<ll> vll;

#ifdef LOCAL
#define err(...) fprintf(stderr, __VA_ARGS__)
#else
#define err(...) while (0)
#endif

double START_TIME;

void exit() {
#ifdef LOCAL	
	cerr << "TIME: " << setprecision(5) << fixed << (clock() - START_TIME) / CLOCKS_PER_SEC << endl;
#endif	
	exit(0);
}

template<typename A, typename B>
ostream& operator<<(ostream& os, pair<A, B> p) {
	os << "(" << p.first << ", " << p.second << ")";
	return os;
}

template<typename T>
ostream& operator<<(ostream& os, vector<T> v) {
	fi(0, sz(v) - 1) {
		os << v[i] << " ";
	}
	return os;
}

template<typename T>
ostream& operator<<(ostream& os, set<T> t) {
	for (auto z : t) {
		os << z << " ";
	}
	return os;
}

template<typename T1, typename T2>
ostream& operator<<(ostream& os, map<T1, T2> t) {
	cerr << endl;
	for (auto z : t) {
		os << "\t" << z.first << " -> " << z.second << endl;
	}
	return os;
}

#ifdef LOCAL
#define dbg(x) {cerr << __LINE__ << "\t" << #x << ": " << x << endl;}
#define dbg0(x, n) {cerr << __LINE__ << "\t" << #x << ": "; for (int ABC = 0; ABC < n; ABC++) cerr << x[ABC] << ' '; cerr << endl;}
#else
#define dbg(x) while(0){}
#define dbg0(x, n) while(0){}
#endif

#ifdef LOCAL
#define ass(x) if (!(x)) { cerr << __LINE__ << "\tassertion failed: " << #x << endl, abort(); }
#else
#define ass(x) assert(x)
#endif

///////////////////////////////////////////////////

const int MAX = 2e5 + 41;
string F = "First";
string S = "Second";

void print(string s) {
	printf("%s\n", s.c_str());
	exit(0);
} 

int n;
vi e[MAX];
int d[MAX];

void init() {
	d[0] = 1;	
	fi(1, MAX - 1) {
		d[i] = 1 - d[i - 1];
		if (i >= 2) {
			d[i] = max(d[i], 1 - d[i - 2]);
		}
	}
	dbg0(d, 10);
}

int dist0[MAX];
int dist1[MAX];

void dfs(int x, int p, int dist[MAX]) {
	for (int y : e[x]) {
		if (y == p) continue;
		dist[y] = dist[x] + 1;
		dfs(y, x, dist);
	}
}

void solve () {
	if (n == 1)	print(F);
	if (n == 2) print(S);

	dfs(0, -1, dist0);
	pii v1 = mp(-1, -1);
	fi(0, n - 1) {
		v1 = max(v1, mp(dist0[i], i));
	}
	dfs(v1.second, -1, dist1);
	int a = v1.second;
	pii v2 = mp(-1, -1);
	fi(0, n - 1) {
		v2 = max(v2, mp(dist1[i], i));
	}	
	int dm = v2.first;
	dbg(a);
	dbg0(dist1, n);
	dbg(dm);
	if (d[dm]) {
		print(F);
	} else {
		print(S);
	}
}

int main() {
#ifdef LOCAL
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
	START_TIME = (double)clock();
#endif

	init();	
	scanf("%d", &n);
	fi(0, n - 2) {
		int x, y;
		scanf("%d %d", &x, &y);
		x--, y--;
		e[x].pb(y);
		e[y].pb(x);
	}
	solve();

	exit();
	return 0;
}





Measured memory_bytes: 25984
#include<stdio.h>

int main(void){
    int list[3],i,p,q,r,min=100000;
    scanf("%d %d %d",&p,&q,&r);
    list[0]=p+q;
    list[1]=q+r;
    list[2]=r+p;
    for(i=0;i<3;i++){
        if(min>list[i]){
            min=list[i];
        }
    }
    printf("%d",min);
    return 0;
}


Measured memory_bytes: 128
A,B = map(int,input().split())
import math

def my_index_multi(l, x):
    return [i for i, _x in enumerate(l) if _x == x]

la = [-1]*10099
lb = [-1]*10099


for i in range(10099):
  la[i] = math.floor(i*0.08) 

for i in range(10099):
  lb[i] = math.floor(i*0.1)

alist = (my_index_multi(la,A))
blist = (my_index_multi(lb,B))

alist.sort()
blist.sort()


andl = list(set(alist) & set(blist))
andl.sort()
if len(andl) > 0:
  print(andl[0])
  
else :
  print(-1)

Measured memory_bytes: 3828
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ABC068
{
    class Program
    {
        static void Main(string[] args)
        {
            int n;
            n = int.Parse(Console.ReadLine());
            Console.WriteLine("ABC"+n);
            Console.ReadKey();
        }
    }
}

Measured memory_bytes: 11092