akhauriyash/Code-Regression huggingface dataset:
import scala.collection.mutable.ArrayBuffer

object Main {

  def main(args: Array[String]): Unit = {

    class UnionFind(par: Array[Int]) {

      def root(x: Int): Int =
        if (par(x) == x) x
        else {
          par(x) = root(par(x))
          par(x)
        }

      def unite(x: Int, y: Int): Unit = {
        val rx = root(x)
        val ry = root(y)
        if (rx != ry)
          par(rx) = ry
      }

      def same(x: Int, y: Int): Boolean =
        root(x) == root(y)

    }

    object UnionFind {

      def apply(n: Int): UnionFind =
        new UnionFind(Array.range(0, n))

    }

    val sc = new java.util.Scanner(System.in)

    val N = sc.nextInt()
    val A = Array.fill(N, N)(sc.nextInt())

    val _E = new ArrayBuffer[((Int, Int),Int)]() // (辺(u,v), 重みw)
    (0 until N) foreach { i =>
      (0 until N) foreach { j =>
        if (A(i)(j) >= 0) {
          _E.append(((i, j), A(i)(j)))
        }
      }
    }
    val E: List[((Int, Int), Int)] = _E.sortBy(_._2).toList // 辺(軽い順)

    // 最初, 全ての頂点は別の木として初期化する
    val unionset = UnionFind(N)
    var count = 0
    // 軽い辺から見ていき
    E foreach { e =>
      val ((u, v), w) = e
      // u, v が別の木ならば, これは軽い辺なので安全に追加できる.
      if (!unionset.same(u, v)) {
        unionset.unite(u, v)
        count += w
      }
    }

    // 入力が連結グラフであることから,最終的に出来上がった木は1本となり, これが最小全域木である
    // 加えた辺の重さの合計が最小全域木の重さの合計
    println(count)
  }
  
}


Measured memory_bytes: 62692
import java.util.*;

public class Main {
	
	public static void dfs(int[][] map, int w, int h, int x, int y) {
		map[y][x] = 0;
		for (int dy = -1; dy <= 1; dy++) {
			for (int dx = -1; dx <= 1; dx++) {
				int nx = x + dx;
				int ny = y + dy;
				if (0 <= nx && nx < w && 0 <= ny && ny < h && map[ny][nx] == 1) {
					dfs(map, w, h, nx, ny);
				}
			}
		}
		return;
	}
	
	public static int solve(int[][] map, int w, int h) {
		int count = 0;
		for (int y = 0; y < h; y++) {
			for (int x = 0; x < w; x++) {
				if (map[y][x] == 1) {
					dfs(map, w, h, x, y);
					count++;
				}
			}
		}
		return count;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String output = "";
		while (sc.hasNext()) {
			int w = sc.nextInt();
			int h = sc.nextInt();
			int[][] map = new int[h][w];
			if (w == 0 && h == 0) {
				break;
			} else {
				for (int i = 0; i < h; i++) {
					for (int j = 0; j < w; j++) {
						map[i][j] = sc.nextInt();
					}
				}
				output += solve(map, w, h) + "\n";
			}
		}
		sc.close();
		
		System.out.print(output);

	}

}

Measured memory_bytes: 43336
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include<stdio.h>
#include<string.h>
int main() {
	char str[1001],*pt=str;
	scanf("%[^\n]*s", str);
	while (*pt) {
		if (*pt == 'a') {
			if (*(pt + 1) == 'p'&&*(pt + 2) == 'p'&&*(pt + 3) == 'l'&&*(pt + 4) == 'e')
				pt[0]='p',pt[1] ='e', pt[2] = 'a', pt[3] = 'c', pt[4] = 'h',	pt += 5;
		}
		if (*pt == 'p') {
			if (*(pt + 1) == 'e'&&*(pt + 2) == 'a'&&*(pt + 3) == 'c'&&*(pt + 4) == 'h')
				pt[0]='a',pt[1] = pt[2] = 'p', pt[3] = 'l', pt[4] = 'e', pt += 5;
		}
		pt++;
	}
	printf("%s\n", str);
	return 0;
}

Measured memory_bytes: 520
#include<iostream>
#include<stdio.h>
#include<cctype>
#include<string>
using namespace std;


int main() {
	int c = 0,j = 0;
	bool clear = false;
	string S, P;
	cin >> S >> P;

	S += S;
	
int   ca = S.find(P);
	


	if(ca==-1){
		cout << "No" << endl;
	}
	else{ cout << "Yes" << endl; }

	return 0;
}


Measured memory_bytes: 3204
#include<stdio.h>
int main(void)
{
	char o;
	int a,b,n;
	
	scanf("%d %c %d",&a,&o,&b);
	if(o=='+') {
		n=a+b;
	}
	if(o=='-'){
		n=a-b;
	}
	printf("%d\n",n);
	return 0;
}

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

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

Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;int h,w,k,l,m,a,b,s,t,u,v,i,j,x[999][999];main(){while(1){memset(x,0,3950000);v=0;cin>>k;if(!k){break;}cin>>w>>h;for(i=0;i<k;i++){cin>>a>>b;x[a][b]=1;}cin>>s>>t;for(i=1;i<=w;i++){for(j=1;j<=h;j++){u=0;for(l=0;l<s;l++){for(m=0;m<t;m++){if(x[i+l][j+m]){u++;}}}v=max(v,u);}}cout<<v<<endl;}}

Measured memory_bytes: 5028
def floor_sum(n, m, a, b):
    res = 0
    while True:
        if a >= m:
            res += (n - 1) * n * (a // m) // 2
            a %= m
        if b >= m:
            res += n * (b // m)
            b %= m
        y_max = (a * n + b) // m
        if y_max == 0: break
        x_max = y_max * m - b
        res += (n - (x_max + a - 1) // a) * y_max
        n, m, a, b = y_max, a, m, -x_max % a
    return res

import sys
input = sys.stdin.buffer.readline

T = int(input())
res = [None] * T

for i in range(T):
    n, m, a, b = map(int, input().split())
    res[i] = str(floor_sum(n, m, a, b))

print('\n'.join(res))

Measured memory_bytes: 78100
#include <cstdio>
#include <iostream>
using namespace std;
int N, M, C, result, B[105];

int main()
{
    scanf("%d %d %d", &N, &M, &C);
    for(int i = 0; i < M; i++)
    {
        scanf("%d", &B[i]);
    }
    for(int i = 0; i < N; i++)
    {
        int Sum = C;
        for(int j = 0; j < M; j++)
        {
            int num;
            scanf("%d", &num);
            Sum += num * B[j];
        }
        if(Sum > 0)
        {
            result++;
        }
    }
    printf("%d", result);
}

Measured memory_bytes: 256
#include <iostream>
#include<vector>
#include<climits>
#include<algorithm>
#include<bitset>
#include<cmath>
#include<functional>
#include <numeric>
#define b 42
using namespace std;
using ll = unsigned long long;
int main(){
  ll N,K;
  vector<ll> bits(b);
  cin>>N>>K;
  for(int i=0;i<N;++i){
    ll A;
    cin>>A;
    bitset<b> bs(A);
    for(int j=0;j<b;++j){
      if(bs[j])bits[j]++;
    }
  }
  ll sum=0;
  ll a=pow(2,b-1);
  ll kk=0;
  for(int i=b-1;i>=0;--i){
    if(bits[i]>=(N+1)/2){//1が多い(0を選ぶ)
      sum+=bits[i]*a;
    }else{//0が多い(1を選ぶ)
      if(kk+a<=K){
        sum+=(N-bits[i])*a;
        kk+=a;
      }else{//0選ぶ
      	sum+=bits[i]*a;
      }
    }
    a/=2;
  }
  cout<<sum<<endl;
  return 0;
}


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

int main() {
    int N,X,Y;
    cin >> N >> X >> Y;
    vector<int> num(N,0);//at(0)が余計

    int A = X - 1;
    int B = Y - X + 1;
    int C = N - Y;

    int i = 0;
    int j = 0;

    //A-A
    if(A != 0){
        for(i = 0; i < A; i++){
        num.at(i + 1) += A - i;
        }
    }

    //C-C
    if(C != 0){
        for(i = 0; i < C; i++){
        num.at(i + 1) += C - i;
        }
    }

    //A-B
    if(A!=0){
        if(B%2 == 0){//Bが偶数
            for(i = 0; i < A; i++){//A側
                for(j = 0; j < B/2; j++){
                    num.at(i + 1 + j + 1) += 2;
                }
                num.at(i + 1 + B/2) -= 1;
            }
        }else{//Bが奇数
            for(i = 0; i < A; i++){//A側
                for(j = 0; j < B/2; j++){
                   num.at(i + 1 + j + 1) += 2;
                }
            }
        }
    }

    //B-C
    if(C!=0){
        if(B%2 == 0){//Bが偶数
            for(i = 0; i < C; i++){//C側
                for(j = 0; j < B/2; j++){
                    num.at(i + 1 + j + 1) += 2;
                }
                num.at(i + 1 + B/2) -= 1;
            }
        }else{//Bが奇数
            for(i = 0; i < C; i++){//C側
                for(j = 0; j < B/2; j++){
                   num.at(i + 1 + j + 1) += 2;
                }
            }
        }
    }

    //B-B
    for(i = 0; i < (B-1)/2; i++){
        num.at(i + 1) += B;
    }if(B%2 == 0){
        num.at(B/2) += B/2;
    }

    //A-B-C
    if(A != 0 && C!= 0){
        for(i = 0; i < A; i++){
            for(j = 0; j < C; j++){
                num.at(i + j + 3) += 1;
            }
        }
    }

    for(i = 0;i < N-1; i++){
        cout << num.at(i+1) << endl;
    }
}


Measured memory_bytes: 256
#include <stdio.h>
#include <ctype.h>
int main(void) {
  char ch;
  char temp, i;

  i = 0;
  while (1) {
    scanf("%c", &ch);

    if (islower(ch)) {
      printf("%c", toupper(ch));
    } else if (isupper(ch)) {
      printf("%c", tolower(ch));
    } else if (ch == '\n') {
      break;
    } else {
      printf("%c", ch);
    }
  }

  puts("");

  return 0;
}

Measured memory_bytes: 956
N, K = map(int, input().split(' '))
mod = 10 ** 9 + 7
fac = [0] * max(N + 1, 2 * K)
finv = [0] * max(N + 1, 2 * K)
inv = [0] * max(N + 1, 2 * K)
fac[0] = fac[1] = 1
finv[0] = finv[1] = 1
inv[1] = 1
for i in range(2, max(N + 1, 2 * K)):
    fac[i] = fac[i - 1] * i % mod
    inv[i] = mod - inv[mod % i] * (mod // i) % mod
    finv[i] = finv[i - 1] * inv[i] % mod


def comb(n, k):
    return (fac[n] * (finv[k] * finv[n - k]) % mod) % mod


for i in range(1, K+1):
    if i == 1:
        print(N - K + 1)
    elif i - 1 <= N - K:
        l = comb(K - 1, i - 1)
        r = comb(N - K + 1, i)
        print(l * r % mod)
    else:
        print(0)


Measured memory_bytes: 3828
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < n; i++)
#define per(i,n) for(int i = n-1; i >= 0; i--)
typedef long long ll;
typedef pair<int, int> P;
typedef pair<long long, long long> Pll;
typedef vector<int> vi;
typedef vector<ll> vll;
const long long mod = 1000000007LL;

int main() {
  int x;
  cin >> x;
  x -= 400;
  x /= 200;
  cout << 8-x << endl;
  return 0;
}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
#define loop(n, i) for(int i=0;i<n;i++)
#define loop1(n, i) for(int i=1;i<=n;i++)
#define rloop(n, i) for(int i=n;i;i++)
#define HERE cout << "HERE: " << __LINE__ << endl;
#define INSP(v) cout << v << " at " << __LINE__ << endl;
using namespace std;
using ll = long long;
template <class T>
using V = vector<T>;

struct ModInt {
    ll v;
    static unsigned M;
    ModInt() : v(0) {}
    ModInt(ll x) : v((x % M + M) % M) {}

    ModInt& operator+=(const ModInt& r) {
        v = (v + r.v) % M;
        return *this;
    }
    ModInt& operator-=(const ModInt& r) {
        v = (v - r.v + M) % M;
        return *this;
    }
    ModInt& operator*=(const ModInt& r) {
        v = (v * r.v) % M;
        return *this;
    }
    ModInt operator-() const { return (M - v % M); }

    friend ModInt operator+(ModInt l, const ModInt& r) { return l += r; }
    friend ModInt operator-(ModInt l, const ModInt& r) { return l -= r; }
    friend ModInt operator*(ModInt l, const ModInt& r) { return l *= r; }
    friend bool operator==(ModInt l, const ModInt& r) { return l.v == r.v; }
    friend bool operator!=(ModInt l, const ModInt& r) { return !(l == r); }

    ModInt pow(ll n) const {
        ModInt base = *this, ans = 1;
        while (n) {
            if (n & 1) ans *= base;
            base *= base;
            n /= 2;
        }
        return ans;
    }
};
unsigned ModInt::M;
ostream& operator<<(ostream& o, const ModInt& r) {
    o << r.v;
    return o;
}

template <class T>
using Mat = V<V<T>>;

template <class T>
Mat<T> product(const Mat<T>& a, const Mat<T>& b) {
    int lrows = a.size();
    int lcols = a[0].size();
    int rcols = b[0].size();

    Mat<T> ret(lrows, V<T>(rcols, 0));
    loop (lrows, i) loop (rcols, j) loop (lcols, k) {
        ret[i][j] += a[i][k] * b[k][j];
    }
    return ret;
}

template <class T>
Mat<T> pow(const Mat<T>& a, ll n) {
    int rows = a.size();
    auto base = a;
    Mat<T> ans(rows, V<T>(rows, 0));
    loop (rows, i) ans[i][i] = 1;

    while (n) {
        if (n & 1) ans = product(ans, base);
        base = product(base, base);
        n /= 2;
    }
    return ans;
}

template <class T>
ostream& operator<<(ostream& o, const Mat<T>& r) {
    int rows = r.size();
    int cols = r[0].size();
    loop (rows, i) {
        loop (cols, j) {
            o << r[i][j] << " ";
        }
        o << endl;
    }
    return o;
}

int main() {
    ll l, a, b; cin >> l >> a >> b >> ModInt::M;
    ll crr = a;

    ModInt x = 0, s = a;

    loop1 (18, d) {
        ll last = 1;
        loop (d, i) last *= 10;
        last--;
        last = min(last, a + b * (l - 1));
        if (last < crr) continue;
        ll c = (last - crr) / b + 1;
        crr += b * c;

        ModInt shift = ModInt(10).pow(d);
        Mat<ModInt> mat = {
            { shift, 0, 0 },
            { 1, 1, 0 },
            { 0, b, 1 }
        };
        mat = pow(mat, c);

        auto nx = x * mat[0][0] + s * mat[1][0] + mat[2][0];
        auto ns = x * mat[0][1] + s * mat[1][1] + mat[2][1];
        x = nx, s = ns;
    }

    cout << x << endl;

    return 0;
}



Measured memory_bytes: 256
import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

class UnionFind():
    def __init__(self,n):
        self.n = n
        self.parents = [-1]*n

    def find(self,x): #根を見つける、繋ぎ直す
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    
    def unite(self,x,y): #x,yの含むグループを併合する
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return
        
        if self.parents[x] > self.parents[y]:
            x,y = y,x

        self.parents[x] += self.parents[y]
        self.parents[y] = x
    
    def same(self,x,y):#xとyが同じグループにいるか判定
        return self.find(x) == self.find(y)

def solve(N,M):
    edges = [tuple(map(int,input().split())) for _ in range(M)]
    edges.sort(key = lambda x:x[2])
    uf = UnionFind(N)

    ans = 0
    for a,b,c in edges:
        if uf.same(a,b):
            continue
        else:
            uf.unite(a,b)
            ans += c
    print(ans)

def main():
    while True:
        N,M = map(int,input().split())
        if N == 0:
            return
        solve(N,M)
if __name__ == '__main__':
    main()


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

int main()
{
 int N; cin >> N;
 int a[N];
 for(int i=0;i<N;i++){
     int b;cin >> b;
     a[i]=b;
 }
 sort(a,a+N);
 int mid=(int)N/2;
 int ans=a[mid]-a[mid-1];
 cout << ans;
 return 0;
}

Measured memory_bytes: 640
def insertion_sort(numbers, n, g):
    """insertion sort method
    (only elements whose distance is larger than g are the target)

    Args:
        numbers: list of elements to be sorted
        n: len(numbers)
        g: distance

    Returns:
        partially sorted list, counter
    """
    counter = 0
    copied_instance = []
    for data in numbers:
        copied_instance.append(data)

    for i in range(g, n):
        target = copied_instance[i]
        j = i - g
        while j >= 0 and target < copied_instance[j]:
            copied_instance[j + g] = copied_instance[j]
            j -= g
            counter += 1
        copied_instance[j + g] = target
    return copied_instance, counter


def shell_sort(numbers, n, key=lambda x: x):
    """shell sort method

    Args:
        numbers: list of elements to be sorted
        n: len(numbers)

    Returns:
        sorted numbers, used G, swapped number
    """
    counter = 0
    copied_instance = []
    for data in numbers:
        copied_instance.append(data)

    G = [1]
    g = 4
    while g < len(numbers):
        G.append(g)
        g = g * 3 + 1
    G = G[::-1]
    for g in G:
        copied_instance, num = insertion_sort(copied_instance, n, g)
        counter += num

    return copied_instance, G, counter


length = int(raw_input())
numbers = []
counter = 0
while counter < length:
    numbers.append(int(raw_input()))
    counter += 1

numbers, G, counter = shell_sort(numbers, length)
print(len(G))
print(" ".join([str(x) for x in G]))
print(counter)
for n in numbers:
    print(str(n))

Measured memory_bytes: 93164
#include<bits/stdc++.h>
using namespace std;
int main (){
  int n;
  string  s;
  cin >> n;
  cin >> s;

  char tmp;
  int count;
  string ans;
  
  count = 0;
  char old;
  //  old = '#';
  //cout << tmp << endl;
  for ( int i = 0; i < n; i++ ){
    
    /*cout << "tmp status " << endl;
    cout << "s.at " << s.at(i) << i << endl;
    cout << "old " << old << endl;*/
    
    if( i == 0 ) {
      tmp = s.at(0);
      count++;
      ans += s.at(0);
      old = s.at(0);
      //      cout << "count " << count << endl;
    }else{
      tmp = s.at(i);
      if( tmp == s.at(i) ){
        if( old == tmp ){ // old と被ってるので次
          
        }else { // old とも被ってない
          count++;
          //  cout << "count " << count << endl;
          old = s.at(i);
          ans += s.at(i);
        }
      }else{
        count++;
        //        cout << "count " << count << endl;
        old = s.at(i);
        ans += s.at(i);
      }     
    }


    /*
    cout << "tmp " << tmp << endl;
    cout << "count " << count << endl;
    cout << " " << endl;
      
    */   
  }

  cout << count << endl;
  //cout << "final count" <<count << endl;
  //cout << ans << endl;
}


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

int const N=1e5+5, M=10+5, OO = 0x3f3f3f3f;

long long n;
long long ans;
char s[M];
map <string, long long> mp;

int main()
{
//    freopen("input.txt","rt",stdin);
//    freopen("output.txt","wt",stdout);
//    freopen("mo3gza.txt","wt",stdout);
    scanf("%I64d ",&n);
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<10; j++)
            scanf("%c",s+j);
        cin.ignore();
        sort(s,s+10);
        mp[s]++;
    }
    for(auto x : mp)
    {
        ans+=((x.second)*(x.second-1))/2;
    }
    cout<<ans<<endl;

    return 0;
}





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

int N;
int A[200000];
int main()
{
	cin >> N;
	for( int i = 0; i < N; i++ ) {
		cin >> A[i];
	}
	int64_t ans = 0;
	for( int i = 1; i < N; i++ ) {
		if( A[i-1] > A[i] ) {
			ans += (A[i-1]-A[i]);
			A[i] = A[i-1];
		}
	}
	cout << ans << endl;
}

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

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    
    // 2. 出力.
    if(N & 1) printf("%d\n", N / 2);
    else      printf("%d\n",(N - 1) / 2);
    return 0;
    
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner scan = new Scanner(System.in);
        
        int n = scan.nextInt();
        int k = scan.nextInt();
        
        int[] a = new int[n];
        int[] b = new int[200100];
        
        for(int i=0;i<a.length;i++)
        {
            a[i] = scan.nextInt();
        }
        
        HaveNumbers(a,b);
        
        Arrays.sort(b);
        
        int ans = 0;
        for(int i=0;i<(b.length-k);i++)
        {
            ans += b[i];
        }
        System.out.println(ans);
    
    }
    static void HaveNumbers(int[] a,int[] b){
        for(int i=0;i<a.length;i++)
        {
            b[a[i]-1]++;
        }
    }
}


Measured memory_bytes: 79260
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <string.h>
int main()
{
    char b[2];
    scanf("%s", b);
    char ans[2];
    if (strcmp(b, "A") == 0)
    {
        printf("%s\n", "T");
        return 0;
    }
    else if (strcmp(b, "C") == 0)
    {
        printf("%s\n", "G");
        return 0;
    }
    else if (strcmp(b, "G") == 0)
    {
        printf("%s\n", "C");
        return 0;
    }
    else if (strcmp(b, "T") == 0)
    {
        printf("%s\n", "A");
        return 0;
    }
    
    return 0;
}

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

using namespace std;

int main(){
  vector<string> result;
  int i;
  string str;
  result.clear();
  cin>> i;
  for(int k = 0; k < i; k++){
    cin >> str;
    result.push_back(str);
  }
  
  sort(result.begin(), result.end());
  result.erase(unique(result.begin(), result.end()), result.end());;
  
  cout << result.size() << "\n";
  return 0;
}

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

using namespace std;

typedef long long int ll;

int main(){
    ll n,i,k,j,Min;
    cin>>n>>k;
    vector<ll>a(n),cost(n);
    for(i=0;i<n;i++){
        cin>>a[i];
    }
    cost[0] = 0;
    cost[1] = abs(a[1] - a[0]);
    for(i=2;i<n;i++){
         Min = INT_MAX;
        for(j=1;j<=k;j++){
            if(i-j>=0)
            Min = min(abs(a[i]-a[i-j]) + cost[i-j],Min);
        }
        cost[i] = Min;
    }
    cout<<cost[n-1]<<endl;
    return 0;
}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
#include<boost/variant.hpp>
using namespace std;
typedef long long ll;
typedef vector<boost::variant<bool, ll, int, string, double, char*>> any;
template<typename T> inline void pr(const vector<T> &xs){
	for(int i=0; i<xs.size()-1; i++) cout<<xs[i]<<" ";
	(xs.empty()?cout:(cout<<xs[xs.size()-1]))<<endl;
}
template<typename T> inline void debug(const vector<T> &xs){
#ifdef DEBUG
	pr(xs);
#endif
}

int main(){
	string L;
	const ll P = 1e9+7;
	cin >> L;

	vector<ll> e3(L.size());
	e3[0] = 1;
	for(int i=1; i<L.size(); i++) e3[i] = 3*e3[i-1]%P;
	ll ans = 1;
	for(int i=L.size()-1; i>=0; i--){
		if(L[i]=='1'){
			ans = 2*ans + e3[L.size()-1-i];
			ans %= P;
		}
	}

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


Measured memory_bytes: 1280
import java.util.Scanner;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class Main {

	public static void main(String[] args) {
		try (Scanner scanner = new Scanner(System.in)) {
			String s = scanner.next();
			String t = scanner.next();
			StringBuilder sb = new StringBuilder();
			for (char c : t.toCharArray()) {
				sb.append("[").append(c).append("\\?]");
			}
			Matcher matcher = Pattern.compile(sb.toString()).matcher(s);
			int index = -1;
			while (matcher.find(index + 1)) {
				index = matcher.start();
			}
			if (index >= 0) {
				System.out
						.println((s.substring(0, index) + t + s.substring(index + t.length())).replaceAll("\\?", "a"));
			} else {
				System.out.println("UNRESTORABLE");
			}
		}
	}
}


Measured memory_bytes: 23764
#include <cstdio>
#include <algorithm>
using namespace std;
int main() {
	int n;
	while(scanf("%d",&n),n) {
		int cnt[10]={0};
		for(int i=0;i<n;i++) {
			int x;
			scanf("%d",&x);
			cnt[x]++;
		}
		for(int i=0;i<10;i++) {
			for(int j=0;j<cnt[i];j++) {
				printf("*");
			}
			if(cnt[i]==0) printf("-");
			printf("\n");
		}
	}
}

Measured memory_bytes: 1000
n = int(input())
temp = 0
stations = list()

for i in range(n-1):
    stations.append(list(map(int,input().split())))


for i in range(n-1):
    temp=0
    c,s,f = stations[i]
    if temp < s:
        temp = s
    temp = temp + c
    for j in range(i+1,n-1):
        c,s,f = stations[j]
        if temp < s:
            temp = s
        if temp % f != 0:
            amari = temp % f
            amari = f - amari
            temp += amari
        temp = temp + c
    print(temp)
        
print(0)

Measured memory_bytes: 3188
txt = gets.chomp

if txt == 'SUN'
  puts 7
elsif txt == 'MON'
  puts 6
elsif txt == 'TUE'
  puts 5
elsif txt == 'WED'
  puts 4
elsif txt == 'THU'
  puts 3
elsif txt == 'FRI'
  puts 2
elsif txt == 'SAT'
  puts 1
end

Measured memory_bytes: 1788
#include <iostream>
using namespace std;
typedef long long ll;
ll h, w, a, b, fac[1100000], res;
const ll MOD = 1e9 + 7;

ll pow(ll x, ll y){
    if (y == 0) {
        return 1;
    } else if (y % 2) {
        return x * pow(x, y - 1) % MOD;
    } else {
        ll z = pow(x, y / 2);
        return z * z % MOD;
    }
}

ll modcom(ll x, ll y){
    return fac[x] * pow(fac[y], MOD - 2) % MOD * pow(fac[x - y], MOD - 2) % MOD;
}

int main(void){
    // Your code here!
    cin >> h >> w >> a >> b;
    fac[0] = 1;
    for (ll i = 1; i <= 1e6; i++) fac[i] = fac[i - 1] * i % MOD;
    for (ll i = 0; i < h - a; i++) {
        res += modcom(i + b - 1, b - 1) * modcom(w + h - b - i - 2, w - b - 1) % MOD;
        res %= MOD;
    }
    cout << res << endl;
}


Measured memory_bytes: 8448
#include<bits/stdc++.h>
using namespace std;
int a[127],l=1,i;
char s[27],c;
int main(){
    cin>>s;
    for(i=0;s[i]!='\0';i++){
        a[s[i]]=1;
         l++;
    }
    for(c='z';c>='a';c--) 
         if(!a[c]) 
             s[l++]=c;
    cout<<(next_permutation(s,s+l)?s:"-1")<<endl;

}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
	ll n,i,j,k,p=1,q=0,a=0,b,c,x;
	cin>>n;
	vector<pair<string,ll> > v;string ss;
	for(i=0;i<n;i++)
	{
		cin>>ss;cin>>k;v.push_back(make_pair(ss,k));
	}
	cin>>ss;
	for(i=0;i<n;i++)
	{
		if(ss==v[i].first)
		{x=i;break;
		}
	}
	for(i=x+1;i<n;i++)
	{
		q=q+v[i].second;
	}
	cout<<q;
}

Measured memory_bytes: 256
n, a, b = map(int, input().split())
s = input()
tuka = 0
kaigai = 0
for i in range(n):
    if s[i] == "a" and tuka < a+b:
        tuka += 1
        print("Yes")
    elif s[i] == "b" and tuka < a+b and kaigai < b:
        tuka += 1
        kaigai += 1
        print("Yes")
    else:
        print("No")

Measured memory_bytes: 9008
#include<iostream>
#include<algorithm>
#include<bits/stdc++.h>
#define ll long long int

using namespace std;

main()
{
	ll n;
	cin>>n;
	string s;
	cin>>s;
	ll r=0,w=0;
	
	for(int i=0;i<s.length();i++)
	{
		if(s[i]=='W')
			w++;
		else
			r++;
	}
	ll ans=0;
	for(ll i=s.length()-1;i>=0;i--)
	{
				if(w<=0)
			break;

		if(s[i]=='W')
			w--;
		else
			w--,ans++;
		
	}
	cout<<ans<<endl;

}

Measured memory_bytes: 3724
import itertools
N = int(input())
P = [int(a)-1 for a in input().split()]
Q = [int(a)-1 for a in input().split()]
i = 0
ans = 0
for a in itertools.permutations(range(N), N):
    a = [b for b in a]
    if a == P:
        ans -= i
    if a == Q:
        ans += i
    i += 1

print(abs(ans))

Measured memory_bytes: 41324
#include <iostream>
#include <algorithm>
#include <stdlib.h>

using namespace std;

int main(void){
    int N, M;
    cin >> N >> M;

    int A[N+5];
    int a, b;
    for(int i=1;i<=N;i++){
        A[i] = 0;
    }
    for(int i=0;i<M;i++){
        cin >> a >> b;
        A[a] = A[a] + 1;
        A[b] = A[b] + 1;
    }
    for(int i=1;i<=N;i++){
        if(A[i] % 2 == 1){
            cout << "NO" << endl;
            return 0;
        }
    }
    cout << "YES" << endl;
    return 0;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
#define all(v) ((v).begin()),((v).end())
#define ll long long
#define fastIO cout << fixed << setprecision(12), ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
double const EPS = 1e-12, PI = acos(-1);
const int N = 1e6 + 9, M = 5e3 + 9, OO = 1e9 + 7, MOD = 1e9 + 7;
const ll inf = 1e18;

int main() {
  fastIO;
#ifdef LOCAL
  freopen("input.in", "rt", stdin);
#endif
  int a, b, c;
  cin >> a >> b >> c;
  cout << min({a + b, b + c, a + c});
  return 0;
}


Measured memory_bytes: 256
#include<string>
#include<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<chrono>
#include<functional>
#include<random>
#include<unordered_set>
using namespace std;
typedef long long int llint;
#define mp make_pair
#define mt make_tuple
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define fir first
#define sec second
#define res resize
#define ins insert
#define era erase
const llint mod=1000000007;
const llint big=1e17-10;
const long double pai=3.141592653589793238462643383279;
template <class T,class U>void mineq(T& a,U b){if(a>b){a=b;}}
template <class T,class U>void maxeq(T& a,U b){if(a<b){a=b;}}
int main(void){
	llint i,j,n,p,q;cin>>n>>p;
	llint ad=0,ev=0;
	if(p==0){ev++;}else{ad++;}
	for(i=0;i<n;i++){cin>>q;if(q%2==0){ad*=2;ev*=2;}else{llint at=ad+ev;ad=at;ev=at;}}
	cout<<ev<<endl;
	return 0;
}

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

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

    int a,b,x;
    cin >> a >> b >> x;
    //int ans = 0;

    if(a + b >= x && a <= x){
        cout << "YES" << endl;
    }else{
        cout << "NO" << endl;
    }
    

    return 0;
}

Measured memory_bytes: 256
N,M = map(int,input().split())
Switch = [0] * N
for i in range(M):
  k,*S = map(int,input().split())
  for s in S:
    s -= 1
    Switch[s] |= (1 <<i)
#print(Switch)
P = list(map(int,input().split()))
p = 0
for i in range(M):
  p |= (P[i] <<i)
#print(p)

ans = 0
for i in range(2 ** N):
  light = 0
  for j in range(N):
    if (i >>j) & 1 == 1:
      light ^= Switch[j]
  if light == p:
    ans += 1
print(ans)


Measured memory_bytes: 39664
#include <iostream>
#include <algorithm>

using namespace std;
using ll = long long;

void solve(ll A, ll B, ll C) {
  cout << min(C,B/A) << endl;
}

int main() {
  ll A;
  cin >> A;
  ll B;
  cin >> B;
  ll C;
  cin >> C;
  solve(A, B, C);
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n) ; ++i)
using namespace std;
using ll = long long ;
using P = pair<int, int> ;
#define PI 3.14159265358979323846264338327950
int main () {
    int a,b ;
    cin >> a >> b;
    string aa, bb;
    aa = to_string(a);
    bb = to_string(b);
    string aaa, bbb ;
    rep(i,b){
        aaa = aaa + aa;
    }
    rep(i,a){
        bbb = bbb + bb;
    }
   if (aaa > bbb){
       cout << bbb << endl;
   }
   else {
       cout << aaa << endl;
   }


}



Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <string>
#include <map>
#include <queue>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define REP(i, n) for (int i = 0; i < (n); i++)
#define RREP(i, n) for (int i = (n) - 1; i >= 0; i--)
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define RFOR(i, a, b) for (int i = (a); i > (b); i--)
#define ALL(a) (a).begin(), (a).end()
#define MOD 1000000007

int main() {
    int N, dp[101][4][4][4] = {};
    dp[0][3][3][3] = 1;
    cin >> N;
    REP(i, N) REP(j, 4) REP(k, 4) REP(l, 4) {
        if (dp[i][j][k][l] == 0) continue;

        REP(a, 4) {
            if (a == 2 && j == 1 & k == 0) continue;
            if (a == 2 && j == 0 & k == 1) continue;
            if (a == 1 && j == 2 & k == 0) continue;
            if (a == 2 && j == 1 & l == 0) continue;
            if (a == 2 && k == 1 & l == 0) continue;

            dp[i + 1][a][j][k] += dp[i][j][k][l];
            dp[i + 1][a][j][k] %= MOD;
        }
    }
    int ans = 0;
    REP(i, 4) REP(j, 4) REP(k, 4) ans = (ans + dp[N][i][j][k]) % MOD;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define REP(i,st,ed) for(register int i=st,i##end=ed;i<=i##end;++i)
#define DREP(i,st,ed) for(register int i=st,i##end=ed;i>=i##end;--i)
typedef long long ll;
template<typename T>inline bool chkmin(T &x,T y){return (y<x)?(x=y,1):0;}
template<typename T>inline bool chkmax(T &x,T y){return (y>x)?(x=y,1):0;}
inline int read(){
	int x;
	char c;
	int f=1;
	while((c=getchar())!='-' && (c>'9' || c<'0'));
	if(c=='-') f=-1,c=getchar();
	x=c^'0';
	while((c=getchar())>='0' && c<='9') x=(x<<1)+(x<<3)+(c^'0');
	return x*f;
}
inline ll readll(){
	ll x;
	char c;
	int f=1;
	while((c=getchar())!='-' && (c>'9' || c<'0'));
	if(c=='-') f=-1,c=getchar();
	x=c^'0';
	while((c=getchar())>='0' && c<='9') x=(x<<1ll)+(x<<3ll)+(c^'0');
	return x*f;
}
const int maxn=3e5+10;
int a[maxn];
bool solve(int L,int R){
	if((R-L)&1) return 1;
	if(L==R) return 0;
	for(int i=L+1;i<R;i+=2) if(i!=a[i]) return 1;
	int x=0,y=0;
	for(int i=L;i<=R;i+=2){
		if(a[i]<i){
			if(x>=a[i]) return 1;
			x=a[i];
		}
		else if(a[i]>i){
			if(y>=a[i]) return 1;
			y=a[i];
		}
		else return 1;
	}
	return 0;
}
int main(){
	int n=read();
	REP(i,1,n) a[i]=read();
	int Max=0,lst=1;
	REP(i,1,n){
		chkmax(Max,a[i]);
		if(Max==i){
			if(solve(lst,i)){
				printf("No\n");
				return 0;
			}
			lst=i+1;
		}
	}
	printf("Yes\n");
	return 0;
}


Measured memory_bytes: 1408
#include <bits/stdc++.h>
using namespace std;
#define f(i,a,b) for(ll i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(ll i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define pc(x)  __builtin_popcount (x)
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define ld long double
#define pii pair< int,int >
#define pll pair< ll,ll >
#define sz(a) a.size()
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod 1000000007
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >
#define flush fflush(stdout) 
#define gcd __gcd
#define primeDEN 727999983
#define nx_pe next_permutation(s.begin(),s.end())
#define cl cout<<"\n"

void print(ll n)
{
	if(n>0)
	{
		n--;
		print(n/26);
        char x=(n%26)+(char)65;
        x=tolower(x);
        cout<<x;
		// printf("%c",(n%26)+65);
	}
}
    
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin) ;
    freopen("output.txt", "w", stdout) ;
    #endif
    ios_base::sync_with_stdio(false);
    cin.tie(NULL) ; cout.tie(NULL) ;
    std::ios::sync_with_stdio(false);
    ll n;
    cin>>n;
    print(n);

}




Measured memory_bytes: 3648
class UnionFind:
    def __init__(self, N):
        self.parent = list(range(N))
        self.rank = [0] * N
        self.size = [1] * N

    def find(self, x):
        r = x
        while self.parent[r] != r:
            r = self.parent[r]
        while self.parent[x] != r:
            x, self.parent[x] = self.parent[x], r
        return r

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
            self.size[y] += self.size[x]
        else:
            self.parent[y] = x
            self.size[x] += self.size[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def get_size(self, x):
        return self.size[self.find(x)]

n, q = map(int, input().split())
uf = UnionFind(n)
for _ in range(q):
    com, x, y = map(int, input().split())
    if com == 0:
        uf.unite(x, y)
    else:
        print(1 if uf.same(x, y) else 0)



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

int main() {
    int h, n, a;
    cin >> h >> n;
    int sum = 0;
    for (int i = 0; i < n; ++i) {
        cin >> a;
        sum += a;
    }
    cout << (sum >= h ? "Yes" : "No") << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);i++)
#define loop(i,x,n) for(int i=(x);i<(n);i++)
#define all(v) (v).begin(),(v).end()
#define int long long
using namespace std;
const int MOD=1e9+7;
const int INF=1e10;



signed main(){
  int n;
  cin>>n;
  vector<int> a(n);

  rep(i,n)cin>>a[i];

  sort(all(a));
  int ichi=a[n-1];
  int tmp=INF;
  int ans;
  if(ichi%2==0){
    int mid=ichi/2;
    rep(i,n-1){
      if(tmp>abs(mid-a[i])){
        tmp=abs(mid-a[i]);
        ans=a[i];
      }
    }
  }else{
    int mid=ichi/2;
    rep(i,n-1){
      if(a[i]<=mid&&tmp>(mid-a[i])){
        ans=a[i];
        tmp=mid-a[i];
      }else if(mid+1<=a[i]&&tmp>a[i]-mid-1){
        tmp=a[i]-mid-1;
        ans=a[i];
      }
    }
  }
  cout<<ichi<<' '<<ans<<endl;
  return 0;
}


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

typedef long long   ll;
typedef long double ld;
using namespace std;

int main() {
    string a,b,c;
    cin >> a >> b >> c;
    if(a[a.size()-1] == b[0] && b[b.size()-1] == c[0]) cout << "YES" << "\n";
    else cout << "NO" << "\n";

    return 0;
}

Measured memory_bytes: 3576
from itertools import combinations
n = int(input())
set_3m = set()
cnt = {}
for i in range(n):
    s = input()
    try:
        if s[0] in {'M', 'A', 'R', 'C', 'H'}:
            set_3m.add(s[0])
            cnt[s[0]] += 1
    except KeyError:
        cnt[s[0]] = 1
sum_cnt = 0
for c in combinations(set_3m, 3):
    sum_cnt += cnt[c[0]] * cnt[c[1]] * cnt[c[2]]
print(sum_cnt)    

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

int n;
int s[200020];

int main(){
  scanf("%d",&n);
  for(int i=0;i<n;i++){
    int x,y;
    scanf("%d %d",&x,&y);
    
    int z=x+y;
    while(s[z]){
      s[z]=0;
      z++;
    }
    s[z]=1;
  }
  for(int z=0;z<200020;z++)
    if(s[z])printf("%d 0\n",z);
  return 0;
}

Measured memory_bytes: 3984
a=int(input())+1
b=int(input())+1
c=int(input())+1
x=int(input())
cnt=0
for i in range(a):
  for j in range(b):
    for k in range(c):
      if 500*i+100*j+50*k==x:
        cnt+=1
print(cnt)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define BIT(n) (1LL << (n))
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPB(i, n) for (int i = 0; i < BIT(n); i++)
#define REPS(i, x) for (int i = 1; i <= (int)(x); 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 FORA(i, n) for (auto &&i : n)
#define FORS(i, m, n) for (int i = m; i <= n; i++)
#define DEBUG(x) cerr << #x << ": " << x << "\n"
#define DEBUG2(x, y) cerr << #x << ": " << x << " " << #y << ": " << y << "\n"
#define DEBUG3(x, y, z)                                                        \
  cerr << #x << ": " << x << " " << #y << ": " << y << " " << #z << ": " << z  \
       << "\n"
#define PRINTALL(V)                                                            \
  for (auto v : (V)) {                                                         \
    cerr << v << " ";                                                          \
  }                                                                            \
  cerr << "\n";
#define ALL(v) v.begin(), v.end()
#define fst first
#define snd second
#define mp make_pair
#define pb push_back
#define epb emplace_back
#define int long long
#define pint pair< int, int >
#define ld long double
using namespace std;
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;
}
template < class T > using vec = std::vector< T >;
template < class T > void print(const T &x) { cout << x << "\n"; }
const int MOD = 1000000007, INF = 1061109567, INF2 = INF * INF;
const double EPS = 1e-10, PI = acos(-1.0);
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
signed main() {
  cin.tie(0), ios::sync_with_stdio(false);
  cout << fixed << setprecision(10);
  int N;
  cin >> N;
  vec< int > a(N);
  REP(i, N) {
    int p;
    cin >> p;
    p--;
    a[p] = i;
  }
  REP(i, N - 1) cout << a[i] + 1 << " ";
  cout << a[N - 1] + 1 << "\n";
}

Measured memory_bytes: 1664
N = int(input())
list = [int(_) for _ in input().split()]

flag = 1
for i in range(N):
  ans = 0
  for j in range(N):
    if i!=j:
      ans += list[j]
    
  if ans <= list[i]:
      flag = 0
      break

if flag:
  print('Yes')
else:
  print('No')
  

Measured memory_bytes: 2940
// #define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(v) v.begin(), v.end()
#define Graph vector<vector<int>>
typedef long long ll;
typedef pair<int, int> P;
const int INF = 1000000007;

int main(){
    ll N;
    cin >> N;
    vector<ll> A(N), digit(64, 0);
    rep(i, N) cin >> A[i];

    rep(i, N){
        bitset<64> s(A[i]);
        rep(j, 64){
            if(s.test(j)) digit[j]++;
        }
    }

    ll ans = 0, a = 1;

    rep(i, 64){
        ll tmp = (N - digit[i]) * digit[i];
        tmp %= INF;
        tmp *= a;
        tmp %= INF;

        ans += tmp;
        ans %= INF;
        a *= 2;
        a %= INF;
    }

    cout << ans << endl;
    
}

Measured memory_bytes: 2560
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect, bisect_left, bisect_right

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
L = [LIST() for i in range(N)]

A_a = []
# for i in range()
A = []
B = []
for a, b in L:
    c = a % b
    A_a.append(c)
    B.append(b)
    A.append(a)

ruiseki = 0
cnt = 0
for i in range(N):
    amari = B[N-i-1] - ((A[N-i-1] + ruiseki) % B[N-i-1])
    if amari == B[N-i-1]:
        cnt += 0
        ruiseki += 0
    else:
        cnt += amari
        ruiseki += amari
    # print()
    # print("amari:", amari)
    # print(amari)
    # cnt += amari
print(cnt)



Measured memory_bytes: 34212
n,m=map(int,input().split())
x=[0]*n
for i in range(m):
  a,b=map(int,input().split())
  x[a-1]+=1
  x[b-1]+=1
ans="YES"
for i in range(n):
  if x[i]%2:ans="NO"
print(ans)

Measured memory_bytes: 3828
#include <iostream>
#include <string>
using namespace std;
int main()
{
	int a, b, c;
	cin >> a >> b >> c;
	int c1[10000] = {0};

	int length = 0;
	for (int i = 1; i <= c; i++)
	{
		if (c % i == 0)
		{
			c1[length] = i;
			length++;
		}
	}
	
	int count = 0;
	for (int i = a; i <= b; i++)
	{
		for (int j = 0; j < length; j++)
		{
			if (i == c1[j])
			{
				count++;
			}
		}
	}
	cout << count << endl;
}


Measured memory_bytes: 3120
n = int(input())
a = list(map(int, input().split()))

b=[]

for i in range(n):
    if(a[i]==i+1):
        b.append(1)
    else:
        b.append(0)
        
#print(b)
count = 0
if(n>=3):
    for i in range(n-1):
        prev = b[i]
        now = b[i+1]
        if(prev+now == 2):
            count+=1
            b[i+1]=0
        elif(prev==1 and now ==0):
            count+=1
            
    if(b[n-1]==1):
        count+=1
    print(count)
else:
    if(sum(b)>=1):
        print(1)
    else:
        print(0)


Measured memory_bytes: 56300
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef pair<ll,ll> pll;
typedef double db;
#define INF 1e8
#define EPS 1e-9
#define ALL(x) x.begin() , x.end()
#define ALLR(x) x.rbegin() , x.rend()
#define UNIQUE(c) (c).resize(unique(ALL(c)) - (c).begin())
#define PI acos(-1.0) 

int main()
{
  //ios_base::sync_with_stdio(0);
  //cin.tie(0);
  int N,Q,s,t,x;
  cin >> N >> Q;
  priority_queue<tuple<ll, ll, ll>,vector<tuple<ll, ll, ll>>,greater<tuple<ll, ll, ll>> >q;
  for(int i = 0; i < N; i++)
  {
    cin >> s >> t >> x;
    s -= x; t -= x;
    q.push(make_tuple(s, t, x));
  }
  vector<pll> c;
  vl ans(Q,-1);
  for(int i = 0; i < Q; i++)
  {
      cin>>x;
      c.push_back({x,i});
  }
  priority_queue<pll,vector<pll>,greater<pll> >pend;
  multiset<ll> dist;
  ll prev = 0, acum = 0;
  for(int i = 0; i < Q; i++)
  {
      //cout<<i<<endl;
      //cout<<get<0>(q.top())<<" "<<get<1>(q.top())<<" "<<c[i].first<<endl;
      while(!q.empty() && get<0>(q.top()) - c[i].first <= 0)
      {
          if(get<1>(q.top()) - c[i].first > 0)
          {
              pend.push({get<1>(q.top()),get<2>(q.top())});
              dist.insert(get<2>(q.top()));
          }
          q.pop();
      }
      while(!pend.empty() && pend.top().first - c[i].first <= 0)
      {
          dist.erase(dist.find(pend.top().second));
          pend.pop();   
      }
      if(!dist.empty())
      {
          ans[c[i].second] = *dist.begin();
      }
  }
  for(int i = 0; i < Q; i++)
  {
      cout<<ans[i]<<"\n";
  }

}

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

using namespace std;

#define INF 1001000100010001000
#define MOD 1000000007
#define EPS 1e-10
#define int long long
#define rep(i, N) for (int i = 0; i < N; i++)
#define Rep(i, N) for (int i = 1; i < N; i++)
#define For(i, a, b) for (int i = (a); i < (b); i++)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define pii pair<int, int>
#define vi vector<int>
#define vvi vector<vi >
#define vb vector<bool>
#define vvb vector<vb >
#define vp vector< pii >
#define all(a) (a).begin(), (a).end()
#define Int(x) int x; cin >> x;
#define int2(x, y) Int(x); Int(y);
#define int3(x, y, z) Int(x); int2(y, z);
#define in(x, a, b) ((a) <= (x) && (x) < (b))
#define fir first
#define sec second
#define ffir first.first
#define fsec first.second
#define sfir second.first
#define ssec second.second
#define Decimal fixed << setprecision(10)

//int dxy[5] = {0, 1, 0, -1, 0};
// cmd

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

    Int(n);

    int ans = 0;
    for (int x = 1; x * x <= n; x++) {
        if (n % x) continue;
        int m1 = n / x;
        if (x < m1 - 1) ans += m1-1;
    }

    std::cout << ans << std::endl;

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <cmath>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)

int main() {
  int K, X;
  int L = -1000000;
  int R = 1000000;

  cin >> K >> X;

  int l = max(L, X - K + 1);
  int r = min(R, X + K - 1);
  rep2(i, l, r + 1) {
	cout << i;
	if(i < r) cout << ' ';
  }
  cout << endl;
}


Measured memory_bytes: 888
res = []

n = int(input())
a = [int(c) for c in input()]

def solve():
    if a[0] == 0:
        return False
    for x in range(1, 2**n):
        s = list(filter(lambda i: (x >> i) & 1, range(n)))
        xl = [(x >> i) & 1 for i in range(n)]
        if a[x] == 0:
            for d in s:
                y = x ^ (1 << d)
                if a[y] == 1:
                    break
            else:
                continue
            def move_ceiling(r, dest):
                i, j = r[-1]
                if i < dest:
                    for i in range(i, dest):
                        if xl[i] == 0 and j == 1:
                            r.append((i, 0))
                            j = 0
                        elif xl[i] == 1 and j == 0:
                            r.append((i, 1))
                            j = 1
                        r.append((i + 1, j))
                else:
                    for i in range(i, dest, -1):
                        if xl[i - 1] == 0 and j == 1:
                            r.append((i, 0))
                            j = 0
                        elif xl[i - 1] == 1 and j == 0:
                            r.append((i, 1))
                            j = 1
                        r.append((i - 1, j))
                return r
            def move_floor(r, dest):
                i, j = r[-1]
                if j == 1:
                    r.append((i, 0))
                for i in range(i + 1, dest + 1) if i < dest else range(i - 1, dest - 1, -1):
                    r.append((i, 0))
                return r
            r = [(s[0] + 1, 1), (s[0], 1), (s[0], 0), (s[0] + 1, 0)]
            cur = s[0] + 1
            for d in s[1:]:
                r0 = [(d + 1, 1)] if cur == d else move_ceiling([(d + 1, 1)], cur)
                r1 = move_ceiling(r.copy(), d + 1)
                r1 = move_floor(r1, cur)
                r1.pop()
                r2 = list(reversed(r))
                r2 = move_floor(r2, d + 1)
                r = r0 + r1 + r2
                cur = d + 1
            r = move_floor(r, n)
            r.reverse()
            r = move_floor(r, n)
            r.pop()
            res.append(r)
        else:
            for d in s:
                y = x ^ (1 << d)
                if a[y] != 1:
                    return False
    return True

if __name__ == '__main__':
    if solve():
        print('Possible')
        r = [(i, j) for r in res for i, j in r]
        r.append((n, 0))
        print(len(r) - 1)
        for i, j in r:
            print(i, j)
    else:
        print('Impossible')


Measured memory_bytes: 5852