akhauriyash/Code-Regression huggingface dataset:
h,w=map(int,input().split())
s=[input()+'#' for i in range(h)]
s.append('#'*(w+1))
h1=[[0]*(w+1) for i in range(h+1)]
w1=[[0]*(w+1) for i in range(h+1)]
for j in range(h):
  r=0
  for i in range(w+1):
    if s[j][i]=='#':
      for k in range(i-r,i+1):
        h1[j][k]=r
      r=0
      h1[j][i]=0
    else:
      r+=1
for j in range(w):
  r=0
  for i in range(h+1):
    if s[i][j]=='#':
      for k in range(i-r,i+1):
        w1[k][j]=r
      r=0
      w1[i][j]=0
    else:
      r+=1
ans=0
for i in range(h):
  for j in range(w):
    ans=max(ans,h1[i][j]+w1[i][j]-1)
print(ans)

Measured memory_bytes: 123352
#include<iostream>
#include<cstdio>

int main(){
  int a,b,c,d,e;
  std::scanf("%d %d %d %d %d",&a,&b,&c,&d,&e);
  //std::cout << a << b << c << d << e << std::endl;
  int flag = 0,temp;
  do{
    flag = 0;
    if(a<b){
      temp = a;
      a = b;
      b = temp;
      flag = 1;
    }
    if(b<c){
      temp = b;
      b = c;
      c = temp;
      flag = 1;
    }
    if(c<d){
      temp = c;
      c = d;
      d = temp;
      flag = 1;
    }
    if(d<e){
      temp = d;
      d = e;
      e = temp;
      flag = 1;
    }
  }while(flag);
  std::printf("%d %d %d %d %d\n",a,b,c,d,e);
}

Measured memory_bytes: 3144
using System;
using System.Linq;

namespace AIZU {
	class Program {
		static int cin() { return cin(-1); }
		static int cin(int D) {
			string s = Console.ReadLine();
			if (string.IsNullOrEmpty(s))
				return D;
			return int.Parse(s);
		}
		static void print(object j) { Console.WriteLine(j.ToString()); }
		static void print(string j) { Console.WriteLine(j); }

		static void Main(string[] args) {
			var n = cin();
			for (int ingh = 0; ingh <n; ingh++) {
				char[] right = Console.ReadLine().ToCharArray();
				right=right.OrderByDescending(i=>i).ToArray();
				char[] rev = right.Reverse().ToArray();

				int max = int.Parse(new string(right)),
					min = int.Parse(new string(rev));
				print(max - min);
			}
		}
	}
}

Measured memory_bytes: 10008
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

namespace AtCoder.D
{
    public class Program
    {
        public static void Main() { var r = GetResult(); Debug.WriteLine(r); Console.Write(r); }

        private static object GetResult()
        {
            var (N, M) = Read2Longs();

            var gcd = 0L;

            foreach (var cd in GetAll(M).OrderBy(x => x))
            {
                if (M / cd >= N)
                {
                    gcd = cd;
                }
                else
                {
                    break;
                }
            }

            return gcd;
        }

        public static List<long> GetAll(long n)
        {
            var l = new List<long>();
            var sqrt = Math.Sqrt(n);
            for (long d = 1; d <= sqrt; d++)
            {
                if (n % d == 0)
                {
                    l.Add(d);
                    if (n / d != d)
                    {
                        l.Add(n / d);
                    }
                }
            }
            return l;
        }

        #region Console.Read

        public static string ReadText() { return Console.ReadLine(); }
        public static List<string> ReadTexts() { return Console.ReadLine().Split(' ').ToList(); }
        public static long ReadLong() { return long.Parse(Console.ReadLine()); }
        public static (long, long) Read2Longs() { var ls = ReadLongs(); return (ls[0], ls[1]); }
        public static (long, long, long) Read3Longs() { var ls = ReadLongs(); return (ls[0], ls[1], ls[2]); }
        public static (long, long, long, long) Read4Longs() { var ls = ReadLongs(); return (ls[0], ls[1], ls[2], ls[3]); }
        public static (long, long, long, long, long) Read5Longs() { var ls = ReadLongs(); return (ls[0], ls[1], ls[2], ls[3], ls[4]); }
        public static List<long> ReadLongs() { return Console.ReadLine().Split(' ').Select(x => long.Parse(x)).ToList(); }

        #endregion
    }
}


Measured memory_bytes: 28452
import math
class point:
    def __init__(self):
        self.x = 0.0
        self.y = 0.0
 
def koch(n,a,b):
    if n == 0 :
        return
 
    rad = 1.0471975511965976
    s = point()
    t = point()
    u = point()
    tmp = point()
 
    s.x = (2 * a.x + b.x) / 3.0
    s.y = (2 * a.y + b.y) / 3.0
 
    t.x = (2 * b.x + a.x) / 3.0
    t.y = (2 * b.y + a.y) / 3.0
 
    tmp.x, tmp.y = s.x-t.x ,s.y-t.y
    u.x = (tmp.x * math.cos(rad) + tmp.y * math.sin(rad)) + t.x
    u.y = (-tmp.x * math.sin(rad) + tmp.y * math.cos(rad)) + t.y
 
 
    koch(n-1, a, s)
    print(s.x, s.y)
 
    koch(n-1, s, u)
    print(u.x, u.y)
 
    koch(n-1, u, t)
    print(t.x, t.y)
 
    koch(n-1, t, b)
 
    return
 
a = point()
b = point()
a.x, a.y =   0.0, 0.0
b.x, b.y = 100.0, 0.0
n = int(input())

print(a.x, a.y)
koch(n, a, b)
print(b.x, b.y)

Measured memory_bytes: 8072
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
import functools
def s(): return input()
def k(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def X(): return list(input())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 9)
mod = 10**9+7
cnt = 1
ans = 0
inf = float("inf")

a,b = map(str,input().split())

a = Decimal(a)
b = Decimal(b)
print(int(a*b))


Measured memory_bytes: 10244
//Credit - > https://github.com/flash7even/Programming-Contest/blob/master/Code%20Repository/Dynamic%20Programming/Digit%20DP/Digit-DP.cpp
#include <bits/stdc++.h>
using namespace std;

vector<int> num;
int d, k;
int DP[102][12][2];
/// DP[p][c][f] = Number of valid numbers <= b from this state
/// p = current position from left side (zero based)
/// c = number of times we have placed the digit d so far
/// f = the number we are building has already become smaller than b? [0 = no, 1 = yes]

int call(int pos, int cnt, int f){
    if(cnt > k) return 0;

    if(pos == (int)num.size()){
        if(cnt == k) return 1;
        return 0;
    }

    if(DP[pos][cnt][f] != -1) return DP[pos][cnt][f];
    int res = 0;

    int LMT;

    if(f == 0){
        /// Digits we placed so far matches with the prefix of b
        /// So if we place any digit > num[pos] in the current position, then the number will become greater than b
        LMT = num[pos];
    } else {
        /// The number has already become smaller than b. We can place any digit now.
        LMT = 9;
    }

    /// Try to place all the valid digits such that the number doesn't exceed b
    for(int dgt = 0; dgt<=LMT; dgt++){
        int nf = f;
        int ncnt = cnt;
        if(f == 0 && dgt < LMT) nf = 1; /// The number is getting smaller at this position
        if(dgt != d) ncnt++;
        if(ncnt <= k) res += call(pos+1, ncnt, nf);
    }

    return DP[pos][cnt][f] = res;
}

int solve(string bb){
    num.clear();
    for(int i=bb.length()-1; i>=0; --i) {
        num.push_back(bb[i]-'0');
    }
    reverse(num.begin(), num.end());
    /// Stored all the digits of b in num for simplicity
    memset(DP, -1, sizeof(DP));
    int res = call(0, 0, 0);
    return res;
}

int main () {
    string bb;
    cin >> bb >> k;
    int res = solve(bb) - solve("0");
    cout << res << endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const long long Max = 10e7;
typedef long long ll;
int mod = 1000000007;
const int Size = 1000-10;
int main()
{
    int n;
    cin >> n;
    int dp[n+5] = {};
    int A[n+5] = {};
    for(int i = 1; i <= n; i++)
    {
        cin >> A[i];
    }
    dp[n] = 0;
    dp[n-1] = abs(A[n-1] - A[n]);
    for(int i = n-2; i >= 1; i--)
    {
        dp[i] = min(abs(A[i] - A[i+1]) + dp[i+1], abs(A[i]-A[i+2])+dp[i+2]);
    }
    cout << dp[1] << endl;
    return 0;
}


Measured memory_bytes: 1024
import java.util.Scanner;

public class Main {
    
    static final int MAX = 200000;
    static final int SENTINEL = 2000000000;
    static int[] L = new int[MAX/2 + 2];
    static int[] R = new int[MAX/2 + 2];
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[MAX];
        
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        
        long ans = mergeSort(a, n, 0, n);
        
        System.out.println(ans);
    }

    private static long mergeSort(int[] a, int n, int left, int right) {
        // TODO 自動生成されたメソッド・スタブ
        int mid = 0;
        long v1, v2, v3 = 0;
        if (left + 1 < right) {
            mid = (left + right) / 2;
            v1 = mergeSort(a, n, left, mid);
            v2 = mergeSort(a, n, mid, right);
            v3 = merge(a, n, left, mid, right);
            return v1 + v2 + v3;
        }
        return 0;
    }

    private static long merge(int[] a, int n, int left, int mid, int right) {
        // TODO 自動生成されたメソッド・スタブ
        int i, j, k;
        long count = 0;
        int n1 = mid - left;
        int n2 = right - mid;
        
        for (i = 0; i < n1; i++)
            L[i] = a[left + i];
        for (i = 0; i < n2; i++)
            R[i] = a[mid + i];
        L[n1] = R[n2] = SENTINEL;
        i = j = 0;
        
        for (k = left; k < right; k++) {
            if (L[i] <= R[j]) {
                a[k] = L[i++];
            } else {
                a[k] = R[j++];
                count += n1 - i; // = mid + j - k - 1
            }
        }
        return count;
    }
}


Measured memory_bytes: 102312
import math
import sys
from operator import itemgetter

# N, K = map(int, input().split())
# h = list(map(int, input().split()))
# S = [input() for _ in range(H)]
# X = [[0 for j in range(100)] for i in range(200)]


### input
N, M = map(int, input().split())
X = list(map(int, input().split()))
X = sorted(X)
xintval = list(range(0))
for i in range(len(X) - 1):
	xintval.append(X[i+1] - X[i])

## solve
xintval = sorted(xintval, reverse = False)
if (N >= M):
	print(0)
else:
	sum = 0
	for i in (range(M - N)):
		sum += xintval[i]
	print(sum)


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

int main(){
  int A, B;
  cin >> B >> A;
  
  int n1, n2, n3, n4;
  
  n1 = A + (B - 1);
  n2 = A - (B - 1);
  
  n3 = min(n1, n2);
  n4 = max(n1, n2);
  
  for (int i = n3; i < n4 + 1; i++) {
    cout << i << " ";
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int X,Y;
  cin >> X >> Y;
  for(int i=0;i<=X;i++){
    if(i*2+(X-i)*4==Y){
      cout << "Yes" << endl;
      return 0;
    }
  }
  cout << "No" << endl;
}

Measured memory_bytes: 3636
#include <cstdio>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;

int main()
{
    int n;
    scanf("%d", &n);
    vector<int> a(n);
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &a[i]);
    }

    sort(a.begin(), a.end(), greater<int>());

    /*
    for (int i = 0; i < a.size(); i++)
    {
        printf("%d, ", a[i]);
    }
    printf("\n");
    */

    int i = 1;
    long long int b = -1, c = -1;

    while (i < n)
    {
        if (a[i] == a[i - 1])
        {
            b = a[i];
            break;
        }
        i++;
    }

    if (b == -1)
    {
        printf("0\n");
        return 0;
    }

    i += 2;

    while (i < n)
    {
        if (a[i] == a[i - 1])
        {
            c = a[i];
            break;
        }
        i++;
    }

    if (c == -1)
    {
        printf("0\n");
        return 0;
    }

    printf("%lld\n", b * c);

    return 0;
}

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

int main(){
  int N,M,C;
  int B[M],A[M],sum,res;
  
  res = 0;
  cin >> N >> M >> C;
  for(int i=0;i<M;i++){
    cin >> B[i];
  }
  for(int j=0;j<N;j++){
    sum = C;
    for(int i=0;i<M;i++){
      cin >> A[i];
      sum += B[i]*A[i];
    }
    if(sum>0){
      res++;
    }
  }
  
  cout << res << endl;
  return 0;
}

Measured memory_bytes: 2304
MOD=10**9+7
cnt=0; sum=0; prev=nil; can=true; h=Hash.new(0)
def gs() gets.chomp end
def gi() gets.to_i end
def gsmi() gets.chomp.split.map(&:to_i) end

def desc(ar) ar.sort{|x,y|y<=>x} end##
def min(a,b) a<=b ? a : b end
def max(a,b) a>=b ? a : b end
def sum(ar) ar.inject(:+) end

def C(a,b) b==0||a==b ? 1 : (b=a-b if a/2<b;(a-b+1..a).inject(:*)/(1..b).inject(:*)) end

def puts_yesno(can) puts(can ? 'Yes' : 'No') end
def putsend(s) puts s; exit end
def debug(k,v) puts "#{k}:#{v}" end
########### ( ˘ω˘ )ｽﾔｧ… ###########
m1,d1=gsmi
m2,d2=gsmi
puts m1!=m2 ? 1 : 0

Measured memory_bytes: 3836
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repr(i, n) for (int i = (int)(n); i >= 0; i--)
#define REP(i, m, n) for (int i = (int)(m); i <= (int)(n); i++)
#define all(v) v.begin(), v.end()
typedef long long ll;

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

const long long INF = 1LL << 60;

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

  string s1 = "";
  string s2 = "";
  string t1 = "";
  string t2 = "";
  rep(i, s.size()/2){
    s1 += s[i];
    t1 += s[i];
  }
  rep(i, s.size()/2){
    s2 += s[s.size()/2 + (i+1)];
    t2 += s[s.size()/2 + (i+1)];
  }
  reverse(all(t1));
  reverse(all(t2));
  
  cout << (s1 == s2 && s1 == t1 && s2 == t2 ? "Yes" : "No") << endl;

  return 0;
}


Measured memory_bytes: 256
N = int(input())
A = [int(input()) for _ in range(N)]

A.sort()
n = N//2
if N%2 != 0:
    ans1,ans2,ans = 0,0,0
    ar1,ar2 = A[:n],A[n+1:]
    ar = []
    for i in range(n):
        ar.append(ar2[i])
        ar.append(ar1[i])
    ar.append(A[n])
    for i in range(N-1):
        ans1 += abs(ar[i]-ar[i+1])
    ar = [A[n]]+ar[:-1]
    for i in range(N-1):
        ans2 += abs(ar[i]-ar[i+1])
    ans = max(ans1,ans2)
else:
    ans = 0
    ar1,ar2 = A[:n],A[n:]
    ar = []
    for i in range(n):
        ar.append(ar2[i])
        ar.append(ar1[i])
    for i in range(N-1):
        ans += abs(ar[i]-ar[i+1])
 
print(ans)

Measured memory_bytes: 16292
#include<stdio.h>
int main (void)
{ int n,i,j,k;
 long long int ans;
  char s[200020];
  scanf("%s",s);
 // printf("%c",)
  i=0;
  n=0;
 ans=0;
  while(s[n]!='\0'){n++;}
 //printf("%d\n",n);
 for(i=0;i<n;i++)
  //printf("%c",s[i]);
  for(i=0;i<n;i++)
  {
  switch(s[i])
  {
    case '0' :
      ans+=0;
      break;
     case '1' :
      ans+=1;
      break;
     case '2' :
      ans+=2;
      break;
     case '3' :
      ans+=3;
      break;
     case '4' :
      ans+=4;
      break;
     case '5' :
      ans+=5;
      break;
     case '6' :
      ans+=6;
      break;
     case '7' :
      ans+=7;
      break;
     case '8' :
      ans+=8;
      break;
     case '9' :
      ans+=9;
      break;
    }
  }
 if(ans%9==0){printf("Yes\n");}
 else{printf("No");}
  return 0;
}

Measured memory_bytes: 1924
n,k=map(int,input().split())
s=list(input())
j=0
ans=0
cnt=0
for i in range(n):
    if s[i]=="0":
        if i==0 or s[i-1]=="1":
            cnt+=1
    if cnt>k:
        while s[j]=="1":
            j+=1
        while s[j]=="0":
            j+=1
        cnt-=1
    ans=max(ans,i-j+1)

print(ans)

Measured memory_bytes: 4084
/*  ***  In The Name of God ... ***  */ 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;


#define int long long
#define all(v) v.begin() , v.end()
#define pb push_back
#define endl '\n' 
template<typename T> inline bool smin(T &a, const T &b){ return b < a ? a = b,1:0;}
template<typename T> inline bool smax(T &a, const T &b){ return a < b ? a = b,1:0;}

int n ; 

int32_t main()
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n ;
	for ( int i = 1 ; i <= 100 * 1000 + 10 ; i++ ) {
		if ( i * ( i + 1 ) / 2 >= n )
			return cout << i , 0 ;
	}
}


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

int main(){
	char str[1000];
	int num;
	char op[100];
	int i, j;
	int s, f;
	char re[1000];
	char replace[] = "replace";
	char reverse[] = "reverse";
	char print[] = "print";

	scanf("%s", str);
	scanf("%d", &num);

	for(i=0; i<num; i++){
		scanf("%s", op);
		
		if(strcmp(op, replace) == 0){
			scanf("%d %d %s", &s, &f, re);
			for(j=s; j<= f; j++){
				str[j] = re[j-s];
			}
		}	
		else if(strcmp(op, reverse) == 0){
			scanf("%d %d", &s, &f);
			strcpy(re, str);
			for(j=0; j<=f-s; j++){
				str[j+s] = re[f-j];
			}
		}
		else if(strcmp(op, print) == 0){
			scanf("%d %d", &s, &f);
			for(j=s; j<=f; j++){
				printf("%c", str[j]);
			}
			printf("\n");
		}
	}
	
	return 0;

}


Measured memory_bytes: 2100
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
//#include<algorithm>
//#include<cmath>
#include<string>
using namespace std;
int main() {
	int a=0,n;
	char in[3];
	cin >> n;
	while (n--) {
		cin >> in;
		if (in[0] == 'A') a++;
		else {
			a--;
			if (a < 0) {
				cout << "NO" << endl;
				return 0;
			}
		}
	}
	if (a) cout << "NO" << endl;
	else cout << "YES" << endl;
	return 0;
}

Measured memory_bytes: 3088
// In the name of God

#include <bits/stdc++.h>

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int m1, d1, m2, d2;	
	cin >> m1 >> d1 >> m2 >> d2;
	if(m1 != m2) cout << 1;
	else cout << 0;
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdio>
#include <cmath>
#include <set>
using namespace std;
const int maxn=1e5+5;
int t1[maxn*4];
inline int lc(int u){
	return u<<1;
}
inline int rc(int u){
	return u<<1|1;
}
inline void co(int u){
	t1[u]=t1[lc(u)]+t1[rc(u)];
}
inline void insert(int u,int l,int r,int id,int d){
	//cout<<"print insert "<<l<<' '<<r<<' '<<id<<endl;
	if (l==r){
		t1[u]+=d;
		return;
	}
	int mid=(l+r)/2;
	if (id<=mid) insert(lc(u),l,mid,id,d);
	else insert(rc(u),mid+1,r,id,d);
	co(u);
}
inline int kth(int u,int l,int r,int k){
	if (l==r) return l;
	int mid=(l+r)/2;
	if (k-t1[lc(u)]>0) return kth(rc(u),mid+1,r,k-t1[lc(u)]);
	else return kth(lc(u),l,mid,k);
}
int a[maxn],num[maxn],len;
int n,k,m;
vector<int> adj[maxn];
int ufs[maxn];
inline int find(int u){
	if (ufs[u]==u) return u;
	else return ufs[u]=find(ufs[u]);
}
multiset<int> st[maxn];
inline void upd(int u,int x){
	if (st[u].size()<k-1){
		st[u].insert(x);
		return;
	}
	else{
		multiset<int>::iterator it1;
		it1=st[u].begin();
		if ((*it1)<x){
			int tp=(*it1);
			//cout<<"print tp x "<<tp<<' '<<x<<endl;
			st[u].erase(it1);
			st[u].insert(x);
			insert(1,1,len,tp,1);
		}
		else{
			insert(1,1,len,x,1);
		}
	}
}
inline void prints(multiset<int> s){
	for (multiset<int>::iterator it2=s.begin();it2!=s.end();it2++){
		cout<<(*it2)<<' ';
	}
	cout<<endl;
}
inline void join(int u,int v){
	if (u==0||v==0) return ;
	int ru=find(u),rv=find(v);
	if (ru==rv) return;
	if (st[ru].size()<st[rv].size()) swap(ru,rv);
	for (multiset<int>::iterator it2=st[rv].begin();it2!=st[rv].end();it2++){
		upd(ru,(*it2));
	}
	st[rv].clear();
	ufs[rv]=ru;
}
inline void add(int id){
	upd(find(id),a[id]);
	int u=id-1,v=id+1;
	if (v==n+1) v=0;
	if (a[u]<a[id]) u=0;
	if (a[v]<a[id]) v=0;
	if (u==0&&v==0) return;
	join(id,u);
	join(id,v);
}
int main(){
	cin>>n>>k>>m;
	for (int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		num[++len]=a[i];
	}
	if (m==1){
		cout<<"0"<<endl;
		return 0;
	}
	if (k==1){
		sort(a+1,a+n+1);
		int ans=2e9;
		for (int i=1;i+m-1<=n;i++){
			//cout<<"print cur "<<a[i+m-1]<<' '<<a[i]<<endl;
			ans=min(ans,a[i+m-1]-a[i]);
		}
		cout<<ans<<endl;
		return 0;
	}
	sort(num+1,num+len+1);
	len=unique(num+1,num+len+1)-num-1;
	for (int i=1;i<=n;i++){
		int x=lower_bound(num+1,num+len+1,a[i])-num;
		adj[x].push_back(i);
		a[i]=x;
	}
	for (int i=1;i<=n;i++){
		ufs[i]=i;
	}
	int ans=2e9;
	for (int i=len;i>=1;i--){
		for (int j=0;j<adj[i].size();j++){
			int tp=adj[i][j];
			add(tp);
		}
		if(t1[1]>=m) ans=min(ans,num[kth(1,1,len,m)]-num[i]);
	}
	cout<<ans<<endl;
}

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

// {U}{INT,LONG,LLONG}_{MAX,MIN}
#define INF         INT_MAX/3
#define LLINF       LLONG_MAX/3
#define MOD         (1000000007LL)
#define MODA(a, b)  a=((a)+(b))%MOD
#define MODP(a, b)  a=((a)*(b))%MOD
#define inc(i, l, r)   for(int i=(l);i<(r);i++)
#define dec(i, l, r)   for(int i=(r)-1;i>=(l);i--)
#define pb          push_back
#define se          second
#define fi          first
#define mset(a, b)  memset(a, b, sizeof(a))

using LL  = long long;
using G   = vector<vector<int>>;

int di[] = {0, -1, 0, 1};
int dj[] = {1, 0, -1, 0};
// }}}

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


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

char upcase(char &c) {
  return toupper((unsigned char) c);
};

int main () {
  string a,b,c;
  cin >> a >> b >> c;
  cout << upcase(a[0]) << upcase(b[0]) << upcase(c[0]) << endl;
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define mo 1000000007
#define pi 3.1415926535898
#define eps 1e-9 
using namespace std;
long long read(){
    long long xx=0,flagg=1;
    char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-')
        ch=getchar();
    if(ch=='-'){
        flagg=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        xx=xx*10+ch-'0';
        ch=getchar();
    }
    return xx*flagg;
}
void pus(long long xx,long long flagg){
    if(xx<0){
        putchar('-');
        xx=-xx;
    }
    if(xx>=10)
        pus(xx/10,0);
    putchar(xx%10+'0');
    if(flagg==1)
        putchar(' ');
    if(flagg==2)
        putchar('\n');
    return;
}
long long n,q,i,x[200005],a[800005],b[800005],c[800005],p1,max1,max2;
void pus2(int w){
	a[w<<1]+=c[w];
	a[(w<<1)|1]+=c[w];
	b[w<<1]+=c[w];
	b[(w<<1)|1]+=c[w];
	c[w<<1]+=c[w];
	c[(w<<1)|1]+=c[w];
	c[w]=0;
}
void buildtree(int u,int v,int w){
	int mid=(u+v>>1);
	if(u==v){
		if(v==i){
			a[w]=v;
			b[w]=-v;
		}
		else{
			a[w]=1LL*mo*mo+v;
			b[w]=1LL*mo*mo-v;
		}
		return;
	}
	buildtree(u,mid,w<<1);
	buildtree(mid+1,v,(w<<1)|1);
	a[w]=min(a[w<<1],a[(w<<1)|1]);
	b[w]=min(b[w<<1],b[(w<<1)|1]);
}
void atree(int u,int v,int w){
	int mid=(u+v>>1);
	if(u==v){
		max1=min(max1,a[w]-v);
		return;
	}
	pus2(w);
	atree(u,mid,w<<1);
	atree(mid+1,v,(w<<1)|1);
	a[w]=min(a[w<<1],a[(w<<1)|1]);
	b[w]=min(b[w<<1],b[(w<<1)|1]);
}
void xtree(int u,int v,int w){
	int mid=(u+v>>1);
	if(u==v){
		a[w]=min(a[w],max2+v);
		b[w]=min(b[w],max2-v);
		return;
	}
	pus2(w);
	if(p1<=mid) xtree(u,mid,w<<1);
	else xtree(mid+1,v,(w<<1)|1);
	a[w]=min(a[w<<1],a[(w<<1)|1]);
	b[w]=min(b[w<<1],b[(w<<1)|1]);
}
void ytree(int u,int v,int w){
	int mid=(u+v>>1);
	if(u==v){
		max1=min(max1,b[w]);
		return;
	}
	pus2(w);
	if(p1<=mid) ytree(u,mid,w<<1);
	else{
		max1=min(max1,b[w<<1]);
		ytree(mid+1,v,(w<<1)|1);
	}
	a[w]=min(a[w<<1],a[(w<<1)|1]);
	b[w]=min(b[w<<1],b[(w<<1)|1]);
}
void ztree(int u,int v,int w){
	int mid=(u+v>>1);
	if(u==v){
		max1=min(max1,a[w]);
		return;
	}
	pus2(w);
	if(p1<=mid){
		max1=min(max1,a[(w<<1)|1]);
		ztree(u,mid,w<<1);
	}
	else
		ztree(mid+1,v,(w<<1)|1);
	a[w]=min(a[w<<1],a[(w<<1)|1]);
	b[w]=min(b[w<<1],b[(w<<1)|1]);
}
int main(){
	//freopen("camp.in","r",stdin);
	//freopen("camp.out","w",stdout);
	n=read();q=read();x[0]=read();i=read();
	buildtree(1,n,1);
	for(i=1;i<=q;i++){
		x[i]=read();
		p1=x[i];max1=1LL*mo*mo;
		ytree(1,n,1);//<=p1
		max2=max1+x[i];max1=1LL*mo*mo;
		ztree(1,n,1);//>=p1
		max2=min(max2,max1-x[i]);
		c[1]+=abs(x[i]-x[i-1]);
		a[1]+=c[1];
		b[1]+=c[1];
		p1=x[i-1];
		xtree(1,n,1);
	}
	max1=1LL*mo*mo;
	atree(1,n,1);
	pus(max1,2);
	return 0;
}

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

using namespace std;
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)

typedef long long ll;
typedef pair<ll, ll> P;
const ll INF = 1LL<<60;

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

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

ll modpow(ll a, ll n, ll mod) {
  ll res = 1;
  while (n > 0) {
    if (n & 1) res = res * a % mod;
    a = a * a % mod;
    n >>= 1;
  }
  return res;
}

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

  double R;
  cin >> R;

  cout << setprecision(16) << 2 * 3.1415926535 * R << endl;

  return 0;
}


Measured memory_bytes: 3796
use std::io::Read;
use std::collections::HashMap;

fn main() {
    let mut buf = String::new();
    std::io::stdin().read_to_string(&mut buf).unwrap();

    let answer = solve(&buf);

    println!("{}", answer);
}

fn solve(input: &str) -> String {
    let mut iterator = input.split_whitespace();

    let n: usize = iterator.next().unwrap().parse().unwrap();
    let k: i64 = iterator.next().unwrap().parse().unwrap();
    let q: i64 = iterator.next().unwrap().parse().unwrap();

    let mut map: HashMap<usize, i64> = HashMap::new();
    for _i in 0..q {
        let a: usize = iterator.next().unwrap().parse().unwrap();
        *map.entry(a).or_insert(0) += 1;
    }

    let mut answer = Vec::with_capacity(n);
    for i in 1..(n + 1) {
        if k - q + *map.get(&i).unwrap_or(&0) > 0 {
            answer.push("Yes");
        } else {
            answer.push("No");
        }
    }

    return answer.join("\n");
}

#[test]
fn test() {
    assert_eq!(
        solve(
            r"6 3 4
3
1
3
2"
        ),
        "No
No
Yes
No
No
No"
    );
    assert_eq!(
        solve(
            r"6 5 4
3
1
3
2"
        ),
        "Yes
Yes
Yes
Yes
Yes
Yes"
    );
    assert_eq!(
        solve(
            r"10 13 15
3
1
4
1
5
9
2
6
5
3
5
8
9
7
9"
        ),
        "No
No
No
No
Yes
No
No
No
Yes
No"
    );
}


Measured memory_bytes: 12540
#include<bits/stdc++.h>
using namespace std;
vector<int> v[1<<17];int n,k,a,y,t,i;
int s(int x,int p){int r=0;for(t:v[x])r=max(r,s(t,x));a+=++r>=k&&p;return r%k;}
int main(){cin>>n>>k>>y;for(a=(y!=1);cin>>y;v[y-1].push_back(++i));s(0,0);cout<<a;}

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

int main(){

    string s[3];

    rep(i,3){
        cin >> s[i];
    }

    string A="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    string a="abcdefghijklmnopqrstuvwxyz";

    rep(i,3){
        rep(j,26){
            if(s[i][0]==a[j]){
                cout << A[j];
            }
        }
    }

    cout << endl;

    return 0;
}

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

# cities = [[0] * N for i in range(N)]
# print(cities)
cities = {}
 
for a in range(N):
    cities[a+1] = []
# print(cities)
 
for i in range(M):
    i1, i2 = map(int, input().split())
    cities[i1].append(i2)
    cities[i2].append(i1)
# print(cities)
def connected_components(graph):
    seen = set()
    def component(n):
        nodes = set([n])
        while nodes:
            n = nodes.pop()
            seen.add(n)
            nodes |= set(graph[n]) - seen
            yield n
    for n in graph:
        if n not in seen:
            yield component(n)
print(len([list(x) for x in connected_components(cities)])-1)

Measured memory_bytes: 42808
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

func wordScanner(n int) *bufio.Scanner {
	s := bufio.NewScanner(os.Stdin)
	s.Split(bufio.ScanWords)
	b := make([]byte, n)
	s.Buffer(b, n)
	return s
}

func scanInts(s *bufio.Scanner, vals ...*int) {
	for i := range vals {
		s.Scan()
		n, _ := strconv.Atoi(s.Text())
		*vals[i] = n
	}
}

func scanIntSlice(s *bufio.Scanner, n int) []int {
	vals := make([]int, n)
	for i := range vals {
		s.Scan()
		m, _ := strconv.Atoi(s.Text())
		vals[i] = m
	}
	return vals
}

func main() {
	var n int
	s := wordScanner(100)
	scanInts(s, &n)

	a := scanIntSlice(s, n)
	b := scanIntSlice(s, n)
	c := scanIntSlice(s, n-1)

	ans := 0
	j := -1
	for _, i := range a {
		ans += b[i-1]
		if i == j+1 {
			ans += c[j-1]
		}
		j = i
	}
	fmt.Println(ans)
}


Measured memory_bytes: 640
N  = int(input())
A = list(map(int, input().split()))

cur = 1000
stock = 0

for ix in range(N-1):
    if A[ix] < A[ix+1]:
        # buy
        stock += cur // A[ix]
        cur %= A[ix]
    else:
        # A[ix] > A[ix+1]
        # sell
        cur += stock * A[ix]
        stock = 0

if stock != 0:
    cur += stock * A[N-1]
    stock = 0

print(cur)

Measured memory_bytes: 9188
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>

using namespace std;

template<class T>
struct Vec2
{
	Vec2(){}
	Vec2(T _x, T _y) : x(_x), y(_y) {}

	Vec2 operator+(const Vec2& rhs) const { return Vec2(x + rhs.x, y + rhs.y); }
	Vec2 operator-(const Vec2& rhs) const { return Vec2(x - rhs.x, y - rhs.y); }
	Vec2 operator*(T s) const { return Vec2(x*s, y*s); }
	T dot(const Vec2& rhs) const { return x*rhs.x + y*rhs.y; }
	T cross(const Vec2& rhs) const { return x*rhs.y - y*rhs.x; }

	bool operator<(const Vec2& rhs) const
	{
		if (x != rhs.x) return x < rhs.x;
		return y < rhs.y;
	}

	T x;
	T y;
};

typedef Vec2<int> VecI;

template<class T>
T cross(const Vec2<T> &O, const Vec2<T> &A, const Vec2<T> &B)
{
	return (A - O).cross(B - O);
}

int main()
{
	int N;
	scanf("%d", &N);

	static VecI P[100000];
	for (int i = 0; i < N; i++) {
		int x, y;
		scanf("%d %d", &P[i].y, &P[i].x);
	}
	sort(P, P+N);

	static int H[100000];
	int k = 0;
	for (int i = 0; i < N; i++) {
		while (k >= 2 && cross(P[H[k - 2]], P[H[k - 1]], P[i]) < 0) {
			k--;
		}
		H[k++] = i;
	}

	int t = k + 1;
	for (int i = N - 2; i >= 0; i--) {
		while (k >= t && cross(P[H[k - 2]], P[H[k - 1]], P[i]) < 0) {
			k--;
		}
		H[k++] = i;
	}

	printf("%d\n", k-1);
	for (int i = k-1; i > 0; i--) {
		printf("%d %d\n", P[H[i]].y, P[H[i]].x);
	}

	return 0;
}


Measured memory_bytes: 3628
/*ex3_3
ryo_1129*/
#include <stdio.h>

int main(void){
	int N,K,i,division; //変数宣言
	scanf("%d %d",&N,&K); //入力整数NとK進数
	division = N; 
	i = 0; //桁数を数える変数
	//NがK以上の場合、商がK未満になるまで割る
	while(division >= K){
		division = division/K;
		i++ ; //割った回数の記録
	}
	printf("%d\n",i+1);
}

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

#define REP(i,n) for(int i=0;i< (n);i++)
#define REPR(i, n) for(int i = (n);i >= 0;i--)
#define FOR(i, m, n) for(int i = (m);i < (n);i++)
#define FORR(i, m, n) for(int i = (m);i >= (n);i--)
#define SORT(v, n) std::sort(v, v+n);
#define VSORT(v) std::sort(v.begin(), v.end());
#define VRSORT(v) std::sort(v.rbegin(), v.rend());
#define ll long long
#define pb(a) push_back(a)
#define ALL(obj) (obj).begin(),(obj).end()

using namespace std;

const int INF = 99999999;
const ll LINF = 9999999999999;

typedef pair<ll, ll> LP;
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };



char S[1010][1010] = {};
ll cost_map[1010][1010] = {};
ll ch, cw, dh, dw,H,W;

void dfs(ll w, ll h,ll cost) {

	deque<tuple<ll,ll,ll>> uncalced;
	uncalced.emplace_back(make_tuple(w, h, cost));

	while (!uncalced.empty()) {
		tuple<ll, ll, ll> state = uncalced.front();
		uncalced.pop_front();
		w= get<0>(state);
		h = get<1>(state);
		cost = get<2>(state);

		
		cost_map[w][h] = cost;
		if (w == dw && h == dh) return;

		//普通に移動
		if (w + 1 < W && cost_map[w + 1][h] > cost && S[w + 1][h] == '.') uncalced.emplace_front(make_tuple(w + 1, h, cost));  //マス目に移動でき、コストが小さくできる余地がある
		if (w > 0 && cost_map[w - 1][h] > cost && S[w - 1][h] == '.')uncalced.emplace_front(make_tuple(w - 1, h, cost));
		if (h + 1 < H && cost_map[w][h + 1] > cost && S[w][h + 1] == '.')uncalced.emplace_front(make_tuple(w , h+1, cost));
		if (h< H && cost_map[w][h - 1]>cost && S[w][h - 1] == '.')uncalced.emplace_front(make_tuple(w , h-1, cost));

		//ワープ移動
		REP(i, 5) {
			REP(j, 5) {
				int movew = i - 2;
				int moveh = j - 2;
				if (w + movew < W && w + movew >= 0 && h + moveh < H && h + moveh >= 0 && cost_map[w + movew][h + moveh]>cost + 1 && S[w + movew][h + moveh] == '.')uncalced.emplace_back(make_tuple(w + movew, h+moveh, cost+1));
			}
		}
	}
}



int main() {

	cin >> H>>W>>ch>>cw>>dh>>dw;
	ch--; cw--; dh--; dw--;
	REP(j, H) {
		REP(i, W) {
			cin >> S[i][j];
			cost_map[i][j] = LINF;
		}
	}

	dfs(cw, ch,0);

	if (cost_map[dw][dh] == LINF) {
		cout << -1 << endl;
	}
	else {
		cout << cost_map[dw][dh];
	}

	return 0;

}


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

#define for_(i,a,b) for(int i=(a);i<(b);++i)

typedef double Double;
const Double EPS = 1e-9;

typedef struct Point {
	Double x, y;
	
	Point() {}
	Point(Double x_, Double y_) : x(x_), y(y_) {}
	
	Point operator + (const Point& a) const { return Point(x + a.x, y + a.y); }
	Point operator - (const Point& a) const { return Point(x - a.x, y - a.y); }
	Point operator / (const Double& a) const { return Point(x / a, y / a); }
} Vector;

Double norm(const Point& a) { return a.x * a.x + a.y * a.y; }
Double abs(const Point& a) { return sqrt(norm(a)); }
Double dot(const Vector& a, const Vector& b) { return a.x * b.x + a.y * b.y; }
Double cross(const Vector& a, const Vector& b) { return a.x * b.y - a.y * b.x; }

int ccw(const Point& a, const Point& b, const Point& c) {
	Vector ba = b - a, ca = c - a;
	if (cross(ba, ca) > 0) return +1;
	if (cross(ba, ca) < 0) return -1;
	if (dot(ba, ca) < 0) return +2;
	if (abs(ba) < abs(ca)) return -2;
	return 0;
}

typedef struct Line {
	Point s, e;
	Line() {}
	Line(Point s_, Point e_) : s(s_), e(e_) {}
} Segment;

bool is_cross(const Segment& a, const Segment& b) {
	return (ccw(a.s, a.e, b.s) * ccw(a.s, a.e, b.e) <= 0 &&
			ccw(b.s, b.e, a.s) * ccw(b.s, b.e, a.e) <= 0);
}

struct Rect {
	Point p[4];
	
	enum {IN, ON, OUT};
	int point_in_rect(const Point& pp) {
		bool in = false;
		
		for_(i,0,4) {
			Point a = p[3 - i] - pp, b = p[(6 - i) % 4] - pp;
			if (a.y > b.y) swap(a, b);
			if (a.y <= 0 && 0 < b.y && cross(a, b) + EPS < 0) in = !in;
			if (fabs(cross(a, b)) < EPS && dot(a, b) <= 0) return ON;
		}
		
		return in ? IN : OUT;
	}
	
	bool isCross(Rect& r) {
		for_(i,0,4) {
			int res = point_in_rect(r.p[i]);
			if (res == IN || res == ON) return true;
		}
		
		for_(i,0,4) {
			int res = r.point_in_rect(p[i]);
			if (res == IN || res == ON) return true;
		}
		
		for_(i,0,4) {
			Segment segi(p[i], p[(i + 1) % 4]);
			
			for_(j,0,4) {
				Segment segj(r.p[j], r.p[(j + 1) % 4]);
				
				if (is_cross(segi, segj)) return true;
			}
		}
		
		return false;
	}
};

int N, M;
vector< Rect > rects;

vector< bool > vis;
vector< vector< int > > adj;

void dfs(int v) {
	vis[v] = true;
	for (int u : adj[v]) if (!vis[u]) dfs(u);
}

void solve() {
	rects = vector< Rect >(M);
	
	for_(i,0,M) {
		int xa, ya, xb, yb, xc, yc, xd, yd;
		cin >> xa >> ya >> xb >> yb >> xc >> yc >> xd >> yd;
		rects[i].p[0] = Point(xa, ya);
		rects[i].p[1] = Point(xb, yb);
		rects[i].p[2] = Point(xc, yc);
		rects[i].p[3] = Point(xd, yd);
	}
	
	adj.assign(M, vector< int >());
	
	for_(i,0,M) for_(j,i+1,M) {
		if (rects[i].isCross(rects[j])) {
			adj[i].push_back(j);
			adj[j].push_back(i);
		}
	}
	
	vis.assign(M, false);
	
	int ans = 0;
	
	for_(i,0,M) {
		if (vis[i]) continue;
		++ans;
		dfs(i);
	}
	
	cout << ans << endl;
}

int main() {
	while (cin >> N, N) {
		for_(i,0,N) {
			cin >> M;
			solve();
		}
	}
}

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

ll n;
vector<int> a;
int cnt;

void dfs2(bitset<3> bt, ll num){
	if(num > n) return;
  	if(bt.test(0) && bt.test(1) && bt.test(2)) cnt++;
  	
  	rep(i,3){
    	bitset<3> tmp = bt;
      	tmp.set(i,1);
      	dfs2(tmp, num*10+a.at(i));
    }
  	
  	return;
}

void dfs(){
	rep(i,3){
    	bitset<3> bt("000"); bt.set(i,1);
      	dfs2(bt,a.at(i));
    }
}

int main(){
	cin >> n;
  	a = vector<int>(3);
  	a.at(0) = 3;
  	a.at(1) = 5;
  	a.at(2) = 7;
  	cnt = 0;
  	dfs();
  	cout << cnt << endl;
}

Measured memory_bytes: 3624
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 102333
using namespace std;
typedef long long ll;
const int inf=0x3bbbbbbb;
int n,head[N],to[N<<1],nxt[N<<1],val[N<<1],tot;
inline void add(int x,int y,int z)
{
	to[++tot]=y;
	nxt[tot]=head[x];
	head[x]=tot;
	val[tot]=z;
}
int size[N],maxx[N],G=0;
void dfs(int x,int pre)
{
	size[x]=1,maxx[x]=0;
	int i,y;
	for(i=head[x];i;i=nxt[i])if((y=to[i])!=pre)
	{
		dfs(y,x);
		size[x]+=size[y];
		maxx[x]=max(maxx[x],size[y]);
	}
	maxx[x]=max(maxx[x],n-size[x]);
	if(maxx[x]<maxx[G])G=x;
}
ll ans;
int main()
{
	cin>>n;
	int i,x,y,z,minval=inf,maxsize=0,siz,flag=1;
	for(i=1;i<n;++i)
	{
		scanf("%d%d%d",&x,&y,&z);
		add(x,y,z),add(y,x,z);
	}
	maxx[0]=inf;
	dfs(1,0);
	for(x=1;x<=n;++x)
	{
		if(x!=G)
		{
			for(i=head[x];i;i=nxt[i])if(size[y=to[i]]<size[x]&&y!=G)
				ans+=(ll)min(size[y],n-size[y])*2*val[i];
		}
		else
		{
			for(i=head[x];i;i=nxt[i])
			{
				minval=min(minval,val[i]);
				y=to[i];
				if(size[y]<size[x])siz=size[y];
				else siz=n-size[x];
				maxsize=max(maxsize,siz);
			}
			if(maxsize==(n+1)/2)
			{
				for(i=head[x];i;i=nxt[i])
				{
					y=to[i];
					if(size[y]<size[x])siz=size[y];
					else siz=n-size[x];
					ans+=(ll)siz*2*val[i];
					if(siz==(n+1)/2)ans-=val[i];
				}
			}
			else
			{
				for(i=head[x];i;i=nxt[i])
				{
					y=to[i];
					if(size[y]<size[x])siz=size[y];
					else siz=n-size[x];
					ans+=(ll)siz*2*val[i];
					if(val[i]==minval&&flag)flag=0,ans-=val[i];
				}
			}
		}
	}
	cout<<ans;
	return 0;
}

Measured memory_bytes: 7808
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<int,pii> piii;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define all(a)  (a).begin(),(a).end()
#define pb push_back
#define INF 999999999
#define MAX_V 100

struct edge{int to,cost;};
vector<edge> G[MAX_V];
int d[MAX_V][10];
int c,n,m,s,g;

int dijkstra(int s,int V){
    priority_queue< piii,vector<piii>,greater<piii> > que;
    rep(i,MAX_V)rep(j,10)d[i][j]=INF;
    d[s][c]=0;
    que.push(make_pair(0,pii(s,c)));
    
    while(que.size()){
        piii p=que.top();
        que.pop();
        
        int v=p.second.first ;
        int w=p.second.second;
        if(d[v][w]<p.first)continue;
        
        rep(i,G[v].size()){
            edge e=G[v][i];
            rep(j,10){
                if(d[e.to][j]>d[v][j]+e.cost){
                    d[e.to][j]=d[v][j]+e.cost;
                    que.push(make_pair(d[e.to][j],pii(e.to,j)));
                }
            }
            for(int j = 1;j<10;j++){
                if(d[e.to][j-1]>d[v][j]+e.cost/2){
                    d[e.to][j-1]=d[v][j]+e.cost/2;
                    que.push(make_pair(d[e.to][j-1],pii(e.to,j-1)));
                }
            }
        }
    }
    int mini = INF;
    rep(i,10){
        mini = min(mini,d[V][i]);
    }
    return mini;
}

int main(){
    while(cin>>c>>n>>m>>s>>g&&c&&n&&m&&s&&g){
        rep(i,MAX_V)rep(j,10)G[i].clear();
        s--,g--;
        rep(i,m){
            int a,b,f;
            cin>>a>>b>>f;
            a--,b--;
            G[a].pb(edge{b,f});
            G[b].pb(edge{a,f});
        }
        cout<<dijkstra(s,g)<<endl;
    }
}

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


int main(){
  int n , m ; cin >> n >> m ; 
  vector<int> to[100005] ; 
  const int INF = 1001001001 ; 
  
  rep(i,m) {
    int a, b ; 
    cin >> a >> b  ;
    a-- ; //頂点番号
    b-- ; 
    to[a].push_back(b) ; //a to b
    to[b].push_back(a) ; //b to a
  }
  
  queue<int> q ; 
  vector<int> dist(n , INF) ; 
  vector<int> pre(n , -1) ; 
  
  dist[0] = 0 ;
  q.push(0) ; 
  
  while(!q.empty()){//emptyでないならば
    int v = q.front() ;
    q.pop();//先頭の値を削除
    
    for(int u : to[v]){//uは頂点の番号でto[v]はvに行く頂点
      if(dist[u] != INF) continue ; 
      
      dist[u] = dist[v]+1 ; //vに行く頂点は+1
      pre[u] = v ;//目印
      q.push(u) ; //
    }
  }
  
  cout << "Yes" << endl ; 
  
  rep(i,n){
    if(i == 0) continue ; 
    int ans = pre[i];
    ans++ ;
    cout << ans << endl;
  }
  
  return 0 ; 

}

Measured memory_bytes: 10680
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		boolean[][] card_array = new boolean[4][13];
		String card;
		int number;

		int count = sc.nextInt();

		for(int i = 0; i < count; i++) {
			card = sc.next();
			number = sc.nextInt();
			switch (card) {
			case "S":
				card_array[0][number - 1] = true;
				break;
			case "H":
				card_array[1][number - 1] = true;
				break;
			case "C":
				card_array[2][number - 1] = true;
				break;
			case "D":
				card_array[3][number - 1] = true;
				break;
			}
		}
		sc.close();
		for(int i = 0; i < card_array.length; i++) {
			for(int j = 0; j < card_array[i].length; j++) {
				if(card_array[i][j] == false ) {
					switch (i) {
					case 0:
						System.out.printf("S %d\n", j + 1);
						break;
					case 1:
						System.out.printf("H %d\n", j + 1);
						break;
					case 2:
						System.out.printf("C %d\n", j + 1);
						break;
					case 3:
						System.out.printf("D %d\n", j + 1);
						break;
					}
				}
			}
		}
	}
}



Measured memory_bytes: 26284
d = int(input())
c = list(map(int, input().split()))
s = [list(map(int, input().split())) for i in range(d)]
cmax=max(c)
c_index = c.index(cmax)
for i in range(d):
  if i % 5 == 4:
    print(c_index+1)
  else:
    max_value = max(s[i])
    max_index = s[i].index(max_value)
    print(max_index+1)


Measured memory_bytes: 73728
MAX = 100000 #階乗のmodを求めたい中で最大のもの
MOD = 10**9+7

fac = [0]*MAX   #階乗のmod
inv = [0]*MAX    #その数の逆元
finv = [0]*MAX   #階乗の逆元

def COMinit():
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2,MAX):
        fac[i] = (fac[i-1] * i) % MOD
        inv[i] = MOD-(inv[MOD%i] * (MOD//i))%MOD
        finv[i] = (finv[i-1]*inv[i]) %MOD
        
    
def COM(n,k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return (fac[n] * (finv[k]*finv[n-k]))%MOD

#pが素数でないと使えない
COMinit()
n,k = map(int,input().split())
a = list(map(int,input().split()))
a.sort(reverse = True)
MOD = 10**9+7
ans = 0
for i in range(n):
  if n-i < k:
    continue
  C = COM(n-i-1,k-1)
  ans += ((a[i]-a[n-i-1]) * C) % MOD
  ans %= MOD

print(ans)
  
      
        
        

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

int main() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    vector<int> w(n), b(n);
    int W = 0, B = 0;
    rep(i,n){
        if(s[i]=='.') W++;
        w[i] = W;
    }
    for(int i = n-1; i >= 0; --i) {
        if(s[i]=='#') B++;
        b[i] = B;
    }
    int ans = 1e9;
    ans = min(n-W, n-B);
    for(int i = 0; i < n; ++i) {
        int r = max(0, i+1-w[i]);
        int l = max(0, n-i-1-b[i]);
        ans = min(ans, r+l);

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

Measured memory_bytes: 5212
#include <iostream>
using namespace std;
int main() {
    string S; cin >> S;
    int i1=0, i2=S.length()-1, cnt=0;
    for (int i=0; i<S.length()/2; i++) {
        if (S[i1]!=S[i2]) cnt++;
        i1++; i2--;
    }
    cout << cnt << endl;
    return 0;
}


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

x = a[0]
y = sum(a[1:])
ans = abs(x - y)

for i in range(1, N - 1):
    x += a[i]
    y -= a[i]
    buff = abs(x - y)
    if buff < ans:
        ans = buff

print(ans)


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

int main() {
  int n;
  cin >> n;
  int res = n % 1000;
  res = res == 0 ? 0 : 1000 - res;
  cout << res << endl;
  return 0;
}

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

using namespace std;

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

const int INF = 1000000000;
const ll LINF = (ll) 4000000000000000000;
const ll MOD = (ll) 1000000007;
const double PI = acos(1.0);
const int limit = 100010;

#define REP(i,m,n) for(int i=m;i<(int)(n);i++)
#define rep(i,n) REP(i,0,n)
#define rep2(i,n) REP(i,1,n+1)
#define rep3(i,n) REP(i,0,n+1)
#define REPLL(i,m,n) for(ll i=m;i<(ll)(n);i++)
#define repll(i,n) REPLL(i,0,n)
#define repll2(i,n) REPLL(i,1,n+1)
#define MP make_pair
#define YES(n) cout << ((n) ? "YES" : "NO") << endl
#define Yes(n) cout << ((n) ? "Yes" : "No") << endl
#define Possible(n) cout << ((n) ? "Possible" : "Impossible") << endl
#define NP(v) next_permutation(v.begin(),v.end())
#define Size(s) (int) s.size()

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

int main() {
    int n, x;
    cin >> n >> x;
    int m_min = INF;
    int ans = n;

    rep(i, n) {
        int m;
        cin >> m;
        m_min = min(m_min, m);
        x -= m;
    }

    ans += x / m_min;
    cout << ans << endl;

    return 0;
}

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

#define ms(s, n) memset(s, n, sizeof(s))
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define FORd(i, a, b) for (int i = (a) - 1; i >= (b); i--)
#define FORall(it, a) for (__typeof((a).begin()) it = (a).begin(); it != (a).end(); it++)
#define sz(a) int((a).size())
#define present(t, x) (t.find(x) != t.end())
#define all(a) (a).begin(), (a).end()
#define uni(a) (a).erase(unique(all(a)), (a).end())
#define pb push_back
#define pf push_front
#define mp make_pair
#define fi first
#define se second
#define prec(n) fixed<<setprecision(n)
#define bit(n, i) (((n) >> (i)) & 1)
#define bitcount(n) __builtin_popcountll(n)
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<pi> vii;
const int MOD = (int) 1e9 + 7;
const int INF = (int) 1e9;
const ll LINF = (ll) 1e18;
const ld PI = acos((ld) -1);
const ld EPS = 1e-9;
inline ll gcd(ll a, ll b) {ll r; while (b) {r = a % b; a = b; b = r;} return a;}
inline ll lcm(ll a, ll b) {return a / gcd(a, b) * b;}
inline ll fpow(ll n, ll k, int p = MOD) {ll r = 1; for (; k; k >>= 1) {if (k & 1) r = r * n % p; n = n * n % p;} return r;}
template<class T> inline int chkmin(T& a, const T& val) {return val < a ? a = val, 1 : 0;}
template<class T> inline int chkmax(T& a, const T& val) {return a < val ? a = val, 1 : 0;}
inline ll isqrt(ll k) {ll r = sqrt(k) + 1; while (r * r > k) r--; return r;}
inline ll icbrt(ll k) {ll r = cbrt(k) + 1; while (r * r * r > k) r--; return r;}
inline void addmod(int& a, int val, int p = MOD) {if ((a = (a + val)) >= p) a -= p;}
inline void submod(int& a, int val, int p = MOD) {if ((a = (a - val)) < 0) a += p;}
inline int mult(int a, int b, int p = MOD) {return (ll) a * b % p;}
inline int inv(int a, int p = MOD) {return fpow(a, p - 2, p);}
inline int sign(ld x) {return x < -EPS ? -1 : x > +EPS;}
inline int sign(ld x, ld y) {return sign(x - y);}
#define db(x) cerr << #x << " = " << (x) << ", ";
#define endln cerr << "\n";
#define chkpt cerr << "-----\n";

const int maxn = 50 + 5;
int n;
string s[maxn];
int cnt[maxn][maxn];

void solve() {
	cin >> n;
	FOR(i, 0, n) {
		cin >> s[i];
		FOR(j, 0, sz(s[i])) {
			cnt[i][s[i][j] - 'a']++;
		}
	}
	string s = "";
	while (1) {
		int found = 0;
		FOR(i, 0, 26) {
			int ok = 1;
			FOR(j, 0, n) {
				if (!cnt[j][i]) {
					ok = 0;
					break;
				}
			}
			if (ok) {
				s += 'a' + i;
				FOR(j, 0, n) {
					cnt[j][i]--;
				}
				found = 1;
				break;
			}
		}
		if (!found) break;
	}
	cout << s << "\n";
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
#ifdef _LOCAL_
	freopen("in.txt", "r", stdin); //freopen("out.txt", "w", stdout);
#endif
	solve();
#ifdef _LOCAL_
	//printf("\nTime elapsed: %dms", 1000 * clock() / CLOCKS_PER_SEC);
#endif
	return 0;
}

Measured memory_bytes: 256