akhauriyash/Code-Regression huggingface dataset:
fn main() {
    let s = std::io::stdin();
    let mut sc = Scanner { stdin: s.lock() };
    let n = sc.read();
    let mut a: Vec<usize> = sc.vec(n);
    let mut count = 0;
    for i in 1..n {
        if a[i - 1] == i {
            count += 1;
            a.swap(i - 1, i);
        }
    }
    if a[n - 1] == n {
        count += 1;
    }
    println!("{}", count);
}

pub struct Scanner<R> {
    stdin: R,
}

impl<R: std::io::Read> Scanner<R> {
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .stdin
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n')
            .take_while(|&b| b != b' ' && b != b'\n')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }
    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
    #define rep(i, n) for(int i = 0; i < n; i++)
    using namespace std;
     
    int main() {
        long x, ans;
        cin >> x;
        ans = 2 * (x / 11);
        x -= 11 * (x / 11);
        if(x > 6) ans += 2;
        else if(x > 0) ans += 1;
        cout << ans << endl;
    }

Measured memory_bytes: 256
// Problem Code: abc170_d

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>

using namespace std;

int not_divisible(int N, vector<int>& A) {
	int cnt = 0, limit = *max_element(A.begin(), A.end());
	vector<int> freq(limit + 1);
	vector<bool> mark(limit + 1);

	for (int x: A)
		freq[x]++;

	for (int i = 1; i <= limit; i++) {
		if (freq[i] == 0 || mark[i])
			continue;
		for (int x = i; x <= limit; x += i)
			mark[x] = true;
		cnt += freq[i] == 1;
	}

	return cnt;
}

int main() {
	int N;
	cin >> N;
	vector<int> A(N);
	for (int i = 0; i < N; i++)
		cin >> A[i];
	cout << not_divisible(N, A);
	return 0;
}

Measured memory_bytes: 8196
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, srt, end) for (long long i = (srt); i < (long long)(end); i++)

int main(){
    ll N, Q, K;
    cin >> N;
    vector<vector<pair<ll,ll>>> G(N+1);
    rep(i, 0, N-1){
        ll a, b, c;
        cin >> a >> b >> c;
        G[a].push_back({b,c});
        G[b].push_back({a,c});
    }


    cin >> Q >> K;

    queue<ll> que;
    vector<ll> par(N+1), dist(N+1);
    dist[K] = 0;
    par[K] = K;
    que.push(K);
    while(!que.empty()){
        auto t = que.front();
        que.pop();
        for(auto g : G[t]){
            if(g.first == par[t]) continue;
            par[g.first] = t;
            dist[g.first] = dist[t] + g.second;
            que.push(g.first);
        }
    }

    rep(i, 0, Q){
        ll x, y;
        cin >> x >> y;
        cout << dist[x] + dist[y] << endl;
    }

    return 0;
}

Measured memory_bytes: 10752
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
signed main(){
  Int n,c;
  cin>>n>>c;
  using P = pair<Int, Int>;
  vector<vector<P> > v(c);
  for(Int i=0;i<n;i++){
    Int s,t,u;
    cin>>s>>t>>u;
    u--;
    v[u].emplace_back(s,t);
  }
  vector<P> e;
  for(Int i=0;i<c;i++){
    sort(v[i].begin(),v[i].end());
    auto u=v[i];
    v[i].clear();
    for(auto p:u){
      if(v[i].empty()||v[i].back().second!=p.first)
	v[i].push_back(p);
      else v[i].back().second=p.second;
    }
    for(auto p:v[i]) e.push_back(p);
  }
  sort(e.begin(),e.end());
  //for(auto p:e) cout<<p.first<<" "<<p.second<<endl;
  auto check=[&](Int x){
    vector<Int> v(x,-1);
    //cout<<x<<endl;
    for(Int i=0;i<(Int)e.size();i++){
      bool f=0;
      for(Int j=0;j<x;j++){
	if(v[j]<e[i].first){
	  //cout<<i<<" "<<j<<endl;
	  v[j]=e[i].second;
	  f=1;
	  break;
	}
      }
      if(!f) return 0;
    }
    return 1;
  };
  Int ans=1;
  while(!check(ans)) ans++;
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 4728
s = int(input())
mod = 10**9+7

fact = [1,1]
finv = [1,1]
inv = [0,1]
 
for i in range(2,s+5):
    fact.append((fact[-1]*i)%mod)
    inv.append((inv[mod%i]*(mod-mod//i))%mod)
    finv.append((finv[-1]*inv[-1])%mod)
 
def nCr(n,r,mod):
    if r > n:
        return 0
    else: 
        return fact[n]*finv[r]*finv[n-r]%mod

def nPr(n,r,mod):
    if r > n:
        return 0
    else: 
        return fact[n]*finv[n-r]%mod

ans = 0
for i in range(1,s//3+1):
    x = s-3*i
    ans += nCr(i+x-1,x,mod)
    ans %= mod
print(ans)

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

int add (int a, int b) 
{
	a += b;
	if (a >= 1000000007) 
		a -= 1000000007;
	return a;
}                 
 
int main () 
{
	ios_base :: sync_with_stdio (NULL);cin.tie (NULL), cout.tie (NULL);  
	int n, m, dp[2001], ans, s[2001], t[2001], pref[2001];
	dp[0] = pref[0] = 1;
	cin >> n >> m;
	for (int i = 1; i <= n; i ++) 
	cin >> s[i];
	for (int i = 1; i <= m; i ++) 
	cin >> t[i], pref[i] = 1;
	for (int i = 1; i <= n; i ++) 
	{
	 for (int j = 1; j <= m; j ++) 
	 	if (s[i] == t[j])
	 		dp[j] = add (dp[j], pref[j - 1]);
	  for (int j = 1; j <= m; j ++) 
	  	pref[j] = add (pref[j - 1], dp[j]);
	}
	cout << pref[m];
	return 0;      
}

Measured memory_bytes: 256
import java.util.*;
import java.io.*;

class Main {

    public static void main(String[] args) {

	Scanner stdin = new Scanner(System.in);
	int[] date = {31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
	int[] cum = new int[12];
	for ( int i = 1; i < cum.length; i++ ) {
	    cum[i] = cum[i - 1] + date[i - 1];
	}

	String[] days = {"Thursday", "Friday", "Saturday", "Sunday", "Monday", "Tuesday", "Wednesday"};
	
	while ( true ) {

	    final int m = stdin.nextInt();
	    final int d = stdin.nextInt();
	    if ( m == 0 && d == 0 ) {
		break;
	    }

	    final int day = cum[m - 1] + d - 1;
	    System.out.println( days[day % 7] );
	    
	}	
	
    }
    
}

Measured memory_bytes: 17208
# Vicfred
# https://atcoder.jp/contests/abc072/tasks/arc082_a
# greedy, bucket sort
class Counter(dict):
    def __missing__(self, i):
        return 0

n = int(input())
a = list(map(int, input().split()))

counter = Counter()

for item in a:
    counter[item] += 1
    counter[item+1] += 1
    counter[item-1] += 1

maxima = max(counter.values())

print(maxima)



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

    int a[n];
    for(int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    if(n == k) {
        cout << 1 << endl;
        return 0;
    }

    int count = 0;
    for(int i = 1; i < n; i += k - 1) {
        count++;
    }

    cout << count << endl;
    return 0;
}


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

typedef long long int ll;
typedef long double ld;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
#define pll pair<ll,ll>
#define MP make_pair
#define ff first
#define ss second
#define PB push_back
#define mod 1000000007
#define lp(i,start,end) for(ll i=start;i<=end;i++) 
#define deb1(a) cout<<#a<<" = "<<(a)<<endl;
#define deb2(a,b) cout<<#a<<" = "<<(a)<<", "<<#b<<" = "<<(b)<<endl;
#define deb3(a,b,c) cout<<#a<<" = "<<(a)<<", "<<#b<<" = "<<(b)<<", "<<#c<<" = "<<(c)<<endl;


ll modu(ll a, ll b)
{
	ll ans =1;
	while(b>0)
	{
		if(b&1)
		ans = (ans*a)%mod;
		b/=2;
		a = (a*a)%mod;
	}
	return ans;
}

int main()
{
	fastio
	ll t=1;
	//cin >> t;
	while(t--)
	{
		ll x[6],ans;
		lp(i,1,5){
			cin>>x[i];
			if(x[i]==0)
				ans=i;
		}
		cout<<ans<<endl;

	}
	return 0;	
}


Measured memory_bytes: 3608
<?php
fscanf(STDIN, "%d %d %d", $H, $W, $K);
$map = [];
for ($i = 0; $i < $H; $i++) {
    fscanf(STDIN, "%s", $c);
    $map[$i] = str_split($c);
}
$HW = pow(2, $H+ $W);
$ans = 0;
for ($i = 1; $i < $HW; $i++) {
    $cnt = 0;
    $selH = intdiv($i, pow(2, $W));
    $selW = $i - pow(2, $W) * $selH;
    if ($selH === 0 || $selW === 0) continue;
    $cnt = 0;
    for ($y = 0; $y < $H; $y++) {
        if (($selH & pow(2, $y)) === 0) continue;
        for ($x = 0; $x < $W; $x++) {
            if (($selW & pow(2, $x)) === 0) continue;
            if ($map[$y][$x] === '#') $cnt++;
        }
    }
    if ($cnt === $K) $ans++;
}
printf("%d", $ans);

Measured memory_bytes: 16208
#include <iostream>

int sum_digit(int n) {
  int sum = 0;
  while(n != 0) {
    sum += n % 10;
    n /= 10;
  }
  return sum;
}

int is_harshad(int n) {
  int sum = sum_digit(n);
  return n % sum == 0;
}

int main() {
  int n;
  std::cin >> n;
  if(is_harshad(n))
    std::cout << "Yes\n";
  else
    std::cout << "No\n";
}

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

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> ii;
typedef tuple<ll, ll, ll> iii;
typedef vector<ll> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
#define REP(i,n) for (ll i = 0; i < n; ++i)
#define REPR(i,n) for (ll i = n-1; i >= 0; --i)
#define FOR(i,m,n) for (ll i = m; i < n; ++i)
#define FORR(i,m,n) for (ll i = n-1; i >= m; --i)
#define FORE(x,xs) for (const auto& x : xs)
#define ALL(v) v.begin(), v.end()

const int MAX = 2e5+10;
const int BITS = 31;

vi createTable(const vi& word) {
    int n = word.size();
    vi table(n+1);
    table[0] = -1;
    int j = -1;
    REP (i, n) {
        while (j >= 0 && word[i] != word[j]) j = table[j];
        table[i+1] = ++j;
    }
    return table;
}

vi kmp(const vi& str, const vi& word) {
    vi table = createTable(word), ret;
    int m = 0, i = 0, n = str.size();
    while (m+i < n) {
        if (word[i] == str[m+i]) {
            if (++i == (int)(word.size())) {
                ret.push_back(m);
                m = m+i-table[i];
                i = table[i];
            }
        } else {
            m = m + i - table[i];
            if (i > 0) i = table[i];
        }
    }
    return ret;
}

int N;
int A[MAX], B[MAX];

vi sub(int bit) {
    vi a(N), a_not(N), b(2*N-1);
    REP (i, N) {
        int n = (A[i] >> bit) & 1;
        a[i] = n;
        a_not[i] = (1^n);
    }
    REP (i, N-1) b[i] = b[i+N] = ((B[i] >> bit) & 1);
    b[N-1] = ((B[N-1] >> bit) & 1);

    vi ret;
    FORE (idx, kmp(b, a)) ret.push_back(idx);
    FORE (idx, kmp(b, a_not)) ret.push_back(idx);
    return ret;
}

vii solve() {
    map<int, int> shift_count;
    REP (bit, BITS) {
        FORE (s, sub(bit)) shift_count[s]++;
    }

    vii ret;
    for (auto iter = shift_count.begin(); iter != shift_count.end(); iter++) {
        int shift = iter->first;
        if (iter->second != BITS) continue;
        ret.push_back(make_pair((N-shift)%N, A[0] ^ B[shift]));
    }
    sort(ALL(ret));
    return ret;
}

int main() {
    cin >> N;
    REP (i, N) cin >> A[i];
    REP (i, N) cin >> B[i];
    FORE (x, solve()) cout << x.first << " " << x.second << endl;
}

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

using namespace std;

int main() {

    int N, M;
    cin >> N >> M;

    int ans = 0;
    for (int i = 1; i <= M/2; i++) {
        if (M % i == 0 and M / i >= N) {
            ans = i;
        }
    }

    if (N == 1) ans = M;

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

Measured memory_bytes: 256
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Scanner;

public class Main {
	static Scanner sc = new Scanner(System.in);
	static int[][] trans = { 
		{ 0, 1, 2, 3, 4, 5, 6, 7 },
		{ 4, 7, 6, 5, 0, 3, 2, 1 },
		{ 0, 4, 5, 1, 3, 7, 6, 2 },
		{ 1, 5, 6, 2, 0, 4, 7, 3 },
		{ 2, 6, 7, 3, 1, 5, 4, 0 },
		{ 3, 7, 4, 0, 2, 6, 5, 1 },
	};
	static int[] C = new int[8];
	static int[] color = new int[8];
	static ArrayList<Oct> octs;

	public static void main(String[] args) {
		while (sc.hasNext()) {
			HashMap<String, Integer> map = new HashMap<String, Integer>();
			for (int i = 0; i < 8; ++i) {
				String c = sc.next();
				if (!map.containsKey(c)) {
					map.put(c, map.size());
				}
				C[i] = map.get(c);
			}
			octs = new ArrayList<Oct>();
			color[0] = C[0];
			boolean[] used = new boolean[8];
			used[0] = true;
			dfs(1, color, used);
			System.out.println(octs.size());
		}
	}

	static void dfs(int pos, int[] color, boolean[] used) {
		if (pos == 8) {
			if (check(color)) {
				octs.add(new Oct(color));
			}
			return;
		}
		for (int i = 1; i < 8; ++i) {
			if (used[i]) continue;
			color[pos] = C[i];
			used[i] = true;
			dfs(pos + 1, color, used);
			used[i] = false;
		}
	}

	static boolean check(int[] color) {
		int[] c = new int[8];
		for (int i = 0; i < 6; ++i) {
			for (int j = 0; j < 8; ++j) {
				c[j] = color[trans[i][j]];
			}
			for (int j = 0; j < 4; ++j) {
				rot(c);
				for (Oct o : octs) {
					if (Arrays.equals(o.c, c)) {
						return false;
					}
				}
			}
		}
		return true;
	}
	
	static void rot(int[] color) {
		for (int i = 0; i < 2; ++i) {
			int tmp = color[i * 4 + 0];
			color[i * 4 + 0] = color[i * 4 + 1];
			color[i * 4 + 1] = color[i * 4 + 2];
			color[i * 4 + 2] = color[i * 4 + 3];
			color[i * 4 + 3] = tmp;
		}
	} 
	
	static class Oct {
		int[] c;

		Oct(int[] c) {
			this.c = c.clone();
		}
	}

}

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

signed main() {
  int X;
  cin >> X;
  
  int ans = 0;
  
  int beki = 0;
  for( int i = 1; i < 1000; i++ ){ //b
    beki = i;
    for( int j = 2; j < 1000; j++ ){//p
      beki *= i;
      if( ans < beki && beki <= X ){
        ans = beki;
      }
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 1LL<<62
#define inf 1000000007 

int main() {
	double n;
	cin>>n;
	double ans1,ans2;
	ans1=ans2=0;
	for(ll i=1;i<=n;i++){
		if(i%2!=0){
			ans1++;
		}
	}
	cout <<ans1/n;
	// your code goes here
	return 0;
}

Measured memory_bytes: 384
fun main(arr: Array<String>) {
    val (n,m) = readLine()!!.split(" ").map { it.toInt() }
    val inpt = (1..n).map { readLine()!!.split(" ").map { it.toInt() }.drop(1) }
    val ans = (1..m).filter {f-> inpt.all { it.contains(f) } }
    println(ans.size)
}


Measured memory_bytes: 38280
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Main main = new Main();
        main.solve();
    }

    public void solve() {
        Scanner scan = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
        long X = scan.nextLong();
        long current = 100;
        long ans = 0;
        while (current < X) {
            ans += 1;
            current = (long) Math.floor(current * 1.01);
        }
        System.out.println(ans);
    }
}


Measured memory_bytes: 27064
import functools
N, M = list(map(int,input().split()))
A = list(map(int,input().split()))
ASUM = functools.reduce(lambda x, y: x + y, A)
if len([1 for i in range(N) if A[i]/ASUM*4*M >= 1]) >= M:
    print('Yes')
else:
    print('No')

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

int main() {
	string s;
	int cnt = 0;
	cin >> s;
	for (int i = 0;i < 3;i++) {
		if (s[i] == 'o') cnt++;
	}
	cout << 700 + cnt * 100;
	return 0;
}

Measured memory_bytes: 256
N=int(input())
Papers = list(map(int,input().split()))

evens = [i for i in Papers if i %2==0]

flg = 0

for j in evens:
    if j%3==0 or j%5==0:
        flg += 0
    else:
        flg+=1

if flg!=0:
    print('DENIED')
else:
    print('APPROVED')

Measured memory_bytes: 3060
#include<bits/stdc++.h>
#include<unordered_set>
#include<unordered_map>
#include <iostream>
#include <string>
#include <cmath>
using namespace std;
#define ll long long
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
#define FORR(i,a,b)for(ll i=(a);i<=(b);i++)
#define repR(i,n) for(ll i=n;i>=0;i--)
#define all(v)(v).begin(),(v).end()
#define rall(v)(v).rbegin(),(v).rend()
#define F first
#define S second
#define pb push_back
#define pu push
#define COUT(x) cout<<(x)<<endl
#define PQ priority_queue<ll>
#define PQR priority_queue<ll,vector<ll>,greater<ll>>
#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define mp make_pair
#define maxs(x,y) (x = max(x,y))
#define mins(x,y) (x = min(x,y))
#define sz(x) (int)(x).size()
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll MOD = 1000000007LL;
const ll INF = 1LL << 60;
using vll = vector<ll>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vvll = vector<vll>;
using vstr = vector<string>;
using pll = pair<ll, ll>;
using vc = vector<char>;
using vvc = vector<vc>;
ll dx[4]={0,1,0,-1};
ll dy[4]={1,0,-1,0};
int main(){
  ll h,w;
  cin>>h>>w;
  ll n;
  cin>>n;
  vll a(n);
  rep(i,n) cin>>a[i];
  vvll ans(h,vll(w));
  ll cu=0;
  ll i=0;
  ll j=0;
  while(1){
    if(a[cu]==0) cu++;
    if((i%2==0&&j==w-1)||(i%2==1&&j==0)){
      ans[i][j]=cu+1;
      a[cu]--;
      i++;
      if(i==h) break;
    }
    else if(i%2==0){
      ans[i][j]=cu+1;
      j++;
      a[cu]--;
    }
    else if(i%2==1){
      ans[i][j]=cu+1;
      j--;
      a[cu]--;
    }
  }
  rep(i,h){
    rep(j,w){
      cout<<ans[i][j]<<" ";
    }
    cout<<endl;
  }
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
#define int long long 
int x[10],y[10];
signed main(void){
  int N; cin >> N;
  double fac = 1.0;
  for(int i = 0; i < N; i++){
    fac *= (double)(i+1);
    cin >> x[i] >> y[i];
  }
  vector<int> id(N);
  for(int i = 0; i < N; i++){ id[i] = i;}
  double ans = 0.0;
  do{
    
    double sum = 0.0;
    for(int i = 0; i < N-1; i++){
      int X1 = x[id[i]];
      int Y1 = y[id[i]];
      
      int X2 = x[id[i+1]];
      int Y2 = y[id[i+1]];
    
    sum += sqrt(pow(X2-X1,2.0)+pow(Y2-Y1,2.0));
      
    }
    
    ans += sum;
    
  }while(next_permutation(id.begin(),id.end()));
  
  printf("%.20f\n", ans/fac );
  
  return 0;
}

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

#define int long long
#define rep(i,l,r) for(int i=(int)(l);i<(int)(r);i++)
#define all(x) (x).begin(),(x).end()
#define pb push_back
template<class T>bool chmax(T &a,T b){if(a<b){a=b;return 1;}return 0;}
template<class T>bool chmin(T &a,T b){if(a>b){a=b;return 1;}return 0;}

typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;

const int inf = 1LL<<60;
const int mod = 1e9 + 7;
const double eps = 1e-9;

/*{
}*/

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

  vector<string> s(n);
  rep(i, 0, n) cin >> s[i];

  map<string, int> cnt;
  rep(i, 0, n){
    sort(all(s[i]));
    cnt[s[i]]++;
  }

  int ans = 0;
  for(auto i : cnt){
    ans += i.second*(i.second-1)/2;
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 18176
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<climits>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<tuple>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vii vector<int>
#define vll vector<ll>
#define lb lower_bound
#define pb push_back
#define mp make_pair
#define rep(i,n) for(ll i=0;i<n;i++)
#define rep2(i,a,b) for(ll i=a;i<b;i++)
#define repr(i,n) for(ll i=n-1;i>=0;i--)
#define all(x) x.begin(),x.end()
#define INF (ll)1e9+7
#define LLINF (ll)1e30
// #define int ll
using namespace std;
const int MOD = 1e9 +7;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    string s,t,res="";
    cin>>s>>t;
    int T=t.size(),S=s.size();
    int dp[3010][3010]={};
    rep(i,S){
        rep(j,T){
            if(s[i]==t[j]){
                dp[i+1][j+1]=max(dp[i][j]+1,dp[i+1][j+1]);
            }
            dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j+1]);
            dp[i+1][j+1]=max(dp[i+1][j],dp[i+1][j+1]);            
        }
    }
    while(S>0 && T>0){
        if(dp[S][T]==dp[S-1][T]) S--;
        else if(dp[S][T]==dp[S][T-1]) T--;
        else{
            res =s[S-1] +res;
            T--;S--;
        }
    }
    cout<<res<<endl;
    return 0;
}

Measured memory_bytes: 35712
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>

#define _GLIBCXX_DEBAC
using namespace std;
	
int findx(int n) {
	int sum = 0;
	while (n > 0) {
		sum += n % 10;
		n /= 10;
	}

	return sum;
}

string divide[4] = { "dream","dreamer","erase","eraser" };

int main() {
	string s;
	cin >> s;
	bool a = false;
	for (int i = 0; i < s.size(); i++) {
		if (i % 2 == 0) {
			if (s[i] == 'L') {
				a = true;
				break;
			}
		}
		else {
			if (s[i] == 'R') {
				
				a = true;
				break;
			}
		}
	}
	if (a) { cout << "No\n"; }
	else { cout << "Yes\n"; }
		return 0;
}









Measured memory_bytes: 256
from collections import deque
h, w = map(int, input().split())

maze = [list(input()) for _ in range(h)]
#print(maze)
ans = 0
def solve(sx, sy):
    INF = 1000000
    reached = [[INF for _ in range(w)] for _ in range(h)]
    reached[sx][sy] = 0
    d = deque()
    d.append([sx, sy])
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]    
    while d:
        x, y = d.popleft()
        for i in range(4):
            next_y = y + dy[i]
            next_x = x + dx[i]
            if next_x < 0 or next_x > h - 1 or next_y < 0 or next_y > w - 1:
                continue
            if maze[next_x][next_y] == "#":
                continue
            if reached[next_x][next_y] != INF:
                continue
            d.append([next_x, next_y])
            reached[next_x][next_y] = reached[x][y] + 1
    gl = 0
    for i in range(h):
        for j in range(w):
            if maze[i][j] == ".":
                gl = max(gl, reached[i][j])
    return gl

for i in range(h):
    for j in range(w):
        if maze[i][j] == ".":
            res = solve(i, j)
            ans = max(ans, res)
print(ans)

        

Measured memory_bytes: 47596
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list
#from itertools import combinations # (string,3) 3回
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))
def main():
    n = int(input())
    XY = []
    for i in range(n):
        x,y = readInts()
        XY.append([x,y])
    a = 0
    for x1,y1 in XY:
        for x2,y2 in XY:
            a += ((x1-x2) ** 2 + (y1-y2)**2) **0.5
    print(a/n)
if __name__ == '__main__':
  main()


Measured memory_bytes: 3060
A = int(input())
B = int(input())
C = int(input())
X = int(input())
ans = 0

for a in range(A+1):
    for b in range(B+1):
        for c in range(C+1):
            if 500*a + 100*b + 50*c == X:
                ans +=1
print(ans)

Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MOD 1000000007
//
ll n;
vector<ll>a;
vector<vector<ll>>dp;
//

ll F(ll idx, ll k)
{
	if (k < 0)
		return 0;
	if (idx == n)
		return (k == 0);
	if (dp.at(idx).at(k) != -1)
		return dp.at(idx).at(k);
	ll aa = F(idx, k - 1);
	ll bb = F(idx + 1, k - a.at(idx) - 1);
	ll cc = F(idx + 1, k);
	ll ans = (aa - bb + cc) % MOD;
	ans = (ans + MOD) % MOD;
	return (dp.at(idx).at(k) = ans);
}

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

	ll k; cin >> n >> k;
	a = vector<ll>(n);
	for (auto &it : a)
		cin >> it;
	dp = vector<vector<ll>>(n, vector<ll>(k + 1, -1));
	cout << F(0, k);

	return 0;
}

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

int main() {
int n;
cin>>n;
string s[n];
for(int i=0;i<n;i++){
  cin>>s[i];
}
int flg=1;
for(int i=0;i<n-1;i++){
  if(s[i][s[i].size()-1]!=s[i+1][0]) flg=0;
}
//cout<<flg<<endl;
sort(s,s+n);
for(int i=0;i<n-1;i++){
  if(s[i]==s[i+1]) flg=0;
}
if(flg) cout<<"Yes"<<endl;
else cout<<"No"<<endl;

//cout<<s[1]<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define clr(a) memset(a, 0, sizeof(a))
#define sz(x) x.size()
#define printarray(arr) for (auto it = arr.begin(); it != arr.end(); ++it) cout<<*it<<" "; cout<<endl;
#define rep(n) for (ll i = 0; i < n; i++)
#define repc(i, n) for (ll i = 0; i < n; i++)
#define FOR(i, x, y) for (int i = x; i < y; i++)
#define DEC(i, x, y) for (int i = x; i >= y; i--)
#define all(v) v.begin(), v.end()
#define min3(a, b, c) min(a, min(b, c))
#define max3(a, b, c) max(a, max(b, c))
#define alla(a, n) a, a + n
#define gcd(a, b) __gcd(a, b)
#define lcm(a, b) (a * b)/gcd(a, b)
#define int long long int
#define ull unsigned long long

using namespace std;
const int MOD = 1e9 + 7;
const int MAXN = 1e5 + 5;

int fastexpo(int b, int exp){
    if(exp == 0) return 1;
    if(exp == 1) return b;
    int ans = (fastexpo(b,exp/2) % MOD);
    ans *= ans;
    ans %= MOD;
    if(exp % 2 == 1){
        ans *= b;
    }
    ans %= MOD;
    return ans;
}



signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin>>n;
    int a[n+2];
    for(int i= 0;i<n;i++){
        cin>>a[i];
    }
    int pref[n+2];
    pref[0] = 1;
    int fin = 0;
    for(int i= 1;i<=n;i++){
        pref[i] = pref[i-1]%MOD;
        pref[i] += (a[i-1]%MOD);
        pref[i] %= MOD;
        fin = pref[i];
    }
    int ans= 0;
    for(int i= 0;i<n;i++){
        ans += ((a[i]%MOD) * (fin-pref[i+1]+MOD)%MOD)%MOD;
        ans %= MOD;
    }
    cout<<ans<<endl;
    return 0;
}





Measured memory_bytes: 6772
N = int(input())
def kaijou(x):
    h = 1
    for i in range(1,x+1):
        h *= i
    return h
P = list(map(int, input().split()))
Q = list(map(int, input().split()))
a = 0
b = 0
R = [0 for _ in range(N)]
S = [0 for _ in range(N)]
for i in range(N):
    R[P[i]-1] = 1
    s = P[i]-1-sum(R[:(P[i]-1)])
    a += s*kaijou(N-1-i)
for j in range(N):
    S[Q[j]-1] = 1
    t = Q[j]-1-sum(S[:(Q[j]-1)])
    b += t*kaijou(N-1-j)
print(abs(a-b))

Measured memory_bytes: 3064
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
long long min(long long x,long long y){return x<y?x:y;}
int main(void){
	int n,m,i,j,num;
	scanf("%d%d",&n,&m);
	long long a[n],b[n],c[m],d[m];
	for(i=0;i<n;i++)scanf("%lld%lld",&a[i],&b[i]);
	for(i=0;i<m;i++)scanf("%lld%lld",&c[i],&d[i]);
	for(i=0;i<n;i++){
		long long dis=200000000;
		for(j=0;j<m;j++){
			int di = labs(a[i]-c[j])+labs(b[i]-d[j]);
			if(di<dis){
				dis=di;
				num = j;
			}
		}
		printf("%d\n",num+1);
	}
	
	return 0;
}

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

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)

int main() {
  string S;
  cin >> S;
  int temp = 0;
  int  ans;
  for(int i = 0; i < S.size(); i++) {
    if(S[i] == 'A' || S[i] == 'C' || S[i] == 'G' || S[i] == 'T' ) temp++;
    else {
      temp = 0;
    }
  ans = max(temp, ans);
  }

  cout << ans << endl;
  

  return 0;
}

Measured memory_bytes: 760
//
// Created by Hideaki Imamura on 2020-03-14.
//
# include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair <ll, ll> l_l;
typedef pair<int, int> i_i;

template<class T>
inline bool chmax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
inline bool chmin(T &a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

# define EPS (1e-7)
# define INF (1e9)
# define PI (acos(-1))
//const ll mod = 1000000007;

int n;

void dfs(int x, int y, string s) {
    if (x == n) {
        cout << s << endl;
        return;
    }

    for (int i = 0; i <= y + 1; ++i) {
        dfs(x + 1, max(y, i), s + (char)('a' + i));
    }
    //cout << s[x-1] - 'a' + 1 << " " << y << endl;
    //if (s[x-1] - 'a' + 1 <= y) dfs(x + 1, y + 1, s + (char)(s[x-1] + 2));
}

int main() {
    cin >> n;
    dfs(1, 0, "a");
    return 0;
}

Measured memory_bytes: 1536
import collections

[n,m] = [int(i) for i in input().split()]
def BFS(s,G,num):
    ls = collections.deque()
    check = [0] * num
    marker = [-1] * num
    check[0] = 1
    ls += G[s]
    for i in G[s]:
        marker[i] = s
    while(len(ls)):
        now = ls.popleft()
        if check[now] == 1:
            continue
        else:
            #print(now)
            check[now] = 1
            ls += G[now]
            for i in G[now]:
                if marker[i] == -1:
                    marker[i] = now
    return marker
dic = collections.defaultdict(list)
for i in range(m):
    [a,b] = [int(i)-1 for i in input().split()]
    dic[a].append(b)
    dic[b].append(a)

ans = BFS(0,dic,n)

print("Yes")
for i in range(1,n):
    print(ans[i]+1)


Measured memory_bytes: 39420
def f(operand, a, b):
    if operand == "+":
        return int(a) + int(b)

    elif operand == "-":
        return int(a) - int(b)

    elif operand == "*":
        return int(a) * int(b)

por=[]

por = list(input().split())

stack=[]

for i in por:

    #number
    if i.isdigit() == True:  
        stack.append(int(i))

    #string
    else:                     
        b = stack.pop()
        a = stack.pop()
        stack.append(f(i,a,b))

print(stack[0])



Measured memory_bytes: 5600
/**
  * http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_11_B&lang=jp
  * Structure and Class - Dice II
  */
object Main {

  class Dice(numbers: IndexedSeq[Int]) {
    def apply(number: Int): Int = {
      numbers(number)
    }

    def rotateTo(direction: Char): Dice = {
      direction match {
        case 'N' => new Dice(IndexedSeq(numbers(1), numbers(5), numbers(2), numbers(3), numbers(0), numbers(4)))
        case 'S' => new Dice(IndexedSeq(numbers(4), numbers(0), numbers(2), numbers(3), numbers(5), numbers(1)))
        case 'W' => new Dice(IndexedSeq(numbers(2), numbers(1), numbers(5), numbers(0), numbers(4), numbers(3)))
        case 'E' => new Dice(IndexedSeq(numbers(3), numbers(1), numbers(0), numbers(5), numbers(4), numbers(2)))
      }
    }

    def find(number: Int): Int = {
      numbers.indexWhere(_ == number)
    }
  }

  def main(args: Array[String]): Unit = {
    val dice = new Dice(io.StdIn.readLine().split(" ").map(_.toInt))
    val questions = io.StdIn.readInt()
    Iterator.continually(io.StdIn.readLine()).takeWhile(_ != null).map(_.split(" ").map(_.toInt))
      .take(questions)
      .map {
        case Array(top, front) => determineRight(dice, top, front)
      }
      .foreach(println)
  }

  def determineRight(dice: Dice, top: Int, front: Int): Int = {
    val operationsToTop = Seq("", "N", "W", "E", "S", "NN")
    val operationsToFront = Seq("S", "", "WSE", "ESW", "SEEN", "N")
    val dice2 = operationsToTop(dice.find(top)).foldLeft(dice)(_.rotateTo(_))
    val dice3 = operationsToFront(dice2.find(front)).foldLeft(dice2)(_.rotateTo(_))
    dice3(2)
  }
}

Measured memory_bytes: 44316
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<ll,ll>;

int main(){
        ll h, n;
        scanf("%lld %lld", &h, &n);
        vector<ll> value(n), weight(n);
        for(ll i=0; i<n; i++) scanf("%lld %lld", &weight[i], &value[i]);

        vector<ll> dp(300000, 1e18);
        dp[0] = 0;
        for(ll i=0; i<n; i++){
                for(ll j=0; j<=300000; j++){
                        if(0<=j-weight[i]) dp[j] = min(dp[j], dp[j-weight[i]]+value[i]);
                }
        }
        ll ans = 1e18;
        for(ll i=h; i<300000; i++) ans = min(ans, dp[i]);
        printf("%lld\n", ans);
        return 0;
}

Measured memory_bytes: 2560
#define _CRT_SECURE_NO_WARNINGS
#include "bits/stdc++.h"
using namespace std;
#define rep(i, n) for(int i=0; i<(n); ++i)
#define FOR(i, m, n) for(int i=(m); i<(n); ++i)
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define mp make_pair
#define pb push_back
#define Cout(x) cout << (x) << endl
#define Cout2(x, y) cout << (x) << " " << (y) << endl
#define dump(x) cerr << #x << " = " << (x) << endl;
typedef long long LL;
typedef vector<int> VI;
typedef vector<LL> VL;
typedef vector<string> VS;
typedef vector<bool> VB;
typedef vector<vector<int>> VVI;
typedef pair<int, int> PII;
const int inf = 1e9;
const double pi = acos(-1.0);

int main() {
	LL N, W; cin >> N >> W;
	VL w(N), v(N);
	rep(i, N)cin >> w[i] >> v[i];

	vector<VL> dp(109, VL(100009));
	rep(i, N) {
		rep(j, W + 1) {
			if (j >= w[i]) {
				dp[i + 1][j] = max(dp[i + 1][j], dp[i][j - w[i]] + v[i]);
			}
			dp[i + 1][j] = max(dp[i + 1][j], dp[i][j]);
		}
	}
	Cout(dp[N][W]);
}

Measured memory_bytes: 86528
#include <limits.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <math.h>

#define P 1000000007

int comp(const void *a, const void *b){return *(int*)a-*(int*)b;}

int main(void){
	int n, i;
	int a[100001];
	scanf("%d", &n);
	for(i=0; i<n; i++){
		scanf("%d", a+i);
	}
	long n1=0, n2=0;
	{
		int sum=0;
		int f=0;
		for(i=0; i<n; i++){
			sum += a[i];
			if(f){
				if(sum<=0){n1=n1+1-sum; sum=1;}
			}else{
				if(sum>=0){n1=n1+1+sum; sum=-1;}
			}
			f=!f;
		}
	}
	{
		int sum=0;
		int f=1;
		for(i=0; i<n; i++){
			sum += a[i];
			if(f){
				if(sum<=0){n2=n2+1-sum; sum=1;}
			}else{
				if(sum>=0){n2=n2+1+sum; sum=-1;}
			}
			f=!f;
		}
	}
	printf("%ld\n", n1<n2?n1:n2);
}


Measured memory_bytes: 512
N,K = list(map(int,input().split()))

ans = 0.0
for n in range(1,N+1):
	judge = 0
	k_min = 0
	while judge == 0:
		if n*(2**k_min) >= K:
			judge = 1
		else:
			k_min += 1
	ans += 1.0/(N*(2**k_min))
print(ans)


Measured memory_bytes: 2940
//Author:xht37
#include <bits/stdc++.h>

#define ui unsigned int
#define ll long long
#define ul unsigned ll
#define ld long double

#define pi pair <int, int>
#define fi first
#define se second
#define mp make_pair

#define ls (p << 1)
#define rs (ls | 1)
#define md ((t[p].l + t[p].r) >> 1)

#define vi vector <int>
#define pb push_back
#define pq priority_queue

#define dbg(x) cerr << #x" = " << (x) << endl
#define debug(...) fprintf(stderr, __VA_ARGS__)

#define fl(x) freopen(x".in", "r", stdin), freopen(x".out", "w", stdout)

using namespace std;

namespace io {
	const int SI = 1 << 21 | 1;
	char IB[SI], *IS, *IT, OB[SI], *OS = OB, *OT = OS + SI - 1, c, ch[100];
	int f, t;
	#define gc() (IS == IT ? (IT = (IS = IB) + fread(IB, 1, SI, stdin), IS == IT ? EOF : *IS++) : *IS++)
	inline void flush() {
		fwrite(OB, 1, OS - OB, stdout), OS = OB;
	}
	inline void pc(char x) {
		*OS++ = x;
		if (OS == OT) flush();
	}

	template <class I>
	inline void rd(I &x) {
		for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;
		for (x = 0; c >= '0' && c <= '9'; x = (x << 3) + (x << 1) + (c & 15), c = gc());
		x *= f;
	}
	template <class I>
	inline void rd(I &x, I &y) {
		rd(x), rd(y);
	}
	template <class I>
	inline void rd(I &x, I &y, I &z) {
		rd(x), rd(y), rd(z);
	}
	template <class I>
	inline void rda(I *a, int n) {
		for (int i = 1; i <= n; i++) rd(a[i]);
	}
	inline void rdc(char &c) {
		for (c = gc(); c < 33 || c > 126; c = gc());
	}
	inline void rds(char *s, int &n) {
		for (c = gc(); c < 33 || c > 126; c = gc());
		for (n = 0; c >= 33 && c <= 126; s[++n] = c, c = gc());
	}
	inline void rds(string &s) {
		for (c = gc(); c < 33 || c > 126; c = gc());
		for (s.clear(); c >= 33 && c <= 126; s.pb(c), c = gc());
	}

	template <class I>
	inline void print(I x, char k = '\n') {
		if (!x) pc('0');
		if (x < 0) pc('-'), x = -x;
		while (x) ch[++t] = x % 10 + '0', x /= 10;
		while (t) pc(ch[t--]);
		pc(k);
	}
	template <class I>
	inline void print(I x, I y) {
		print(x, ' '), print(y);
	}
	template <class I>
	inline void print(I x, I y, I z) {
		print(x, ' '), print(y, ' '), print(z);
	}
	template <class I>
	inline void printa(I *a, int n) {
		for (int i = 1; i <= n; i++) print(a[i], " \n"[i==n]);
	}
	inline void printc(char c) {
		pc(c);
	}
	inline void prints(char *s, int n) {
		for (int i = 1; i <= n; i++) pc(s[i]);
		pc('\n');
	}
	inline void prints(string s) {
		int n = s.length();
		while (t < n) pc(s[t++]);
		pc('\n'), t = 0;
	}
	struct Flush {
		~Flush() {
			flush();
		}
	} flusher;
}
using io::rd;
using io::rda;
using io::rdc;
using io::rds;
using io::print;
using io::printa;
using io::printc;
using io::prints;

const int N = 1e5 + 7;
int n;
ll a[N], l = 2, r = 2;

int main() {
	rd(n), rda(a, n);
	for (int i = n; i; i--) {
		l = ((l - 1) / a[i] + 1) * a[i], r = r / a[i] * a[i];
		if (l > r) return print(-1), 0;
		r += a[i] - 1;
	}
	print(l, r);
	return 0;
}

Measured memory_bytes: 5428
#include <bits/stdc++.h>
using namespace std;
int main(){
  int N;
  cin >> N;
  string S;
  cin >> S;
  int c = 0;
  for (int i = 0; i < N; i++){
    if (S[i] == 'R'){
      c++;
    } else {
      c--;
    }
  }
  cout << (c > 0 ? "Yes" : "No");
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
	
	static List<P> data;
	
	public static void main(String[] args) {
		Scanner in=new Scanner(System.in);
		while(true) {
			int n=in.nextInt();
			if(n==0)break;
			if(n==1) {
				int one=in.nextInt();
				System.out.println(one);
				continue;
			}
			
			data=new ArrayList<>();
			for(int i=0;i<n;i++) {
				P p=new P();
				String str=in.next();
				p.c=str.toCharArray();
				data.add(p);
			}
			System.out.println(calc(1,1,data.get(0).c[0]));
		}
	}
	
	static int calc(int level,int b,char op) {
		Stack<Integer> stk=new Stack<>();
		int res;
		
		for(int i=b;i<data.size();i++) {
			
			char c[]=data.get(i).c;
			if(c.length<=level)break;
			//System.out.println("Level="+level+" b="+i+" data="+c[level]);
			
			if(c[level]=='*' || c[level]=='+') {
				//System.out.println("Level="+level+":"+c[level]);
				stk.push(calc(level+1,i+1,c[level]));
			}
			else if(c[level]>='0' && c[level]<='9')stk.push(c[level]-48);
		}
		
		if(op=='*') {
			res=1;
			while(!stk.isEmpty()) res*=stk.pop();
		}
		else {
			res=0;
			while(!stk.isEmpty())res+=stk.pop();
		}
		
		return res;
	}

}

class P{
	char c[];
}





Measured memory_bytes: 31804
// tsukasa_diary's programing contest code template
#include <bits/stdc++.h>
using namespace std;
// define
#define for_(i,a,b) for(int i=a;i<b;++i)
#define for_rev(i,a,b) for(int i=a;i>=b;--i)
#define allof(a) a.begin(),a.end()
#define minit(a,b) memset(a,b,sizeof(a))
#define size_of(a) (int)a.size()
// typedef
typedef long long lint;
typedef double Double;
typedef pair<int, int> pii;
//
typedef vector< int > Array;
typedef vector< Array > Matrix;
typedef vector< Double > DArray;
typedef vector< DArray > DMatrix;
typedef vector< string > SArray;
typedef vector< pii > PArray;
// popcount
inline int POPCNT(int _x) { return __builtin_popcount(_x); }
inline int POPCNT(lint _x) { return __builtin_popcountll(_x); }
// inf
const int iINF = 1L << 30;
const lint lINF = 1LL << 60;
// eps
Double EPS = 1e-9;
// in range
inline bool in_range(int _v, int _mx, int _mi) { return _mi <= _v && _v < _mx; }
inline bool in_range(Double _v, Double _mi, Double _mx) { return -EPS < _v - _mi && _v - _mx < EPS; }
inline bool in_range(int _x, int _y, int _W, int _H) { return 0 <= _x && _x < _W && 0 <= _y && _y < _H; }
// neighbor clockwise
const int DX[4] = {0,1,0,-1}, DY[4] = {-1,0,1,0};
const int DX_[8] = {0,1,1,1,0,-1,-1,-1}, DY_[8] = {-1,-1,0,1,1,1,0,-1};
// variable update
inline void modAdd(int& _a, int _b, int _m) { _a = (_a + _b) % _m; }
inline void modAdd(lint& _a, lint _b, lint _m) { _a = (_a + _b) % _m; }
inline void minUpdate(int& _a, int _b) { _a = min(_a, _b); }
inline void minUpdate(lint& _a, lint _b) { _a = min(_a, _b); }
inline void maxUpdate(int& _a, int _b) { _a = max(_a, _b); }
inline void maxUpdate(lint& _a, lint _b) { _a = max(_a, _b); }

int n, m;
map< char, char > table;

void solve() {
	for_(i,0,m) {
		char c; cin >> c;
		
		if (table.find(c) != table.end()) c = table[c];
		
		cout << c;
	}
	
	cout << endl;
}

int main() {
	while (cin >> n, n) {
		table.clear();
		
		for_(i,0,n) {
			char a, b; cin >> a >> b;
			table[a] = b;
		}
		
		cin >> m;
		
		solve();
	}
	return 0;
}

Measured memory_bytes: 1188
a, b = map(int, input().split())
if a == 1 or b == 1:
    if a == b:
        print('Draw')
    elif a == 1:
        print('Alice')
    elif b == 1:
        print('Bob')
else:
    if a == b:
        print('Draw')
    elif a > b:
        print('Alice')
    elif b > a:
       	print('Bob')

Measured memory_bytes: 3060
n,m=map(int,input().split())
l=list(map(int,input().split()))
l1=[]
for i in range(n-m+1):
  if l[i]>=0:
    l1.append(l[i+m-1])
  elif l[i]<=0<=l[i+m-1]:
    l1.append(l[i+m-1]-l[i]+min(abs(l[i]),abs(l[i+m-1])))
  else:
    l1.append(abs(l[i]))
print(min(l1)) 


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

int main()
{
    char buffer[256];
    char result[256][256];
    int count=0;
    unsigned int i, j;
    
    while(1)
    {
        int m, h;
        char deck[256];
        char shuffled[256];
        int length;
        int index;
        
        fgets(buffer, 256, stdin);
        sscanf(buffer, "%s", deck);
        int ret = strcmp(deck, "-");
        if(0==ret) break;
        //printf("debug %s %s\n", deck, "-");
        length=strlen(deck);
        
        fgets(buffer, 256, stdin);
        sscanf(buffer, "%d", &m);
        
        index=0;
        for(i=0;i<m;i++)
        {
            fgets(buffer, 256, stdin);
            sscanf(buffer, "%d", &h);
            index+=h;
        }
        index = index % length;
        strcpy(shuffled, deck);
        if(index!=0)
        {
            memcpy(shuffled, &deck[index], (length-index)*sizeof(char));
            
            //printf("%s\n", shuffled);
            memcpy(&shuffled[length-index], &deck[0], index*sizeof(char));
            //printf("%s\n", shuffled);
        }
        strcpy(result[count++], shuffled);
        
    }
    
    for(i=0;i<count;i++)
    {
        printf("%s\n", result[i]);
    }
    
    return(0);
}


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

const int INF = 1e9;
const int MOD = 1e9 + 7;

int main() {

    int N;
    string S;
    cin >> N >> S;

    int ans = 0;
    for (int i = 0; i <= 1000; i++) {
        int d[3] = {i / 100, i % 100 / 10, i % 10};
        int now = 0;
        rep(j, N) {
            if (S[j] - '0' == d[now])
                now++;
            if (now == 3) {
                ans++;
                break;
            }
        }
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>
using bint = boost::multiprecision::cpp_int;

int main()
{
    int H, W;
    std::cin >> H >> W;
    std::vector<std::vector<bool>> area(H, std::vector<bool>(W));
    for (int i = 0; i < H; i++) {
        std::string s;
        std::cin >> s;
        for (int j = 0; j < W; j++) {
            if (s.at(j) == '.') {
                area.at(i).at(j) = true;
            } else if (s.at(j) == '#') {
                area.at(i).at(j) = false;
            }
        }
    }
    std::vector<int> sums{};
    std::vector<int> last_continue_column(W, 0);
    for (int i = 0; i < H; i++) {
        int last_continue_row = 0;
        for (int j = 0; j < W; j++) {
            if (not area[i][j]) {
                last_continue_row = 0;
                last_continue_column[j] = 0;
                continue;
            }
            int sum_row;
            if (last_continue_row != 0) {
                sum_row = last_continue_row;
            } else {
                int idx = 0;
                while (area[i][j + idx]) {
                    idx++;
                    if (j + idx == W) {
                        break;
                    }
                }
                last_continue_row = idx;
                sum_row = last_continue_row;
            }
            int sum_column;
            if (last_continue_column[j] != 0) {
                sum_column = last_continue_column[j];
            } else {
                int idx = 0;
                while (area[i + idx][j]) {
                    idx++;
                    if (i + idx == H) {
                        break;
                    }
                }
                last_continue_column[j] = idx;
                sum_column = last_continue_column[j];
            }
            sums.emplace_back(sum_row + sum_column - 1);
        }
    }
    std::cout << *std::max_element(sums.begin(), sums.end()) << std::endl;
    return 0;
}

Measured memory_bytes: 19180
import java.util.Scanner;
import java.util.stream.IntStream;

public class Main{
	static IntStream REPS(int v){return IntStream.range(0,v);}
	static IntStream REPS(int l,int r){return IntStream.rangeClosed(l,r);}
	static IntStream INS(int n) {return REPS(n).map(i->getInt());}
	static Scanner s=new Scanner(System.in);
	static int getInt(){return Integer.parseInt(s.next());}

	public static void main(String[]$){
		int a=getInt(),b=getInt();
		for(int i=getInt();i>0;--i) {
			int A=getInt(),B=getInt();
			if(Math.min(b,B)-Math.max(a,A)>0) {
				System.out.println(1);
				return;
			}
		}
		System.out.println(0);
	}
}

Measured memory_bytes: 26304
#include<stdio.h>
#include<math.h>
int main()
{
    long long int i,n,s=0,ans=0,a[200009],m=1e9+7;
    scanf("%lld",&n);
    for(i=0;i<n;i++)
    {
        scanf("%lld",&a[i]);
        ans+=s*a[i];
        ans%=m;
        s+=a[i];
        s%=m;
    }
    printf("%lld",ans);
}

Measured memory_bytes: 3260
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
    int N;
    cin >> N;
    long double ans = 0;
    for(int i = 0; i < N; i++){
        long double x;
        string u;
        cin >> x >> u;
        if(u == "JPY")
            ans += x;
        else
            ans += (380000*x);
    }
    cout << ans << "\n";
    return 0;
}


Measured memory_bytes: 256
package main

import (
	"fmt"
)

func main() {
	var S string
	fmt.Scan(&S)

	ans := func() int {
		switch S {
		case "SUN":
			return 7
		case "MON":
			return 6
		case "TUE":
			return 5
		case "WED":
			return 4
		case "THU":
			return 3
		case "FRI":
			return 2
		case "SAT":
			return 1
		}
		return 0
	}()

	fmt.Println(ans)
}


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


int N;
vector<int> E[101];
bool V[101];
int ans;

void dfs(int v, int lvl) {
  if(V[v]) {
    ans = max(ans, lvl);
  } else {
    V[v] = true;
    for(int i = 0; i < E[v].size(); i++) {
      dfs(E[v][i], lvl + 1);
    }
    V[v] = false;
  }
}

int main(void) {
  while(1) {
    cin >> N;
    if(N == 0) break;
    REP(i, 0, N) {
      int a, b;
      cin >> a >> b;
      E[a].push_back(b);
      E[b].push_back(a);
    }

    ans = 0;
    REP(i, 1, 101) {
      dfs(i, 0);
    }

    cout << ans << endl;

    REP(i, 1, 101) {
      E[i].clear();
    }
  }

  return 0;
}

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

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)    FOR (i,0,n)
#define ALL(f,x,...) ([&](decltype((x)) ALL) {                          \
            return (f)(begin(ALL), end(ALL), ## __VA_ARGS__); })(x)

using namespace std;

using ll = int64_t;

template<class T> void gc(T &x)
{
    char c;
    int s = 0;
    x = 0;

    c = getchar_unlocked();

    if (c == '-') s = 1;
    else if ('0' <= c && c <= '9')  x = c - '0';

    while (true)
    {
        c = getchar_unlocked();

        if (c < '0' || '9' < c) break;
        x = x * 10 + (c - '0');
    }

    if (s) x = -x;
}

int main()
{
    int N;

    gc(N);

    vector<int> A(N);

    REP (i, N) gc(A[i]);

    // a + b - (a xor b) = 2 * (a and b)
    // a + b と a xor b が等しいならば
    // a and b は ゼロ

    ll ans = 0;
    ll idx = 0;
    ll last;
    ll tmp = A[0];

    REP (i, N)
    {
        // 最も小さい値
        // 1回も論理積 (&) がゼロにならない場合
        last = i;

        ans += (idx + 1) - i;

        FOR (j, idx + 1, N)
        {
            if (!(tmp & A[j]))
            {
                // 論理積 (&) がゼロの場合
                ans++;
                last = j;
                tmp += A[j];
            }
            else break;
        }

        tmp -= A[i];

        // last が idx より小さくなる場合がある
        idx = max(idx, last);

    }

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


Measured memory_bytes: 1024