akhauriyash/Code-Regression huggingface dataset:
# import sys
# input = sys.stdin.readline
import bisect

# template input
def IT():  # 整数1個
    return int(input())

def IL():  # 整数複数
    return [int(_) for _ in input().split()]

def IS():  # 文字列複数
    return [_ for _ in input().split()]

def ILS(n):  # 整数1つ　縦にズラーってなってるやつ
    return [int(input()) for _ in range(n)]

def SLS(n):  # 文字列　縦にズラーってなってるやつ
    return [input() for _ in range(n)]

def ILSS(n):  # 整数複数　縦にズラーってなってるやつ
    return [[int(_) for _ in input().split()] for j in range(n)]

# template technique
def bit_full_search(ss):
    n = len(ss)
    for i in range(1 << n):
        s = ""
        for j in range(n + 1):
            if ((1 & i >> j) == 1):
                s += ss[j]
        print(s)

def bit_full_search2(A):
    # https://blog.rossywhite.com/2018/08/06/bit-search/
    value = []
    for i in range(1 << len(A)):
        output = []

        for j in range(len(A)):
            if ((i >> j) & 1) == 1:
                # output.append(A[j])
                output.append(A[j])
        value.append([format(i, 'b').zfill(16), sum(output)])

    value.sort(key=lambda x: x[1])
    bin = [value[k][0] for k in range(len(value))]
    val = [value[k][1] for k in range(len(value))]
    return bin, val

def matching_bisect(list1_val, list2_val, n):
    # 2分探索
    j = 0
    for i in range(len(list1_val)):
        j = bisect.bisect_left(list2_val, n - list1_val[i])
        if j < len(list2_val):
            if list1_val[i] + list2_val[j] == n:
                # ans = list2_bin[j] + list1_bin[i]
                break
    return j

"""ここからメインコード"""

def main():
    n = IT()
    AB = ILSS(n)
#    print(AB)

    for i in range(n):
        AB[i].append(AB[i][1] + AB[i][0])
    AB.sort(key=lambda x: x[2], reverse = True)

    a_point = 0
    b_point = 0
    for i in range(n):
        if i % 2 == 0:
            a_point += AB[i][0]
        else:
            b_point += AB[i][1]
    print(a_point - b_point)

main()


Measured memory_bytes: 26024
#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 2e9
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;

int main()
{
	int a[3];
	REP(i, 3) cin >> a[i];

	sort(a, a + 3);

	if (a[0] == 5 && a[1] == 5 && a[2] == 7) cout << "YES" << endl;
	else cout << "NO" << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define M 1101
#define MOD 1000000007
#define fi first
#define se second
#define vi vector<int>
#define vl vector<ll>
#define all(v) v.begin(),v.end()
#define allr(v) v.rbegin(),v.rend()
#define repl(i,l,r) for(long long i=l;i<=r;++i)
#define rep(i,l,r) for(int i=l;i<=r;++i)
#define ins insert
#define inf INT_MAX
#define vp vector< pair<int,int> >
int n,m;
int parent[100005];
void make_set(int v){
    parent[v]=v;
}
int find_set(int v)
{
    if(v==parent[v])
    {
        return v;
    }
    return parent[v]=find_set(parent[v]);
}
void union_sets(int a,int b)
{
    a=find_set(a);
    b=find_set(b);
    if(a!=b)
    {
        if(rand()%2)
        {
            swap(a,b);
        }
        parent[b]=a;
    }

}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n>>m;
    rep(i,1,n)
    {
        make_set(i);
    }
    rep(i,1,m)
    {
        int x,y,z;cin>>x>>y>>z;
        union_sets(x,y);
    }
    int ans=0;
    rep(i,1,n)
    {
        if(i==find_set(i))
        {
            ans++;
        }
    }
    cout<<ans<<"\n";
    return 0;
}



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

#define rep(i,n) for(int i=0; i<(n); i++)
#define reps(i,n) for(int i=1; i<(n); i++)
#define pii pair<int,int>
#define gsort(x,n) sort((x),(x)+(n),greater<int>())
#define all(x) (x).begin(), (x).end()
#define rv(s) reverse((s).begin(),(s).end())
#define int long long
#define abs(a) llabs(a)
#define setout(n,x) setw(n) << setfill(x)
#define Fixed fixed << setprecision(10)
const long long mod = 1000000007;
using namespace std;

signed main(){

    cin.tie(0);
    ios::sync_with_stdio(false);

    string s;
    cin>>s;
    sort(all(s));
    int cnt = 1;
    
    if(s.size()==1){
        cout<<"No"<<'\n';
        return 0;
    }

    rep(i,s.size()){
        if(i!=0){
            if(s[i]==s[i-1]) cnt++;

            if(s[i]!=s[i-1]){
                if(cnt % 2 != 0){
                    cout<<"No"<<'\n';
                    return 0;
                }
                cnt = 1;
            }
        }
    }
    cout<<"Yes"<<'\n';
}

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

int main(){
  string S;
  
  cin>>S;
  
  for(int i=0;i<S.size()/2;++i){
    if(S[i]!=S[S.size()-1-i]){
      cout<<"No"<<endl;
      return 0;
    }
  }
  
  cout<<"Yes"<<endl;
}

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

S = input()

if S[0] == S[1]:
    if S[0] != S[2] and S[2] == S[3]:
        print("Yes")
    else:
        print("No")
elif S[0] == S[2]:
    if S[0] != S[1] and S[1] == S[3]:
        print("Yes")
    else:
        print("No")
elif S[0] == S[3]:
    if S[0] != S[1] and S[1] == S[2]:
        print("Yes")
    else:
        print("No")
else:
    print("No")


Measured memory_bytes: 3064
n = gets.to_i
a = gets.split.map(&:to_i)
r = n.even?
first = a.shift
odds = a.select.with_index(1) { |_,i| i.odd? }
evens = a.select.with_index(1) { |_,i| i.even? }

if r
  puts (odds.reverse + [first] + evens).join(" ")
else
  puts (evens.reverse + [first] + odds).join(" ")
end


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

int main(){
    int n, x; cin >> n >> x;
    if (x == 1 || x == 2 * n - 1) {
        cout << "No" << endl;
        return 0;
    }
    cout << "Yes" << endl;
    if (n == 2) {
        cout << 1 << endl;
        cout << 2 << endl;
        cout << 3 << endl;
        return 0;
    }
    vector<int> ans(2*n-1, -1);
    vector<bool> check(2*n, false);
    if (x == 2) {
        ans[n-2] = 3;
        ans[n-1] = 2;
        ans[n]   = 1;
        ans[n+1] = 4;
    }
    else {
        ans[n-2] = x-1;
        ans[n-1] = x;
        ans[n]   = x+1;
        ans[n+1] = x-2;
    }
    for (int i = 0; i < 2*n-1; i++) {
        if (ans[i] == -1) continue;
        check[ans[i]] = true;
    }
    int id = 1;
    for (int i = 0; i < 2*n-1; i++) {
        if (ans[i] != -1) continue;
        while (check[id]) id++;
        ans[i] = id; id++;
    }
    for (int i = 0; i < 2*n-1; i++) {
        cout << ans[i] << endl;
    }
    return 0;
}

Measured memory_bytes: 4064
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <math.h>
#include <map>
using namespace std;

bool check(string s){
    vector<int> v(26,0);
    for(int i=0;i<s.length();i++)v[s[i]-'a']++;
    int m=0;
    for(int i=0;i<26;i++)m=max(v[i],m);
   if( m>s.length()/2)return true;
   else return false;
}

int main(){
string s;cin>>s;long long n=s.length();
for(int i=0;i<n-1;i++){
    if(check(s.substr(i,2))){cout<<i+1<<" "<<i+2;return 0;}
}
for(int i=0;i<n-2;i++){
    if(check(s.substr(i,1+2))){cout<<i+1<<" "<<i+3;return 0;}
}
cout<<-1<<" "<<-1;
}

Measured memory_bytes: 512
// https://atcoder.jp/contests/arc097/tasks/arc097_b

#include <iostream>
#include <vector>
#include <array>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <algorithm>
#include <iomanip>
#include <cmath>
#include <limits>

using namespace std;

int u_find(vector<int>& roots, int id) {
	if (roots[id] == id) {
		return id;
	} else {
		return roots[id] = u_find(roots, roots[id]);
	}
}

int main (int argc, char* argv[]) {
	int n, m;
	cin >> n >> m;

	vector<int> p(n);
	vector<int> roots(n);
	for (int i = 0; i < n; i++) {
		cin >> p[i];
		p[i]--;
		roots[i] = i;
	}

	for (int i = 0; i < m; i++) {
		int from, to;
		cin >> from >> to;
		from--; to--;
		int f_id = u_find(roots, from);
		int t_id = u_find(roots, to);
		if (f_id != t_id) {
			roots[f_id] = t_id;
		}
	}

	int res = 0;
	for (int i = 0; i < n; i++) {
		if (u_find(roots, i) == u_find(roots, p[i]) ) {
			res++;
		}
	}
	cout << res << endl;
}


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

int cnt;
void chk(bool map[9][9], int N, int cur, int depth, bool checked[9]){
    if(depth==N){
        cnt++;
        return;
    }
    for(int i=1;i<=N;i++){
        if(map[cur][i]&&(!checked[i])){
            bool fl[9];
            for(int j=1;j<=8;j++) fl[j]=checked[j];
            fl[i]=true;
            chk(map,N,i,depth+1,fl);
        }
    }
}

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

    bool map[9][9];
    for(int i=1;i<=8;i++){
        for(int j=1;j<=8;j++){
            map[i][j]=false;
        }
    }

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

    bool fl[9];
    for(int i=1;i<=8;i++) fl[i]=false;

    cnt=0;
    fl[1]=true;
    chk(map,N,1,1,fl);

    cout << cnt << endl;

    return 0;
}

Measured memory_bytes: 256
#!/usr/bin/env python3

import array
import collections


UNDEF = -1


def compute_connected_components(max_v, adj_list):
    group = array.array("l", (UNDEF for _ in range(max_v)))
    g_idx = 0
    for u in range(max_v):
        if group[u] == UNDEF:
            group[u] = g_idx
            q = collections.deque()
            q.append(u)
            while q:
                v = q.popleft()
                for w in adj_list[v]:
                    if group[w] == UNDEF:
                        group[w] = g_idx
                        q.append(w)
            else:
                g_idx += 1
    return group


def main():
    n, m = map(int, input().split())
    adj_list = [set() for _ in range(n)]
    for _ in range(m):
        s, t = map(int, input().split())
        adj_list[s].add(t)
        adj_list[t].add(s)
    group = compute_connected_components(n, adj_list)
    q = int(input())
    for _ in range(q):
        s, t = map(int, input().split())
        print("yes" if group[s] == group[t] else "no")


if __name__ == '__main__':
    main()

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

int find(int a, vector<int> b, int i){
    for(int j = i; j <= INF; j++){
        if(b[j] == a) return j;
    }
    return INF;
}

bool check(int a[15], vector<int> b, int n){
    int A = 0, B = 0;
    rep(i,n){
        if(a[i] == 1) A++;
        if(b[i] == 1) B++;
    }
    return (A != B);
}

int countSwap(int a[15], vector<int> b, int n){
    if(check(a, b, n)) return INF;

    int ret = 0;
    rep(i,n){
        if(a[i] != b[i]){
            int p = find(a[i], b, i);
            ret += p - i;

            int temp = b[i];
            b[i] = b[p];
            b[p] = temp;
        }
    }
    return ret;
}

int main(){
    int n, m;
    int b[15], p[15];

    cin >> n >> m;
    rep(i,n) cin >> b[i];
    rep(i,m) cin >> p[i];

    vector<int> v0;
    vector<int> v1;

    int temp = 1;
    rep(i,m){
        rep(j,p[i]){
            v0.emplace_back((temp + 1) % 2);
            v1.emplace_back(temp);
        }
        if(temp == 1) temp = 0;
        else temp = 1;
    }
    cout << min(countSwap(b, v0, n), countSwap(b, v1, n)) << endl;
}

Measured memory_bytes: 3136
def abc170_c_1():
    """
    もうちょいコンパクトに書いてみる
    """
    def solve():
        x, n = map(int, input().split(' '))
        if n == 0:
            return x

        p = list(map(int, input().split(' ')))

        search_range_min = min(min(p), x) - 1
        search_range_max = max(max(p), x) + 1
        search_values = [i for i in range(search_range_min, search_range_max + 1) if i not in p]

        ans = min(search_values, key=lambda a: abs(a - x))

        return ans
    
    print(solve())

if __name__ == '__main__':
    abc170_c_1()


Measured memory_bytes: 9172
import java.util.*;

public class Main {

    static class Edge {
        int from, to;
        public Edge(int from, int to) {
            this.from = from;
            this.to = to;
        }
    }

    static void bfs(int start) {
        visited = new boolean[n];
        visited[start] = true;

        Deque<Integer> deque = new ArrayDeque<>();
        deque.offer(start);

        while (!deque.isEmpty()) {
            Integer node = deque.poll();
            List<Edge> edges = graph.get(node);

            for (Edge edge : edges) {
                if (visited[edge.to]) continue;
                dist[start][edge.to] = dist[start][node] + 1;
                visited[edge.to] = true;
                deque.offer(edge.to);
            }
        }
    }

    static void createGraph() {
        graph = new ArrayList<>();
        for (int i = 0; i < n; ++i) graph.add(new ArrayList<>());
        for (int i = 0; i < n - 1; ++i) {
            graph.get(i).add(new Edge(i, i + 1));
            graph.get(i + 1).add(new Edge(i + 1, i));
        }
    }

    static int n;
    static int x;
    static int y;
    static int[][] dist;
    static boolean[] visited;
    static List<List<Edge>> graph;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        x = sc.nextInt() - 1;
        y = sc.nextInt() - 1;
        createGraph();
        graph.get(x).add(new Edge(x, y));
        graph.get(y).add(new Edge(y, x));
        dist = new int[n][n];
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                dist[i][j] = 0;
            }
        }

        for (int i = 0; i < n; ++i) {
            bfs(i);
        }

        int[] arr = new int[n + 1];
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                arr[dist[i][j]]++;
            }
        }

        for (int i = 1; i < n; ++i) {
            System.out.println(arr[i]);
        }
    }
}

Measured memory_bytes: 75688
#include<bits/stdc++.h>
#define ll long long
using namespace std;
bool pal(string s){
    int l=0,r=s.length()-1;
    if(r+1==1)return 1;
    while(l<r){
        if(s[l]!=s[r])return 0;
        l++;r--;
    }
    return 1;
}
int main(){
    string s;cin>>s;
    int n=s.length();
    if(!pal(s)){
        //cout<<1<<endl;
        cout<<"No"<<endl;
        return 0;
    }
    string s1=s.substr(0,(n-1)/2);
    if(!pal(s1)){
        //cout<<2<<endl;
        cout<<"No"<<endl;
        return 0;
    }
    int l=(n+3)/2;l--;
    s1=s.substr(l,n-l);
    if(!pal(s1)){
        //cout<<3<<endl;
        cout<<"No"<<endl;
        return 0;
    }
    cout<<"Yes"<<endl;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = Integer.parseInt(sc.next());
        int b = Integer.parseInt(sc.next());
        int ans = 1;
        int cnt = 0;
        cnt = b - a;
        if (b == 1) {
            System.out.println(0);
        } else if (cnt <= 0) {
            System.out.println(ans);
        } else {
            while (cnt > 0) {
                cnt = cnt - a + 1;
                ans++;
            }
            System.out.println(ans);
        }
    }
}

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

public class ABC0137_A1v1 {
    private static void Main(string[] args) {
        var input = Console.ReadLine().Trim();
        Prepare(input);
    }

    private static void Prepare(string input) {
        var numbers = input.Split().Select(x => int.Parse(x)).ToArray();
        Compute(numbers[0], numbers[1]);
    }

    private static void Compute(int numA, int numB) {
        var candidates = new int[] {
            numA + numB,
            numA - numB,
            numA * numB,
        };
        var answer = candidates.Max();

        OutputAnswer(answer.ToString());
    }

    private static void OutputAnswer(string text) => Console.WriteLine(text);
}

Measured memory_bytes: 13396
#include<bits/stdc++.h>
using namespace std;
string a;
int n;
bool cfind=false,ffind=false;
int main()
{
	std::ios::sync_with_stdio(false);
	cin>>a;
	for(int i=0;i<a.size();i++)
	{
		if(a[i]=='C')
		{
			for(int j=i+1;j<=a.size();j++)
            {
            	if(a[j]=='F')
            	{
            		cout<<"Yes"<<endl;
            		return 0;
				}
            }
		}
	 } 
	 cout<<"No"<<endl;
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
using namespace std;
int main()
{
  int N, M;
  cin >> N >> M;
  vector <int> A(N);
  int sum = 0;
  for (int i = 0; i < N; i++) {
    cin >> A[i];
    sum += A[i];
  }
  int popular = 0;
  for (int i = 0; i < N; i++) {
    if ((A[i]*4*M) >= sum) {
      popular++;
    }
  }
  if (popular >= M) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
  return 0;
}


Measured memory_bytes: 256
import numpy as np
import sys
N, M, K = [int(x) for x in input().split(" ")]
A = [0] + [int(x) for x in input().split(" ")]
B = [0] + [int(x) for x in input().split(" ")]

Acum = np.cumsum(A)
Bcum = np.cumsum(B)

# iが増えるとjは非増加であることを利用して、jはM側からdecrementしていく
ans, j = 0, M
for i in range(N+1):
    a = Acum[i]
    if a > K:
        break
    while Bcum[j] > K - a:
        j -= 1
    ans = max([i + j, ans])
print(ans)



Measured memory_bytes: 59912
// J'aime
// Chemise Blanche

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

#define int long long

#define ii pair<int,int>
#define fi first
#define sc second

#define all(x) (x).begin(),(x).end()
#define dbg(x) cerr << __LINE__ << " > " << #x << " = " << (x) << endl

void MAIN() {
  int n; cin >> n;
  vector<int> v(n);
  for (auto &i : v) cin >> i;
  vector<int> c(n);
  for (auto &i : c) cin >> i;
  int ans = 0;
  for (int i = 0; i < (1 << n); i++) {
    int x = 0, y = 0;
    for (int j = 0; j < n; j++) {
      if ((i >> j) & 1) {
        x += v[j];
        y += c[j];
      }
    }
    ans = max(ans, x - y);
  }
  cout << ans << '\n';
}

signed main() {
#ifdef _DEBUG
  // freopen("in" , "r", stdin );
  // freopen("out", "w", stdout);
#endif
  ios::sync_with_stdio(0); cin.tie(0);
  int T = 1;
  // cin >> T;
  while (T--) MAIN();
}


Measured memory_bytes: 3648
#include <iostream>
#include <string>
#include <stdlib.h>
#include <algorithm>
#include <math.h>
using namespace std;

int main(void) {
    
    int n;
    cin >> n;
    
    int current_target = 0;
    int max_divide_times = 0;
    int current_max_num = 1;
    int counter = 0;
    
    while (n >= 1) {
        current_target = n;
        counter = 0;
        
        while (current_target % 2 == 0) {
            counter++;
            current_target /= 2;
        }
        
        if (counter > max_divide_times) {
            max_divide_times = counter;
            current_max_num = n;
        }
        n--;
    }
    
    cout << current_max_num << endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<stdio.h>
#include<cstring>
#include<cmath>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
#include<unordered_map>
#define ll long long 
#define dd double
using namespace std;
 
int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  
  int p,q,r;
  cin>>p>>q>>r;
  int a[3];
  a[0]=p;
  a[1]=q;
  a[2]=r;
  int i,j;
  int smallest=a[0]+a[1];
  for(i=0;i<3;i++){
  	for(j=0;j<3;j++){
  		if(i!=j){
  			if(smallest>a[i]+a[j]){
  				smallest=a[i]+a[j];
			  }
		  }
  		
	  }
  }
  
  cout<<smallest<<endl;
  
  
  
  return 0;
}

Measured memory_bytes: 3632
n = int(input())
n1, n2 = 200001, 400001
s1, s2 = [[] for _ in range(n1)], [[] for _ in range(n1)]
s3, s4 = [[] for _ in range(n2)], [[] for _ in range(n2)]
for _ in range(n):
    x, y, u = input().split()
    x, y = int(x), int(y)
    a, b = x + y, x - y + 200000
    s1[x].append([y, u])
    s2[y].append([x, u])
    s3[a].append([b, u])
    s4[b].append([a, u])
ans = 100000000
for t in s1:
    if not t:
        continue
    a, b = -1, -1
    t.sort()
    for tt in t:
        if tt[1] == "U":
            a = tt[0]
        elif tt[1] == "D":
            b = tt[0]
        if not min(a, b) == -1 and a < b:
            ans = min(ans, 5 * (b - a))
for t in s2:
    if not t:
        continue
    a, b = -1, -1
    t.sort()
    for tt in t:
        if tt[1] == "R":
            a = tt[0]
        elif tt[1] == "L":
            b = tt[0]
        if not min(a, b) == -1 and a < b:
            ans = min(ans, 5 * (b - a))
for t in s3:
    if not t:
        continue
    a, b, c, d = -1, -1, -1, -1
    t.sort()
    for tt in t:
        if tt[1] == "U":
            a = tt[0]
        elif tt[1] == "D":
            b = tt[0]
        elif tt[1] == "R":
            c = tt[0]
        elif tt[1] == "L":
            d = tt[0]
        if not min(a, c) == -1 and a > c:
            ans = min(ans, 5 * (a - c))
        if not min(b, d) == -1 and d > b:
            ans = min(ans, 5 * (d - b))
for t in s4:
    if not t:
        continue
    a, b, c, d = -1, -1, -1, -1
    t.sort()
    for tt in t:
        if tt[1] == "U":
            a = tt[0]
        elif tt[1] == "D":
            b = tt[0]
        elif tt[1] == "R":
            c = tt[0]
        elif tt[1] == "L":
            d = tt[0]
        if not min(b, c) == -1 and c < b:
            ans = min(ans, 5 * (b - c))
        if not min(a, d) == -1 and a < d:
            ans = min(ans, 5 * (d - a))
print(ans if not ans == 100000000 else "SAFE")

Measured memory_bytes: 257868
#include<iostream>
#include<cstdio>
#include<queue>
#include<vector>
#include<string.h>
#include<algorithm>
#include<cmath>
#include<map>

using namespace std;



long long i,j,k,N,K,ans,n,m;

char S[20],A[26]={'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};

int main()
{
  cin>>N;
  
  m=0;
  n=N-1;
  k=1;
  while(n>=0)
  {
    k*=26;
    m+=1;
    n+=-k;
  }
  n+=k;

  for(i=0;i<m;i++)
  {
    j=n%26;
    S[m-i-1]=A[j];
    n=n/26;
  }
  
  for(i=0;i<m;i++)
  {
    cout<<S[i];
  }
  
  
}

Measured memory_bytes: 3648
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<map>
#include<unordered_map>

using namespace std;

typedef long long ll;
typedef vector <ll> v_ll;
typedef vector <vector <ll> > vv_ll;
typedef vector < pair <ll,ll> > vp_ll;
typedef pair <ll,ll> p_ll;

ll mod_inv(ll x,ll n){
  x%=n;
  if (x<0) x+=n;
  ll y = x,z = n-2;
  ll ret=1;
  while (z>0){
    if(z%2==1){
      ret*=y;
      ret%=n;
    }
    y*=y;
    y%=n;
    z/=2;
  }
  return ret;
}

ll N,A,B,K;
ll MOD;
int main(){
  MOD=998244353;
  cin >> N >> A >> B >> K;
  v_ll NCK(N+1,0);
  NCK[0]=1;
  for (ll i=1;i<=N;i++){
    NCK[i]=(NCK[i-1]*(N+1-i))%MOD;
    NCK[i]*=mod_inv(i,MOD);
    NCK[i]%=MOD;
  }
  /*
  for (ll i=0;i<=N;i++){
    cout << NCK[i] << endl;
  }
  */
  ll ans=0;
  ll a=0,b=0;
  for (ll i=0;i<=N;i++){
    if ( (K>=A*i) && (K-A*i)%B==0 && (K-A*i)/B<=N ){
      a=i;b=(K-A*i)/B;
      ans+=(NCK[a]*NCK[b])%MOD;
      ans%=MOD;
    }
  }
  cout << ans << endl;
}


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

typedef pair<int,int>P;

#define X first
#define Y second

int mp[5010][5010];

set<int>xs;
set<int>ys;

int xl[5010];
int yl[5010];

int x_find(int n){
	int le=0,ri=5009;
	while(le!=ri){
		int p=(le+ri)/2;
		if(xl[p]==n)return p;
		if(xl[p]<n)le=p+1;
		else ri=p-1;
	}
	return le;
}

int y_find(int n){
	int le=0,ri=5009;
	while(le!=ri){
		int p=(le+ri)/2;
		if(yl[p]==n)return p;
		if(yl[p]<n)le=p+1;
		else ri=p-1;
	}
	return le;
}

int x_find2(int n){
	int le=0,ri=5005,p=2502;
	while(le<ri){
		if(xl[p]==n)return p;
		if(xl[p]<n)le=p+1;
		else ri=p-1;
		p=(le+ri)/2;
	}
	if(xl[p]==n)return p;
	while(xl[p]>n)p--;
	while(xl[p+1]<n)p++;
	return p;
}

int y_find2(int n){
	int le=0,ri=5005,p=2502;
	while(le<ri){
		if(yl[p]==n)return p;
		if(yl[p]<n)le=p+1;
		else ri=p-1;
		p=(le+ri)/2;
	}
	if(yl[p]==n)return p;
	while(yl[p]>n)p--;
	while(yl[p+1]<n)p++;
	return p;
}

int x_find3(int n){
	int le=0,ri=5005,p=2502;
	while(le<ri){
		if(xl[p]==n)return p;
		if(xl[p]<n)le=p+1;
		else ri=p-1;
		p=(le+ri)/2;
	}
	if(xl[p]==n)return p;
	while(xl[p]<n)p++;
	while(xl[p-1]>n)p--;
	return p;
}

int y_find3(int n){
	int le=0,ri=5005,p=2502;
	while(le<ri){
		if(yl[p]==n)return p;
		if(yl[p]<n)le=p+1;
		else ri=p-1;
		p=(le+ri)/2;
	}
	if(yl[p]==n)return p;
	while(yl[p]<n)p++;
	while(yl[p-1]>n)p--;
	return p;
}

int main(){
	
	int n,m;
	cin>>n>>m;
	
	vector<P>V;
	
	xs.insert(-1100000000);
	ys.insert(-1100000000);
	xs.insert(-1100000001);
	ys.insert(-1100000001);
	
	for(int i=0;i<n;i++){
		int x,y;
		cin>>x>>y;
		V.push_back(P(x,y));
		xs.insert(x);
		ys.insert(y);
	}
	
	for(int i=1100000000;xs.size()<5010;i++){
		xs.insert(i);
	}
	for(int i=1100000000;ys.size()<5010;i++){
		ys.insert(i);
	}
	
	set<int>::iterator it = xs.begin();
	for( int i=0;it != xs.end(); i++){
		xl[i]=*it;
		++it;
	}
	
	set<int>::iterator it2 = ys.begin();
	for( int i=0;it2 != ys.end(); i++){
		yl[i]=*it2;
		++it2;
	}
	
	for(int i=0;i<n;i++){
		mp[x_find(V[i].X)][y_find(V[i].Y)]++;
	}
	
	
	for(int j=0;j<5010;j++){
		for(int i=1;i<5010;i++){
			mp[i][j]+=mp[i-1][j];
		}
	}
	
	for(int j=0;j<5010;j++){
		for(int i=1;i<5010;i++){
			mp[i][j]+=mp[i][j-1];
		}
	}
	
	for(int i=0;i<m;i++){
		int x1,y1,x2,y2;
		cin>>x1>>y1>>x2>>y2;
		x1=x_find3(x1);
		y1=y_find3(y1);
		x2=x_find2(x2);
		y2=y_find2(y2);
		
		
		cout<<mp[x2][y2]-mp[x2][y1-1]-mp[x1-1][y2]+mp[x1-1][y1-1]<<endl;
		//cout<<mp[x2][y2]<<" "<<mp[x2][y1]<<" "<<mp[x1][y2]<<" "<<mp[x1][y1]<<endl;
		//cout<<mp[x2][y2]-mp[x2][y1]-mp[x1][y2]+mp[x1][y1]<<endl;
		
	}
	
	
	return 0;
}


Measured memory_bytes: 99776
# -*- coding: utf-8 -*-
import sys

X = int(input())

if X < 100:
    print(0)
    sys.exit()

list_X = list(str(X))

one_X = list_X[-1]
ten_X = list_X[-2]

nessesary_money = 105 * 2 * int(ten_X)
if int(one_X) > 0 and int(one_X) <= 5:
    nessesary_money += 100 + int(one_X)
elif int(one_X) > 5:
    nessesary_money += 200 + int(one_X)

if nessesary_money <= X:
    print(1)
else:
    print(0)



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

using namespace std;


int main() {
  while (true) {
    int m, nmin, nmax;
    cin >> m >> nmin >> nmax;

    if (m + nmin + nmax == 0) {
      break;
    }
    vector<int> p(m);
    for (int i = 0; i < m; i++) {
      cin >> p[i];
    }

    int gapMax = -1;
    int gapMaxIdx = -1;
    for (int i = nmin - 1; i <= nmax - 1; i++) {
      int temp = p[i] - p[i + 1];
      if (temp >= gapMax) {
        gapMax = temp;
        gapMaxIdx = i;
      }
    }

    cout << gapMaxIdx + 1 << endl;
   
  }
  
  return 0;
}

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

using namespace std;

#define rep(i,s,e) for(int i=s; i<e; i++)

int main(){
    char s[20];
    cin >> s;

    s[5] = ' ';
    s[13] = ' ';

    cout << s << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
  using namespace std;
#define ll long long
#define fw(p) for(int w=0;w<(p);w++)
#define fx(p) for(int x=0;x<(p);x++)
#define fy(p) for(int y=0;y<(p);y++)
#define fz(p) for(int z=0;z<(p);z++)
#define fyg(p,g) for(int y=(g);y<(p);y++)
#define fzg(p,g) for(int z=(g);z<(p);z++)
#define ce(d) cout<<d<<endl;
#define vecp(p) int aa;cin>>aa;(p).push_back(aa);
#define vecpl(p) long long aa;cin>>aa;(p).push_back(aa);
#define vecps(p) string aa;cin>>aa;(p).push_back(aa);
#define vecp2(p) cin>>aa;(p).push_back(aa);
#define vecpl2(p) long long ab;cin>>ab;(p).push_back(ab);
#define vecps2(p) string ab;cin>>ab;(p).push_back(ab);
#define set0(k,n) for(int nn=0;nn<(n);nn++){ (k).push_back(0); }
#define sorts(c) sort((c).begin(),(c).end());
#define reverses(c) reverse((c).begin(),(c).end());
#define vec(b) vector<int> (b);
#define vecl(b) vector<long long> (b);
#define vecs(b) vector<string> (b);
#define vecsize(b,size) vector<int> (b)((size));
#define pb(b,a) (b).push_back((a));
#define doublece(a,b) cout<<(a)<<' '<<(b)<<endl;
#define pairs(s) vector<pair<int,int>> (s);
#define pairsl(s) vector<pair<ll,ll>> (s);
#define pairss(s) vector<pair<string,string>> (s);
#define pairsp(s) int aa,bb;cin>>aa>>bb;(s).push_back(make_pair(aa,bb));
#define pairspl(s) int aa,bb;cin>>aa>>bb;(s).push_back(make_pair(aa,bb));
#define pairsps(s) int aa,bb;cin>>aa>>bb;(s).push_back(make_pair(aa,bb));
#define pairsREV(s) (s).push_back(make_pair(bb,aa));
#define pairslREV(s) (s).push_back(make_pair(bb,aa));
#define pairssREV(s) (s).push_back(make_pair(bb,aa));
#define MOD 1000000007

int gcd(int x,int y){
	
	if(x%y==0){
		return y;
	}else{
		return gcd(y,x%y);
	}
	
}

int main() {
	
	int N;
  cin>>N;
	vec(A)
	vec(H)
	fx(N){
		vecp(H)
	}

	pb(A,H.at(0));
	fyg(N,1){
		int plus=A.at(y-1);
		if(H.at(y)>H.at(y-1)){
			plus+=H.at(y)-H.at(y-1);
		}
		pb(A,plus)
	}
	ce(A.at(N-1))
}


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

cnt_minus = len([a[i] for i in range(n) if a[i] < 0])

if cnt_minus % 2 == 0:
    print(sum([abs(a[i]) for i in range(n)]))
else:
    mi = min([abs(a[i]) for i in range(n)])
    print(sum([abs(a[i]) for i in range(n)]) - 2 * mi)


Measured memory_bytes: 66536
# from sys import stdin
# import math
from functools import lru_cache


@lru_cache(maxsize=1000)
def combinations_count(n, r):
    if n < 2:
        return 0
    return n*(n-1)//2


N = int(input())
A = list(map(int, input().split()))
# print(A)

d = {}
cnt = 0
for i in range(N):
    d[A[i]] = d.get(A[i], 0)+1
# print(d)
sum1 = 0
for key, value in enumerate(d):
    # print(key,value)
    sum1 = sum1+combinations_count(d.get(value, 0), 2)

for l in range(N):

    # print(d)
    # print(len(d))
    sum = 0
    sum = sum1-combinations_count(d.get(A[cnt], 0), 2)
    d[A[cnt]] = d.get(A[cnt], 0)-1
    sum = sum+combinations_count(d.get(A[cnt], 0), 2)
    # for key, value in enumerate(d):
    #     # print(key,value)
    #     sum = sum+combinations_count(d.get(value, 0), 2)
    print(sum)
    d[A[cnt]] = d.get(A[cnt], 0)+1
    # d = {}
    cnt += 1


Measured memory_bytes: 99020
#include <bits/stdc++.h>
#define int long long
using namespace std;
#define float long double
typedef vector<int> vi;
#define pb push_back

int mod(int a,int b){
    return (a-b)>0?(a-b):(b-a);
}


int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n;
	int k;
	cin >> n >> k;
	int *arr = new int [n];
	for(int i =0 ; i < n ; i++) cin >> arr[i];
	if(n == 1 ) cout << 0;
	else if(n == 2) cout << mod(arr[1],arr[0]);
	else{
        int *temp = new int [n];
        temp[1] = mod(arr[1],arr[0]);
        temp[0] = 0;
        for(int i  = 2 ; i < n ; i++){
                int t = INT_MAX;
            for(int j = 1 ; j <=k && i-j>=0; j++){
                t = min(t,temp[i-j] + mod(arr[i],arr[i-j]));
            }
            temp[i] = t;
        }
        cout << temp[n-1] ;
	}
}


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

int main() {

  double N ; cin >> N;
  
  double L, H, W;
  double V = 0, maxV = 0;
  
  for (int i = 0; i < 100000000; i++) {
    
    L = N/4 + i*0.000001;
    H = L;
    W = N - L - H;
    if (W < 0 ) break;
    
    V = L * H * W;
    
    if (V > maxV) maxV = V;
  }

//cout << maxV << endl; 
    printf("%.12lf\n", maxV);
}


Measured memory_bytes: 256
#include "stdio.h"

long long int N;
long long int A[100001];
bool flag=false;
bool flag2 = false;
bool flag3=false;
long long int ans=1;

int main() {
	scanf("%lld", &N);
	for (int i = 1; i <= N; i++) {
		scanf("%lld", &A[i]);
		if (i > 1) {
			if (!flag3) {
				if (A[i] - A[i - 1] > 0) {
					flag = true;
					flag2 = true;
					flag3 = true;
				}
				if (A[i] - A[i - 1] < 0) {
					flag = false;
					flag2 = false;
					flag3 = true;
				}
			}
			else {
				if (A[i] - A[i - 1] > 0) {
					flag2 = true;
				}
				if (A[i] - A[i - 1] < 0) {
					flag2 = false;
				}
				if (flag != flag2) {
					flag = flag2;
					ans++;
					flag3 = false;
				}
			}
		}
	}
	printf("%lld\n", ans);
}

Measured memory_bytes: 896
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <climits>
#include <algorithm>
#include <map>
#include <set>
#include <stack>
#include <vector>
#include <queue>
#include <bitset>
#include <string>
using namespace std;
 
#define rep(i,n) for(int i=0; i<n; i++)
#define repa(i,s,e) for(int i=s; i<=e; i++)
#define repd(i,s,e) for(int i=s; i>=e; i--)
 
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef pair<int, int> pii;

string line;
int S, r, N;
vi cakes;

const int MAX_N = 15;
const int TSIZE = (2 << MAX_N) + 1;
double edges[MAX_N][MAX_N];
double dp[TSIZE][MAX_N];
bitset<15> used;

double minval;

void dfs(int v, int s, double value) {
	if(used.count() == N) {
		minval = min(minval, value + cakes[s] + cakes[v]);
		return;
	}

	int state = used.to_ulong();
	if(dp[state][v] <= value) return; 
	
	dp[state][v] = value;
	for(int i=0; i<N; i++) {
		if(v != i && !used[i]) {
			value += edges[v][i];
			used.set(i);
			dfs(i, s, value);
			used.reset(i);
			value -= edges[v][i];
		}
	}
}

void solve() {
	N = cakes.size();
	memset(&edges[0][0], 0, sizeof(double) * MAX_N * MAX_N);
	for(int i=0; i<TSIZE; i++) for(int j=0; j<MAX_N; j++) dp[i][j] = 10000.0;

	for(int i=0; i<N; i++) {
		for(int j=i+1; j<N; j++) {
			double d = 2.0 * sqrt((double)(cakes[i] * cakes[j]));
			edges[i][j] = edges[j][i] = d;
		}
	}

	minval = 10000.0;
	for(int i=0; i<N; i++) {
		used.set(i);
		dfs(i, i, 0.0);
		used.reset(i);
	}
	//cout << minval << endl;
	cout << (minval <= S ? "OK" : "NA") << endl;
}

int main() {
	while( 1 ) {
		getline(cin, line);
		if(line == "") break;

		stringstream ss;
		ss << line;
		ss >> S;
		cakes.clear();
		while(ss>>r) {
			cakes.push_back(r);
		}
		solve();
	}
}

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

int main() {
    int N;
    string S;
    cin >> N >> S;
    long long tmpans = 0;
    long long ans = 0;
    for (int i = 0; i < N; i++) {
        if (S[i] == 'I') {
            tmpans++;
        } else {
            tmpans--;
        }
        ans = max(ans, tmpans);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast,no-stack-protector") 
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>

#define int long long
#define ll long long
#define ull unsigned long long
#define ld long double
#define rep(i, l, r) for (int i = l; i < r; i++)
#define repb(i, r, l) for (int i = r; i > l; i--)
#define sz(a) (int)a.size()
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define pb push_back
#define mp(a, b) make_pair(a, b)
#define ret(a) {cout << a; exit(0);}

using namespace std;

mt19937 mrand(random_device{}()); 
const ll mod=1000000007;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b,ll mod) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}

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

const int N = 2e5 + 123;
int n , m , k;
int a[N];
string s;
main(){
	ios::sync_with_stdio(0); cin.tie(0);cout.tie(0);
	int a;
	cin >> a;
	cout << a * a;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define s first
#define p second
using namespace std;
typedef pair<pair<int,int>,pair<int,int> > P;
int d[32][32][4],h,w,c[32][32],e[4],dx[]={0,1,0,-1},dy[]={-1,0,1,0};
priority_queue<P,vector<P>,greater<P> >Q;
void Pb(int a,int b,int f,int g){Q.push(make_pair(make_pair(a,b),make_pair(f,g)));}
void B(int k,int z,int y,int x){
	d[y][x][z]=k;
	for(int i=0;i<4;i++){
		int r=(i+z)%4,xx=x+dx[r],yy=y+dy[r];
		if(xx<0||yy<0||xx==w||yy==h)continue;
		if(i==c[y][x])Pb(k,r,yy,xx);
		else Pb(k+e[i],r,yy,xx);
	}
}
int main(){
	while(cin>>w>>h&&w){
	for(int i=0;i<h;i++){
		for(int j=0;j<w;j++){
			cin>>c[i][j];
			for(int k=0;k<4;k++)d[i][j][k]=11451419;
		}
	}Pb(0,1,0,0);
	for(int i=0;i<4;i++)cin>>e[i];
	while(!Q.empty()){
		int a=Q.top().s.s,b=Q.top().s.p,f=Q.top().p.s,g=Q.top().p.p;
		Q.pop();if(d[f][g][b]>a)B(a,b,f,g);
	}
	int a=11451419;
	for(int i=0;i<4;i++)a=min(a,d[h-1][w-1][i]);
	cout<<a<<endl;
	}return 0;
}

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

using vb=vector<bool>;
using vi=vector<int>;
using vvi=vector<vi>;
using ll=long long;
using vl=vector<ll>;
using vvl=vector<vl>;
using si=set<int>;
using qi=queue<int>;
using pi=pair<int,int>;

void solve() {
    int k,a,b; cin>>k>>a>>b;
    if(a/k<b/k||a%k==0){
        cout<<"OK\n";
    }else{
        cout<<"NG\n";
    }
}

bool boosts=false, tests=false;

int main() {
    if(boosts) {
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
    }

    int tcases=1;
    if(tests) {
        cin>>tcases;
    }
    for(int tcase=1; tcase<=tcases; tcase++) {
        solve();
    }

    return 0;
}


Measured memory_bytes: 3648
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define rep2(i,a,b) for(int i=a;i<=b;i++)
#define pb push_back
#define eb emplace_back

int in(){int x;cin>>x;return x;}

int pos;
int a[200];
char s[1100];
int number(){
    return a[s[pos++]];
}
int expr();
int factor(){
    bool f=false;
    if(s[pos]=='-'){
        f=true;
        pos++;
        return 1-factor();
    }
    if(s[pos]=='('){
        pos++;
        int res = expr();
        pos++;
        return res;
    }
    else return number();
}
int expr(){
    int ret = factor();
    for(;;){
        if(s[pos]=='+'){
            pos++;ret|=factor();
        }
        else if(s[pos]=='*'){
            pos++;ret&=factor();
        }
        else if(s[pos]=='~'){
            pos++;int r=factor();
            if(ret == 1 and r==0)ret = 0;
            else ret = 1;
        }
        else break;
    }
    return ret;
}
main(){
    a['T']=1;
    a['F']=0;
    bool F = false;
    while(1){
        string t;cin>>t;
        if(t=="#")exit(0);
        pos = 0;
        rep(i,t.size()){
            if(i<t.size()-1 and t.substr(i,2)=="->"){
                s[pos++]='~';i++;
            }
            else s[pos++]=t[i];
        }
        bool flag = true;
        rep(i,1<<11){
            rep(j,11)a['a'+j]=(i&(1<<j)?1:0);
            pos = 0;
            int l = expr();
            pos++;
            int r = expr();
            flag &= l==r;
        }
        cout << (flag ? "YES\n":"NO\n");
        F = true;
        for(int i=t.size()-1;i>=0;i--)s[i]=' ';
    }
}


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

using namespace std;

#define SZ(v) ((int)(v).size())
#define ALL(v) (v).begin(),(v).end()
#define one first
#define two second
using ll = long long;
using pi = pair<int, int>;
const int INF = 0x3f3f3f3f;
const ll LINF = 1ll * INF * INF;

string S;
int main() {
	cin >> S;
	int N = SZ(S);
	ll ans = 0;
	for(int s=0; s<(1<<N-1); s++) {
		int ns = s + (1<<N-1);
		ll sum = 0, now = 0;
		for(int i=0; i<N; i++) {
			now *= 10;
			now += S[i] - '0';
			if(ns & (1<<i)) {
				sum += now;
				now = 0;
			}
		}
		ans += sum;
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
#include<iostream>
#define for0(i, n) for(int i = 0; i < (n); i++)
#define for1(i, n) for(int i = 1; i <= (n);i++)
using namespace std;
int get() { int r; cin >> r; return r; }
signed main() {
	double x1, x2, y1, y2, x3, y3, a, b, c, d;
	cin >> x1 >> y1 >> x2 >> y2;
	a = x1 - x2; b = y1 - y2;
	c = b; d = a;
	if (d < 0)d *= -1;
	else c *= -1;
	int q = get();
	for1(i, q) {
		cin >> x3 >> y3;
		double k1 = -100000, k2 = 100000;
		while (k2 - k1 >= 0.0000000000001) {
			double mid = (k1 + k2) / 2;
			if ((a * (y3 + k1 * d - y1) - b * (x3 + k1 * c - x1)) * ((a * (y3 + mid * d - y1) - b * (x3 + mid * c - x1))) > 0) {
				k1 = mid;
			}
			else k2 = mid;
		}
		double k = k1 + k2;
		printf("%.20f %.20f\n", x3 + k * c, y3 + k * d);
	}
}


Measured memory_bytes: 3272
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
#define rep(i,n) for(int i=0;i<n;i++)
#define mod 1000000007 // 10^9+7
#define INF 99999999999 //10^12-1
#define dev 998244353 //tenka1
#define P pair<int,int>
#define F first
#define S second
int n,m,cnt=0;
int a[200000];
int dp[200000];
signed main(){
    cin>>n>>m;
    rep(i,m)cin>>a[i];
    dp[0]=1;
    rep(i,n+1){
        if(i==0)continue;
        if(i==1&&a[0]!=1)dp[1]=dp[0];
        else if(i==a[cnt])cnt++;
        else if(i>1)dp[i]=(dp[i-1]+dp[i-2])%mod;
    }
    cout<<dp[n]<<endl;
    return 0;
}



Measured memory_bytes: 1536
/*
 * Fast UNION(サイズによるUNION) + 経路圧縮
 * (入門データ構造とアルゴリズム(オライリー)8章)
 */
#include <stdio.h>

#define N 100000

/* 互いに素な集合を木で表す配列: */
/* 負の値: この要素は根であり、値はその木の要素数*(-1) */
/* 正の値: 親要素のインデックス */
int S[N+1];

/* 各場所に置いてある数字 */
int P[N+1];

/* 経路圧縮のためのワーク */
int W[N+1];

void makeset(int size) {
    int i;
    /* 自身のみを含む1要素の集合に属するように初期化 */
    for (i = 1; i <= size; i++) {
        S[i] = -1; /* 根であり要素数は1 */
    }
}

/* 経路圧縮つきfind(非再帰版) */
int find(int x) {
    int *w, *ww;

    for (w = W; S[x] > 0; w++) {
        *w = x;
        x = S[x];
    }

    for (ww = W; ww < w; ww++) {
        *ww = x;
    }


    return x;
}

void merge(int x, int y) {
    int root1 = find(x);
    int root2 = find(y);

    if (root1 == root2) {
        return;
    }

    /* 要素数が少ない方を子にする。*/
    /* 要素数を-1倍して格納しているので不等号の向きに注意 */
    if (S[root2] < S[root1]) {
        /** root1をroot2の子にする */
        S[root2] += S[root1];
        S[root1] = root2;
    } else {
        /** root2をroot1の子にする */
        S[root1] += S[root2];
        S[root2] = root1;
    }
}

int main()
{
    int i;
    int n, m;
    int x, y;
    int r;

    scanf("%d %d", &n, &m);

    makeset(n);

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

    for (i = 1; i <= m; i++) {
        scanf("%d %d", &x, &y);
        merge(x, y);
    }

    r = 0;
    for (i = 1; i <= n; i++) {
        if (find(i) == find(P[i])) {
            r++;
        }
    }

    printf("%d\n", r);
    return 0;
}


Measured memory_bytes: 896
#include<bits/stdc++.h>
#define B begin()
#define Y second
#define E end()
#define X first
#define M (1e9)
using namespace std;
map<int,int>::iterator p;
map<int,int> m;

int Read(int x){
  for(p=m.B;p!=m.E;p++)
    if(x<=(*p).X)return (*p).Y;
}

void Del(int x){
  for(p=m.B;p!=m.E;p++)
    if((*p).Y==x)(*p).Y=-1;
}

void Write(int x,int y){
  int s=-1;
  for(p=m.B;p!=m.E;p++){
    if(!y)return;
    if((*p).Y!=-1){
      s=(*p).X;
      continue;
    }
    if((*p).X-s>=y)m[s+y]=x,y=0;
    else y-=(*p).X-s,(*p).Y=x;
    s=(*p).X;
  }
}

int main(){
  int n,a,b;
  string s;
  while(1){
    cin>>n;
    if(!n)break;
    m.clear();
    m[M]=-1;
    while(n--){
      cin>>s;
      if(s=="R")cin>>a,cout<<Read(a)<<endl;
      if(s=="W")cin>>a>>b,Write(a,b);
      if(s=="D")cin>>a,Del(a);
    }
    cout<<endl;
  }
  return 0;
}

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



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

using namespace std;

template <class T>
using vec = std::vector<T>;
typedef long long ll;
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; }

const long long INF = 1LL<<60;

int lcm(int a,int b){
    //最小公倍数
    return a/__gcd(a,b) * b;
}

struct edge{int from, to,cost;};

// int型の2次元配列(3×4要素の)の宣言
// vector<vector<int>> data(3, vector<int>(4));

string T;

int main()
{
    cin>>T;
    int size=T.size();
    rep(i,size){
        if(T[i]=='?') T[i]='D';
    }

    cout<<T<<endl;
    return 0;

}




Measured memory_bytes: 3728
object Scanner {
  private val buf = new Array[Byte](1024); private var ptr = 0; private var len = 0
  @inline private def isPrintableChar(c: Int): Boolean = 33 <= c && c <= 126
  @inline private def hasNextByte(): Boolean =
    if (ptr >= len) { ptr = 0; len = System.in.read(buf); len > 0 } else { true }
  @inline private def hasNext(): Boolean = {
    while (hasNextByte() && !isPrintableChar(buf(ptr))) ptr += 1
    hasNextByte()
  }
  @inline private def readByte(): Byte =
    if (hasNextByte()) { val res = buf(ptr); ptr += 1; res } else { -1 }
  def next(): String = {
    if(!hasNext()) ???
    val sb = new StringBuilder; var b = readByte()
    while (isPrintableChar(b)) { sb.append(b.toChar); b = readByte() }
    sb.toString
  }
  def nextInt(): Int = {
    val n = nextLong()
    if (n < Int.MinValue || Int.MaxValue < n) ???
    n.toInt
  }
  def nextLong(): Long = {
    if(!hasNext()) ???
    var minus = false; var b = readByte()
    if (b == '-') { minus = true; b = readByte() }
    def go (b: Byte, n: Long = 0): Long =
      if ('0' <= b && b <= '9') { go(readByte(), n * 10 + b - '0') }
      else if (minus) { -n } else { n }
    go(b)
  }
  def nextDouble(): Double = next.toDouble
}

object Main extends App {
  val n = Scanner.nextInt()
  val result = (1 to n-1).map(i=>{
    var a = i
    var b = n-i
    var sum = 0
    while (a>=1){
      sum = sum + a%10
      a = (a-a%10)/10
    }
    while (b>=1){
      sum = sum + b%10
      b = (b-b%10)/10
    }
    sum
  }).min
  println(result)
}

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

int main(){
  string H;
  cin >> H;
  for(int i=0; i<H.size(); i++){
    if(H.at(i) == ','){
      H.at(i) = ' ';
    }
    cout << H.at(i);
  }
  
}

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

int main() {
  string n;

  cin >> n;

  if ( n[0] == n[1] && n[1] == n[2] ) {
    cout << "Yes" << endl;
  } else if (n[1] == n[2] && n[2] == n[3]) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }

  return 0;

}


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

#define FOR(i, a, b) for(int i = a; i < b; i ++)
#define FORS(i, a, b, c) for(int i = a; i < b; i += c)
#define FORN(i, a, b) for(int i = a; i <= b; i ++)
#define FORD(i, a, b) for(int i = a-1; i >= b; i --)
#define FORE(i, b) for(auto &i:b)
#define REP(i, b) FOR(i, 0, b)
#define REPN(i, b) FORN(i, 0, b)
#define SQ(i) (i*i)
#define ALL(a) a.begin(), a.end()
#define ALLA(a,n) a, a+n
#define SORT(a) sort(ALL(a))
#define SORTA(a, n) sort(ALLA(a, n))
#define REV(a) reverse(ALL(a))
#define REVA(a, n) reverse(ALLA(a, n))
#define MAX(a, b) a = max(a, b)
#define MIN(a, b) a = min(a, b)
#define IN(a, b) (a.find(b) != a.end())
#define BACK(a) a.back(); a.RB()
#define QBACK(a) a.top(); a.pop()
#define PRINT(a) FORE(i, a) cout << i << " "; cout << endl

#define PB  push_back
#define RB  pop_back
#define RF  pop_front
#define INS insert
#define F   first
#define S   second
#define UM  unordered_map
#define US  unordered_set
#define PQ  priority_queue

#define IO ios_base::sync_with_stdio(false); cin.tie(NULL)

typedef long long ll;
typedef unsigned long long ull;

typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<ll> vll;
typedef pair<int,int> pi;
typedef pair<double,double> pd;
typedef pair<ll,ll> pll;
typedef queue<int> qi;
typedef queue<double> qd;
typedef queue<ll> qll;
typedef US<int> si;
typedef US<double> sd;
typedef US<ll> sll;
typedef vector<vi> mi;
typedef vector<vd> md;
typedef vector<vll> mll;
typedef vector<pi> vpi;
typedef vector<pd> vpd;
typedef vector<pll> vpll;


int main(){
  IO; int N; ll A, B, C;
  cin >> N >> A >> B >> C;
  vector<string> T(N); FORE(i,T)cin>>i; T.PB("");
  vector<char> ans(N);
  int ok = 1;
  REP(i,N){
    if(T[i]=="AB"){
      if(!A&&!B){
        ok = 0;
        break;
      }
      if(A==1&&B==1){
        if(T[i+1]=="AC")A++,B--,ans[i]='A';
        else A--,B++,ans[i]='B';
      }else{
        if(A<B)A++,B--,ans[i]='A';
        else A--,B++,ans[i]='B';
      }
    }else if(T[i]=="BC"){
      if(!B&&!C){
        ok = 0;
        break;
      }
      if(B==1&&C==1){
        if(T[i+1]=="AB")B++,C--,ans[i]='B';
        else B--,C++,ans[i]='C';
      }else{
        if(B<C)B++,C--,ans[i]='B';
        else B--,C++,ans[i]='C';
      }
    }else{
      if(!A&&!C){
        ok = 0;
        break;
      }
      if(A==1&&C==1){
        if(T[i+1]=="AB")A++,C--,ans[i]='A';
        else A--,C++,ans[i]='C';
      }else{
        if(A<C)A++,C--,ans[i]='A';
        else A--,C++,ans[i]='C';
      }
    }
  }
  if(ok){
    cout<<"Yes"<<endl;
    FORE(i,ans)cout<<i<<endl;
  }else cout<<"No"<<endl;
}


Measured memory_bytes: 9536