akhauriyash/Code-Regression huggingface dataset:
/*

      #     #     #####  #####  #           #  #
     # #   # #    #      #   #  #     #     #  #
    #   # #   #   #####  #   #   #   # #   #   #
   #     #     #  #      #   #    # #   # #     
   #           #  #####  #####     #     #     @

*/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

const int INF = (int) 1e9 + 123;
const ll LINF = (ll) 1e18 + 123;
const ld EPS = (ld) 1e-7;
const ll MOD = (ll) 1e9 + 7;

#define sz(x) (int) (x).size()
#define mp(x, y) make_pair(x, y)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define lb(s, t, x) (int) (lower_bound(s, t, x) - s)
#define ub(s, t, x) (int) (upper_bound(s, t, x) - s)
#define rep(i, f, t) for (int i = f; i < t; i++)

ll power(ll x, ll y, ll mod = MOD) {
    if (y == 0) {
        return 1;
    }
    if (y & 1) {
        return power(x, y - 1, mod) * x % mod;
    } else {
        ll tmp = power(x, y / 2, mod);
        return tmp * tmp % mod;
    }
}

template<typename A, typename B> bool mini(A &x, const B &y) {
    if (y < x) {
        x = y;
        return true;
    }
    return false;
}

template<typename A, typename B> bool maxi(A &x, const B &y) {
    if (y > x) {
        x = y;
        return true;
    }
    return false;
}

template<typename T> void read(T first, T last) {
    while (first != last) {
        cin >> *(first++);
    }
}

template<typename T> void print(T first, T last) {
    while (first != last) {
        cout << *(first++) << " ";
    }
    cout << "\n";
}  

void run();

#define TASK ""

int main() {
#ifdef LOCAL
    if (strlen(TASK) > 0) {
        cerr << "Reminder: you are using file i/o, filename: " TASK "!" << endl << endl;
    }
#endif
#ifndef LOCAL
    if (strlen(TASK)) {
        freopen(TASK ".in", "r", stdin);
        freopen(TASK ".out", "w", stdout);
    }
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#endif
    cout << fixed << setprecision(12);
    run();
    return 0;
}

// == SOLUTION == //

void run() {
    ll a, b, c;
    cin >> a >> b >> c;
    for (int i = 0; i < 100000; i++) {
        if (a % 2 == 1 || b % 2 == 1 || c % 2 == 1) {
            cout << i << "\n";
            return;
        }
        ll na = (b + c) / 2;
        ll nb = (a + c) / 2;
        ll nc = (a + b) / 2;
        a = na;
        b = nb;
        c = nc;
    }
    cout << "-1\n";
}


Measured memory_bytes: 256
/*
A0014
Integral
*/
#include <stdio.h>

main()
{
int d;
long S;
int i;

while (EOF != scanf("%d",&d))
{    S = 0;
     for(i=0;i<600;i+=d)
     {    S += d * (i*i);
     }
     printf("%ld\n",S);
}
return(0);
}

Measured memory_bytes: 0
#include<stdio.h>
#include<string.h>
int n,m,i,j,k;
int num,id,cnt;

char A[10];
char B[10];
char tmp;

int flg[1001];

int main(){
  while(1){
    scanf("%d %d",&n,&m);
    if(n==0&&m==0)break;
    
    for(i=1;i<=n;i++)flg[i]=0;
    id=1;
    cnt=n;
    
    for(i=1;i<=m;i++){

      //printf("%d %d\n",i,id);
      if(i%15==0){
        strcpy(A,"FizzBuzz");
      }else if(i%5==0){
        strcpy(A,"Buzz");
      }else if(i%3==0){
        strcpy(A,"Fizz");
      }else{
        j=0;
        num=i;
        while(num>0){
          A[j]=num%10+'0';
          j++;
          num/=10;
        }
        for(k=0;k<j/2;k++){
          tmp=A[k];
          A[k]=A[j-1-k];
          A[j-1-k]=tmp;
        }
        A[j]='\0';
      }
      
      scanf("%s",B);
      
      if(cnt==1)continue;


      //printf("%s %s %d %d\n",A,B,strcmp(A,B),id);
      if(strcmp(A,B)!=0){
        flg[id]=1;
        //printf("%d\n",id);
        cnt--;
      }
      
      while(1){
        id++;
        if(id==n+1)id=1;
        if(flg[id]==0)break;
      }
      
    }
    
    j=0;
    for(i=1;i<=n;i++){

      if(flg[i]==0){
        if(j!=0)printf(" ");
        j=1;
        printf("%d",i);
      }
      
    }
    printf("\n");
    
  }
  return 0;
}

Measured memory_bytes: 624
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=1000010,mo=1e9+7;
int x,n,len,ans, a[maxn],b[maxn],c[maxn],f[maxn],base[maxn];
signed main()
{
    cin>>n;
    for(int i=1;i<=n;i++)cin>>c[i],a[c[i]]=i;
    for(int i=1,x=0;i<=n;i++)x+=a[i],cout<<x<<" ";cout<<endl;
    for(int i=n,x=0;i>=1;i--)x+=a[i],b[i]=x;
    for(int i=1;i<=n;i++)cout<<b[i]<<" ";
}

Measured memory_bytes: 3968
import java.util.*;
import java.io.*;

public class Main {
 
    public static void main(String[] args) {
        FastScanner sc = new FastScanner();
        int s = sc.nextInt();
        int w = sc.nextInt();

        if (s <= w) {
            System.out.println("unsafe");
        } else {
            System.out.println("safe");
        }
    }
}


class FastScanner {
    private final InputStream in = System.in;
    private final byte[] buffer = new byte[1024];
    private int ptr = 0;
    private int buflen = 0;
    private boolean hasNextByte() {
        if (ptr < buflen) {
            return true;
        }else{
            ptr = 0;
            try {
                buflen = in.read(buffer);
            } catch (IOException e) {
                e.printStackTrace();
            }
            if (buflen <= 0) {
                return false;
            }
        }
        return true;
    }
    
    private int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1;}
    
    private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126;}
    
    public boolean hasNext() { 
        while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++; return hasNextByte();
    }
    
    public String next() {
        if (!hasNext()) throw new NoSuchElementException();
        StringBuilder sb = new StringBuilder();
        int b = readByte();
        while(isPrintableChar(b)) {
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }
    
    public long nextLong() {
        if (!hasNext()) throw new NoSuchElementException();
        long n = 0;
        boolean minus = false;
        int b = readByte();
        if (b == '-') {
            minus = true;
            b = readByte();
        }
        if (b < '0' || '9' < b) {
            throw new NumberFormatException();
        }
        while(true){
            if ('0' <= b && b <= '9') {
                n *= 10;
                n += b - '0';
            }else if(b == -1 || !isPrintableChar(b)){
                return minus ? -n : n;
            }else{
                throw new NumberFormatException();
            }
            b = readByte();
        }
    }
    
    public int nextInt() {
        long nl = nextLong();
        if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) throw new NumberFormatException();
        return (int) nl;
    }
    public double nextDouble() { return Double.parseDouble(next());}
}

Measured memory_bytes: 25300
#include <bits/stdc++.h>
#include <array>
#define FOR(i,a,b) for(int i=(a);i<=(b);++i) 
#define RFOR(i,a,b) for(int i=(a);i>=(b);--i) 
#define REP(i,n) for(int i=0;i<(n);++i)
#define RREP(i,n) for(int i=(n);i>0;--i)
#define CI cin>> 
#define CO cout<<
#define EN <<endl 
#define all(x) (x).begin(),(x).end() 
using namespace std;
template <typename T> istream & operator >> (istream & is, vector<T> & vec) { for (T& x : vec) is >> x; 	return is; }
using ll = long long;
using VI = vector<int>;
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }

int main() {
	int n; CI n;
	vector<pair<string, pair<int, int>>> sp(n);
	REP(i, n) {
		CI sp[i].first >> sp[i].second.first;
		sp[i].second.second = i + 1;
	}

	sort(sp.begin(), sp.end());
	sp.push_back(make_pair("a", make_pair(10000,10000)));

	vector<pair<int, int>> ans;
	vector<pair<int, int>> memo;
	bool flag = true;
	REP(i, n) {
		if(flag)
			memo.push_back(make_pair(sp[i].second.first, sp[i].second.second));
		if (sp[i].first == sp[i + 1].first) {
			memo.push_back(make_pair(sp[i+1].second.first,sp[i+1].second.second));
			flag = false;
		}
		else {
			sort(begin(memo),end(memo),greater<pair<int,int>>());
			REP(j, memo.size()) {
				ans.push_back(memo[j]);
			}
			memo.clear();
			flag = true;
		}
	}

	REP(i, n) {
		CO ans[i].second EN;
	}

}

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

int main() {
  int n;
  cin >> n;
  vector<int>vec(n);
  rep(i,n) cin >> vec[i];
  ll sumsum=0;
  ll sum =0;
  rep(i,n){
    sumsum+=vec[i]*vec[i];
    sum+=vec[i];
  }
  
  ll ans=100000000;
  for(int i=1;i<=100;i++){
    ll num=sumsum-2*i*sum+i*i*n;
    if(ans>num)ans=num;
  }
  
  cout << ans << endl;
  
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define sz(a) int((a).size()) 
#define pb push_back 
#define all(c) (c).begin(),(c).end() 
#define tr(c,i) for(auto i = (c).begin(); i != (c).end(); i++) 
#define present(c,x) ((c).find(x) != (c).end()) 
#define cpresent(c,x) (find(all(c),x) != (c).end())
#define F(i,n) for(int i=0;i<n;i++)
#define MOD 1000000007
#define VE(i,v) for(int i = 0;i < (v).size();i++)

using namespace std;
#define trace(...) cerr<<__FUNCTION__<<":"<<__LINE__<<" "; __f(#__VA_ARGS__, __VA_ARGS__)
template<typename Arg1>
void __f(const char *name, Arg1 &&arg1) {
	cerr<<name<<" : "<<arg1<<endl;
}
template<typename Arg1, typename ... Args>
void __f(const char *names, Arg1 &&arg1, Args &&... args) {
	const char *comma=strchr(names+1,',');
	cerr.write(names,comma-names)<<" : "<<arg1<<" | ";
	__f(comma+1,args...);
}
typedef vector<int> vi; 
typedef vector<vi> vvi; 
typedef pair<int,int> ii;
typedef vector<ii> vii;
typedef long long ll;
typedef unsigned int ui;
typedef vector<ll> vl; 
typedef vector<vl> vvl; 
typedef pair<ll,ll> pll;
typedef vector<pll> vpll; 
 




int main()

{
	std::ios::sync_with_stdio(false);
	cin.tie(NULL);
	int T;
	T=1;
	for(int tc=1; tc<=T;tc++)
	{
		ll A, B;
		cin >> A >> B;
		ll ans = A*B/(__gcd(A,B));
		cout<<ans<<"\n";
	}
 
 
 
	return 0;
}
 
 


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

typedef long long ll;
typedef pair<ll, ll> P;
typedef vector<ll> vll;

int main() {
    int n;
    string a, b, c;
    cin >> n >> a >> b >> c;
    ll ans = 0;
    for (int i = 0; i < n; ++i) {
        if ((a[i] != b[i]) && (b[i] != c[i]) && (a[i] != c[i])) {
            ans += 2;
        } else if (a[i] == b[i] && b[i] == c[i]) {
            continue;
        } else {
            ans += 1;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <set>
#include <map>
#include <list>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <vector>
#include <string>
#include <bitset>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <utility>
#include <numeric>
#include <complex>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <cassert>
#include <iostream>
#include <iterator>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef vector<int> vint;
typedef pair<int, int> pint;
typedef vector<long long> vlong;
#define rep(i, n) REP(i, 0, n)
#define all(v) v.begin(), v.end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define INF 2e9
signed main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  vint a(3);
  cin>>a[0]>>a[1]>>a[2];
  sort(all(a));
  cout<<abs(a[1]-a[0])+abs(a[2]-a[1])<<'\n';
  return(0);
}


Measured memory_bytes: 256
#include <stdio.h>
#include <math.h>
int prime(int n)
{
	int i;
	if(n<2) return 0;
	for (i=2; i<=(int)sqrt((double)n); i++)
		if (n%i==0) return 0;
	return 1;
}

int main(void)
{
	int i,sum=0,n,a;
	scanf("%d",&n);
	for (i=1; i<=n; i++)
	{
		scanf("%d",&a);
		if(prime(a))
			sum+=1;
	}
	printf("%d\n",sum);
	return 0;
}



Measured memory_bytes: 2048
while 1:
 H, W = map(int,raw_input().split())
 if H + W == 0:break
 for h in range(H):
  if h % 2 == 0:
   if W % 2 == 0:
    print ('#.'*(W//2))
   else:
    print ('#.'*(W//2)+'#')
  else:
   if W % 2 == 0:
    print ('.#'*(W//2))
   else:
    print ('.#'*(W//2)+'.')
 print ''

Measured memory_bytes: 6408
#include <algorithm>
#include <cassert>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
typedef long long ll;
// const int INF = (1 << 30) - 1;
// const ll LL_INF = (1LL << 62) - 1;
// const ll MOD = 1e9 + 7;

int N;
vector<vector<pair<int, int>>> vvp;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> N;
  vvp.resize(N);
  for (int i = 0; i < N; i++) {
    int a;
    cin >> a;
    vvp[i].resize(a);
    for (int j = 0; j < a; j++) {
      int x, y;
      cin >> x >> y;
      x--;
      vvp[i][j] = make_pair(x, y);
    }
  }

  int ans = 0;
  int m = 1 << N;
  for (int i = 0; i < m; i++) {
    vector<int> trust(N, 0);
    int b = i;
    int j = 0;
    int cnt = 0;
    while (b > 0) {
      if (b % 2 != 0) {
        trust[j] = 1;
        cnt++;
      }
      b /= 2;
      j++;
    }

    bool flag = true;
    for (int j = 0; j < N; j++) {
      if (trust[j] == 1) {
        for (int k = 0; k < vvp[j].size(); k++) {
          int x = vvp[j][k].first;
          int y = vvp[j][k].second;
          if (y != trust[x]) {
            flag = false;
            break;
          }
        }
      }
    }

    if (flag) {
      ans = max(ans, cnt);
    }
  }

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

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  
  int N, M;
  cin >> N >> M;
  
  int X[M] ={};
  for (int i = 0; i < M; i++) {
    cin >> X[i];
  }
  sort(X, X + M);
  
  int L[M - 1] = {};
  for (int i = 0; i < M - 1; i++) {
    L[i] = X[i + 1] - X[i];
  }
  sort(L, L + M - 1);
  
  int count = 0;
  for (int i = 0; i < M - N; i++) {
    count += L[i];
  }
  
  cout << count << endl;
  
}

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

#include <boost/range/adaptors.hpp>
#include <boost/range/irange.hpp>

using namespace std;
using namespace boost;
using namespace boost::adaptors;

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

    cout << s.size() / 2 - count(s.begin(), s.end(), 'p') << endl;
}

Measured memory_bytes: 512
#include<stdio.h>
 
int main(void)
{
  	int N;
  	int count=0;
  	int i=0;
    // 整数の入力
    scanf("%d\n",&N);
  	int P[N];
  	int min=N;
  	for(i=0;i<N;i++){
      	scanf("%d\n",&P[i]);
    }
    // 処理
   	for(i=0;i<N;i++){
    	if(P[i]<=min){
          	count++;
          	min=P[i];
        }
    }
      printf("%d\n",count);
    return 0;
}


Measured memory_bytes: 896
import java.io.BufferedReader;
import java.io.Closeable;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Scanner;
import java.util.StringTokenizer;
import java.util.TreeMap;

public class Main {
	
	public static void main(String[] args) throws IOException {
		final Scanner sc = new Scanner(System.in);
		
		final long N = sc.nextLong();
		
		int min = Integer.MAX_VALUE;
		for(long j = 1; j * j <= N; j++){
			if(N % j != 0){ continue; }
			
			min = Math.min(min, Math.max(Long.toString(j).length(), Long.toString(N / j).length()));
		}
		
		System.out.println(min);
	}
	
	public static class Scanner implements Closeable {
		private BufferedReader br;
		private StringTokenizer tok;
 
		public Scanner(InputStream is) throws IOException {
			br = new BufferedReader(new InputStreamReader(is));
		}
 
		private void getLine() throws IOException {
			while (!hasNext()) {
				tok = new StringTokenizer(br.readLine());
			}
		}
 
		private boolean hasNext() {
			return tok != null && tok.hasMoreTokens();
		}
 
		public String next() throws IOException {
			getLine();
			return tok.nextToken();
		}
 
		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}
 
		public long nextLong() throws IOException {
			return Long.parseLong(next());
		}
 
		public double nextDouble() throws IOException {
			return Double.parseDouble(next());
		}
		
		public int[] nextIntArray(int n) throws IOException {
			final int[] ret = new int[n];
			for(int i = 0; i < n; i++){
				ret[i] = this.nextInt();
			}
			return ret;
		}
		
		public long[] nextLongArray(int n) throws IOException {
			final long[] ret = new long[n];
			for(int i = 0; i < n; i++){
				ret[i] = this.nextLong();
			}
			return ret;
		}
 
		public void close() throws IOException {
			br.close();
		}
	}
}

Measured memory_bytes: 23124
#http://at274.hatenablog.com/entry/2018/02/03/140504
#重み付きUnion-Find木

class WeightedUnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
        # 根への距離を管理
        self.weight = [0] * (n+1)

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            y = self.find(self.par[x])
            # 親への重みを追加しながら根まで走査
            self.weight[x] += self.weight[self.par[x]]
            self.par[x] = y
            return y

    # 併合
    def union(self, x, y, w):
        rx = self.find(x)
        ry = self.find(y)
        # xの木の高さ < yの木の高さ
        if self.rank[rx] < self.rank[ry]:
            self.par[rx] = ry
            self.weight[rx] = w - self.weight[x] + self.weight[y]
        # xの木の高さ ≧ yの木の高さ
        else:
            self.par[ry] = rx
            self.weight[ry] = -w - self.weight[y] + self.weight[x]
            # 木の高さが同じだった場合の処理
            if self.rank[rx] == self.rank[ry]:
                self.rank[rx] += 1

    # 同じ集合に属するか
    def same(self, x, y):
        return self.find(x) == self.find(y)

    # xからyへのコスト
    def diff(self, x, y):
        return self.weight[x] - self.weight[y]

N,M = map(int,input().split())
uf = WeightedUnionFind(N)

for _ in range(M):
    L,R,D = map(int,input().split())
    L -= 1; R -= 1
    if uf.find(L) == uf.find(R):
        if uf.diff(L,R) != D:
            print("No")
            break
    else:
        uf.union(L,R,D)
else:
    print("Yes")


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

int main() {
  int num;
  string str;
  map <string, int> mp;
  cin >> num;
  
  vector<int> vec(num);
  
  for(int i = 0; i < num; i++){
    cin >> str;
    mp[str]++;
  }
  
  cin >> num;
  
  for(int i = 0; i < num; i++){
    cin >> str;
    mp[str]--;
  }
  
  for(auto itr: mp){
   vec.push_back(itr.second);
  }
  
  sort(vec.begin(), vec.end(), greater<int>());
  
  cout << vec.at(0);
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
using namespace std;
using Graph = vector<vector<int>>;

vector<bool> seen;
int count; //連結成分の数をカウント

void dfs(const Graph &G, int v) {
    seen[v] = true; // v を訪問済にする
    count ++;

    // v から行ける各頂点 next_v について
    for (auto next_v : G[v]) { 
        if (seen[next_v]) continue; // next_v が探索済だったらスルー
        dfs(G, next_v); // 再帰的に探索
    }
}

int main(){
    int N , M;
    cin >> N >> M;
    Graph G(N);
    for(int i = 0; i < M; i++){
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    seen.assign(N, false);
    int ans = 0;
    for(int i = 0; i < N; i++){
        count = 0;
        if(seen[i]){
            continue;
        }
        dfs(G, i);
        if(count > ans) ans = count;
    }
    cout << ans << endl;
    return 0;        
}

Measured memory_bytes: 23512
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1000000007;
int main(){
  ll n,m;cin >> n >> m;
  vector<ll> a(n),b(m),ca(n*m),cb(n*m);
  for(int i=0;i<n;i++){
    cin >> a[i];
    ca[a[i]-1]++;
  }
  for(int i=0;i<m;i++){
    cin >> b[i];
    cb[b[i]-1]++;
  }
  sort(a.begin(),a.end(),greater<ll>());
  sort(b.begin(),b.end(),greater<ll>());
  int ta=0;
  int tb=0;
  ll ans=1;
  for(int i=n*m-1;i>=0;i--){
    if(ca[i]>=2||cb[i]>=2){
      cout << 0 << endl;
      return 0;
    }
    if(ca[i]&&cb[i]){
      ta++;
      tb++;
      continue;
    }
    else if(ca[i]&&!cb[i]){
      ta++;
      ans*=tb;
    }
    else if(!ca[i]&&cb[i]){
      tb++;
      ans*=ta;
    }
    else{
      ans*=(ta*tb-n*m+i+1);
    }
    ans%=mod;
  }
  cout << ans << endl;
}

Measured memory_bytes: 15872
#include<bits/stdc++.h>
using namespace std;
string a;
bool c;
int main()
{
	cin>>a;
	if(a[0]!='A')puts("WA");
	else
	{
		for(int s=1;s<a.size();s++)
		{
			if(a[s]=='C'&&c==1||a[s]!='C'&&a[s]>='A'&&a[s]<='Z'||a[s]=='C'&&(s<2||s==a.size()-1))
			{
				puts("WA");
				return 0;
			}
			if(a[s]=='C')c=1;
		}
		if(c)
		puts("AC");
		else
		puts("WA");
	}
}

Measured memory_bytes: 256
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from fractions import Fraction
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations, accumulate
from operator import add, mul, sub, itemgetter, attrgetter


import sys
# sys.setrecursionlimit(10**6)
# readline = sys.stdin.buffer.readline
readline = sys.stdin.readline

INF = 1 << 60


def read_int():
    return int(readline())


def read_int_n():
    return list(map(int, readline().split()))


def read_float():
    return float(readline())


def read_float_n():
    return list(map(float, readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def ep(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.perf_counter()
        ret = f(*args, **kwargs)
        e = time.perf_counter()

        ep(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, X, M):
    ans = 0
    x = X
    x %= M

    x = X
    s = [X]
    u = set()
    while True:
        x *= x
        x %= M
        s.append(x)
        if x in u:
            break
        u.add(x)

    i = s.index(s[-1])
    if i + 1 >= N:
        return sum(s[:N]) % M

    N -= i
    ans += sum(s[:i])

    s = s[i:]
    s.pop()
    ss = sum(s)
    ans += (N // len(s)) * ss
    ans += sum(s[:N%len(s)])
    return ans


def main():
    N, X, M = read_int_n()
    print(slv(N, X, M))

if __name__ == '__main__':
    main()


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

int main(){
  int data[5],k;
  for (int i=0;i<5;i++){
    scanf("%d",data+i);
  }
  
  scanf("%d",&k);

  int max_e = *(max_element(data,data+5));
  int min_e = *(min_element(data,data+5));
  if ((max_e-min_e)<=k){
    printf("Yay!\n");
  }
  else {
    printf(":(\n");
  }
  return 0;
}


Measured memory_bytes: 256
# -*- coding: utf-8 -*-
"""
aaa
"""
#import re #正規表現
import sys
import bisect
#import heapq
#import collections
#import math

def main():
    length = int(input())
    X = [0] * length
    for i, line in enumerate(sys.stdin): 
        X[i] = int(line)
    print(LIS2(X))

def LIS(X):
    res = 0
    N = len(X)
    dp = [1] * N
    for i in range(N):
        for j in range(i):
            if i == 0: dp[0] = 1
            elif X[i] > X[j]: dp[i] = max(dp[i], dp[j]+1)
        res = max(res, dp[i])
    return res

def LIS2(X):
    INF = 10 ** 10
    N = len(X)
    dp = [INF] * (N+1)
    dp[0] = -1
    for a in X:
        idx = bisect.bisect_right(dp, a-1)
        dp[idx] = min(a, dp[idx])
    return max(i for i in range(N+1) if dp[i] < INF)

    
if __name__ == '__main__':
    main()



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

int main() {
int64_t   a,p,x,t,s,ans;
int f,g;
	cin >>  a ;
double b;
 cin >>  b;
	if (a<10000){
	f=a;
	ans = a*b;
	    cout << ans << endl;
	}
	else{
	f=a%100;
	f=f*b;
	a=a/100;
	b=b*100;
	s=b;
	ans = a*s +f;
	     cout << ans << endl;
	}
}

Measured memory_bytes: 3728
n = int(input())

a = []
xy = []
for i in range(n):
    a.append(int(input()))
    xy.append([list(map(int, input().split()))for _ in range(a[-1])])

# print(xy)
ans = 0
for i in range(2 ** n):
    h = [0] * n
    for j in range(n):
        if (i >> j) & 1:
            h[j] = 1

    f = True
    for j in range(n):
        for k in range(len(xy[j])):
            x = xy[j][k][0] - 1
            y = xy[j][k][1]

            if y == 1:
                if (h[j] == 1 and h[x] == 0):
                    f = False
            else:
                if (h[j] == 1 and h[x] == 1):
                    f = False

    if f:
        ans = max(ans, sum(h))

print(ans)


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

int main() {

	int jn; //?????????????????°
	int *p;
	int score;

	while (true) {

		cin >> jn;

		if (jn == 0)
			break;

		score = 0;

		p = new int[jn];

		for (int i = 0; i < jn; i++)
			cin >> p[i];


		for (int i = 0; i < jn; i++) {

			for (int j = 0; j < jn - 1; j++) {

				if (p[j] < p[j + 1]) {
					int tmp;
					tmp = p[j];
					p[j] = p[j + 1];
					p[j + 1] = tmp;
				}

			}

		}

		for (int i = 1; i < jn - 1; i++)
			score += p[i];

		score = score / (jn - 2);

		cout << score << endl;

		delete[] p;

	}


	return 0;

}

Measured memory_bytes: 1196
// ABC113B.cpp : このファイルには 'main' 関数が含まれています。プログラム実行の開始と終了がそこで行われます。
//

#include <iostream>
using namespace std;
int main()
{
	double N, T, A;
	double H[1001];
	//double I[1001];
	cin >> N >> T >> A;
	//double B;
	//B = A;//型変換
	//double S;
	//S = T;//型変換
	for (int i = 1; i <= N; i++)cin >> H[i];

	double temp[1001];
	for (int i = 1; i <= N; i++)
	{
		//[i] = H[i];//型変換
		temp[i] = T - H[i] * 0.006;
		temp[i] = A - temp[i];
		if (temp[i] < 0) temp[i] = -temp[i];
	}
	double  d[2][1001] = {};
	for (int i = 1; i <= N; i++)
	{
		d[0][i] = i;
		d[1][i] = temp[i];
	}

	for (int i = 1; i <= N; i++)
	{

		if (d[1][1] > d[1][i])
		{
			d[1][1] = d[1][i];
			d[0][1] = d[0][i];
		}

	}
	cout << d[0][1] << endl;
	return 0;
}

// プログラムの実行: Ctrl + F5 または [デバッグ] > [デバッグなしで開始] メニュー
// プログラムのデバッグ: F5 または [デバッグ] > [デバッグの開始] メニュー

// 作業を開始するためのヒント: 
//    1. ソリューション エクスプローラー ウィンドウを使用してファイルを追加/管理します 
//   2. チーム エクスプローラー ウィンドウを使用してソース管理に接続します
//   3. 出力ウィンドウを使用して、ビルド出力とその他のメッセージを表示します
//   4. エラー一覧ウィンドウを使用してエラーを表示します
//   5. [プロジェクト] > [新しい項目の追加] と移動して新しいコード ファイルを作成するか、[プロジェクト] > [既存の項目の追加] と移動して既存のコード ファイルをプロジェクトに追加します
//   6. 後ほどこのプロジェクトを再び開く場合、[ファイル] > [開く] > [プロジェクト] と移動して .sln ファイルを選択します


Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
using namespace std;
 
#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
 
typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<VI> VVI;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;

int main() {
    vector<double> a;
    double x;
    while (~scanf("%lf", &x)){
        a.push_back(x);
    }
    double mi = 1e9, ma = 0;
    REP(i,a.size()){
        mi = fmin(mi, a[i]);
        ma = fmax(ma, a[i]);
    }
    cout << ma - mi << endl;

    return 0;
}

Measured memory_bytes: 3328
#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
#include <sstream>
#include <algorithm>
#include <cstdlib>
#include <map>
#include <queue>
#include <utility>
#include <vector>
#include <set>
#include <memory.h>
#include <iomanip>
#include <bitset>
#include <list>
#include <stack>
#include <deque>
#include <numeric>
#include <complex>

using namespace std;

#define mod 1000000007

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

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

int main() {
  int A[5], B[5];
  cin >> A[0] >> A[1] >> A[2] >> A[3] >> A[4];
  for (int i = 0; i < 5; i++) {
    if (A[i] % 10 != 0) B[i] = A[i] % 10;
    else B[i] = 10;
  }
  int mini = 0,minA = 11;
  for (int i = 0; i < 5; i++) {
    if(minA > B[i]) {
      minA = B[i];
      mini = i;
    }
  }
  int ans = 0;
  for (int i = 0; i < 5; i++) {
    if (i == mini) continue;
    if (B[i] != 10)ans += (A[i] / 10 + 1) * 10;
    else ans += A[i] / 10 * 10;
  }
  cout << ans + A[mini] << "\n";
}
    

Measured memory_bytes: 256
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<array>
#include<cmath>
#include<cstdio>
using namespace std;

int main(){

    int n;
    string s;
    int k;

    cin >> n >> s >> k;

    for(int i = 0; i < n; ++i){
        if(s[i] != s[k-1])s[i] = '*';
    }

    cout << s << endl;

    return 0;
}

Measured memory_bytes: 256
#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() {
  ll x;
  ll k;
  ll d;
  cin >> x >> k >> d;

  ll y = - x / d;
  if(k % 2 == 1 && abs(y) % 2 == 0) {
    y++;
  } else if(k % 2 == 0 && abs(y) % 2 == 1) {
    y++;
  }

  ll min_abs = 10e16;
  for(int dy=-2;dy<=2;dy++) {
    ll ydy = y + dy*2;
    if(abs(ydy) > k) {
      ydy = k * (ydy < 0 ? -1 : 1);
      min_abs = min(min_abs, abs(x + (ydy)*d));
    }
    min_abs = min(min_abs, abs(x + (ydy)*d));
  }
  cout << min_abs << endl;
  return 0;
}


Measured memory_bytes: 3600
package main

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

func getScanner(fp *os.File) *bufio.Scanner {
	scanner := bufio.NewScanner(fp)
	scanner.Split(bufio.ScanWords)
	scanner.Buffer(make([]byte, 500001), 500000)
	return scanner
}

func getNextString(scanner *bufio.Scanner) string {
	scanner.Scan()
	return scanner.Text()
}

func getNextInt(scanner *bufio.Scanner) int {
	i, _ := strconv.Atoi(getNextString(scanner))
	return i
}

func getNextInt64(scanner *bufio.Scanner) int64 {
	i, _ := strconv.ParseInt(getNextString(scanner), 10, 64)
	return i
}

var abc [200][200]int

func main() {
	fp := os.Stdin
	if len(os.Args) > 1 {
		fp, _ = os.Open(os.Args[1])
	}

	scanner := getScanner(fp)
	writer := bufio.NewWriter(os.Stdout)

	n := getNextInt(scanner)

	ans := 0
	d := 0

	for i := 0; i < n; i++ {
		p := getNextInt(scanner) - 1
		if p == i {
			d++
			continue
		}
		ans += (d + 1) / 2
		d = 0
	}
	ans += (d + 1) / 2
	fmt.Fprintln(writer, ans)

	writer.Flush()
}


Measured memory_bytes: 1664
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <numeric>
#include <string>
#include <cstdio>
#include <cstring>
#include <queue>
#include <stack>
#include <set>
#include <cmath>
#include <bitset>

typedef long long ll;
typedef unsigned long long ull;
using namespace std;

#define FALSE printf("false\n");
#define TRUE printf("true\n");
#define all(x) (x).begin(),(x).end()
#define rep(i,n) for(int i = 0;i < ((int)(n));++i)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );
#define test(a) cout<<"line:"<<__LINE__<<"["<<(#a)<<": "<<(a)<<"]"<<endl

const int INF = 1e9+7;
const ll INFL = 9*1e18;
const int dx[4] = { 1, 0, -1, 0 };
const int dy[4] = { 0, 1, 0, -1 };

#define SUM(vec) accumulate(all(vec),0LL) // 配列の中身を全部足す
template<typename T>void print(T&& x){cout<<x<<endl;}// 改行付き出力
ll inline digit(ll num){int tmp = 0;while(num){tmp++;num/=10;}return tmp;} // 桁数
template<typename T>inline T digitSum(T num){T sum = 0;while(num){sum+=num%10;num/=10;}return sum;} // 各桁の和
template<typename T>inline T gcd(T a,T b){if(b == 0)return a;return gcd(b,a%b);} // 最大公約数
template<typename T>inline T lcm(T a, T b){T g = gcd(a,b);return a/g*b;} // 最小公倍数
template<typename T>inline T power(T a,T b){T tmp=1;rep(i,b){tmp*=a;}return tmp;} // 累乗
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
int ctoi(char c){return ('0' <= c && c <= '9')?(c - '0'):-1;}

// TODO: write
int main() {
  int n;cin>>n;
  vector<pair<int,int>> ba(n);rep(i,n)cin>>ba[i].se>>ba[i].fi;
  sort(all(ba));

  int time = 0;
  rep(i,n){
    time += ba[i].se;
    if(ba[i].fi < time){
      print("No");
      return 0;
    }
  }
  print("Yes");
  return 0;
}



Measured memory_bytes: 1792
#include <stdio.h>
int main(void) {
  int year;
  int A;
  int B;
  scanf("%d",&year);
  if (year == 1) {
    printf("Hello World\n");
  } else if (year == 2) {
    scanf("%d",&A);
    scanf("%d",&B);
    printf("%d\n",A+B);
  }
  return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm> // sort

#define REP(i, n) for (long long i = 0; i < (n); i++) 
typedef long long ll;
static const ll MOD = 1000000007;
static const ll INF = 1000000000000000000LL;
using namespace std;

int main(){
    int W,a,b;
    cin >> W >> a >> b;

    //(a < b) b - (a + W)  (a > b)a - (b + W)
    int res;

    if(a < b)
    {
      res = b - (a + W);
    }
    else
    {
      res = a - (b + W);
    }

    if(res < 0) res = 0;

    cout << res << endl;
    return 0;    

}

Measured memory_bytes: 256
// 2011/10/22 Tazoe

#include <iostream>
using namespace std;

int no(int C[10002], int i, int c)
{
	int sum = 0;
	int nc = 1;
	int p = i-1;
	int q = i+1;

	while(C[p]==c){
		nc++;
		p--;
	}
	while(C[q]==c){
		nc++;
		q++;
	}

	if(nc<4)
		return 0;
	else
		sum = nc;

	while(true){
		if(C[p]==0||C[q]==0||C[p]!=C[q])
			return sum;

		c = C[p];
		nc = 0;

		while(C[p]==c){
			nc++;
			p--;
		}
		while(C[q]==c){
			nc++;
			q++;
		}

		if(nc<4)
			return sum;
		else
			sum += nc;
	}

	return -1;
}

int main()
{
	while(true){
		int N;
		cin >> N;
		if(N==0)
			break;

		int C[10002];
		C[0] = 0;
		for(int i=1; i<=N; i++)
			cin >> C[i];
		C[N+1] = 0;

		int M = N;
		for(int i=1; i<=N; i++){
			for(int j=1; j<=3; j++){
				int n = no(C, i, j);
				if(N-n<M)
					M = N-n;
			}
		}

		cout << M << endl;
	}

	return 0;
}

Measured memory_bytes: 0
#include <stdio.h>
#include <map>
#pragma warning(disable : 4996)

#define N_MAX 200000

int N, K;
double P[N_MAX];
int main(void) {
	scanf("%d %d", &N, &K);
	for (int i = 0; i < N; ++i) {
		int IN;
		scanf("%d", &IN);
		P[i] = (IN + 1.0) / 2.0;
	}
	double ans = 0;
	double cur = 0;
	for (int i = 0; i < K; ++i) {
		cur += P[i];
	}
	ans = cur;
	for (int i = K; i < N; ++i) {
		cur = cur - P[i - K] + P[i];
		if (cur > ans) {
			ans = cur;
		}
	}
	printf("%lf", ans);
	return 0;
}
 

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

//#define int long long
//struct Fast {Fast(){cin.tie(0);ios::sync_with_stdio(0);}} fast;
//const int MOD = 1e9 + 7;
using intpair = pair<int, int>;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define reps(i, n, m) for (int i = (int)(n); i <= (int)(m); i++)
#define ALL(obj) (obj).begin(), (obj).end()
#define rALL(obj) (obj).rbegin(), (obj).rend()
#define ceiv(a, b) ((int)((a) + (b) - 1)/(int)(b))

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

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

void solve(){
    bool field[H][W], visited[H][W];
    rep(i,H)rep(j,W) visited[i][j] = false;
    rep(i,H)rep(j,W) cin >> field[i][j];
    
    int ans = 0;
    
    rep(y,H)rep(x,W){
        if(visited[y][x] || !field[y][x]) continue;
        stack<intpair> s;
        s.push({x,y});
        ans++;
        while(!s.empty()){
            int x2 = s.top().first, y2 = s.top().second;
            visited[y2][x2] = true;
            s.pop();
            rep(i,8){
                if(!is_safe(x2+dx[i], y2+dy[i])) continue;
                if(!field[y2+dy[i]][x2+dx[i]])   continue;
                if(visited[y2+dy[i]][x2+dx[i]])  continue;
                s.push({x2+dx[i],y2+dy[i]});
            }
        }
    }
    cout << ans << endl;
}

signed main(){
    while(true){
        cin >> W >> H;
        if(H==0 && W==0) break;
        solve();
    }
}


Measured memory_bytes: 3180
#define _USE_MATH_DEFINES
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<string>
#include<iostream>
#include<iostream>
#include<cctype>
#include<cstdio>
#include<vector>
#include<stack>
#include<queue>
#include <algorithm>
#include<math.h>
#include<set>
#include<map>
#include <sstream>
#include<iomanip>
#include <ctype.h>
using namespace std;

//#include<bits/stdc++.h>


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

	for (int i = 0; i < p.size() - 1; i++) {
		string h = p.substr(i, 2);
		if (h == "AC" ) {
			cout << "Yes" << endl; return 0;
		}
	}
	cout << "No" << endl;

	return 0;
}

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

using namespace std;

int main() {
 
    long long N;
    cin >> N;
    vector<long long> A(N), B(N);
    long long sum_A = 0, sum_B = 0;
 
    for (int i = 0; i < N; i++){
        cin >> A[i];
        sum_A += A[i];
    }
 
    for (int i = 0; i < N; i++){
        cin >> B[i];
        sum_B += B[i];
    }
 
    long long cnt = 0;
 
    for (int i = 0; i < N; i++){
        if (A[i] < B[i]){
            cnt += (B[i] - A[i]) / 2;
        }else{
            cnt -= (A[i] - B[i]);
        }
    }
 
    if (cnt >= 0){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
 
    return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
#define int long long
#define ll long long
using ull = unsigned long long;
using namespace std;
const int INF = 1e10;
const int MOD = 1e9 + 7;
#define dump(x)                             \
    if (dbg) {                              \
        cout << #x << " = " << (x) << endl; \
    }
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define FORR(i, a, b) for (int i = (a); i <= (b); ++i)
#define pb push_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define all(v) (v).begin(), (v).end()
#define SZ(x) ((int)(x).size())
#define P pair<int, int>
#define V vector<int>
#define S set<int>
#define itn int
bool dbg = false;
int gcd(int a, int b) {
    while (1) {
        if (a < b)
            swap(a, b);
        if (!b)
            break;
        a %= b;
    }
    return a;
}
int A, B;
int isqrt(int n) {
    FOR(i, 1, INF) {
        if (i * i > n) {
            return i - 1;
        }
    }
}
bool IsPrime(int num) {
    if (num < 2)
        return false;
    else if (num == 2)
        return true;
    else if (num % 2 == 0)
        return false;  // 偶数はあらかじめ除く

    double sqrtNum = sqrt(num);
    for (int i = 3; i <= sqrtNum; i += 2) {
        if (num % i == 0) {
            // 素数ではない
            return false;
        }
    }

    // 素数である
    return true;
}

void solve() {
    int N = gcd(A, B);
    int ans = 1;
    int n = isqrt(N);
    FORR(i, 2, n) {
        int flag = 0;
        while (N % i == 0) {
            N /= i;
            flag = 1;
        }
        ans += flag;
    }
    if (IsPrime(N)) {
        ans++;
    }
    cout << ans << endl;
    return;
}

signed main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cin >> A >> B;
    solve();
    return 0;
}


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

using namespace std;
using ll = long long int;
using P = pair<int, int>;

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

int main(void){

    int n;
    cin >> n;

    cout << n*(n+1)/2 << endl;

    return 0;
}

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

#define MOD 1000000007

long long kai[200010];

void init(){
  kai[0] = 1;
  kai[1] = 1;
  for(int i = 2;i < 200010;i++){
    kai[i] = kai[i-1] * i % MOD;
  }
}

long long pow_mod(long long a, int b){
  long long ans = 1;
  while(b > 0){
    if(b & 1) ans = (ans * a) % MOD;
    a = (a * a) % MOD;
    b >>= 1;
  }
  return ans;
}

long long gyaku(long long a){
  return pow_mod(a,MOD-2) % MOD;
}

long long comb(int n, int r){
  return kai[n] * gyaku(kai[n-r]) % MOD * gyaku(kai[r]) % MOD;
}



int main(){
  int h, w, a, b;
  cin >> h >> w >> a >> b;

  init();

  long long ans = 0;

  for(int i = 0;i < h-a;i++){
    ans = (ans + comb(b+i-1, b-1) * comb(w-b-1+h-i-1, w-b-1)) % MOD;
  }

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



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

struct rectangle{
    int h,w,d;
    rectangle(int h,int w):h(h),w(w),d(h*h+w*w){}
    bool operator<(const rectangle &rhs) const{
        if (d!=rhs.d) return d<rhs.d;
        else return h<rhs.h;
    }
};

const int MAX=151;

int h,w;
vector<rectangle> rs;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    for (int i=1;i<MAX;++i)
        for (int j=i+1;j<MAX;++j)
            rs.emplace_back(i,j);
    sort(rs.begin(),rs.end());
    while(cin >> h >> w,h){
        rectangle ans=*upper_bound(rs.begin(),rs.end(),rectangle{h,w});
        cout << ans.h << ' ' << ans.w << '\n';
    }
}


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

#define repd(i, a, b) for (ll i = (a); i < (b); i++)
#define repb(i, n) for (ll i = (n)-1; i >= 0; i--)
#define rep(i, n) repd(i, 0, n)

using namespace std;

using ll = long long;
using ul = unsigned long long;
ll mod = 1000000007;

int main() {
source:
    ll n, a, b;
    cin >> n >> a >> b;
    ll num_max = b * n - (b - a);
    ll num_min = a * n + (b - a);
    cout << max(num_max - num_min + 1, 0LL) << endl;
    return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
#define DUMP(x)  cout << #x << " = " << (x) << endl;
#define FOR(i, m, n) for(ll i = m; i < n; i++)
#define IFOR(i, m, n) for(ll i = n - 1; i >= m; i-- )
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)
#define FOREACH(x,a) for(auto& (x) : (a) )
#define ALL(v) (v).begin(), (v).end()
#define SZ(x) ll(x.size())

void yes(){
  cout << "YES" << endl;
  exit(0);
}

void no(){
  cout << "NO" << endl;
  exit(0);
}

int main(){
  string s; cin >> s;
  string t = "keyence";
  ll n = SZ(s);
  ll m = SZ(t);

  //sの左からi文字目まで一致しているとする
  IREP(i,m){
    bool ok = true;
    IREP(j,i){
      if(s[j] != t[j]){
        ok = false;
        break; 
      }
    }
    REP(j,m-i){
      if(s[n-1-j] != t[m-1-j]){
        ok = false;
        break;
      }
    }
    if(ok) yes();
  }
  no();
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define set_zero(a) memset(a,0,sizeof(a));
#define ll long long
#define PI 2 * acos(0.0)
#define MAX 1000000000
#define INF 1000000 
#define M 1000000007
using namespace std;
vector<string> v1;
void permute(string str) 
{ 
    do { 
      v1.push_back(str);
    } while (next_permutation(str.begin(), str.end())); 
}
long double distance(ll a, ll b ,ll c ,ll d){
   long long int a1 = pow(abs(b-a),2);
   long long int a2 = pow(abs(d-c),2);
   long double dis = (long double) a1 + (long double) a2;
   long double y = sqrt(dis);
   return y;
}
int main(){
   ll n;
   cin>>n;
   vector< pair < ll,ll > > v;
   v.push_back({0,0});
   for(ll i = 1;i<=n;i++){
      ll x,y;
      cin>>x>>y;
      v.push_back({x,y});
   }
   string s;
   for(ll i = 1;i<=n;i++){
      string d = to_string(i);
      s.push_back(d[0]);
   }
   permute(s);
   long double ans1 = 0;
   long double cnt = 0;
      for(ll i = 0;i<v1.size();i++){
          string h = v1[i];
          ll k = h[0] - '0';
          long double sum = 0;
          for(ll j = 1;j<h.length();j++){
             ll u  = h[j] - '0';
             ll a = v[k].first;
             ll b = v[u].first;
             ll c = v[k].second;
             ll d = v[u].second;
             sum += distance(a,b,c,d);
             k = h[j] - '0';
          }
          ans1 += sum;
          cnt++;
      }
   long double main_ans = ans1/cnt ;
   cout<<fixed<<setprecision(10)<<main_ans<<endl;
   return 0;
}

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

using namespace std;

#define int long long
typedef vector<int> vint;
typedef pair<int, int> pint;
const double PI = 3.14159265358979323846;
const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
// cout << fixed << setprecision(20);

int N, W;
int v[110], w[110];
int dp[110][220000];

signed main() {
    cin >> N >> W;
    for (int i = 0; i < N; i++) {
        cin >> w[i] >> v[i];
        for (int j = 0; j <= W; j++) {
            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j]);
            dp[i + 1][j + w[i]] = max(dp[i + 1][j + w[i]], dp[i][j] + v[i]);
        }
    }
    int ans = 0;
    for (int i = 0; i <= W; i++)ans = max(ans, dp[N][i]);
    cout << ans << endl;
}


Measured memory_bytes: 172672
#include<set>
#include<iostream>
using namespace std;
int main()
{
	
	int n, i;
	cin >> n;
	int a[n];
	set<int> cpp;
	for (i = 0; i < n; i++)
	{
		cin >> a[i];
		cpp.insert(a[i]);
	}
	set<int>::iterator	iter = cpp.begin();
	for (iter; iter != cpp.end(); iter++)
	{
		if (iter!=cpp.begin())
			cout<< " ";
		cout << *iter;
	}
        cout<<endl;
	return 0;
}


Measured memory_bytes: 8156
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int res = Integer.MAX_VALUE;
        int[] X = new int[N];
        for(int i = 0; i < N; i++) X[i] = sc.nextInt();

        for(int i = 1; i <= 100; i++) {
            int tmp = 0;
            for(int j = 0; j < N; j++) {
                tmp += (int)Math.pow(Math.abs(X[j]-i), 2);
            }
            res = Math.min(res, tmp);
        }
        System.out.println(res);
    }
}


Measured memory_bytes: 35808
#include <bits/stdc++.h>
using namespace std;
long int pow107 = (int)pow(10, 9) + 7;
long int limit = LONG_MAX;

bool comp(pair<int, string> a, pair<int, string> b){
    if(a.first != b.first) return a.first > b.first;
    else return a.second < b.second;
}

long int jou(long int x, long int y){
    long int f = 1;
    for(int i = 0; i < y; ++i){
        f = f * x % pow107;
    }
    return f;
}

bool pn(long int x){
    if(x != 2 && x % 2 == 0)
        return false;
    for(int i = 3; i < x; ++i){
        if(x != i && x % i == 0)
            return false;
    }
    return true;
}

long int factorial(long int n){
    long int f = 1;
    for(long int i = 1; i <= n; ++i){
        f = f * i % pow107;
    }
    return f;
}

//最大limit
//10^9+7    pow107
//素数pn
//n乗jou
//コンビネーションfactorial
//

int main(){
    string s[3];
    cin >> s[0] >> s[1] >> s[2];

    for(int i = 0; i < 3; ++i){
        cout << char('A' + (s[i][0] - 'a'));
    }
    cout << endl;

    return 0;
}


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

using namespace std;

const int INF = 1e9;

int n, m, a[100005], sum[100005][25], dp[(1 << 20) + 5], cnt[25];

int main() {
	scanf("%d%d", &n, &m);
	
	for (int i = 1; i <= n; i++)
	scanf("%d", &a[i]);
	
	for (int i = 1; i <= n; i++) {
		a[i]--;
		cnt[a[i]]++;
		sum[i][a[i]] = 1;
		
		for(int j = 0; j < m; j++)
		sum[i][j] += sum[i - 1][j];	
	}	
	
	for(int i = 1; i < (1 << m); i++)
	dp[i] = INF;
	
	for (int i = 1; i < (1 << m); i++) {
		int len = 0;
		for (int j = 0; j < m; j++) {
			if (i & (1 << j))
			len += cnt[j];
		}
		for (int j = 0; j < m; j++) {
			if (i & (1 << j)) {
				int mask = i ^ (1 << j);
				int cool = len - cnt[j];
				//cool + 1 ~ len
				dp[i] = min(dp[i], dp[mask] + len - cool - (sum[len][j] - sum[cool][j]));
			}
		}
	}
	
	printf("%d\n", dp[(1 << m) - 1]);
}


Measured memory_bytes: 17372
import java.io.*;
import java.util.*;

class Main {

    // Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
    public static void main(String[] args) throws Exception {
        final Scanner sc = new Scanner(System.in);
        String S;
        S = sc.next();
        solve(S);
    }

    static void solve(String S){
        System.out.println(calc(S));
    }

    static int calc(String S) {
        switch (S) {
            case "SUN": return 7;
            case "MON": return 6;
            case "TUE": return 5;
            case "WED": return 4;
            case "THU": return 3;
            case "FRI": return 2;
            case "SAT": return 1;
        }
        return 0;
    }
}


Measured memory_bytes: 23764