akhauriyash/Code-Regression huggingface dataset:
#include <iostream>

using namespace std;

int N;
long long int X, x[100005];

long long int gcd(long long int n, long long int m) {
	if (n < m) { return gcd(m, n); }

	if (m == 0) { return n; }
	if (n == 0) { return m; }

	return gcd(m, n%m);
}

int main(void) {

	cin >> N>>X;

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

	long long int ans = gcd(abs(X - x[1]), 0);

	for (int i = 2; i <= N; i++) {
		ans = gcd(ans, abs(X - x[i]));
	}

	cout << ans << endl;

	//system("pause");
	return 0;
}

Measured memory_bytes: 1024
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) throws Exception {
		//BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		//String line = br.readLine();
		Scanner scan = new Scanner(System.in);

		int a = scan.nextInt();
		int b = scan.nextInt();
		int c = scan.nextInt();
		if(a+b+c==17)
			System.out.println("YES");
		else 
			System.out.println("NO");
	}
}


Measured memory_bytes: 21844
#pragma  warning (disable:4996)
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
using namespace std;
int gcd(int d, int x){
	if (x == 0) return d;
	else return gcd(x, d%x);
}
long long lcm(int a, int b){
	int g = gcd(a, b);
	return a / g*b;
}
int main(){
	int n, m;
	while (cin >> n >> m){
		int s = n + m;
		n = max(n, m);
		m = s - n;
		cout << gcd(n, m) << " " << lcm(n, m) << endl;
	}return 0;
}

Measured memory_bytes: 1160
#include<iostream>
#include<math.h>
#include<algorithm>
#include<utility>
#include<queue>
#include<string.h>
#include<string>
#include<set>
#include<map>
#include<unordered_map>
#include<stack>
#include<vector>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
const ll INF=2e18;

ll N;
int main(){
    cin>>N;
    ll ans=0;
    ll now=0;
    ll pre=INF;
    for(ll i=0;i<N;i++){
        ll h;
        cin>>h;
        if(pre>=h){
            now++;
        }else{
            ans=max(ans,now);
            now=1;
        }
        pre=h;
    }
    ans=max(ans,now);
    cout<<ans-1;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
  int n, k;
  cin >> n >> k;
  int l[n], ans = 0;
  for(int i=0; i<n; ++i) cin >> l[i];
  sort(l, l+n, greater<int>());
  for(int i=0; i<k; ++i) ans += l[i];
  cout << ans << endl;
}

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

int main(void){

  int N,ans = 1;
  cin >> N;
  int data[N];
  for(int i=0;i<N;i++) cin >> data[i];
  sort(data,data+N,greater<int>());
  for(int i=0;i<N-1;i++){
      if(data[i] > data[i+1]) ans++;
      
  }
  cout << ans << endl;
}


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

#define LL long long

using namespace std;

int main(){
	ios_base::sync_with_stdio(false);
	LL n;
	cin >> n;
	vector<LL> a(n);
	vector<LL> b(n);
	vector<LL> c(n-1);
	for (LL i = 0; i < n; i++){
		cin >> a[i];
		a[i]--;
	}
	for (LL i = 0; i < n; i++){
		cin >> b[i];
	}
	for (LL i = 0; i < (n-1); i++){
		cin >> c[i];
	}
	LL res = 0;
	for (LL i = 0; i < n; i++)
		res += b[i];
	for (LL i = 1; i < n; i++){
		if (a[i] == a[i-1]+1)
			res += c[a[i-1]];
	}
	cout << res << "\n";
}


Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    String[] str = in.readLine().split(" ");
    System.out.println((str[0].substring(0,1)+str[1].substring(0,1)+str[2].substring(0,1)).toUpperCase());
  }
}

Measured memory_bytes: 37076
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
struct gates
{
    int l;
    int r;
};
gates a[1000000];int n,m;
void readdata()
{
    cin>>n>>m;
    for (int i=1;i<=m;i++)
    {
        cin>>a[i].l>>a[i].r;
    }
}

bool comp(gates a, gates b)
{
    return a.r<b.r;
}

void solve()
{
    for (int i=2;i<=m;i++)
    {
        if (a[i].l<=a[i-1].r)
        {
            a[i].r=a[i-1].r;
            a[i].l=max(a[i].l,a[i-1].l);
        }
        else
        {
            cout<<0;
            return;
        }
    }
    cout<<a[m].r-a[m].l+1;
}

int main()
{
   // freopen("prison.inp","r",stdin);
   // freopen("prison.out","w",stdout);
    readdata();
    sort(a+1,a+1+m,comp);
    solve();
    return 0;
}


Measured memory_bytes: 1152
#include <stdio.h>

int a[100001];

int main()
{
  int N;
  int bt = 1;
  scanf("%d", &N);
  for(int i = 1; i <= N; i++){
    scanf("%d", &a[i]);
  }
  int i = 0;
  while((bt != 2) && (i < N)){
    bt = a[bt];
    i++;
  }
  if(bt == 2) printf("%d\n", i);
  else        printf("%d\n", -1);
  return 0;
}


Measured memory_bytes: 512
#include "bits/stdc++.h"
#define MOD 1000000007
#define INF 11234567890
#define in std::cin
#define out std::cout
#define rep(i,N) for(LL i=0;i<N;++i)
typedef long long int LL;

int N, a[112];
int ans, randm;
bool color[8];

int main()
{
	in >> N;
	rep(i, N) { in >> a[i]; }

	memset(color, false, sizeof(color));
	rep(i, N)
	{
		if (a[i] < 3200)
		{
			if (1 <= a[i] && a[i] <= 399) { color[0] = true; }
			if (400 <= a[i] && a[i] <= 799) { color[1] = true; }
			if (800 <= a[i] && a[i] <= 1199) { color[2] = true; }
			if (1200 <= a[i] && a[i] <= 1599) { color[3] = true; }
			if (1600 <= a[i] && a[i] <= 1999) { color[4] = true; }
			if (2000 <= a[i] && a[i] <= 2399) { color[5] = true; }
			if (2400 <= a[i] && a[i] <= 2799) { color[6] = true; }
			if (2800 <= a[i] && a[i] <= 3199) { color[7] = true; }
		}
		else
		{
			++randm;
		}
	}
	rep(i, 8)
	{
		if (color[i]) { ++ans; }
	}
	if (ans > 0)
	{
		out << ans << " " << ans + randm << std::endl;
	}
	else
	{
		out << 1 << " " << randm << std::endl;
	}
	return 0;
}

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

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

  vector<int64_t> po(n + 1);
  po[0] = 2;
  po[1] = 1;
  for (int i = 2; i <= n; ++i) {
    po[i] = po[i - 1] + po[i - 2];
  }

  cout << po.back() << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, n) for (int i=0, i##_len=(n); i<i##_len; ++i)
#define FOR(i, a, b) for (int i=(a); i<(b); ++i)
using ll = long long;
using namespace std;

int main()
{
    int N;
    cin >> N;
    int H[N];
    REP(i, N) cin >> H[i];

    int ret = 1;
    FOR(i, 1, N)
    {
        bool ok = true;
        REP(j, i)
        {
            if (H[j] > H[i]) ok = false;
        }

        if (ok) ++ret;
    }

    cout << ret << endl;
    return 0;
}


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

#define whole(f, x, ...)                                 \
  ([&](decltype((x)) whole) {                            \
    return (f)(begin(whole), end(whole), ##__VA_ARGS__); \
  })(x)

using namespace std;
using ll = long long;

void solve() {
  long long l, r;
  cin >> l >> r;
  long long ans = ((l % 2019) * (r % 2019)) % 2019;

  for (long long i = l; i <= r; i++) {
    for (long long j = i + 1; j <= r; j++) {
      ans = min(ans, ((i % 2019) * (j % 2019) % 2019));
      if (ans == 0) {
        cout << 0 << endl;
        return;
      }
    }
  }
  cout << ans << endl;
}

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  std::cout << std::fixed << std::setprecision(15);

  solve();
  return 0;
}


Measured memory_bytes: 256
import java.util.*;

public class Main {
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		while(sc.hasNext()){
			int n = sc.nextInt();
			if(n==0)break;
			int[] s = new int[n];
			int[] t = new int[n];
			for(int i=0;i<n;i++){
				s[i] = sc.nextInt();
			}
			
			int count = 0;
			while(true){
				int eq;
				for(int i=0;i<n;i++){
					eq = 0;
					for(int j=0;j<n;j++){
						if(s[i]==s[j])eq++;
					}
					t[i] = eq;
				}
				
				eq=0;
				for(int i=0;i<n;i++){
					if(s[i]==t[i])eq++;
				}
				if(eq==n){
					System.out.println(count);
					for(int i=0;i<n;i++){
						if(i!=0)System.out.print(" ");
						System.out.print(s[i]);
					}
					System.out.println();
					break;
				}
				count++;
				s = Arrays.copyOf(t,n);
				
			}
	
		}
		
	}	
}

Measured memory_bytes: 24500
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define REP(i,a,b) for(int i=(a),_end_=(b);i<=_end_;i++)
#define DREP(i,a,b) for(int i=(a),_end_=(b);i>=_end_;i--)
#define EREP(i,u) for(int i=start[u];i;i=e[i].next)
#define fi first
#define se second
#define mkr(a,b) make_pair(a,b)
#define SZ(A) ((int)A.size())
template<class T>inline void chkmin(T &a,T b){ if(a>b)a=b;}
template<class T>inline void chkmax(T &a,T b){ if(a<b)a=b;}
inline int read()
{
	int s=0,f=1;char ch=getchar();
	while(!isdigit(ch) && ch!='-')ch=getchar();
	if(ch=='-')ch=getchar(),f=-1;
	while(isdigit(ch))s=s*10+ch-'0',ch=getchar();
	return ~f?s:-s;
}

const int maxn=320;

int n,k,mod;

int dp[maxn][maxn],s[maxn][maxn];
int C[maxn][maxn];

inline void init()
{
	n=read();k=read();mod=read();
	C[0][0]=1;
	REP(i,1,n+1)REP(j,0,i)C[i][j]=(C[i-1][j]+(j?C[i-1][j-1]:0))%mod;
}

inline void doing()
{
	DREP(j,k,0)dp[1][j]=1,s[1][j]=(s[1][j+1]+dp[1][j])%mod;
	REP(i,2,n+1)DREP(j,k,0)
	{
		REP(a,1,i-1)
			dp[i][j]=(dp[i][j]+(ll)dp[i-a][j]*s[a][j+1]%mod*C[i-2][a-1])%mod;
		s[i][j]=(s[i][j+1]+dp[i][j])%mod;
	}
	printf("%d\n",dp[n+1][0]);
}

int main()
{
	init();
	doing();
	return 0;
}


Measured memory_bytes: 1408
#include <bits/stdc++.h>
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define RFOR(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define rep(i,n) FOR(i,0,(n))
#define REPS(i,n) FOR(i,1,(n)+1)
#define RREP(i,n) RFOR(i,0,(n))
#define rng(x) (x).begin(),(x).end()
#define rrng(x) (x).rbegin(),(x).rend()
#define debug(x) cout << #x << " = " << (x) << endl;
#define SORT(x) sort(rng(x))
#define RSORT(x) sort(rrng(x))
#define SUM(x) accumulate(rng(x),0)
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define bn(x) ((1<<x)-1)
#define dup(x,y) (((x)+(y)-1)/(y))
#define uni(x) x.erase(unique(rng(x)),x.end())
#define SP << " " <<
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using pii = pair<int, int>;
using tiii = tuple<int, int, int>;
const int mod = 1000000007;
const double EPS = 1e-9;
const int INF = (1<<30)-1;
const ll INFLL = (1LL<<62)-1;
const int dx[4] = {1,0,-1,0};
const int dy[4] = {0,1,0,-1};
//cout << fixed << setprecision(10);

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

ll gcd(ll a, ll b) { return b ? gcd(b,a%b) : a;}
ll lcm(ll a, ll b) { return a/gcd(a,b)*b;}

//const int mod = 1000000007;
struct mint {
  ll x;
  mint(ll x=0):x(x%mod){}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const {
    mint res(*this);
    return res+=a;
  }
  mint operator-(const mint a) const {
    mint res(*this);
    return res-=a;
  }
  mint operator*(const mint a) const {
    mint res(*this);
    return res*=a;
  }
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const {
    return pow(mod-2);
  }
  mint& operator/=(const mint a) {
    return (*this) *= a.inv();
  }
  mint operator/(const mint a) const {
    mint res(*this);
    return res/=a;
  }
};

struct combination {
  vector<mint> fact, ifact;
  combination(int n):fact(n+1),ifact(n+1) {
    fact[0] = 1;
    for (int i = 1; i <= n; ++i) fact[i] = fact[i-1]*i;
    ifact[n] = fact[n].inv();
    for (int i = n; i >= 1; --i) ifact[i-1] = ifact[i]*i;
  }
  mint operator()(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n]*ifact[k]*ifact[n-k];
  }
} comb(100005);
// comb(n,k)ならcomb(n+k+5)とかにしておく

mint f(int n, int k) {
  if (n < 0) return 0;
  mint res = comb(n,k);
  // nPk = nCk * k!
  //res *= comb.fact[k]; // <- nPk求めたいときは必要
  return res;
}
// f(n,k).x で nCk か nPk が計算される

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

  for (int i = 1; i <= k; ++i) {
    mint ans = f(n-k+1,i).x * f(k-1,i-1).x;
    printf("%lld\n", ans);
  }
  return 0;
}

Measured memory_bytes: 1792
#include <stdio.h>
#include <iostream>
#include <utility>
#include <algorithm>
#include <math.h>
#include <vector>
using namespace std;

int heap[500001];
int H;
int parent(int i)
{
    return i / 2;
}

int left(int i)
{
    return 2 * i;
}

int right(int i)
{
    return 2 * i + 1;
}

void maxHeapify(int A[], int i)
{
    int l = left(i);
    int r = right(i);
    int largest;
    if (l <= H && A[i] < A[l])
        largest = l;
    else
        largest = i;
    if (r <= H && A[r] > A[largest])
        largest = r;

    if (largest != i)
    {
        swap(A[largest], A[i]);
        maxHeapify(A, largest);
    }
}

void buildHeap(int A[])
{
    for(int i = H/2; i >= 1; i--)
        maxHeapify(A,i);
}
int main()
{
    cin >> H;
    for(int i = 1; i<= H; i++)
        cin >> heap[i];
    buildHeap(heap);
    for(int i =1; i<= H; i++)
        printf(" %d", heap[i]);
    printf("\n");
    return 0;
}


Measured memory_bytes: 5140
import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) throws IOException {

		new Main().run();
	}

	@SuppressWarnings("unchecked")
	private void run() throws IOException {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		int m = scanner.nextInt();
		List<Integer>[] books = new List[10];
		for (int i = 0; i < 10; i++)
			books[i] = new ArrayList<Integer>();
		while (n-- > 0) {
			int c = scanner.nextInt();
			int g = scanner.nextInt() - 1;
			books[g].add(c);
		}
		int[] dp = new int[m + 1];
		Arrays.fill(dp, -1);
		dp[0] = 0;
		for (int i = 0; i < 10; i++) {
			Collections.sort(books[i], Collections.reverseOrder());
			for (int j = m - 1; j >= 0; j--) {
				int sum = 0;
				for (int k = 0; k < books[i].size() && j + k < m; k++) {
					sum += books[i].get(k);
					dp[j + k + 1] = Math.max(dp[j + k + 1], dp[j] + sum
							+ (k + 1) * k);
				}
			}
		}
		System.out.println(dp[m]);
	}
}

Measured memory_bytes: 27936
package main

import "fmt"

func IsPalindrome(s string) bool {
	r := make([]rune, len(s))
	for i, a := range s {
		r[len(s)-i-1] = a
	}

	return s == string(r)
}

func main() {

	var S string
	fmt.Scan(&S)
	N := len(S)

	S1 := S[:int((N-1)/2)]
	S2 := S[int((N+3)/2)-1:]

	ret := "No"
	if IsPalindrome(S) && IsPalindrome(S1) && IsPalindrome(S2) {
		ret = "Yes"
	}
	fmt.Println(ret)

}


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



int main() {
	int n; cin >> n;
	vector< int > h(n);
	for(int i=0;i<n;++i) cin >> h[i];

	vector< int > dp(n+1, 1e9+1);

	dp[0] = 0;
	for(int i=0;i<n;++i){
		if (i>0) dp[i] = min(dp[i], dp[i-1] + abs(h[i] - h[i-1]));
		if (i>1) dp[i] = min(dp[i], dp[i-2] + abs(h[i] - h[i-2]));
	}
	cout << dp[n-1] << endl;
	
  return 0;
}


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

int main(void){
    string s;
    cin >> s;
    int k;
    cin >> k;
    set<string> ans;
    for(int i=1;i<k+1;i++){
        for(int j=0;j<s.size()-(i-1);j++){
            ans.insert(s.substr(j,i));
        }
    }
    rep(i,k-1){
        ans.erase(*begin(ans));
    }
    
    cout << *begin(ans) <<endl;
    
    
    
    
    
    return 0;
}




































































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

int main()
{
ll n ;
cin >> n ;
string x ;
cin >> x ;
vector<ll> v(200010,0);
ll po=0;
rep(i,n)if(x[i]=='1')po++;
vector<ll> ans(n,-1);
vector<ll> vv(n,0);
vector<ll> vvv2(n,0);
vector<ll> vvv(n,0);
ll a=1;
rep(i,n){
  if(x[n-i-1]=='1')vv[i]=a;
  a*=2;
  if(po-1 == 0){
    ans[n-i-1]=0;
  }
  else a%=(po-1);
}
a=1;
rep(i,n){
  if(x[n-i-1]=='1')vvv[i]=a;
  else vvv2[i]=a;
  a*=2;
  a%=(po+1);
}
ll sum1=0,sum2=0;
rep(i,n){
  sum1+=vv[i];
  sum2+=vvv[i];
}

rep(ii,200009){
  ll i=ii+1;
  ll cnt=0;
  while(i!=0){
    cnt++;
    i=i%(__builtin_popcountll(i));
  }
  v[ii+1]=cnt;
}
rep(i,n){
  ll t;
  if(x[i]=='1'&&ans[i]==0)continue;
  if(x[i]=='1')t=(sum1+po-1-vv[n-1-i])%(po-1);
  else t=(sum2+vvv2[n-1-i])%(po+1);
  ans[i]=v[t]+1;
}
for(auto an:ans)cout << an << endl;
return 0;
}

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

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

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

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

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

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

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

int main() {
    {
        _time time(disable);
        string card; _i64 m, h; 
        while(cin >> card && card != "-") {
            cin >> m;
            _rep(i, m) {
                cin >> h;
                rotate(card.begin(), card.begin() + h, card.end());
            }
            cout << card << endl;
        }
    }
    return 0;
}


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

int main()
{
    int n;
    cin >> n;
    int a[n + 1];
    vector <int> dp(n + 1);
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    for(int i = 1; i <= n; i++)
        dp[a[i]] = dp[a[i] - 1] + 1;
        
    int mx(0);
    for(int i = 1; i <= n; i++)
        mx = max(mx, dp[i]);
    cout << n - mx;
}


Measured memory_bytes: 1792
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <cmath>
#include <tuple>
#include <cstdio>
#include <bitset>
#include <sstream>
#include <iterator>
#include <numeric>
#include <map>
#include <cstring>

using namespace std;

//#define DEBUG_ //!!提出時にコメントアウト!!
#ifdef DEBUG_
	#define dump(x)  cerr << #x << " = " << (x) << endl;
#else
	#define dump(x)  ; //何もしない文
#endif

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define SZ(x) ((int)(x).size()) //unsignedのサイズをint型に変換
#define pb push_back

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

template <typename T>
std::string printVector(const std::vector<T> &data)
{
    std::stringstream ss;
    std::ostream_iterator<T> out_it(ss, ", ");
    ss << "[";
    std::copy(data.begin(), data.end() - 1, out_it);
    ss << data.back() << "]";
    return ss.str();
}

const int MOD = 1e9+7;
const LL LINF = 1001002003004005006ll;
const int INF = 1001001001;
const int MAX_N = 10;

int N,M;
LL ans;
VI adj[MAX_N];

void bfs(int start, bool *visited)
{
    bool allVisited = true;

    for(int i = 0; i < N; i++)
    {
        if(visited[i] == false)  allVisited = false;
    }

    if(allVisited) 
    {
        ans++;
        return;
    }

    for(auto p : adj[start])
    {
        dump(start)
        dump(p)
        dump(visited[p])
        if(visited[p] == false)
        {
            visited[p] = true;
            bfs(p, visited);
            visited[p] = false;
        }
    }

    return;
}


int main(int argc, char const *argv[])
{
    cin.tie(0);
    ios::sync_with_stdio(false);	
    cin >> N >> M;
    REP(i,M)
    {
        int a,b; cin >> a >> b;
        a--; b--;
        adj[a].pb(b);
        adj[b].pb(a);
    }
    ans = 0;
    bool visited[MAX_N];
    REP(i,MAX_N)
    {
        visited[i] = false;
    }
    visited[0] = true;

    bfs(0,visited);
    cout << ans << endl;


}


Measured memory_bytes: 256
"""
unite時に矛盾しないかどうかを判定させる。
同じ木の中では、より右にいるノードを親とする。
親との距離をどこかに記録しておく。
"""
class UnionFind():
    def __init__(self,n):
        self.n=n
        self.parents = [i for i in range(n+1)]
        self.dict = [0]*(N+1)
    def find(self,x):
        if self.parents[x]==x:
            return x
        else:
            self.find(self.parents[x])
            u = self.dict[self.parents[x]]
            self.parents[x]=self.find(self.parents[x])
            #xのdictを更新する。
            self.dict[x] += u
            return self.parents[x]
    def unite(self,x,y,d):
        xRoot = self.find(x)
        yRoot = self.find(y)
        if xRoot == yRoot:
            if self.dict[x]-self.dict[y]!=d:
                print("No")
                exit()
        #より右にいるノードを親にする
        if self.dict[y]+d > self.dict[x]:
            self.parents[xRoot] = yRoot
            self.dict[xRoot] = self.dict[y]+d-self.dict[x]
        else:
            self.parents[yRoot] = xRoot
            self.dict[yRoot] = self.dict[x]-(self.dict[y]+d)

N,M = map(int,input().split())
tree = UnionFind(N)
for _ in range(M):
    l,r,d = map(int,input().split())
    tree.unite(l,r,d)
print("Yes")

Measured memory_bytes: 98464
#include <bits/stdc++.h>
#include <cmath>
#include <numeric>
using namespace std;
#define rep(i,a,b) for(int64_t i=(a);i<(b);++i) // a ≦ i < b 
#define Rrep(i,a,b) for(int64_t i=(a);i>=(b);--i) // reverse repeat. a から b まで減少．
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend() //逆イテレータ
#define RANGE(a,b,c) (a).begin()+(b),(a).begin()+(c) // [b,c) イテレータ
#define INF 1000000000000000
#define MOD 1000000007
using PII = pair<int64_t, int64_t>;
using VI = vector<int64_t>;
using VVI = vector<VI>;
using VS = vector<string>;
using VP = vector<PII>;
using i64 = int64_t;
template<typename T> void invec(vector<T> &A){for(T& a:A) cin >> a;} 

int N; 
void out(string s, int mojisu, int rank){
    if (rank == N) cout << s << "\n";
    else 
        rep(i, 0, mojisu+1)
            out(s + (char)('a' + i), (i < mojisu ? mojisu : mojisu + 1), rank+1);
}

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

cin >> N;

out("a", 1, 1);


return 0;
}
// コンテスト前はtemplate振り返り。
// 書いて考える．場合分け．情報整理．
// 問題文から考える。自分ができることから考えっる。
// 単純に分かる量から．愚直解を実装して研究．
// 境界，出力文字列 チェック．行末にスペース入れない．
// 可読性優先．高速化次点．
// まずは全探索，分割，次にDP(小さい問題から大きな問題)
// 制限を見る．境界に注意．求めたい量の変域．動かせる量．
// 偶奇，逆から，ソート，出現回数，出現位置，DP， 余事象，包除
// データ構造． 問題の特徴量．単調性→二分探索。逆から考える。
// 存在判定：構成方法，入力の特徴
// 構築問題。極端解を試す。
// 例外を十分に含む一般化．想像力の限界
// 小さい系から例示
// 代数的処理．前処理によるクエリ高速化．
// 始めは過剰に例示・場合分けしてもいい．各場合を確実に対処．
// 自明な例から処理，除外．
// 小数のときは，精度の設定する．doubel 変数に数値を入力するときは 123. とする．
// コーナーケース。境界値。数表出力プログラム作る
// 実行エラー：vector添え字超え．0割り．



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

int main(void){
  int n;
  cin >> n;
  string s;
  rep(i, n){
     cin >> s;
     if(s == "Y"){
       cout << "Four" << endl;
       break;
     }
    if(i == (n - 1)){
       cout << "Three" << endl;
    }
  }
  
}


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

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

const ll mod =  1000000007;  //出力は (ans % mod + mod) % mod  (負の剰余を正にする)
const int inf = 1e9;
const long long INF = 1LL << 60;   // INF = 1152921504606846976

int main()
{
    int n,m; cin >> n >> m;
    vector<P> v;
    rep(i,m){
        int a,b; cin >> a >> b;
        v.push_back(make_pair(b,a));
    }
    sort(v.begin(),v.end());
    int ans = 1;
    int tmp = v[0].first-1;
    rep(i,m){
        if(i == 0) continue;
        P p = v[i];
        int l = p.second, r = p.first;
        if(l >  tmp){
            ans++;
            tmp = r-1;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 1400
#pragma GCC optimize("Ofast")
#define _USE_MATH_DEFINES
#include "bits/stdc++.h"

using namespace std;

using u8 = uint8_t;
using u16 = uint16_t;
using u32 = uint32_t;
using u64 = uint64_t;
using i8 = int8_t;
using i16 = int16_t;
using i32 = int32_t;
using i64 = int64_t;

constexpr char newl = '\n';
constexpr double eps = 1e-10;

#define FOR(i,a,b) for (int i = (a); i < (b); i++)
#define F0R(i,b) FOR(i,0,b)
#define RFO(i,a,b) for (int i = ((b)-1); i >=(a); i--)
#define RF0(i,b) RFO(i,0,b)
#define fi first
#define se second
#define debug(x) cout << #x << ": " << x << '\n';
#define rng(a) a.begin(),a.end()
#define rrng(a) a.rbegin(),a.rend()

template<typename T1, typename T2> inline void chmin(T1& a, T2 b) { if (a > b) a = b; }
template<typename T1, typename T2> inline void chmax(T1& a, T2 b) { if (a < b) a = b; }
template<class T> void Print(vector<T> v) {
  F0R(i, v.size()) {
    cout << v[i] << ' ';
  }
  cout << newl;
}

#if 1


// INSERT ABOVE HERE
signed main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);

  int L, R, d;
  cin >> L >> R >> d;
  int r = 0;
  for (int i = L; i <= R; i++) {

    if (i % d == 0) r++;
  }
  cout << r;
}
#endif


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

#define si(v) int(v.size())
#define all(v) v.begin(), v.end()
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define rep2(i, n, m) for (ll i = n; i <= (m); ++i)
#define rep3(i, n, m) for (ll i = n; i >= (m); --i)

template<class T, class U> void chmax(T &a, U b) { if (a < b) a = b; }
template<class T, class U> void chmin(T &a, U b) { if (b < a) a = b; }

using ll = long long;
using ld = long double;
using namespace std;

signed main()
{
  cout << fixed << setprecision(20);
  ios::sync_with_stdio(false);
  cin.tie(0);
  
  int n, m; cin >> n >> m;
  cout << (n - 1) * (m - 1) << endl;
  
  return (0);
}

Measured memory_bytes: 3620
"""
A = 3, B = 4
[青青青][赤赤赤赤][青青青][赤赤赤]...

N = 8
[青青青赤赤赤赤青]

return 青 = 4
"""

def count_balls():
    # 入力
    N, A, B = map(int, input().split())
    # [青青青赤赤赤赤]の個数と余り
    comb_count = N // (A + B)
    remainder = N % (A + B)
    # 集計
    if remainder <= A:
        return A * comb_count + remainder
    else:
        return A * comb_count + A

result = count_balls()
print(result)

Measured memory_bytes: 9180
#include <bits/stdc++.h>
using namespace std;
#define dhoom ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);  
typedef long long ll;
typedef long double ld;
const ll inf = 1e18;
const int nax = 2e6 + 7;
const ll mod = 1e9 + 7;
//ll tree[4 * nax];
//9uS-22RSwk7gQqh
int count(ll x){
	int cnt = 0;
	while(x != 0){
		cnt++;
		x /= 10;
	}
	return cnt;
}
vector< pair< int , int > > st(100) , ch(100);
vector< int > ans(100);
int main()
{
	string a , b , c;
	cin >> a >> b >> c;
	char p , q , r;
	p = a[0] - 'a' + 'A';
	q = b[0] - 'a' + 'A';
	r = c[0] - 'a' + 'A';
	cout << p << q << r << endl;
}



Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<map>
using namespace std;
map<int,int> Suc,Lost;
string S;
int main() {
	int N,M,x,Goal=0,Lose=0;
	scanf("%d%d",&N,&M);
	for(int i=1;i<=M;i++) {
		scanf("%d",&x);
		cin>>S;
		if(S[0]=='W') {
			if(!Suc[x])
				Lose++,Lost[x]++;
		} else {
			if(!Suc[x])
				Suc[x]=1,Goal++;
		}
	}
	map<int,int>::iterator it;
	for(it=Lost.begin();it!=Lost.end();it++)
		if(!Suc[it->first]) Lose-=Lost[it->first];
	printf("%d %d\n",Goal,Lose);
}

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


namespace ConsoleApplication8
{
    class Program
    {
        static void Main(string[] args)
        {
            var ab = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int a = ab[0];
            int b = ab[1];
            int c = a / b;
            int d = a % b;
            double e =1.0* a / b;
            Console.WriteLine("{0} {1} {2:F10}",c,d,e);
        }
    }
}

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

#define mp make_pair
#define pb push_back
#define mt make_tuple
#define eb emplace_back

int mod = 1e9 + 7;
vector<int> fib(112345, -1);

int fibf(int n){
    if(n < 2) return 1;
    if(fib[n] > -1) return fib[n];
    fib[n] = (fibf(n - 1) + fibf(n - 2)) % mod;
    return fib[n];
}

int main(){
    int n, m;
    cin >> n >> m;
    int current, prev = -1;
    vector<int> dist;
    for(int i = 0; i < m; i++){
        cin >> current;
        if(prev == current - 1 && prev){
            cout << 0 << endl;
            return 0;
        }
        else{
            dist.pb((current - 1) - (prev + 1));
            prev = current;
        }
    }
    dist.pb(n - (prev + 1));
    long long res = 1;
    for(int in : dist)
        res = (1LL * res * fibf(in)) % mod;
    cout << res << endl;
    return 0;
}


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

int main(void) {
  int N, Y;
  cin >> N >> Y;
  
  for (int i = 0; i <= Y / 10000 ; i++) {
    for (int j = 0; j <= Y / 5000; j++) {
      int k = Y - 10000*i - 5000*j;
      if (10000*i + 5000*j <= Y and k % 1000 == 0 and k / 1000 + i + j == N) {
        cout << i << ' ' << j << ' ' << (Y - 10000*i - 5000*j) / 1000 << endl;
        return 0;
      }
    }
  }
  
  cout << -1 << ' '<< -1 << ' ' << -1 << endl;
  return 0;
}
  

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double lb;
typedef vector<int,vector<int>> vec;
typedef pair<int,int> P;
typedef long double ld;
#define REP(i,j,n) for (int i=j;i<(n);i++)
#define RREP(i,n,j) for (int i = n; j<i;i--)
#define print(out) cout<< out  << "\n";
#define all(vec) vec.begin(),vec.end()
#define mod 1000000007
const int INF = 1e9;
const ld eps = 1.0e-9; // 許容される誤差


int main(){
  ll L;cin>>L;
  long double ans=(1.0*L)/3;
  cout<<fixed<<setprecision(6)<<ans*ans*ans+eps<<"\n";
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<cstdlib>
using namespace std;
int main(){
    int N,okiba, ans=0;
    vector<int> t(100004);
    vector<int> x(100004);
    vector<int> y(100004);

    t[0]=0;
    y[0]=0;
    x[0]=0;

        cin>>N;

        for(int i=1;i<=N;i++){
            cin>>t[i]>>x[i]>>y[i];
        }
        for(int i=1;i<=N;i++){
                    
            okiba=abs(x[i]-x[i-1])+abs(y[i]-y[i-1]);


            if((t[i]-t[i-1])%2==1&&okiba%2==0){
                ans=1;
                break;
            }

            if(t[i]-t[i-1]<okiba){
                ans=1;
                break;
            }
        }

    if(ans==0){
        cout<<"Yes"<<endl;
    }else{
        cout<<"No"<<endl;
    }



    return 0;

}

Measured memory_bytes: 1408
import sys
input=sys.stdin.readline
a=int(input())
ans=[]
total=0
for i in range(a):
    z=list(map(int,input().split()))
    ans.append(z)
for i in range(a):
    if(i==0):
        t1=ans[0][0]
        t2=ans[0][1]
        t3=ans[0][2]
        
    else:
        x1=t1
        x2=t2
        x3=t3
        t1=max(x2,x3)+ans[i][0]
        t2=max(x1,x3)+ans[i][1]
        t3=max(x1,x2)+ans[i][2]
        
    
print(max(t1,t2,t3))        

    


Measured memory_bytes: 30580
#include <bits/stdc++.h>
using namespace std;
#define _MACRO(_1, _2, _3, NAME, ...) NAME
#define _repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define _rep(i,n) _repl(i,0,n)
#define rep(...) _MACRO(__VA_ARGS__, _repl, _rep)(__VA_ARGS__)
#define pb push_back
#define all(x) begin(x),end(x)
#define uniq(x) sort(all(x)),(x).erase(unique(all(x)),end(x))
#ifdef LOCAL
#define dbg(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
void _dbg(string){cerr<<endl;}
template<class H,class... T> void _dbg(string s,H h,T... t){int l=s.find(',');cerr<<s.substr(0,l)<<" = "<<h<<", ";_dbg(s.substr(l+1),t...);}
template<class T,class U> ostream& operator<<(ostream &o, const pair<T,U> &p){o<<"("<<p.first<<","<<p.second<<")";return o;}
template<class T> ostream& operator<<(ostream &o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}
#else
#define dbg(...) {}
#endif

const long INF = LLONG_MAX / 3;

int main(){
  int n;
  cin>>n;
  vector<double> p(n);
  rep(i,n) cin>>p[i];

  vector<double> dp(n+1, 0);
  dp[0] = 1;
  rep(i,n){
    vector<double> nxt(n+1, 0);
    rep(j,n){
      nxt[j] += (1.0 - p[i])*dp[j];
      nxt[j+1] += (p[i])*dp[j];
    }
    swap(nxt, dp);
  }

  double ans = 0;
  rep(i,n/2 + 1,n+1) ans += dp[i];

  printf("%.9f\n", ans);

  return 0;
}


Measured memory_bytes: 256
h,W=map(int,input().split())
c=[list(map(int,input().split())) for i in range(10)]
a=[list(map(int,input().split())) for i in range(h)]
#print(c,a)
import heapq
def dijkstra_heap(s):
    #始点sから各頂点への最短距離
    d = [float("inf")] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d
n,w = 10,90 #n:頂点数　w:辺の数
edge = [[] for i in range(n)]
#edge[i] : iから出る道の[重み,行先]の配列
for i in range(10):
    for j in range(10):
        x,y,z = i,j,c[j][i]
        #edge[x].append([z,y]) #有向辺
        edge[y].append([z,x]) #有向辺
ans=[]
for i in range(10):
    ans.append(dijkstra_heap(i)[1])
    #print(dijkstra_heap(i))
#print(ans)
A=0
for i in range(h):
    for j in range(W):
        if a[i][j]>=0:
            A+=ans[a[i][j]]
print(A)


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

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,int> plli;
typedef pair<int,pii> pipii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<pii> vpii;

#define rep(i,n) for (int i=0;i<(n);i++)
#define rep2(i,a,b) for (int i=(a);i<(b);i++)
#define rrep(i,n) for (int i=(n);i>0;i--)
#define rrep2(i,a,b) for (int i=(a);i>b;i--)
#define pb push_back
#define fi first
#define se second
#define all(a) (a).begin(),(a).end()

const ll mod = 1e9 + 7;
const ll INF = 1<<30;
const int dx4[4] = {1, 0, -1, 0};
const int dy4[4] = {0, 1, 0, -1};
const int dx8[8] = {1, 1, 1, 0, 0, -1, -1, -1};
const int dy8[8] = {0, 1, -1, 1, -1, 0, 1, -1};
const double pi = 3.141592653589793;

int n;

signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    while (true) {
        cin >> n;
        if (n == 0) break;
        int ch[n] = {};
        rep(i, n) cin >> ch[i];
        int ans = 1e12;
        rep(i, n)rep2(j, 1, 4){
            int nokori = n;
            int l = i - 1;
            int r = i + 1;
            int cnt = 1;
            int color = j;
            while (true) {
                while (r < n) {
                    if (ch[r] == color) cnt++;
                    else break;
                    r++;
                }
                while (l >= 0) {
                    if (ch[l] == color) cnt++;
                    else break;
                    l--;
                }
                if (cnt < 4) break;
                nokori -= cnt;
                if (nokori < 4) break;
                cnt = 0;
                if (r < n) color = ch[r];
                else if (l >= 0) color = ch[l];
                else break;
            }
            ans = min(ans, nokori);
        }
        cout << ans << endl;
    }
}

Measured memory_bytes: 3260
#include <iostream>
using namespace std;
int gcd(int a, int b) {
    if (b == 0) return a >= 0 ? a : -a;
    return gcd(b, a % b);
}
bool solve() {
    int N, K, g;
    cin >> N >> K >> g;
    int M = g;
    for (int i = 1, A; i < N; i++) {
        cin >> A;
        if (A > M) M = A;
        g = gcd(g, A);
    }
    if (K > M) return false;
    if (g == 1 || K % g == 0) return true;
    return false;
}
int main() {
    cout << (solve() ? "POSSIBLE" : "IMPOSSIBLE") << endl;
}

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

ll N, X, D;

// [l, r]
struct Range {
  ll l, r;

  bool operator<(const Range &that) { return l < that.l; }
};

int main() {
  cin >> N >> X >> D;

  if (D == 0) {
    cout << (X == 0 ? 1 : N + 1) << endl;
    return 0;
  }

  ll AD = abs(D);
  unordered_map<int, vector<Range>> klass;
  klass[0].push_back(Range{0, 0});

  for (int i = 1; i <= N; ++i) {
    ll l = i * X + D * i * (i - 1) / 2;
    ll r = l + D * i * (N - i);
    klass[((i * X) % AD + AD) % AD].push_back(Range{min(l, r), max(l, r)});
  }

  ll ans = 0;
  for (auto it = klass.begin(); it != klass.end(); it++) {
    int i = (*it).first;
    sort(all(klass[i]));

    int C = klass[i].size();
    rep(j, C) {
      ll l = klass[i][j].l;
      ll r = klass[i][j].r;
      while (j + 1 < C && klass[i][j + 1].l <= r) {
        ++j;
        r = max(r, klass[i][j].r);
      }
      ans += (r - l) / AD + 1;
    }
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 17864
#include<bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i) 
#define PI acos(-1)

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

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

    int n;
    cin>>n;
    vector<double> as(n);
    rep(i, n) cin>>as[i];

    double ans = 0;
    rep(i, n) ans += 1LL / as[i];
    ans = 1LL / ans;
    printf("%.10f\n", ans);
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define pi 3.141592653589793238
#define int long long
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

// mt19937 gen_rand_int(chrono::steady_clock::now().time_since_epoch().count());
// mt19937_64 gen_rand_ll(chrono::steady_clock::now().time_since_epoch().count());
// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

long long power(long long a, long long b,long long m) {
    long long res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a %m;
        a = a * a %m;
        b >>= 1;
    }
    return res;
}

signed main()
{

ios_base::sync_with_stdio(false);
cin.tie(NULL);  
cout.tie(0);   

#ifndef ONLINE_JUDGE
    if(fopen("INPUT.txt","r"))
    {
    freopen ("INPUT.txt" , "r" , stdin);
    freopen ("OUTPUT.txt" , "w" , stdout);
    }
#endif  

    int n;
    cin>>n;
    int a[n+1];
    for(int i=1;i<=n;i++)
        cin>>a[i];
    int l=0,r=8e17;
    int mn=1e18;
    while (l<=r)
    {
        int mid=l+(r-l)/2;
        bool flag=false;
        for(int j=max(mid-100,0LL);j<=mid+100;j++)
        {
            int temp[n+1];
            for(int i=1;i<=n;i++)
            {
                temp[i]=a[i]+j;
            }
            int tot=0;
            for(int i=1;i<=n;i++)
            {
                tot+=temp[i]/(n+1);
                temp[i]%=n+1;
                if(temp[i]==n)
                    tot++;
            }
            if(tot<=j)
            {
                flag=true;
                mn=min(mn,j);
            }
        }
        if(flag)
        {
            r=mid-1;
        }
        else
        {
            l=mid+1;
        }        
    }
    cout<<mn;
    

} 
    


Measured memory_bytes: 3644
H, W = map(int, input().split())

n_black_col = [0]*W
n_black_row = []

inp = []
for row in range(H):
    tmp = input()
    inp.append(tmp)
    r =[1 if a == "." else 0 for a in tmp]
    n_black_col = [n_black_col[i] + r[i] for i in range(W)]
    n_black_row.append(sum(r))

remove_col = []
remove_row = []
for ind, i in enumerate(n_black_col):
    if i == H:
        remove_col.append(ind)
for ind, i in enumerate(n_black_row):
    if i == W:
        remove_row.append(ind)

for i in range(H):
    if i in remove_row:
        continue
    str = ""
    for j in range(W):
        
        if j in	remove_col:
            continue
        str += inp[i][j]
    print(str)











Measured memory_bytes: 3064
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

#define F first
#define S second
#define pb push_back
#define eb emplace_back
#define PI 3.14159265359
#define sz(c) (int)c.size()
#define len(c) (int)c.length()
#define hcf(a, b) __gcd(a, b)
#define all(c) c.begin(), c.end()
#define vint vector<int>
#define vll vector<ll>
#define vpint vector<pair<int, int>>
#define vpll vector<pair<ll, ll>>
#define fr(it, a, b) \
    for (int it = (a); it < (b); it++)
#define tr(c, it) \
    for (auto it = c.begin(); it != c.end(); it++)
#define cpresent(c, e) (find(all(c), e) != c.end())
#define present(c, e) (c.find(e) != c.end())
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef unsigned long long lu;
const ll mod = 1e9 + 7;
int32_t main()
{
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, c = 0, d = 0, ans = 0;
    cin >> n;
    string s;
    cin >> s;
    for (auto u : s)
    {
        if (u == 'R' && d)
        {
            c++;
        }
        if (u == 'W')
        {
            d = 1;
        }
    }
    for (int j = 0, i = n - 1; i > j; j++)
    {
        if (s[j] == 'W')
        {
            while (s[i] != 'R' && i > 0)
            {
                i--;
            }
            if (i <= j)
            {
                break;
            }
            ans++;
            swap(s[i], s[j]);
        }
    }
    cout << min(c, ans) << "\n";
    return 0;
}

Measured memory_bytes: 3740
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 

using namespace std;
using namespace __gnu_pbds; 
  
#define ll long long
#define X first
#define Y second
#define all(x) x.begin(), x.end()
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> 

#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
	enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
	ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
	*this << "[";
	for (auto it = d.b; it != d.e; ++it)
		*this << ", " + 2 * (it == d.b) << *it;
	ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "

const int mod = (int)1e9 + 7;
const int MX = (int)1e5 + 10;

void add_self(int &x, int y){x += y; if(x >= mod) x -= mod;}
void sub_self(int &x, int y){x -= y; if(x < 0) x += mod;}
void mul(int &x, int y){x = x * 1LL * y % mod;}

int main(){

	cin.tie(0); cout.tie(0);
	ios_base::sync_with_stdio(0);

	ll a, b, n;
	cin >> a >> b >> n;

	ll x = min(b - 1, n);
	ll res = a * x / b - a * (x / b);
	cout << res << endl;

	return 0;
}

Measured memory_bytes: 3652
import math
A,B,H,M = map(int,input().split())
hun_deg = 360*(M/60)
ji_deg = 360*(H/12)+30*(M/60)
deg = abs(hun_deg-ji_deg)
ans = math.sqrt(A**2+B**2-2*A*B*math.cos(math.radians(deg)))
print(ans)

Measured memory_bytes: 9508
/*Kriti Verma */
#include<bits/stdc++.h>
#define     ll          long long
#define     MOD         10e9+7
#define     pb          push_back
#define     vll         vector<long long>
#define     vi          vector<int>
#define     vl          vector<long>
#define     pii         pair<int, int>
#define     pll         pair<ll,ll>
#define     mp          make_pair
#define     all(a)      (a).begin(),(a).end()
#define     rep(i,a,b)  for(int i=a;i<b;i++)
#define     MAX         100002 
#define     ios          ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;

int main() {
    
    ios
    ll n,ac=0,wa=0,tle=0,re=0;
    cin >> n;
    while(n--){
        string s;
        cin >> s;
        if(s=="AC")ac++;
        else if(s=="WA")wa++;
        else if(s=="TLE")tle++;
        else re++;

    }
    cout << "AC "<< "x "<< ac <<"\n";
     cout << "WA "<< "x "<< wa <<"\n";
      cout << "TLE "<< "x "<< tle <<"\n";
       cout << "RE "<< "x "<< re <<"\n";
    return 0;
}



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

#define NMAX 201
#define INF 2000000000

using namespace std;

typedef unsigned long long ull;

ull A, B, C, D;
ull multA, multB;
ull mult;

ull cmmdc(ull a, ull b)
{
    ull c;
    while(b)
    {
        c = a % b;
        a = b;
        b = c;
    }
    return a;
}

int main()
{
    cin >> A >> B >> C >> D;

    multB = B / C + B / D - B / (C * D / cmmdc(C, D));
    multA = (A - 1) / C + (A - 1) / D - (A - 1) / (C * D / (cmmdc(C, D)));
    mult = multB - multA;
    cout << B - A + 1 - mult << '\n';
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
using namespace std;
int main(void){
    int n,m;
    cin >> n;
    vector<string> s(n);
    for(int i = 0;i < n;i++){
          cin >> s[i];
    }
    cin >> m;
    vector<string> t(m);
    for(int i = 0;i < m;i++){
          cin >> t[i];
    }
    int ans = 0;
    for(int i = 0;i < n;i++){
          int temp = 0;
          for(int j = 0;j < n;j++){
                if(s[i] == s[j]) temp++;
          }
          for(int k = 0;k < m;k++){
                if(s[i] == t[k]) temp--;
          }
          ans = max(ans,temp);
    }
    cout << ans << endl;
}


Measured memory_bytes: 3616
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vvi = vector<vi>;
using vvl = vector<vl>;
const int INF = 1 << 28;
const ll MOD = 1'000'000'007;
template <class T> bool chmax(T &a, const T &b) { return (a < b) ? (a = b, 1) : 0; }
template <class T> bool chmin(T &a, const T &b) { return (b < a) ? (a = b, 1) : 0; }

int main() {
    int x;
    cin >> x;
    ll ret = 1;
    while ((1 + ret) * ret / 2 < x)
        ret++;
    cout << ret << endl;
    return 0;
}

Measured memory_bytes: 764
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <unordered_map>
#include <cmath>
using namespace std;

typedef unsigned int uint;
typedef long long llong;
typedef unsigned long long ullong;
// -2.1e-9 <= int <= 2.1e9
// -9.2e-18 <= long long <= 9.2e18
// 0 <= unsigned int <= 4.2e9
// 0 <= unsigned long long <= 18.4e18

bool check(string &S, int first, int last)
{
    while (first <= last) {
        if (S[first] != S[last]) {
            return false;
        }
        ++first;
        --last;
    }
    return true;
}


int main()
{
    string S;
    cin >> S;
    size_t N = S.size();

    if (!check(S, 0, N-1)) {
        cout << "No" << endl;
        return 0;
    }
//    if (S.size() == 3) {
//        cout << "Yes" << endl;
//        return 0;
//    }

    if (!check(S, 0, (N-1)/2-1)) {
        cout << "No" << endl;
        return 0;
    }

    if (!check(S, (N+3)/2-1, N-1)) {
        cout << "No" << endl;
        return 0;
    }

    cout << "Yes" << endl;
    return 0;
}


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

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

  int sum = 0;
  for (int i = 0; i < N; i++) {
    int x,a,b;
    cin >> x;

    a = x * 2;
    b = (K - x) * 2;
    if (a < b) {
      sum += a;
    } else {
      sum += b;
    }
  }
  
  cout << sum << endl;

}

Measured memory_bytes: 256