akhauriyash/Code-Regression huggingface dataset:
import java.util.*;
import java.io.*;

public class Main {
	static PrintWriter out;
	static StringBuilder sb;
	static int mod = 1000000007;
	static long inf = (long) 1e16;
	static int[] l, r;
	static int n, c, t;
	static ArrayList<Integer>[] ad;
	static long[][][] memo;
	static boolean f;
	static boolean[] vis[];
	static int[][] mat, mat1;
	static int[] ans, a;
	static ArrayList<Integer> rr, bb, gg;

	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		out = new PrintWriter(System.out);
        int ans=0;
        String s=sc.nextLine();
        if(s.contains("R"))
        	ans++;
        if(s.contains("RR"))
        	ans++;
        if(s.contains("RRR"))
        	ans++;
        System.out.println(ans);
		out.flush();
	}

	static class Scanner {
		StringTokenizer st;
		BufferedReader br;

		public Scanner(InputStream system) {
			br = new BufferedReader(new InputStreamReader(system));
		}

		public Scanner(String file) throws Exception {
			br = new BufferedReader(new FileReader(file));
		}

		public String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}

		public String nextLine() throws IOException {
			return br.readLine();
		}

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

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

		public char nextChar() throws IOException {
			return next().charAt(0);
		}

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

		public int[] nextArrInt(int n) throws IOException {
			int[] a = new int[n];
			for (int i = 0; i < n; i++)
				a[i] = nextInt();
			return a;
		}

		public long[] nextArrLong(int n) throws IOException {
			long[] a = new long[n];
			for (int i = 0; i < n; i++)
				a[i] = nextLong();
			return a;
		}

		public boolean ready() throws IOException {
			return br.ready();
		}

		public void waitForInput() throws InterruptedException {
			Thread.sleep(3000);
		}
	}
}


Measured memory_bytes: 25424
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<stdbool.h>
#include<math.h>

int a,b,c,s,m;
int K;
int main(){
#ifdef DEBUG
	printf("DEBUGGING ON\n");
#endif
	scanf("%d %d %d %d",&a,&b,&c,&K);
	s=a+b+c;
	if (a<b) a=b;
	if (a<c) a=c;
	m= a*(int)pow(2.0,K);
	printf("%d\n",m+s-a);
	return (0);
}

Measured memory_bytes: 128
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {


		Scanner sc = new Scanner(System.in);
		long X = sc.nextLong();

		long deposit = 100;
		long cnt = 0;
		
		for(;;) {
			cnt++;
			deposit = (long)Math.floor(deposit * 1.01);
			if(deposit >= X) {
				System.out.println(cnt);
				return;
			}
		}

	}

}


Measured memory_bytes: 35820
#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 a, b, c;
    cin >> a >> b >> c;
    int sum = a + b +c;

    rep(i,1000000){
        int sum = a * i + b + c;
        if (a * i % a == 0 &&  a * i % b == c){
            
            cout << "YES" << endl;
            return 0 ;
        }
    }
    cout << "NO" << endl;
    return 0;
}

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

int main() {
  int H, W, i, j, k, l;
  cin >> H >> W;
  string s[H];
  
  for(i=0; i<H; i++)
    cin >> s[i];
  
  for(i=0; i<H; i++)
    for(j=0; j<W; j++) {
      if(s[i].at(j) == '.') {
        int bomb = 0;
        for(k=i-1; k<=i+1; k++)
          for(l=j-1; l<=j+1; l++)
            if(k>=0 && k<H && l>=0 && l<W && s[k].at(l) == '#')
              bomb++;
        s[i].at(j) = char(bomb + '0');
      }
    }
  
  for(i=0; i<H; i++)
    cout << s[i] << endl;
}


Measured memory_bytes: 256
#include <stdio.h>
long long n, k, t, s, m, f;
long long a[15];
int b[15];
long long c[15];
int main() {
	scanf("%lld%lld", &n, &k);
	for (int i = 0; i < n; i++) {
		scanf("%lld", a + i);
	}
	m = 20000000000;
	for (int i = 0; i < (1 << n); i++) {
		t = i;
		s = 0;
		c[0] = 0;
		f = 0;
		for (int j = 0; j < n; j++) {
			b[j] = t % 2;
			t /= 2;
			if (b[j])s++;
		}
		if (s < k)continue;
		t = 0;
		f = 0;
		for (int j = 0; j < n; j++) {
			if (b[j]) {
				if (f >= a[j]) {
					f++;
					t += f - a[j];
				}
			}
			if (f < a[j])f = a[j];
		}
		if (t < m)m = t;
	}
	printf("%lld\n", m);
}

Measured memory_bytes: 1732
import java.util.*;


public class Main {
  public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    int n = scanner.nextInt();
    scanner.nextLine();
    String[] str = new String[n];
    int[] ans = new int[4];
    for(int i=0; i<n; i++){
      str[i] = scanner.nextLine();
    }
    
    for(int i=0; i<n; i++){
      String s = str[i];
      switch(s){
        case "AC":
        ans[0] ++;
        break;

        case "WA":
        ans[1] ++;
        break;

        case "TLE":
        ans[2] ++;
        break;

        case "RE":
        ans[3] ++;
        break;
      }
    }
    

    System.out.println("AC x "+ans[0]);
    System.out.println("WA x "+ans[1]);
    System.out.println("TLE x "+ans[2]);
    System.out.println("RE x "+ans[3]);
    
    scanner.close();
    return;
  }
  
}


Measured memory_bytes: 65352
import numpy as np
from collections import Counter
import collections
import numpy as np 
from scipy import sqrt, power, exp, log10
from scipy.fftpack import fft, ifft, fftfreq
import tarfile
import re
import os
import glob
from datetime import datetime
import time
import numpy.linalg as LA

round = lambda x:(x*2+1)//2
a,b = list(map(int,input().split()))
S = input()
sub= "AC"
l = np.zeros(len(S)+1)
for i in range(len(S)):
  l[i+1] = l[i] + (1 if S[i:i+2]=="AC" else 0)

for i in range(b):
    r,t = list(map(int,input().split()))
    n = l[t-1]-l[r-1]
    print(int(n))

Measured memory_bytes: 16448
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> lpair;
const ll MOD = 1e9 + 7;
const ll INF = 1e18;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
#define rREP(i,m,n) for(ll i = (m); i >= (n); i--)
#define print(x) cout << (x) << endl;
#define printa(x,n) for(ll i = 0; i < n; i++){ cout << (x[i]) << " ";} cout<<endl;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int c[3][3];
    rep(i,9) cin >> c[i/3][i%3];

    bool flag = true;
    int tatesabun[2][3];
    rep(i,2) rep(j,3)
    {
        tatesabun[i][j] = c[i][j] - c[i+1][j];
    }
    int yokosabun[3][2];
    rep(i,3) rep(j,2)
    {
        yokosabun[i][j] = c[i][j] - c[i][j+1];
    }

    if (tatesabun[0][0]!=tatesabun[0][1] || tatesabun[0][1] != tatesabun[0][2]) flag = false;
    if (tatesabun[1][0]!=tatesabun[1][1] || tatesabun[1][1] != tatesabun[1][2]) flag = false;
    if (yokosabun[0][0]!=yokosabun[1][0] || yokosabun[1][0] != yokosabun[2][0]) flag = false;
    if (yokosabun[0][1]!=yokosabun[1][1] || yokosabun[1][1] != yokosabun[2][1]) flag = false;

    // if (tatesabun[0][0]!=tatesabun[0][1] || tatesabun[0][1] != tatesabun[0][2]) cout << 1;
    // if (tatesabun[1][0]!=tatesabun[1][1] || tatesabun[1][1] != tatesabun[1][2]) cout << 2;
    // if (yokosabun[0][0]!=yokosabun[1][0] || yokosabun[1][0] != tatesabun[2][0]) cout << 3;
    // if (yokosabun[0][1]!=yokosabun[1][1] || yokosabun[1][1] != tatesabun[2][1]) cout << 4;

    // rep(i,2)
    // {
    //     rep(j,3)
        
    //     {
    //         cout << tatesabun[i][j] << " ";
    //     }
    //     cout << endl;
    // }

    // rep(i,2)
    // {
    //     rep(j,3)
    //     {
    //         cout << yokosabun[j][i] << " ";
    //     }
    //     cout << endl;
    // }

    if (flag)
    {
        cout << "Yes"<< endl;
    }
    else
    {
        cout << "No" << endl;
    }
}


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

typedef pair<int, int> pint;

int main()
{
	int N, M;
	int sum = 0;
	int A[MAX_N], B[MAX_N];
	pint C[MAX_N];
	priority_queue<int> pq;

	cin >> N >> M;
	for (int i = 0; i < N; i++)
	{
		int a, b;
		cin >> a >> b;
		C[i].first = a;
		C[i].second = b;
	}

	sort(C, C + N);

	int j = 0;
	for (int i = 1; i <= M; i++)
	{
		while (C[j].first <= i && j < N)
		{
			pq.push(C[j].second);
			j++;
		}
		if (pq.empty())continue;
		sum += pq.top();
		pq.pop();
	}

	cout << sum << endl;
	return 0;
}


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

using namespace std;

#define ll long long
#define F first
#define S second
#define ii pair < int , int >

const int N=1e5+2;
char a[N];
int main()
{
    string s;
    cin>>s;
    int z=0,o=0;
    int sum=0;
    string lst="";
    int j=0;
    int n=s.size();
    for(int i=0;i<n;i++){
            if(lst=="")
            {
                lst+=s[i];
                j=0;
                continue;
            }
       if(s[i]!=lst[j]){
            lst.pop_back();
            j--;
            sum++;
       }
       else{
        lst+=s[i];
        j++;
       }
    }
    printf("%d",sum*2);

}


Measured memory_bytes: 3812
#coding:utf-8

S = input()
Mflag = False
Yflag = False
li = [(i+j) for (i,j) in zip(S[::2],S[1::2])]


if 1 <= int(li[0]) <= 12:
    Mflag = True
else:
    pass

if 1 <= int(li[1]) <= 12:
    Yflag = True
else:
    pass

if Mflag and Yflag:
    print("AMBIGUOUS")
elif Mflag == True and Yflag == False:
    print("MMYY")
elif Mflag == False and Yflag == True:
    print("YYMM")
else:
    print("NA")

Measured memory_bytes: 3064
L = input()
digits = len(L)
MOD = 10**9 + 7
ans = pow(2, L.count('1'), MOD)
counter = 0
for i, d in enumerate(L, 1):
    if d == '1':
        ans = (ans + (pow(3, digits - i, MOD) * pow(2, counter, MOD)) % MOD) % MOD
        counter += 1
print(ans)

Measured memory_bytes: 3188
#include<iostream>
#include<vector>
#include<string>
#include<math.h>
#include<stdio.h>
#include<queue>
using namespace std;

int main()
{
	string a;
	cin >> a;
	int size_a;
	size_a = a.length();
	string b = "";

	for (int i = 0; i < size_a; i++)
	{
		if (a[i] == '0')
		{
			b.push_back('0');
		}
		else if (a[i] == '1')
		{
			b.push_back('1');
		}
		else if (a[i]!='0' && a[i]!='1' &&b.length()>0)
		{
			b.pop_back();
		}
	}

	cout << b << endl;

}



Measured memory_bytes: 3092
#include<bits/stdc++.h>
using namespace std;
int main(){
    int a , b ;
    cin >> a >> b ;
    if ((a + b) % 2 == 1){
        cout << (a + b) / 2.0 + 0.5 << endl;
    }
    else {
        cout << (a + b) / 2.0 << endl;
    }
}

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

int main() {
  int N;
  cin >> N;
  set<int> S;
  for (int i = 0; i < N; i++) {
    int n;
    cin >> n;
    S.insert(n);
  }

  int q;
  cin >> q;
  int count = 0;
  for (int i = 0; i < q; i++) {
    int n;
    cin >> n;
    if (S.count(n) > 0) count++;
  }
  cout << count << endl;
}


Measured memory_bytes: 7696
r,g,b,n = map(int,input().split())
count = 0
lis = [r,g,b]
lis.sort()
r = lis[0]
g = lis[1]
b = lis[2]
for i in range((n//b)+1):
    cn = n - b*i
    for j in range((cn//g)+1):
        cn2 = cn - g*j
        if cn2%r == 0:
            count += 1
print(count)

Measured memory_bytes: 3064
n = int(input())
p = list(map(int, input().split()))
ans = 0
for i in range(1, len(p) - 1):
    if max(p[i - 1], p[i], p[i + 1]) != p[i] and min(p[i - 1], p[i], p[i + 1]) != p[i]:
        ans += 1

print(ans)

Measured memory_bytes: 3060
list = [int(input()) for i in range(3)]
A,B,C =list[0],list[1],list[2]
X = int(input())

count =0
for i in range (A+1):
    for j in range(B+1):
        for k in range(C+1):
            if 500*i +100*j + 50*k ==X:
                count +=1

print(count)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define fi first
#define se second
#define mpp make_pair
#define li 100005
#define lo long long
#define pb push_back
#define inf 1000000000
#define md 1000000007
using namespace std;
int n,A[li],mp[li],mp2[li],mn=inf;
vector< pair<int,int> > v,v2;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&A[i]);
    for(int i=1;i<=n;i+=2) {
        mp[A[i]]++;
    }
    for(int i=1;i<=n;i+=2) {
        v.push_back(mpp(mp[A[i]],A[i]));
    }
    for(int i=2;i<=n;i+=2) {
        mp2[A[i]]++;
    }
    for(int i=2;i<=n;i+=2) {
        v2.push_back(mpp(mp2[A[i]],A[i]));
    }
    sort(v.begin(),v.end());
    sort(v2.begin(),v2.end());
    reverse(v.begin(),v.end());
    reverse(v2.begin(),v2.end());
    for(int i=0;i<(int)v.size();i++){
        int cev=n/2-v[i].fi;
        int cev2=-1;
        for(int j=0;j<(int)v2.size();j++){
            if(v2[j].se!=v[i].se){
                cev2=n/2-v2[j].fi;
                break;
            }
        }
        if(cev2==-1) cev+=n/2;
        else cev+=cev2;
        //cout<<"CEV:"<<cev<<endl;
        mn=min(mn,cev);
    }
    printf("%d\n",mn);
    return 0;
}


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

using namespace std;
#define sqr(x) ((x)*(x))
#define cube(x) ((x)*(x)*(x))
#define GCD(a, b) __gcd(a, b)
#define LCM(a, b) ((a)*(b)/GCD(a,b))
#define PI (3.141592653589793238462643383279502884197169399375105820974944)
#define MP make_pair
#define n1 first
#define n2 second
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define PDB pair<db,db>
#define SI set<int>
#define SL set<ll>
#define MS multiset
#define MSI multiset<int>
#define MSLL multiset<ll>
#define PB push_back
#define PF push_front
#define VI vector<int>
#define VPI vector<pair<int,int>>
#define VLL vector<ll>
#define VS vector<string>
#define SZ(x) ((int)x.size())

typedef long long ll;

typedef unsigned long long ull;
typedef long double ld;
typedef double db;
const int INF = 1000000007;
const ll LINF = 1000000000000000555;
const int N = 550555;
const int L = 21;
const int M = 2155;

void solve() {
    ll n,m;
    cin >> n >>m;

    ll sum = 0;
    while (m--){
        ll x;
        cin >> x;
        sum += x;
    }

    if (n >= sum) cout << n-sum; else
        cout << -1;

}

int main() {
    ios_base::sync_with_stdio(false);
#ifdef dxz05
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#else

#endif

    int T = 1;
    //cin >> T;

    while (T--) {
        solve();
    }

    return 0;
}

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

int main(){
    int a, b, c, x;
    cin >> a >> b >> c >> x;
    int res = 0;
    for(int i=0;i<=a;i++){
        for(int j=0;j<=b;j++){
            for(int k=0;k<=c;k++){
                int total = 500*i + 100*j + 50*k;
                if(total==x) res++;
            }
        }
    }
    cout << res << endl;
}


Measured memory_bytes: 256
#include<iostream>
#include <cstring>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
#include<assert.h>
#include<numeric>
using namespace std;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
using ll = long long;
typedef pair<int,int> pint;
typedef pair<ll,int> pli;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=1e9+7 ;

int main(){
  int N, K; cin >> N >> K; double ki[N];
  rep(i, N){
    double a; cin >> a; double b = a*0.5+0.5;
    ki[i] = b;
  }
  double tmp=0.0, ans=0.0;
  rep(i, K){
    tmp+=ki[i];
  }
  rep(i, N-K){
    ans = max(tmp, ans);
    tmp-=ki[i]; tmp+=ki[i+K];
  }
  ans = max(tmp, ans);
  printf("%.12lf\n", ans);
}

Measured memory_bytes: 1792
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <map>
#include <vector>
using namespace std;

int main(int argc, char const *argv[]) {
  long long int N, M;
  cin >> N >> M;

  if (N != 1 && M != 1) {
    long long int ans = (N - 2) * (M - 2);
    cout << ans << endl;
    return 0;
  } else if (N * M == 1) {
    cout << 1 << endl;
  } else {
    long long int ans = N * M - 2;
    cout << ans << endl;
    return 0;
  }
  return 0;
}

Measured memory_bytes: 256
#pragma GCC optimize("O3")
#include<bits/stdc++.h> 
using namespace std;
using ll=long long;
using P=pair<ll,ll>;
template<class T> using V=vector<T>; 
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
const ll inf=(1e18);
const ll mod=998244353;
ll gcd(ll a,ll b) {return b ? gcd(b,a%b):a;}
ll lcm(ll c,ll d){return c/gcd(c,d)*d;}
struct __INIT{__INIT(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);}} __init;
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
struct edge{
    ll to,cost;
};
V<edge> graph[200005];
V<ll> dist;
void dfs1(int now,int par){
    for(edge &e:graph[now]){
        if(e.to==par)continue;
        dfs1(e.to,now);
        chmax(dist[now],dist[e.to]+e.cost);
    }
}
ll dfs2(int now,int d_par,int par){
    V<P> dc;
    dc.emplace_back(0,-1);
    for(edge &e:graph[now]){
        if(e.to==par)dc.emplace_back(d_par+e.cost,e.to);
        else dc.emplace_back(e.cost+dist[e.to],e.to);
    }
    sort(all(dc),greater<P>());
    ll res=dc[0].fi+dc[1].fi;
    for(edge &e:graph[now]){
        if(e.to==par)continue;
        chmax(res,dfs2(e.to,dc[dc[0].se==e.to].fi,now));
    }
    return res;
}
int main(){
    int n;
    cin>>n;
    dist.assign(n,0);
    for(int i=0;i<n-1;i++){
        int a,b;
        cin>>a>>b;
        a--;b--;
        graph[a].emplace_back(edge{b,1});
        graph[b].emplace_back(edge{a,1});
    }
    if(n==1){
        cout<<"First"<<"\n";
        return 0;
    }
    dfs1(n/2,-1);
    ll ma=dfs2(n/2,0,-1);
    ma--;
    if(ma%3==0)cout<<"Second"<<"\n";
    else cout<<"First"<<"\n";
}

Measured memory_bytes: 47488
#include <stdio.h>

int main()
{
    int a, b, c, tmp;
    scanf("%d %d %d", &a, &b, &c);
    if(a > b) { tmp = a; a = b; b = tmp; }
    if(a < c && c < b) { printf("Yes\n"); }
    else { printf("No\n"); }
    return 0;
}

Measured memory_bytes: 128
IDENTIFICATION DIVISION.
        PROGRAM-ID. AtCoder.
      
        ENVIRONMENT DIVISION.
      
        DATA DIVISION.
        WORKING-STORAGE SECTION.
        01 INP PIC X(100).
        01 A PIC S9(15).
        01 B PIC S9(15).
        01 C PIC S9(15).
      	01 D PIC S9(15).
      	01 E PIC S9(15).
      	01 F PIC -ZZZZZZZZZZZZ9.
	    01 temp1 PIC 9(15).
        01 temp2 PIC 9(15).
        01 N PIC 9(15).
      
        PROCEDURE DIVISION.
      	MAIN.
			ACCEPT INP.
        	PERFORM VARYING temp1 FROM 1 BY 1
            UNTIL INP(temp1:1) = SPACE
        	END-PERFORM.
        	SUBTRACT 1 FROM temp1.
        	MOVE INP(1:temp1) TO A.
        	ADD 2 TO temp1.
        	PERFORM VARYING temp2 FROM temp1 BY 1
            UNTIL INP(temp2:1) = SPACE
        	END-PERFORM.
        	COMPUTE N = temp2 - temp1.
        	MOVE INP(temp1:N) TO B.
      		ACCEPT INP.
      		IF INP(B:1) = 'A' THEN
      			MOVE 'a' TO INP(B:1) 
      		END-IF.
      		IF INP(B:1) = 'B' THEN
      			MOVE 'b' TO INP(B:1) 
      		END-IF.
      		IF INP(B:1) = 'C' THEN
      			MOVE 'c' TO INP(B:1) 
      		END-IF.
      		DISPLAY INP.
		STOP RUN.

Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
#define INFTY 10000000000
typedef long long int ll;
const int MOD=1000000007;
using Graph = vector<vector<int>>;
using ipair = pair<ll,ll>;
bool operator< (const ipair a, const ipair b){return a.first < b.first;};
#define rep(i,n) for (ll i = 0; i < (n); ++i)
ll gcd(ll a, ll b) { return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) { return a/gcd(a,b)*b;}

int main(){
    int n;cin>>n;
    vector<int> cnt(4,0);
    rep(i,n){
        string s;
        cin>>s;
        if(s=="AC")cnt[0]++;
        if(s=="WA")cnt[1]++;
        if(s=="TLE")cnt[2]++;
        if(s=="RE")cnt[3]++;   
    }
    printf("AC x %d\n",cnt[0]);
    printf("WA x %d\n",cnt[1]);
    printf("TLE x %d\n",cnt[2]);
    printf("RE x %d\n",cnt[3]);
    return 0;
}

Measured memory_bytes: 3724
//By TheOneYouWant
#pragma GCC optimize ("-O2")
#include <bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;
#define fastio ios_base::sync_with_stdio(0);cin.tie(0)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define memreset(a) memset(a,0,sizeof(a))
#define testcase(t) int t;cin>>t;while(t--)
#define forstl(i,v) for(auto &i: v)
#define forn(i,e) for(int i=0;i<e;++i)
#define forsn(i,s,e) for(int i=s;i<e;++i)
#define rforn(i,s) for(int i=s;i>=0;--i)
#define rforsn(i,s,e) for(int i=s;i>=e;--i)
#define bitcount(a) __builtin_popcount(a) // set bits (add ll)
#define ln '\n'
#define getcurrtime() cerr<<"Time = "<<((double)clock()/CLOCKS_PER_SEC)<<endl
#define dbgarr(v,s,e) cerr<<#v<<" = "; forsn(i,s,e) cerr<<v[i]<<", "; cerr<<endl
#define inputfile freopen("input.txt", "r", stdin)
#define outputfile freopen("output.txt", "w", stdout)
#define dbg(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); \
stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
void err(istream_iterator<string> it) { cerr<<endl; }
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
	cerr << *it << " = " << a << "\t"; err(++it, args...);
}
template<typename T1,typename T2>
ostream& operator <<(ostream& c,pair<T1,T2> &v){
	c<<"("<<v.fi<<","<<v.se<<")"; return c;
}
template <template <class...> class TT, class ...T>
ostream& operator<<(ostream& out,TT<T...>& c){
    out<<"{ ";
    forstl(x,c) out<<x<<" ";
    out<<"}"; return out;
}
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll,ll> p64;
typedef pair<int,int> p32;
typedef pair<int,p32> p96;
typedef vector<ll> v64;
typedef vector<int> v32; 
typedef vector<v32> vv32;
typedef vector<v64> vv64;
typedef vector<p32> vp32;
typedef vector<p64> vp64;
typedef vector<vp32> vvp32;
typedef map<int,int> m32;
const int LIM=2e5+5,MOD=1e9+7;
const ld EPS = 1e-9;

int read(){
    int xx=0,ff=1;char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){xx=(xx<<3)+(xx<<1)+ch-'0';ch=getchar();}
    return xx*ff;
}

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
using mint = modint;

int main(){
	fastio;
	mint::set_mod(MOD);

	string s; cin>>s;
	v32 sa = suffix_array(s);
	ll ans = s.length()*(s.length()+1)/2;
	forstl(r,lcp_array(s,sa)) ans -= r;
	cout<<ans<<ln;


	return 0;
}

Measured memory_bytes: 15668
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,l,r) for(long long i=(l);i<(r);++i)
#define REP(i,n) FOR(i,0,n)
#define REPS(i,n) FOR(i,0,n+1)
#define int long long
#define mp make_pair
#define pb push_back
#define eb emplace_back
const int MOD=1e9+7;
const int INF=1e18;

signed main(){
    int N,M;cin>>N>>M;
    int ans=1900*M+100*(N-M);
    ans*=pow(2,M);
    cout<<ans<<endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
vector<int> X,Y;
int px[50],py[50];

int N,K;
int main(){
  cin>>N>>K;
  for(int i=0;i<N;i++){
    cin>>px[i]>>py[i];
    X.push_back( px[i] );
    Y.push_back( py[i] );
  }
  sort(X.begin(),X.end());
  sort(Y.begin(),Y.end());
  X.erase( unique( X.begin() , X.end() ) , X.end() );
  Y.erase( unique( Y.begin() , Y.end() ) , Y.end() );

  unsigned long long ans=-1;
  
  unsigned long long xx,yy;
  
  for(int i=0;i<X.size();i++){
    for(int j=0;j<Y.size();j++){
      for(int k=i+1;k<X.size();k++){
        for(int l=j+1;l<Y.size();l++){

          int ax=X[i], bx=X[k];
          int ay=Y[j], by=Y[l];

          int count=0;
          for(int p=0;p<N;p++)
            if( ax<=px[p]&&px[p]<=bx )
              if( ay<=py[p]&&py[p]<=by )
                count++;
          
          if(count>=K){
            xx=bx-ax;
            yy=by-ay;
            //            cout<<xx<<' '<<yy<<' '<<xx*yy<<endl;
            ans=min(ans, xx*yy);
          }
        }
      }
    }
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
	string temp;
	int now = 0;
	cin >> temp;
	for(int i=0; i<4; i++)
	{
		if(temp[i] == '+') now ++;
		else               now --;
	}
	printf("%d\n",now);
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int n,m,s;
struct point{
	int v;
	ll w;
	bool operator<(const point&p)const{
		return w>p.w;
	}
};
ll d[100005];
bool vis[1000005];
ll inf=1e12;
vector<point>e[100005];
void solve(){
	fill(d,d+n+1,inf);
	d[s]=0;vis[s]=1;
	priority_queue<point> q;
	for(int i=0;i<e[s].size();i++)q.push(e[s][i]);
	int k=1;
	while(k!=n&&!q.empty()){
		point p=q.top();q.pop();
		if(!vis[p.v]){
			d[p.v]=p.w;
			vis[p.v]=1;
			for(int i=0;i<e[p.v].size();i++)q.push({e[p.v][i].v,e[p.v][i].w+p.w});
			k++;
		}		
	}
	for(int i=0;i<n;i++){
		if(d[i]>=inf){
			cout<<"INF"<<endl;
		}else cout<<d[i]<<endl;
	}
}
int main(){
	cin>>n>>m>>s;
	int u,v,w;
	while(m--){
		cin>>u>>v>>w;
		e[u].push_back({v,w});
	}
	solve();
	return 0;
}


Measured memory_bytes: 21764
using System;
using System.Linq;
using System.Collections.Generic;
using static System.Console;
using static System.Math;
 
public class Hello{
    public static void Main(){
//        long readhp = long.Parse(ReadLine());
        string[] reader = ReadLine().Split(' ');
//        int monster = int.Parse(reader[0]);
//        int wazasu = int.Parse(reader[1]);
//        string[] readerhp = ReadLine().Split(' ');
//        long total = 0;
//        int leng = readerhp.Length;
        int a = int.Parse(reader[0]);
        int b= int.Parse(reader[1]);
        if(a==b){WriteLine("Yes");}
        else{WriteLine("No");}
        
    }
}

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

#define rep(i,n) for(int i=0;i<n;i++)
#define repa(i,a,n) for(int i=a;i<=n;i++)
#define repb(i,a,n) for(int i=a;i>=n;i--)
#define trav(a,x) for(auto a=x.begin();a!=x.end();a++)
#define all(x) x.begin(),x.end()
#define pb push_back
typedef long double ld;
typedef vector <int> vi;
typedef long long ll;

void solve()
{
  ll x,p,n;
  cin>>x;

  p=100;
  n=0;

  while(p<x){
    p+=p/100;
    ++n;
  }

  cout<<n<<"\n";
}

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

  int t;
  t=1;

  rep(i,t) solve();

return 0;
}


Measured memory_bytes: 3588
#include <iostream>
#include <cstdio>
#include <sstream>

#include <string>
#include <vector>
#include <map>
#include <set>
#include <list>
#include <deque>
#include <queue>
#include <stack>

#include <algorithm>
#include <utility>
#include <numeric>
#include <functional>

#include <chrono>
#include <random>

using namespace std;
using i64 = int_fast64_t;
using ui64 = uint_fast64_t;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<i64>;
using vvl = vector<vl>;
using vd = vector<double>;
using vvd = vector<vd>;
using vb = vector<bool>;
using vvb = vector<vb>;
using pii = pair<int, int>;
using pll = pair<i64, i64>;

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

int main(){
    int N;
    cin >> N;
    int ta = 0, hb=0, both=0;
    int ret = 0;
    for(int i=0;i<N;i++){
        string s;
        cin >> s;
        for(int i=0;i<s.length()-1;i++){
            if(s[i] == 'A' && s[i+1] == 'B')ret++;
        }
        if(s[0] == 'B' && s[s.length()-1] == 'A')both++;
        else if(s[0] == 'B')hb++;
        else if(s[s.length()-1] == 'A')ta++;
    }
    cerr << ta << " " << hb << " " << both << endl;
    if(!ta && !hb && !both)cout << ret << endl;
    else if(!ta && !hb) cout << both + ret -1 << endl;
    else if(!ta || !hb) cout << both + ret << endl;
    else cout << both + ret + min(ta, hb) << endl; 
    return 0;
}


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

typedef long long s64;

struct object
{
	int a, b, c, d;
	object() {}
	object(const int &_a, const int &_b, const int &_c, const int &_d)
		: a(_a), b(_b), c(_c), d(_d) {}

	inline s64 value() const
	{
		return ((s64)a << 30) | (b << 20) | (c << 10) | d;
	}

	inline object rotate() const
	{
		return {b, c, d, a};
	}
};
map<s64, int> all;

inline void add(object cur, int delta)
{
	for (int k = 0; k < 4; ++k)
		all[(cur = cur.rotate()).value()] += delta;
}

inline int query(const object &a)
{
	return all[a.value()];
}

inline bool existed(const object &a)
{
	return all.find(a.value()) != all.end();
}

const int MaxN = 400;

int n;
object f[MaxN + 1];

int main()
{
	cin >> n;
	for (int i = 1; i <= n; ++i)
	{
		cin >> f[i].a >> f[i].b;
		cin >> f[i].c >> f[i].d;
		add(f[i], 1);
	}

	s64 res = 0;
	for (int i = 1; i < n; ++i)
	{
		add(f[i], -1);

		for (int j = i + 1; j <= n; ++j)
		{
			add(f[j], -1);

			object cur = f[j];
			for (int k = 0; k < 4; ++k)
			{
				object f1(cur.b, cur.a, f[i].b, f[i].a);
				object f2(cur.a, cur.d, f[i].c, f[i].b);
				object f3(cur.d, cur.c, f[i].d, f[i].c);
				object f4(cur.c, cur.b, f[i].a, f[i].d);

				if (!existed(f1) || !existed(f2) || !existed(f3) || !existed(f4))
				{
					cur = cur.rotate();
					continue;
				}

				s64 ways = 1;
				ways *= query(f1), add(f1, -1);
				ways *= query(f2), add(f2, -1);
				ways *= query(f3), add(f3, -1);
				ways *= query(f4);

				add(f1, 1), add(f2, 1), add(f3, 1);

				res += ways;

				cur = cur.rotate();
			}

			add(f[j], 1);
		}
	}

	cout << res << endl;

	return 0;
}

Measured memory_bytes: 384
while 1:
    n = int(input())
    if n == 0:
        break
    count = 0
    for i in range(1,n):
        cnt = 0
        for j in range(i,n):
            cnt += j
            if cnt >= n:
                break
        if cnt == n:
            count += 1
    print(count)




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

#define ll          long long
#define mp	    make_pair
#define pb          push_back
#define pii         pair<int,int>
#define vi          vector<int>
#define vii         vector<pii>
#define mi          map<int,int>
#define mii         map<pii,int>
#define all(a)      (a).begin(),(a).end()
#define x           first
#define y           second
#define sz(x)       (int)x.size()
#define endl        '\n'
#define hell        1000000007
#define lbnd        lower_bound
#define ubnd        upper_bound
#define bs          binary_search
#define gcd(a,b)    __gcd((a),(b))
#define lcm(a,b)    ((a)*(b)) / gcd((a),(b))
#define rep(i,a,b)  for(int i=a;i<b;i++)
using namespace std;
int A[26];
void solve(){
	string s;
	cin>>s;
	rep(i,0,sz(s))
		A[s[i]-'a']++;
	rep(i,0,26)
		if(A[i]%2){
			cout<<"No"<<endl;
			return;
		}
	cout<<"Yes"<<endl;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    t =1;
//    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
#include <stdio.h>
int main()
{
	int s, h, m;
	cin >> s;
	h = s / 3600; m = (s - h * 3600) / 60; s = s - ((h * 3600) + (m * 60));
	printf("%d:%d:%d\n", h, m, s);
	cin >> s;
	return 0;
}

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

def main():
    n = int(input())
    s = input()
    s = list(s)
    s.append(s[0])
    for d0 in ["S", "W"]:
        for d1 in ["S", "W"]:
            pat = wrap(n, s, d0, d1)
            if pat[0] == pat[n] and pat[1] == pat[n + 1]:
                res = "".join(pat[:n])
                print(res)
                return
    print("-1")

def wrap(n, s, d0, d1):
    ds = [d0, d1]
    for i in range(2, n + 2):
        d = get_dnext(ds[i - 2], ds[i - 1], s[i - 1])
        ds.append(d)
    assert len(ds) == n + 2
    return ds

def get_dnext(dpre, di, si):
    if di == "S" and si == "o":
        dnext = dpre
    elif di == "S" and si == "x":
        dnext = inv(dpre)
    elif di == "W" and si == "o":
        dnext = inv(dpre)
    elif di == "W" and si == "x":
        dnext = dpre
    else:
        raise Exception
    return dnext

def inv(d):
    return "W" if d == "S" else "S"

main()


Measured memory_bytes: 5640
#include "bits/stdc++.h"
using namespace std;
#ifdef _DEBUG
#include "dump.hpp"
#else
#define dump(...)
#endif

#define int long long
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)
const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)(1e9) + 7;
template<class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (b < a) { a = b; return true; } return false; }

int longestIncreasingSubsequence(const vector<int> &v) {
	int n = v.size();
	vector<int> dp(n, INF);
	for (int i = 0; i < n; i++)
		*lower_bound(dp.begin(), dp.end(), v[i]) = v[i];
	return find(dp.begin(), dp.end(), INF) - dp.begin();
}

template<class T, class ...Tail>
void tiedSort(vector<T> &a, vector<Tail>&... tail) {
	int n = a.size();
	using S = tuple<T, Tail...>;
	vector<S> s(n);
	for (int i = 0; i < n; i++)
		s[i] = make_tuple(a[i], tail[i]...);
	sort(s.begin(), s.end());
	for (int i = 0; i < n; i++)
		tie(a[i], tail[i]...) = s[i];
}

#define double long double

signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(15);
	const double PI = 3.14159265358979323846L;
	int sx, sy, gx, gy; cin >> sx >> sy >> gx >> gy;
	if (sx > gx) {
		swap(sx, gx);
		swap(sy, gy);
	}
	bool minus = false;
	if (sy > gy) {
		sy = -sy;
		gy = -gy;
		minus = true;
	}
	int N; cin >> N;
	auto inrange = [&](int x, int y) { return x >= sx && x <= gx && y >= sy && y <= gy; };
	vector<int> x, y;
	vector<int> X(N), Y(N); rep(i, 0, N) {
		cin >> X[i] >> Y[i];
		if (minus)Y[i] = -Y[i];
		if (inrange(X[i], Y[i])) {
			x.emplace_back(X[i]);
			y.emplace_back(Y[i]);
		}
	}
	tiedSort(y, x);
	dump(x, y);
	int lis = longestIncreasingSubsequence(x);
	dump(lis);
	double r = 10;
	double d = r * 2 - PI * 2 * r / 4;
	dump(d);
	double ans = (abs(gx - sx) + abs(gy - sy)) * 100;

	if (lis == min(gx - sx, gy - sy) + 1) {
		ans -= max(0LL, lis - 1)*d;
		ans += -r * 2 + PI * 2 * r / 2;
		dump(-r * 2, PI * 2 * r / 2);
	}
	else {
		ans -= lis*d;
	}

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

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

int main(){
	vector<int> l;

	int n, k;

	cin >> n >> k;

	int t;

	for (int i = 0; i < n; i++){
		cin >> t;
		l.push_back(t);
	}

	sort(l.begin(), l.end(), greater<int>());

	int sum = 0;
	for (int i = 0; i < k; i++){
		sum += l[i];
	}
	cout << sum << endl;
}

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

/*第二引数で第一引数を割ったときの切り上げの計算*/
long long int maxtime(long long int x, long long int y) {
	return(x + y - 1) / y;

}
/*最大公約数*/
long long int lcm(long long int number1, long long int number2) {
	long long int m = number1;
	long long int n = number2;

	if (number2 > number1) {
		m = number2;
		n = number1;
	}
	long long int s = -1;
	while (s != 0) {
		s = m % n;
		m = n;
		n = s;
	}
	return m;
}
/*最大公倍数*/
long long int gcd(long long int number1, long long int number2) {
	long long int m = number1;
	long long int n = number2;
	return m / lcm(m, n) * n;
}
int main() {
	int N;
	int X;
	vector<long long int> s;
	cin >> N >> X;
	for (int i = 0; i < N; i++) {
		int x;
		cin >> x;
		long long int sum = abs(x - X);
		s.push_back(sum);
	}
	long long int sum = s[0];
	for (int i = 0; i < N; i++) {
		sum = lcm(sum, s[i]);
	}
	cout << sum;
}

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

a, b = map(int, input().split())

if 0 < a <= b:
    ans = 'Positive'
elif a <= b < 0:
    if (b - a + 1) % 2 == 0:
        ans = 'Positive'
    else:
        ans = 'Negative'
else:
    ans = 'Zero'

print(ans)


Measured memory_bytes: 2940
card = [ list(map(int, input().split())) for _ in range(3)]
N = int(input())
b = [int(input()) for _ in range(N)]

checker =[[ False for _ in range(3)] for _ in range(3)]

flag = False

for i in range(3):
    for j in range(3):
        for k in range(N):
            if card[i][j] ==  b[k]:
                checker[i][j] = True

for i in range(3):
    if all(checker[i]):
        flag = True
        print('Yes')
        exit()

for i in range(3):
    for j in range(3):
        if checker[j][i] == True:
            temp = True
        else:
            temp = False
            break
    if temp == True:
        print('Yes')
        exit()


if checker[0][0] == checker[1][1] == checker[2][2] == True:
    print('Yes')
    exit()

if checker[0][2] == checker[1][1] == checker[2][0] == True:
    print('Yes')
    exit()


print('No')


Measured memory_bytes: 3064
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<string>
#define size 100005
using namespace std;

struct Queue {
    int top, tail, Q[size];
    public:
    void initialize(){
        tail = top = 0;
    }
    
    bool empty(){
        return top == tail;
    }
    
    void enqueue(int x){
        Q[tail] = x;
        tail++;
        tail%=size;
    }
    
    int dequeue(){
        if(empty()){
            return 0;
        }
        int res = Q[top];
        top++;
        top%=size;
        
        return res;
    }
    
};

int main(){
    Queue queue1, queue2;
    
    int n, num, q, time=0;
    
    string Q[size];
    
    cin >> n >> q;
    queue1.initialize();
    queue2.initialize();
    
    for(int i=0; i<n; i++){
        cin >> Q[i] >> num;
        
        queue1.enqueue(i);
        queue2.enqueue(num);
    }
    
    int a, b;
    
    while(!queue1.empty()){
        
        a = queue1.dequeue();
        b = queue2.dequeue();
        
        if(b <= q){
            time += b;
            
            cout << Q[a] << " " << time << endl;
        }
        else {
            
            time += q;
            b -= q;
            queue1.enqueue(a);
            queue2.enqueue(b);
            
            
        }
    }
    
    return 0;
    
}
    
    
    
    
    
    
    



Measured memory_bytes: 6956
#include<bits/stdc++.h>
using namespace std;
#define fastIO ios::sync_with_stdio(0), cin.tie(0)
#define all(x) (x).begin() (x).end()
#define rall(x) (x).rbegin() (x).rend()
typedef long long ll;

int main(){
	fastIO;
	int x; cin>>x;
	string s; cin>>s;
	int changes=0;
	for(int i=0, j=x-1; j>i; i++){
		if(s[i]=='W'){
			while(s[j]=='W'){
				j--;
			}
			if(j>i){
				s[i] = 'R';
				s[j] = 'W';
				changes++;
			}
			else break;
		}
	}
	cout<<changes<<endl;
}


Measured memory_bytes: 3728
#include <bits/stdc++.h>
#include <unordered_set>
using namespace std;
#define ll long long
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define repeat(i,s,n) for(int (i)=s; (i)<(n); (i)++)
#define revrep(i,n) for(int (i)=(n)-1;i>=0; i--)

int hs(string s) {
  map<char,int> tbl;
  tbl['A']=1;
  tbl['C']=2;
  tbl['G']=4;
  tbl['T']=8;
  return tbl[s[0]]*16+tbl[s[1]]+tbl[s[2]]*16*16;
}

const int state_num = (1+2+4+8)*16*16+(1+2+4+8)*16+(1+2+4+8);
bool g[state_num+1][state_num+1];

int dp[101][state_num+1];

bool check(string s) {
  if(s.find("AGC")!=string::npos)
    return false;
  rep(i,3) {
    swap(s[i],s[i+1]);
    if(s.find("AGC")!=string::npos) {
      return false;
    }
    swap(s[i],s[i+1]);
  }
  return true;
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout<<setprecision(std::numeric_limits<float>::max_digits10);
  cout<<fixed;
  string acgt="ACGT";
  rep(i,4) {
    rep(j,4) {
      rep(k,4) {
        rep(l,4) {
          stringstream ss;
          ss<<acgt[i]<<acgt[j]<<acgt[k]<<acgt[l];
          string s=ss.str();
          stringstream from,to;
          from<<acgt[i]<<acgt[j]<<acgt[k];
          to<<acgt[j]<<acgt[k]<<acgt[l];
          //cout << "check("<<s<<")="<<check(s)<<endl;
          if(!check(s)) {
            g[hs(from.str())][hs(to.str())]=false;
          } else {
            g[hs(from.str())][hs(to.str())]=true;
          }
        }

        //cout << "from="<<from.str()<<",to="<<to.str()<<",can="<<g[hs(from.str())][hs(to.str())]<<endl;
      }
    }
  }
  int n;
  cin>>n;
  if(n==3) {
    cout << 61 << endl;
    return 0;
  }
  memset(dp,0,sizeof(dp));
  repeat(s,1,state_num+1) {
    dp[3][s]=1;
  }
  dp[3][hs("ACG")]=0;
  dp[3][hs("AGC")]=0;
  dp[3][hs("GAC")]=0;
  const int p=1e9+7;
  repeat(i,3,n) {
    repeat(s0,1,state_num+1) {
      repeat(s1,1,state_num+1) {
        if(g[s0][s1]) {
          dp[i+1][s1]+=dp[i][s0];
          dp[i+1][s1]%=p;
        }
      }
    }
  }
  int ans=0;
  repeat(s,1,state_num+1) {
    ans+=dp[n][s];
    ans%=p;
  }
  cout << ans << endl;
  return 0;
}


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

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

   int cnt = 0;
   int n = s.size();
   char c = s[0];
   for (int i = 1; i< n; i++) {
      if (c != s[i]) cnt++;
      c = s[i];
   }

   cout << cnt << endl;

   return 0;
}

Measured memory_bytes: 512
import sys
input = sys.stdin.readline

n,m=map(int,input().split())
d={i+1:[] for i in range(n)}
for i in range(m):
    x,y=map(int,input().split())
    d[x].append(y)
    d[y].append(x)

visit=set()
ans= 0 
for i in range(1,n+1):
    if i not in visit:
        ans+=1
        stack = [i]
        while stack:
            c=stack.pop()
            visit.add(c)
            for i in d[c]:
                if i not in visit:
                    stack.append(i)
print(ans-1)





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

#define REP(i, n) for(int i = 0; i < (int)(n); ++i)
#define FOR(i, m, n) for(int i = (m); i < (int)(n); ++i)
#define ALL(x) (x).begin(), (x).end()
#define INF 2000000000

#ifdef LOCAL
  #define eprintf(...) fprintf(stdout, __VA_ARGS__)
#else
  #define eprintf(...) 0
#endif

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef unsigned int uint;

int main() {
  int n;
  cin >> n;
  int current = 1;
  int prev = current;
  while(1){
    current *= 2;
    if(current > n){
      cout << prev << endl;
      break;
    }
    else if(current == n) {
      cout << current << endl;
      break;
    }
    prev = current;
  }


  return 0;
}


Measured memory_bytes: 256
//#include <tourist>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <string>
#include <iomanip>
#include <limits>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <list>
#include <queue>
#include <tuple>
#include <deque>
#include <algorithm>
#include <numeric>
#include <iomanip>
#include <utility>
#include <complex>
#include <functional>
using namespace std;
const int MOD = 1000000007;
typedef long long ll;
typedef pair<ll, ll> p;
const int INF = (1 << 28);
const int dx[4] = {0, 1, 0, -1}, dy[4] = {-1, 0, 1, 0};
const int Dx[8] = {0, 1, 1, 1, 0, -1, -1, -1}, Dy[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
#define yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define no cout << "No" << endl
#define NO cout << "NO" << endl
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define INF 2e9
#define ALL(v) v.begin(), v.end()
//setprecision(15)有効数字15桁
//-std=c++14
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b)
{
    return a * b / gcd(a, b);
}
struct edge {
    int to, cost;
};
int n, b, c;
vector<int> a;
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
  	int x, y;
    cin >> x>>y;
    cout <<x+y/2 << "\n";
}



Measured memory_bytes: 256
import java.util.Scanner;

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

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

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

        sc.close();
    }

    static int solve(int N, int i) {
        return N + 1 - i;
    }
}

Measured memory_bytes: 35596
#include <stdio.h>
#define INF (1<<21)
int N = 100;
int min(int a, int b){
    return a < b ? a : b;
}
int main(){
    int n, i, j, k, l;
    int p[N+1], m[N+1][N+1];
    scanf("%d", &n);
    for( i = 1; i <= n; i++ ){
        scanf("%d", &p[i-1]);
        scanf("%d", &p[i]);
    }
    for( i = 1; i <= n; i++ ){
        m[i][i] = 0;
    }
    for( l = 2; l <= n; l++ ){
        for( i = 0; i <= n - l + 1; i++ ){
            j = i + l - 1;
            m[i][j] = INF;
            for( k = i; k <= j - 1; k++ ){
                m[i][j] = min( m[i][j], m[i][k] + m[k+1][j] + p[i-1] * p[k] * p[j] ); 
            }
        }
    }
    printf("%d\n", m[1][n]);

    return 0;
}


Measured memory_bytes: 2112
import itertools

n = int(input())
A = [0]+list(map(int,input().split()))

cumsum = list(itertools.accumulate(A))

d = {}

ans = 0
for i in cumsum:
    if i not in d:
        d[i] = 1
    else:
        ans += d[i]
        d[i] += 1

print(ans)

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

using namespace std;


int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    if(fopen(".inp", "r")) freopen(".inp", "r", stdin);
    for(int i=1 ; i<=5 ; ++i) {
        int a; cin >> a;
        if(!a) return cout << i, 0;
    }

    return 0;
}


Measured memory_bytes: 3580
import java.util.Scanner;
//import java.util.Arrays;
public class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int tHp = sc.nextInt();
		int tAttack = sc.nextInt();
		int aHp = sc.nextInt();
		int aAttack = sc.nextInt();
		String result = "";
		while(true){
			aHp -= tAttack;
			if(aHp <= 0){
				result = "Yes";
				break;
			}
			tHp -= aAttack;
			if(tHp <= 0){
				result = "No";
				break;
			}
		}
		System.out.println(result);
	}
}


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

using namespace std;
using namespace __gnu_pbds;
using ll = long long;
using ld = long double;
using ii = pair<ll, ll>;
using vi = vector<ll>;
using vvi = vector<vi>;
using vii = vector<ii>;
using vvii = vector<vii>;

template<class T>
using min_heap = priority_queue<T, vector<T>, greater<T>>;
template<class TIn, class TOut = null_type>
using order_tree = tree<TIn, TOut, less<TIn>, rb_tree_tag,
	tree_order_statistics_node_update>;

constexpr int INF = 2000000010;
constexpr ll LLINF = 9000000000000000010LL;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	int N;
	string S;
	cin >> N >> S;

	unordered_map<string, int> mp;
	string vl(N+1, ' ');
	for (int m = 0; m < (1<<N); ++m) {
		int l = 0, r = N;
		for (int i = 0; i < N; ++i)
			vl[((m>>i)&1) ? (l++) : (r--)] = S[i];
		vl[l] = '-';
		mp[vl]++;
	}

	ll ans = 0LL;
	reverse(S.begin(), S.end());
	for (int m = 0; m < (1<<N); ++m) {
		int l = 0, r = N;
		for (int i = 0; i < N; ++i)
			vl[((m>>i)&1) ? (l++) : (r--)] = S[i];
		vl[l] = '-';
		ans += mp[vl];
	}

	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 69492
s = input()
length = len(s)

def solve(word, length):

    first = (length-1) // 2
    last = (length+3) // 2
    
    if isPalindrome(word) and isPalindrome(s[:first]) and isPalindrome(s[last-1:]):
        print("Yes")
    else:
        print("No")

def isPalindrome(word):
    palindrome = True
    size = len(word)
    start = 0
    end = size - 1

    while start <= end:
        if word[start] != word[end]:
            palindrome = False
            return palindrome
        
        start += 1
        end -= 1
    
    return palindrome

solve(s, length)

Measured memory_bytes: 3064
#include <cstdio>
using namespace std;

typedef long long ll;

int m;
ll ans, sum;

int main() {
	scanf("%d", &m);
	for (int i = 1; i <= m; ++i) {
		ll d, c;
		scanf("%lld%lld", &d, &c);
		ans += c; sum += d * c;
	}
	printf("%lld\n", ans - 1 + (sum - 1) / 9LL);
	return 0;
}

Measured memory_bytes: 128
#include <iostream>
using namespace std;
int main(){
    char a[4];
    int ans=0;
    for(int i =0;i<4;i++){
        cin >> a[i];
    }
    for(int i=0;i<4;i++){
        if(a[i]=='+'){
            ans = ans+1;
        }else{
            ans = ans-1;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <numeric>
#include <string>
#define REP(i,n) for(int i = 0; i < (n); ++i)
using namespace std;

int main(){
    int W,N;
	cin >> W >> N;

	vector<int> ret(W);
    iota(begin(ret),end(ret),1);

    REP(i, N){
    	int a,b;
    	string str;
    	getline(cin,str,',');
    	a = stoi(str);

    	getline(cin,str,'\n');
    	b = stoi(str);

    	int buf = ret[a-1];
    	ret[a-1] = ret[b-1];
    	ret[b-1] = buf;
    }
    REP(i, W) cout << ret[i] << endl;
    return 0;
}

Measured memory_bytes: 1212