akhauriyash/Code-Regression huggingface dataset:
// E.

#include <iostream>
#include <sstream>
#include <algorithm>
#include <vector>

using namespace std;

static const int INF = 1 << 29;

typedef pair<int, int> II;

int main(int argc, char *argv[]) {
	int n, k;
	cin >> n >> k;
	int dist[100][100] = {};
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			if (i == j) {
				dist[i][j] = 0;
			} else if (i == 0 || j == 0) {
				dist[i][j] = 1;
			} else {
				dist[i][j] = INF;
			}
		}
	}
	int m = ((n - 1) * (n - 2)) / 2;
	int r = m - k;
	if (r < 0) {
		cout << -1 << endl;
	} else {
		for (int k = 0; k < n; ++k) {
			for (int i = 0; i < n; ++i) {
				for (int j = 0; j < n; ++j) {
					dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
				}
			}
		}
		for (int i = 1; i < n; ++i) {
			for (int j = i + 1; j < n; ++j) {
				if (r <= 0) {
					break;
				}
				--r;
				dist[i][j] = 1;
				dist[j][i] = 1;
			}
		}
		vector<II> v;
		int cnt = 0;
		for (int i = 0; i < n; ++i) {
			for (int j = i + 1; j < n; ++j) {
				if (dist[i][j] == 1) {
					v.push_back({ i + 1, j + 1 });
				}
				cnt += dist[i][j] == 2;
			}
		}
		cout << v.size() << endl;
		for (auto kv : v) {
			cout << kv.first << " " << kv.second << endl;
		}
	}
	return 0;
}


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


int main() {
 int N,max,sum;
  max=1;
  sum=0;
  
  cin >> N;
  
  int L[N];
  
  for (int i = 0; i < N; i++) {
   cin >> L[i];
    if (max<L[i]) max=L[i];
    sum = sum + L[i];
  }
  
  if (max<sum-max) cout<<"Yes";
  else cout<<"No";
  cout << endl;
  
 
  
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define fast                                                                   \
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long
#define ll long long
#define f(i, n) for (int i = 0; i < n; i++)
#define ff(i, n) for (int i = 1; i <= n; i++)
#define F first
#define S second
#define vpii vector<pair<int,int> >
#define sz size()
#define all(v) v.begin(),v.end()
#define pb push_back   
#define PB pop_back
#define vl vector<int>
#define mp make_pair
#define mod 1000000007
typedef unsigned long long ull;
const int N = 200005;
const int MOD = 998244353 ;

int c1, c2, c3, c4;
void solve(){
    int n;
    string s;
    cin>>n;
    while(n--){
        cin>>s;
        if(s == "AC")c1++;
        else if(s == "WA")c2++;
        else if(s == "TLE")c3++;
        else if(s == "RE")c4++;
    }
    cout<<"AC x "<<c1<<endl;
    cout<<"WA x "<<c2<<endl;
    cout<<"TLE x "<<c3<<endl;
    cout<<"RE x "<<c4<<endl;
}

int32_t main() {
    fast
    int t;
    t = 1;
    //cin >> t;
    while(t--)solve();
    return 0;
}


Measured memory_bytes: 3644
// https://atcoder.jp/contests/abc097/tasks/arc097_a

#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 INF 1e9
#define ALL(v) (v).begin(), (v).end()
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;

int l, K;
char f;
string c, s;
set<string> p;
set<char> sc;

void ss(char f)
{
  REP(i, l)
  {
    if (s[i] == f)
    {
      FOR(j, 1, min(l - i + 1, 6))
      {
        p.insert(s.substr(i, j));
      }
    }
  }
}

int main()
{
  cin >> s >> K;
  l = s.length();
  REP(i, l)
  {
    sc.insert(s[i]);
  }

  for (auto &scc : sc)
  {
    if (K <= p.size())
      break;
    ss(scc);
  }

  int i = 0;
  for (auto &q : p)
  {
    i++;
    if (i == K)
    {
      cout << q << '\n';
      break;
    }
  }

  return 0;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
#ifdef _DEBUG
#define dlog(str) cout << "====" << str << endl;
#else
#define dlog(str)
#endif
#define INF 999999999
#define MOD 1000000007
#define REP(i, n) for(int i = 0, i##_l = (n); i < i##_l; i++)
#define FOR(i, s, e) for(int i = s, i##_l = (e); i < i##_l; i++)
#define LLI long long int
#define _min(a,b) ((a<b)?a:b)
#define _max(a,b) ((a<b)?b:a)
#define chmax(a, b) a = _max(a, b)
#define chmin(a, b) a = _min(a, b)
#define bit(a, shift) ((a>>shift)&1))
#define pm(a) ((a)?1:-1)
#define SORT(v) sort(v.begin(),v.end())
#define RSORT(v) sort((v).rbegin(), (v).rend())
// int 2.14E±9    lli 9.2E±18    double 1.7E±380


int main()
{
    cout << fixed << setprecision(10);

    int n;
    cin >> n;
    vector<int> c(n);
    REP(i, n)
    {
        char ch;
        cin >> ch;
        if (ch == 'R')c[i] = 0;
        else c[i] = 1;
    }

    int r2w = count_if(c.begin(), c.end(), [](int x) {return x == 0; });
    int w2r = n - r2w;

    int l = 0, r = n - 1;

    int cnt = 0;
    while (true)
    {
        while (l < n-1 && c[l] == 0)l++;
        while (0<r && c[r] == 1)r--;
        if (r <= l)break;
        c[l] = 0;
        c[r] = 1;
        cnt++;
    }

    cout << cnt;
    return 0;
}

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

using namespace std;
inline void prep ()
{
  cin.tie (0);
  cin.sync_with_stdio (0);
};
const double pi = acos(-1.);
//printf(%.12lf\n,mid);
// __builtin_popcount(int) count 1's in binary
// get decimal part of number
/*
double intpart;
double thiss = modf((double)(n*m)/(double)k, &intpart);
*/
// round = (int)(num+.5)
int mod = 998244353;

long long mymod(long long num){
  if (num< 0 && !(num%mod == 0)){
    if (mod == 1){
      return 0;
    }
    return mod-abs(num)%mod;
  }else{
    return num%mod;
  }
}

/*string sentence = And I feel fine...;
    istringstream iss(sentence);
*/  

double eps = .000000001;

int main ()
{
  prep();
  int n;
  cin >> n;
  int order[n];
  for (int i=0; i<n; i++){
      cin >> order[i];
  }
  int summ = 0;
  for (int i=0; i<n; i++){
      int num;
      cin >> num;
      summ += num;
  }
  int extra[n];
  for (int i=0; i<n-1; i++){
      cin >> extra[i];
  }
  for (int i=1; i<n; i++){
      if (order[i]-order[i-1] == 1){
          summ += extra[order[i-1]-1];
      }
  }
  cout << summ;
  return 0; 
}

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

ll n, k;
vector<int> a;
map<int, int> m;
vector<int> order;

int now = 0;
int cyclestart = -1;

void dfs(int node) {
    auto it = m.find(node);
    if (it != m.end()) {
        cyclestart = node;
        return;
    }
    m[node] = now++;
    order.push_back(node);
    dfs(a[node]);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> k;
    a = vector<int> (n);
    for (int &x: a) cin >> x, x--;
    if (k == 1) {
        cout << a[0] + 1 << endl;
        return 0;
    }
    dfs(0);
    int len = m.size();
    if (k < len) {
        cout << order[k] + 1 << endl;
        return 0;
    }
    int start = m[cyclestart];
    int cyclelen = len - start;
    k-=start;
    k%= cyclelen;
    assert(k + start < n);
    cout << order[k + start] + 1 << endl;

}

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

long long n,x,y;

int main()
{
	scanf("%lld",&n);
	for(long long i=1;i<=3500;i++){
		for(long long j=1;j<=3500;j++){
			x=(i*j*n);
			y=(4*i*j-i*n-j*n);
			if(y<=0)continue;
			if((x%y)==0){
				printf("%lld %lld %lld\n",i,j,x/y);
				return 0;
			}
		}
	}
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll=long long int;
using ld=long double;
using VI=vector<ll>;
using VD=vector<ld>;
using VVI=vector<VI>;
using VC=vector<char>;
using VVC=vector<VC>;
using VS=vector<string>;
using PLL =pair<ll,ll>;
using PLD=pair<ld,ld>;
using VPLL=vector<PLL>;
#define print(x) std::cout<<x<<"\n"
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define repd(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define ALL(x) (x).begin(),(x).end()
#define ALLR(x) (x).rbegin(),(x).rend()
#define SZ(x) ((ll)(x).size())
#define MAX(x) *max_element((x).begin(),(x).end())
#define MIN(x) *min_element((x).begin(),(x).end())
#define SORTR(x) sort((x).rbegin(),(x).rend())
#define SORT(x) sort((x).begin(),(x).end())
#define SUM(x) accumulate((x).begin(),(x).end(), 0)
#define FILL(x,a) fill(x.begin(),x.end(),a)
#define EACH(i,x) for(typeof((x).begin()) i=(x).begin(); i!=(x).end(); ++i)
#define EXIST(v, x) (std::find(v.begin(), v.end(), x) != v.end())

const ll INF = 1e18;
const ld EPS   = 1e-10;
const int MOD  = int(1e9)+7;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
template <class BidirectionalIterator>
bool next_partial_permutation(BidirectionalIterator first, BidirectionalIterator middle,BidirectionalIterator last){reverse(middle, last); return next_permutation(first , last);}
ll gcd(ll x, ll y) { return (x % y)? gcd(y, x % y): y; }
ll lcm(ll x, ll y) { return x / gcd(x, y) * y; }
ll GCD(VI v){ll a = v[0]; for (ll i = 1; i<SZ(v); i++) {a = gcd(a, v[i]);} return a;}
ll LCM(VI v){ll a = v[0]; for (ll i = 1; i<SZ(v); i++) {a = lcm(a, v[i]);} return a;}
VI Bit2Vector(const ll bit, ll n) {	VI s;	rep(i,n) if (bit & (1 << i)) s.push_back(i); return s;}


void Main()
{
	ll n,m,l; ll res=0;
	ll k;
	cin>>n>>k;
	VI h(n),b(n);
	rep(i, n) cin >> h[i];
	
	//VVI dp(n*2,VI(INF,0));
	VI dp(1000010,INF);
	//rep(i,n) dp[i]=0;
	dp[0]=0;
	rep(i,n){
		rep(w,k+1){
			if(i+w>=n) continue;
			ll cost=abs(h[i+w]-h[i]);
			dp[i+w]=min(dp[i+w],dp[i]+cost);
		}
	}
	res=dp[n-1];
	cout << res << "\n";
	return;
}

int main()
{
	std::cin.tie(0);
	std::ios_base::sync_with_stdio(false);
	std::cout << std::fixed << std::setprecision(15);
	Main();
}


Measured memory_bytes: 9600
#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 INF 1e9
#define ALL(v) v.begin(), v.end()

using namespace std;
typedef unsigned long long ll;

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

    vector<ll> p(n, 0);
    REP(i, n) cin >> p[i];

    ll ans = 0;

    REP(i, n){
        if (p[i]-1 == i){
            if (i != n-1 && p[i+1]-1 == i+1){
                ans ++;
                i++;
            }
            else{
                ans++;
            }
        }
    }

    cout << ans << endl;
}


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

long long a, b;

long long f(long long x)
{
    if (x & 1)
        return (x + 1) / 2 % 2;
    else
        return (x / 2 % 2) ^ x;
}

int main()
{
    std::cin >> a >> b;
    std::cout << (f(a - 1) ^ f(b)) << "\n";
    return 0;
}

Measured memory_bytes: 256
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.NoSuchElementException;

public class Main {

	int N,Q,size;
	int[] segment;

	public void init(int _size){
		size = 1;

		while(size < _size)size *= 2;
		segment = new int[2 * size];
		for(int i = 0;i < 2 * size - 1;i++){
			segment[i] = 0;
		}
	}

	public void update(int i,int a){
		i += size - 1;
		segment[i] += a;

		while(i > 0){
			i = (i - 1) / 2;
			segment[i] += a;
		}
	}

	public int query(int a,int b,int k,int l,int r){
		if(r <= a || b <= l)return 0;

		if(a <= l && r <= b)return segment[k];
		else{
			int vl = query(a,b,k * 2 + 1,l,(l + r) /2);
			int vr = query(a,b,k * 2 + 2,(l + r) / 2,r);

			return vl + vr;
		}
	}

	public void solve() {
		N = nextInt();
		Q = nextInt();

		init(N);

		for(int i = 0;i < Q;i++){
			int c = nextInt();
			int x = nextInt();
			int y = nextInt();

			if(c == 0){
				update(x - 1,y);
			}else{
				out.println(query(x - 1,y,0,0,size));
			}
		}
	}

	public static void main(String[] args) {
		out.flush();
		new Main().solve();
		out.close();
	}

	/* Input */
	private static final InputStream in = System.in;
	private static final PrintWriter out = new PrintWriter(System.out);
	private final byte[] buffer = new byte[2048];
	private int p = 0;
	private int buflen = 0;

	private boolean hasNextByte() {
		if (p < buflen)
			return true;
		p = 0;
		try {
			buflen = in.read(buffer);
		} catch (IOException e) {
			e.printStackTrace();
		}
		if (buflen <= 0)
			return false;
		return true;
	}

	public boolean hasNext() {
		while (hasNextByte() && !isPrint(buffer[p])) {
			p++;
		}
		return hasNextByte();
	}

	private boolean isPrint(int ch) {
		if (ch >= '!' && ch <= '~')
			return true;
		return false;
	}

	private int nextByte() {
		if (!hasNextByte())
			return -1;
		return buffer[p++];
	}

	public String next() {
		if (!hasNext())
			throw new NoSuchElementException();
		StringBuilder sb = new StringBuilder();
		int b = -1;
		while (isPrint((b = nextByte()))) {
			sb.appendCodePoint(b);
		}
		return sb.toString();
	}

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

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

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

Measured memory_bytes: 64256
import java.util.Scanner;

class Main{
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);

		long N=sc.nextLong();
		long A=sc.nextLong();
		long B=sc.nextLong();

		if(A>B) {
			System.out.println(0);
		}
		else if(N==1 && A!=B){
			System.out.println(0);
		}
		else if(N==1 && A==B) {
			System.out.println(1);
		}
		else {
			System.out.println(B*(N-2)-A*(N-2)+1);
		}
	}
}

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

int main() {
  int N;
  cin >> N;
  int A[N];
  priority_queue<int> que;
  for (int i = 0; i < N; i++) {
    cin >> A[i];
    que.push(A[i]);
  }
  int first = que.top();
  que.pop();
  int second = que.top();
  
  for (int i = 0; i < N; i++) {
    if (A[i] == first) {cout << second << endl;}
    else {cout << first << endl;}
  }
}
      
      
    
    

Measured memory_bytes: 3316
#!/usr/bin/env python3
#%% for atcoder uniittest use
import sys
input= lambda: sys.stdin.readline().rstrip()
def pin(type=int):return map(type,input().split())
def tupin(t=int):return tuple(pin(t))
def lispin(t=int):return list(pin(t))
#%%code
def resolve():
    N,=pin()
    if N==1:
        print(0)
        return

        
    n=int(N**0.5)+1
    divs=dict()
    temp=N
    for i in range(2,n+4):
        while (1):
            if temp%i !=0:
                break
            divs.setdefault(i,0)
            divs[i]+=1
            temp/=i
    if temp>1:
        divs.setdefault(temp,1)
    #print(divs)
    check=1
    ans=0
    for p,q in divs.items():
        check*=p**q
        temp2=0
        for i in range(1,50):
            temp2+=i
            if temp2>q:
                break
            ans+=1
            
            
        #print(ans)
    print(ans)
    assert N== check
    
#%%submit!
resolve()


Measured memory_bytes: 63708
let read_ints () =
  let str = read_line() in
  List.map (fun x -> int_of_string x) (Str.split (Str.regexp " +") str)
;;

let rec create_range (x : int) =
  if x = 0 then
    [0]
  else
    0 :: (List.map (fun x -> x + 1) (create_range (x - 1)) )
;;

let rec min_list (x : int list) =
  match x with
  |[] -> 1234567
  |h :: t -> min h (min_list t)
;;

let str1 = read_ints() in
let p = read_ints() in
let x2 = List.nth str1 0 in
let n = List.nth str1 1 in
let all_numbers = create_range 101 in
let all_numbers2 = List.filter (fun x -> not (List.exists (fun y -> y = x) p)) all_numbers in
let dist = List.map (fun x -> abs(x - x2)) all_numbers2 in
let mini = min_list dist in
let ans = List.find (fun x -> abs(x - x2) = mini) all_numbers2 in
print_endline (string_of_int ans)


Measured memory_bytes: 3808
#include<algorithm>
#include<bitset>
#include<cmath>
#include<complex>
#include<deque>
#include<functional>
#include<iomanip>
#include<iostream>
#include<iterator>
#include<map>
#include<numeric>
#include<queue>
#include<set>
#include<stack>
#include<string>
#include<unordered_map>
#include<unordered_set>
#include<utility>
#include<vector>

using namespace std;
typedef long long ll;

#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
#define ALL(x) (x).begin(),(x).end()
#define SIZE(x) ((ll)(x).size())
#define MAX(x) *max_element(ALL(x))
#define MIN(x) *min_element(ALL(x))
#define D()
#define INF 1000000000000
#define MOD 10000007
#define MAXR 100000
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define INITA(a,i,j,v) for(ll k=i;k<=j;k++){a[k]=v;}

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

int main() {
    int n; cin >> n;
    ll t[101]; INITA(t, 0, 100, 0);
    ll res = 1;
    REP(i, n) {
        cin >> t[i];
        res = res / gcd(res, t[i]) * t[i];
    }
    cout << res << endl;
    return 0;
}

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

string s, t;
int c[3000][3000] = {};
pair<int, int> w[3000][3000] = {};
string ans = "";

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
    cin >> s >> t;
    
    c[0][0] = (s[0] == t[0]);
    
    for (int i = 1; i < s.length(); i++)
    {
        c[i][0] = (c[i - 1][0] | (s[i] == t[0]));
        w[i][0] = {-1, 0};
    }
    for (int i = 1; i < t.length(); i++)
    {
        c[0][i] = (c[0][i - 1] | (s[0] == t[i]));
        w[0][i] = {0, -1};
    }
    
    for (int i = 1; i < s.length(); i++)
    {
        for (int j = 1; j < t.length(); j++)
        {
            if (s[i] == t[j])
            {
                c[i][j] = c[i - 1][j - 1] + 1;
                w[i][j] = {-1, -1};
            }
            else
            {
                if (c[i - 1][j] > c[i][j - 1])
                {
                    c[i][j] = c[i - 1][j];
                    w[i][j] = {-1, 0};
                }
                else
                {
                    c[i][j] = c[i][j - 1];
                    w[i][j] = {0, -1};
                }
            }
        }
    }
    
    int i = s.length() - 1;
    int j = t.length() - 1;
    
    if (c[i][j] == 0)
        return 0;
    
    while (1)
    {
        int x = w[i][j].first;
        int y = w[i][j].second;
        
        if ((s[i] == t[j] && c[i][j] == 1) || (x == -1 && y == -1))
            ans += s[i];
        if (s[i] == t[j] && c[i][j] == 1)
            break;
        
        i += x;
        j += y;
    }
    
    reverse(ans.begin(), ans.end());
    
    cout << ans;

    return 0;
}


Measured memory_bytes: 109088
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 1; i <= (int)(n); i++)
vector<int> input(int N) {
  vector<int> vec(N);
  for (int i = 0; i < N; i++) {
    cin >> vec.at(i);
  }
  return vec;
}

int main() {
  int n,l,sum=0;
  cin >> n >> l;
  rep(i,n){
    sum += l+i-1;
  }
  if(l>=0){
    cout << sum-l << endl;
  }
  else if(n+l-1>=0){
    cout << sum << endl;
  }else{
    cout << sum-(n+l-1) << endl;
  }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define MAX_N 100005
int N,M;
int s[MAX_N];

int check(int X){
  int res=0;
  int lv=1;
  int p=0;
  while( lv + X <= s[N-1] ){
    while(p+1<N&&s[p]<=lv)p++;
    
    int f=p;
    if( s[f] >= lv + X)f--;
    if(f>0 && abs(s[f]-lv) > abs(s[f-1]-lv) )f--;
    if(f<0)return 1e9;
    res++;
    lv+=max(1, X-abs(s[f]-lv));
  }
  return res+1;
}

int solve(){
  int left=s[0];
  int right=1e9;
  int mid;
  while(right-left>1){
    mid=(left+right)/2;
    if(check(mid) >= M){
      left=mid;
    }else{
      right=mid;
    }
  }

  
  if(check(left)>=M)return left;
  else return -1;
}

int main(){
  while(cin>>N>>M){
    if(N==0&&M==0)break;
    for(int i=0;i<N;i++)cin>>s[i];
    cout<<solve()<<endl;
  }
  return 0;
}

Measured memory_bytes: 3448
#include<bits/stdc++.h>
using namespace std;
int main()
{
    char c;
    int n,g=0,w=0,y=0,p=0;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>c;
        if(c=='G') g=1;
        else if(c=='W') w=1;
        else if(c=='Y') y=1;
        else if(c=='P') p=1;
    }
    int sum=(g+w+y+p);
    if(sum==1) cout<<"One"<<endl;
    else if(sum==2) cout<<"Two"<<endl;
    else if(sum==3) cout<<"Three"<<endl;
    else if(sum==4) cout<<"Four"<<endl;

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <tuple>
#include <numeric>
#include <functional>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef pair<ll, ll> P;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define exrep(i, a, b) for(ll i = a; i <= b; i++)
#define out(x) cout << x << endl
#define exout(x) printf("%.10f\n", x)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define pb push_back
#define re0 return 0
const ll mod = 1000000007;
const ll INF = 1e16;
const ll MAX_N = 100010;
 
ll dp[2][110][110];  /* dp[id][i+1][j] : 先頭からi桁目までで0以外の数字がj個現れるs以下の数の個数
                                         ただし、id = 0 のとき現時点でsと等しい
                                         id = 1 のとき現時点でs未満が確定 */
 
int main() {
    string s;
    ll k;
    cin >> s >> k;
    ll m = s.size();  // sはm桁とする
    
    dp[0][0][0] = 1;
    rep(id, 2) {
        rep(i, m) {
            rep(j, m) {
                ll lim = s[i] - '0';  //  先頭からi桁目にはlim以下の数を置ける
                if(id) {  // s未満が確定していたら
                    lim = 9;
                }
                exrep(x, 0, lim) {  // 先頭からi桁目にxを置くとする
                    dp[id || x < lim][i+1][j + (x != 0)] += dp[id][i][j];
                }
            }
        }
    }
    
    out(dp[0][m][k] + dp[1][m][k]);
    re0;
}

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

int main(){
int r;
  cin >> r;
  if(r < 1200){
  cout << "ABC" << endl;
  }
  else if(r < 2800){
  cout << "ARC" << endl;
  }
  else{
  cout << "AGC" << endl;
  }
  return 0;
}

Measured memory_bytes: 256
program abc168a
      implicit none
      character(3)::n
      integer::i

         read *, n
         i=len_trim(n)

         if ( n(i:i)=='2' .or. n(i:i)=='4' .or. n(i:i)=='5' &
             .or. n(i:i)=='7' .or. n(i:i)=='9' ) then
            print *, 'hon'
         else if ( n(i:i)=='0' .or. n(i:i)=='1' &
                  .or. n(i:i)=='6' .or. n(i:i)=='8' ) then
            print *, 'pon'
         else
            print *, 'bon'
         end if

   end program abc168a

Measured memory_bytes: 2856
#include<stdio.h>
int N,M,A[105][105],B[105],i,j,t;
int main()
{
	scanf("%d%d",&N,&M);
	for(i=0;i<N;i++)
		for(j=0;j<M;j++)
			scanf("%d",&A[i][j]);
	for(i=0;i<M;i++)
		scanf("%d",&B[i]);
	for(i=0;i<N;i++)
	{
		for(j=t=0;j<M;j++)
			t+=A[i][j]*B[j];
		printf("%d\n",t);
	}
	return 0;
}


Measured memory_bytes: 2108
#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <set>
#include <map>
#include <cassert>
using namespace std;

typedef long long ll;

const ll MAX_N = 1e2 + 2, inf = 1000000LL * 1000000LL;
string s;
ll k;
ll dp[MAX_N][2];

ll calc (string t) {
    for (ll i = 0; i < MAX_N; i++)
        dp[i][0] = dp[i][1] = inf;

    dp[0][0] = 0, dp[0][1] = 1;
    for (ll i = 1; i < t.size(); i++) {
        dp[i][1] = min(dp[i - 1][0], dp[i - 1][1]) + 1;
        dp[i][0] = (t[i] == t[i - 1]? dp[i - 1][1]: min(dp[i - 1][1], dp[i - 1][0]));
    }

    return min(dp[t.size() - 1][0], dp[t.size() - 1][1]);
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    cin >> s >> k;
    if (s.size() == 1) {
        cout << (k / 2) << "\n";
        return 0;
    }

    if (k == 1) {
        cout << calc(s) << "\n";
        return 0; 
    }

    if (s[0] != s[s.size() - 1]) {
        cout << calc(s) * k << "\n";
        return 0;
    }

    ll l = 1;
    for (ll i = 1; i < s.size(); i++)
        if (s[i] == s[0])
            l++;
        else
            break;

    if (l == s.size()) {
        cout << (1LL * s.size() * k) / 2 << "\n";
        return 0;
    }

    ll r = 1;
    for (ll i = s.size() - 2; ~i; i--)
        if (s[i] == s[0])
            r++;
        else
            break;


    string g;
    for (ll i = l - 1; i + r - 1 < s.size(); i++)
        g += s[i];

    ll ans = (l / 2) + (r / 2) + ((l + r) / 2) * (k - 1) + calc(g) * k;
    cout << ans << "\n";
    return 0;
}


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

using namespace std;

// INF
#define IINF (INT_MAX/2)
#define INF (1<<29)

// math
#define SQ(x) ((x)*(x))

// container utility
#define ALL(x) (x).begin(), (x).end()
#define MP make_pair
#define PB push_back
#define EACH(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();i++)

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

// typedef
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<PII> VII;
typedef vector<VI> VVI;

typedef long long ll;

// conversion
template<class T> inline string toStr(T a) { ostringstream oss; oss << a; return oss.str(); }
inline int toInt(string s) { return atoi(s.c_str()); }

// prime
bool isPrime(int a) { for(int i=2; i*i <=a; i++) if(a%i == 0) return false; return true; }

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

// inRange
inline bool inRange(int x, int y, int W, int H) {
  return 0<=x && x<W && 0<=y && y<H;
}

// isPalindrome
inline bool isPalindrome(string s) {
  return equal(s.begin(), s.end(), s.rbegin());
}

ll cfront[100], cback[100];

ll memo[101][101];

ll dfs(int l, int r) {
  
  if(memo[l][r]) return memo[l][r];
  if(l+1 == r) return 0;
  
  ll ret = INF;
  REP(m, l+1, r) {
    ret = min(ret, dfs(l, m) + dfs(m, r)
              + cfront[l]*cback[m-1]*cfront[m]*cback[r-1]);
  }
  
  return memo[l][r] = ret;
}

int main() {
  int N; cin >> N;
  rep(i, N)
    cin >> cfront[i] >> cback[i];
  cout << dfs(0, N) << endl;
  
  return 0;
}

Measured memory_bytes: 1232
#include <algorithm>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
#define rep(i, n) for(int(i) = 0; (i) < (n); (i)++)
#define FOR(i, m, n) for(int(i) = (m); (i) < (n); (i)++)
#define All(v) (v).begin(), (v).end()
#define pb push_back
#define MP(a, b) make_pair((a), (b))
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
const int INF = 1 << 30;
const ll LINF = 1LL << 60;
const int MOD = 1e9 + 7;

bool dp[90][90][25600];

int main() {
    int H, W;
    cin >> H >> W;
    vector<vector<int>> A(H, vector<int>(W)), B(H, vector<int>(W));
    rep(i, H) rep(j, W) { cin >> A[i][j]; }
    rep(i, H) rep(j, W) { cin >> B[i][j]; }
    dp[0][0][A[0][0] - B[0][0] + 12800] = true;
    dp[0][0][-A[0][0] + B[0][0] + 12800] = true;

    for(int i = 0; i < H; i++) {
        for(int j = 0; j < W; j++) {
            for(int k = 0; k < 25600; k++) {
                if(dp[i][j][k]) {
                    if(i + 1 < H) {
                        dp[i + 1][j][k + (A[i + 1][j] - B[i + 1][j])] = true;
                        dp[i + 1][j][k - (A[i + 1][j] - B[i + 1][j])] = true;
                    }
                    if(j + 1 < W) {
                        dp[i][j + 1][k + (A[i][j + 1] - B[i][j + 1])] = true;
                        dp[i][j + 1][k - (A[i][j + 1] - B[i][j + 1])] = true;
                    }
                }
            }
        }
    }

    int res = INF;
    for(int i = 0; i < 25600; i++) {
        if(dp[H - 1][W - 1][i]) {
            res = min(res, abs(i - 12800));
        }
    }
    cout << res << endl;

    return 0;
}

Measured memory_bytes: 179328
#include <bits/stdc++.h>
#define INF 1e9
using namespace std;

int main(){
  int e, zz;
  while(cin >> e, e){
    int min_c = INF;
    for(int z = 0; (zz = z * z * z) <= e; z++){
      for(int y = 0; zz + y * y <= e; y++){
        int tmp = zz + y * y;
        int x = e - tmp;
        if(x < 0) continue;
        min_c = min(min_c, x + y + z);
      }
    }
    cout << min_c << endl;
  }
  return 0;
}



Measured memory_bytes: 2996
#include <bits/stdc++.h>
#include <cmath>
using namespace std;
#define fast                                                                   \
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long
#define ll long long
#define f(i, n) for (int i = 0; i < n; i++)
#define fo(i,a,n) for (i = a; i <= n; i++)
#define F first
#define S second
#define pii pair<int,int>
#define sz size()
#define all(v) v.begin(),v.end()
#define pb push_back
#define pf push_front    
#define PB pop_back
#define pll pair<long long, long long>
#define vi vector<int>
#define vl vector<int>
#define mp make_pair
#define mod 1000000007
typedef unsigned long long ull;
const int N = 200005;
const int MOD = 998244353 ;



void solve(){
    int n, m, c1 = 0, c2 = 0;
    cin>>n>>m;
    int b[n+4] = {0}, c[n+4] = {0};
    vector<pair<int,int> > v;
    f(i,m){
        int x;
        string s;
        cin>>x>>s;
        if(s[0] == 'W' && b[x] == 0)c[x]++;
        else b[x] = 1;
    }
    f(i,n+1){
        c1 += b[i];
        if(b[i] == 1)c2 += c[i];
    }
    cout<<c1<<" "<<c2;
}

int32_t main() {
    fast
    int t;
    t = 1;
    //cin >> t;
    while(t--)solve();
    return 0;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define N 100100

ll n,cnt,dis;
ll d[N];
set<pair<ll,ll> > S;
ll sz[N],u[N],v[N];
set<pair<ll,ll> >::iterator it,it2;

int main()
{
	scanf("%lld",&n);
	for (ll i=1;i<=n;i++) {
		scanf("%lld",&d[i]);
		S.insert(mp(d[i],i));
		sz[i]=1;
	}
	
	for (ll i=1;i<n;i++)
	{
		it=S.end(); it--;
		ll now=(*it).second,num=sz[now];
		S.erase(it);
		if (n-2*num<=0) return puts("-1"),0;
		it2=S.lower_bound(mp(d[now]-(n-2*num),0));
		if (it2==S.end() || (*it2).first!=d[now]-(n-2*num)) return puts("-1"),0;
		u[++cnt]=now; v[cnt]=(*it2).second;
		sz[(*it2).second]+=num;
		dis+=2*num*(n-num);
	}
	for (int i=1;i<=n;i++) dis-=d[i];
	if (dis!=0) return puts("-1"),0;
	for (ll i=1;i<=cnt;i++) printf("%lld %lld\n",u[i],v[i]);
	return 0;
}

Measured memory_bytes: 10752
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std; const int inf = numeric_limits<int>::max();
struct __io{__io(){ios_base::Init i; ios_base::sync_with_stdio(0); cin.tie(0);}} __io; // fast I/O
#ifdef LOCAL // setting up print debugging (yes lol)
template<class K, class V>ostream& operator<<(ostream&s,const pair<K,V>&p){s<<'<'<<p.x<<", "<<p.y<<'>';return s;}
template<class T, class=typename T::value_type, class=typename enable_if<!is_same<T,string>::value>::type>
ostream& operator<<(ostream&s,const T&v){s<<'[';for(auto&x:v){s<<x<<", ";}if(!v.empty()){s<<"\b\b";}s<<']';return s;}
void __prnt(){cerr<<endl;} template<class T, class...Ts>void __prnt(T&&a,Ts&&...etc){cerr<<a<<' ';__prnt(etc...);}
#define print(...) __prnt(__VA_ARGS__)
#else
#define print(...)
#endif

struct query {
    int l;
    int r;
    int i;
    int ans;
};

signed main() {
    int n, t;
    cin >> n >> t;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    vector<query> q(t);
    for (int i = 0; i < t; ++i) {
        cin >> q[i].l >> q[i].r;
        q[i].i = i;
        q[i].l--;
        q[i].r--;
    }

    int sqrtn = sqrt(n) + 1;
    sort(q.begin(), q.end(), [&sqrtn](query &a, query &b) {
        if (a.l / sqrtn != b.l / sqrtn) {
            return a.l / sqrtn < b.l / sqrtn;
        }
        return a.r < b.r;
    });

    vector<int> m(n+1);
    int l = 0;
    int r = -1;
    int cnt = 0;

    for (auto &q : q) {
        if (r < q.l || q.r < l) {
            print("!");
            m.assign(n+1, 0);
            cnt = 0;
            l = q.l;
            r = q.l - 1;
        }
        while (r < q.r) {
            r++;
            if (m[a[r]] == 0) cnt++;
            m[a[r]]++;
        }
        while (r > q.r) {
            m[a[r]]--;
            if (m[a[r]] == 0) cnt--;
            r--;
        }
        while (l < q.l) {
            m[a[l]]--;
            if (m[a[l]] == 0) cnt--;
            l++;
        }
        while (l > q.l) {
            l--;
            if (m[a[l]] == 0) cnt++;
            m[a[l]]++;
        }
        q.ans = cnt;
    }
    sort(q.begin(), q.end(), [](query &a, query &b) {return a.i < b.i;});

    for (auto &q : q) {
        cout << q.ans << '\n';
    }
}


Measured memory_bytes: 15492
#define _USE_MATH_DEFINES
#define INF 10000000
#include <iostream>
#include <sstream>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
#include <limits>
#include <map>
#include <string>
#include <cstring>
#include <set>
#include <deque>
#include <bitset>

using namespace std;

typedef long long ll;
typedef pair<int,string> P;

static const double eps = 1e-8;

int main(){
	int n;
	while(~scanf("%d",&n)){
		if(n==0) break;

		int* a = new int[n];
		for(int i=0;i<n;i++){
			scanf("%d",a+i);
		}

		int dst;
		scanf("%d",&dst);
		
		int lb = 0;
		int ub = n-1;

		int res=0;
		for(int i=0;i<50;i++){
			res++;
			int md = (lb+ub)/2;

			if(dst == a[md]){
				break;
			}
			else if(dst < a[md]){
				ub = md-1;
			}
			else{
				lb = md+1;
			}
			
			if(ub<lb){
				break;
			}
		}
		printf("%d\n",res);
		delete[] a;
	}
}

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

int a[100],d[101];

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

Measured memory_bytes: 1192
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n1 = scan.nextInt();
        int n2 = scan.nextInt();
        int n3 = scan.nextInt();
        if(n1+n2+n3>21) System.out.println("bust");
        else System.out.println("win");
    }
}

Measured memory_bytes: 21716
#include<iostream>
#include<algorithm>
#include<climits>
#include<string>
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define scan(arg) cin>>arg
#define prin(arg) cout<<arg<<"\n"
#define prin2(arg1,arg2) cout<<arg1<<" "<<arg2<<"\n"
using namespace std;
typedef long long ll;
string s;
int main(){
  cin>>s;
  if(s[5]=='0'&&(s[6]=='1'||s[6]=='2'||s[6]=='3'||s[6]=='4')){
    prin("Heisei");
  }
  else{
    prin("TBD");
  }
  

  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <array>
#include <queue>
#include <map>
#include <set>
#include <sstream>
#include <stdio.h>

using namespace std;

#define Rep(i,a,b) for(int i = a; i < b; i++)
#define rep(i,b) Rep(i,0,b)
#define rrep(i,a) for(int i = a; i >= 0; i--)
#define allof(a) (a).begin(), (a).end()
#define pb push_back

typedef long long ll;
const int inf = 1e9 + 7;
const ll infll = 1ll << 60ll;
const ll mod = 1e9 + 7;
// 0~3までは右左下上 4~7までは斜め
constexpr int dx[] = { 1, 0, -1, 0, 1, 1, -1, -1 };
constexpr int dy[] = { 0, -1, 0, 1, 1, -1, -1, 1 };

// 最大公約数
ll gcd(ll a, ll b) {
	if (b == 0) return a;
	return gcd(b, a%b);
}

// 最小公約数
long lcm(long a, long b) {
	return a / gcd(a, b) * b;
}

int h, w;

int a[500][500];
vector<pair<int, int>> pa;

int cnt = 0;

void bfs(int i, int j) {
	if (a[i][j] % 2) {
		// 自身より右か下のマスに送る
		if (j + 1 < w) {
			a[i][j]--;
			a[i][j + 1]++;
			pa.push_back({ i+1,j+1 });
			pa.push_back({ i + 1,j+2});
			cnt++;
		}
		else if (i + 1 < h) {
			a[i][j]--;
			a[i + 1][j]++;
			pa.push_back({ i + 1,j + 1 });
			pa.push_back({ i + 2,j + 1 });
			cnt++;
		}
	}
}

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

	//memset(a,0,sizeof(a));

	cin >> h >> w;

	// 横がw 縦がh
	rep(i, h) {
		rep(j, w) {
			cin >> a[i][j];
		}
	}

	rep(i, h) {
		rep(j, w) {
			bfs(i, j);
		}
	}

	cout << cnt << endl;
	rep(i, cnt) {
		cout << pa[2 * i].first << " " << pa[2 * i].second << " "
			<< pa[2 * i + 1].first << " " << pa[2 * i + 1].second << endl;
	}

	return 0;
}

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

using namespace std;

#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)((x).size()))

typedef pair<int, int> PII;
typedef vector<int> VI;
typedef long long int64;
typedef unsigned int uint;
typedef unsigned long long uint64;

#define gi(x) ((x) = F())
#define gii(x, y) (gi(x), gi(y))
#define giii(x, y, z) (gii(x, y), gi(z))

int F()
{
	char ch;
	int x, a;
	while (ch = getchar(), (ch < '0' || ch > '9') && ch != '-');
	if (ch == '-') ch = getchar(), a = -1;
	else a = 1;
	x = ch - '0';
	while (ch = getchar(), ch >= '0' && ch <= '9')
		x = (x << 1) + (x << 3) + ch - '0';
	return a * x;
}

int n, a[2010], x, mn[2010][2010];

long long ans;

int main()
{
	gii(n, x);
	for (int i = 1; i <= n; ++i) gi(a[i]), ans += a[i];
	for (int i = 1; i <= n; ++i)
	{
		mn[i][i] = a[i];
		for (int j = i + 1; j <= n; ++j)
			mn[i][j] = min(mn[i][j - 1], a[j]);
	}
	for (int i = 0; i <= n; ++i)
	{
		long long ret = 1LL * x * i;
		for (int j = 1; j <= n; ++j)
		{
			int k = j - i;
			if (k < 1) k += n, ret += min(mn[k][n], mn[1][j]);
			else ret += mn[k][j];
		}
		ans = min(ans, ret);
	}
	printf("%lld\n", ans);
	return 0;
}



Measured memory_bytes: 15360
#include<bits/stdc++.h>
#define a first
#define b second
#define pb push_back
#define SZ(x) ((int)x.size())
#define L(i,u) for (register int i=head[u]; i; i=nxt[i])
#define rep(i,a,b) for (register int i=(a); i<=(b); i++)
#define per(i,a,b) for (register int i=(a); i>=(b); i--)
using namespace std;
typedef long long ll;
typedef unsigned int ui;
typedef pair<int,int> Pii;
typedef vector<int> Vi;
template<class T> inline void read(T &x){
	x=0; char c=getchar(); int f=1;
	while (!isdigit(c)) {if (c=='-') f=-1; c=getchar();}
	while (isdigit(c)) {x=x*10+c-'0'; c=getchar();} x*=f;
}
template<class T> inline void umin(T &x, T y){x=x<y?x:y;}
template<class T> inline void umax(T &x, T y){x=x>y?x:y;}
inline ui R() {
	static ui seed=416;
	return seed^=seed>>5,seed^=seed<<17,seed^=seed>>13;
}
const int N = 266666;
int n,v[N];Pii s[N];
struct Frac{
	ll a,b;// a/b
	Frac(ll A=0,ll B=1){a=A;b=B;}
}ans;
ll gcd(ll a, ll b){return !b?a:gcd(b,a%b);}
inline Frac Norm(Frac y){
	ll g=gcd(y.a,y.b);y.a/=g;y.b/=g;return y;
}
inline void upd(Frac &x, Frac y){
	y=Norm(y);if(1.0*x.a/x.b>1.0*y.a/y.b)x=y;
}
bool cmp(Pii x, Pii y){return x.a+max(x.b-x.a,0)<y.a+max(y.b-y.a,0);}
bool ck(int k){
	ll tot=0;rep(i,1,n)tot+=max(s[i].b-s[i].a,0);
	rep(i,1,k)tot-=v[i];return tot>=0;
}
int main() {
	read(n);rep(i,1,n)read(s[i].a),read(s[i].b);
	sort(s+1,s+n+1,cmp);
	rep(i,1,n)v[i]=s[i].a+max(s[i].b-s[i].a,0);
	int L=0,R=n;
	while(L<R){
		int mid=(L+R+1)>>1;
		if(ck(mid))L=mid;else R=mid-1;
	}
	int k=L;assert(k<n);
	ll ori=0;rep(i,1,n)ori+=max(s[i].b-s[i].a,0);
	rep(i,1,k)ori-=v[i];
	ans.a=1;ans.b=1;
	rep(i,1,n){
		ll tot=ori;
		if(i<=k)tot=tot+s[i].a-v[k+1];else tot-=max(s[i].b-s[i].a,0);
		upd(ans,(Frac){s[i].a-tot,s[i].b});
	//	printf("%d %lld %lld\n",i,s[i].a-tot,s[i].b);
	}
	ll x=ans.a,y=ans.b;
//	printf("%d %lld %lld\n",k,x,y);
	ans=(Frac){y-x+y*k,n*y};ans=Norm(ans);
	printf("%lld %lld\n",ans.a,ans.b);
	return 0;
}


Measured memory_bytes: 1408
#include <iostream>
#include <sstream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cassert>

using namespace std;

#define FOR(i,k,n) for(int i=(k); i<(int)(n); ++i)
#define REP(i,n) FOR(i,0,n)
#define FORIT(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)

template<class T> void debug(T begin, T end){ for(T i = begin; i != end; ++i) cout<<*i<<" "; cout<<endl; }
inline bool valid(int x, int y, int W, int H){ return (x >= 0 && y >= 0 && x < W && y < H); }

typedef long long ll;
const int INF = 100000000;
const double EPS = 1e-8;
const int MOD = 1000000007;
int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
double dist(double x, double y){
  return sqrt(x * x + y * y);
}

int main(){
  int N;
  int CASE = 1;
  while(cin>>N && N){
    printf("Case %d: ", CASE++);
    double x[14][2], y[14][2];
    double d[14];
    REP(i, N){
      REP(j, 2) cin>>x[i][j]>>y[i][j];
      d[i] = dist(x[i][0] - x[i][1] , y[i][0] - y[i][1]);
    }
    double dp[1<<14][14][2];
    REP(i, 1<<14)REP(j, 14)REP(k, 2) dp[i][j][k] = INF;
    REP(i, N)REP(k, 2) dp[1<<i][i][k] = d[i];
    REP(S, 1<<N){
      REP(from, 2 * N){
        int f_i = from / 2;
        int f_j = from % 2;
        REP(to, 2 * N){
          int t_i = to / 2;
          int t_j = to % 2;
          if(S & (1<<t_i)) continue;
          dp[S | (1<<t_i)][t_i][t_j] = min(dp[S | (1<<t_i)][t_i][t_j],
              dp[S][f_i][f_j] + dist(x[f_i][f_j] - x[t_i][(t_j + 1) % 2], y[f_i][f_j] - y[t_i][(t_j + 1) % 2]) + d[t_i]);
        }
      }
    }
    double ans = 1e16;
    REP(i, N)REP(j, 2) ans = min(ans, dp[(1<<N) - 1][i][j]);
    
    printf("%.5f\n", ans);
  }
  return 0;
}

Measured memory_bytes: 4832
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>
#include <math.h>
#include <cassert>
#define rep(i,n) for(int i = 0; i < n; ++i )
using namespace std;
using ll = long long;
using P = pair<int,int>;

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

  auto f = [&](char l, char r){
    int cnt = 0;
    if(s[0]==l) ++cnt;
    rep(i,n-1) if(s[i]==s[i+1]) ++cnt;
    if(s[n-1]==r) ++cnt;
    cnt += 2*k;
    return cnt > n ? n - 1 : cnt - 2;
  };
  int ans = 0;
  ans = max(ans,f('L','L'));
  ans = max(ans,f('L','R'));
  ans = max(ans,f('R','L'));
  ans = max(ans,f('R','R'));
  cout << ans << endl;
}

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

int main() {
    int n, m;
    cin >> n >> m;
    int even, odd;
    even = n == 0? 0: n * (n-1)/2;
    odd = m == 0? 0: m * (m-1)/2;

    cout << even + odd << endl;
    return 0;
}

Measured memory_bytes: 256
import Control.Applicative
import Control.Monad
import Data.Char

count :: String -> [Int]
count [] = take 26 (repeat 0)
count (x:xs) | 'A' <= x && x <= 'Z'  =
    take c rcount ++ [rcount!!c + 1] ++ drop (c+1) rcount
    where c = ord x - ord 'A'
          rcount = count xs
count (x:xs) | 'a' <= x && x <= 'z'  =
    take c rcount ++ [rcount!!c + 1] ++ drop (c+1) rcount
    where c = ord x - ord 'a'
          rcount = count xs
count (x:xs) = count xs

main = do
    s <- getContents
    let c = count s
    putStr $ concat[ chr (i + ord 'a'):" : " ++ show(c!!i) ++"\n" | i <- [0..25] ]
    

Measured memory_bytes: 4316
#include <algorithm>
#include <bits/stdc++.h>
#include<iostream>
#include<string>
using namespace std;
#define rep(i, n) for (int i = 0; i <(int)(n); i++)
#define all(x) (x).begin(), (x).end()
#define ll long long
int x[10];
int y[10];
int n;

int zyou(int n){
    int ans=1;
    while(n>0){
        ans*=n;
        n--;
    }
    return ans;
}

double dist(int i,int j){
    double dx=abs(x[i]-x[j]);
    double dy=abs(y[i]-y[j]);
    return pow(dx*dx+dy*dy,0.5);
}

int main(){
    cin>>n;
    for(int i = 1; i <= n; i++) cin >> x[i] >> y[i];
    vector<int> v(n);
    rep(i,n) v[i]=i+1;
    double sum=0.0;
    do{
      for(int i=0;i<n-1;i++)sum+=dist(v[i],v[i+1]);
    }while(next_permutation(all(v)));
    cout<<fixed<<setprecision(12)<<sum/zyou(n)<<endl;
}

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

using namespace std;

#define SZ(x) (int)(x.size())
#define REP(i, n) for(int i=0;i<(n);++i)
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define RREP(i, n) for(int i=(int)(n);i>=0;--i)
#define RFOR(i, a, b) for(int i=(int)(a);i>=(int)(b);--i)
#define ALL(a) (a).begin(),(a).end()
#define DUMP(x) cerr<<#x<<" = "<<(x)<<endl
#define DEBUG(x) cerr<<#x<<" = "<<(x)<<" (L"<<__LINE__<<")"<< endl;

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using P = pair<int, int>;

const double eps = 1e-8;
const ll MOD = 1000000007;
const int INF = INT_MAX / 2;
const ll LINF = LLONG_MAX / 2;

template <typename T1, typename T2>
bool chmax(T1 &a, const T2 &b) {
  if(a < b) {a = b; return true;}
  return false;
}

template <typename T1, typename T2>
bool chmin(T1 &a, const T2 &b) {
  if(a > b) {a = b; return true;}
  return false;
}

template<typename T1, typename T2>
ostream& operator<<(ostream &os, const pair<T1, T2> p) {
  os << p.first << ":" << p.second;
  return os;
}

template<class T>
ostream &operator<<(ostream &os, const vector<T> &v) {
  REP(i, SZ(v)) {
    if(i) os << " ";
    os << v[i];
  }
  return os;
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(10);

  string s = "1";
  int keta = 10;
  REP(i, 10) {
    cout << "? " << s << endl;
    char c; cin >> c;
    if(c == 'N') {
      keta = i;
      break;
    }
    s.push_back('0');
  }
  if(keta == 10) {
    string tmp = "";
    string ans = "";
    REP(i, 9) {
      tmp.push_back('2');
      if(i == 0) ans.push_back('1');
      else ans.push_back('0');
      cout << "? " << tmp << endl;
      char c; cin >> c;
      if(c == 'Y') {
        cout << "! " << ans << endl;
        return 0;
      }
    }
    cout << "! " << 1000000000 << endl;
    return 0;
  }

  string ans = "";
  for(int i=keta;i>=1;--i) {
    int l, r;
    if(i == keta) {
      l = 0;
      r = 9;
    } else {
      l = -1;
      r = 9;
    }
    while(r - l > 1) {
      int mid = (l + r) / 2;
      string tmp = "";
      REP(j, keta-i) {
        tmp.push_back(ans[j]);
      }
      tmp.push_back(mid + '0');
      REP(j, i) {
        tmp.push_back('9');
      }
      cout << "? " << tmp << endl;
      char c; cin >> c;
      if(c == 'Y') {
        r = mid;
      } else {
        l = mid;
      }
    }
    ans.push_back(r+'0');
  }
  cout << "! " << ans << endl;
}
























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

using _i64 = int64_t;
using _u64 = uint64_t;
using _f64 = double;

#define endl "\n"

#define _for(i, start, end) for(_i64 i = (_i64)start; i < (_i64)end; ++i)
#define _rep(i, number) _for(i, 0, number)
#define _foreach(e, data) for(auto& e : data)
#define _all(data) data.begin(), data.end()

template<typename type>
_i64 _size(const type& data) { return static_cast<_i64>(data.size()); }
template<typename type, size_t size>
_i64 _size(const type (&)[size]) { return static_cast<_i64>(size); }

enum _flag : bool { able = true, disable = false };

struct _time {
    _time(_flag flag) { check = flag; if(!check) { return; } gettime(start); }
    ~_time() {
        if(!check) { return; }; gettime(end);
        _i64 elapse = chrono::duration_cast<chrono::milliseconds>(end - start).count();
        cout << endl << "Time: " << elapse << " ms" << endl;
    }
    private:
    using _timer = chrono::time_point<chrono::system_clock>;
    _timer start, end; bool check;
    void gettime(_timer& time) { time = chrono::system_clock::now(); }
};

struct _ini { _ini() { ios::sync_with_stdio(false); cin.tie(nullptr); } } _ini;

#include <boost/multiprecision/cpp_int.hpp>

namespace boost_mp = boost::multiprecision;

int main() {
    {
        _time time(disable);
        _i64 N; boost_mp::cpp_int data1, data2; cin >> N;
        const boost_mp::cpp_int max = boost_mp::pow((boost_mp::cpp_int)10, 80);
        _rep(i, N) {
            cin >> data1 >> data2;
            if(data1 + data2 < max) { cout << data1 + data2 << endl; }
            else { cout << "overflow" << endl; }
        }
    }
    return 0;
}


Measured memory_bytes: 3100