akhauriyash/Code-Regression huggingface dataset:
#include <functional>
#include <iostream>
#define min(a, b) (a > b ? b : a)

int tb[30];
int main() {
    int n;
    std::function<void(int, int, int)> f;
    f = [&](int dpt, int pre, int left) {
        if (!left) {
            for (int i = 0; i < dpt; i++) std::cout << (i ? " " : "") << tb[i];
            std::cout << std::endl;
        } else {
            for (int num = min(pre, left); num > 0; num--) {
                tb[dpt] = num;
                f(dpt + 1, num, left - num);
            }
        }
        tb[dpt] = 0;
    };
    while (std::cin >> n && n) { f(0, n, n); }
}

Measured memory_bytes: 2988
#include <algorithm>
#include <array>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

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

constexpr double EPS = 1e-7;
constexpr int INF = 1e9;
#define PI (acos(-1))

constexpr int MOD = 1e9 + 7;

int main(int argc, char const *argv[]) {
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(15);

	int N;
	cin >> N;
	vector<int> A(N);
	vector<int> B(N);
	vector<int> C(N);

	for (int i = 0; i < N; i++) {
		cin >> A[i];
	}
	for (int i = 0; i < N; i++) {
		cin >> B[i];
	}
	for (int i = 0; i < N; i++) {
		cin >> C[i];
	}
	sort(A.begin(), A.end());
	sort(B.begin(), B.end());
	sort(C.begin(), C.end());

	vector<vector<int>::iterator> ab_bounds(N);
	vector<vector<int>::iterator> bc_bounds(N);
	for (int i = 0; i < N; i++) {
		auto a_bound = upper_bound(A.begin(), A.end(), B[i] - 1);
		ab_bounds[i] = a_bound;
	}

	for (int i = 0; i < N; i++) {
		auto c_bound = lower_bound(C.begin(), C.end(), B[i] + 1);
		bc_bounds[i] = c_bound;
	}

	ll ans = 0;
	for (int i = 0; i < N; i++) {
		auto a_bound = upper_bound(A.begin(), A.end(), B[i] - 1);
		auto c_bound = lower_bound(C.begin(), C.end(), B[i] + 1);

		ans += (a_bound - A.begin()) * (C.end() - c_bound);
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 3072
#[allow(dead_code)]
fn main() {
    let n = i::i();
    for x in 1..3501 {
        for y in 1..3501 {
            if 4 * x * y - n * y - n * x <= 0 {
                continue;
            }
            if n * x * y % (4 * x * y - n * y - n * x) == 0 {
                println!("{} {} {}", x, y, n * x * y / (4 * x * y - n * y - n * x));
                return;
            }
        }
    }
}

#[allow(unused_imports)]
use std::cmp::*;
#[allow(unused_imports)]
use std::collections::{HashMap, HashSet, VecDeque};
#[allow(unused_imports)]
use std::io::*;
#[allow(unused_imports)]
use std::num::*;
#[allow(unused_imports)]
use std::str::*;

#[allow(dead_code)]
mod i {
    use super::*;

    pub fn read<T: FromStr>() -> T {
        stdin()
            .bytes()
            .map(|c| c.unwrap() as char)
            .skip_while(|c| c.is_whitespace())
            .take_while(|c| !c.is_whitespace())
            .collect::<String>()
            .parse::<T>()
            .ok()
            .unwrap()
    }

    pub fn str() -> String {
        read()
    }

    pub fn s() -> Vec<char> {
        str().chars().collect()
    }

    pub fn i() -> i64 {
        read()
    }

    pub fn u() -> usize {
        read()
    }

    pub fn u2() -> (usize, usize) {
        (read(), read())
    }

    pub fn u3() -> (usize, usize, usize) {
        (read(), read(), read())
    }

    pub fn f() -> f64 {
        read()
    }

    pub fn c() -> char {
        read::<String>().pop().unwrap()
    }

    pub fn iv(n: usize) -> Vec<i64> {
        (0..n).map(|_| i()).collect()
    }

    pub fn iv2(n: usize) -> Vec<(i64, i64)> {
        (0..n).map(|_| iv(2)).map(|a| (a[0], a[1])).collect()
    }

    pub fn uv(n: usize) -> Vec<usize> {
        (0..n).map(|_| u()).collect()
    }

    pub fn uv2(n: usize) -> Vec<(usize, usize)> {
        (0..n).map(|_| uv(2)).map(|a| (a[0], a[1])).collect()
    }

    pub fn uv3(n: usize) -> Vec<(usize, usize, usize)> {
        (0..n).map(|_| uv(3)).map(|a| (a[0], a[1], a[2])).collect()
    }

    pub fn fv(n: usize) -> Vec<f64> {
        (0..n).map(|_| f()).collect()
    }

    pub fn cmap(h: usize) -> Vec<Vec<char>> {
        (0..h).map(|_| s()).collect()
    }
}


Measured memory_bytes: 4352
def Judge(data,n,d,m):
    now=m
    for i in range(d):
        if now==1:
            if data[i][now]:
                now+=1
        elif now==n:
            if data[i][n-1]:
                now-=1
        elif data[i][now-1]:
            now-=1
        elif data[i][now]:
            now+=1
    return now

while True:
    n=input()
    if n==0:break
    m,star,d=input(),input(),input()
    data=[[0]+map(int,raw_input())+[0] for i in range(d)]
    flag=False
    if Judge(data,n,d,m)==star:
        print 0
    else:
        for i in range(d):
            for j in range(1,n):
                if data[i][j]==0 and data[i][j+1]!=1 and data[i][j-1]!=1:
                    data[i][j]=1
                    if Judge(data,n,d,m)==star:
                        print i+1,j
                        flag=True
                        break
                    else:
                        data[i][j]=0
            if flag:
                break
        else:
            print 1

Measured memory_bytes: 4292
n, a, b = map(int, input().split())
s = input()
ans = []
x = 0
y = 0
for i in range(n):
  if s[i] == 'c':
    ans.append('No')
  elif s[i] == 'a':
    if x < a + b:
      x += 1
      ans.append('Yes')
    else:
      ans.append('No')
  elif s[i] == 'b':
    if x < a + b and y + 1 <= b:
      x += 1
      y += 1
      ans.append('Yes')
    else:
      ans.append('No')

for e in ans:
  print(e)   

Measured memory_bytes: 10016
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int INF = 1e9;
const ll LINF = 1e18;
const int MOD = 1e9 + 7;

int main() {
  int a, p;
  cin >> a >> p;
  cout << (3 * a + p) / 2 << endl;
}

Measured memory_bytes: 256
import sys
line = sys.stdin.readline
M = int(line())
b = list(map(int, line().split()))
c = [0] * M
for i in range(M, 0, -1):
    ball = 0
    for j in range(2, M+1):
        if i * j > M:
            break
        ball += c[i * j - 1]
    c[i - 1] = (b[i - 1] + ball) % 2
ans = []
for i, v in enumerate(c):
    if v == 1:
        ans.append(i + 1)
print(len(ans))
print(*ans)


Measured memory_bytes: 14104
#include <iostream>
#include <algorithm>
using namespace std;
 
int main()
{
    int N;
    cin >> N;
 
    int p[5000];
    for(int i=0; i<N; i++){
        cin >> p[i];
    }
 
    int min_sum = 20000;
 
    for(int I=0; I<=p[0]; I++){
        int q[5000];
        for(int i=0; i<N; i++){
            q[i] = p[i];
        }
 
        int sum = I;
        q[0] -= I;
 
        for(int i=0; i<=N-2; i++){
            if(q[i]<=0)
                continue;
 
            sum += q[i]*2;
            q[i+1] -= q[i];
        }
 
        if(q[N-1]>0){
            sum += q[N-1];
        }
 
        min_sum = min(min_sum, sum);
    }
 
    cout << min_sum << endl;
 
    return 0;
}

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

int main()
{
  char s[10010],t[10010];
  scanf("%s",s);
  scanf("%s",t);
  int mi=100000000,mx=-1;
  for(int i=0; s[i]; i++)
    mi=min(mi,(int)s[i]);
  for(int i=0; t[i]; i++)
    mx=max(mx,(int)t[i]);
  if(mi<mx)
  {
    cout<<"Yes";
  }
  else if(mi==mx)
  {
    int i=0;
    for(; s[i]&&t[i]&&s[i]==t[i]; i++);
    if(s[i]||t[i]=='\0')
    {
      cout<<"No";
    }
    else
    {
      cout<<"Yes";
    }
  }
  else
  {
    cout<<"No";
  }

  return 0;
}


Measured memory_bytes: 256
#include <iostream>


long *getinput(long *n, long *k)
{
  std::cin >> *n >> *k;
  long *w = new long[(*n)];
  for (int i=0; i<*n; i++)
    std::cin >> w[i];

  return w;
}

int check_track_count(long w[], long n, long target, long k)
{
  long tmpw=w[0], count=1;
  for(int i=1; i<n; i++)
  {
    if (w[i] > target) return 1;
    if (w[i] + tmpw <= target)
    {
      tmpw += w[i];
    }else{
      tmpw = w[i];
      count ++;
    }
  }

  if (tmpw > target) return 1;//最後の1台が積載量超えた
  if (count > k) return 1;//トラックの台数が多い -> 積載量が足りない
  if (count < k) return -1;//トラックの台数が少ない -> 積載量多すぎ


  return 0;
}

long sum (long w[], long n)
{
  long s =0;
  for(int i=0; i<n; i++) s += w[i];
  return s;
}

int main() 
{
  long n, k, *w;
  long high;
  long low;
  w = getinput(&n, &k);

  high = 2*sum(w,n)/k;
  low = sum(w,n)/(k+1);
  do{
    long mid = (high + low)/2;
    int tcheck = check_track_count(w, n,mid,k);
    
     if (tcheck<=0  ) //トラックの積載量が多すぎ
      high = mid;
    else if (low == mid)  low ++;//トラックの積載量が足りない かつ low ==mid 
    else   low = mid ;
      
  }
  while (high != low);
  std::cout << high << std::endl;

  delete w;
}


Measured memory_bytes: 3560
import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        scanner.useDelimiter(",");
        String a = scanner.next();
        String b = scanner.next();
        String c = scanner.next();
        System.out.println(a + " " + b + " " + c);
    }
}

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

int main() {
  char c;
  cin >> c;
  if(c=='a' || c=='i' || c=='u' || c=='e' || c=='o'){
    cout << "vowel" << endl;
  }
  else{
    cout << "consonant" << endl;
  }
}

Measured memory_bytes: 256
#include <algorithm>
#include <cstdio>
#include <functional>
#include <iostream>
#include <cfloat>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <time.h>
#include <vector>
#include <complex>
using namespace std;
int main()
{
	int n,A[100],B[100],C[100],D[100];
	int big[100],small[100];
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>A[i]>>B[i];
		big[i]=0;
	} 
	for(int i=0;i<n;i++){
		cin>>C[i]>>D[i];
		small[i]=0;
		for(int j=0;j<n;j++){
			if(A[j]<C[i] and B[j]<D[i]){
				small[i]++;
				big[j]++;
			}
		}
	} 
	
	int ans=0;
	while(1){
		int k=-1;
		int count=101;
		for(int i=0;i<n;i++){
			if(small[i]<=0) continue;
			if(small[i]<count){
				k=i;
				count=small[i];
			}
		}
		if(count>100) break;
		small[k]=0;
		count=0;
		int x=-1;
		int count1=101;
		for(int j=0;j<n;j++){
			if(big[j]<=0) continue;
			if(A[j]<C[k] and B[j]<D[k]){
				big[j]--;
				if(big[j]<count1) {
					count1=big[j];
					x=j;
				}
				count++;
			}
		}
		if(count>0) ans++;
		if(x>=0) {
			big[x]=0;
			for(int i=0;i<n;i++){
				if(A[x]<C[i] and B[x]<D[i]) small[i]--;
			}
		}
	}
	cout<<ans;
	system ("pause");
    return 0;
}

Measured memory_bytes: 504
#include <complex>
#include <cmath>
#include <iostream>
#include <vector>
using namespace std;

#define X real()
#define Y imag()

// ----- debug macro -----
#define DMPPT(p,stream) stream << (p).X << "," << (p).Y
// ----- ----- ----- -----

// ????????????????§???????????????????????????\??????????????????????????¨???????????????
typedef complex<double> PT;
typedef complex<double> VC;

// ??´??? or ???????????????????????????????????????
VC get_vc_normal(VC a) {
	a = a * PT(0,-1);
	return a / abs(a);
}

int N;
const double EPS = 1e-9;

// rest code
int main() {
	while(cin >> N, N) {
		vector<PT> p;
		for(int i = 0; i < N; i++) {
			double x, y;
			cin >> x >> y;
			p.push_back(PT(x,y));
		}

		int res = 1;
		for(int i = 0; i < p.size(); i++) {
			for(int j = 0; j < p.size(); j++) {
				if(i == j) continue;
				VC a, b;
				PT c[2];
				double len;
				a = (p[j] - p[i]) / 2.0;
				if(abs(a) > 1.0) continue;
				b = get_vc_normal(a);
				len = sqrt(1.0 - norm(a));
				c[0] = p[i] + a + len*b;
				c[1] = p[i] + a - len*b;

				for(int k = 0; k < 2; k++) {
					int tmp = 0;
					for(int l = 0; l < p.size(); l++) {
						if(abs(c[k] - p[l]) < 1.0 + EPS) tmp++;
					}
					res = max(res, tmp);
				}
			}
		}
		cout << res << endl;
	}
}

Measured memory_bytes: 1276
#include<bits/stdc++.h>
// Begin Header {{{
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
using Graph = vector<vector<ll>>;
#define rep(i,n) for(ll i=0; i<n; i++)
#define loop(i, j, n) for(ll i=j; i<n; i++)
#define all(x) (x).begin(), (x).end()
constexpr int INF  = 0x3f3f3f3f;
const long long mod=1e9+7;
const long double PI = acos(-1);
// }}} End Header

int main() {
	int n;
	cin >> n;
	ll ans = 0;
	rep(i,n){
		ll a; cin >> a;
		ans+=a;
	}
	cout << ans-n << endl;
	return 0;
}

Measured memory_bytes: 3528
use std::borrow::Borrow;
use std::cmp::{max, min};
use std::io::{stdin, Read};
use std::str::FromStr;

// https://qiita.com/tubo28/items/e6076e9040da57368845
fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

#[allow(dead_code)]
fn main() {
    let d = read::<usize>();
    let g = read::<usize>();
    let n = d;
    let pcs = (0..n)
        .map(|_| (read::<usize>(), read::<usize>()))
        .collect::<Vec<_>>();
    let pcs = pcs.into_iter().enumerate().collect::<Vec<_>>();

    let width = 1 << n;
    let t = (0..width).map(|bits| (0..n).map(move |i| bits >> i & 1));
    let mut ans = usize::max_value();

    for x in t {
        let fil = x.collect::<Vec<_>>();
        let total_value: usize = pcs
            .iter()
            .map(|&(i, (p, c))| {
                if fil[i] == 1 {
                    (i + 1) * 100 * p + c
                } else {
                    0
                }
            })
            .sum();
        let total_count: usize = pcs
            .iter()
            .map(|&(i, (p, c))| if fil[i] == 1 { p } else { 0 })
            .sum();
        let rest = (&pcs).into_iter().filter(|x| fil[x.0] == 0);

        if total_value >= g {
            ans = min(ans, total_count)
        } else {
            let mut total_count = total_count;
            let mut total_value = total_value;

            'for1: for &(i, (p, c)) in rest.rev() {
                let div = if (g - total_value) % ((i + 1) * 100) == 0 {
                    (g - total_value) / ((i + 1) * 100)
                } else {
                    (g - total_value) / ((i + 1) * 100) + 1
                };
                let pp = min(div, p);
                total_count += pp;
                total_value += pp * ((i + 1) * 100);

                if total_value >= g {
                    ans = min(ans, total_count);
                    break 'for1;
                }
            }
        }
    }
    println!("{}", ans);
}


Measured memory_bytes: 4352
#include<iostream>
#include<cstdio>
using namespace std;
int main()
{
	int a,b,c,x,i,j,l,ans=0;
	cin>>a>>b>>c>>x;
	for(i=0;i<=a;i++)
		for(j=0;j<=b;j++)
			for(l=0;l<=c;l++)
				if(500*i+100*j+50*l==x) ans++;
	cout<<ans<<endl;
	return 0;
}

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

if n % 4 == 0:
	print("Yes")
elif n % 4 == 1 and n >= 21:
	print("Yes")
elif n % 4 == 2 and n >= 14:
	print("Yes")
elif n % 4 == 3 and n >= 7:
	print("Yes")
else:
	print("No")


Measured memory_bytes: 2940
import sys

readline = sys.stdin.readline
n, m = map(int, readline().split())
grid = []
for _ in range(n):
    row = readline()
    real_row = [c for c in row if c != "\n"]
    grid.append(real_row)
dp = []
sys.setrecursionlimit(10**7)

for _ in range(n):
    temp = []
    for j in range(m):
        temp.append(-1)
    dp.append(temp)


def traverse(i, j):
    path = 0
    if i < n-1 and j < m-1:
        if dp[i][j] != -1:
            return dp[i][j]
    if i == n - 1 and j == m - 1:
        return 1
    elif i == n - 1:
        if grid[i][j + 1] != "#":
            path += traverse(i, j + 1)
    elif j == m - 1:
        if grid[i + 1][j] != "#":
            path += traverse(i + 1, j)
    else:
        if grid[i + 1][j] != "#":
            path += traverse(i + 1, j)
        if grid[i][j + 1] != "#":
            path += traverse(i, j + 1)
    dp[i][j] = path
    return path % (10 ** 9 + 7)


print(traverse(0, 0))


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

#include <cstdlib>  // abs() for integer 絶対値求めやつ

#include <cmath>    // abs() for float, and fabs()

#include <algorithm>
#include <vector>
#include <string>
#define rep(i,n) for(int i = 0; i< (n);i++)

#define SORT(a) sort((a).begin(),(a).end());

#define che(a,string) cout<<string<<":"<<(a)<<endl;

#define ch(a,string) cout<<string<<":"<<(a)<<" ";

using namespace std;

typedef pair<int,int> p;

int main(){
  int n,k;
  cin>>n>>k;
  vector<int> A(n);
  rep(i,n){
	cin>>A[i];
  }
  int ans = 0;
  int K = k -1;
  while(n>0){
	if(ans==0){
	  n-=k;
	  ans ++;
	}
	else{
	  n-=K;
	  ans++;
	}
  }
  cout <<ans<<endl;
}

Measured memory_bytes: 640
fn main() {
    let (r, w) = (std::io::stdin(), std::io::stdout());
    let mut sc = IO::new(r.lock(), w.lock());
    let n: usize = sc.read();
    let m: usize = sc.read();
    let mut graph = vec![vec![]; n];
    for _ in 0..m {
        let a = sc.read::<usize>() - 1;
        let b = sc.read::<usize>() - 1;
        graph[a].push(b);
        graph[b].push(a);
    }

    let mut color = vec![0; n];
    let mut single = 0;
    let mut bipartite = 0;
    let mut other = 0;
    for i in 0..n {
        if color[i] == 0 {
            color[i] = 1;
            let is_bipartite = dfs(i, &graph, &mut color);
            let is_single = graph[i].is_empty();
            if is_single {
                single += 1;
            } else if is_bipartite {
                bipartite += 1;
            } else {
                other += 1;
            }
        }
    }

    let mut ans = single * n * 2 - single * single;
    ans += (bipartite + other) * other * 2 - other * other;
    ans += bipartite * bipartite * 2;
    println!("{}", ans);
}

fn dfs(v: usize, graph: &Vec<Vec<usize>>, color: &mut Vec<u8>) -> bool {
    let mut ok = true;
    for &next in graph[v].iter() {
        if color[next] == 0 {
            color[next] = if color[v] == 1 { 2 } else { 1 };
            ok &= dfs(next, graph, color);
        } else {
            ok &= color[next] != color[v];
        }
    }
    ok
}

pub struct IO<R, W: std::io::Write>(R, std::io::BufWriter<W>);

impl<R: std::io::Read, W: std::io::Write> IO<R, W> {
    pub fn new(r: R, w: W) -> IO<R, W> {
        IO(r, std::io::BufWriter::new(w))
    }
    pub fn write<S: std::ops::Deref<Target = str>>(&mut self, s: S) {
        use std::io::Write;
        self.1.write(s.as_bytes()).unwrap();
    }
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .0
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r' || b == b'\t')
            .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r' && b != b'\t')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }
    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}


Measured memory_bytes: 16252
x=[]
a=[] #appendのために宣言が必要
while True:
    try:
        a.append(list(map(int,input().split())))

    except:
        break;
        #または、quit(),os.exit()をして止める。


#[[1, 2, 2, 3, 1], [4, 5, 3, 4, 1, 2, 3, 4], [2, 3, 5, 6, 0, 2]]
for i in range(len(a)//2):
    x.append(i)
    n=i*2
    m=i*2+1
    s=sum(a[m])/a[n][0]
    for t in range(len(a[m])):
      if s>=a[m][t]:
        x[i]=x[i]+1
    print(x[i]-i)


Measured memory_bytes: 7452
#include <bits/stdc++.h>
using namespace std;
string grid[1000];
int h,w,ct;
bool vis[1000][1000];
set<int> adj[1000000];
set<pair<int,int> > co;
void dfs(int i,int j)
{
	if(vis[i][j]||grid[i][j]=='#')	return;
	co.insert(make_pair(i,j));
	vis[i][j]=true;
	if(i)dfs(i-1,j);
	if(i<h-1)dfs(i+1,j);
	if(j)dfs(i,j-1);
	if(j<w-1)dfs(i,j+1);
}
int main() {
	// your code goes here
	#ifndef ONLINE_JUDGE
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
	#endif
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	cin>>h>>w;
	int ch,cw;
	cin>>ch>>cw;
	int dh,dw;
	cin>>dh>>dw;
	for(int i=0;i<h;i++)
		cin>>grid[i];
	ct=0;
	memset(vis,false,sizeof(vis));
	map<pair<int,int>,int> gn;
	for(int i=0;i<h;i++)
	{
		for(int j=0;j<w;j++)
		{
			if(vis[i][j]||grid[i][j]=='#')	continue;
			dfs(i,j);
			for(set<pair<int,int> >::iterator it=co.begin();it!=co.end();it++)
				{gn[*it]=ct;}//cout<<(*it).first<<" "<<(*it).second<<" "<<ct<<endl;}
			co.clear();
			ct++;
		}
	}
	//cout<<ct<<endl;
	for(int i=0;i<h;i++)
		for(int j=0;j<w;j++)
		{
			for(int k=max(0,i-2);k<min(i+3,h);k++)
				for(int l=max(0,j-2);l<min(j+3,w);l++)
				{
					if(grid[i][j]=='#'||grid[k][l]=='#')	continue;
					if(gn[make_pair(i,j)]==gn[make_pair(k,l)])	continue;
					adj[gn[make_pair(i,j)]].insert(gn[make_pair(k,l)]);
					adj[gn[make_pair(k,l)]].insert(gn[make_pair(i,j)]);
				}
		}
	//cout<<adj[0].size()<<" "<<adj[1].size();
	int node=gn[make_pair(ch-1,cw-1)];
	int dis[ct+1],d=0;
	queue<int> n1;
	n1.push(node);
	bool v1[ct];
	for(int i=0;i<=ct;i++)
	{
		dis[i]=-1;v1[i]=false;
	}
	dis[node]=0;
	while(n1.size())
	{
		node=n1.front();
		n1.pop();
		//cout<<node<<" "<<d<<endl;
		for(set<int>::iterator it=adj[node].begin();it!=adj[node].end();it++)
		{
			if(v1[*it])	continue;
			v1[*it]=true;
			n1.push(*it);
			dis[*it]=dis[node]+1;
		}
	}
	cout<<dis[gn[make_pair(dh-1,dw-1)]];
	return 0;
}

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

int main(){
  long long n,t,now,next,ans=0;cin>>n>>t>>now;
  REP(i,n-1){
    cin>>next;
    ans+=min(t,next-now);
    now=next;
  }
  cout<<ans+t;
}

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

#define gcd(m,n) __gcd(m,n)
#define lcm(m,n) m*(n/gcd(m,n))
#define fast std::ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pi acos(-1.0)
#define endl '\n'
#define MOD 1000000007
#define ull unsigned long long
#define ll long long
#define ld long double
#define pb push_back
#define dbg(x) cout << #x << "  " << x << endl;

using namespace std;

ll mod(ll a, ll b) { return (a % b + b) % b; }
ll power(ll base, ll exp) 
{ll res=1;while(exp>0) {if(exp%2==1) res=(res*base);base=(base*base);exp/=2;}return res;}


int main()
{
	fast;
	ll n,x; cin>>n; ll arr[n]; 
	unordered_map<ll,ll>mp;
	for(ll i = 0; i < n; i++)
	{
		cin>>x; mp[x]++; arr[i] = x;
	}
	ll ans = 0;
	for(auto i = mp.begin(); i != mp.end(); i++)
	{
		if(i->second == 1) continue;
		ans += (i->second)*(i->second-1)/2;
	}
	for(ll k = 0; k < n; k++)
	{
		ll t = arr[k];
		ll t1 = ( mp[t] ) * ( mp[t] - 1) / 2;
		mp[t]--; 
		ll t2 = ( mp[t] ) * ( mp[t] - 1) / 2;
		cout << ans - (t1 - t2) << endl;
		mp[t]++;
	}
	return 0;	
} 

Measured memory_bytes: 9160
#include <stdio.h>
#include <stdlib.h>

struct Node{
    int key,parent,left,right;
};

void pre(struct Node *T,int h){
    if(h==-1) return;
    printf(" %d",T[h].key);
    pre(T,T[h].left);
    pre(T,T[h].right);
}
void in(struct Node *T,int h){
    if(h==-1) return;
    in(T,T[h].left);
    printf(" %d",T[h].key);
    in(T,T[h].right);
}

int main(void){
    int m,n,i,h=-1;
    char command[10];
    scanf("%d",&m);
    struct Node *T=malloc(sizeof(struct Node)*m);
    for(i=0;i<m;i++){
        T[i].parent=-1;
        T[i].left=T[i].right=-1;
    }
    for(i=0;i<m;i++){
        scanf("%s",command);
        if(command[0]=='i'){
            int x=h,y=-1,z;
            scanf("%d",&z);
            T[i].key=z;
            while(x!=-1){
                y=x;
                if(z<T[x].key) x=T[x].left;
                else x=T[x].right;
            }
            T[i].parent=y;
            if(y==-1) h=i;
            else if(z<T[y].key) T[y].left=i;
            else T[y].right=i;
        }
        else if(command[0]=='p'){
            in(T,h);
            printf("\n");
            pre(T,h);
            printf("\n");
        }
    }
    
    return 0;
}


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

x=[int(i) for i in input().split()]
y=[int(i) for i in input().split()]
y_plus=0
xy_dif=0

for i in range(n):
    if x[i]<y[i] and (x[i]-y[i])%2==0:
        y_plus=y_plus+int(0.5*(y[i]-x[i]))
        x[i]=y[i]
    elif x[i]<y[i] and (x[i]-y[i])%2==1:
        y_plus=y_plus+int(0.5*(y[i]-x[i]+1))
        x[i]=y[i]+1
        xy_dif=xy_dif+1
    else:
        xy_dif=xy_dif+x[i]-y[i]


#print(x)
#print(y_plus,xy_dif)

if xy_dif<=y_plus:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 4600
s=list(input())
ans=1000
tmp=s
for i in s:
    l=[]
    cnt=0
    for j in s:
        if j!=i:
            cnt+=1
        else:
            l.append(cnt)
            cnt=0
    l.append(cnt)
    if max(l)<=ans:
        ans=max(l)
print(ans)


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

int main() {
  
  int N, K;
  cin >> N >> K;
  int dist;
  dist = 0;
  
  for (int i = 0; i < N; i++) { 
    int x;
    cin >> x;
    
    int A = 0, B = 0;
    A = x*2;
    if (x > K){
      B = (x - K) * 2;
    }
    else {
      B = (K - x) * 2;
    }
    
    if (A <= B) {
      dist += A;
    }
    else {
      dist += B;
    }
  }
  cout << dist << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<math.h>
#define N 100005
#define K 200005
#define MOD (long long )1e9+7
#define ll long long int
using namespace std;
  vector<ll> dp(1<<21,-1);
bool c[21][21];
 int n;
void add_self(int &a,int b)
{
    a+=b;
    if(a>=MOD)
    {
        a-=MOD;
    }
}
void sub_self(int &a,int b)
{
    a-=b;
    if(a<0)
    {
        a+=MOD;
    }
}

ll min(ll a,ll b)
{
    return a<=b?a:b;
}
ll dfs(int mask,int a)
{
    if(dp[mask]!=-1)
    {
        return dp[mask];
    }
    if(mask==(1<<n) -1)
    {
       return 1;
    }
    if(a==n)
    {
        return 0;
    }
    int ans=0;
    for(int j=0;j<n;j++)
    {
        if(c[a][j] && !(mask&(1<<j)))
        {
            //cout<<-2<<endl;
            
            ans+=dfs(mask|(1<<j),a+1);
           if(ans>MOD)
           {
               ans-=MOD;
           }
        }
    }
    return dp[mask]=ans;
}
int main() {
   
    cin>>n;
  
  
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            cin>>c[i][j];
        }
    }
   
    ll ans =dfs(0,0);
    
    cout<<ans<<endl;
}


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

using namespace std;

struct edge
{
  int to, cost;
};


int N, M, S, T, D[100000];
vector< edge > g[100000];

int Dijkstra(int s, int t)
{
  typedef pair< int, int > Pi;

  vector< int > min_cost(N, 1 << 30);
  priority_queue< Pi, vector< Pi >, greater<> > que;
  que.emplace(0, s);
  min_cost[s] = 0;
  while(!que.empty()) {
    auto p = que.top();
    que.pop();
    if(p.second == t) return (p.first);
    if(p.first > min_cost[p.second]) continue;
    for(auto &e : g[p.second]) {
      if(p.first + e.cost >= min_cost[e.to]) continue;
      min_cost[e.to] = p.first + e.cost;
      que.emplace(min_cost[e.to], e.to);
    }
  }
  return (-1);
}

int main()
{
  cin >> N >> M >> S >> T;
  --S, --T;
  for(int i = 0; i < N; i++) cin >> D[i];
  for(int i = 0; i < M; i++) {
    int a, b;
    cin >> a >> b;
    --a, --b;
    g[a].emplace_back((edge) {b, D[b]});
  }
  for(int i = 1; i < N; i++) {
    g[i].emplace_back((edge) {i - 1, 0});
  }
  cout << Dijkstra(S, T) << endl;
}

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

partial_sum = [0] * N

tmp = 0
for i in range(N):
    tmp += A[i]
    partial_sum[i] = tmp

ans = abs(partial_sum[0]-(partial_sum[-1]-partial_sum[0]))

for i in range(1,N-1):
    ans = min(ans, abs(partial_sum[i]-(partial_sum[-1]-partial_sum[i])))

print(ans)


Measured memory_bytes: 24832
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
using namespace std;

long long i, o, t, j, l, s, z;

long long f(long long o, long long i, long long j, long long l)
{
	return  o + (i / 2) * 2 + (j / 2) * 2 + (l / 2) * 2;
}

int main(void)
{
	scanf("%lld %lld %lld %lld %lld %lld %lld", &i, &o, &t, &j, &l, &s, &z);
	printf("%lld\n", max(f(o, i, j, l), ((i > 0 && j > 0 && l > 0) ? (f(o, i - 1, j - 1, l - 1) + 3) : 0)));
	return 0;
}


Measured memory_bytes: 256
perfectPower :: Integer -> [Integer]
perfectPower x = 1 : do
  p <- [2 .. floor (0.001 + sqrt (fromIntegral x))]
  return $ floor (0.001 + fromIntegral x ** (1 / fromIntegral p)) ^ p

solve :: Integer -> Integer
solve x = maximum $ filter (<= x) $ perfectPower x

main :: IO ()
main = do
  x <- read <$> getLine
  print . solve $ x


Measured memory_bytes: 508
a=readlines.map(&:chomp)
b=a[1].split.map(&:to_i)
s=0
b.each {|e|s+=e}
c=s/a[0].to_i
d1=0;b.each {|e|d1+=(e-c)**2}
d2=0;b.each {|e|d2+=(e-c-1)**2}
d3=0;b.each {|e|d3+=(e-c+1)**2}
puts [d1, d2, d3].min

Measured memory_bytes: 1788
n = int(input())
a = list(map(int,input().split()))
a_dic = dict()
a_set = set()
for num in a:
  if num in a_dic:
    a_dic[num] += 1
  else:
    a_dic[num] = 1
  a_set.add(num)
k = len(a_dic)
a_set = list(a_set)
if k == 1:
  if 0 in a_dic:
    if a_dic[0] == n:
      print('Yes')
      exit()
elif k == 2:
  if a_dic[0] == n/3 and a_dic[a_set[1]] == 2*n/3:
    print('Yes')
    exit()
elif k == 3:
  if a_set[0] ^ a_set[1] ^ a_set[2] == 0:
    if a_dic[a_set[0]] == a_dic[a_set[1]] == a_dic[a_set[2]] == n/3:
      print('Yes')
      exit()
print('No')

Measured memory_bytes: 20820
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <ctime>

#define Rep(i, n) for (int i = 1; i <= n; i ++)
#define Rep0(i, n) for (int i = 0; i <= n; i ++)
#define RepG(i, x) for (int i = head[x]; i; i = edge[i].next)
#define v edge[i].to
#define mp(a, b) make_pair(a, b)

using namespace std;

const int N = 1000100;

char s0[N], s1[N];

int q[N];

int main()
{
	
	int n;
	scanf("%d", &n);
	scanf("%s%s", s0 + 1, s1 + 1);
	bool flag = true;
	Rep(i, n) if (s0[i] != s1[i]) flag = false;
	if (flag) { printf("0\n"); return 0;}
	int ans = 0, cnt = 0, l = n, he = 1, ta = 0;
	for (int i = n; i; i --) if (s1[i] != s1[i - 1]){
		bool flag = false;
		while (l && (s0[l] != s1[i] || l > i)) l --, flag = true;
		if (!l){ printf("-1\n"); return 0;}
		while (he <= ta && q[he] >= ta - he + 1 + i) he ++;
		if (l < i) q[++ ta] = l;
		ans = max(ans, ta - he + 1);
	}
	
	printf("%d\n", ans + 1);
	
	return 0;
}
/*

*/


Measured memory_bytes: 6144
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long long int lli;
typedef long double ld;
const int oo = 1e9;
const int mod = 1e9+9;

//Juan Pablo Betancourt Maldonado

const int nax = 1e5+3;
int n;
int dp[nax];
int a[nax];
int f(int i){
	if (i==n-1) return 0;
	if(dp[i]!=-1) return dp[i];
	int ans = abs(a[i]-a[i+1])+f(i+1);
	if(i!=n-2) ans = min(ans, abs(a[i]-a[i+2])+f(i+2));
	return dp[i]=ans;
}
int main(){
	cin>>n;
	for(int i=0; i<n; i++) cin>>a[i];
	memset(dp, -1, sizeof dp);
	cout<<f(0)<<endl;
	return 0;
}

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

#include <iostream>
//#include <algorithm>
// #include <iomanip>
#define ll long long
#define map unordered_map
#define set unordered_set
#define pll pair<ll, ll>
#define vll vector<ll>

using namespace std;

const ll MOD = 1000000007LL;
const ll INF = (1LL << 60LL);

ll N, A, B, C;

vector<ll> l_list;

ll calc(ll bits[]) {
  ll a = 0;
  ll b = 0;
  ll c = 0;

  ll r = 0;

  for (ll i = N - 1; i >= 0; i--) {
    // cout << bits[i];

    switch (bits[i]) {
      case 1:
        if (a > 0) {
          r += 10;
        }
        a += l_list[i];
        break;
      case 2:
        if (b > 0) {
          r += 10;
        }
        b += l_list[i];
        break;
      case 3:
        if (c > 0) {
          r += 10;
        }
        c += l_list[i];
        break;
    }
  }

  if (a == 0 || b == 0 || c == 0) {
    return INF;
  }

  r += abs(A - a);
  r += abs(B - b);
  r += abs(C - c);
  return r;
}

int main() {
  scanf("%lld %lld %lld %lld", &N, &A, &B, &C);

  for (ll i = 0; i < N; i++) {
    ll v;
    scanf("%lld", &v);
    l_list.emplace_back(v);
  }

  ll base = 4;
  ll K = N;
  ll bits[K];
  fill_n(bits, K, 0);

  ll ans = INF;

  for (;;) {
    bool finish = false;

    ll v = calc(bits);
    if (v < ans) {
      ans = v;

      // for (ll i = K - 1; i >= 0; i--) {
      //   cout << bits[i];
      // }
      // cout << endl;
      // cout << v << endl;
    }

    for (ll i = 0; i < K; i++) {
      if (bits[i] + 1 < base) {
        bits[i] += 1;
        break;
      } else {
        bits[i] = 0;

        if (i == K - 1) {
          finish = true;
          break;
        }
      }
    }
    if (finish) {
      break;
    }
  }

  cout << ans << endl;
}


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

int main() {
	// your code goes here
	int n,m;
	cin>>n>>m;
	char mat[n][m];
	queue<pair<int,pair<int,int>>>q;
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			cin>>mat[i][j];
			if(mat[i][j]=='#')
				q.push(make_pair(0,make_pair(i,j)));
		}
	}
	int x[]={0,0,1,-1};
	int y[]={-1,1,0,0};
	int ans=0;
	while(!q.empty()){
		pair<int,pair<int,int>>p=q.front();
		q.pop();
		ans=max(ans,p.first);
		for(int i=0;i<4;i++){
			int r=p.second.first+x[i];
			int s=p.second.second+y[i];
			if(r>=0 && r<n && s>=0 && s<m && mat[r][s]=='.'){
				mat[r][s]='#';
				q.push(make_pair(p.first+1,make_pair(r,s)));
			}
		}
	}
	cout<<ans;
	return 0;
}

Measured memory_bytes: 13328
#include<stdio.h>
int main()
{
	int a,b,c,d;
	while (scanf("%d%d%d%d",&a,&b,&c,&d)!=EOF)
	{
		if(c>=b||a>=d)
		{
			printf("0\n");
		}
		if(a<c&&c<b&&b<d)
		{
			printf("%d\n",b-c);
		}
		if(c<a&&a<b&&d<b&&d>a)
		{
			printf("%d\n",d-a);
		}
		if(c>a&&b>d)
		{
			printf("%d\n",d-c);
		}
		if(a>c&&d>b)
		{
			printf("%d\n",b-a);
		}
		if(a==c&&b==d)
		{
			printf("%d\n",b-a);
		}
		if(a==c&&b>d)
		{
			printf("%d\n",d-c);
		}
		if(b==d&&a<c)
		{
			printf("%d\n",d-c);
		}
		if(a==c&&d>b)
		{
			printf("%d\n",b-a);
		}
		if(b==d&&c<a)
		{
			printf("%d\n",b-a);
		}
	}
	return 0;
}

Measured memory_bytes: 128
N = int( input())
F = [0]*(N+1)
Q = 10**9 + 7
for i in range(1,N+1):
    n = i
    for j in range(2, int( N**(1/2))+1):
        while n%j == 0:
            F[j] += 1
            n //= j
    if n != 1:
        F[n] += 1
ans = 1
for i in range(N+1):
    ans *= F[i]+1
    ans %= Q
print(ans)


Measured memory_bytes: 3188
#include <stdio.h>
#include <math.h>

int main(void){
	int hen1,hen2,taikaku,tyouhou=0,hisigata=0;
	
	while(scanf("%d,%d,%d",&hen1,&hen2,&taikaku) != EOF){
		if(sqrt((double)(hen1*hen1 + hen2*hen2)) == taikaku && hen1 == hen2){
			// 正方形
		}else if(sqrt((double)(hen1*hen1 + hen2*hen2)) == taikaku){
			// 長方形
			tyouhou++;
		}else if(hen1 == hen2){
			hisigata++;
		}
	}
	printf("%d\n%d\n",tyouhou,hisigata);
	return 0;
}

Measured memory_bytes: 596
from math import *

A, B, H, M = map(int, input().split())

angle_H = (60*H + M) * 2 * pi / 720
angle_M = M * pi / 30

angle = pi + abs(pi - abs(angle_H - angle_M))

ans_sq = A**2 + B**2 - 2*A*B * cos(angle)
ans = sqrt(ans_sq)

print(ans)


Measured memory_bytes: 9496
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int a[] = new int[4];
        a[0] = scanner.nextInt();
        a[1] = scanner.nextInt();
        a[2] = scanner.nextInt();
        a[3] = scanner.nextInt();
        int r = scanner.nextInt();
        int t = scanner.nextInt();
        int x = 0;
        java.util.Arrays.sort(a);
        for (int i = 0; i < a.length; i++) {
            x = a[1] + a[2] + a[3];
        }
        if (r < t) {
            x = x + t;
        } else {
            x = x + r;
        }
        System.out.println(x);
    }

}



Measured memory_bytes: 26252
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <bitset>
#include <deque>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>
#include <iterator>
#include <string>
#include <chrono>
#include <random>

#define int long

const int INF = 1000000009;
const long LINF = 1123456789012345678;

int n[10];

signed main(){
	int a;
	for(int i = 0; i < 4; i++){
		scanf("%ld", &a);
		n[a]++;
	}
	if(n[1] == 1 && n[9] == 1 && n[7] == 1 && n[4] == 1){
		printf("YES\n");
	}else{
		printf("NO\n");
	}
	return 0;
}


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

int main() {
    int m, f, r;
    
    while (1) {
        cin >> m >> f >> r;
    
        if (m == -1 && f == -1 && r == -1) break;
    
        if (m == -1 || f == -1) {
            cout << "F" << endl;
        } else if (m + f >= 80) {
            cout << "A" << endl;
        } else if (m + f >= 65) {
            cout << "B" << endl;
        } else if (m + f >= 50) {
            cout << "C" << endl;
        } else if (m + f >= 30) {
            if (r >= 50) {
                cout << "C" << endl;
            } else {
                cout << "D" << endl;   
            }
        } else {
            cout << "F" << endl;   
        }   
    }
    return 0;
}


Measured memory_bytes: 3092
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
const int MAX_V = 1e+5, INF = 1e+9;
struct edge {int to, cost;};
typedef pair<int, int> P;
int V, E, r, D[MAX_V]; vector<edge> G[MAX_V];

void dijkstra(int s) {
  fill(D, D+V, INF); D[r] = 0;
  priority_queue<P, vector<P>, greater<P>> q;
  q.push(P(0, s));
  while(!q.empty()) {
    P p = q.top(); q.pop();
    int now = p.second;
    if(D[now] < p.first) continue;
    for(int i = 0; i < G[now].size(); ++i) {
      edge e = G[now][i];
      if(D[e.to] > D[now] + e.cost) {
        D[e.to] = D[now] + e.cost;
        q.push(P(D[e.to], e.to));
      }
    }
  }
}
int main() {
  scanf("%d %d %d", &V, &E, &r);
  for(int i = 0, s, t, d; i < E; ++i) {
    scanf("%d %d %d", &s, &t, &d);
    edge e = {t, d};
    G[s].push_back(e);
  }
  dijkstra(r);
  for(int i = 0; i < V; ++i) {
    if(D[i] == INF) {
      printf("%s\n", "INF");
    } else {
      printf("%d\n", D[i]);
    }
  }
}


Measured memory_bytes: 12616
# include <iostream>
# include <algorithm>
# include <vector>
# include <string>
# include <set>
# include <map>
# include <cmath>
# include <iomanip>
# include <functional>
# include <utility>
# include <stack>
# include <queue>
# include <list>
# include <tuple>
# include <unordered_map>
# include <numeric>
# include <complex>
# include <bitset>
using namespace std;
using LL = long long;
using ULL = unsigned long long;
typedef pair<LL, LL> P;
constexpr int INF = 2000000000;
constexpr int HINF = INF / 2;
constexpr double DINF = 100000000000000000.0;
constexpr long long LINF = 9223372036854775807;
constexpr long long HLINF = 4500000000000000000;
constexpr long long MMOD = 500000004;
const double PI = acos(-1);
int dx[4] = { 0,1,0,-1 }, dy[4] = { 1,0,-1,0 };
# define ALL(x)      (x).begin(),(x).end()
# define UNIQ(c)     (c).erase(unique(ALL((c))), end((c)))
# define mp          make_pair
# define eb          emplace_back
# 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(i,0,n)
# define INIT        std::ios::sync_with_stdio(false);std::cin.tie(0)

int n;

int main() {
	cin >> n;
	cout << 0 << endl << flush;
	string s, ss;
	cin >> s;
	if (s == "Vacant")return 0;
	int left = 0, right = n;
	bool last;
	while (right - left > 1) {
		int mid = (right + left) / 2;
		cout << mid << endl << flush;
		cin >> ss;
		if (ss == "Vacant")return 0;
		if (mid % 2 == 0) {
			if (ss != s)right = mid;
			else left = mid;
			last = true;
		}
		else {
			if (ss != s)left = mid;
			else right = mid;
			last = false;
		}
	}
	if (last) {
		cout << right << endl << flush;
		cin >> ss;
	}
	else {
		cout << left << endl << flush;
		cin >> ss;
	}
}

Measured memory_bytes: 852
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using static System.Console;
using static System.Math;

namespace AtCoder
{
    class Program
    {
        static void Main(string[] args)
        {
            var n = ReadInt();
            var ans = 0;
            for (int i = 1; i <= n; i++)
            {
                if (i.ToString().Count() % 2 != 0)
                {
                    ans++;
                }
            }
            WriteLine(ans);
        }

        private static string Read() { return ReadLine(); }
        private static string[] Reads() { return (Read().Split()); }
        private static int ReadInt() { return int.Parse(Read()); }
        private static long ReadLong() { return long.Parse(Read()); }
        private static double ReadDouble() { return double.Parse(Read()); }
        private static int[] ReadInts() { return Array.ConvertAll(Read().Split(), int.Parse); }
        private static long[] ReadLongs() { return Array.ConvertAll(Read().Split(), long.Parse); }
        private static double[] ReadDoubles() { return Array.ConvertAll(Read().Split(), double.Parse); }

        //最大公約数

        public static int Gcd(int a, int b)
        {
            if (a < b)
            {
                return Gcd(b, a);
            }
            while (b != 0)
            {
                var reminder = a % b;
                a = b;
                b = reminder;
            }
            return a;
        }

        //最小公倍数
        public static int Lcm(int a, int b)
        {
            return a * b / Gcd(a, b);
        }

        //文字数を数える
        public static int CountChar(string s, char c)
        {
            return s.Length - s.Replace(c.ToString(), "").Length;
        }
    }
}


Measured memory_bytes: 15312
#include <iostream>
#include <iomanip>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <array>
#include <tuple>
#include <string>
#include <algorithm>
#include <functional> // greater など
#include <cmath>      // abs など
#include <numeric>    // accumulate, gcd など
#include <cassert>    // assert
#include <stdexcept>
#include <bitset>
using namespace std;

// #include <boost/multiprecision/cpp_int.hpp>
// using namespace boost::multiprecision;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
typedef long long ll;
// typedef int128_t ll;
// typedef cpp_int ll;

// GCC, 配列のアクセスなど
#define _GLIBCXX_DEBUG
// Clang, 配列のアクセスなど
#define _LIBCPP_DEBUG 0

#define debug(...)

//////////////// //////////////// //////////////// //////////////// ////////////////
//////////////// //////////////// //////////////// //////////////// ////////////////

// constexpr inline ll mod = 1'000'000'007;
constexpr int max_n = 200'000 + 5;

int n;
vector<bool> x(max_n);
vector<vector<ll>> pow2(3, vector<ll>(max_n));
vector<ll> sums(3);
int cnt;

int main()
{
    // 高速な入出力
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << setprecision(15); // 浮動小数の表示の精度

    cin >> n;
    rep(i, n) {
        char c; cin>>c;
        x[i] = (c == '1');
        if (x[i]) { cnt++; }
    }

    if (cnt == 0) {
        rep(i, n) {
            cout << '1' << '\n';
        }
        return 0;
    }

    for (int j = -1; j <= 1; j++) {
        if (cnt + j <= 0) { continue; }
        pow2[j+1][0] = 1;
        rep(i, n) {
            pow2[j+1][i+1] = pow2[j+1][i] * 2 % (cnt + j);
        }
    }
    debug(pow2[0][0]);
    debug("ををを");
    rep(j,3) {
        reverse(pow2[j].begin(), pow2[j].begin() + n);
    }
    debug("ぬやうさあさああｓ");
    debug(pow2[0][0]);
    for (int j = -1; j <= 1; j++) {
        debug("ｎｙぽいｓだｆだ", j);
        if (cnt + j <= 0)
        {
            continue;
        }
        rep(i, n) {
            debug("んｄそあいｆｊさｌｋｄｋｌｄさあっｓｄｆじょいさｆぁｋふぉえｋｒｐｆじぇｗｋｗ", i, x[i]);
            if (x[i]) { sums[j+1] += pow2[j+1][i]; sums[j+1] %= cnt+j; }
        }
    }

debug("っわああああ^^^^");
    rep(i, n) {
        if (x[i] && cnt == 1) {
            cout << 0 << '\n';
            continue;
        }
        int tmpres = 1;
        ll tmp = 0;
        if (x[i]) {
            tmp = sums[0] - pow2[0][i];
            tmp += cnt-1;
            tmp %= cnt-1;
        } else {
            tmp = sums[2] + pow2[2][i];
            tmp %= cnt+1;
        }
        while (tmp != 0) {
            tmpres++;
            tmp %= bitset<64>(tmp).count();
        }
        cout << tmpres << '\n';
    }

    return 0;
}


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

#define vi vector<int>
#define vl vector<long>
#define vvi vector<vector<int>>
#define vvl vector<vector<long>>
#define pint pair<int, int>
#define plong pair<long, long>
long INF = (1LL << 60);

int main() {
    int N;
    cin>>N;
    vi A(N+1);
    REP(i, 0, N+1){
        cin >> A[i];
    }
    
    if(N == 0){
        if(A[0] == 1) cout << 1 << endl;
        else cout << -1 << endl;
        return 0; 
    }
    vl maxN(N+1, 0);
    vl node(N+1, 0);
    maxN[0] = 1;
    
    REP(i, 1, N+1){
        maxN[i] = (long)min((maxN[i-1] - A[i-1]) * 2, INF);
    }
    /*
    REP(i, 0, N+1) cout << maxN[i] << " ";
    cout << endl;
    */
    node[N] = A[N];
    for(int i = N-1; i >=0; i--){
        if(maxN[i] >= node[i+1] + A[i]){
            node[i] = node[i+1] + A[i];
        }else if(maxN[i] >= (long)(node[i+1]+1)/2 + A[i]){
            node[i] = maxN[i];
        }else{
            cout << -1 << endl;
            return 0;
        }
    }
    
    cout << accumulate(node.begin(), node.end(), 0LL) << endl;
}

Measured memory_bytes: 5100
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <ctime>
#include <cstring>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

#define rep(i,n)   for (int i = 0; i < (n); ++i)
#define sort(a)    sort((a).begin(), (a).end());
#define uniq(a)    SORT(a);(a).erase(unique((a).begin(), (a).end()), (a).end());
#define find(a,x)  find((a).begin(), (a).end(), (x)) != (a).end()
#define reverse(a) reverse((a).begin(), (a).end());
#define out(d) cout << (d);
#define outl(d) std::cout<<(d)<<"\n";
#define Yes() printf("Yes\n");
#define No() printf("No\n");
#define YES() printf("YES\n");
#define NO() printf("NO\n");
#define ceil(x, y) ((x + y - 1) / (y))

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

const ll MOD = 1000000007; // 10^9 + 7

ll sum(vector<ll> a) {
  ll ret = 0;
  for (int i = 0; i < a.size(); i++)
    ret += a[i];
  return ret;
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  srand((unsigned)time(NULL));

  string s; cin >> s;
  s += '.';
  ll n = s.size(), ans = 0;

  vector<ll> l(n + 1);
  ll sum = 0;
  for (int i = 0; i < n; i++) {
    if (s[i] == '<') sum++;
    else sum = 0;

    l[i + 1] = sum;
  }

  vector<ll> r(n + 1);
  sum = 0;
  for (int i = n - 1; i >= 0; i--) {
    if (s[i] == '>') sum++;
    else sum = 0;

    r[i] = sum;
  }

  for (int i = 0; i < n; i++) {
    ans += max(l[i], r[i]);
  }

  outl(ans)
}


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

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

    int n = s.length();
    int t = 0;
    string ans;
    while(1){
        if(t >= n){
            break;
        }
        ans += s[t];
        t += w;
    }

    cout << ans << endl;
}

Measured memory_bytes: 3596
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <bitset>
#include <deque>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>
#include <iterator>
#include <string>
#include <chrono>
#include <random>
#include <tuple>
#include <utility>
#include <fstream>
#include <complex>

const long INF = (1l << 30);
const long LINF = (1l << 60);

long n;
long d[55];

int main(){
    scanf("%ld", &n);
    for(int i = 0 ; i < n; i++){
        scanf("%ld", d+i);
    }
    long ans = 0;
    for(int i = 0; i < n; i++){
        for(int j = i+1; j < n; j++){
            ans += d[i] * d[j];
        }
    }
    printf("%ld\n", ans);
}


Measured memory_bytes: 256