akhauriyash/Code-Regression huggingface dataset:
#include <utility>
#include <iostream>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

int binarySearch(int key, const std::vector<int> &S){
  int L = 0;
  int R = S.size();
  int mid;
  while (L < R) {
    mid = (L+R)/2;
    if (S[mid]==key) {
      return 1;
    }
    if (key > S[mid]) {
      L = mid + 1;
    }else if (key < S[mid]) {
      R = mid;
    }
  }
  return 0;
}


int main(int argc, char const *argv[]) {
  int n; std::cin >> n;
  int val;
  std::vector<int> S; S.reserve(100000);

  for (size_t i = 0; i < n; i++) {
    std::cin >> val;
    S.push_back(val);
    }

  int num=0;


  int q; std::cin >> q;
  int key;
  for (size_t i = 0; i < q; i++) {
    std::cin >> key;
    if (binarySearch(key, S)) num++;
  }


  std::cout << num << '\n';

  return 0;
}



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

bool cont(int x, vector<int> &dig){
  bool ret = false;
  while(x>0){
    int c = x % 10;
    if(binary_search(dig.begin(), dig.end(), c))
      ret = true;
    x /= 10;
  }
  return ret;
}

int main(){
  int N, K; cin >> N >> K;
  vector<int> dig(K);
  
  for(int i = 0; i < K; i++){
    cin >> dig[i];
  }
  sort(dig.begin(), dig.end());
  
  int ans = N;
  while(cont(ans, dig)){
    ans++;
  }
  
  
  cout << ans << endl;
}

Measured memory_bytes: 256
#![allow(dead_code)]
use std::io::{self, Read};
use std::str::FromStr;
use std::u64;
use std::collections::VecDeque;

pub struct Scanner<R: Read> {
    reader: R,
}
impl<R: Read> Scanner<R> {
    pub fn new(reader: R) -> Scanner<R> {
        Scanner { reader: reader }
    }
    pub fn read<T: FromStr>(&mut self) -> T {
        let s = self
            .reader
            .by_ref()
            .bytes()
            .map(|c| c.expect("failed to read char") as char)
            .skip_while(|c| c.is_whitespace())
            .take_while(|c| !c.is_whitespace())
            .collect::<String>();
        s.parse::<T>().ok().expect("failed to parse token")
    }
}

// 0からidxまでの最短経路を探す
fn find_shortest(mat: &Vec<Vec<u64>>, dist: &mut Vec<u64>) {
    // BFSで探索していく感じ？
    let n = mat.len();
    let mut que = VecDeque::new();
    que.push_back(0);
    dist[0] = 0;

    while let Some(i) = que.pop_front() {
        for j in 0..n {
            if mat[i][j] < u64::MAX {
                let d = dist[i] + mat[i][j];
                if dist[j] > d {
                    dist[j] = d;
                    que.push_back(j);
                }
            }
        }
    }
}

// ダイクストラのアルゴリズムを使った最短経路探索
fn dijkstra(mat: &Vec<Vec<u64>>, dist: &mut Vec<u64>) {
    let n = mat.len();
    // 初期状態
    dist[0] = 0;
    for i in 1..n {
        dist[i] = u64::MAX;
    }

    let mut par: Vec<usize> = vec![0; n];       // 親の添え字
    let mut check: Vec<bool> = vec![false; n];  // 訪問状態

    for _ in 0..n {
        // 探索済みでない最小のd[u]を調査
        let mut min = u64::MAX;
        let mut mid = 0;
        for i in 0..n {
            if check[i] == false && dist[i] <= min {
                mid = i;
                min = dist[i];
            }
        }

        // d[u]を訪問済みとし、未訪問の集合を更新する
        check[mid] = true;
        for i in 0..n {
            if check[i] == false 
                && mat[mid][i] != u64::MAX 
                && dist[mid] + mat[mid][i] < dist[i] {
                par[i] = mid;
                dist[i] = dist[mid] + mat[mid][i];
            }
        }
    }
}


fn main() {
    let sin = io::stdin();
    let sin = sin.lock();
    let mut sc = Scanner::new(sin);

    let n: usize = sc.read();
    let mut mat: Vec<Vec<u64>> = vec![vec![u64::MAX; n]; n];
    for _ in 0..n {
        let u: usize = sc.read();
        let k: usize = sc.read();
        for _ in 0..k {
            let v: usize = sc.read();
            let c: u64 = sc.read();
            mat[u][v] = c;
        }
    }

    // 0からiまでの最短経路
    let mut dist: Vec<u64> = vec![u64::MAX; n];
    // find_shortest(&mat, &mut dist);
    dijkstra(&mat, &mut dist);

    for i in 0..n {
        println!("{} {}", i, dist[i]);
    }
}



Measured memory_bytes: 5044
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: i32 = sc.read();
    let a: Vec<i32> = sc.vec(n);
    let sum = a.iter().sum::<i32>();
    let mut count = 0;
    for a in a.into_iter() {
        if a * 4 * m >= sum {
            count += 1;
        }
    }
    if count >= m {
        println!("Yes");
    } else {
        println!("No");
    }
}

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: ToString>(&mut self, s: S) {
        use std::io::Write;
        self.1.write(s.to_string().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: 4352
#include<stdio.h>
int main()
{
     long long int a,b,c,k,ans;
     scanf("%lld%lld%lld%lld",&a,&b,&c,&k);
     if(a>=k)
          ans=k;
     else if(a<k&&a+b>=k)
          ans=a;
     else if(a+b<k)
          ans=a-(k-a-b);

     printf("%lld\n",ans);

     return 0;

}


Measured memory_bytes: 1728
#include <bits/stdc++.h>
#define ll long long
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end))) // rep(i, 1, 5) --> {1,2,3,4} // rep(i, 5, 1) --> {4,3,2,1} // rep(it, end(v), begin(v)) --> *it

using namespace std;

int main()
{
    ll n, k;
    cin >> n >> k;
    vector<double> v(n);
    rep(i, 0, n)
    {
        ll a; 
        cin >> a;
        v[i] = (a*(a+1)/2)/(double)a;
    }
    vector<double> dp(n+1);
    dp[0] = 0;
    rep(i, 1, n + 1)
        dp[i] = dp[i-1] + v[i-1];
    double res = 0;
    for (int i = 1; i + k - 1 <= n; i++)
        res = max(res, dp[i+k-1] - dp[i-1]);
    cout << setprecision(10) << res;    
    return 0;
}

Measured memory_bytes: 3328
n,m=map(int,input().split())
a = 1
Mod=10**9+7
d = [1]*(n+1)
for i in range(n):
  d[i+1]=((m-n+i)*d[i]+i*d[i-1])%Mod
  a=a*(m-i)%Mod
print(a*d[n]%Mod)

Measured memory_bytes: 28480
#include <cassert>
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
/*
//#if __cplusplus >= 201103L
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
*/

// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
/*
//#if __cplusplus >= 201103L
#include <array>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
*/
using namespace std;
#define  Int  long long

template <typename T>
struct WeightedUnionFind{
  Int n;
  T d;
  vector<Int> r,p;
  vector<T> ws;
  WeightedUnionFind(){}
  WeightedUnionFind(Int sz,T d_):
    n(sz),d(d_),r(n,1),p(n),ws(n,d){iota(p.begin(),p.end(),0);}
  Int find(Int x){
    if(x==p[x]){
      return x;
    }else{
      Int t=find(p[x]);
      ws[x]+=ws[p[x]];
      return p[x]=t;
    }
  }
  T weight(Int x){
    find(x);
    return ws[x];
  }
  bool same(Int x,Int y){
    return find(x)==find(y);
  }
  void unite(Int x,Int y,T w){
    w+=weight(x);
    w-=weight(y);
    x=find(x);y=find(y);
    if(x==y) return;
    if(r[x]<r[y]) swap(x,y),w=-w;
    r[x]+=r[y];
    p[y]=x;
    ws[y]=w;
  }
  T diff(Int x,Int y){
    return weight(y)-weight(x);
  }
};

signed main(){
  Int n,m;
  cin>>n>>m;
  WeightedUnionFind<Int> wuf(n+1,0);
  for(Int i=0;i<m;i++){
    Int l,r,d;
    cin>>l>>r>>d;
    l--;r--;
    if(wuf.same(l,r)){
      if(wuf.diff(l,r)!=d){
  cout<<"No"<<endl;
  return 0;
      }
    }else{
      wuf.unite(l,r,d);
    }
  }
  cout<<"Yes"<<endl;
  return 0;
}


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

//  a^b % m
long long powmod(long long a, long long b, long long m)
{
    long long r = 1;
    for (; b>0; b>>=1, a=a*a%m)
        if (b&1)
            r = r*a%m;
    return r;
}

int main()
{
    long long X, Y;
    cin>>X>>Y;

    long long M = 1000000007;
    vector<long long> F(1000001);
    F[0] = 1;
    for (long long i=1; i<=1000000; i++)
        F[i] = F[i-1]*i%M;

    long long ans = 0;
    for (long long a=0; a<=X; a++)
    {
        long long b = (X-a)/2;
        if (a+2*b==X && a*2+b==Y)
            ans += F[a+b]*powmod(F[a],M-2,M)%M*powmod(F[b],M-2,M)%M,
            ans %= M;
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 8572
#include<iostream>
#include<vector>
using namespace std;
 
int main(){
	int n; cin >> n;
	vector<string> s(n);
	for(int i=0;i<n;i++) cin >> s[i];
	vector<int> marchnum(5,0);
	for(int i=0;i<n;i++){
		if(s[i].front()=='M') marchnum[0]++;
		if(s[i].front()=='A') marchnum[1]++;
		if(s[i].front()=='R') marchnum[2]++;
		if(s[i].front()=='C') marchnum[3]++;
		if(s[i].front()=='H') marchnum[4]++;
	}
	long long ans=0;
	for(int i=0;i<3;i++){	
		for(int j=i+1;j<4;j++){
			long long temp=0;
			for(int k=j+1;k<5;k++) temp+=marchnum[k];
			ans+=marchnum[i]*marchnum[j]*temp;
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 6144
#include<bits/stdc++.h>
using namespace std;
int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n, a, b;
  cin >> n >> a >> b;
  cout << min(a, b) << " " << max(0, a+b-n) << endl;  
  return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
 
    public static void main(String[] args) {
      Scanner sc=new Scanner(System.in);
      int A,B;
      A=sc.nextInt();
      B=sc.nextInt();
     // System.out.println(A);
      sc.close();
      System.out.println(solve(A,B));
    }
  
  static long solve(int a,int b){
    long result=1;
    int i;
    for(i=2;i<=a&&i<=b;i++){
      if(a%i==0&&b%i==0){
        result=result*i;
        a=a/i;
        b=b/i;
        i=1;
       // System.out.println("a,b,result="+a+" "+b+" "+result);
      }
    }
    
    return result*(long)a*(long)b;
  }
 
}

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


typedef long long int ll;

vector<ll> adj[1000001]; 


#define mod 1000000007
#define pb push_back
#define endl cout<<"\n";
#define prt1(a) cout<<a<<" "
#define prt2(a,b) cout<<a<<" "<<b<<" "
#define prt3(a,b,c) cout<<a<<" "<<b<<" "<<c<<" "
#define rep(i,st,end) for( i=st;i<end;i++)
#define repv(i,st,end) for( i=st;i>=end;i--)
#define fio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define TEST cin>>tc;while(tc--)

int main()
{
    ll k;
    cin>>k;
    ll g=0;
    for(int i=1;i<=k;i++)
    {
        for(int j=1;j<=k;j++)
        {
            for(int c=1;c<=k;c++)
            {
                g+=__gcd(c,__gcd(i,j));
            }
        }
    }
    cout<<g;
}

Measured memory_bytes: 27036
n = gets.to_i
s = gets.chomp.split("")

max = 0
1.upto(n) do |i|
  first = s[0...i].uniq.sort
  last = s[i..-1].uniq.sort
  num = first.size - (first - last).size
  max = [max, num].max
end

puts max

Measured memory_bytes: 1788
# ITP1_7_A_0001.rb

while true
	m,f,r = gets.split.map(&:to_i)

	if ( m == -1 && f == -1 && r == -1 )
		break
	end

	if ( m == -1 || f == -1 )
		puts "F"
	elsif m + f >= 80
		puts "A"
	elsif m + f >= 65
		puts "B"
	elsif m + f >= 50
		puts "C"
	elsif m + f >= 30
		if r >= 50
			puts "C"
		else
			puts "D"
		end
	else
		puts "F"
	end
end

Measured memory_bytes: 6096
#include <algorithm>
#include <iostream>
#include <cmath>
#include <deque>

using namespace std;
int main()
{
    int kus;
    deque<int> hold,out;
    cin>>kus;
    for(int i=0;i<3;++i)
    {
        int dev=pow(10,2-i);
        hold.push_back(ceil(kus/dev));
        kus=kus-ceil(kus/dev)*dev;
    }
    for(int j:hold)
    {
        if(j==1) out.push_back(9);
        else out.push_back(1);
    }
    int change=out[0]*100+out[1]*10+out[2];
    cout<<change;
}


Measured memory_bytes: 256
N, K, C = list(map(int, input().split(" ")))
S = input()

F_list = []
B_list = []

f_count = 0
b_count = 0
f_rest = 0
b_rest = 0
S_len = len(S)
# o
for i in range(S_len):
    if f_count == K and b_count == K:
        break

    if f_count < K:
        if S[i] == "o" and f_rest == 0:
            f_rest += C
            f_count += 1
            F_list.append(i+1)
        else:
            if f_rest > 0:
                f_rest -= 1
    if b_count < K:
        if S[-(i+1)] == "o" and b_rest == 0:
            b_rest += C
            b_count += 1
            B_list.append(S_len-i)
        else:
            if b_rest > 0:
                b_rest -= 1

for i in range(K):
    if F_list[i] == B_list[-(i+1)]:
        print(F_list[i])


Measured memory_bytes: 20620
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<sstream>
#include<cmath>
#include<numeric>
#include<map>
#include<stack>
#include<queue>
#include<list>
#include<set>
#include<cstring>
using namespace std;

int main() {

  double t, x; cin >> t >> x;
  printf("%.10lf\n", t/x);

  return 0;
}



///


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

using namespace std;

int MAX = 9;

vector <int> v;

int main() {
	int n;
	
	while (cin>>n) {
		v.clear();
		
		for (int i=0; i<=MAX; i++) v.push_back(n-i);
		sort(v.begin(), v.end());
		
		int ans = 0;
		
		for (int i=0; i<=MAX; i++) {
			for (int j=0; j<=MAX; j++) {
				for (int k=0; k<=MAX; k++) {
					if (binary_search(v.begin(), v.end(), i+j+k)) ans++;
				}
			}
		}
		cout << ans << endl;
	}
	
	return 0;
}

Measured memory_bytes: 1216
#include "bits/stdc++.h"
using namespace std;
#define Rep(i,n) for(int i=0;i<(int)(n);i++)
#define For(i,n1,n2) for(int i=(int)(n1);i<(int)(n2);i++)
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define RREP(i,n) for(ll i=((ll)(n)-1);i>=0;i--)
#define FOR(i,n1,n2) for(ll i=(ll)(n1);i<(ll)(n2);i++)
#define RFOR(i,n1,n2) for(ll i=((ll)(n1)-1);i>=(ll)(n2);i--)
#define all(a)  (a).begin(),(a).end()
#define SORT(a) sort((a).begin(),(a).end())
#define oorret 0
#define oor(x) [&](){try{x;} catch(const out_of_range& oor){return oorret;} return x;}()
#define IOS cin.tie(0),ios::sync_with_stdio(false)
typedef long long ll;
typedef unsigned long long ull;
typedef std::pair<ll, ll> P;
template<typename T1, typename T2> inline bool chmin(T1& a, T2 b) { if (a > b) { a = b; return 1; }return 0; }
template<typename T1, typename T2> inline bool chmax(T1& a, T2 b) { if (a < b) { a = b; return 1; }return 0; }
template<class Type>struct is_vector : std::false_type {};
template<class ValueType, class Alloc>struct is_vector<std::vector<ValueType, Alloc>> : std::true_type {};
template <typename T> inline std::ostream& operator << (std::ostream& out, const std::vector<T>& v) {
	if (v.empty())return out;
	constexpr bool is_vector_v = is_vector<T>::value;
	if (is_vector_v)for (auto itr = v.begin(); itr != v.end();)out << (*itr), out << ((++itr != v.end()) ? "\n" : "");
	else for (auto itr = v.begin(); itr != v.end();)out << (*itr), out << ((++itr != v.end()) ? " " : "");
	return out;
}
inline void put() {}
template<class T> inline void put(const T& first) { std::cout << first << "\n"; }
template<class T, class... N> inline void put(const T& first, const N& ... rest) { std::cout << first << " "; put(rest...); }
inline void putn() {}
template<class T, class... N> inline void putn(const T& first, const N& ... rest) { std::cout << first << "\n"; putn(rest...); }


int main() {
	IOS;
	ll n;
	cin >> n;
	vector<ll> a(n);
	REP(i, n) {
		cin >> a[i];
	}
	ll res = 0;
	map<ll, ll> mp;
	REP(i, n) {
		mp[a[i]] += 1;
	}
	for (auto&& v : mp) {
		ll t = v.second;
		res += t * (t - 1) / 2;
	}
	REP(i, n) {
		ll r = res;
		ll t = mp[a[i]];
		r -= t * (t - 1) / 2;
		t--;
		r += t * (t - 1) / 2;
		put(r);
	}
	return 0;
}

Measured memory_bytes: 11136
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    d = defaultdict(lambda : 0)
    n = I()
    for i in range(n):
        u = input()
        d[u] = 1
    ans = ["Opened by", "Closed by"]
    m = I()
    k = 0
    for i in range(m):
        t = input()
        if not d[t]:
            print("Unknown",t)
        else:
            print(ans[k],t)
            k ^= 1
    return

#Solve
if __name__ == "__main__":
    solve()



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



signed main(){
    int n,p=0,t,x,y,t0=0,x0=0,y0=0;
    cin >>n;
    for(int i=0;i<n;i++ ){
        cin >> t >> x >>y;
        if(abs(x0-x)+abs(y0-y)>abs(t0-t))p=1;
        else{
            if((-abs(x0-x)-abs(y0-y)+abs(t0-t))%2 ==1)p=1; 
        }
        t0=t;x0=x;y0=y;
    }
    if(p==1)cout <<"No";
    else cout << "Yes";
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <climits>
#include <algorithm>
#include <set>
#include <unordered_map>
#include <queue>
#include <iomanip>

#define rep(i,n) for(int i=0; i<(int)(n); i++)
using namespace std;

int N;
int A, B;
vector<long> H(100005);

bool fi(long n) {
  long ans = 0;
  rep(i, N) {
    long rem = H.at(i) - n*B;
    if (rem > 0) {
      ans += rem / (A-B);
      if (rem % (A-B) > 0) {
        ans++;
      }
    }
  }
  // cout << "n: " << n << " ans: " << ans << endl;
  return (n >= ans);
}

int binary_search(int from, int to) {
  int pos = (from+to)/2;
  if (from == to) {
    return from;
  }
  if (fi(pos)) {
    return binary_search(from, pos);
  } else {
    return binary_search(pos+1, to);
  }
}

int main() {
  cin >> N >> A >> B;
  long ma = 0;
  rep(i, N) {
    cin >> H.at(i);
    ma = max(ma, H.at(i));
  }
  long inf = ma/B + 1;
  int ans = binary_search(0, inf);
  cout << ans << endl;
}


Measured memory_bytes: 1024
#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstdio>
#include <string>

using namespace std;

int main()
{
    int A, B, X;

    cin >> A >> B >> X;

    if(X >= A && X <= A + B)
    {
        cout << "YES";
    }
    else
    {
        cout << "NO";
    }

    return 0;
}

Measured memory_bytes: 888
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int a, b;
  cin >> a >> b;
 
  if ((a + b) % 2 == 0 ) {
    cout << (a+b)/2 << endl;
  }
  else {
    cout << "IMPOSSIBLE" << endl;
  }
  
  return 0;
}

Measured memory_bytes: 256
/*input
3
1 2 2
*/
#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define endl "\n"
#define ll long long int
#define vi vector<int>
#define vll vector<ll>
#define vvi vector < vi >
#define pii pair<int,int>
#define pll pair<long long, long long>
#define mod 1000000007
#define inf 1000000000000000001
#define all(c) c.begin(),c.end()
#define mp(x,y) make_pair(x,y)
#define mem(a,val) memset(a,val,sizeof(a))
#define eb emplace_back
#define f first
#define s second
#define watch(x) cout << (#x) << " is " << (x) << endl
#define N 100002

using namespace std;
int main()
{
	fastio
	ll T=1,n,m;string str;
	// cin>>T;
	// cin.ignore(); put after cin, just b4 a getline(cin, s) to avoid getline() directly getting \n
	while(T--)
	{
		ll p=0,q=0,tmp=0,sum=0,count=0; //tmp variable
		int flag=0;
		
		cin>>n;
		ll a[n];
		for(ll i=0;i < n;i++)
			cin>>a[i];
		tmp =1;
		for (int i = 0; i < n; ++i)
		{
			if(a[i]!=tmp)
			{
				a[i]=-1;
				count++;
			}
			else
			{
				tmp++;
			}
		}
		if(count==n )
		{
			cout << -1 << endl;
		}
		else
		{
			cout << count << endl;
		}
		
	}
	return 0;
}

Measured memory_bytes: 1792
import itertools
N,M,K=map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
A_=[0]+list(itertools.accumulate(A))
B_=[0]+list(itertools.accumulate(B))

ans=0
j=M
for i in range(N+1):
    a=A_[i]
    K_a=K-a
    while (j>=0 and B_[j]>K_a):
        j-=1
    if a+B_[j]<=K:
        ans=max(ans,i+j)
print(ans)


Measured memory_bytes: 50504
#include "vector"
#include "set"
#include "map"
#include "unordered_map"
#include "string"
#include "iostream"
#include "algorithm"
#include "queue"

using namespace std;

#define ll long long
#define INF 2e9
#define MOD 998244353

typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int, int> pii;


template<typename T>
ostream& operator<<(ostream& os, const vector<T>& v) {
    bool first = true;
    for (const auto& j: v) {
        if (!first) {
            os << " ";
        }
        first = false;
        os <<j;
    }
    return os;
}

template<typename T>
istream& operator>>(istream& is, vector<T>& v) {
    for (auto& elem : v) {
        is >> elem;
    }
    return is;
}

vector<vi> g;
vi p;
vi h;
void dfs(int x, int prev) {
    p[x] = prev;
    h[x] = (prev == -1) ? 0 : h[prev] + 1;

    for (int y : g[x]) {
        if (y != prev) {
            dfs(y, x);
        }
    }
}

struct v {
    int a;
    int b;
    int c;
};

bool comp(const v& x, const v& y) {
    return x.c < y.c;
}

int nod(int a, int b) {
    if (b == 0) {
        return a;
    } else {
        return nod(b, a % b);
    }
}

void solve() {
    int n;
    cin >> n;

    int ans = 0;
    for (int i=1; i<=n; i++) {
        for (int j=1; j<=n; j++) {
            int x = nod(i, j);
            for (int k=1; k<=n; k++) {
                ans += nod(x, k);
            }
        }
    }

    cout << ans;
}

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);

    if (0) {
        int tests;
        cin >> tests;
        while (tests--) {
            solve();
            cout << "\n";
        }
    } else {
        solve();
        cout << endl;
    }

    return 0;
}

Measured memory_bytes: 3696
import java.util.Scanner;

public class Main {

	static Scanner sc = new Scanner(System.in);

	public static void main(String[] args) {
		while (true) {
			int N = sc.nextInt();
			if (N < 0) break;
			boolean[][] hor = new boolean[9][8];
			boolean[][] ver = new boolean[8][9];
			for (int i = 0; i < N; ++i) {
				char dir = sc.next().charAt(0);
				int I = sc.nextInt();
				int J = sc.nextInt();
				if (dir == 'x') {
					hor[J][I] = true;
				} else {
					ver[J][I] = true;
				}
			}
			int r = 0;
			int c = 1;
			int dr = 1;
			int dc = 1;
			boolean first = true;
			while (true) {
				int nr = r + dr;
				int nc = c + dc;
				if (!first && r + nr == 1 && c + nc == 3) {
					System.out.println("75 25");
					break;
				}
				r = nr;
				c = nc;
				boolean reflec = false;
				if (r % 2 == 0) {
					if (hor[r / 2][c / 2]) {
						dr *= -1;
						reflec = true;
					}
				} else {
					if (ver[r / 2][c / 2]) {
						dc *= -1;
						reflec = true;
					}
				}
				if ((r == 0 || c == 0 || r == 16 || c == 16) && !reflec) {
					System.out.printf("%d %d\n", c * 50, r * 50);
					break;
				}
				first = false;
			}
		}
	}
}

Measured memory_bytes: 12000
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <queue>
#include <string>
using namespace std;
typedef long long int ll;

int cnt[4];
vector<ll> vv[4];
ll sum[4][100];

int main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	int n; ll W; cin >> n >> W;
	vector<ll> w(n),v(n);
	for(int i=0;i<n;i++){
		cin >> w[i] >>v[i];
		for(int j=0;j<4;j++){
			if(w[0]+j==w[i]){
				cnt[j]++;
				vv[j].push_back(v[i]);
			}
		}
	}
	for(int i=0;i<4;i++){
		sort(vv[i].begin(),vv[i].end());
		reverse(vv[i].begin(),vv[i].end());
	}
	for(int i=0;i<4;i++){
		for(int j=1;j<=cnt[i];j++){
			sum[i][j]+=vv[i][j-1];
			sum[i][j]+=sum[i][j-1];
		}
	}
	ll ans=0;
	for(int i=0;i<=cnt[0];i++){
		for(int j=0;j<=cnt[1];j++){
			for(int k=0;k<=cnt[2];k++){
				for(int l=0;l<=cnt[3];l++){
					if((ll)(i+j+k+l)*w[0]+j+2*k+3*l<=W){
						ans=max(ans,sum[0][i]+sum[1][j]+sum[2][k]+sum[3][l]);
					}
				}
			}
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
# a+b > c AND b+c > a AND c+a > b

import itertools
triangle = 0

N = int(input())
L = [int(x) for x in input().split(" ")]


for trio in itertools.combinations(L, 3):
    if(trio[0] + trio[1] > trio[2]
    and trio[1] + trio[2] > trio[0]
    and trio[2] + trio[0] > trio[1]
    and trio[0] != trio[1] 
    and trio[1] != trio[2] 
    and trio[0] != trio[2]):
        triangle += 1

print(triangle)

Measured memory_bytes: 9196
#include<stdio.h>
int main(){
    int n,k,x,y,a;
    scanf("%d%d%d%d",&n,&k,&x,&y);
    if(n<k){
        a=n*x;
    }else{
        a=k*x;
    }
    
    if(n>k){
        a+=(y*(n-k));
    }
    printf("%d\n",a);
    return 0;
}


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

long long c[100001];

int main() {
  long long n, k; cin >> n >> k;
  while (n--) {
    int a, b; cin >> a >> b;
    c[a] += b;
  }
  int r = 0;
  while (k > 0) {
    k -= c[r++];
  }
  cout << --r << endl;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
const int mod=100000;
int dp[100][100][2][2];//0:曲がってない,1:曲がった	0:北向き,1:東向き
int main(){
	int w,h;
	while(true){
		cin>>w>>h;
		if(w==0)	return 0;
		memset(dp,0,sizeof(dp));
		dp[1][0][0][0]=dp[0][1][0][1]=1;
		for(int i=0;i<h;i++){
			for(int j=0;j<w;j++){
				int out=0;
				for(int k=0;k<2;k++)
					for(int l=0;l<2;l++)
						dp[i][j][k][l]%=mod,out+=dp[i][j][k][l];
				if(i+1<h){//縦に移動
					dp[i+1][j][0][0]+=dp[i][j][0][0]+dp[i][j][1][0];
					dp[i+1][j][1][0]+=dp[i][j][0][1];
				}
				if(j+1<w){//横に移動
					dp[i][j+1][0][1]+=dp[i][j][0][1]+dp[i][j][1][1];
					dp[i][j+1][1][1]+=dp[i][j][0][0];
				}
			}
		}
		int ans=0;
		for(int i=0;i<2;i++)
			for(int j=0;j<2;j++)	ans+=dp[h-1][w-1][i][j];
		ans%=mod;
		cout<<ans<<endl;
	}
}
					
				

Measured memory_bytes: 1324
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cmath>
#include<map>
#include<iomanip>
#include<queue>
#include<stack>
#include<time.h>
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=1;i<=n;i++)
#define ggr getchar();getchar();return 0;
#define prique priority_queue
constexpr auto mod = 1000000007;
#define inf 1e15
#define key 1e9
using namespace std;
typedef pair<int, int>P;
template<class T> inline void chmax(T& a, T b) {
	a = std::max(a, b);
}
template<class T> inline void chmin(T& a, T b) {
	a = std::min(a, b);
}
//combination(Nが小さい時はこれを使う)
const int MAX = 330000;
int fac[MAX], finv[MAX], inv[MAX];
void COMinit() {
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;
	for (int i = 2; i < MAX; i++) {
		fac[i] = fac[i - 1] * i % mod;
		inv[i] = mod - inv[mod % i] * (mod / i) % mod;
		finv[i] = finv[i - 1] * inv[i] % mod;
	}
}
int COMB(int n, int k) {
	if (n < k) return 0;
	if (n < 0 || k < 0) return 0;
	return fac[n] * (finv[k] * finv[n - k] % mod) % mod;
}

bool prime(int n) {
	int cnt = 0;
	for (int i = 1; i <= sqrt(n); i++) {
		if (n % i == 0)cnt++;
	}
	if (cnt != 1)return false;
	else return n != 1;
}
int gcd(int x, int y) {
	if (y == 0)return x;
	return gcd(y, x % y);
}
int lcm(int x, int y) {
	return x / gcd(x, y) * y;
}

//繰り返し二乗法（Nが大きい時の場合のcombination)
int mod_pow(int x, int y, int m) {
	int res = 1;
	while (y) {
		if (y & 1) {
			res = res * x % m;
		}
		x = x * x % m;
		y >>= 1;
	}
	return res;
}
int kai(int x, int y) {
	int res = 1;
	for (int i = x - y + 1; i <= x; i++) {
		res *= (i % mod); res %= mod;
	}
	return res;
}
int comb(int x, int y) {
	if (y > x)return 0;
	return kai(x, y) * mod_pow(kai(y, y), mod - 2, mod) % mod;
}
//UnionFind
class UnionFind {
protected:
	int* par, * rank, * size;
public:
	UnionFind(unsigned int size) {
		par = new int[size];
		rank = new int[size];
		this->size = new int[size];
		rep(i, size) {
			par[i] = i;
			rank[i] = 0;
			this->size[i] = 1;
		}
	}
	int find(int n) {
		if (par[n] == n)return n;
		return par[n] = find(par[n]);
	}
	void unite(int n, int m) {
		n = find(n);
		m = find(m);
		if (n == m)return;
		if (rank[n] < rank[m]) {
			par[n] = m;
			size[m] += size[n];
		}
		else {
			par[m] = n;
			size[n] += size[m];
			if (rank[n] == rank[m])rank[n]++;
		}
	}
	bool same(int n, int m) {
		return find(n) == find(m);
	}
	int getsize(int n) {
		return size[find(n)];
	}
};
int dight(int n) {
	int ans = 1;
	while (n >= 10) {
		n /= 10;
		ans++;
	}
	return ans;
}
int dight_sum(int n) {
	int sum = 0;
	rep(i, 20)sum += (n % (int)pow(10, i + 1)) / (pow(10, i));
	return sum;
}
signed main() {
	int a, b;
	cin >> a >> b;
	if (a <= 9 && b <= 9)cout << a * b << endl;
	else puts("-1");
	ggr
}


Measured memory_bytes: 256
def combination(n, r):
    if r > n-r:
        r = n-r
    a = 1
    for i in range(n, n-r, -1):
        a = a * i
    d = 1
    for i in range(1, r+1):
        d = d*i
    return a//d


def generate_prime_map(n):
    m = {}
    b, e = 2, 0
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            m[b] = e
        b, e = b + 1, 0
    if n > 1:
        m[n] = 1
    return m


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

m = generate_prime_map(M)

ans = 1
mod = 10**9+7
for v in m.values():
    ans *= combination(v+N-1, v)
    ans %= mod
print(ans)


Measured memory_bytes: 3064
k,n = map(int, input().split())
lst = list(map(int, input().split()))

maxDis = (k-lst[-1]) + lst[0]
for i in range(n-1):
  if lst[i+1] - lst[i] > maxDis:
    maxDis = lst[i+1] - lst[i]
print(k-maxDis)

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

ll fact(ll n)
{
    ll f=1;
    for(ll i=1;i<=n;i++) f = f*i;
    return f;
}

int main()
{
    ll n,a=0,b=0;
    cin>>n;
    vector<ll> p(n+1),q(n+1);
    set<ll> s;
    for(ll i=1;i<=n;i++)
    {
        cin>>p[i];
        s.insert(i);
    }
    for(ll i=1;i<=n;i++) cin>>q[i];
    for(ll i=1;i<=n;i++)
    {
        ll tmp = 1,d=p[i];
        auto it = s.begin();
        while(it!=s.end())
        {
            if(d== *it) break;
            tmp++;
            it++;
        } 
        if(tmp!=1)
        {
            ll eachelrepeat = fact(n-i+1)/(n-i+1);
            a += ((tmp-1)*eachelrepeat); 
        }
        s.erase(p[i]);
    }
    for(ll i=1;i<=n;i++) s.insert(i);
    for(ll i=1;i<=n;i++)
    {
        ll tmp = 1,d=q[i];
        auto it = s.begin();
        while(it!=s.end())
        {
            if(d== *it) break;
            tmp++;
            it++;
        } 
        if(tmp!=1)
        {
            ll eachelrepeat = fact(n-i+1)/(n-i+1);
            b += ((tmp-1)*eachelrepeat); 
        }
        s.erase(q[i]);
    }
    a++;b++;
  //  cout<<a<<" "<<b<<endl;
    cout<<abs(a-b)<<endl;
}

Measured memory_bytes: 256
$;=''
board = $<.map(&:chomp).map(&:split).map{|a| [?.] + a + [?.]}
board.unshift [?.] * 10
board << [?.] * 10

def to_be_turned(board, i, j, di, dj, c)
	count = 0
	loop do 
		i += di
		j += dj
		return count if board[i][j] == c
		return 0 if board[i][j] == ?.
		count += 1
	end
end

def play(board, i, j, c)
	[-1, 0, 1].repeated_permutation(2).map { |di, dj|
		next if di == 0 && dj == 0
		turn(board, i, j, di, dj, c)
	}
end

def turn(board, i, j, di, dj, c)
	board[i][j] = c
	loop do 
		i += di
		j += dj
		return if board[i][j] == ?.
		if board[i][j] == c
			loop do
				i -= di
				j -= dj
				return if board[i][j] == c
				board[i][j] = c
			end
		end
	end
end

c = ?o
skip = false
loop do
	max = 0
	max_by = nil
	ord = (1..8).to_a
	ord.reverse! if c == ?x
	ord.each do |i|
		ord.each do |j|
			next unless board[i][j] == ?.
			x = [-1, 0, 1].repeated_permutation(2).map { |di, dj|
				next 0 if di == 0 && dj == 0
				to_be_turned(board, i, j, di, dj, c)
			}.inject(:+)
			if x > max
				max = x
				max_by = [i, j]
			end
		end
	end

	if max_by
		play(board, *max_by, c)
		skip = false
	elsif skip
		break
	else
		skip = true
	end
	c = (c == ?o ? ?x : ?o)
end

board.shift
board.pop
board.each do |a|
	a.pop
	a.shift
end
puts board.map(&:join)

Measured memory_bytes: 8876
#include<bits/stdc++.h>
#define rep(i,N) for(ll (i)=0;(i)<(N);(i)++)
#define chmax(x,y) x=max(x,y)
#define chmin(x,y) x=min(x,y)
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int mod = 1000000007;

int main() {
  int n, q;
  cin >> n >> q;
  string ac = "AC";
  string s;
  cin >> s;
  vector<int> sum(n + 1);
  int cur = 0;
  for (int i = 1; i < n; ++i) {
    if(s[i] == ac[1] && s[i - 1] == ac[0]) cur++;
    sum[i + 1] = cur;
  }
  rep(i, q) {
    int l, r;
    cin >> l >> r;
    --l; --r;
    
    int ans = sum[r + 1] - sum[l + 1];
    cout << ans << endl;
  }
}

Measured memory_bytes: 1408
r, g, b, n = gets.split.map(&:to_i)
puts(
  (0..n).step(r).flat_map do |i|
    (0..(n - i)).step(g).map { |j| (n - (i + j)) % b == 0 ? 1 : 0 }
  end.inject(:+)
)


Measured memory_bytes: 56940
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApp15
{
    class Class45
    {
        static void Main()
        {
            int n = int.Parse(Console.ReadLine());
            var a = Console.ReadLine().Split().Select(int.Parse).ToArray();

            int count = 1;
            for(int i = 0; i < n; i++)
            {
                if (a[i] == count) count++;
            }
            count--;
            if (count == 0) Console.WriteLine(-1);
            else Console.WriteLine(n - count);
        }
    }
}


Measured memory_bytes: 35676
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>

using namespace std;

//repetition
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define CLR(a) memset((a), 0 ,sizeof(a))
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

//constants
const double EPS = 1e-10;
const double PI  = acos(-1.0);
const int INF = 1<<28;


int main(int argc, char **argv) {
    int N;
    cin >> N;
    vector<long long> A, B;
    A.resize(N, 0);
    B.resize(N, 0);
    REP(i, N)
        cin >> A[i] >> B[i];

    long long ans = 0;
    REP(i, N){
        if ( (A[N-i-1]+ans) % B[N-1-i] == 0 )
            continue;
        else{
            ans += B[N-i-1] - ((A[N-i-1]+ans) % B[N-i-1]);
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 1792
import java.util.*;

public class Main {

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

        int a = sc.nextInt();
        int b = sc.nextInt();

        int count = 0;

        if(b > 1){
            count += Math.ceil((b - a) / (a - 1.0)) + 1;
        }
        

        System.out.println(count);
    }
}

Measured memory_bytes: 23380
using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
	static void Main(string[] args)
	{
		var inputs = Console.ReadLine().Split(' ').Select(p => int.Parse(p)).ToArray();
		int result = Calc(inputs[0]) + Calc(inputs[1]);
		Console.WriteLine(result.ToString());
	}

	private static int Calc(int num)
	{
		return (num * (num - 1))/2;
	}
}


Measured memory_bytes: 11348
V,E = map(int,input().split())
cost_matrix = [[float('inf')]*V for _ in range(V)]
for i in range(V):
    cost_matrix[i][i] = 0
for i in range(E):
    start,end,cost = map(int,input().split())
    cost_matrix[start][end] = cost
for stop in range(V):
    for start in range(V):
        for end in range(V): 
            cost_matrix[start][end] = min(cost_matrix[start][end],cost_matrix[start][stop]+cost_matrix[stop][end])
is_negative = False
for start in range(V):
    for end in range(V):
        if cost_matrix[start][end] < 0 and start == end:
            is_negative = True
        elif cost_matrix[start][end] == float('inf'):
            cost_matrix[start][end] = 'INF'
if is_negative:
    print('NEGATIVE CYCLE')
else:
    for start in range(V):
        res = list(map(str,cost_matrix[start]))
        print(' '.join(res))





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

using namespace std;
vector<long long> factors;
#define ll long long


#define pii pair<int,int>
#define pll pair<ll,ll>
#define _ <<'\n'
#define __ << ' '
#define all(x) (x).begin(), (x).end()
#define gcd __gcd
int IT_MAX = 1 << 17;
int MOD = 1000000007;
const int INF = 0x3f3f3f3f;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
const double PI = acos(-1);
const double ERR = 1e-10;
#define szz(x) (int)(x).size()
#define IOS ios_base::sync_with_stdio(false); cout.tie(0);cin.tie(0);
#define flush fflush(stdout)

template<typename T>
int BS(vector<T> &mas, T val)
{
	int l, r;
	l = 0;
	r = mas.size() - 1;
	while (r - l > 1)
	{
		int mid = l + (r - l) / 2;
		if (mas[mid] < val)
		{
			l = mid;
		} else
			r = mid;
	}
	if (mas[r] == val)
		return r;
	if (mas[l] == val)
		return l;
	return -1;
}

template<typename T>
int UBS(vector<T> &mas, T val)
{
	int l, r;
	l = 0;
	r = mas.size() - 1;
	while (r - l > 1)
	{
		int mid = l + (r - l) / 2;
		if (mas[mid] < val)
		{
			l = mid;
		} else
			r = mid;
	}

	if (mas[l] >= val)
		return l;
	if (mas[r] >= val)
		return r;
	return -1;
}

ll mod(ll a, ll m)
{ return (a + (abs(a) / m) * m + m) % m; }


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

	vector<ll> dist;
	int n,m;
	cin >> n>> m;
	if( n >= m)
	{
		cout << 0;
		return 0;
	}
	vector<ll> x(m);
	for(int i = 0; i < m; ++i){
		cin >> x[i];
	}
	sort(all(x));
	for(int i = 1;i < m; ++i){
		dist.push_back(x[i] - x[i - 1]);
	}
	sort(all(dist));
	ll dsum = 0;
	for(int i = 0; i <n - 1; ++i){
		dsum += dist[dist.size() - 1 - i] - 1;
	}
	cout << x[x.size() - 1] - x[0] + 1 - n - dsum;


	return 0;
}

Measured memory_bytes: 2168
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i, a, b) for (int i = (a); i < (int)(b); ++i)
#define rrep(i, a, b) for (int i = ((int)a) - 1; i >= ((int)a); --i)
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
using pii = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;

void dump_impl(string s) {}
template <class H, class... T>
void dump_impl(string s, H head, T... tail) {
    int p = 0;
    rep(i, 0, sz(s)) {
        char x = s[i];
        if (p == 0 && x == ',') {
            cerr << "=" << head << ", ";
            dump_impl(s.substr(i + 1), tail...);
            return;
        } else {
            cerr << x;
            if (x == '(') p++;
            if (x == ')') p--;
        }
    }
}
#ifdef LOCAL
#define dump(...) do { cerr << "\x1b[33;1m"; dump_impl(#__VA_ARGS__ ",", __VA_ARGS__); cerr << "\x1b[0m" << endl; } while (0) 
#else
#define dump(...)
#endif

constexpr int DY[8] = {-1, 0, 1, 0, -1, 1, 1, -1};
constexpr int DX[8] = {0, 1, 0, -1, 1, 1, -1, -1};

struct State {
    string s;
    int i;
    char next() {
        char ret = check();
        i++;
        return ret;
    }
    char check() {
        if (sz(s) == i) {
            return '$';
        }
        return s[i];
    }
};

int neg(int a) {
    if (a == 0) return 2;
    if (a == 1) return 1;
    if (a == 2) return 0;
    assert(false);
}
int mul(int a, int b) {
    return min(a, b);
}
int add(int a, int b) {
    return max(a, b);
}

int P, Q, R;

int num(State &st) {
    char x = st.next();
    if ('0' <= x && x <= '2') return x - '0';
    if (x == 'P') return P;
    if (x == 'Q') return Q;
    if (x == 'R') return R;
    assert(false);
}
int formula(State &st) {
    char x = st.check();
    if (x == '-') {
        st.next();
        return neg(formula(st));
    } else if (x == '(') {
        st.next();
        int left = formula(st);
        char op = st.next();
        int right = formula(st);
        x = st.next();
        assert(x == ')');
        if (op == '*') {
            return mul(left, right);
        } else {
            return add(left, right);
        }
    } else {
        return num(st);
    }
}

void solve(string s) {
    int ans = 0;
    rep(p, 0, 3) {
        rep(q, 0, 3) {
            rep(r, 0, 3) {
                P = p, Q = q, R = r;
                State st = {s, 0};
                int res = formula(st);
                if (res == 2) {
                    ans++;
                }
            }
        }
    }
    cout << ans << endl;
}

signed main() {
    while (1) {
        string s;
        cin >> s;
        if (s == ".") break;
        solve(s);
    }
}


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

const long double EPS = 1e-10;
const long long INF = 1e18;
const long double PI = acos(-1.0L);

const int MAX_N = 105;
const int MAX_V = 100100;
ll dp[MAX_N][MAX_V];

int main() {
  int N, W;
  cin >> N >> W;
  vector<int> w(N, 0), v(N, 0);
  rep(i, N) cin >> w[i] >> v[i];
  rep(i, MAX_N) rep(j, MAX_V) dp[i][j] = INF;
  dp[0][0] = 0;

  rep(i, N) {
    rep(j, MAX_V) {
      if (j - v[i] >= 0) {
        dp[i + 1][j] = min(dp[i + 1][j], dp[i][j - v[i]] + w[i]);
      }
      dp[i + 1][j] = min(dp[i + 1][j], dp[i][j]);
    }
  }

  ll ans = 0;
  rep(i, MAX_V) { 
      if (dp[N][i] <= W) ans = i;
  }
  cout << ans << endl;

  return 0;
}

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

#define rep(i,n) for(int i=0; i<(n); i++)
#define reps(i,x,n) for(int i=x; i<(n); i++)
#define rrep(i,n) for(int i=(n)-1; i>=0; i--)
#define all(X) (X).begin(),(X).end()
#define X first
#define Y second
#define pb push_back
#define eb emplace_back

using namespace std;
typedef long long int ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }

template<class A, size_t N, class T> void Fill(A (&a)[N], const T &v){ fill( (T*)a, (T*)(a+N), v ); }

const ll INF = 1e9+7;


ll sum_v[2005][2005] = {};
ll sum_e[2][2005][2005] = {};
int main(){
	//ios_base::sync_with_stdio(false);
	int N, M, Q, ans=0;
	string S[2005];

	cin >> N >> M >> Q;
	rep(i,N) cin >> S[i];

	rep(i,N) rep(j,M){
		sum_v[i+1][j+1] = sum_v[i+1][j] + sum_v[i][j+1] - sum_v[i][j];
		rep(k,2) sum_e[k][i+1][j+1] = sum_e[k][i+1][j] + sum_e[k][i][j+1] - sum_e[k][i][j];
		if( S[i][j] == '1' ){
			sum_v[i+1][j+1]++;
			if( i>0 && S[i-1][j] == '1' ) sum_e[0][i+1][j+1]++;
			if( j>0 && S[i][j-1] == '1' ) sum_e[1][i+1][j+1]++;
		}
	}

	auto f = [&](ll sum[2005][2005], int x1, int y1, int x2, int y2){
		return sum[x2][y2] - sum[x1][y2] - sum[x2][y1] + sum[x1][y1];
	};

	rep(i,Q){
		int x1, y1, x2, y2;
		cin >> x1 >> y1 >> x2 >> y2;
		int v = f(sum_v, x1-1, y1-1, x2, y2);
		int e0 = f(sum_e[0], x1, y1-1, x2, y2);
		int e1 = f(sum_e[1], x1-1, y1, x2, y2);
		//cout << v << " " << e0 << " " << e1 << endl;
		cout << v - e0 - e1 << endl;
	}

	return 0;
}

Measured memory_bytes: 100096
// Devarshi

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

#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define pb push_back
#define ll long long
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define rep(i,n) for(i=0;i<n;i++)
#define forn(i, n) for (ll i = 0; i < (ll)(n); ++i)
#define for1(i, n) for (ll i = 1; i <= (ll)(n); ++i)
#define ford(i, n) for (ll i = (ll)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (ll i = (ll)(a); i <= (ll)(b); ++i)
#define fora(it,x) for(auto it:x)
#define PI 3.14159265
#define sync ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

typedef pair<ll, ll> pii;
typedef vector<ll> vi;
typedef vector<pii> vpi;
typedef vector<vi> vvi;
typedef long long i64;
typedef vector<i64> vi64;
typedef vector<vi64> vvi64;
typedef pair<i64, i64> pi64;
typedef long double ld;

template<class T> bool uin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool uax(T &a, T b) { return a < b ? (a = b, true) : false; }

const int maxn=1000001;

string convo(string s){
    int rem=6-s.size();
    while(rem--) s='0'+s;
    return s;
}

int main(){

sync

int n,m;
cin>>n>>m;

vector<string> ans(m);
set<int> s[n+1];
int m1=m;
map<pii,int> mapp;
int cnt=0;
while(m1--){
int x,y;
cin>>x>>y;
mapp[mp(x,y)] = cnt;
s[x].insert(y);
cnt++;
}
//vector<string> ans(m);
fore(i,1,n){
  int cnt=1;
  for(auto it:s[i]){
    string s1,s2;
    s1=to_string(i);
    s1=convo(s1);
    s2=to_string(cnt);
    s2=convo(s2);
    ans[mapp[mp(i,it)]]=s1+s2;
    cnt++;
  }
}
fore(i,0,m-1){
  cout<<ans[i]<<endl;
}
return 0;
}


Measured memory_bytes: 22656
class PriorityQueue
  def initialize(&comp)
    @heap = []
    @node_num = 0
    if !block_given?
      @comp = Proc.new { |x, y| x <= y }
    else
      @comp = comp
    end
  end
  attr_reader :heap

  def push(x)
    i = @node_num # 自分のノード番号
    @node_num += 1
    while i > 0
      par = (i - 1) / 2 # 親のノード番号
      break if @comp.call(@heap[par], x) # 逆転してないなら抜ける
      # 親ノードを下ろして自分を上に
      @heap[i] = @heap[par]
      i = par
    end
    @heap[i] = x
  end

  alias_method(:<<, :push)

  def pop
    # 最(小|大)値
    ret = @heap[0]
    # 根にもってくる値
    @node_num -= 1
    x = @heap[@node_num]
    # 根から下ろしていく
    i = 0
    while i * 2 + 1 < @node_num
      # 子どうしを比較
      a, b = i * 2 + 1, i * 2 + 2
      a = b if b < @node_num && !@comp.call(@heap[a], @heap[b])
      break if @comp.call(x, @heap[a])
      @heap[i] = @heap[a]
      i = a
    end
    @heap[i] = x
    return ret
  end

  def get
    @node_num == 0 ? nil : @heap[0]
  end

  def empty?
    return get.nil?
  end
end

n, m = gets.split.map(&:to_i)
a = gets.split.map(&:to_i)
q = PriorityQueue.new { |x, y| x > y }
a.each do |e|
  q.push e
end

m.times do
  q.push(q.pop / 2)
end
puts q.heap.inject(:+)


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

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

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

int main()
{
	char s[4], t[4];
	int cnt = 0;
	cin >> s;
	cin >> t;

	for (int i = 0; i < 3; i++)
	{
		if (s[i] == t[i]) {
			cnt++;
		}
	}

	cout << cnt << "\n";

	return 0;
}

Measured memory_bytes: 256