akhauriyash/Code-Regression huggingface dataset:
H, W = map(int, input().split())
s = [input() for _ in range(H)]

dp = [[2501] * W for _ in range(H)]
dp[0][0] = 1

q = [(0, 0)]
while q:
    nq = []
    while q:
        y, x = q.pop()
        t = dp[y][x] + 1
        if y < H - 1:
            if s[y + 1][x] == '.' and dp[y + 1][x] > t:
                dp[y + 1][x] = t
                nq.append((y + 1, x))
        if y > 0:
            if s[y - 1][x] == '.' and dp[y - 1][x] > t:
                dp[y - 1][x] = t
                nq.append((y - 1, x))
        if x < W - 1:
            if s[y][x + 1] == '.' and dp[y][x + 1] > t:
                dp[y][x + 1] = t
                nq.append((y, x + 1))
        if x > 0:
            if s[y][x - 1] == '.' and dp[y][x - 1] > t:
                dp[y][x - 1] = t
                nq.append((y, x - 1))
    q = nq

if dp[H - 1][W - 1] == 2501:
    print(-1)
else:
    print(sum(s[y].count('.') for y in range(H)) - dp[H - 1][W - 1])


Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
int dp[105][105];
bool b[105][105];
int main()
{
    int h,w;
    cin>>h>>w;
    for(int i=0;i<h;i++)
    {
        for(int j=0;j<w;j++)
        {
            char c;
            cin>>c;
            if(c=='#') b[i][j]=1;
        }
    }
    if(b[0][0]) dp[0][0]=1;
    else dp[0][0]=0;
    for(int i=0;i<h;i++)
    {
        for(int j=0;j<w;j++)
        {
            if(i==0&&j==0) continue;
            if(i==0) dp[i][j]=dp[i][j-1]+(b[i][j-1]==0&&b[i][j]==1);
            if(j==0) dp[i][j]=dp[i-1][j]+(b[i-1][j]==0&&b[i][j]==1);
            if(i>0&&j>0) dp[i][j]=min(dp[i-1][j]+(b[i-1][j]==0&&b[i][j]==1),dp[i][j-1]+(b[i][j-1]==0&&b[i][j]==1));
        }
    }
    cout<<dp[h-1][w-1]<<'\n';
}


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

int main(void) {
	string S;
	cin >> S;
	int tapNum = (int) S.length();
	bool ans = true;
	for (int i = 0; i < tapNum; i++) {
		if (((i + 1) % 2 == 0 && S[i] == 'R') || ((i + 1) % 2 == 1 && S[i] == 'L')) {
			ans = false;
			break;
		}
	}
	if (ans) {
		cout << "Yes" << "\n";
	} else {
		cout << "No" << "\n";
	}

	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int A[1000];
int B[1000];

int main(){
  int N;
  cin>>N;
 
  for(int i=1; i<N; i++){
    cin>>B[i];
  }

  A[1]=B[1];
  A[N]=B[N-1];
  int S=A[1]+A[N];
  
  for(int i=2; i<N; i++){
    A[i]=min(B[i-1], B[i]);
    S +=A[i];
  }
  
  cout<<S<<endl;
}


Measured memory_bytes: 256
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <cmath>
#include <iomanip>

using namespace std;
using ll = long long;

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

#include <iostream>

int main()
{
    string S;
    cin >> S;

    if (S[0] == S[1] || S[1] == S[2] || S[2] == S[3]) { cout << "Bad" << endl; }
    else { cout << "Good" << endl; }
}

Measured memory_bytes: 256
/*
                IftekharMd.Shishir
                Dept. of Information and Communication Engineering
                University of Rajshahi
*/

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>

#define ll  long long
#define ull  unsigned long long
#define ld  long double
#define f(i,n)  for(i=0;i<n;i++)
#define F(i,n)  for(i=n-1;i>=0;i--)
#define fa(i,a,b)  for(i=a;i<=b;i++)
#define Fa(i,a,b)  for(i=a;i>=b;i--)
#define printArray(i,a,n)  f(i,n)cout<<a[i]<<" "; cout<<endl;
#define printSet(a)  for(auto setData:a) cout<<setData<<" ";cout<<endl;
#define printMap(a)  for(auto mapData:a) cout<<mapData.first<<" "<<mapData.second<<endl;
#define printVector(a)  for(auto vectorData:a)cout<<vectorData<<" ";cout<<endl;
#define printLinkedList()  temp=head;while(temp){cout<<temp->data<<" ";temp=temp->post;} cout<<endl;

#define pb(x)  push_back(x)
#define all(a)  a.begin(),a.end()
#define rall(a)  a.rbegin(),a.rend()

#define bs  binary_search
#define lb  lower_bound
#define ub  upper_bound
#define mp  make_pair
#define TxtIO  freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
#define TxtTest freopen("C:/Users/Iftekhar/Documents/what/input.txt", "r", stdin);
#define FastIO  ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
#define TestCase  ll t;cin>>t;while(t--)
#define points(x)  fixed<<setprecision(x)
#define scd(a,x,y)  a/__gcd(x,y);
#define nl  cout<<endl;
#define done  return 0

const ld PI= 3.14159265358979323846264338327950288;  //2*acos(0.0);
const long long MOD= 1000000007;
const long long MAX = 32000;

// stringstream demo(str);  demo >> x;
// stringstream demo;  demo << x;  name=demo.str();

using namespace __gnu_pbds;
using namespace std;
typedef tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;

int main()
{
        FastIO;
        //TxtTest;
        ll n,i;
        cin>>n;
        if(n==1) {
                cout<<1<<endl;
                done;
        }
        ll a[7]={2,4,8,16,32,64,128};
        for(i=0;i<7-1;i++){
                if(n>=a[i] && n<a[i+1]){
                        cout<< a[i] <<endl;
                        done;
                }
        }
        done;
}


Measured memory_bytes: 3612
#include <iostream>
#include <queue>
#include <algorithm>
#include <climits>
using namespace std;

int N,M,R;
int edges[210][210];
int dp[1<<8][210];
int r2bit[210];

struct State {
    int id;
    int condition;
    int cost;
    bool operator<(const State& a) const {
        return cost > a.cost;
    }
};

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

    // init
    for (int i=0; i<210; i++) r2bit[i] = -1;
    for (int i=0; i<(1<<8); i++) {
        for (int j=0; j<210; j++) {
            dp[i][j] = INT_MAX;
        }
    }
    for (int i=0; i<210; i++) {
        for (int j=0; j<210; j++) {
            edges[i][j] = -1;
        }
    }

    vector<int> mustVertex(R);
    for (int i=0; i<R; i++) {
        cin >> mustVertex[i];
        r2bit[mustVertex[i]] = i;
    }

    for (int i=0; i<M; i++) {
        int a,b,c;
        cin >> a >> b >> c;
        edges[a][b] = c;
        edges[b][a] = c;
    }


    priority_queue<State> q;
    for (int i=0; i<mustVertex.size(); i++) {
        dp[1<<i][mustVertex[i]] = 0;
        q.push( State{ mustVertex[i], (1<<i), 0 } );
    }

    while (!q.empty()) {
        State n = q.top();
        q.pop();

        if (dp[n.condition][n.id] < n.cost) continue;

        for (int i=1; i<=N; i++) {
            if (edges[n.id][i] == -1) continue;
            int dst = i;
            int next_cost = edges[n.id][dst] + n.cost;
            int next_condition = n.condition;
            if (r2bit[dst] != -1) {
                next_condition |= (1<<r2bit[dst]);
            }
            if (dp[next_condition][dst] > next_cost) {
                dp[next_condition][dst] = next_cost;
                q.push( State{ dst, next_condition, next_cost } );
            }
        }
    }

    int ans = INT_MAX;
    for (int i=0; i<mustVertex.size(); i++) {
        ans = min(ans, dp[(1<<R)-1][mustVertex[i]]);
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 4980
import java.util.*;
public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int H = sc.nextInt();
		int W = sc.nextInt();
		char[] s = new char[H*W];
		for(int i = 0; i < H; i++) {
			String S = sc.next();
			for(int j = 0; j < W; j++)
				s[i*W+j] = S.charAt(j);
		}
		int[] n = new int[H*W];
		Arrays.fill(n, 100000);
		n[0] = 0;
		ArrayDeque<Integer> q = new ArrayDeque<>();
		q.offer(0);
		Set<Integer> NG = new HashSet<>();
		for(int i = 0; i < H; i++)
			NG.add(i*W+W);
		while(q.size() > 0) {
			int x = q.poll();
			if(!NG.contains(x+1)) {
				if(s[x+1] == s[x]) {
					if(n[x+1] > n[x]) {
						n[x+1] = n[x];
						q.offer(x+1);
					}
				}
				else {
					if(n[x+1] > n[x] + 1) {
						n[x+1] = n[x] + 1;
						q.offer(x+1);
					}
				}
			}
			if(x + W >= H * W)
				continue;
			if(s[x+W] == s[x]) {
				if(n[x+W] > n[x]) {
					n[x+W] = n[x];
					q.offer(x+W);
				}
			}
			else {
				if(n[x+W] > n[x] + 1) {
					n[x+W] = n[x] + 1;
					q.offer(x+W);
				}
			}
		}
		if(s[0] == '#')
			System.out.println((n[H*W-1])/2 + 1);
		else
			System.out.println((n[H*W-1]+1)/2);

	}

}

Measured memory_bytes: 23892
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
using namespace std;
using ll = long long ;
using P = pair<int,int> ;
using pll = pair<long long,long long>;
constexpr int INF = 1e9;
constexpr long long LINF = 1e17;
constexpr int MOD = 1000000007;

int main(){
    string s;cin >>s;
    if(s == "ARC") cout << "ABC" << endl;
    else cout << "ARC" << endl;
    return 0;
}

Measured memory_bytes: 3624
def to_lines(s):
    h = 0
    b = 0
    for c in s:
        if c == '(':
            h += 1
        else:
            h -= 1
        b = min([b, h])
    return (b, h)


def check(lines):
    h = 0
    for line in lines:
        if h + line[0] < 0:
            return False
        h += line[1]
    return True


def main():
    N = int(input())
    up_lines = list()
    down_lines = list()
    total = 0
    for _ in range(N):
        line = to_lines(input())
        total += line[1]
        if line[1] >= 0:
            up_lines.append(line)
        else:
            inv_line = (line[0] - line[1], -line[1])
            down_lines.append(inv_line)
    up_lines.sort(key=lambda x: x[0], reverse=True)
    down_lines.sort(key=lambda x: x[0], reverse=True)
    if total == 0 and check(up_lines) and check(down_lines):
        print('Yes')
    else:
        print('No')


if __name__ == '__main__':
    main()

Measured memory_bytes: 84228
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
#define ll long long
#define pb push_back
#define fr first
#define sc second
#define MAX ((ll)(1e17+100))
#define MX ((ll)(1e6+100))
#define ARRS ((ll)(2e6+100))
#define HS ((ll)(233))
#define MOD ((ll)(1e9+7))
#define EP ((double)(1e-9))
#define LG 21
#define mul(a,b) a=((a)*(b))%MOD
using namespace std;



int main(){
	ll n,k;
	vector<ll> va;
	vector<ll> vb;
	cin>>n>>k;
	for(int i=0; i<n; i++){
		ll t;
		cin>>t;
		if(t>=0)va.pb(t);
		else vb.pb(-t);
	}
	va.pb(0);
	vb.pb(0);
	sort(va.begin(),va.end());
	sort(vb.begin(),vb.end());
	for(int i=1; i<va.size(); i++){
		//va[i]+=va[i-1];
	}
	for(int i=1; i<vb.size(); i++){
		//vb[i]+=vb[i-1];
	}
	ll pas=MAX;
	for(int i=0; i<vb.size(); i++){
		if(va.size()>k-i)
		pas=min(pas,2*vb[i]+va[k-i]);
	}
	for(int i=0; i<va.size(); i++){
		if(vb.size()>k-i)
		pas=min(pas,2*va[i]+vb[k-i]);
	}
	cout<<pas;
}


Measured memory_bytes: 1656
import java.util.*;
public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    char a = sc.next().charAt(0);
    if(a == 'a' || a == 'i' || a == 'u' || a == 'e' || a =='o'){
      System.out.println("vowel");
    }else{
      System.out.println("consonant");
    }
  }
}

Measured memory_bytes: 21716
/* **
   ** SMIT MANGUKIYA
   ** DA-IICT(201801191)
   **
*/

#include <bits/stdc++.h>
using namespace std;

#define FAST ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);srand(time(NULL))
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define el endl
#define INF LONG_LONG_MAX
#define MINF LONG_LONG_MIN
#define FOR(i,a,b) for(ll i=a;i<b;i++)
#define RFOR(i,a,b) for(ll i=a;i>b;i--)
#define gcd(a,b) __gcd((a),(b))
#define lcm(a,b) (a*b)/gcd(a,b)
#define PI 3.141592653589793
#define MOD 1000000007

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

ll b_power(ll a,ll b);            // a^b
ll min_div(ll n);                 // minimum divisor from 2 to ....n
int is_prime(ll n);               // is prime!
ll ncr(ll n, ll c);		  // ncr(combination)
int solve[2001][2001] ;
void pre()
{
	int i,j;
	for(i=0;i<2001;i++){
    solve[i][0]=1;
    solve[i][i]=1;
    }
    for(i=1;i<2001;i++)
        for(j=1;j<2001;j++)
            if (i!=j)
                solve[i][j]=(solve[i-1][j]%MOD+solve[i-1][j-1]%MOD)%MOD;
}
// ---------------------------------------------------------------------------------------------------
int main() {
        FAST;
         pre();
        ll n,k;
       
        cin >> n >> k;
        for(ll i=1 ; i<=k ; i++)
        {
        	ll temp=  solve[n-k+1][i];
			int g = k - i;
        	ll temp2 = solve[g + i -1][i-1]%MOD;
        	ll ans = (temp * temp2)%MOD;
        	cout << ans << "\n";
		}
        
        

}

// ---------------------------------------------------------------------------------------------------

ll b_power(ll a, ll b)
{
    ll res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a;
        a = a * a;
        b >>= 1;
    }
    return res;
}

ll min_div(ll n)
{
    for(ll i=2;i*i<=n;i++){
        if(n%i==0){
            return i;
        }
    }
    return n;
}

int is_prime(ll n)
{
    if(n==2)
        return 1;
    for(ll i=2; i*i <= n; i++)
    {
        if(n%i==0)
        return 0;
    }

    return 1;
}

ll ncr( ll n, ll c){
    ll t=1;
    c = min(c,n-c);
    for(ll i=1; i<=c ;i++)
        t= ((t*(n-i+1))/i)%MOD;
    return t;
}


Measured memory_bytes: 15872
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _0007
{
    class Program
    {
        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            double answer = 100;
            for (int i = 0; i < n; i++)
            {
                answer = Math.Ceiling(answer * 1.05);
            }
            Console.WriteLine(answer*1000);
        }
    }
}



Measured memory_bytes: 13848
#include<iostream>
#include<string>
 
using namespace std;
 
int main() {
  string s;
  cin >> s;
  for (auto& e : s) {
    if (e == '7') {
      cout << "Yes" << endl;
      exit(0);
    }
  }
  cout << "No" << endl;
}

Measured memory_bytes: 3164
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (ll i = 0; i < n; i++)
#define repl(i, l, r) for (ll i = (l); i < (r); i++)
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define CST(x) cout << fixed << setprecision(x)
using ll = long long;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
using pl = pair<ll, ll>;
const ll MOD = 1000000007;
const int inf = 1e9 + 10;
const ll INF = 4e18;
const int dx[9] = {1, 0, -1, 0, 1, -1, -1, 1, 0};
const int dy[9] = {0, 1, 0, -1, 1, 1, -1, -1, 0};
int main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);

	ll n;
	cin >> n;
	ll ans = INF;
	repl(i, 1, (ll)sqrt(n) + 1) {
		if (n % i == 0) {
			ll p = i, q = n / i;
			ans = min(ans, p + q);
		}
	}
	cout << ans - 2 << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
        using namespace std;
        #define rep(i,a,b) for(int i =a; i<b;++i)
        #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
        #define endl "\n"
        typedef  long long int ll;
        const int N = 5e5+5;
        const int mod = 1e9+7;
        ll m,n,_left[N],_right[N],a[N];
        bool comp(const pair <int ,int > &p1 , const pair<int ,int > &p2)
        {
            return p2.first < p1.first;
        }
    int  main()
    {
        IOS;
        int t = 1;
       // cin>>t;
        while(t--)
        {
              string s;
              cin>>s;
              ll last_val;
              bool flag=  0;
              rep(i,0,s.length())
              {
                  if( s[i] == '<' )
                  {
                      if(s[i-1]== '<' and i-1 >=0)
                      {
                          a[i] = a[i-1]+1;
                      }
                      else if(s[i-1]=='>' and i-1>=0)
                      {
                          a[i] = 0;
                      }
                      else {a[i] = 0;}
                  }
                  else
                  {
                      if(s[i-1]=='<' and i-1>=0)
                      {
                          ll j = i,cnt = 0;
                          while(j<s.length() and s[j]=='>')
                          {
                              cnt++,j++;
                          }
                          a[i] = max(cnt,a[i-1]+1);
                          if(cnt<a[i-1]+1 and cnt>1)
                          {
                              flag = 1;
                              last_val = cnt;
                          }
                      }
                      else if(s[i-1] == '>' and i-1 >= 0 )
                      {
                          if(flag)
                          {
                              flag = 0;
                              a[i] = last_val - 1;
                          }
                          else
                          {
                              a[i] = a[i-1]-1;
                          }
                      }
                      else
                      {
                          int j = i,cnt = 0;
                          while(j<s.length() and s[j]=='>')
                          {
                              cnt++,j++;
                          }
                          a[i] = cnt;
                      }
                  }
              }
              ll sum = 0;
        rep(i,0,s.length()){
        sum += a[i];}
         cout<<sum + (s[s.length()-1] =='<' ? a[s.length()-1]+1: 0)<<endl;
        }

    }


Measured memory_bytes: 5020
import std.stdio;
import std.algorithm;
import std.string;
import std.range;
import std.array;
import std.conv;
import std.complex;
import std.math;
import std.ascii;
import std.bigint;
import std.container;
import std.typecons;

auto readInts() {
	return array(map!(to!int)(readln().strip().split()));
}
auto readInt() {
	return readInts()[0];
}
auto readLongs() {
	return array(map!(to!long)(readln().strip().split()));
}
auto readLong() {
	return readLongs()[0];
}

const real eps = 1e-10;

void main(){
	while(true) {
		auto l = readInts();
		auto x = l[0];
		auto y = l[1];
		auto s = l[2];
		if(x == 0 && y == 0 && s == 0) {
			return;
		}
		int ans;
		for(int i = 1; i*(100+x)/100 < s; ++i) {
			int t = (s-i*(100+x)/100)*100/(100+x);
			while((t+1)*(100+x)/100 <= (s-i*(100+x)/100)) {
				++t;
			}
			if(i*(100+x)/100 + t*(100+x)/100 == s) { 
				ans = max(i*(100+y)/100 + t*(100+y)/100, ans);
			}
		}
		writeln(ans);
	}
}

Measured memory_bytes: 2528
#include "bits/stdc++.h"

using namespace std;

#define int long long
#define ll long long
typedef pair<int, int> P;
#define mod 1000000007
#define INF (1LL<<60)

#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define YES puts("YES\n")
#define Yes puts("Yes\n")
#define NO  puts("NO\n")
#define No  puts("No\n")


struct UnionFind {
	vector< int > data;

	UnionFind(int sz) {
		data.assign(sz, -1);
	}

	bool unite(int x, int y) {
		x = find(x), y = find(y);
		if (x == y) return (false);
		if (data[x] > data[y]) swap(x, y);
		data[x] += data[y];
		data[y] = x;
		return (true);
	}

	int find(int k) {
		if (data[k] < 0) return (k);
		return (data[k] = find(data[k]));
	}

	int size(int k) {
		return (-data[find(k)]);
	}
};

signed main() {

	int N;
	cin >> N;
	vector<int> x(N), y(N);

	int MAX = 100000;
	UnionFind uf(2*MAX);

	rep(i, N) {
		cin >> x[i] >> y[i];
		x[i]--; y[i]--;
		uf.unite(x[i], y[i] + MAX);
	}

	map<int, int> cx, cy;
	for (int i = 0; i < MAX; i++) {
		cx[uf.find(i)]++;
	}
	for (int i = MAX; i < 2*MAX; i++) {
		cy[uf.find(i)]++;
	}
	int ans = 0;
	for (int i = 0; i < 2 * MAX; i++) {
		ans += cx[i] * cy[i];
	}
	ans -= N;
	cout << ans << endl;


	
	return 0;
}


Measured memory_bytes: 28416
#define _USE_MATH_DEFINES
#include<iostream>
#include<string>
#include<queue>
#include<cmath>
#include<map>
#include<set>
#include<list>
#include<iomanip>
#include<vector>
#include<random>
#include<functional>
#include<algorithm>
#include<stack>
#include<cstdio>
#include<bitset>
#include<unordered_map>
#include<climits>
#include<fstream>
using namespace std;
///////////////////library zone!!!!!!!!!!!!!!!!!!!!!!!!!!!!
typedef long long ll;
typedef long double ld;
#define all(a) (a).begin(),(a).end()
#define EPS (1e-5)
#define bit(n,k) ((n>>k)&1)
const ll Mod = 1000000007;
const ll mod = 998244353;
struct H {
	ll x, y;
	bool operator<(const H& b) const {
		if (x != b.x) return x < b.x;
		return y < b.y;
	}
	bool operator>(const H & b) const {
		if (x != b.x) return x > b.x;
		return y > b.y;
	}
	bool operator==(const H & b) const { return x == b.x && y == b.y; }
	bool operator!=(const H & b) const { return (*this) != b; }
};
struct P {
	ll pos, cost;
	bool operator<(const P& b) const { return cost < b.cost; }
	bool operator>(const P& b) const { return cost > b.cost; }
};
struct B {
	ll to, cost;
};
struct E {
	ll from, to, cost;
	bool operator<(const E& b) const { return cost < b.cost; }
	bool operator>(const E& b) const { return cost > b.cost; }
};
template<typename T, typename U>
void chmin(T & a, U b) {
	if (a > b) a = b;
}
template<typename T, typename U>
void chmax(T & a, U b) {
	if (a < b) a = b;
}
template<typename T>
T max_0(T a) {
	if (a < 0) return 0;
	return a;
}
template<typename T>
T min_0(T a) {
	if (a > 0) return 0;
	return a;
}
ll read() {
	ll u;
	ll k = scanf("%lld", &u);
	return u;
}
ll gcd(ll i, ll j) {
	if (i > j) swap(i, j);
	if (i == 0) return j;
	return gcd(j % i, i);
}
ll mod_pow(ll x, ll n, ll p) {
	ll res = 1;
	while (n > 0) {
		if (n & 1) res = res * x % p;
		x = x * x % p;
		n >>= 1;
	}
	return res;
}//x^n%p
const ll Inf = 3023372036854775807;
const int inf = 1500000000;
#define int long long
//----------------------------------------------------
int n, m;
H a[200000];
signed main() {
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		cin >> a[i].y >> a[i].x;
	}
	sort(a, a + m);
	int k = 0;
	int ans = 0;
	for (int i = 0; i < m; i++) {
		if (k < a[i].y + 1) {
			ans++;
			k = a[i].x;
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")
using namespace std;

using ll = long long;
using ull = unsigned long long;
using ld = long double;

#define forn(i, a, n) for (int i = (int)(a); i < (int)(n); ++i)
#define ford(i, a, n) for (int i = (int)(n) - 1; i >= (int)(a); --i)
#define fore(i, a, n) for (int i = (int)(a); i <= (int)(n); ++i)
#define all(a) (a).begin(), (a).end()
#define fs first
#define sn second
#define trace(a)\
    for (auto i : a) cerr << i << ' ';\
    cerr << '\n'
#define eb emplace_back

#ifndef M_PI
const ld M_PI = acos(-1.0);
#endif

template<typename T>
inline void setmax(T& a, T b) {
    if (a < b) a = b;
}

template<typename T>
inline void setmin(T& a, T b) {
    if (a > b) a = b;
}

const ld eps = 1e-9;
const int INF = 2000000000;
const ll LINF = 1ll * INF * INF;
const ll MOD = 1000000007;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); 
    srand((unsigned)chrono::high_resolution_clock::now().time_since_epoch().count());
    int n;
    cin >> n;
    vector<int> a(n);
    forn(i, 0, n) cin >> a[i];
    int mn = INF, mx = -INF;
    forn(i, 0, n) setmin(mn, a[i]);
    forn(i, 0, n) setmax(mx, a[i]);
    vector<pair<int, int>> ans;
    if (abs(mn) > abs(mx)) {
        int pos = find(all(a), mn) - a.begin();
        forn(i, 0, n) if (a[i] > 0) ans.eb(pos, i);
        ford(i, 1, n) ans.eb(i, i - 1);
    } else {
        int pos = find(all(a), mx) - a.begin();
        forn(i, 0, n) if (a[i] < 0) ans.eb(pos, i);
        forn(i, 1, n) ans.eb(i - 1, i);
    }
    cout << ans.size() << '\n';
    for (auto p : ans) cout << 1 + p.fs << ' ' << 1 + p.sn << '\n';
}


Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <queue>
#define MOD (1000000007l)
#define rep(i, n) for(long i = 0; i < n; i++)

using namespace std;

int main(void) {
  long a, b, c, d, e, k;
  cin >> a >> b >> c >> d >> e >> k;
  if (k < e - a) {
    cout << ":(" << endl;
  } else {
    cout << "Yay!" << endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
int main(){
  int n,a,b,c,d,e,f;
  scanf("%d %d %d %d %d",&n,&a,&b,&c,&d);
  e=a/c;
  if(a%c)e++;
  f=b/d;
  if(b%d)f++;
  if(e<f)e=f;
  printf("%d\n",n-e);
  return 0;
}

Measured memory_bytes: 596
def gcd(a, b):
    if a < b:
        a, b = b, a
    while(b != 0):
        a, b = b, a%b
    return a

N = int(input())
A = list(map(int,input().split()))
ans = A[0]
for i in range(1,N):
    ans = gcd(ans, A[i])
print(ans)

Measured memory_bytes: 14224
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <cmath>
#include <map>
using namespace std;
#define MOD 1000000007
#define ADD(X,Y) ((X) = ((X) + (Y)%MOD) % MOD)
typedef long long i64; typedef vector<int> ivec; typedef vector<string> svec;

char S[101010];
int K;
int L;

int to_a(char c)
{
	if (c == 'a') return 0;
	return 'z' - c + 1;
}

int main()
{
	scanf("%s%d", S, &K);
	L = strlen(S);
	for (int i = 0; i < L - 1; ++i) {
		if (to_a(S[i]) <= K) {
			K -= to_a(S[i]);
			S[i] = 'a';
		}
	}
	K %= 26;
	for (int i = 0; i < K; ++i) {
		S[L - 1]++;
		if (S[L - 1] > 'z') S[L - 1] = 'a';
	}
	puts(S);

	return 0;
}


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

#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)
#define fst first
#define snd second
#define pb push_back
#define ALL(x) x.begin(),x.end()
#define EPS (1e-9)
#define equals(a,b) (fabs((a)-(b))<EPS)

using namespace std;

bool LT(double a,double b) { return !equals(a,b) && a < b; }
bool LTE(double a,double b) { return equals(a,b) || a < b; }

const string YES = "";
const string NO  = "";

typedef long long ll;

void solve() {

}

int main() {
  int n;
  cin >> n;
  vector<int> d(n);
  rep(i,n) cin >> d[i];
  sort(ALL(d));
  int m = n / 2;
  if( m-1 >= 0 && d[m] == d[m-1] ) {
    puts("0");
    return 0;
  }
  cout << d[m] - d[m-1] << endl;
  return 0;
}


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

  
int32_t main()
{


	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
    int n;
    cin>>n;
 map<string ,int> mp;

for(int  i=0;i<n;i++)
{
    string s;
    cin>>s;
   sort(s.begin(),s.end());
mp[s]++;

}
int count=0;
for(auto it=mp.begin();it!=mp.end();it++)
{
    int x=it->second;
    if(x>1)
    count+=(x*(x-1))/2;
}
cout<<count;
}


Measured memory_bytes: 11264
var
	f,a:array[0..100010] of longint;
	n,i,j,k:longint;
function g(x,y:longint):longint;
begin
	g:=abs(a[x]-a[y]);
end;
function min(x,y:longint):longint;
begin
	if x<y then exit(x) else exit(y);
end;
begin
	readln(n,k);
	for i:=1 to n do read(a[i]);
	f[1]:=0;
	for i:=2 to n do
	begin
		f[i]:=2147483640;
		for j:=1 to k do 
			if i-j>0 then f[i]:=min(f[i],f[i-j]+g(i,i-j));
	end;
	writeln(f[n]);
end.

Measured memory_bytes: 896
import sys
from heapq import heappop, heappush

n, m = list(map(int, input().split()))
links = [set() for _ in range(n)]
lines = sys.stdin.readlines()
for line in lines[:-1]:
    u, v = list(map(int, line.split()))
    u -= 1
    v -= 1
    links[u].add(v)
s, t = list(map(int, lines[-1].split()))
s -= 1
t -= 1

q = [(0, s)]
visited = set()
ans = -1
while q:
    c, v = heappop(q)
    key = (c % 3, v)
    if key in visited:
        continue
    visited.add(key)
    if v == t and c % 3 == 0:
        ans = c // 3
        break
    c += 1
    d = c % 3
    for u in links[v]:
        new_key = (d, u)
        if new_key in visited:
            continue
        heappush(q, (c, u))

print(ans)


Measured memory_bytes: 64268
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (int)(n); ++i)
#define all(x) x.begin(),x.end()
#define ln '\n'
const long double PI = acos(-1.0L);
const long long MOD = 1000000007LL;
// const long long MOD = 998244353LL;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
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() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int A,B,Q; cin >> A >> B >> Q;
    vector<ll> S(A+2),T(B+2),x(Q);
    rep(i,A) cin >> S[i+1];
    rep(i,B) cin >> T[i+1];
    S[0] = T[0] = -1e11;
    S[A+1] = T[B+1] = 1e11;
    rep(i,Q) cin >> x[i];

    rep(i,Q) {
        int p = lower_bound(all(S),x[i]) - S.begin();
        int q = lower_bound(all(T),x[i]) - T.begin();

        ll res = 1e18;
        chmin(res,S[p] - x[i] + abs(S[p] - T[q]));
        chmin(res,T[q] - x[i] + abs(S[p] - T[q]));
        chmin(res,abs(S[p-1] - x[i]) + abs(S[p-1] - T[q]));
        chmin(res,abs(T[q] - x[i]) + abs(S[p-1] - T[q]));
        chmin(res,abs(S[p] - x[i]) + abs(S[p] - T[q-1]));
        chmin(res,abs(T[q-1] - x[i]) + abs(S[p] - T[q-1]));
        chmin(res,abs(S[p-1] - x[i]) + abs(S[p-1] - T[q-1]));
        chmin(res,abs(T[q-1] - x[i]) + abs(S[p-1] - T[q-1]));
        cout << res << ln;
    }
}

Measured memory_bytes: 3712
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <cstring>
#include <numeric>
#include <algorithm>
#include <fstream>
#include <functional>
#include <array>
#include <map>
#include <queue>
#include <time.h>
#include <limits.h>
#include <set>
#include <stack>
#include <random>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#define rep(i,s,n) for(int i = (s); (n) > i; i++)
#define REP(i,n) rep(i,0,n)
#define RANGE(x,a,b) (min(a,b) <= (x) && (x) <= max(a,b)) //hei
#define DUPLE(a,b,c,d) (RANGE(a,c,d) || RANGE(b,c,d) || RANGE(c,a,b) || RANGE(d,a,b))
#define INCLU(a,b,c,d) (RANGE(a,c,d) && (b,c,d))
#define PW(x) ((x)*(x))
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define MODU 1000000007LL
#define bitcheck(a,b)   ((a >> b) & 1)
#define bitset(a,b)      ( a |= (1 << b))
#define bitunset(a,b)    (a &= ~(1 << b))
#define MP(a,b) make_pair((a),(b))
#define Manh(a,b) (abs((a).first-(b).first) + abs((a).second - ((b).second))
#define pritnf printf
#define scnaf scanf
#define itn int
#define PI 3.141592653589


#define izryt bool
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
template<typename A, size_t N, typename T>
void Fill(A(&array)[N], const T& val) {
	std::fill((T*)array, (T*)(array + N), val);
}
pll Dir[4] = {
	{ -1 ,0 },{ 0 , 1 },{ 1 ,0 },{ 0 ,-1 }
};

//[a, b)
#define Getsum(ar, a,b) (ar[b] - ar[a])
#define chmax(a,b) a = max(a,b)
#define chmin(a,b) a = min(a,b)

struct Edge {
	int from, to;
	ll w;
	bool operator<(const Edge& rhs) const {
		return MP(w, MP(from, to)) < MP(rhs.w, MP(rhs.from, rhs.to));
	}

};
typedef vector<vector<Edge>> Graph;

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

ll factorial(ll n) {//階乗
	ll ret = 1;
	rep(i, 1, n + 1)
		ret = (ret * i) % MODU;

	return ret;
}

ll mod_pow(ll x, ll n, ll mod) {
	ll res = 1;
	while (n > 0) {
		if (n & 1) res = res * x % mod;
		x = x * x % mod;
		n >>= 1;
	}
	return res;
}
ll divmod(ll a, ll b, ll m) { // a/b(mod m)
								  // a/b (mod m)
								  // a*b^-1
								  // b^-1 * b = 1
								  // b^(m-1) = 1 
								  // b^(m-2) * b = 1
								  // b^-1 = b^(m-2)

								  // a/b = a * b^(m-2)

	return (a * 1LL * mod_pow(b, m - 2, m)) % m;
}
ll ncr(ll n, ll r) {
	return divmod(factorial(n), (factorial(r) * (factorial(n - r))) % MODU, MODU);
}


signed main() {
	int n, p;
	string s;
	cin >> n >> p >> s;

	ll ans = 0;
	int base = 1;
	map<int, int> cou;
	cou[0]++;
	reverse(s.begin(), s.end());
	int csum = 0;
	REP(i, n) {
		if(p == 2 || p == 5 ){
          if((s[i] - '0') % p == 0)
			ans += (n-i);
            
        }
      else{
		csum += base * (s[i] - '0');
		base = (base * 10) % p;
		csum %= p;
		ans += cou[csum];
		cou[csum]++;
      }
	}
	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 900
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<queue>
#include<set>
using namespace std;
typedef long long LL;
const int N=2e5+100;
int gi() {
	int w=0;bool q=1;char c=getchar();
	while ((c<'0'||c>'9') && c!='-') c=getchar();
	if (c=='-') q=0,c=getchar();
	while (c>='0'&&c <= '9') w=w*10+c-'0',c=getchar();
	return q? w:-w;
}
int head[N],nxt[N],to[N],w[N];
int c[3],col[N],e;
bool vis[N],flag;
inline void dfs(int k,int d) {
	c[col[k]=d]++;vis[k]=true;
	for (int i=head[k];i;i=nxt[i],e++)
		if (!vis[to[i]]) dfs(to[i],(d+w[i])%3);
		else if ((d+w[i])%3!=col[to[i]]) flag=false;
}
int main()
{
	int n=gi(),m=gi(),i,a,b,tot=0;LL ans=0;
	for (i=1;i<=m;i++) {
		a=gi(),b=gi();
		to[++tot]=b,nxt[tot]=head[a],head[a]=tot,w[tot]=1;
		to[++tot]=a,nxt[tot]=head[b],head[b]=tot,w[tot]=2;
	}
	for (i=1;i<=n;i++)
		if (!vis[i]) {
			c[0]=c[1]=c[2]=e=0;
			flag=true;
			dfs(i,0);
			if (flag)
				if (c[0]&&c[1]&&c[2])
					ans+=1LL*c[0]*c[1]+1LL*c[0]*c[2]+1LL*c[1]*c[2];
				else ans+=e>>1;
			else ans+=1LL*(c[0]+c[1]+c[2])*(c[0]+c[1]+c[2]);
		}
	printf("%lld\n",ans);
	return 0;
}


Measured memory_bytes: 5504
import sys
from collections import Counter

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def main():
    N, M = map(int, readline().split())
    A = list(map(int, readline().split()))
    BC = list(map(int, read().split()))

    counter = Counter(A)
    for b, c in zip(BC[::2], BC[1::2]):
        counter[c] += b

    ans = cnt = 0
    for n in sorted(counter.keys(), reverse=True):
        if cnt + counter[n] >= N:
            ans += n * (N - cnt)
            break
        else:
            ans += n * counter[n]
            cnt += counter[n]

    print(ans)
    return


if __name__ == '__main__':
    main()


Measured memory_bytes: 107740
#include<stdio.h>
#include<string.h>

int main(void)
{
    char deck[200], str1[200], str2[200];
    int h, m, i, j, n, length;
    
    while(1){
        scanf("%s", &deck);
        if(strcmp(deck, "-") == 0){
            break;
        }
        length = strlen(deck);
        scanf("%d", &m);
        for(i=0;i<m;i++){
            n = 0;
            scanf("%d", &h);
            for(j=0;j<length;j++){
                if(j < h){
                    str1[j] = deck[j];
                    str1[j+1] = '\0';
                }
                else{
                    str2[n] = deck[j];
                    str2[n+1] = '\0';
                    n++;
                }
            }
            strcat(str2, str1);
            strcpy(deck, str2);
        }
        printf("%s\n", deck);
    }
    return 0;
}

Measured memory_bytes: 600
#include<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) for(int i = 0; i < (b); i++)
#define all(a) (a).begin(), (a).end()
#define show(x)  cerr << #x << " = " << (x) << endl;
//const int INF = 1e8;
using namespace std;

class StronglyConnectedComponents{
	private:
		vector<bool> used;
		vector<int> vs; //帰りがけ順の並び
		void dfs(int v){
			used[v] = true;
			rep(i,g[v].size()){
				if(not used[g[v][i]]) dfs(g[v][i]);
			}
			vs.emplace_back(v);
		}
		void rdfs(int v, int k){
			used[v] = true;
			cmp[v] = k;
			rep(i,rg[v].size()){
				if(not used[rg[v][i]]) rdfs(rg[v][i], k);
			}
		}
	public:
		typedef vector<vector<int>> graph;
		const int v; // 頂点数
		int nv; // SCCした後の頂点数
		graph g, rg; // グラフ、辺が逆になったグラフ
		vector<int> cmp; //属する強連結成分のトポロジカル順序

		StronglyConnectedComponents(int v) : used(v), v(v), g(v), rg(v), cmp(v) { }

		void addEdge(int from, int to){
			g[from].emplace_back(to);
			rg[to].emplace_back(from);
		}
		int solve(){ // 強連結成分分解をしたあとのグラフの頂点数を返す
			fill(all(used),0);
			vs.clear();
			rep(i,v){
				if(not used[i]) dfs(i);
			}
			fill(all(used),0);
			int k = 0;
			for(int i = vs.size() - 1; i >= 0; i--){
				if(not used[vs[i]]) rdfs(vs[i], k++);
			}
			return nv = k;
		}
		graph getCssGraph(vector<vector<int>>& node){
			node = vector<vector<int>>(nv); // node[i]:=SCCによって頂点iに同一視された頂点
			graph res(nv); // CSSしたあとのグラフ
			rep(i,v){
				node[cmp[i]].emplace_back(i);
				for(auto to : g[cmp[i]]){
					if(cmp[i] == cmp[to]) continue;
					res[cmp[i]].emplace_back(cmp[to]);
				}
			}
			return res;
		}
		void out(){
			rep(i,v){ cout << cmp[i] << ' '; } cout << endl;
		}
};

void dfs(int pos, vector<bool>& used, vector<vector<int>>& g){
	used[pos] = true;
	for(auto to : g[pos]){
		if(used[to]) continue;
		dfs(to, used, g);
	}
}

int main(){
	int n;
	while(cin >> n,n){
		StronglyConnectedComponents scc(n);
		vector<double> p(n); // 寝坊する確率
		rep(i,n){
			int m;
			cin >> p[i] >> m;
			rep(j,m){
				int a;
				cin >> a;
				scc.addEdge(i, a - 1);
			}
		}
		scc.solve();

		vector<vector<int>> node;
		StronglyConnectedComponents::graph g = scc.getCssGraph(node);
		double ans = 1;

		vector<bool> used(n,0);
		rep(i,scc.nv){
			if(used[node[i][0]]) continue;

			double tmp = 1.00;
			rep(j,node[i].size()){
				tmp *= p[node[i][j]];
			}
			ans *= 1.00 - tmp;
			dfs(node[i][0], used, scc.g);
		}
		cout << fixed << setprecision(9) << ans << endl;
	}
}



Measured memory_bytes: 3412
# -*- coding: utf-8 -*-

K=[1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]

a = int(input())

num = a-1
print(K[num])

Measured memory_bytes: 2940
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace _20170409_AOJ
{
    class ALDS1_1A
    {
        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            int[] iArr = Console.ReadLine().Split(' ').Select(s => int.Parse(s)).ToArray();

            InsertionSort(iArr, n);

            Console.ReadLine();
        }

        static void InsertionSort(int[] _arr, int _n)
        {
            for (int i = 1; i < _n; i++)
            {
                WriteArr(_arr);
                int v = _arr[i];
                int j = i - 1;
                while (j >= 0 && _arr[j] > v)
                {
                    _arr[j + 1] = _arr[j];
                    j--;
                }
                _arr[j + 1] = v;
            }
            WriteArr(_arr);
        }

        static void WriteArr(int[] _arr)
        {
            int len = _arr.Length;
            if (len > 0)
            {
                Console.Write(_arr[0]);
            }

            if (len > 1)
            {
                for (int i = 1; i < len; i++)
                {
                    Console.Write(string.Format(" {0}", _arr[i]));
                }
            }
            Console.Write("\r\n");
        }
    }
}

Measured memory_bytes: 9524
#include<bits/stdc++.h>
#define   ll          long long int
#define   sz          200010
#define   sc(a)       scanf("%lld",&a)
#define   sc2(a,b)    scanf("%lld %lld",&a,&b)
#define   py          printf("Yes\n")
#define   pn          printf("No\n")
using namespace std;


ll num[sz];



int main()
{

    string a,b,s;

    cin>>a>>b;

    a+=b;

    ll l,i,j,n=0,d,k,p;

    for(i=0;i<a.length();i++)
    {
        p=a[i]-'0';
        n=n*10+p;
    }

    k=sqrt(n);

    if(k*k==n)py;
    else
        pn;


    return 0;
}



Measured memory_bytes: 256
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <climits>
#include <queue>

using namespace std;

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

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

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);
const int INF = 1e8;

string f(string s, string t){
  for(int i=min(SZ(t),SZ(s));i>=1;--i){
	if(t.substr(0,i) == s.substr(SZ(s)-i,i)){
	  return s + t.substr(i);
	}
  }
  return s+t;
}

string le(string& s, string& t){
  if(SZ(s) < SZ(t)) return s;
  else if(SZ(s) > SZ(t)) return t;
  return min(s,t);
}

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

  int N;
  while(cin>>N,N){
	VS vs(N); REP(i,N) cin >> vs[i];
	SORT(vs);
	vs.erase(unique(ALL(vs)), vs.end());
	N = SZ(vs);
	vector<bool> use(N, true);
	REP(i,SZ(vs)){
	  REP(j,SZ(vs)){
		if(i == j) continue;
		if(vs[i].find(vs[j]) != string::npos)
		  use[j] = false;
		string cat = f(vs[i], vs[j]);
		if(cat == vs[i])
		  use[j] = false;
		if(cat == vs[j])
		  use[i] = false;
	  }
	}
	{
	  VS vs_;
	  REP(i,N) if(use[i]) vs_.PB(vs[i]);
	  vs = vs_;
	}

	N = SZ(vs);
	string sum[1<<10][11];
	REP(i,N) sum[1<<i][i] = vs[i];

	REP(b,1<<N) REP(i,N){
	  if(!((b>>i) & 1)) continue;
	  for(int j=0;j<N;++j){
		if((b>>j) & 1) continue;
		string& s = sum[b|(1<<j)][j];
		string cat = f(sum[b][i], vs[j]);
		if(s != "")
		  s = le(s, cat);
		else s = cat;
	  }
	}  

	string res(1000, 127);
	REP(i,N)
	  res = le(res, sum[(1<<N)-1][i]);
	
	cout << res << endl;
  }

  return 0;
}

Measured memory_bytes: 1720
#include <iostream>
#include <stdio.h>
#include <bits/stdc++.h>
#include <queue>
#include <math.h>
#define ll long long
#define INF 100000000000
#define N 10000000
using namespace std;

int main(void){
    for (int i=1; i<=5; i++){
        int p;
        cin>>p;
        if(i!=p){
            cout<<i<<endl;
            return 0;
        }
    }
}

Measured memory_bytes: 3568
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>

using namespace std;
using boost::multiprecision::cpp_int;

typedef long long ll;
typedef pair<ll, ll> pll;

const ll INF = 1e17;
const ll MOD = 1e9+7;

int main() {
    // input, ready
    ll H,W;
    cin >> H >> W;

    if (H==1 || W==1) cout << 1 << endl;
    else cout << (H*W+1)/2 << endl;

    return 0;
}


Measured memory_bytes: 256
#ifndef HOME
#pragma GCC optimize "-O3"
#endif
 
#include <bits/stdc++.h>
 
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using namespace std;
 
const int C = 1000 * 1000 * 1000;
 
int main() {
    ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    ll x;
    cin >> x;
    cout << "0 0 ";
    ll d = (C - x % C) % C;
    ll y = x + d;
    cout << C << " " << d << " ";
    cout << 1 << " " << y / C << "\n";
    return 0;
}
 

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
struct Fast {
    Fast() {
        cin.tie(0);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(20);
    }
} fast;
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
long long mod = 1000000007;
#define REP(i, n) for (long long i = 0; i < (n); i++)
#define rep(i, a, n) for (long long i = a; i < (n); i++)
long long modpow(long long m, long long n, long long modvalue) {
    if (n == 0) return 1;
    if (n % 2 == 0) {
        long long t = modpow(m, n / 2, modvalue);
        return t * t % modvalue;
    } else {
        return modpow(m, n - 1, modvalue) * m % modvalue;
    }
}
bool bitcheck(ll x, ll y) { return (x >> y) & 1; }

template <typename A, size_t N, typename T> void Fill(A (&array)[N], const T& val) {
    std::fill((T*)array, (T*)(array + N), val);
}
// long long mod = 998244353;

long long moddiv(long long a, long long b, ll modvalue) { return (a * modpow(b, mod - 2, modvalue)) % modvalue; }

const ll INF = 1LL << 60;

void print_binary(long long a) {
    for (int i = 31; i >= 0; i--) {
        cout << (a >> i & 1);
    }
    cout << endl;
}

ll nCkmod(ll n, ll k, ll modvalue) {
    ll numera = 1;
    for (int i = n; i > n - k; i--) {
        numera *= i;
        numera %= modvalue;
    }
    ll denomi = 1;
    REP(i, k) {
        denomi *= (i + 1);
        denomi %= modvalue;
    }
    return moddiv(numera, denomi, modvalue);
}
map<ll, ll> cnt;
void primeFactors(long long n) {
    while (n % 2 == 0) {
        cnt[2]++;
        n = n / 2;
    }
    for (int i = 3; i <= sqrt(n); i = i + 2) {
        while (n % i == 0) {
            cnt[i]++;
            n = n / i;
        }
    }
    if (n > 2) {
        cnt[n]++;
    }
}
int main() {
    ll n;
    cin >> n;
    string s;
    cin >> s;
    ll j = 0;
    ll ans = 0;
    REP(i, n) {
        while (j <= n - 1 && s[n - 1 - j] == 'W') {
            j++;
        }
        if (s[i] == 'W') {
            if (i > n - 1 - j) {
                break;
            }
            ans++;
            swap(s[i], s[n - 1 - j]);
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 3680
#include<iostream>
#include<algorithm>
int main() {
	bool a[31];
	int input;
	for (int i = 0; i < 31; ++i) {
		a[i] = false;
	}
	for (int i = 0; i < 28; ++i) {
		std::cin >> input;
		a[input] = true;
	}
	for (int i = 1; i < 31; ++i) {
		if (a[i] == false) {
			std::cout << i << std::endl;
		}
	}
	return 0;
}

Measured memory_bytes: 3112
#include <cstdio>

int main(){
    int n,m;
    scanf("%d %d",&n,&m);
    int a[m],b[m],c[n];
    for(int i = 0; i < m; i++){
        scanf("%d %d",&a[i],&b[i]);
    }
    for(int i = 0; i < n; i++){
        c[i] = 0;
    }
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(i + 1 == a[j]){
                c[i]++;
            }
            if(i + 1 == b[j]){
                c[i]++;
            }
        }
    }
    for(int i = 0; i < n; i++){
        printf("%d\n",c[i]);
    }

    return 0;
}

Measured memory_bytes: 504
n,m,x = map(int,input().split())
a = [int(i) for i in input().split()]

if a[0] < x < a[m-1]:
    for i in range(1,m):
        if x < a[i]:
            ans = min(i,m-i)
            break
else:
    ans = 0

print(ans)

Measured memory_bytes: 3060
#import<iostream>
#import<algorithm>
using namespace std;int*p,P[1001],*q,Q[1<<20],n,m,v,*i,*j;main(){for(;cin>>n>>m,n;cout<<v<<endl){for(p=P+1;n--;v=0)cin>>*p++;sort(P,p);p=unique(i=P,p);for(q=Q;i-p;++i)for(j=P;j<i+1;)*q++=*j+++*i;sort(Q,q);q=unique(i=Q,q);for(*q++=m+1;*i<=m;++i)v=max(v,*i+upper_bound(Q+1,q,m-*i)[-1]);}}

Measured memory_bytes: 2832
#include<iostream>
using namespace std;
int main(){
	int a,b,c,d;
	cin>>a;
	b=a/3600;
	c=(a-b*3600)/60;
	d=a-b*3600-c*60;
	cout<<b<<":"<<c<<":"<<d<<endl;
	return 0;
}

Measured memory_bytes: 1168
while 1:
    n,m,l=map(int,input().split())
    if n==-1 and m==-1 and l==-1:
        break
    elif n==-1 or m==-1:
        print("F")
    elif n+m>=80:
        print("A")
    elif n+m>=65:
        print("B")
    elif n+m>=50:
        print("C")
    elif n+m>=30:
        if l>=50:
            print("C")
        else:
            print("D")
    else:
        print("F")


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

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

using namespace std;
bool isOK(vector<int> &a){
    rep(i,a.size()-1){
        if( a[i]> a[i+1])return false;
    }
    return true;
}
int main(void){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    int N;
    cin >> N;
    vector<int> P(N),t;
    rep(i,N) cin >> P[i];
    rep(i,N)rep(j,N){
        t = P;
        swap(t[i],t[j]);
        if(isOK(t)){
            cout << "YES" << endl;
            return 0;
        }
    }
    cout << "NO" << endl;
}

Measured memory_bytes: 256