akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <utility>
#include <vector>

using namespace std;

typedef pair<long long, long long> P;

const int M = 1e9+7;

int n;
vector<int> edge[100005];
bool done[100005];

P dfs(int u)
{
  done[u] = true;
  P mul = make_pair(1, 1);
  for (int v: edge[u]) {
    if (done[v]) continue;
    P tmp = dfs(v);
    mul.first *= tmp.first + tmp.second;
    mul.second *= tmp.first;
    mul.first %= M;
    mul.second %= M;
  }
  return mul;
}

int main()
{
  cin >> n;
  for (int i = 0; i < n; i++) {
    int x, y; cin >> x >> y;
    edge[x].push_back(y);
    edge[y].push_back(x);
  }
  
  P tmp = dfs(1);
  long long ans = (tmp.first + tmp.second) % M;
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 9984
#include<bits/stdc++.h>
using namespace std;
int main(){
    long long int t[2],a[2],b[2];
    for(int i=0;i<2;i++)cin >> t[i];
    for(int i=0;i<2;i++)cin >> a[i];
    for(int i=0;i<2;i++)cin >> b[i];
    long long int move=t[0]*(a[0]-b[0])+t[1]*(a[1]-b[1]);
    long long int MAX=max(max(0LL,t[0]*(a[0]-b[0])),move);
    long long int MIN=min(min(0LL,t[0]*(a[0]-b[0])),move);
    if(move==0)cout << "infinity";
    else{
        if(MIN==0 || MAX==0)cout << 0;
        else if(move>0 && (abs(MIN)%move)!=0LL)cout << 2LL*(abs(MIN)/move+1) - 1;
        else if(move>0 && (abs(MIN)%move)==0LL)cout << 2LL*(abs(MIN)/move+1) - 2;
        else if(move<0 && (MAX%abs(move))!=0LL)cout << 2LL*(MAX/abs(move)+1) - 1;
        else if(move<0 && (MAX%abs(move))==0LL)cout << 2LL*(MAX/abs(move)+1) - 2;
    }
}

Measured memory_bytes: 3648
#include <bits/stdc++.h>
#include <stdio.h>
#include <math.h>
using namespace std;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using ll = long long int;

int main(){
    int N;
    cin >> N;
    string S;
    cin >> S;
    ll count = 0;
    for(int i=0; i<N-2; i++){
        if(S[i]=='A'&&S[i+1]=='B'&&S[i+2]=='C'){
            count++;
        }
    }
    cout << count;
}

Measured memory_bytes: 256
#include <queue>
#include <stack>
#include <map>
#include <algorithm>
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <complex>
typedef long long int LL;
typedef unsigned long long int ULL;
using namespace std;

// 插入此處

int a[200005];

int main() {
    int k, n;
    scanf("%d%d", &k, &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    int m = a[0] + (k - a[n - 1]);
    for (int i = 1; i < n; i++) {
        m = max(m, a[i] - a[i - 1]);
    }
    printf("%d\n", k - m);
}


Measured memory_bytes: 896
#include <stdio.h>
#include <iostream>
#include <ctype.h>
#include <string>

using namespace std;

int main(void){
	int i, j;
	string s, suc1("the"), suc2("this"), suc3("that");
	while(getline(cin,s)){
		while(s.find(suc1) == -1 && s.find(suc2) == -1 && s.find(suc3) == -1){	
			for(j = 0;j < s.size();j++){
				if(s[j] == 'z')
					s[j] = 'a';
				else if(isalpha(s[j]))
					s[j]++;
			}
		}
		cout << s << endl;
	}
	return 0;
}

Measured memory_bytes: 1192
import java.io.*;
import java.util.*;
public class Main{
    public static void main(String[] args) throws IOException{
        MyReader r = new MyReader();  
        long N, K; {long[] a = r.ll(); N = a[0]; K = a[1];}
        long[] A = r.ll();
        long MOD = 1000000007;
        long num = 0;
        for (int i = 0; i < N; i++) {
            long Ai = A[i];
            long n = 0;
            for (int j = 0; j < i; j++)
                if(Ai > A[j])
                    n++;      
            num = (num + K*(K-1)/2%MOD*n)%MOD;
            n = 0;
            for (int j = i+1; j < N; j++)
                if(Ai > A[j])
                    n++;   
            num = (num + K*(K+1)/2%MOD*n)%MOD;
        }
        print(num);
    }
    static void print(Object o){
        System.out.print(o.toString());
    }
    static void println(Object o){
        System.out.println(o.toString());
    }
    static int Int(String s){
        return Integer.parseInt(s);
    }
    static long Long(String s){
        return Long.parseLong(s);
    }
    static class MyReader extends BufferedReader{
        MyReader(){
            super(new InputStreamReader(System.in));
        }
        String s() throws IOException{
            return readLine();
        }
        String[] ss() throws IOException{
            return s().split(" ");
        }
        int i() throws IOException{
            return Int(s());
        }
        int[] ii() throws IOException{
            String[] ss = ss();
            int size = ss.length;
            int[] ii = new int[size];
            for(int j = 0; j < size; j++) ii[j] = Integer.parseInt(ss[j]);
            return ii;
        }
        long l() throws IOException{
            return Long(s());
        }
        long[] ll() throws IOException{
            String[] ss = ss();
            int size = ss.length;
            long[] ll = new long[size];
            for(int j = 0; j < size; j++) ll[j] = Long.parseLong(ss[j]);            
            return ll;
        }
    }
}

Measured memory_bytes: 23764
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int H, W;
  cin >> H >> W;
  vector<vector<char>> a(H, vector<char>(W));
  vector<vector<char>> b(H, vector<char>(W));
    
  for (int i = 0; i < H; i++){
    for (int j = 0; j < W; j++){
      cin >> a.at(i).at(j);
    }
  }
  
  b = a;
  int sum = 0;
  
  for (int i = 0; i < H; i++){
    int count = 0;
    for (int j = 0; j < W; j++){
      if (a.at(i).at(j) == '.'){
        count ++;
      }
    }
    if (count == W){
      b.erase(b.begin() + i - sum);
      sum ++;
    }
  }
  
  a = b;
  
  int sum2 = 0;
  for (int j = 0; j < W ; j++){
    int count2 = 0;
    for (int i = 0; i < H - sum; i++){
      if (a.at(i).at(j) == '.'){
        count2 ++;
      }
    }
    if (count2 == H - sum){
      for (int k = 0; k < b.size(); k++){
        b.at(k).erase(b.at(k).begin() + j - sum2);
      }
      sum2 ++;
    }
  }

  for (int i = 0; i < H - sum; i++){
    for (int j = 0; j < W - sum2; j++){
      cout << b.at(i).at(j);
      if (j == b.at(i).size() - 1){
        cout << endl;
      }
    }
  }

}

Measured memory_bytes: 256
s = input()
def ki(tap):
    for i in range(0,len(tap),2):
        if tap[i]=='L':
            return 'No'

def gu(tap):
    for i in range(1,len(tap),2):
        if tap[i]=='R':
            return 'No'

if ki(s)=='No' or gu(s)=='No':
    print('No')
else:
    print('Yes')


Measured memory_bytes: 38256
using System;
using System.Collections;
using System.Collections.Generic;
using System.Text;
using System.IO;
using System.Linq;
using System.Diagnostics;
using System.Globalization;
using static System.Console;
using static System.Math;

namespace soundhound_a
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] input = ReadLine().Split().Select(int.Parse).ToArray();

            if(input[0]+input[1] == 15){
                WriteLine("+");
            } else if(input[0]*input[1] == 15){
                WriteLine("*");
            }else {
                WriteLine("x");
            }

        }
    }
}

Measured memory_bytes: 13396
#include <bits/stdc++.h>
using namespace std;
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define lli long long int
#define tc int t;cin>>t;while(t--)
#define all(x) x.begin(),x.end()
#define f first
#define s second
#define pb push_back
#define vi vector<int>
#define vll vector<lli>
#define maxn 300005
#define mod 998244353
 
 
int main(){
    fastio;
    int a,b,c,d;
    cin>>a>>b>>c>>d;
    lli dp[c+1][d+1];
    dp[a][b]=1;
    for(int i=a;i<=c;i++)
    {
        for(int j=b;j<=d;j++)
        {
            if(i<=a and j<=b)
            {dp[i][j]=1;continue;}
            dp[i][j]=0;
            if(i-1>=a)
            dp[i][j]=(dp[i-1][j]*j)%mod;
            if(j-1>=b)
            dp[i][j]+=(dp[i][j-1]*i)%mod,dp[i][j]%=mod;
            if(i>a and j>b)
            {
                dp[i][j]=(dp[i][j]-(((i-1)*(j-1)%mod)*dp[i-1][j-1])%mod+mod)%mod;
            }
           // cout<<i<<" "<<j<<" "<<dp[i][j]<<"\n";
        }
    }
    cout<<dp[c][d]<<"\n";
    return 0;
}

Measured memory_bytes: 73832
import java.util.*

object MainKt {
    @JvmStatic
    fun main(args: Array<String>) {
        val scanner = Scanner(System.`in`)
        val n = scanner.nextInt()

        when(n){
            1 -> println("Hello World")
            2 -> {
                val a = scanner.nextInt()
                val b = scanner.nextInt()
                println(a+b)
            }
        }

    }
}

Measured memory_bytes: 31264
#include<cstdio>
#include<bits/stdc++.h>
typedef long long int ll;
#define REP(i, n) for(int i = 0; i < (n); i++)
#define FOR_IN(i, a, b) for(int i = (a); i < (b); i++)
#define BETWEEN(x, a, b) ((x) >= (a) && (x) <= (b))
#define BIT(b, i) (((b) >> (i)) & 1)
#define LOG_F 1
#define LOG(...) if(LOG_F) fprintf(stderr, __VA_ARGS__)

using namespace std;

ll pow(int x, int n){
  return n == 0 ? 1 : x * pow(x, n - 1);
}


/*

 */
int a,b,c;

int main(){
  cin>>a>>b>>c;
  if(b-a == c-b)
    cout<<"YES\n";
  else
    cout<<"NO\n";

  return 0;
}


Measured memory_bytes: 256
# -*- coding: utf-8 -*-
H = int(input())
W = int(input())
N = int(input())

if(H > W):
  if(N%H == 0):
    print(int(N/H))
  else:
    print(int(N/H)+1)
else:
  if(N%W == 0):
    print(int(N/W))
  else:
    print(int(N/W)+1)


Measured memory_bytes: 2940
#include <vector>

#include <iostream>

// nまでの数が素数かどうかを判定できるvectorを返す
std::vector<bool> factor(const int n) {
  int size = n + 1;
  std::vector<bool> isPrime(size, true);
  isPrime[0] = false;
  isPrime[1] = false;
  for (int i = 2; i < size; i++) {
    if (!isPrime[i])
      continue;
    for (int k = 2; i * k < size; k++) {
      isPrime[i * k] = false;
    }
  }
  return isPrime;
}

// minFactor[i]: iを割り切る最小の素数。存在しない場合は-1。
std::vector<int> fastFactor(const int n) {
  int size = n + 1;
  std::vector<int> minFactor(size, -1);
  for (int i = 2; i < size; i++) {
    if (minFactor[i] != -1)
      continue;
    minFactor[i] = i;
    for (int k = 2; i * k < size; k++) {
      if (minFactor[i * k] == -1) {
        minFactor[i * k] = i;
      }
    }
  }
  return minFactor;
}

// factor
// verify https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/1/ALDS1_1_C
void verify_factor() {
  std::vector<bool> isPrime = factor(10000);
  int n;
  std::cin >> n;
  int ans = 0;
  for (int i = 0; i < n; i++) {
    int a;
    std::cin >> a;
    bool flag = true;
    for (int j = 1; j < std::min(a, (int)isPrime.size()); j++) {
      if (!isPrime[j])
        continue;
      if (a % j == 0) {
        flag = false;
        break;
      }
    }
    if (flag)
      ans++;
  }
  std::cout << ans << std::endl;
}

// fastFactor
// verify https://atcoder.jp/contests/abc052/tasks/arc067_a
void verify_fastFactor() {
  int n;
  std::cin >> n;
  auto minFactor = fastFactor(1000);
  std::vector<long long int> num(1001, 0LL);
  for (int i = 1; i <= n; i++) {
    int tmp = i;
    while (minFactor[tmp] != -1) {
      num[minFactor[tmp]]++;
      tmp /= minFactor[tmp];
    }
  }

  long long int ans = 1LL;
  for (int i = 0; i < (int)num.size(); i++) {
    ans *= num[i] + 1LL;
    ans %= 1000000007;
  }
  std::cout << ans << std::endl;
}

int main() {
  // verify_factor();
  verify_fastFactor();
  return 0;
}


Measured memory_bytes: 256
import java.lang.Integer.min
import java.util.*
import kotlin.math.max

fun readInt(): Int = readLine()!!.toInt()
fun readInts(): List<Int> = readLine()!!.split(" ").map { it.toInt() }
fun readLongs(): List<Long> = readLine()!!.split(" ").map { it.toLong() }

fun parseInt(): Int {
    var digit = System.`in`.read()
    while(digit <= 32) {
        digit = System.`in`.read()
    }

    val negative = digit == '-'.toInt()
    if (negative) {
        digit = System.`in`.read()
    }
    var res = 0
    while (digit in '0'.toInt()..'9'.toInt()) {
        res *= 10
        res += digit - '0'.toInt()
        digit = System.`in`.read()
    }
    return if (negative) -res else res
}

fun gcd(x : Int, y : Int) : Int {
    var a = x
    var b = y
    var r = 0
    while(b > 0) {
        r = a % b
        a = b
        b = r
    }
    return a
}

val MOD : Int = 1000000007

fun pw(base : Int, exp : Int) : Int {
    var b = base.toLong()
    var e = exp
    var res = 1L
    while(e > 0) {
        if ((e and 1) != 0) {
            res = (1L * res * b) % MOD
        }
        b = (1L * b * b) % MOD
        e = e shr 1
    }

    return res.toInt()
}

fun getBit(x : Long, b : Int) : Int {
    return ((x shr b) and 1).toInt()
}

fun solve(s : Long, x : Long, mx : Long) : Long {
    if(s < x || s % 2 != x % 2) return -1
    val a = (s - x) / 2

    var ans = 0L
    for(b in 60 downTo -1) {
        if(getBit(x, b) == 0 && getBit(a, b) == 1) ans += (1L shl b)
    }

    for(b in 60 downTo -1) {
        if(getBit(x, b) == 1 && getBit(a, b) == 1) return -1
        if(getBit(x, b) == 1 && getBit(a, b) == 0) {
            if(ans + (1L shl b) <= mx) ans += (1L shl b)
        }
    }

    if(ans > mx || ans == 0L) return -1
    return mx - ans
}

fun main() {
//    val t = readLine()!!.toInt()
    val t = 1

    for(testNumber in 1..t) {
        val n = readInt()
        val a = readLongs()

        var x = 0L
        for(i in 2 until n) x = x xor a[i]

        var s = a[0] + a[1]

        println(solve(s, x, a[0]))
    }
}

Measured memory_bytes: 38012
from collections import Counter
def p_fact(n,a):
  m=n
  i=2
  a.append(1)
  while n>1:
    if i>m**.5:
      a.append(n)
      break
    if n%i==0:
      n//=i
      a.append(i)
    else:i+=1  
  return a
n,m=map(int,input().split())
a=Counter(p_fact(m,[]))
b=a.values()
c=a.keys()
ans=1
for i,j in zip(c,b):
  if j>=n:ans*=i**(j//n)
print(ans) 

Measured memory_bytes: 67108
#include<bits/stdc++.h>
#include <algorithm>
#define rep(i,n) for (int i=0;i<(n);i++)
#define PI 3.14159265358979323846264338327950L
using namespace std;
using P = pair<int,int>;
using ll = long long;
using namespace std;
int main(void){
    int n, k;
    cin >> n >> k;
    int cnt = 0;
    int h[n]; rep(i, n){
        cin >> h[i];
        if(h[i] >= k){++cnt;}
    }
    cout << cnt << endl;
}

Measured memory_bytes: 3876
def selection_sort(a)
  n = a.length
  i = 0
  sw = 0
  while i < n do
    j = i
    minj = i
    while j < n do
      if a[j] < a[minj]
        minj = j
      end
      j += 1
    end
    t = a[i]
    a[i] = a[minj]
    a[minj] = t
    if i != minj
      sw += 1
    end
    i += 1
  end
  i = 0
  while i < n do
    print " " if i > 0
    print a[i]
    i += 1
  end
  puts ""
  puts sw
end

n = gets.to_i
a = gets.split.map(&:to_i)

selection_sort(a)



Measured memory_bytes: 6872
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define rep(i,s,e) for(int (i) = (s);(i) <= (e);(i)++)
#define all(x) x.begin(),x.end()

int main() {
  int n;
  string s;
  cin >> n >> s;
  int cnt = 0;
  int left =0;
  for(int i = 0;i < n;i++) {
    if(s[i] == '(') {
      cnt++;
    }
    else {
      cnt--;
    }
    if(cnt == -1) {
      left++;
      cnt = 0;
    }
  }
  string ans = "";

  for(int i = 0;i < left;i++) ans.push_back('(');
  ans = ans + s;
  for(int i = 0;i < cnt;i++) ans.push_back(')');
  cout << ans << endl;
}


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

using namespace std;

typedef pair<int,int> pii;

int grid[505][505];

struct op{
	int a,b,c,d;
	op(int a, int b, int c, int d):a(a),b(b),c(c),d(d){}
};

vector<op> ans;

int main(){
	int h,w;
	cin >> h >> w;
	vector<pii> v;
	for(int i=1;i<=h;i++){
		for(int j=1;j<=w;j++){
			cin >> grid[i][j];
			if(grid[i][j]%2)
				v.push_back(pii(i,j));
		}
	}

	int inc=1,j=0;
	bool carry=false;
	for(int i=1;i<=h;i++){
		j+=inc;
		while(j>0 and j<=w){
			if(grid[i][j]%2){
				carry = !carry;
				if(carry and (j!=1 or inc==1) and (j!=w or inc==-1))
					ans.push_back(op(i,j,i,j+inc));
				else if(carry and i!=h)
					ans.push_back(op(i,j,i+1,j));
			}else{
				if(carry and (j!=1 or inc==1) and (j!=w or inc==-1))
					ans.push_back(op(i,j,i,j+inc));
				else if(carry and i!=h)
					ans.push_back(op(i,j,i+1,j));
			}
			j+=inc;
		}
		inc*=-1;
	}
	cout << ans.size() << endl;
	for(int i=0;i<ans.size();i++){
		cout << ans[i].a << " " << ans[i].b << " " << ans[i].c << " " << ans[i].d << endl; 
	}
}

Measured memory_bytes: 7152
#include <iostream>
#include <string>
using namespace std;
int main() {
  int a[3][3], p[3][3], n;
  cin >> a[0][0] >> a[0][1] >> a[0][2];
  cin >> a[1][0] >> a[1][1] >> a[1][2];
  cin >> a[2][0] >> a[2][1] >> a[2][2];
  cin >> n;
  int b[n];
  for(int i=0; i<3; i++) {
    for(int j=0; j<3; j++) {
      p[i][j] = 0;
    }
  }
  for(int i=0; i<n; i++) {
    cin >> b[i];
    for(int j=0; j<3; j++) {
      for(int k=0; k<3; k++) {
        if (b[i] == a[j][k]) {
          p[j][k] = 1;
        }
      }
    }
  }
  if ((p[0][0] == 1 && p[1][0] == 1 && p[2][0] == 1) || (p[0][1] == 1 && p[1][1] == 1 && p[2][1] == 1) || (p[0][2] == 1 && p[1][2] == 1 && p[2][2] == 1) || (p[0][0] == 1 && p[0][1] && p[0][2]) || (p[1][0] == 1 && p[1][1] && p[1][2]) || (p[2][0] == 1 && p[2][1] && p[2][2]) || (p[0][0] == 1 && p[1][1] && p[2][2]) || (p[0][2] == 1 && p[1][1] && p[2][0])) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
}

Measured memory_bytes: 888
#include <string>
#include <string.h>
#include <iostream>
 
using namespace std;
 
int main()
{
    int N, B[4]; string S;
 
    memset(B, 0, sizeof(B));
 
    while (cin >> N >> S)
    {
        if (S == ",A")
        {
            B[0] += 1;
        }
        else if (S == ",B")
        {
            B[1] += 1;
        }
        else if (S == ",AB")
        {
            B[2] += 1;
        }
        else if (S == ",O")
        {
            B[3] += 1;
        }
    }
 
    cout << B[0] << endl << B[1] << endl << B[2] << endl << B[3] << endl;
 
    return 0;
}


Measured memory_bytes: 3036
#include"bits/stdc++.h"
using namespace std;
using lint = long long int;
using pint = pair<int, int>;
using plint = pair<lint, lint>;
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((lint)(x).size())
#define POW2(n) (1LL << (n))
#define FOR(i, begin, end) for(lint i=(begin),i##_end_=(end);i<i##_end_;i++)
#define IFOR(i, begin, end) for(lint i=(end)-1,i##_begin_=(begin);i>=i##_begin_;i--)
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)
template<typename T1, typename T2> pair<T1, T2> operator+(const pair<T1, T2>& l, const pair<T1, T2>& r) { return make_pair(l.first + r.first, l.second + r.second); }
template<typename T1, typename T2> pair<T1, T2> operator-(const pair<T1, T2>& l, const pair<T1, T2>& r) { return make_pair(l.first - r.first, l.second - r.second); }

double A, B, H, M;
int main() {
	static const double pi = 3.141592653589793;
	cin.tie(0); ios_base::sync_with_stdio(false);
	cin >> A >> B >> H >> M;
	cout << setprecision(16) << sqrt(A * A + B * B - 2 * A * B * cos(abs((H * 60 - 11 * M) / 360 * pi)));
}


Measured memory_bytes: 4272
#include <algorithm>
#include <cmath>
#include <complex>
#include <cstdio>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <string>
#include <vector>

const long long int INF = 1e9;
typedef long long int ll;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define Rep(i, n) for(int i = 1; i <= (int)(n); i++)
#define llrep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define llRep(i, n) for(ll i = 1; i <= (ll)(n); i++)

using namespace std;

struct Point{
	int x,y;
};

bool vector_finder(std::vector<int> vec, int number) {
    auto itr = std::find(vec.begin(), vec.end(), number);
    size_t index = std::distance( vec.begin(), itr );
    if (index != vec.size()) { // 発見できたとき
        return true;
    }
    else { // 発見できなかったとき
        return false;
    }
}

int main(){
    ll R,G,B,N;
    cin >> R >> G >> B >> N;
    ll cnt=0;
    llrep(i,N/R+1){
        llrep(j,N/G+1){
            if (ll b=(N-R*i-G*j)%B==0 && ((N-R*i-G*j)/B)>=0 && ((N-R*i-G*j)/B)<=3000){
                cnt++;
                // cout << i << " " << j << " " << b<< endl;
            }
        }
    }
    cout << cnt << endl;

    return 0;
}


Measured memory_bytes: 256
import java.util.*;public class Main{public static void main(String[]a){Scanner s=new Scanner(System.in);int n=s.nextInt();int[]m=new int[n];for(int i=0;i<n;i++)m[i]=s.nextInt();for(int i=n-1;i>=0;i-=2)System.out.print(m[i]+" ");for(int i=n%2;i<n;i+=2)System.out.print(m[i]+" ");}}

Measured memory_bytes: 94076
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fr(i,a,b) for (ll i = (a), _b = (b); i <= _b; i++)
#define frr(i,a,b) for (ll i = (b), _a = (a); i >= _a; i--)
#define rep(i,n) for (ll i = 0, _n = (n); i < _n; i++)
#define repr(i,n) for (ll i = (n) - 1; i >= 0; i--)
#define debug(x) cout<<#x<<": "<<x<<endl
#define all(ar) ar.begin(), ar.end()
#define sz(x) ((long long)x.size())
#define pb push_back
#define pob pop_back()
#define pf push_front
#define pof pop_front()
#define mp make_pair
#define ff first
#define ss second
#define endl "\n"
#define trace2(x, y)            cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<< endl;
#define trace3(x, y, z)         cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl;
#define trace4(a, b, c, d)      cout <<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl;
#define trace5(a, b, c, d, e)   cout <<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<<": "<<e<<endl;
 
typedef pair<ll, ll> ii;
typedef pair<ll, ii> iii;
typedef vector<ii> vii;
typedef vector<ll> vi;
typedef vector<string> vs;
typedef vector<vi> vvi;

ll const INF=1LL<<60LL;
double const pi=3.14159265358979323846264338327950; 

 
ll gcd(ll a, ll b){
    if(b==0)
        return a;
    return gcd(b,a%b);
}

ll lcm(ll a, ll b){
	return ((a*b)/gcd(a,b));
}

ll modpower(ll base,ll power,ll mod){
	ll res=1;
	while(power){
		if(power%2){
			res=(res*base)%mod;
			power--;
		}
		base=(base*base)%mod;
		power/=2;
	}
	return res;
}
ll const MAX=1000001;

void solve(){
	ll k;
	cin>>k;
	string s;
	cin>>s;
	ll n=s.size();
	if(n<=k)cout<<s<<endl;
	else {
		s=s.substr(0,k)+"...";
		cout<<s<<endl;
	}
}
    
int main () 
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout<<setprecision(11);
    #ifndef ONLINE_JUDGE
    freopen("inputf.in", "r", stdin);
    freopen("outputf.in", "w", stdout);
    #endif
 
    ll t=1;
    //cin>>t;
    while(t--){
        solve();
 
    }
 
    return 0;   
}

Measured memory_bytes: 3656
#include <iostream>
#include <vector>
using namespace std;
inline void chmax(int &a, int b) {
    if (a < b) a = b;
}

int n, m;
vector<vector<int>> graph;

vector<int> dp;
int rec(int now) {
    if (dp[now] != -1) return dp[now];
    dp[now] = 0;
    for (auto next: graph[now]) {
        chmax(dp[now], rec(next) + 1);
    }
    return dp[now];
}

int main() {
    cin >> n >> m;
    graph.assign(n, vector<int>());
    for (int i=0; i<m; ++i) {
        int x, y; cin >> x >> y;
        x--; y--;
        graph[x].push_back(y);
    }
    dp.resize(n, -1);
    int ans = 0;
    for (int i=0; i<n; ++i) chmax(ans, rec(i));
    cout << ans << endl;
}

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

ll sum(const vector<long long> &A) {
	ll res = 0;
	for(auto a: A) {
		res += a;
	}
	return res;
}

void solve(long long N, vector<long long> A, vector<long long> B){
	ll res = min(sum(A), sum(B));

	vector<pair<ll, ll>> C;
	vector<bool> used(2 * N);
	for(int i = 0; i < N; ++i) {
		C.push_back(make_pair(A[i], i));
		C.push_back(make_pair(B[i], i + N));
	}
	sort(C.begin(), C.end());

	ll sum = 0;
	for(int i = 0; i < N; ++i) {
		sum += C[i].first;
		used[C[i].second] = true;
	}
	for(int i = 0; i < N; ++i) {
		if(used[i] && used[i + N]) {
			cout << min(res, sum) << endl;
			return;
		}
	}

	for(int i = 0; i < N; ++i) {
		if (C[N].second == i || C[N].second == i + N) {
			res = min(res, sum - min(A[i], B[i]) + C[N + 1].first);
		} else {
			res = min(res, sum - min(A[i], B[i]) + C[N].first);
		}
	}

	cout << res << endl;
}

int main(){	
	long long N;
	scanf("%lld",&N);
	vector<long long> B(N-1+1);
	vector<long long> A(N-1+1);
	for(int i = 0 ; i <= N-1 ; i++){
		scanf("%lld",&A[i]);
		scanf("%lld",&B[i]);
	}
	solve(N, A, B);
	return 0;
}



Measured memory_bytes: 9716
from collections import deque

H,W = map(int,input().split())
c_h, c_w = map(int,input().split())
d_h, d_w = map(int,input().split())

c_h -= 1
c_w -= 1
d_h -= 1
d_w -= 1

s = [list(input()) for _ in range(H)]

# print(s)

q = deque()
q.append((c_h,c_w))

INF = 1e9
# マス目に入る数字を入れる配列
# 最初はINFで初期化
dist = [[INF for _ in range(W)] for __ in range(H)]

dist[c_h][c_w] = 0
# (右、上、左、下)
dh = (0,1,0,-1)
dw = (1,0,-1,0)

while(len(q) > 0):
    # dequeの一番左を取り出す。
    now = q.popleft()
    now_h,now_w = now

    d = dist[now_h][now_w]

    # 今のマスの上下左右で動けるか確認する
    for di in range(4):
        next_h = now_h + dh[di]
        next_w = now_w + dw[di]

        if (next_h<0 or next_h>=H or next_w<0 or next_w>=W): continue
        if (s[next_h][next_w] == '#'): continue
        if dist[next_h][next_w] <= d: continue

        # 隣り合う動けるマスには同じ数字を記入
        dist[next_h][next_w] = d

        # dequeに前から入れる
        q.appendleft((next_h,next_w))

    # 魔法を使う場合
    for ew in range(-2,3):
        for eh in range(-2,3):
            next_h = eh + now_h
            next_w = ew + now_w

            if (next_h<0 or next_h>=H or next_w<0 or next_w>=W): continue
            if (s[next_h][next_w] == '#'): continue
            if dist[next_h][next_w] <= d+1: continue

            dist[next_h][next_w] = d+1
            q.append((next_h,next_w))

if (dist[d_h][d_w] == INF):
    print(-1)
else:
    print(dist[d_h][d_w])

# print(dist)


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

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int base = Integer.parseInt(br.readLine());
        System.out.println(base*base*base);
    }
}


Measured memory_bytes: 24228
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <unordered_map>
#include <math.h>
#include <cmath>
#include <limits>
#include <numeric>
#include <iomanip>
#include <stdio.h>
#define INF 1000000000
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
typedef long long int ll;
using namespace std;

int main() {

	

	int n, m; cin >> n >> m;
	int r[10], c[10]; 
	rep(i, m) { cin >> r[i] >> c[i]; }

	int i; if (n == 1) { i = 0; }
	else { i = pow(10, n - 1); }

	int ans = INF;
	for (; i < pow(10, n); i++) {
		string num = to_string(i);
		for (int j = 0; j < m; j++) {
			if (num[r[j] - 1] - '0' != c[j]) { goto next; }
		}
		ans = min(ans, i);
	next:;
	}
	if (ans == INF) { cout << "-1" << endl; }
	else { cout << ans << endl; }

	return 0;
}

Measured memory_bytes: 256
using System;
class Pg{
  static void Main(string[] args){
    string[] x = Console.ReadLine().Split(' ');
    int y = int.Parse(x[0]);
    int yz = int.Parse(x[1]);
    int z = int.Parse(x[2]);
    string kk = (y + yz + z) == (y * 3) ? "Yes" : "No";
    Console.WriteLine(kk);
  }
}

Measured memory_bytes: 11092
#include<bits/stdc++.h>
using namespace std;
char s[100005],ss[100005];
signed main(){
	scanf("%s",s);
	int len=strlen(s);
	for(int i=0;i<len;i++){
		switch(s[i]){
			case 'b':{ss[len-i-1]='d';break;}
			case 'd':{ss[len-i-1]='b';break;}
			case 'p':{ss[len-i-1]='q';break;}
			case 'q':{ss[len-i-1]='p';break;}
		}
	}
	if(strcmp(s,ss))printf("No");
	else printf("Yes");
	return 0;
}

Measured memory_bytes: 384
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<stack>
#include<queue>
#include<vector>
#include<algorithm>
#include<string>
#include<iostream>
#include<set>
#include<map>
#include<bitset>

using namespace std;
typedef long long ll;
#define i_7 1000000007
#define i_5 1000000005

ll mod(ll a){
    ll c=a%i_7;
    if(c>=0)return c;
    else return c+i_7;
}
typedef pair<int,int> i_i;
typedef pair<ll,ll> l_l;
ll inf=1000000000000;/*10^12*/
#define rep(i,l,r) for(ll i=l;i<=r;i++)
ll max(ll a,ll b){if(a<b)return b;else return a;}
ll min(ll a,ll b){if(a>b)return b;else return a;}


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

int main(){
    int n,m;cin>>n>>m;
    i_i a[m];rep(i,0,m-1)cin>>a[i].first>>a[i].second;
    sort(a,a+m);
    int ans=0;
    int pos=0;
    while(pos<=m-1){
        int last=a[pos].second;
        while(pos<=m-1){
            if(a[pos].first<last&&last<=a[pos].second)pos++;
            else if(a[pos].first>=last){
                break;
            }else{
                last=a[pos].second;
                pos++;
            }
        }
        ans++;
    }
    
    cout<<ans<<endl;
    
    return 0;
}


Measured memory_bytes: 1024
import itertools

N = int(input())
T = [[] for _ in range(N)]
for i in range(N):
    for _ in range(int(input())):
        x, y = map(int, input().split())
        T[i].append([x - 1, y])

ans = 0

for bit in list(itertools.product([0, 1], repeat=N)):
    ok = True
    for i in range(N):
        if bit[i]:
            for x, y in T[i]:
                if bit[x] != y:
                    ok = False
    if ok:
        ans = max(ans, sum(bit))

print(ans)


Measured memory_bytes: 8948
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<string>
#include<cmath>
#include<vector>
#include<stack>
#include<queue>
#include<time.h>
#include<set>
#include<map>
#define FOR(i,a,b) for(ll i=a;i<b;i++)
#define REP(i,a,b) for(int i=a;i>b;i--)
#define vint vector<int> 
#define vvint vector<vint>
#define ct(a) cout<<a<<endl
#define tget(a,b) get<a>(b)
using namespace std;
typedef long long ll;
const ll INF = 1e17;
const int MOD = 1e9 + 7;


ll N, ans;


int main(void) {
	double a, b; cin >> a >> b;
	ct(a / b);


	return 0;
}


Measured memory_bytes: 256
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>

#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <regex>
#define rep(i,n) for(int i = 0; i < n; i++)
#define reps(i,j,n) for(int i = j; i < n; i++)
#define rrep(i,j,n) for(int i = j-1; i >= n; i--)
#define prec(n) fixed << setprecision(n)
#define print_array(v) rep(__k, v.size()) { cout << v[__k]; if(__k != v.size()-1) cout << " "; else cout << endl; }
#define YesorNo(a) printf(a?"Yes\n":"No\n")
#define fi first
#define se second
using namespace std;

int inf = 2147483647;
int64_t inf64 = 9223372036854775807;
int mod = 1e+7;

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

  int n;
  cin >> n;
  vector<int> b(n-1);
  rep(i,n-1) cin >> b[i];
  int res = b[0] + b[n-2];
  rep(i,n-2) res += min(b[i], b[i+1]);
  cout << res << endl;
  return 0;
}

Measured memory_bytes: 256
//package atcoder;
 
import java.util.*;
 
public class Main{
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		long X = sc.nextLong();
		long rishi = 100;
		long count = 0;
		//System.out.println(Math.pow(1.01, 2));
		while(rishi<X) {
			rishi = (long) Math.floor(rishi*1.01);
			count ++;
			//System.out.println(count);
		}
		System.out.println(count);
		}
		
	}


Measured memory_bytes: 35716
n = gets.to_i
a = gets.split.map(&:to_i)

cash = 1000

chunks = [*a, 0].each_cons(2).chunk { |a, b| a < b }.to_a
chunks.each do |ok, values|
  next unless ok
  
  lowest = values.first.first
  highest = values.last.last
  cash += (cash / lowest) * (highest - lowest)
end

puts cash


Measured memory_bytes: 14188
#include <bits/stdc++.h>
#define ALL(A) (A).begin(),(A).end()
#define ll long long
#define rep(i,n) for(int i=0;i<(n);i++)

const ll mod = 1e9+7;
const ll INF = -1*((1LL<<63)+1);
const int inf = -1*((1<<31)+1);

using namespace std;
ll f[100005];

ll func(ll n){
	if(n<2)return 1;
	return f[n] = n * f[n-2];
}
int main(void){
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll N;
	cin >> N;
	f[0] = 1;
	f[1] = 1;
	f[2] = 2;
	//rep(i,N+1)cout << "f(" << i << ")= "  << func(i) << endl;
	ll ans = 0;
	if(N%2){
		cout << 0 << endl;
		return 0;
	}
	if(N<10)cout << 0 << endl;
	else if(N%2) cout << 0 << endl;
	else if(N%2==0){
		ans += N/10;
		ll x = 50;
		while(x<=N){
			ans += N/x;
			x *=5;
		}
		cout << ans << endl;
	}
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
#define sz(x) ((int)(x).size())
using ll=long long;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define MOD  1000000007
const ll INF=1e18;
template<class T>void show(vector<T>v){for (int i = 0; i < v.size(); i++){cerr<<v[i]<<" ";}cerr<<endl;}
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b){ a = b; return 1; } return 0; }



int main(int argc, char const *argv[]) {
  string s;
  cin >> s;
  if (s[0] == s[1] || s[1] == s[2] || s[2] == s[3]) puts("Bad");
  else
    puts("Good");
  return 0;
}

Measured memory_bytes: 3592
#include <iostream>
#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <cstdio>
#include <string>
#include <vector>
#include <cstring>
#include <algorithm>
#include <unordered_map>

using namespace std;
const int INF = 0x3f3f3f3f;
//static const auto _____ = []()
//{
//	ios::sync_with_stdio(false);
//	cin.tie(nullptr);
//	return nullptr;
//}();
typedef long long ll;

int main(int argc, char *argv[]) {
    int N, V;
    cin >> N >> V;
    vector<ll> v(N + 1, 0);
    vector<ll> w(N + 1, 0);
    for (int i = 1; i <= N; i++) {
        cin >> v[i] >> w[i];
    }
    int upper = N * 1000; // 由题目得到的最大价值，每件物品最大价值为1000，有N件物品
    vector<ll> dp(upper + 1, INF);// 这里求最小容量，所以初始化为-INF
    dp[0] = 0; //前0个物品，价值为0的所消耗的最小容量为0
    for (int i = 1; i <= N; i++) {
        for (int j = upper; j >= w[i]; j--) {
            dp[j] = min(dp[j], dp[j - w[i]] + v[i]);
        }
    }
    // dp[N][i] 存储的是对应前N个物品，价值为i时的最小容量
    // 题目要求我们求最大价值，所以我们更加关注的是dp[N][i]中的i，而不是dp[N][i] = x中的x
    ll res = 0; // 求最大价值
    for (int i = 0; i <= upper; i++) {
        if (dp[i] <= V) {
            res = i;
        }
    }
    cout << res;
    return 0;
}

Measured memory_bytes: 1024
import java.util.*;

public class Main 
{
	final static int MAX=100005;
	static Pp[] object=new Pp[MAX];
	static int head,tail;
	public static void main(String[]args)
	{
		
		Scanner scanner=new Scanner(System.in);
		int sum=0,c;
		int q,n;
		Pp u;
		n=scanner.nextInt();
		q=scanner.nextInt();

		for(int i=1;i<=n;i++ )
		{
			object[i]=new Main().new Pp();
			object[i].name=scanner.next();
			object[i].t=scanner.nextInt();
		}
		
		head=1;tail=n+1;
		while(head!=tail)
		{
			u=dequeue();
			c=min(q,u.t);
			u.t-=c;
			sum+=c;
			if(u.t>0)
			{
				enqueue(u);
			}else {
				System.out.println(u.name+" "+sum);
			}
		}
		
		
		
		
	}
	
	static void enqueue(Pp x)
	{
		object[tail]=x;
		tail=(tail+1)%MAX;
		
	}
	
	static Pp dequeue()
	{
		Pp x=object[head];
		head=(head+1)%MAX;
		return x;
	}
	
	static int min(int a,int b)
	{
		return a<b?a:b;
	}
	
	public  class Pp
	{
		 String name;
		 int t;		
	}
	




}

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

int main()
{
    int ans = 0;
    string s;
    cin >> s;

    for (int i = 0, j = s.length() - 1; i != j && i < j ; i++, j--)
    {
        if (s[i] != s[j]) ans++;
    }

    cout << ans << endl;
}

Measured memory_bytes: 3548
#include <iostream>
#include <string>
#define rep(i, n) for(i = 0; i < n; i++)
#define int long long

using namespace std;

const int N = 1e6 + 10;

int n;
int a[N];
int b[N];

signed main() {
	int i;
	
	cin >> n;
	string s; cin >> s;
	rep(i, n) {
		a[i] = s[i] - '1';
	}
	
	rep(i, n) {
		b[i] = a[i] % 2;
	}
	
	int hoge = 0;
	rep(i, n) {
		if (((n - 1) & i) == i) { hoge ^= b[i]; }
	}
	if (hoge == 1) { cout << 1 << endl; return 0; }
	
	rep(i, n) { if (a[i] == 1) break; }
	if (i < n) { cout << 0 << endl; return 0; }
	
	rep(i, n) {
		b[i] = a[i];
	}
	hoge = 0;
	rep(i, n) {
		if (((n - 1) & i) == i) { hoge ^= b[i]; }
	}
	cout << hoge << endl;
	return 0;
}

Measured memory_bytes: 17028
#include <iostream>

using namespace std;

int n, m;
int a[10001];

int main(int argc, char const *argv[]) {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        cin >> a[i];
    }

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

    return 0;
}


Measured memory_bytes: 3200
#include<bits/stdc++.h>
#define int long long
using namespace std;
constexpr int mod=1e9+7;
signed main(){
    int a,b,h,m;
    cin>>a>>b>>h>>m;
    m+=h*60;
    double rada=2*M_PI*m/60,radb=2*M_PI*m/720;
    double ax=a*sin(rada),ay=a*cos(rada),bx=b*sin(radb),by=b*cos(radb);
    cout<<fixed<<setprecision(20)<<hypot(ax-bx,ay-by)<<endl;
}

Measured memory_bytes: 4100
#include <stdio.h>
 
int main(void)
{
    int a, b, c, tmp;
    scanf("%d%d%d", &a, &b, &c);
    
    if(b < a){
        tmp = b;
        b = a;
        a = tmp;
    }

    printf("%s\n", c > a && c < b ? "Yes" : "No");

    return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#define rep(i, n) for(ll i = 0; i < n; ++i)
#define repR(i, n) for(ll i = n; i >= 0; ++i)
#define FDS(i, n) for(ll i = 0; i < n; ++i)
#define FDSR(i, n) for(ll i = n; i >= 0; ++i)
#define FOR(i, m, n) for(ll i = m; i < n; ++i)
#define FORR(i, m, n) for(ll i = m;i >= n;--i)
#define VSORT(v) sort(v.begin(), v.end());
#define VREV(v) reverse(v.begin(), v.end());
#define INF 999999999
#define itn ll
#define ednl endl
using namespace std;
typedef long long ll;template<typename Typell>Typell G_C_D(Typell a, Typell b){if (a < 0) a = -a;if (b < 0) b = -b;while (b != 0) {a %= b;if (a == 0) return b;b %= a;}return a;}template<typename Typell>
Typell G_C_D(const std::vector<Typell> &list){Typell a = list[0];for (size_t i = 1; i < list.size(); ++i) {a = G_C_D(a, list[i]);}return a;}template<typename Typell>Typell L_C_M(Typell a, Typell b) {if( a == 0 && b == 0)return 0;return a / G_C_D(a, b) * b;}
template<typename Typell>Typell L_C_M(const std::vector<Typell> &list){Typell a = list[0];for (size_t i = 1; i < list.size(); ++i) {a = L_C_M(a, list[i]);}return a;}

int main(){
	cin.tie(0);ios::sync_with_stdio(false);
	int N;
	cin>>N;
	FDS(i,7){
		if(pow(2,i)<=N){
			if(pow(2,i+1)>N){
				cout<<pow(2,i)<<endl;
			}
		}
	}
}

Measured memory_bytes: 256
N,Y=list(map(int,input().split()))
flag=0
Y//=1000
z=Y%5
Y-=z
N-=z
for i in range(N+1):
    if flag==1:
        break
    for j in range(N+1-i):
        if flag==1:
            break
        k=N-i-j
        if i*10+j*5+k*1==Y:
            print(i,j,k+z)
            flag=1
if flag==0:
    print("-1 -1 -1")

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
int main()
{
	int a,b,k;
	cin>>k>>a>>b;
	if((a%k==0)||(b%k==0))
    {
        cout<<"OK"<<endl;
    }
    else if(b/k>a/k)
    {
        cout<<"OK"<<endl;
    }
    else
    {
        cout<<"NG"<<endl;
    }
	return 0;
}


Measured memory_bytes: 3636
#include<bits/stdc++.h>
#define INF 1e9
#define llINF 1e18
#define MOD 1000000007
#define pb push_back
#define mp make_pair 
#define F first
#define S second
#define ll long long
#define ull unsigned long long
#define vi vector<ll>
#define vvi vector<vi>
#define DBG_N(hoge) cerr<<" "<<(hoge)<<endl;
#define DBG cerr<<"!"<<endl;
#define BITLE(n) (1LL<<((ll)n))
#define BITCNT(n) (__builtin_popcountll(n))
#define SUBS(s,f,t) ((s).substr((f)-1,(t)-(f)+1))
#define ALL(a) (a).begin(),(a).end()
using namespace std;
vi S;
bool b_search(ll num){  
  ll le=0,ri=S.size();
  while(ri-le>1){
    ll mid=(ri+le)/2;
    if(S[mid]<=num)le=mid;
    else ri=mid;
  }
  return S[le] == num;
}
int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  ll n;cin>>n;
  S.resize(n+1);
  S[0]=-llINF;
  for(int i=1;i<=n;i++)cin>>S[i];
  S.pb(llINF);
  ll m;cin>>m;
  ll ans=0;
  for(int i=0;i<m;i++){
    ll num;cin>>num;
    ans+=b_search(num);
  }
  cout<<ans<<endl;
  return 0;
}



Measured memory_bytes: 4388
#include <iostream>
#include <string>
#include <iomanip>
#include <algorithm>
#define rep(i,n) for(int i=0; i<n; i++)
using namespace std;
int main()
{
	int n, k, ans;
	cin >> n >> k;
	if(n%k  == 0) ans = 0;
	else ans = 1;
	cout << ans <<endl;
	return 0;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7;
const ll INF = 1LL << 60;
const double PI = 3.141592653589793238;
const double EPS = 1e-10;
ll dp[51][51][2501];
int x[50];
int main() {
	int N, A;
	cin >> N >> A;
	for (int i = 0; i < N; i++) cin >> x[i];
	dp[0][0][0] = 1;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j <= i; j++) {
			for (int k = 0; k <= 50 * j; k++) {
				dp[i + 1][j][k] += dp[i][j][k];
				dp[i + 1][j + 1][k + x[i]] += dp[i][j][k];
			}
		}
	}
	ll ans = 0;
	for (int i = 1; i <= N; i++) ans += dp[N][i][i*A];
	cout << ans << endl;
}


Measured memory_bytes: 48512
#include <iostream>
#include <stack>
#include <sstream>
#include <string>
#include <cstdio>

using namespace std;

int main() {
    double n1, n2;
    string str, temp;
    while (getline(cin, str)) {
        stack<double> st;
        stringstream ss(str);
        while (ss >> temp) {
            if (temp == "+") {
                n2 = st.top();
                st.pop();
                n1 = st.top();
                st.pop();
                st.push(n1 + n2);
            }
            else if (temp == "-") {
                n2 = st.top();
                st.pop();
                n1 = st.top();
                st.pop();
                st.push(n1 - n2);
            }
            else if (temp == "*") {
                n2 = st.top();
                st.pop();
                n1 = st.top();
                st.pop();
                st.push(n1 * n2);
            }
            else if (temp == "/") {
                n2 = st.top();
                st.pop();
                n1 = st.top();
                st.pop();
                st.push(n1 / n2);
            }
            else {
                st.push(stoi(temp));
            }
        }
        printf("%f\n", st.top());
    }

    return 0;
}

Measured memory_bytes: 3156
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.NoSuchElementException;
import java.util.stream.Stream;

public class Main {
    public static void main(String[] args) {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        try {
            int n = Integer.parseInt(br.readLine());
            int[] tmp = Stream.of(br.readLine().split(" "))
                    .mapToInt(Integer::parseInt)
                    .toArray();
            if (n != tmp.length) {
                System.out.println("Heap size not match.");
                return;
            }
            int[] a = new int[n + 1];
            for (int i = 1; i <= n; i++) {
                a[i] = tmp[i - 1];
            }
            for (int i = 1; i <= n; i++) {
                System.out.printf("node %d: ", i);
                System.out.printf("key = %d, ", a[i]);
                if (parent(i) >= 1) {
                    System.out.printf("parent key = %d, ", a[parent(i)]);
                }
                if (left(i) <= n) {
                    System.out.printf("left key = %d, ", a[left(i)]);
                }
                if (right(i) <= n) {
                    System.out.printf("right key = %d, ", a[right(i)]);
                }
                System.out.println();
            }
        } catch (IOException
                | NoSuchElementException
                | NumberFormatException e) {
            System.out.println(e);
        }
    }

    private static int parent(int i) {
        return i / 2;
    }

    private static int left(int i) {
        return i * 2;
    }

    private static int right(int i) {
        return i * 2 + 1;
    }
}



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

#include <boost/range/adaptors.hpp>
#include <boost/range/irange.hpp>

using namespace std;
using namespace boost;
using namespace boost::adaptors;

int main() {
    int64_t h, w, n;
    cin >> h >> w >> n;

    unordered_map<pair<int64_t, int64_t>, int64_t,
                  boost::hash<pair<int64_t, int64_t>>>
            s;
    for (auto _ : irange(0L, n)) {
        int64_t a, b;
        cin >> a >> b;

        for (auto dx : {-2L, -1L, 0L}) {
            for (auto dy : {-2L, -1L, 0L}) {
                auto nx = a + dx;
                auto ny = b + dy;

                if (nx <= 0 || nx > h - 2L) {
                    continue;
                }

                if (ny <= 0 || ny > w - 2L) {
                    continue;
                }

                ++s[make_pair(nx, ny)];
            }
        }
    }

    array<int64_t, 10> ans{};
    ans[0] = (h - 2) * (w - 2);
    for (const auto& kv : s) {
        // cerr << kv.first.first << "," << kv.first.second << ":" << kv.second
        //      << endl;
        ++ans[kv.second];
        --ans[0L];
    }

    for (auto i : irange(0L, 10L)) {
        cout << ans[i] << endl;
    }
}

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

const int INF = 1e9 + 5;

int main(int argc, char const *argv[])
{
	// ios_base::sync_with_stdio(false);
 //    cin.tie(NULL);
    ll int n,w;
    cin>>n>>w;
    ll int wt[n][2];
    for(ll int i=0;i<n;i++){
    	cin>>wt[i][0]>>wt[i][1];
    }
    ll int dp[w+1] = {0};
    for(ll int i=0;i<n;i++){
    	for(ll int j=w-wt[i][0];j>=0;j--){
    		dp[j+wt[i][0]] = max(dp[j]+wt[i][1],dp[j+wt[i][0]]);
    	}
    }
    ll int ans = 0;
    for(ll int i=0;i<=w;i++){
    	ans = max(ans,dp[i]);
    }
    cout<<ans;
	return 0;
}

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

int main(){
    queue<char> A,B,C;
    string s1,s2,s3; cin >> s1 >> s2 >> s3;
    rep(i,s1.size()) A.push(s1[i]);
    rep(i,s2.size()) B.push(s2[i]);
    rep(i,s3.size()) C.push(s3[i]);
    //cout << s1 << " " << s2 << " " << s3 << endl;

    char ch = A.front();
    A.pop();
    while(true){
        switch(ch){
        case 'a': 
            if(A.empty()) {
                cout << "A" << endl;
                return 0;
            }
            ch = A.front();
            A.pop();
            
            break;
        case 'b':
            if(B.empty()) {
                cout << "B" << endl;
                return 0;
            }
            ch = B.front();
            B.pop();
            
            break;

        case 'c' :
            if(C.empty()) {
                cout << "C" << endl;
                return 0;
            }
            ch = C.front();
            C.pop();
            
            break;
        }
    }
    

    return 0;
}


Measured memory_bytes: 256