akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>


using namespace std;

int main(){
    int N;
    string ans = "YES";
    cin >> N;
    vector<int> A(N);
    
    for(int i = 0;i < N;i++){
        cin >> A.at(i);
    }

    sort(A.begin(),A.end());
    
    for(int j = 0;j < N-1;j++){
        if(A.at(j) == A.at(j+1)){
            ans = "NO";
            break;
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
int main()
{
    ll n,a,j,i,k;
    cin>>n;
    ll ar1[5],mn=999999999999999999;
    for(i=0; i<5; i++)
    {
        cin>>ar1[i];
        mn=min(mn,ar1[i]);
    }
    k=n/mn;
    if(k*mn!=n)
        k++;
    cout<<k+4<<endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ll long long
#define fast ios_base::sync_with_stdio(false); cin.tie(0);cout.tie(0);
const ll mod=998244353;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> data_struct;

bool perfect(int s)
{
	int k=sqrt(s);
	return k*k == s;
}

int main()
{
	// cout<<perfect(4);
	int n;
	cin>>n;
	n=n%10;
	if(n==3)
		cout<<"bon";
	else if(n==0||n==1||n==6||n==8)
		cout<<"pon";
	else
		cout<<"hon";
}

Measured memory_bytes: 3680
#include<bits/stdc++.h>
using namespace std;
inline void read(int &x)
{
	x=0;
	static int p;p=1;
	static char c;c=getchar();
	while(!isdigit(c)){if(c=='-')p=-1;c=getchar();}
	while(isdigit(c)) {x=(x<<1)+(x<<3)+(c^'0');c=getchar();}
	x*=p;
}
char s[30];
int cnt[30];
int vis[30];
int main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	cin>>(s+1);
	int n=strlen(s+1);
	for(int i=1;i<=n;i++)
	{
		cnt[s[i]-'a'+1]++;
		if(cnt[s[i]-'a'+1]>1)return cout<<-1<<endl,0;
	}
	if(n==26)
	{
		int last=n;
		char now=s[n];
		while(1)
		{
			if(s[last]+1<='z')s[last]++;
			else last--,cnt[now-'a'+1]=0,now=s[last];
			if(!cnt[s[last]-'a'+1])
			{
				for(int i=1;i<=last;i++)
					cout<<s[i];
				cout<<endl;
				return 0;
			}
			if(last==0)return cout<<-1<<endl,0;
		}
	}
	else 
	printf("%s",s+1);
	for(int i=1;i<=26;i++)
		if(!cnt[i])return printf("%c",i+'a'-1),0;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const ll mod = 1e9 + 7;

int main(){
	int N; cin >> N;
	ll A[N];
	for(int i=0; i<N; i++) cin >> A[i];
	ll ans = 0;
	for(int i=0; i<62; i++){
		ll p = 0, q = 0;
		for(int j=0; j<N; j++){
			if(A[j]>>i & 1) p++;
			else q++;
		}
		ll now = p*q%mod;
		for(int j=0; j<i; j++){
			now = now * 2 % mod;
		}
		ans += now;
		ans %= mod;
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 2688
s = input()[::-1]
t = input()[::-1]
ok = False
for i in range(0,len(s)-len(t)+1):
    if s[i] == t[0] or s[i] == '?':
        for j in range(len(t)):
            if s[i+j] != t[j] and s[i+j] != '?':
                break
        else:
            ok = True
            s = s[:i] + t + s[i+len(t):]
            break
if ok:
    ans = ''
    for i in s[::-1]:
        ans += 'a' if i == '?' else i
else:
    ans = 'UNRESTORABLE'
print(ans)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define forn for(int i=1;i<=n;i++)
#define form for(int j=0;j<m;j++)
#define pb push_back
#define mp make_pair
#define sc second
#define f first
#define kek cout<<"\n"
#define all(v)        ((v).begin()), ((v).end())
#define pob pop_back()
const ll MOD=1e9+7;
const ll INF=1e8;
int main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  // freopen("input.txt", "r", stdin);
  // freopen("output.txt", "w", stdout);
      
     int n;
cin>>n;
set<int> s;
int x;
forn 
{
          cin>>x;
          s.insert(x);
}
if(s.size()==n) cout<<"YES";
else cout<<"NO";



      
      
      
      
      
      
      return 0;
}

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

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

Measured memory_bytes: 256
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
typedef long long int ll;
#define mod 1000000007
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define m0(x) memset(x,0,sizeof(x))

int main(void){
	int n,T,i;
	scanf("%d %d",&n,&T);
	int c[n],t[n];
	int min=1000,flag=0;
	rep(i,n){
		scanf("%d %d",&c[i],&t[i]);
		if(t[i]<=T){
			flag++;
			if(c[i]<min) min=c[i];
		}
	}
	if(flag==0) printf("TLE");
	else printf("%d",min);
	return 0;
}

Measured memory_bytes: 128
import sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = 10**20
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()

def resolve():
    S = SS()

    ans = 0
    stk = []
    for i in S:
        if stk and stk[-1] != i:
            stk.pop()
            ans += 2
        else:
            stk.append(i)

    print(ans)

if __name__ == '__main__':
    resolve()


Measured memory_bytes: 9688
#include <algorithm>
#include <boost/multiprecision/cpp_int.hpp>
#include <cmath>
#include <deque>
#include <iostream>
#include <queue>
#include <string>
#include <vector>

using namespace std;
using ll = long long;
namespace mp = boost::multiprecision;
using mpint = mp::cpp_int;  // 多倍長整数（任意精度）

/*
 * 定数
 */
const long double PI = (acos(-1));
const long double EPS = 1e-10;
const long long INF = 1e18;

/*
 * データ変換 
 */
/* char -> int */
int ctoi(char c) { return (int)(c - '0'); }

/*
 * 数学的な計算
 */
/* 階乗 */
int factorial(int n) {
  int ret = 1;
  for (int i = 1; i < n + 1; ++i) {
    ret = ret * i;
  }
  return ret;
}

/* 最大公約数 */
template <typename T>
T gcd(T x, T y) { return x % y == 0 ? y : gcd(y, x % y); }

/* 最小公倍数 */
template <typename T>
T lcm(T a, T b) { return a * b / gcd(a, b); }

/* n個の整数の最小公倍数 */
template <typename T>
T lcm_n(vector<T> &numbers) {
  T l;
  l = numbers[0];
  for (int i = 1; i < numbers.size(); ++i) {
    l = lcm(l, numbers[i]);
  }
  return l;
}

/*
 * DP向け
 */
template <class T>
bool chmax(T &a, const T &b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
template <class T>
bool chmin(T &a, const T &b) {
  if (b < a) {
    a = b;
    return 1;
  }
  return 0;
}

int main() {
  ll a, b, c, k;

  cin >> a >> b >> c >> k;

  ll ans = 0;

  for (ll i = 0; i < k; ++i) {
    if (a > 0) {
      ++ans;
      --a;
      continue;
    }
    if (b > 0) {
      --b;
      continue;
    }
    --ans;
  }

  cout << ans << endl;

  return 0;
}


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

using namespace std;
using ll = long long;

int main() {
	int H, W;
	cin >> H >> W;
	vector<vector<string>> s(H, vector<string>(W));
	for (int i = 0; i < H; ++i) {
		for (int j = 0; j < W; ++j) { cin >> s[i][j]; }
	}

	for (int i = 0; i < H; ++i) {
		for (int j = 0; j < W; ++j) {
			if (s[i][j] == "snuke") {
				cout << (char)('A' + j) << i + 1 << endl;
				return 0;
			}
		}
	}

	return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int main(void){
    int m,f,r;
    while(1){
        scanf("%d %d %d\n",&m,&f,&r);
        if(m==-1 && f==-1 && r==-1){
            break;
        }else if(m==-1 || f==-1){
            printf("F\n");
        }else if(m+f >= 80){
            printf("A\n");
        }else if(m+f>=65){
            printf("B\n");
        }else if(m+f>=50){
            printf("C\n");
        }else if(m+f>=30){
            if(r>=50){
                printf("C\n");
            }else{
                printf("D\n");
            }
        }else{
            printf("F\n");
        }
    }
    return 0; /*0?????????*/
}

Measured memory_bytes: 588
#include<iostream>
using namespace std;
int main(){
    int W,H,x,y,r;
    cin >> W>>H>>x>>y>>r;

    if(x<W && y<H){
        if(x+r<=W && x-r>=0 && y+r<=H && y-r>=0){
            cout << "Yes\n";
        }
        else{
            cout << "No\n";
        }
    }
    else{
        cout << "No\n";
    }
}

Measured memory_bytes: 3060
from itertools import permutations

def main():
    n, m, r = map(int, input().strip().split())
    rs = list(map(int, input().strip().split()))
    dist = [[10 ** 10 for _ in range(n)] for _ in range(n)]
    for i in range(n):
        dist[i][i] = 0
    for _ in range(m):
        a, b, c = map(int, input().strip().split())
        dist[a-1][b-1] = c
        dist[b-1][a-1] = c
    for k in range(n):
        for i in range(n):
            for j in range(n):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    ans = 10 ** 10
    for trs in permutations(rs):
        tans = 0
        for i in range(len(trs) - 1):
            tans += dist[trs[i]-1][trs[i+1]-1]
        ans = min(ans, tans)
    print(ans)

if __name__ == '__main__':
    main()

Measured memory_bytes: 49496
import copy
# a, b = map(int,input().split())

# n,k = map(int,input().split())
# n = int(input())
# b_l = list(map(int,input().split()))
s = input()

if s == 'Sunny':
        print('Cloudy')
elif s == 'Cloudy':
        print('Rainy')
elif s == 'Rainy':
        print('Sunny')

Measured memory_bytes: 3444
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <set>
#include <cstring>
#include <string>
#include <cmath>
#include <functional>
#include <queue>
#include <map>
using namespace std;

typedef long long ll;
const int M = 1e9 + 7;
const int N = 2e5 + 10;
const int MAX = 1e9 + 1;
//int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};

int n;

int main() {
    int i, j;
    string s;
    cin >> s;
    if (s.size() >= 4 && s[0] == 'Y' && s[1] == 'A' && s[2] == 'K' && s[3] == 'I')
        cout << "Yes\n";
    else
        cout << "No\n";
    return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <cassert>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <vector>

#include <limits.h>

using namespace std;

typedef long long ll;

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;
}

const int INF = INT_MAX / 2;

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

    int ans = 0;
    int min_diff = INF;

    vector<int> vs = {111, 222, 333, 444, 555, 666, 777, 888, 999};
    for (auto v : vs) {
        if (v - N >= 0 && v - N < min_diff) {
            ans = v;
            min_diff = v - N;
        }
    }

    cout << ans << endl;

    return 0;
}


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

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t,n,a,b;
    t = 1;
    while(t--) {
     cin >> n >> a >> b;
     n = n - a;
     cout << n % b << endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<list>
#include<map>
#include<algorithm>

using namespace std;

int main()
{
    int n, k;
    cin >> n >> k;

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

    long long count_min = 0;
    for (int i = 0; i < n - k + 1; i++) {
        long long count = 0;
        int start = x[i];
        int end = x[i + k - 1];
        if (end < 0) {
            count = 0 - start;
        } else if (start < 0 && 0 <= end) {
            int count1 = 0 - start + (end - start);
            int count2 = end + (end - start);
            count = min(count1, count2);
        } else {
            count = end;
        }
        if (i == 0) {
            count_min = count;
        }
        count_min = min(count_min, count);
    }

    cout << count_min << endl;

    return 0;
}


Measured memory_bytes: 640
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
class Program
{
    static void Main(string[] args)
    {
            // 入力
            string[] sS = System.Console.ReadLine().Trim().Split(' ');
            int iN = int.Parse(sS[0]);
            int iA = int.Parse(sS[1]);
            int iB = int.Parse(sS[2]);

            System.Diagnostics.Stopwatch sw = new System.Diagnostics.Stopwatch();
            sw.Start();

            // 解析
            List<int> lstA = new List<int>();                                           // A 購読情報
            List<int> lstB = new List<int>();                                           // B 購読情報
            for (int i = 0; i < iN; i++)
            {
                iA -= 1; if (iA >= 0) { lstA.Add(1); } else { lstA.Add(0); }            // A 購読1 なし0
                iB -= 1; if (iB >= 0) { lstB.Add(1); } else { lstB.Add(0); }            // B 購読1 なし0
            }
            int iC = 0;                                                                 // AB購読最大
            int iD = 0;                                                                 // AB購読最小
            for (int i = 0; i < iN; i++) { if (lstA[i] + lstB[i] == 2) { iC += 1; } }
            lstB.Sort();
            for (int i = 0; i < iN; i++) { if (lstA[i] + lstB[i] == 2) { iD += 1; } }

            // 出力
            System.Console.WriteLine("{0} {1}", iC.ToString().Trim(), iD.ToString().Trim());

            sw.Stop();
#if DEBUG
            Console.WriteLine();
            Console.WriteLine("{0}", sw.Elapsed.ToString());
            Console.WriteLine("続行するには何かキーを押してください．．．");
            Console.ReadKey();
#endif
    }

}


Measured memory_bytes: 13268
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define _GLIBCXX_DEBUG
#define rep(i, c) for (int i = 0; i < (int)c; i++)
#define debug(x) cout << #x << " = " << x << endl
#define print(x) cout << x << endl;
const ll MOD = 1000000007;

int main()
{
    char a;
    cin >> a;
    if (a >= 'A' && a <= 'Z')
        cout << "A" << endl;
    else if (a >= 'a' && a <= 'z')
        cout << "a" << endl;
}


Measured memory_bytes: 3632
#include <iostream>
#include <vector>
#include <bitset>
#include <algorithm>
#include <utility>
#include <map>
#include <functional>
#include <initializer_list>
#include <string>
#include <cmath>
#include <iomanip>
#include <queue>
#include <math.h>
using namespace std;
typedef long long ll;


int main(){
    string A, B;
    cin >> A >> B;
    string ans = "Yes";
    for(int i=0; i<A.size(); i++){
        if(A[i] != B[i]){
            ans = "No";
            }
        }
    if(B.size() != A.size()+1) ans = "No";
    cout << ans;

}

Measured memory_bytes: 3596
use std::cmp::min;

fn read_line<T: std::str::FromStr>() -> T {
  let mut s = String::new();
  std::io::stdin().read_line(&mut s).ok();
  s.trim().parse::<T>().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
  read_line::<String>()
    .split_whitespace()
    .map(|e| e.parse().ok().unwrap())
    .collect()
}

fn main() {
  let x = read_vec::<i64>();
  let a = x[0];
  let b = x[1];
  let n = x[2];

  let x = min(b - 1, n);
  let ans = a * x / b;
  println!("{:?}", ans)
}

Measured memory_bytes: 2076
//
// ツリーの直径を求める (DFS 2 回行う)
//
// verified:
//   AGC 033 C - Removing Coins
//     https://atcoder.jp/contests/agc033/tasks/agc033_c
//


#include <iostream>
#include <vector>
using namespace std;


using Graph = vector<vector<int> >;
struct Diameter {
    vector<int> prev;
    pair<int,int> DiameterDFS(const Graph &G, int v, int p) {
        pair<int,int> res(v, 0);
        for (int i = 0; i < (int)G[v].size(); ++i) {
            if (G[v][i] == p) continue;
            pair<int,int> tmp = DiameterDFS(G, G[v][i], v);
            tmp.second++;
            if (tmp.second > res.second) res = tmp, prev[G[v][i]] = v;
        }
        return res;
    }

    vector<int> solve(const vector<vector<int> > &G) {
        prev.assign((int)G.size(), -1);
        pair<int,int> leaf = DiameterDFS(G, 0, -1);
        prev.assign((int)G.size(), -1);
        pair<int,int> t = DiameterDFS(G, leaf.first, -1);
        vector<int> res;
        int cur = t.first;
        while (cur != -1) res.push_back(cur), cur = prev[cur];
        return res;
    }
};


using Graph = vector<vector<int> >;
int N;
Graph G;

int main() {
    cin >> N;
    G.assign(N, vector<int>());
    for (int i = 0; i < N-1; ++i) {
        int a, b; cin >> a >> b; --a, --b;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    Diameter di;
    auto res = di.solve(G);    
    int V = res.size();
    if (V % 3 == 2) cout << "Second" << endl;
    else cout << "First" << endl;
}


Measured memory_bytes: 21500
import java.io.*;
import java.util.*;
import java.math.BigInteger;

public class Main {

    static class FastScanner {
        BufferedReader br;
        StringTokenizer st;

        public FastScanner() {
            try {
                br = new BufferedReader(new InputStreamReader(System.in));
                st = new StringTokenizer(br.readLine());
            } catch (Exception e){e.printStackTrace();}
        }

        public String next() {
            if (st.hasMoreTokens()) return st.nextToken();
            try {st = new StringTokenizer(br.readLine());}
            catch (Exception e) {e.printStackTrace();}
            return st.nextToken();
        }

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

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

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

        public String nextLine() {
            String line = "";
            if(st.hasMoreTokens()) line = st.nextToken();
            else try {return br.readLine();}catch(IOException e){e.printStackTrace();}
            while(st.hasMoreTokens()) line += " "+st.nextToken();
            return line;
        }
    }
    public static void main(String[] args) {
        FastScanner sc = new FastScanner();
        PrintWriter pw = new PrintWriter(System.out);
        
        int p = sc.nextInt(), q = sc.nextInt(), r = sc.nextInt();

        pw.println(Math.min(p + q, Math.min(q + r, p + r)));

        pw.close();
    }
}


Measured memory_bytes: 21332
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>
#include <bits/stdc++.h>
using namespace std;

const double TL = 1.5 * CLOCKS_PER_SEC;
mt19937 rng((unsigned int) chrono::steady_clock::now().time_since_epoch().count());
#define clr(x, y) memset(x, y, sizeof(x))
#define forn(i, n) for (int i = 0; i < n; i++)
#define LL long long

const int inf = 1e9;

LL n, a, b;
int main() {
  //auto start_clock = clock();
#ifdef LOCAL
  freopen("in", "r", stdin);
#endif
  cin >> n >> a >> b;

  LL m = n / (a + b);
  LL ans = m * a, r = n - m * (a + b);
  if(a <= r) ans += a;
  else ans += r;
  cout << ans << endl;
  return 0;
}

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

int main() {
    long long N;
    cin >> N;
    vector<long long> A(N);
    for (long long i = 0; i < N; i++) {
        cin >> A[i];
    }
    long long left = 0;
    long long right = accumulate(A.begin(), A.end(), 0LL);
    long long minAbs = right;
    for (long long i = 0; i < N; i++) {
        left += A[i];
        right -= A[i];
        minAbs = min(minAbs, abs(right - left));
    }
    cout << minAbs << endl;

    return 0;
}

Measured memory_bytes: 1920
# -*- coding: utf-8 -*-
"""
Created on Sun Apr 12 04:56:52 2020

@author: Kanaru Sato
"""

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

sum = 0
sumlist = [0]
for i in range(n):
    sum += p[i]
    sumlist.append(sum)


Max = -100000
for i in range(n-k+1):
    e = sumlist[i+k]-sumlist[i]
    if Max < e:
        Max = e

print((Max+k)/2)

Measured memory_bytes: 25172
#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <fstream>
#include <set>
#include <utility>
#include <algorithm>
#include <queue>
#include <stack>
#include <deque>
#include <numeric>
#include <sstream>
#include <list>
#include <map>
#include <stdlib.h>
#include <time.h>

#define rep(i,p,n) for(int i=(int)p;i<(int)n;i++)
#define repp(i,p,n) for(int i=(int)p;i>=(int)n;i--)
#define Sort(x) sort(x.begin(),x.end());
#define ll long long
#define INF 2000000000

using namespace std;

int main() {
	string s,ss;
	cin >> s >> ss;
	rep(i, 0, 3) {
		if (s[i] != ss[3 - i - 1]) {
			cout << "NO" << endl;
			return 0;
		}
	}
	cout << "YES" << endl;
	
	return 0;
}



Measured memory_bytes: 256
n, m = map(int, input().split())
m_list = [0] * m
for i in range(n):
  l = list(map(int, input().split()))
  for i in range(1, len(l)):
    m_list[l[i] - 1] += 1
count = 0
for num in m_list:
  if num == n:
    count += 1
print(count)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rrep(i, n) for (int i = 1; i <= (n); ++i)
#define drep(i, n) for (int i = (n)-1; i >= 0; --i)
#define srep(i, s, t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(), a.end()
#define rrng(a) a.rbegin(), a.rend()
#define maxs(x, y) (x = max(x, y))
#define mins(x, y) (x = min(x, y))
#define limit(x, l, r) max(l, min(x, r))
#define lims(x, l, r) (x = max(l, min(x, r)))
#define isin(x, l, r) ((l) <= (x) && (x) < (r))
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcountll
#define uni(x) x.erase(unique(rng(x)), x.end())
#define show(x) cout << #x << " = " << x << endl;
#define PQ(T) priority_queue<T, v(T), greater<T>>
#define bn(x) ((1 << x) - 1)
#define dup(x, y) (((x) + (y)-1) / (y))
#define newline puts("")
#define v(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
typedef long long int ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int, int> P;
typedef tuple<int, int, int> T;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
typedef vector<T> vt;

const int mod = 1000000007;
struct mint {
  ll x; // typedef long long ll;
  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;
  }

  // for prime mod
  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;
  }
};


int main() {
  int n,k;
  cin>>n>>k;
  vi a(n);
  rep(i,n){
    cin >> a[i];
  }
  mint x = 0;
  rep(i,n){
    rep(j,i+1){
      if(a[j] > a[i]){
        x+=1;
      }
    }
  }
  mint y = 0;
  rep(i,n){
    rep(j,i+1){
      if(a[j] < a[i]){
        y+=1;
      }
    }
  }  
  mint ans = 0;
  ans += x*k*(k+1)/2;
  ans += y*k*(k-1)/2;
  cout<<ans.x<<endl;
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define _ ios_base::sync_with_stdio(0);cin.tie(0);
#define REP(i,n) for(int i=0;i<(int)(n);i++)

using namespace std;
const string yes="Yes";
const string no="No";

int n,m;
vector<int> es[100010];

bool checked[100010];
queue<int> que;
int bfs(int s,int t){
  int paths=0;
  REP(i,n)checked[i]=false;
  que.push(s);
  checked[s]=true;
  while(!que.empty()){
    int index=que.front();
    que.pop();
    for(int e:es[index]){
      if(e==t){
	paths++;
	continue;
      }
      if(!checked[e]){
	que.push(e);
	checked[e]=true;
      }
    }
  }
  return paths;
}


string solve(){
  bool hasSix=false;
  int fourCount=0;
  REP(i,n){
    if(es[i].size()%2!=0) return no;
    if(es[i].size()==4) fourCount++;
    if(es[i].size()>=6) hasSix=true;
  }
  if(hasSix) return yes;
  if(fourCount>=3) return yes;
  if(fourCount<=1) return no;

  int s[2]={-1,-1};
  REP(i,n){
    if(es[i].size()==4){
      if(s[0]==-1)
	s[0]=i;
      else
	s[1]=i;
    }
  }
  int paths=bfs(s[0],s[1]);
  if(paths==2) return yes;
  return no;
}

int main(){ _;
  cin>>n>>m;
  int a,b;
  REP(i,m){
    cin>>a>>b;
    a--;b--;
    es[a].push_back(b);
    es[b].push_back(a);
  }
  cout<<solve()<<endl;
}


Measured memory_bytes: 5888
import sys
input = sys.stdin.readline
n = int(input())
s = [''] * 2
s[0] = input().strip()
s[1] = input().strip()
mod = 10 ** 9 + 7
if n == 1:
    print(3)
    exit()
if s[0][0] == s[1][0]:
    ans = 3
    j = 1
    if s[0][1] == s[1][1]:
        ans *= 2
        j += 1
elif s[0][0] == s[0][1]:
    ans = 6
    j = 2

while j < n:
    if s[0][j] == s[1][j]:
        if s[0][j-1] == s[1][j-1]:
            ans = (ans * 2) % mod
        j += 1
    else:
        if s[0][j-1] == s[1][j-1]:
            ans = (ans * 2) % mod
        else:
            ans = (ans * 3) % mod
        j += 2

print(ans)

Measured memory_bytes: 3064
N = int(input())
arr = list(map(int, input().split()))
arr = arr
dp = [0] * N
dp[0] = 0
dp[1] = abs(arr[0]-arr[1])
for i in range(2,N):
    dp[i] = min(abs(arr[i]-arr[i-2])+dp[i-2],abs(arr[i]-arr[i-1])+dp[i-1])
print(dp[N-1])

Measured memory_bytes: 13928
// 20:36 -

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <deque>
#include <vector>
#include <set>
#include <string>
#include <queue>
#include <map>
#include <cmath>
#include <stack>

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

using namespace std;

int main(){
  int N, A, B;
  int cnt = 0;
  cin >> N >> A >> B;

  for(int i = 1; i <= N; i++){
    int work = i;
    int dig = 0;
    while(work > 0){
      dig += work % 10;
      work /= 10;
    }
    // cout << "dig:" << dig << endl;
    if(dig >= A && dig <= B) cnt += i;
  }
  cout << cnt << endl;
  return 0;
}


Measured memory_bytes: 256
while 1:
    n = int(input())
    if n == 0:break
    c = {}
    for _ in range(n):
        s = input().split()
        for e in s:
            if e in c:c[e] += 1
            else:c[e] = 1
    c = [(e, c[e]) for e in c.keys()]
    c.sort(key = lambda x:x[0])
    c.sort(key = lambda x:x[1], reverse = True)
    s = input()
    a = []
    for i in range(len(c)):
        if c[i][0][0] == s:a.append(c[i][0])
    if a == []:print("NA")
    else:print(*a[:5])


Measured memory_bytes: 5616
package main

import (
	"fmt"
)

func main() {
	var x, a, b int
	fmt.Scan(&x, &a, &b)
	a = Abs(x - a)
	b = Abs(x - b)
	if a < b {
		fmt.Println("A")
	} else {
		fmt.Println("B")
	}
}

func Abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}


Measured memory_bytes: 1772
#include <iostream>
#include <set>
using namespace std;
int main(void){
    int N, a;
    cin >> N;
    set<int> s;
    for(int i=0; i<N; i++){
        cin >> a;
        s.insert(a);
    }
    
    if(N == s.size()){
        cout << "YES" << endl;
    }
    else{
        cout << "NO" << endl;
    }
    
}

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

inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> P;
typedef long long ll;

#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define SORT(c) sort((c).begin(),(c).end())
#define REVERSE(c) reverse((c).begin(),(c).end())

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

const double EPS = 1e-10;
const double PI  = acos(-1.0);
const int INT_INF = 2147483647;
const long long LL_INF = 1LL<<60;
const long long MOD = 1000000007;

#define CLR(a) memset((a), 0 ,sizeof(a))

#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

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; }

int main(void){
    ll N,K; cin >> N >> K;
    vector<ll> A(N), F(N); REP(i,N) cin >> A[i]; REP(i,N) cin >> F[i];
    SORT(A); REVERSE(A); SORT(F);

    ll l = -1, r = A[0]*F[N-1], n = (l+r)/2;
    while(r-l>1){
        ll tmp = 0;
        REP(i,N) tmp += max((ll)0, A[i] - n/F[i]);
        if(tmp <= K) r = n;
        else l = n;
        n = (l+r)/2;
    }
    cout << r << endl;
    return 0;
}

Measured memory_bytes: 3328
import java.util.*;

public class Main {
	
	public static int totalMatches(int[] array, int[] array2) {
		int total=0;
		for (int i = 0; i < array2.length; i++) {
			if (Binarysearch(array, array2[i])) {
				total++;
			}
		}
		return total;
	}
	
	public static boolean Binarysearch( int[] array,  int search) {
		int left = 0;
		int right = array.length - 1;
		
		while ( left <= right) {
			int mid = (right+left)/2;
			if(array[mid] < search) {
				left = mid + 1;
			}
			else if(array[mid] > search) {
				right = mid - 1;
			}
			else {
				return true;
			}
		}
		return false;
		
	}
	
	public static void main(String[] args) {
		Scanner input = new Scanner(System.in);
		
		int sizearray = input.nextInt();

		int array[] = new int[sizearray];

		for (int i = 0; i < sizearray; i++) {
			array[i] = input.nextInt();

		}
		
		int sizearray2 = input.nextInt();
		int array2[] = new int[sizearray2];
		for (int i = 0; i < sizearray2; i++) {
			array2[i] = input.nextInt();

		}
		System.out.println(totalMatches(array, array2));
		
		input.close();
	}
	
}



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

typedef long long ll;

ll N, M;
vector<pair<ll, ll>> AB;
vector<ll> B;
vector<vector<pair<ll, ll>>> Adj;
vector<bool> Seen;
set<ll> Res;
ll pos(ll x) {
  return lower_bound(AB.begin(), AB.end(), make_pair(x, -1ll)) - AB.begin();
}
void dfs(ll v) {
  Seen[v] = true;
  for (auto wi : Adj[v]) {
    ll w, i;
    tie(w, i) = wi;
    if (Seen[w]) continue;
    dfs(w);
    if (B[w]) {
      B[w] = 0;
      B[v] = 1 - B[v];
      Res.insert(i);
    }
  }
}
bool check() {
  Seen.resize(N + 1);
  for (ll i = 0; i <= N; ++i) {
    if (Seen[i]) continue;
    dfs(i);
    if (B[i]) return false;
  }
  return true;
}
int main() {
  cin >> N >> M;
  AB.resize(N);
  for (ll i = 0; i < N; ++i) {
    ll a, b;
    cin >> a >> b;
    AB[i] = make_pair(a, b);
  }
  sort(AB.begin(), AB.end());
  B.resize(N + 1);
  for (ll i = 0; i <= N; ++i) {
    B[i] =
        ((i == N ? 0 : AB[i].second) + 2 - (i == 0 ? 0 : AB[i - 1].second)) % 2;
  }
  Adj.resize(N + 1);
  for (ll i = 0; i < M; ++i) {
    ll l, r;
    cin >> l >> r;
    ++r;
    l = pos(l);
    r = pos(r);
    if (l == r) continue;
    Adj[l].emplace_back(r, i);
    Adj[r].emplace_back(l, i);
  }
  if (!check())
    cout << -1 << endl;
  else {
    cout << Res.size() << endl;
    bool first = true;
    for (ll r : Res) {
      cout << (first ? "" : " ") << r + 1;
      first = false;
    }
    cout << endl;
  }
  return 0;
}


Measured memory_bytes: 22784
#define _USE_MATH_DEFINES // for C++  
#include <cmath> 
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <algorithm>
#include <array>
#include <iterator>
#include <utility>
#include <set>
#include <random>
#include <map>
#include <stack>
#include <queue>
#include <list>
#include <functional>
#include <bitset>
#define LL long long
#define NUM 1000000007

using namespace std;

int main() {
    char next, win;
    string sa, sb, sc;
    cin >> sa >> sb >> sc;
    for (size_t count = 0;; count++)
    {
        if (count == 0)
        {
            next = sa.front();
            sa.erase(sa.begin());
        }
        else
        {
            if (next == 'a' && sa.empty())
            {
                win = 'A';
                break;
            }
            else if (next == 'b' && sb.empty())
            {
                win = 'B';
                break;
            }
            else if (next == 'c' && sc.empty())
            {
                win = 'C';
                break;
            }

            if (next == 'a')
            {
                next = sa.front();
                sa.erase(sa.begin());
            }
            else if (next == 'b')
            {
                next = sb.front();
                sb.erase(sb.begin());
            }
            else
            {
                next = sc.front();
                sc.erase(sc.begin());
            }
        }
    }
    cout << win << endl;
}

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

using namespace std;

int main(){
  int n;
  cin>>n;
  int ans=0;
  int a[100];
  for(int i=0;i<n-1;i++){
    cin>>a[i];
    if(i==0){
      ans+=a[i];
    }else{
      ans+=min(a[i-1],a[i]);
    }
  }
  cout<<ans+a[n-2]<<endl;
}


Measured memory_bytes: 3604
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1000005,M=1e9+7;
int n,f[N],sum;
signed main(){
	scanf("%lld",&n);
	f[n]=sum=n;f[n+1]=1;
	for (int i=n-1;i;i--){
		(f[i]+=(n-1)*(n-1))%=M;
		(f[i]+=sum+i+1-f[i+2]+M)%=M;
		(sum+=f[i])%=M;
	}
	printf("%lld\n",f[1]);
}

Measured memory_bytes: 8064
#include<algorithm>
#include<iostream>
#include<vector> 
using namespace std;
int main () {
  int n;
  cin >> n;
  vector<int> d(n);
  for(int i = 0; i < n; i++) {
    cin >> d[i];
  }

  sort(d.begin() , d.end());
  if(d[n/2] != d[(n-1)/2]) {
    cout << d[n/2] -  d[n/2-1] << endl;
  }else{
    cout << 0 << endl;
  }
}


Measured memory_bytes: 640
N, Q = map(int, input().split())
S = input()
s = [0]*(N+1)
for n in range(N):
    if n + 1 < N and S[n] == 'A' and S[n+1] == 'C':
        s[n+1] = s[n] + 1
    else:
        s[n+1] = s[n]
A = []
for q in range(Q):
    l, r = map(int, input().split())
    l -= 1
    r -= 1
    A.append(s[r]-s[l])
for a in A:
    print(a)

Measured memory_bytes: 15416
#include <iostream>

using namespace std;

int main(){
	int a, b;
	cin >> a >> b;
	if(a*b > a+b && a*b > a-b)
		cout << a*b << endl;
	else if(a+b > a-b)
		cout << a+b << endl;
	else
		cout << a-b << endl;

	return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<map>
#include<string>
using namespace std;
int main(){
int n;
cin >>n;
string s;
cin >> s;
for(int i=0;i<s.size();i++){
if('A' <= s[i] + n && 'Z' >= s[i] + n){
    cout << (char)(s[i] + n);
}else{
    cout << (char)(s[i]  - 26 + n);
}
}
cout << endl;
return 0;
}


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

const vector<int> dx = {-1, 0, 1, 0};
const vector<int> dy = {0, 1, 0, -1};

int main() {
    int h, w;
    cin >> h >> w;
    vector<string> grid(h);
    for (int i = 0; i < h; ++i) cin >> grid[i];
    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
            if (grid[i][j] == '#') {
                bool test = true;
                for (int k = 0; k < 4; ++k) {
                    int nx = i + dx[k];
                    int ny = j + dy[k];
                    if (nx < 0 || nx >= h || ny < 0 || ny >= w) continue;
                    if (grid[nx][ny] == '#') {
                        test = false;
                        break;
                    }
                }
                if (test) {
                    cout << "No" << endl;
                    return 0;
                }
            }
        }
    }
    cout << "Yes" << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <stdlib.h>
#include <limits.h>

using namespace std;


int getdis(int a, int b, int c, int d) {
	return abs(a - c) + abs(b - d);
}

int main() {

	int a[50];
	int b[50];
	int c[50];
	int d[50];

	int n, m;
	int dis;

	cin >> n >> m;

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

	for (int i = 0; i < m; i++) {
		cin >> c[i] >> d[i];
	}

	for (int i = 0; i < n; i++) {
		int wk_dis = INT_MAX;
		int ansindex;
		for (int j = 0; j < m; j++) {
			dis = getdis(a[i], b[i], c[j], d[j]);

			if (dis < wk_dis) {
				ansindex = j;
				wk_dis = dis;
			}
		}
		
		cout << ansindex+1 << endl;
	}







	return 0;
}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigDecimal;
import java.math.RoundingMode;

class Main {

	 private static final int A = 0;
	    private static final int B = 1;
	    private static final int C = 2;
	    private static final int D = 3;
	    private static final int E = 4;
	    private static final int F = 5;


	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String str ;
		String[] num1 = null;

		try {


		while ((str = br.readLine()) !=null) {


		 num1 = str.split(" ");

		BigDecimal[] array = new BigDecimal[num1.length] ;


		for(int i=0; i<num1.length; i++){
			array[i] = new BigDecimal(num1[i]);
		}


		BigDecimal x= array[C].multiply(array[E]).subtract(array[B].multiply(array[F])).divide(array[A].multiply(array[E]).subtract(array[B].multiply(array[D])));

		BigDecimal y= array[C].multiply(array[D]).subtract(array[A].multiply(array[F])).divide(array[B].multiply(array[D]).subtract(array[A].multiply(array[E])));

		System.out.println(x.setScale(3, RoundingMode.HALF_UP)+" "+y.setScale(3, RoundingMode.HALF_UP));

		}

		} catch (Exception e) {
			// TODO: handle exception
		}


	}

}

Measured memory_bytes: 24364
#include<iostream>
#include<vector>

int main() {
	int N, M;
	std::cin >> N >> M;
	std::vector<int> height(N);
	for (int i = 0; i < N; i++) std::cin >> height[i];
	std::vector<std::vector<int>> connection(N);
	for (int i = 0; i < M; i++) {
		int A, B;
		std::cin >> A >> B;
		connection[A - 1].push_back(B);
		connection[B - 1].push_back(A);
	}

	int answer = 0;
	for (int i = 0; i < N; i++) {
		bool flag = true;
		for (int j : connection[i]) {
			if (height[j - 1] >= height[i]) flag = false;
		}
		if (flag) answer++;
	}
	std::cout << answer << std::endl;
	return 0;
}

Measured memory_bytes: 8812
a, b, c, d, e, f = map(int, input().split())
kouho = 0
jisho = {}
max_a = 30 // a
max_b = 30 // b
for i in range(max_a + 1):
    for j in range(max_b + 1):
        water = (a * i + b * j) * 100
        if water == 0:
            continue
        lim1 = e * (a * i + b * j)
        lim2 = f - water
        lim = min(lim1, lim2)
        max_c = lim // c
        max_d = lim // d
        for k in range(max_c + 1):
            for m in range(max_d + 1):
                sugar = k * c + m * d
                if sugar > lim:
                    continue
                satoumizu = water + sugar
                if satoumizu > f:
                    continue
                if sugar == 0:
                    continue

                noudo = 100 * sugar / satoumizu
                if noudo > kouho:
                    kouho = noudo
                    jisho[noudo] = (sugar, satoumizu)
if kouho == 0:
    print(100 * a, 0)
    exit()
ans2, ans1 = jisho[kouho]
print(ans1, ans2)


Measured memory_bytes: 73076
encode = {
	'D':'A',
	'E':'B',
	'F':'C',
	'G':'D',
	'H':'E',
	'I':'F',
	'J':'G',
	'K':'H',
	'L':'I',
	'M':'J',
	'N':'K',
	'O':'L',
	'P':'M',
	'Q':'N',
	'R':'O',
	'S':'P',
	'T':'Q',
	'U':'R',
	'V':'S',
	'W':'T',
	'X':'U',
	'Y':'V',
	'Z':'W',
	'A':'X',
	'B':'Y',
	'C':'Z'
	}

code = raw_input()
conversion = ""

for var in code:
	conversion += encode[var]
	
print conversion

Measured memory_bytes: 6348
/* ****GT_18**** */

#include<bits/stdc++.h>
#define ll          long long
#define pb          push_back
#define	endl		'\n'
#define pii         pair<ll int,ll int>
#define vi          vector<ll int>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define sz(x)       (ll int)x.size()
#define hell        1000000007
#define INF        100000000000007
#define rep(i,a,b)	for(ll int i=a;i<b;i++)
#define lbnd        lower_bound
#define ubnd        upper_bound
#define bs          binary_search
#define mp          make_pair
using namespace std;

#define N  105
#define V  100005


ll w,n;
ll wts[N];
ll vals[N];
ll dp[V][2];
ll sm;

ll solve(){
	dp[0][0]=dp[0][1]=0;
	ll ans=0;
	rep(i,0,n){
		rep(j,0,sm+1){
			// if(j==30){
			// 	cerr<<"i: "<<i<<"   "<<dp[j]<<endl;
			// }
			if(dp[j][0]>=INF)continue;
			dp[j+vals[i]][1]=min(dp[j+vals[i]][0],dp[j][0]+wts[i]);
			if(dp[j+vals[i]][1]<=w)ans=max(ans,j+vals[i]);
		}
		rep(j,0,sm+1){
			dp[j][0]=dp[j][1];
		}
		// cerr<<"30:"<<dp[30][1]<<" 50:"<<dp[50][1]<<" 60:"<<dp[60][1]<<" 80:"<<dp[80][1]<<" 90:"<<dp[90][1]<<endl;
	}

	return ans;
}


int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int TESTS=1;
//	cin>>TEST	S;
	rep(j,0,V)rep(i,0,2)dp[j][i]=INF;
	while(TESTS--)
	{
			cin>>n>>w;
			sm=0;
			rep(i,0,n){
				cin>>wts[i]>>vals[i];
				sm+=vals[i];
			}
			// cerr<<"Sm:"<<sm<<endl;
			cout<<solve()<<endl;

			// cout<<ans<<endl;

	}
	return 0;
}


Measured memory_bytes: 5184
#include <bits/stdc++.h>
typedef long long LL;
#define SORT(c) sort((c).begin(),(c).end())

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
using namespace std;
class Vec2{
public:
  double x,y;
  Vec2(){
    Vec2(0,0);
  }
  Vec2(double a,double b){
    x=a,y=b;
  }
  Vec2 operator+(Vec2 a){
    return Vec2(x-a.x,y-a.y);
  }
  Vec2 operator-(Vec2 a){
    return Vec2(x-a.x,y-a.y);
  }
  double norm(void){
    return sqrt(x*x+y*y);
  }
  double sqnorm(void){
    return x*x+y*y;
  }
  Vec2 mul(double k){
    return Vec2(k*x,k*y);
  }
};

double cross(Vec2 a,Vec2 b)
{
  return a.x*b.y-a.y*b.x;
}
pair<Vec2,Vec2> cci(pair<Vec2,double> a,pair<Vec2,double> b)
{
  double s=(a.second*a.second-b.second*b.second)/(a.first-b.first).sqnorm()/2+0.5;
  Vec2 ac=(a.first-b.first).mul(s);
  double k=sqrt(a.second*a.second-ac.sqnorm())/ac.norm();
  return make_pair(a.first+ac+(Vec2(ac.y,-ac.x)).mul(k),a.first+ac+(Vec2(-ac.y,ac.x)).mul(k));
}

int main(void)
{
  for(;;){
    int n;
    cin >> n;
    if(!n) return 0;
    vector<pair<Vec2,double> > c(n);
    REP(i,n) cin >> c[i].first.x >> c[i].first.y >> c[i].second;
    vector<vector<Vec2> > ip(n+1,vector<Vec2>(2));
    ip[0].assign(2,c[0].first);
    REP(i,n-1){
      auto ipp=cci(c[i],c[i+1]);
      ip[i+1][0]=ipp.first;
      ip[i+1][1]=ipp.second;
    }
    ip[n].assign(2,c[n-1].first);
    vector<vector<double> > cost(n+1,vector<double>(2,1e+9));
    cost[0].assign(2,0.0);
    REP(i,n+1) REP(j,i)	REP(k,2) REP(l,2){
      Vec2 a=ip[j][l],b=ip[i][k];
      bool flag=true;
      FOR(m,j+1,i)
	if(!(cross(b-a,ip[m][0]-a)*cross(b-a,ip[m][1]-a) < 0 &&
	     cross(ip[m][1]-ip[m][0],a-ip[m][0])*cross(ip[m][1]-ip[m][0],b-ip[m][0]))){
	  flag=false;
	  break;
	}
      if(flag) cost[i][k]=min(cost[i][k],cost[j][l]+(b-a).norm());
    }
    cout << fixed << setprecision(10) << cost[n][0] << endl;
  }
}

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

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int MAXN = 2e5 + 7;
const ll INF = 1e18;

int main() {
	int n;
	cin >> n;
	string s;
	cin >> s;
	string s1, s2;
	for (int i = 0; i < n / 2; i++) {
		s1 += s[i];
	}
	for (int i = n / 2; i < n; i++) {
		s2 += s[i];
	}
	if (s1 == s2) cout << "Yes\n";
	else cout << "No\n";
	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
#include<string.h>


#define N 100000

int bs(int *,int,int);


int main(){
  int i,n,key,q,S[N];
  int cnt=0;

  scanf("%d",&n);

  for(i=0;i<n;i++){
    scanf(" %d",&S[i]);
  }

  scanf(" %d",&q);

  for(i=0;i<q;i++){
    scanf(" %d",&key);
    if(bs(S,n,key)==1){
      cnt++;
    }
  }
  printf("%d\n",cnt);

  return 0;
}

int bs(int *S,int n,int key){
  int left,right,mid;
    left = 0;
    right = n;
    while(left < right){

        mid = (left + right) / 2;
        if (S[mid] == key){
          return 1;
          }
        else if (key < S[mid]){
            right = mid;
          }
        else {
            left = mid + 1;
          }
    }
return 0;
}



Measured memory_bytes: 2248
#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);

//約数列挙
vector<int> DivAll(int n) {
	vector<int> ret;
	int i = 1;
	for (; i*i < n; i++)
		if (n%i == 0)ret.push_back(i);
	bool flag = i * i == n;
	if (flag)ret.push_back(i);
	for (i = ret.size() - 1 - flag; i >= 0; --i)
		ret.push_back(n / ret[i]);
	return ret;
}

int main() {
	int n; cin >> n;
	VI t(n); rep(i, n)cin >> t[i]; sort(all(t));
	VI div = DivAll(t.back());
	int ans = 0;
	rep(i, n - 1) {
		auto it = lower_bound(all(div), t[i]);
		if (it != div.end())ans += *it - t[i];
		//cout << *it << " - " << t[i] << endl;
	}
	Cout(ans);
}


Measured memory_bytes: 3208
fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}
fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}
fn read_vec2<T: std::str::FromStr>(n: u32) -> Vec<Vec<T>> {
    (0..n).map(|_| read_vec()).collect()
}
fn main(){
    let (a,b,c) = {
        let t = read_vec::<i64>();
        (t[0],t[1],t[2])
    };
    println!("{}",a*b/2);
}


Measured memory_bytes: 4352
#include <bits/stdc++.h> 
#define rep(i, n) for(long long i = 0; i < (long long)(n); i++)
#define Rep(i,s,t) for(long long i=s;i<t;i++)
#define all(x) x.begin(),x.end()
typedef long long ll;
using namespace std;
int main(){
  string s;
  cin>>s;
  map<char,int> m;
  rep(i,4){
    if(m.count(s[i])){m[s[i]]++;}
    else m[s[i]]=1;}
  bool ans=true;
  for(auto x:m){
    if(x.second!=2){ans=false;}}
  if(ans){cout<<"Yes"<<endl;}
  else cout<<"No"<<endl;
}

Measured memory_bytes: 256