akhauriyash/Code-Regression huggingface dataset:
// Problem : C - Low Elements
// Contest : AtCoder Beginner Contest 152
// URL : https://atcoder.jp/contests/abc152/tasks/abc152_c
// Memory Limit : 1024.000000 MB 
// Time Limit : 2000.000000 milisec 
// Powered by CP Editor (https://github.com/coder3101/cp-editor)

#include<bits/stdc++.h>
#define pb push_back
#define int long long
#define vi vector<int>
#define pii pair<int,int>
#define m_p(x,y) make_pair(x,y)
#define vp vector<pair<int,int>>
#define setbits(x) __builtin_popcount(x)
#define f first
#define se second
using namespace std;
template<typename T1,typename T2>istream &operator>>(istream &is, vector<pair<T1,T2>> &v) { for (pair<T1,T2> &t : v) is >> t.f>>t.se; return is; }
template<typename T>istream &operator>>(istream &is, vector<T> &v) { for (T &t : v) is >> t; return is; }
template<typename T>ostream &operator<<(ostream &os, const vector<T> &v) { for (const T &t : v) {os << t <<" ";} os << '\n'; return os; }
double pi=acos(-1.0);
int md=1000000007;
int abst(int a)
{return a<0?-a:a;}
struct HASH{
  size_t operator()(const pii &x)const{
    return (size_t) x.first * 37U + (size_t) x.second;}};

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

int Pow(int n,int x){int ans=1;
 while(x>0)
 {if(x&1)ans=(ans*n)%md;n=(n*n)%md;x=x>>1;}
 return ans;}

int max(int a,int b){return a>b?a:b;}
int min(int a,int b){return a<b?a:b;}

void solve()
{
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int n;
cin>>n;
vi v(n);
cin>>v;
int max=INT_MAX;int count=0;
for(int i=0;i<n;i++)
{
	if(v[i]<max)
	{
		max=v[i];
		count++;
	}
}
cout<<count;
}

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


Measured memory_bytes: 1792
import java.util.Scanner;
public class Main {
	

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		Scanner sc=new Scanner(System.in);
		int wintervacation = sc.nextInt();
		int kokugo= sc.nextInt();
		int  math= sc.nextInt();
		int  kokugoday= sc.nextInt();
		int  mathday= sc.nextInt();
		int dayk=0,daym=0,freeday=0;
		
		int k=kokugo/kokugoday;
		int kk=kokugo%kokugoday;
		if(kk>0){
			dayk=k+1;
		}else if(kk==0){
			dayk=k;
		}
		int p=math/mathday;
		int pp=math%mathday;
		if(pp>0){
			daym=p+1;
		}else if(pp==0){
			daym=p;
		}
		if(dayk<daym){
			freeday=wintervacation-daym;
		}else if(dayk>daym){
			freeday=wintervacation-dayk;
		}else if(dayk==daym){
			freeday=wintervacation-dayk;
		}
		System.out.println(freeday);
	}

}

Measured memory_bytes: 17168
a,b,c = list(map(int, input().split()))
k = int(input())

rest = k
while True:
    if rest == 0 or (a < b and b < c):
        break

    if a >= b:
        b *= 2
        rest -= 1
        continue
    
    if a >= c or b >= c:
        c *= 2
        rest -= 1
        continue

if a < b and b < c:
    print('Yes')
else:
    print('No')


Measured memory_bytes: 9180
#include<stdio.h>
int main()
{

    int a,b,p;
    scanf("%d",&a);
    scanf("%d",&b);

    if(b+b>a)
      {

       p=0;
       printf("%d",p);
   return 0;
      }

else p=a-(b+b);

printf("%d",p);
}


Measured memory_bytes: 128
#include <iostream>
#include <functional>
#include <algorithm>
#include <climits>
#include <string>
#include <vector>
#include <map>
#include <cmath>

using namespace std;

namespace _{struct _{_(){ // initialize
  cin.tie(0); ios::sync_with_stdio(false);
}}_;}
template <typename T, size_t size>
inline size_t len(const T (&)[size]) { return size; }
#define println(s) cout << s << '\n';
#define str to_string
#define rep(i, n) for (int i=0; i<int(n); i++)
#define all(c) (c).begin(), (c).end()

#define MAX_N  100
#define MAX_2N 200
int list[MAX_2N] = {-1};
int n, m;

void dump() {
  //rep(i, 2*n) cout << " " << list[i];
 // cout << '\n';
}
int main() {
  cin >> n >> m;
  rep(i, 2*n) list[i] = i+1;
  dump();

  rep(i, m) {
    int k; cin >> k;
    // temporary (buffer)
    int tmplist[MAX_2N] = {-1};
    // ??????????????£?????????
    if (k == 0) {
      rep(i, 2*n) {
        if (i % 2 == 0) // 1, ., 2, ., 3
          tmplist[i] = list[i/2];
        else // ., n+1, ., n+2, ., n+3
          tmplist[i] = list[n+((i-1)/2)];
      }
    }
    // k??§?????????
    else {
      // 1 ... k | k+1 ... 2n
      // ->
      // k+1 k+2 ... 2n | 1 2 ... k
      //
      rep(i, 2*n) {
        if (i < 2*n-k) // ???
          tmplist[i] = list[i+k];
        else {
          // ??? (1, 2, ..., k)
          tmplist[i] = list[i-(2*n-k)];
        }
      }
    }
    // copy
    rep(i, 2*n) list[i] = tmplist[i];
    dump();
  }

  // output
  rep(i, 2*n) {
    cout << list[i] << '\n';
  }
  return 0;
}

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

int main() {
  int n,b,f,r,v; 
  cin>>n;
  //vector<vector<int > > S(n,vector<int>(4));
  vector<vector<vector<int > > > X(4,vector<vector<int > > (3,vector<int>(10)));
 while(cin>>b>>f>>r>>v){
   X.at(b-1).at(f-1).at(r-1)+=v;
 }
  for(int i=0;i<4;i++){
    for(int j=0;j<3;j++){
      for(int k=0;k<10;k++){
       cout<<" "<< X.at(i).at(j).at(k);
        if(k==9){cout<<endl;}}
      if(j==2&&i<3){cout<<"####################"<<endl;}}
  }
 
  return 0;
}


Measured memory_bytes: 3156
X, Y, Z, K = [int(n) for n in input().strip().split(' ')]
A = sorted([int(s) for s in input().strip().split(' ')], reverse=True)
B = sorted([int(s) for s in input().strip().split(' ')], reverse=True)
C = sorted([int(s) for s in input().strip().split(' ')], reverse=True)

ABC = []
for i, a in enumerate(A):
    for j, b in enumerate(B):
        if (i + 1) * (j + 1) > K:
            break

        for k, c in enumerate(C):
            if (i + 1) * (j + 1) * (k + 1) > K:
                break

            ABC.append(a + b + c)

ABC.sort(reverse=True)

for s in ABC[:K]:
    print(s)


Measured memory_bytes: 47336
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();
        int ans = K * (int) Math.pow(K - 1, N - 1);
        System.out.println(ans);
    }
}

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

#define pb push_back
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
#define ii pair<int,int>
#define ll long long
#define vi vector<int>
#define vll vector<ll>
#define vii vector<ii>

using namespace std;

const int maxn = 1e5+10;
const int mod = 1e9+7;

int n;
vii g[maxn];
int ans[maxn];

void dfs(int u,int p,int color,int& maxc){
	int c=0;
	for(auto &w:g[u]){
		int v=w.ff,e=w.ss;
		if(v==p)
			continue;
		if(c+1==color)
			++c;
		ans[e] = ++c;
		dfs(v,u,c,maxc);
	}
	maxc=max(maxc,c);
}

int32_t main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(int i=1;i<n;++i){
		int a,b;
		cin>>a>>b;
		g[a].pb(ii(b,i));
		g[b].pb(ii(a,i));
	}
	int maxc=0;
	dfs(1,0,-1,maxc);
	cout<<maxc<<endl;
	for(int i=1;i<n;++i){
		cout<<ans[i]<<endl;
	}
	return 0;
}


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

int main() {
	int H, W;
	cin >> H >> W;
	char temp;
	vector<string> a;

	for (int i = 0; i < H; i++) {
		string temp;
		cin >> temp;
		a.push_back(temp);
	}

	vector<vector<bool> > b(H, vector<bool>(W, true));
	

	for (int i = 0; i < H; i++) {
		bool all = true;
		for (int j = 0; j < W; j++) {
			if (a[i][j] == '#') {
				all = false;
			}
		}
		if (all) {
			for (int j = 0; j < W; j++) {
				b[i][j] = false;
			}
		}
	}

	for (int i = 0; i < W; i++) {
		bool all = true;
		for (int j = 0; j < H; j++) {
			if (a[j][i] == '#') {
				all = false;
			}
		}
		if (all) {
			for (int j = 0; j < H; j++) {
				b[j][i] = false;
			}
		}
	}

	for (int i = 0; i < H; i++) {
		bool line = false;
		for (int j = 0; j < W; j++) {
			if (b[i][j]) {
				cout << a[i][j];
				line = true;
			}
		}
		if (line) {
			cout << "\n";
		}
	}


	return 0;
}

Measured memory_bytes: 256
a,b=map(int,input().split())
x=min(25*a/2,10*b)
if 25*a/2>=10*(b+1) or 25*(a+1)/2<=10*b:
  print(-1)
else:
  while x<max(25*a/2,10*b):
    x=x+1
  print(int(x))

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

int main(){
    int n,k;
    cin >> n >> k;
    vector<int> d(k);
    for(int i=0;i<k;i++) cin >> d[i];
    for(int i=n;n<10000;i++){
        int x=i;
        bool flag=0;
        for(int j=0;j<5;j++){
            for(int l=0;l<k;l++){
                if(x%10==d[l]){
                    flag=1;
                }
            }
            x/=10;
            if(x==0) break;
        }
        if(flag==0){
            cout << i << endl;
            break;
        }
    }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; i++)
#define rep2(i, x, n) for(int i = x; i <= n; i++)
#define rep3(i, x, n) for(int i = x; i >= n; i--)
#define elif else if
#define sp setprecision
#define pb(x) push_back(x)
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
typedef pair<ld, ld> pdd;
const ll MOD = 1e9+7;
//const ll MOD = 998244353;
const int inf = 1e8;
const ll INF = 1e16;
const string alpha = "abcdefghijklmnopqrstuvwxyz";

int main(){
    ll N, K;
    cin >> N >> K;
    int ans = 0;
    while(N > 0){
        ans++;
        N /= K;
    }
    cout << ans << endl;
}

Measured memory_bytes: 384
#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <bitset>
#include<iomanip>//小数点以下を精度良く表示
#include <map>

#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <numeric>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#define INF 2000000000
#define INF2 1000000000000000000
#define PI 3.1415926535
#define rep(i,n) for(int i=0;i<(n);i++)
typedef pair<int, int> P;
const ll MOD = 1000000007;
using Graph = vector<vector<int>>;



int main() {
    map<string, int> m;
    int n;
    cin >> n;
    int ans = 0;
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        if (m[s] == 0) {
            ans++;
            m[s] = i + 1;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 19260
#include <bits/stdc++.h>
#include<atcoder/all>
#define INF 1000000007
#define rep(i, N) for(ll i = 0; i < N; i++)
#define rep2(i, j, k) for(ll i = j; i < k; i++)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define print(x) cout << x << "\n"
#define print2(x, y) cout << x << " " << y << "\n"
#define printv(vec) rep(lp, vec.size()) cout << vec[lp] << " "; print(""); 
#define show(x) cerr << #x << " = " << x << "\n";
#define ALL(v) v.begin(), v.end()
#define SUM(v) accumulate(ALL(v), 0)
#define MAX(v) *max_element(ALL(v))
#define MIN(v) *min_element(ALL(v))
#define SORT(v) sort(ALL(v))
#define REV(v) reverse(ALL(v))
#define pb(x) push_back(x)
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
typedef long long ll;
using namespace std;
using namespace atcoder;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
using vs = vector<string>;

const int mod = INF;
class mint {
public:
	ll x;
	mint(ll x = 0) : x((x % mod + mod) % mod) {}
	mint operator-() const { 
		return mint(-x);
	}
	mint& operator+=(const mint& a) {
		if ((x += a.x) >= mod) x -= mod;
		return *this;
	}
	mint& operator-=(const mint& a) {
		if ((x += mod - a.x) >= mod) x -= mod;
		return *this;
	}
	mint& operator*=(const  mint& a) {
		(x *= a.x) %= mod;
		return *this;
	}
	mint operator+(const mint& a) const {
		mint res(*this);
		return res += a;
	}
	mint operator-(const mint& a) const {
		mint res(*this);
		return res -= a;
	}
	mint operator*(const mint& a) const {
		mint res(*this);
		return res *= a;
	}
	mint pow(ll t) const {
		if (!t) return 1;
		mint a = pow(t >> 1);
		a *= a;
		if (t & 1) a *= *this;
		return a;
	}
	mint inv() const {
		return pow(mod - 2);
	}
	mint& operator/=(const mint& a) {
		return (*this) *= a.inv();
	}
	mint operator/(const mint& a) const {
		mint res(*this);
		return res /= a;
	}
	friend ostream& operator<<(ostream& os, const mint& m){
		os << m.x;
		return os;
	}
};

ll modpow(ll x, ll n, ll p = INF) {
	if (n == 0) return 1 % p;
	if (n % 2 == 0) return modpow(x * x % p, n / 2, p);
	else return x * modpow(x, n - 1, p) % p;
}

ll op(ll a, ll b) {
    return max(a, b);
}

ll e() {
    return 0;
}

void Main(){

	ll N, K;
	cin >> N >> K;
	vl v(N);
	rep(i, N) cin >> v[i];
    rep(i, N) v[i] += (K + 5);
	
	segtree<ll, op, e> seg(300000 * 4 + 10);
 	vl dp(N);
    dp[N - 1] = 1;
    seg.set(v[N - 1], 1);
 // print(v[N - 1]);
    for(ll i = N - 2; i >= 0; i--){
      ll ma = seg.prod(v[i] - K, v[i] + K + 1);
      dp[i] = ma + 1;
      seg.set(v[i], dp[i]);
      //print2(i, dp[i]);
      //print(ma);
      //print2(v[i] - 4, v[i] + 4);
      //print("===");
    }
  
  ll ans = MAX(dp);
  print(ans);
	
}

int main(){
	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	ll t = 1;
	//cin >> t;
	rep(i, t) Main();
	return 0;
	
}





Measured memory_bytes: 47852
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long
using namespace std;

int n,w,a[105],b[105];
ll f[100005],s=0;

int main(void){
	scanf("%d %d",&n,&w);
	for(int i=1;i<=n;i++){
		scanf("%lld %lld",&a[i],&b[i]);
		s+=b[i];
	}
	memset(f,0x3f,sizeof(f));
	f[0]=0;
	for(int i=1;i<=n;i++){
		for(int j=s;j>=b[i];j--)
		f[j]=min(f[j],f[j-b[i]]+a[i]);
	}
	for(int i=s;i>=0;i--)
	if(f[i]<=w){
		printf("%d\n",i);
		break;
	}
}

Measured memory_bytes: 896
#include<stdio.h>
int main(void){
  int a;
  scanf("%d",&a);
  
  switch(a){
    case 25:
      printf("Christmas\n");
      break;
    case 24:
      printf("Christmas Eve\n");
      break;
    case 23:
      printf("Christmas Eve Eve\n");
      break;
    case 22:
      printf("Christmas Eve Eve Eve\n");
      break;
  }
  
  
  return 0;
}

Measured memory_bytes: 128
import collections
N = int(input()) 
A = sorted(list(map(int, input().split())))
unique_count = collections.Counter(A)
A_count1 = []
A_unique = list(set(A))
baisu = [0]*(10**6+1)

for k,v in unique_count.items():
    if v == 1: A_count1.append(k)

for a_unique in A_unique:
    for i in range(a_unique*2,10**6+1,a_unique):
        baisu[i] = 1

ans = 0

for a_count1 in A_count1:
    if baisu[a_count1]==0: ans += 1

print(ans)



















Measured memory_bytes: 44536
import sys

import numpy as np
import math, string, itertools, fractions, heapq, collections, re, array, bisect, copy, functools, random
from collections import deque, defaultdict, Counter
from heapq import heappush, heappop
from itertools import permutations, combinations, product, accumulate, groupby
from bisect import bisect_left, bisect_right, insort_left, insort_right
from operator import itemgetter as ig
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20
INF = float("INF")
mod = 10 ** 9 + 7
"""dd = [(-1, 0), (0, 1), (1, 0), (0, -1)];
ddn = dd + [(-1, 1), (1, 1), (1, -1), (-1, -1)];
ddn9 = ddn + [(0, 0)]
for dx, dy in dd:
        nx = j + dx; ny = i + dy
            if 0 <= nx < w and 0 <= ny < h:"""

def wi(): return list(map(int, sys.stdin.readline().split()))
def wip(): return [int(x) - 1 for x in sys.stdin.readline().split()]  # WideIntPoint
def ws(): return sys.stdin.readline().split()
def si(): return int(sys.stdin.readline())  # SingleInt
def ss(): return input()
def hi(n): return [si() for _ in range(n)]
def hs(n): return [ss() for _ in range(n)]  # HeightString
def s_list(): return list(input())
def mi(n): return [wi() for _ in range(n)]  # MatrixInt
def mip(n): return [wip() for _ in range(n)]
def ms(n): return [ws() for _ in range(n)]
def num_grid(n): return [[int(i) for i in sys.stdin.readline().split()[0]] for _ in range(n)]  # NumberGrid
def grid(n): return [s_list() for _ in range(n)]


def main():

    n = int(input())
    p = list(map(int,input().split()))
    q = list(map(int,input().split()))

    number = []
    for i in range(1,n+1):
        number.append(i)

    perm = list(itertools.permutations(number))
    count = 0
    for L in perm:
        count += 1
        if list(L) == p:
            a = count
        if list(L) == q:
            b = count

    print(abs(a-b))

if __name__ == '__main__':
    main()
    

Measured memory_bytes: 23384
#include <bits/stdc++.h>
using namespace std;
int A,B,C;

void swap(int *nx, int *ny)
{
    int temp = *nx;
    *nx = *ny;
    *ny = temp;
}

/*--- *n1≦*n2≦*n3となるように並べ替える ---*/
void sort3(int *n1, int *n2, int *n3)
{
    if (*n1 > *n2) swap(n1, n2);
    if (*n2 > *n3) swap(n2, n3);
    if (*n1 > *n2) swap(n1, n2);
}
int cunt;
int main(){

    cin>>A>>B>>C;
    sort3(&C,&B,&A);
    while(1){
        if(A>=B+2){
            cunt++;    
            B+=2;
        }else
            break;
   }     
   while(1){
        if(A>=C+2){
            C+=2;
            cunt++;
        }else
            break;
    }
    sort3(&C,&B,&A);
    if(A==B&&B==C)
        cout<<cunt<<"\n";
    else if(A==B&&B>C)
        cout<<cunt+2<<"\n";
    else
        cout<<cunt+1<<"\n";
    return 0;    

}



Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repI(i, d, n) for (int i = (d); i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;
using M = map<int, int>;
ll INF = 1ll<<61;
double pi = 3.141592653589793238;

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

  deque<ll> deq;

  rep(i, n) {
    if (i % 2 == 0) deq.push_back(a[i]);
    else deq.push_front(a[i]);
  }

  if (n % 2 == 1) reverse(deq.begin(), deq.end());

  rep(i, n) cout << deq[i] << " ";
  cout << endl;

  return 0;
}


Measured memory_bytes: 5376
#include <bits/stdc++.h>
#include <climits>
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
#define srep(i, begin, end) for (__typeof(end) i = begin; i != end; i++)
#define si(x) int x = scanInt();
#define sll(x) LL x = scanLong();
#define sci(x) int x; scanf("%d", &x);
#define scll(x) LL x; scanf("%lld", &x);
#define pi(x) printf("%d ", x)
#define pll(x) printf("%lld ", x)
#define nl printf("\n")
#define clr(a) memset(a, 0, sizeof(a))
#define PB push_back
#define MP make_pair
using namespace std;
typedef unsigned int UI; // 32 bit integer
typedef long int LI; // 32 bit integer
typedef unsigned long int ULI; // 32 bit unsigned integer
typedef long long int LL; // 64 bit integer
typedef unsigned long long int ULL; // 64 bit unsigned integer
typedef long double LD;
typedef vector<int> VI;
typedef vector<LL> VLL;
typedef deque<int> DI;
typedef deque<LL> DLL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
const LL MOD = 1e9+7;

/* Fast I/O */
inline int scanInt() {
	int n = 0;
	char ch = getchar();
	int sign = 1;
	while(ch < '0' || ch > '9') {
		if(ch == '-')	sign = -1;
		ch = getchar();
	}
	while(ch >= '0' && ch <= '9') {
		n = (n<<1)+(n<<3)+(int)(ch-'0');
		ch = getchar();
	}
	return n*sign;
}

inline LL scanLong() {
	LL n = 0;
	char ch = getchar();
	LL sign = 1;
	while(ch < '0' || ch > '9') {
		if(ch == '-')	sign = -1;
		ch = getchar();
	}
	while(ch >= '0' && ch <= '9') {
		n = (n<<1)+(n<<3)+(LL)(ch-'0');
		ch = getchar();
	}
	return n*sign;
}

const LL MAXN = 1e5+10;
vector<PLL> edges[MAXN];
bool visited[MAXN];

void dfs(LL src, LL cc) {
	visited[src] = true;
	rep(it, edges[src].begin(), edges[src].end()) {
		if(!visited[it->first])	dfs(it->first, cc);
	}
}

int main() {
	sll(n); sll(m);
	rep(i, 0, m) {
		sll(x); sll(y); sll(z);
		edges[x].PB(MP(y, z%2));
		edges[y].PB(MP(x, z%2));
	}
	LL cc = 0;
	rep(i, 1, n+1) {
		if(!visited[i])	dfs(i, cc++);
	}
	pll(cc); nl;
}


Measured memory_bytes: 12544
//define DEBUG for debug
//#define DEBUG

#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define mp make_pair 
#define pb push_back
#define MAX 100000+100
#define MOD 1000000007
typedef long long int ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
#ifdef DEBUG
	freopen("i.txt","r",stdin);
	freopen("o.txt","w",stdout);
#endif
	string day[7] = {"SUN", "MON", "TUE", "WED", "THU", "FRI","SAT"};
	int cevap[7]  = {7,6,5,4,3,2,1};
	string a;cin >> a;
	for(int i = 0;i < 7;i++){
		if(a == day[i]){
			cout << cevap[i];
			return 0;
		}
	}
	return 0;
}

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

"""Enumerates primes in an interval.

Verification: [0009](https://onlinejudge.u-aizu.ac.jp/status/users/hamukichi/submissions/1/0009/judge/4571021/Python3)
"""


import math
import sys


def segment_sieve(begin, end):
    """Enumerates the prime numbers in [`begin`, `end`).

    Returns (as a tuple):

    - `is_prime`: a list of bool values.
      If an integer `i` is a prime number, then `is_prime[i - begin]` is True.
      Otherwise `is_prime[i -begin]` is False.
    - `primes`: a list of prime numbers in [`begin`, `end`).
    """

    assert 1 < begin <= end
    sqrt_end = math.ceil(math.sqrt(end))
    is_prime_small = [True for i in range(sqrt_end)]
    is_prime_small[0] = False
    is_prime_small[1] = False
    is_prime = [True for i in range(end - begin)]
    for i in range(2, sqrt_end):
        if is_prime_small[i]:
            for j in range(2 * i, sqrt_end, i):
                is_prime_small[j] = False
            for k in range(max(2, (begin + i - 1) // i) * i, end, i):
                is_prime[k - begin] = False
    primes = [i for i, cond in enumerate(is_prime, begin) if cond]
    return is_prime, primes


def main():
    ns = [int(n) for n in sys.stdin.readlines()]
    max_n = max(ns)
    begin = 2
    is_prime, _ = segment_sieve(begin, max_n + 1)
    for n in ns:
        print(sum(is_prime[:n + 1 - begin]))


if __name__ == '__main__':
    main()



Measured memory_bytes: 25216
#include<iostream>
#include<queue>
using namespace std;
priority_queue<int> q1;
int main(){
	int a,b,c,d,n;
	int i,j,k;
	bool s[1005];
	cin>>n;
	for(i=0;i<n;i++){
		for(j=0;j<3;j++){
			cin>>a;
			q1.push(a);
		}
		a=q1.top();
		q1.pop();
		b=q1.top();
		q1.pop();
		c=q1.top();
		q1.pop();
		if(a*a==b*b+c*c){
			s[i]=true;
		}else{
			s[i]=false;
		}
	}
	for(i=0;i<n;i++){
		if(s[i]==true){
			cout<<"YES"<<endl;
		}else{
			cout<<"NO"<<endl;
		}
	}
	return 0;
}

Measured memory_bytes: 1208
#include <algorithm>
#include <climits>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <set>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

//std::cout << std::fixed << std::setprecision(10)
constexpr long long MOD = 1000000007;

int main()
{
  int N;
  std::cin >> N;
  std::vector<int> d(N);
  for (auto& val: d)
    std::cin >> val;
  std::sort(d.begin(), d.end());
  std::cout << d[N/2] - d[N/2-1] << std::endl;
  return 0;
}



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

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int x = 0;
  for (int i = 0; i < 5; i++) {
    int a;
    cin >> a;
    x += a;
  }
  cout << 15 - x << endl;
  return 0;
}

Measured memory_bytes: 3652
#include <iostream>
#include <string>
#include <vector>
#include <stdio.h>
#include <algorithm>
#define _USE_MATH_DEFINES
#include <cmath>
#include <numeric>
#include <iomanip>
#include <deque>
#include <tuple>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <sstream>
#include <stdexcept>
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/multiprecision/cpp_dec_float.hpp>

#define rep(i, x) for (int i = 0; i < (int)(x); i++)
#define FOR(i, a, done) for (int i = (a); i < (done); ++i)
#define all(a) (a).begin(), (a).end()
#define F first
#define S second
#define x first
#define y second
#define pb push_back
#define pf push_front
#define debug(a) cout << (a) << endl
namespace mp = boost::multiprecision;
using cpp_int = mp::cpp_int;
using ll = long long;
using namespace std;

ll M = 1000000007;
void solve()
{
	int n,m;
	cin>>n>>m;
	vector<int>a(n);
	int cnt=0;
	int sum=0;
	rep(i,n){
		cin>>a[i];
		sum+=a[i];
	}
	rep(i,n){
		if(a[i]*4*m>=sum){
			cnt++;
		}
	}
	if(cnt>=m){
		cout<<"Yes"<<endl;
	}else{
		cout<<"No"<<endl;
	}

	
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	solve();
}


Measured memory_bytes: 256
# 解説を参考に作成

# import sys
# sys.setrecursionlimit(10 ** 6)
# import bisect
# from collections import deque

def inverse(a, p):
    """逆元"""
    a_, p_ = a, p
    x, y = 1, 0
    while p_:
        t = a_ // p_
        a_ -= t * p_
        a_, p_ = p_, a_
        x -= t * y
        x, y = y, x
    x %= p
    return x


def dev_mod(a, b, mod):
    """a(= A % mod) / b を mod で割った余り"""
    return (a * inverse(b, mod)) % mod


# from decorator import stop_watch
#
#
# @stop_watch
def solve(X, Y):
    mod = 10 ** 9 + 7
    if (2 * Y - X) % 3 != 0:
        print(0)
        return
    a = round((2 * Y - X) / 3)
    b = Y - 2 * a
    a, b = max(a, b), min(a, b)
    
    if b < 0:
        print(0)
        return

    ans = 1
    for i in range(a + 1, a + b + 1):
        ans *= i
        ans %= mod
    ans %= mod
    for i in range(1, b + 1):
        ans = dev_mod(ans, i, mod)
    ans %= mod

    print(ans)


if __name__ == '__main__':
    X, Y = map(int, input().split())
    solve(X, Y)


Measured memory_bytes: 9088
n=int(input())
## これのループを入れ替えたものを考える
# ans=0
# for i in range(1,n):
#     for j in range(1,n):
#         if i%j==0:
#             ans+=i
# print(ans)
ans=0
for j in range(1,n+1):
    ## j+2j+...+[n/j]j
    tmp=n//j
    ans+=tmp*(tmp+1)*j//2
print(ans)

Measured memory_bytes: 63344
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MX=200010, inf=2e9;

int n, m;
bool ans[MX];
pii E[MX];

vector<pii> G[1010];
int D[1010][1010][2];

void dfs3(int v, int st, int idx){
    if(D[st][v][0]==0) D[st][v][0]=idx;
    else D[st][v][1]=idx;
    for(pii &e:G[v]){
        int x=e.first;
        if(D[st][x][0]!=0 && D[st][x][1]!=0) continue;
        if(D[st][x][0]==idx || D[st][x][1]==idx) continue;
        dfs3(x,st,idx);
    }
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    cin>>n>>m;
    for(int i=1; i<=m; i++){
        int u,v; cin>>u>>v;
        E[i]={u,v};
        G[u].push_back({v,i});
    }

    for(int v=1; v<=n; v++){
        D[v][v][0]=D[v][v][1]=-1;
        for(pii &p:G[v]){
            int x,idx; tie(x,idx)=p;
            if(D[v][x][0]!=0 && D[v][x][1]!=0) continue;
            dfs3(x,v,idx);
        }
    }

    for(int i=1; i<=m; i++){
        int u,v; tie(u,v)=E[i];
        ans[i] = !(D[u][v][0]==i && D[u][v][1]==0) ^ (D[v][u][0]==0);
    }
    for(int i=1; i<=m; i++) cout<<(ans[i] ? "same" : "diff")<<'\n';
    return 0;
}

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

using namespace std;

int main()
{
    int n;

    cin >> n;

    long long ans = 0;

    for(int i = 0; i < n; i++){
        int x;

        cin >> x;

        ans += (x - 1);
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<iomanip>
using namespace std;
using point = pair<double, double>;

double l2_dist(point p1, point p2){
  double dx = p1.first - p2.first, dy = p1.second - p2.second;
  return sqrt(dx * dx + dy * dy);
}

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

  vector<point> xy(N);
  for(int i = 0; i < N; i++){
    double x, y;
    cin >> x >> y;
    xy[i] = make_pair(x, y);
  }

  auto max_r = [&](double x, double y){
                 point p = make_pair(x, y);
                 double ret = 0;
                 for(int i = 0; i < N; i++){
                   ret = max(ret, l2_dist(p, xy[i]));
                 }
                 return ret;
               };

  auto fx = [&](double x){
              double ly = 0, uy = 1000;
              double fl = max_r(x, ly), fu = max_r(x, uy);
              while(abs(fl - fu) > 1e-8){
                double m1 = (2 * ly + uy) / 3, m2 = (ly + 2 * uy) / 3;
                double f1 = max_r(x, m1), f2 = max_r(x, m2);
                if(f1 < f2){
                  uy = m2;
                  fu = max_r(x, uy);
                }else{
                  ly = m1;
                  fl = max_r(x, ly);
                }
              }
              return fl;
            };

  double lx = 0, ux = 1000;
  double fl = fx(lx), fu = fx(ux);
  while(abs(fl - fu) > 1e-8){
    //cout << lx << ' ' << ux << endl;
    //cout << fl << ' ' << fu << endl;
    double m1 = (2 * lx + ux) / 3, m2 = (lx + 2 * ux) / 3;
    double f1 = fx(m1), f2 = fx(m2);
    if(f1 < f2){
      ux = m2;
      fu = fx(m2);
    }else{
      lx = m1;
      fl = fx(m1);
    }
  }

  cout << setprecision(20) << fl << endl;
}

  
                                        


Measured memory_bytes: 256
import sys
  
BIG_NUM = 2000000000
MOD = 1000000007
EPS = 0.000000001
  
  
S = str(input())
P = str(input())
  
is_ok = False
  
for i in range(len(S)):
    FLG = True
    for k in range(len(P)):
        if S[(i+k)%(len(S))] != P[k]:
            FLG = False
            break
  
    if FLG == True:
        is_ok = True
        break
  
if is_ok == True:
    print("Yes")
else:
    print("No")


Measured memory_bytes: 5580
#!/usr/bin/env python3
import sys

YES = "Yes"  # type: str
NO = "No"  # type: str


def solve(A: int, B: int, C: int):
    if (A == B and A != C) or (A== C and A != B) or (B == C and A!= B):
        print(YES)
    else:
        print(NO)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    A = int(next(tokens))  # type: int
    B = int(next(tokens))  # type: int
    C = int(next(tokens))  # type: int
    solve(A, B, C)

if __name__ == '__main__':
    main()


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

int main() {
  vector<string> types(4);
  types.at(0) = "AC"; types.at(1) = "WA"; types.at(2) = "TLE"; types.at(3) = "RE";
  map<string,int> judge;
  rep(i,4) {
    judge[types.at(i)] = 0;
  }
  int n;
  cin >> n;
  rep(i,n) {
    string type = "";
    cin >> type;
    if(type == types.at(0)) judge[types.at(0)] += 1;
    if(type == types.at(1)) judge[types.at(1)] += 1;
    if(type == types.at(2)) judge[types.at(2)] += 1;
    if(type == types.at(3)) judge[types.at(3)] += 1;
  }
  rep(i,4){
    auto key = types.at(i);
    auto value = judge[key];
    cout << key << " x " << value << endl;
  }
  return 0;
}


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

int main() {
  int n, m, x, y;
  cin >> n >> m >> x >> y;
  vector<int> xv(n);
  vector<int> yv(m);
  rep(i, n) cin >> xv[i];
  rep(i, m) cin >> yv[i];
  for(int i = x + 1; i <= y; i++) {
    bool flag_x = true;
    bool flag_y = true;
    rep(j, n) {
      if(xv[j] >= i) flag_x = false;
    }
    rep(j, m) {
      if(yv[j] < i) flag_y = false;
    }
    if(flag_x && flag_y) {
      cout << "No War" << endl;
      return 0;
    }
  }
  cout << "War" << endl;
  return 0;
}
    

Measured memory_bytes: 3624
#include <stdio.h>
int main(){
  int N=0,i=0,countAC=0,countWA=0,countTLE=0,countRE=0;
  char str[100000];
    scanf("%d",&N);
  for(i=1;i<=N;i++){
    scanf("%s",str);
    if((str[0]=='A')&&(str[1]=='C')){
      countAC++;
    }else if((str[0]=='W')&&(str[1]=='A')){
      countWA++;
    }else if((str[0]=='R')&&(str[1]=='E')){
      countRE++;
    }else if((str[0]=='T')&&(str[1]=='L')&&(str[2]=='E')){
      countTLE++;
    }
  }
  printf("AC x %d\nWA x %d\nTLE x %d\nRE x %d\n",countAC,countWA,countTLE,countRE);
}

Measured memory_bytes: 1740
#include <stdio.h>

int main(void) {
  int i, j;
  for(i = 1; i < 10; ++i) {
    for(j = 1; j < 10; ++j) {
      printf("%dx%d=%d\n", i, j, i * j);
    }
  }
  return 0;
}


Measured memory_bytes: 2592
#include <iostream>
#include<string>
#include<cmath>
#include<algorithm>
#include<cctype>
#include<queue>
#include<stack>
#include<stdio.h>
#include<vector>
#include<set>
#include<map>
#include<iomanip>
#define rep(i,n) for(int i=0;i<n;i++)
typedef int long long ll;

using namespace std;
int main(){

    string s;
    getline(cin,s);
    for(int i=0;i<s.size();i++){
        if(isalpha(s[i])){
            s[i]=toupper(s[i]);
        }
    }
           cout<<s<<endl;
}



Measured memory_bytes: 3160
#include <bits/stdc++.h>
using namespace std;
int main(){
  long long a,b,c,d;
  long long ans = 0;
  cin >> a >> b >> c >> d;
  ans = a * c;
  if(a * d > ans){
    ans = a * d;
  }
  if(b * c > ans){
    ans = b * c;
  }
  if(b * d > ans){
    ans = b * d;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3628
#include<bits/stdc++.h>
#define INP (1LL<<50)
using namespace std;
long long int dp[100100];
int main()
{
    int a,b,c,i,j;
    cin>>a;
    int s[a];
    for(i=0;i<a;i++)
    {
        dp[i]=INP;
    }
    dp[0]=0;
    for(i=0;i<a;i++)
    {
        cin>>s[i];
    }
    //s[a]=INP;
    for(i=0;i<a;i++)
    {
        dp[i+1]=min(dp[i+1],dp[i]+abs(s[i]-s[i+1]));
        dp[i+2]=min(dp[i+2],dp[i]+abs(s[i]-s[i+2]));
    }
    cout<<dp[a-1]<<endl;
    return 0;
}


Measured memory_bytes: 1408
n1, n2, n3 = [int(i) for i in input().split()]

n4 = [int(j) for j in input().split()]

n5 = []  

for i1 in range(n1):
    n5.append([int(k) for k in input().split()])

r1 = 0
for i2 in range(n1):
    t1 = 0
    for i3 in range(n2):
        t1 += n4[i3] * n5[i2][i3]
    
    if (t1 + n3) > 0:
        r1 += 1

print(r1)

Measured memory_bytes: 3064
#include <iostream>
#include <string>
#include <algorithm>
#include <utility>

using namespace std;

#define REP(var, count) for(int var=0; var<count; var++)

int dp[1010][1010];

int main(void) {
	
	string xstr, ystr;
	cin >> xstr;
	cin >> ystr;
	
	for(int x=0; x<xstr.size()+1; x++) {
		dp[x][0] = x;
		
		for(int y=1; y<ystr.size()+1; y++) {
			if (x==0) { dp[0][y] = y; continue; }
			
			if ( xstr[x-1] == ystr[y-1] ) {
				dp[x][y] = dp[x-1][y-1];
			} else {
				dp[x][y] = min({dp[x-1][y], dp[x][y-1], dp[x-1][y-1]}) + 1;
			}
		}
	}
		
	cout << dp[xstr.size()][ystr.size()] << endl;

}

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

#define N_MAX 3002
#define ll long long

using namespace std;

int n;

ll a[N_MAX];

ll dp[N_MAX][N_MAX];

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    for(int i = n; i >= 1; i--)
        for(int j = i; j <= n; j++)
            dp[i][j] = max(-dp[i + 1][j] + a[i], -dp[i][j - 1] + a[j]);
    cout << dp[1][n] << "\n";
    return 0;
}


Measured memory_bytes: 70016
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  string a,b;
  cin>>a>>b;
  int la=a.size();
  int lb=b.size();
  if(la>lb){cout<<"GREATER"<<endl;}
  else if(la<lb){cout<<"LESS"<<endl;}
  else if(a==b){cout<<"EQUAL"<<endl;}
  else if(a>b){cout<<"GREATER"<<endl;}
  else{cout<<"LESS"<<endl;}
}

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

using namespace std;

int ans, N, X, Y, niv[200009], t[200009], dp[200009];
bool safe[200009];
vector < int > red[200009], blue[200009];
queue < int > cc;

void dfsBlue (int nod, int tata)
{
    t[nod] = tata;
    for (auto it = blue[nod].begin (); it != blue[nod].end (); it ++)
        if (*it != tata)
            niv[*it] = niv[nod] + 1, dfsBlue (*it, nod);
}

bool atMost2BlueD (int x, int y) {return (t[x] == t[y] || x == t[y] || y == t[x] || x == t[t[y]] || y == t[t[x]]);}

int main ()
{
//freopen ("input", "r", stdin);
//freopen ("output", "w", stdout);

scanf ("%d %d %d\n", &N, &X, &Y);
for (int i=1; i<N; i++)
{
    int x, y;
    scanf ("%d %d", &x, &y);
    red[x].push_back (y);
    red[y].push_back (x);
}
for (int i=1; i<N; i++)
{
    int x, y;
    scanf ("%d %d", &x, &y);
    blue[x].push_back (y);
    blue[y].push_back (x);
}
dfsBlue (Y, -1);
for (int i=1; i<=N; i++)
    for (auto it = red[i].begin (); it != red[i].end (); it ++)
        if (!atMost2BlueD (i, *it))
            safe[i] = safe[*it] = 1;
if (safe[X])
{
    printf ("-1\n");
    return 0;
}
for (int i=1; i<=N; i++)
    dp[i] = N + 2;
dp[X] = 0, cc.push (X), ans = niv[X];
while (!cc.empty ())
{
    int nod = cc.front ();
    cc.pop ();
    if (dp[nod] >= niv[nod]) continue;
    if (niv[nod] > ans) ans = niv[nod];
    if (safe[nod])
    {
        printf ("-1\n");///Escape
        return 0;
    }
    for (auto it = red[nod].begin (); it != red[nod].end (); it ++)
        if (dp[*it] > dp[nod] + 1 && atMost2BlueD (nod, *it))
            dp[*it] = dp[nod] + 1, cc.push (*it);
}
printf ("%d\n", 2 * ans);
return 0;
}


Measured memory_bytes: 33276
N = int(input())
A = list(map(int, input().split()))
#print(N, A)
myans = 0
mytgt = A[0]
for n in range(1,N):
    #print(mytgt)
    if A[n] < mytgt:
        myans += (mytgt - A[n])
    mytgt = max(A[n], mytgt)
    #print(n,myans)
print(myans)

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

#define ll long long
#define ull unsigned long long
#define FOR(i,a,b) for (int i=(a);i<(b);++i)
#define REP(i,n) for(int i=0;i<(n);++i)
#define debug(x) cerr<<#x<<": "<<x<<'\n'
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define pb push_back
#define mp make_pair

using namespace std;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> PP;
typedef pair<ll, LP> LPP;

int dy[]={0, 0, 1, -1, 0};
int dx[]={1, -1, 0, 0, 0};

template<class T=int>
T in(){T x;cin>>x;return (x);}
template<class T>
void print(T& x){cout<<x<<'\n';}

const int MOD =(int)1e9+7;
const int MAX =510000;

ll fac[MAX],finv[MAX],inv[MAX];
void COMint(){
    fac[0]=fac[1]=1;
    finv[0]=finv[1]=1;
    inv[1]=1;
    for(int i=2;i<MAX;i++){
        fac[i]=fac[i-1]*i%MOD;
        inv[i]=MOD-inv[MOD%i]*(MOD/i)%MOD;
        finv[i]=finv[i-1]*inv[i]%MOD;
    }
}
ll COM(int n,int k){
    if(n<k) return 0;
    if(n<0||k<0)return 0;
    return fac[n]*(finv[k]*finv[n-k]%MOD)%MOD;
}

ll gcd(ll a,ll b){
    if(b==0)return a;
    if(a>b){
        swap(a,b);
    }
    return gcd(a,b%a);
}
ll lcm(ll a,ll b){
    ll g;g=gcd(a,b);
    return a*b/g;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N=in();
    int M=in();
    ll x[N];
    ll y[N];
    ll x_check[M];
    ll y_check[M];
    REP(i,N){
        cin>>x[i]>>y[i];
    }
    REP(i,M)cin>>x_check[i]>>y_check[i];

    ll ans;
    ll d_m;
    REP(i,N){
        d_m=1e10;
        REP(j,M){
            if(d_m>abs(x[i]-x_check[j])+abs(y[i]-y_check[j])){
                d_m=abs(x[i]-x_check[j])+abs(y[i]-y_check[j]);
                ans=j+1;
            }
        }
        print(ans);
    }
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
 
int main(){
    int n,m;
    char c[128],f;
    string s;
    while(cin >> n && n){
        s = "";
        for(int i=0;i<128;i++)c[i]=i;
        for(int i=0;i<n;i++){
            cin >> f;
            cin >> c[f];
        }
        cin >> m;
        for(int i=0;i<m;i++){
            cin >> f;
            s += c[f];
        }
        cout << s << endl;
    }
}

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

int main() {

	int n, k;
	scanf("%d %d", &n, &k);
	int ans = 0;
	for(int i = 0; i < n; i++) {
		int a;
		scanf("%d", &a);
		if(a > k - a) {
			ans += (k -  a) * 2;
		}else {
			ans += a * 2;
		}
	}
	printf("%d\n", ans);
}

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

#define int long long

const int M = 1e9+7;

int n;
int f[100005][2];
int ee,h[100005],nex[100005<<1],to[100005<<1];

void addedge(int x,int y)
{
	nex[++ee] = h[x];
	to[ee] = y;
	h[x] = ee;
}

void dfs(int x,int pre)
{
	f[x][0] = f[x][1] = 1;
	for(int i=h[x];i;i=nex[i])
		if(to[i]!=pre)
		{
			dfs(to[i],x);
			f[x][0] = (f[x][0]*(f[to[i]][0]+f[to[i]][1]))%M;
			f[x][1] = (f[x][1]*f[to[i]][0])%M;
		}
}

signed main()
{
	cin>>n;
	for(int i=1,x,y;i<n&&cin>>x>>y;i++)
	{
		addedge(x,y);
		addedge(y,x);
	}
	dfs(1,0);
	cout<<(f[1][0]+f[1][1])%M<<endl;
	
	return 0;
}

Measured memory_bytes: 9856
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		int n = s.nextInt();
		if (n > 24) {
			System.out.println(0);
			return;
		}
		int[] a = new int[n];
		Arrays.setAll(a, i -> s.nextInt());
		BitSet b = new BitSet(25);
		b.set(0);
		b.set(24);

		int r = 0;
		loop:
		for (int f = 0, e = 1 << n; f < e; ++f) {
			b.clear(1, 24);
			for (int i = 0; i < n; ++i) {
				int j = ((1 << i) & f) > 0 ? 24 - a[i] : a[i];
				if (b.get(j))
					continue loop;
				b.set(j);
			}

			int v = b.stream().skip(1)
					.map(o -> o - b.previousSetBit(o - 1))
					.min().getAsInt();
			r = Math.max(r, v);
		}
		System.out.println(r);
	}
}


Measured memory_bytes: 29112
#include<bits/stdc++.h>
#define ll long long int
#define vi vector< int >
#define vc vector< char >
#define vvi vector < vector< int > >
#define vvc vector < vector< char > >
#define vl vector< ll >
#define vll vector<pair<ll,ll>>
#define pii pair< int, int >
#define pll pair<ll, ll>
#define pf push_front
#define pb push_back
// #define range(c) c.begin(), c.end()
// #define ranger(c) c.rbegin(), c.rend()
#define all(c) c.begin(), c.end()
#define allr(c) c.rbegin(), c.rend()
#define forn(i, n) for(ll i = 0; i < n; ++i)
#define fornr(i, n) for(ll i = n-1; i >= 0; --i)
#define foro(i, n) for(ll i = 1; i <= n; ++i)
#define foror(i, n) for(ll i = n; i >= 1; --i)
#define endl '\n'
#define MOD 998244353
#define FIO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define pr(a) for(auto it :a) cout << (it) << " "; cout << endl;
#define pr2(a) for(int i = 0; i<a.size(); ++i){ for(int j = 0; j<a[i].size(); ++j) cout << a[i][j] << ' '; cout << endl;}
#define test ll T; cin >> (T); while(T--)

#define present(container, element) (container.find(element) != container.end())
// for set and maps
#define cpresent(container, element) (find(all(container),element) != container.end())
// for vectors

using namespace std;

int main() {
// #ifndef ONLINE_JUDGE
// 	freopen("/home/shivam/input.txt", "r", stdin);
// 	freopen("/home/shivam/output.txt", "w", stdout);
// 	freopen("/home/shivam/error.txt", "w", stderr);
// #endif

	FIO;

	int n;
	cin >> n;
	vi arr(n), brr(n), crr(n);
	forn(i, n)
	cin >> arr[i] >> brr[i] >> crr[i];

	foro(i, n - 1) {
		arr[i] += max(brr[i - 1], crr[i - 1]);
		brr[i] += max(crr[i - 1], arr[i - 1]);
		crr[i] += max(arr[i - 1], brr[i - 1]);
	}

	cout << max(arr[n - 1], max(brr[n - 1], crr[n - 1])) << endl;

	return 0;
}


Measured memory_bytes: 4444
/*
2020-04-20
atcoder ABC
C - Replacing Integer
*/

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

int main() {
    //変数定義, 入力処理
    // vector<vector<int>> data(3, vector<int>(4)); //二次元配列
    unsigned long long N, K;
    cin >> N >> K;
    //処理
    while (N > K / 2) {
        if(N > K) {
            N %= K;
        } else {
            N = K - N;
        }
    }
    //出力処理
    cout <<  N << endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<n;i++)
#define repl(i,l,r) for(ll i=(l);i<(r);i++)
#define per(i,n) for(ll i=n-1;i>=0;i--)
#define perl(i,r,l) for(ll i=r-1;i>=l;i--)
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define ins insert
#define pqueue(x) priority_queue<x,vector<x>,greater<x>>
#define all(x) (x).begin(),(x).end()
#define CST(x) cout<<fixed<<setprecision(x)
#define vtpl(x,y,z) vector<tuple<x,y,z>>
#define at(x,i) get<i>(x);
#define rev(x) reverse(x);
using ll=long long;
using vl=vector<ll>;
using vvl=vector<vector<ll>>;
using pl=pair<ll,ll>;
using vpl=vector<pl>;
using vvpl=vector<vpl>;
const ll MOD=1000000007;
const ll MOD9=998244353;
const int inf=1e9+10;
const ll INF=4e18;
const ll dy[8]={1,0,-1,0,1,1,-1,-1};
const ll dx[8]={0,-1,0,1,1,-1,1,-1};
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
int main(){
    vl p;
    ll n=2;
    while(n<100000){
        bool check=true;
        for(auto x:p){
            if(n%x==0){
                check=false;
                break;
            }
        }
        if(check)p.pb(n);
        n++;
    }
    vl l;
    for(auto x:p){
        ll k=(x+1)/2;
        if(binary_search(all(p),k))l.pb(x);
    }
    vl cus(100001,0);
    for(auto x:l)cus[x]++;
    rep(i,100000)cus[i+1]+=cus[i];
    ll q;cin >> q;
    rep(i,q){
        ll a,b;cin >> a >>b;
        cout << cus[b]-cus[a-1] <<endl;
    }
}

Measured memory_bytes: 1664
#include <iostream>
#include <cstdlib>
 
using namespace std;
// https://qiita.com/Clpsplug/items/81fe12400d4093a8fb5a
 
int main() {
    int N;
    cin >> N;
    string S;
    cin >> S;

    int counter = 0;
    for (int i = 0; i < N - 2; i++) {
        if (S[i] == 'A' && S[i + 1] == 'B' && S[i + 2] == 'C') {
            counter++;
        }
    }

    cout << counter << endl;
}

Measured memory_bytes: 3100
import sys
sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
printV = lambda x: print(*x, sep="\n")
printH = lambda x: print(" ".join(map(str,x)))
def IS(): return sys.stdin.readline()[:-1]
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LII(rows_number): return [II() for _ in range(rows_number)]
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def LLI1(rows_number): return [LI1() for _ in range(rows_number)]

n,w = MI()
item = []
for i in range(n):
	item.append(LI())

def main():
	dp = [0]*(w+1)
	for i in range(n):
		for j in range(w,item[i][0]-1,-1):
			dp[j] = max(dp[j], dp[j-item[i][0]]+item[i][1])
	print(dp[w])

if __name__ == '__main__':
	main()


Measured memory_bytes: 39792
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n,f[200005][2];
char s[200005];
int main()
{
	scanf("%s",s+1);
	n=(int)strlen(s+1);
	f[0][0]=0;
	f[0][1]=-2147483648;
	for(int i=1;i<=n;i++)
	{
		f[i][0]=f[i][1]=-2147483647;
		if(s[i]!='D')f[i][1]=max(f[i][1],max(f[i-1][0],f[i-1][1]));
		if(s[i]!='P')f[i][0]=max(f[i][0],max(f[i-1][0]+1,f[i-1][1]+2));
	}
	int now=f[n][1]>f[n][0];
	for(int i=n;i>=1;i--)
	{
		s[i]=now?'P':'D';
		if(now)now=f[i-1][1]>f[i-1][0];
		else now=f[i-1][1]+2>f[i-1][0]+1;
	}
	printf("%s\n",s+1);
	return 0;
}

Measured memory_bytes: 3416
// Ballazt
//0a..brute force
//0b..greedy
//1..memorizatton of some sort	remember something cleverly
//2..sort
//3..binary search	keep check a particular solution
//4..dp				repeating strucutre,limited choices
//5..dfs/bfs		matrix with obstacles
//6..correlate to graph in some way		each state is a point
#include <bits/stdc++.h>
using namespace std;
#define ll unsigned long long int
#define endl "\n"


int main()

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

	ll x;
	cin>>x;

	ll count=0;
	ll p=100;
	while(1)
	{
		if(x<=p*1.01)
		{
			cout<<count+1;
			return 0;
		}

		else
		{
			count++;
			p*=1.01;
		}
	}



	
}

Measured memory_bytes: 3636
import java.util.*;

class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int[] arr = new int[8];
    for (int i = 0; i < n; i++) {
      String str = sc.next();
      for (int j = 0; j < 8; j++) {
        arr[j] = (int)(str.charAt(j)-'0');
      }
      Arrays.sort(arr);
      int max = 0;
      int min = 0;
      for (int j = 0; j < 8; j++) {
        max += arr[j]*Math.pow(10,j);
        min += arr[7-j]*Math.pow(10,j);
      }
      System.out.println(max-min);
    }
  }
}

Measured memory_bytes: 11000
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

N, K = map(int, input().split())
H = list(map(int, input().split()))

H = sorted(H, reverse=True)
for i in range(min(K, N)):
    H[i] = 0

print(sum(H))


Measured memory_bytes: 25760