akhauriyash/Code-Regression huggingface dataset:
#[allow(unused_imports)]
use std::cmp;
#[allow(unused_imports)]
use std::collections::*;
#[allow(unused_imports)]
use std::vec::Vec;

macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    input!{
        h: usize,
        w: usize,
        a: [chars;h],
    }
    let mut passed = vec![vec![false; w]; h];
    passed[0][0] = true;
    'outer: for i in 0..h {
        for j in 0..w {
            if i == h - 1 && j == w - 1 {
                break 'outer;
            }
            if a[i][j] == '.' {
                continue;
            }
            if !passed[i][j] {
                println!("Impossible");
                return;
            }
            if i < h - 1 && j < w - 1 {
                if a[i + 1][j] == '#' && a[i][j + 1] != '#' {
                    passed[i + 1][j] = true;
                    continue;
                } else if a[i + 1][j] != '#' && a[i][j + 1] == '#' {
                    passed[i][j + 1] = true;
                    continue;
                } else {
                    println!("Impossible");
                    return;
                }
            } else if i < h - 1 {
                if a[i + 1][j] == '#' {
                    passed[i + 1][j] = true;
                    continue;
                } else {
                    println!("Impossible");
                    return;
                }
            } else if j < w - 1 {
                if a[i][j + 1] == '#' {
                    passed[i][j + 1] = true;
                    continue;
                } else {
                    println!("Impossible");
                    return;
                }
            }
        }
    }
    println!("Possible");
}


Measured memory_bytes: 4352
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,flag=0,a=0,b=0;
    cin>>n;
    flag=0;
    for(int i=1; i<10; i++)
    {
        if(n%i==0)
        {
            a=n/i;
            b=i;

            if((a>=1&&a<=9)&&(b>=1&&b<=9))
            {
                cout<<"Yes"<<endl;
                flag=1;
                break;

            }
        }
        else continue;
    }
    if(flag==0) cout<<"No"<<endl;

}


Measured memory_bytes: 3640
#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
typedef long long ll;
long long GCD(long long a, long long b) { return b?GCD(b, a%b):a; }
long long LCM(long long a, long long b) { return a/GCD(a, b)*b; }

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

  // for prime mod
  mint inv() const { return pow(mod-2);}
  mint& operator/=(const mint a) { return *this *= a.inv();}
  mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}

// combination mod prime
struct combination {
  vector<mint> fact, ifact;
  combination(int n):fact(n+1),ifact(n+1) {
    assert(n < mod);
    fact[0] = 1;
    for (int i = 1; i <= n; ++i) fact[i] = fact[i-1]*i;
    ifact[n] = fact[n].inv();
    for (int i = n; i >= 1; --i) ifact[i-1] = ifact[i]*i;
  }
  mint operator()(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n]*ifact[k]*ifact[n-k];
  }
};

int n, k;

int main() {
    cin >> n >> k;
    vector<int> A(n);
    for(int i = 0; i < n; ++i) cin >> A.at(i);
    sort(A.begin(), A.end());

    combination com(n+5);

    mint ans = 0;
    for(int i = 0; i < n; ++i) {
        mint now = com(i, k-1);
        ans += now*A[i];
    }
    reverse(A.begin(), A.end());
    for(int i = 0; i < n; ++i) {
        mint now = com(i, k-1);
        ans -= now*A[i];
    }

    cout << ans.x << endl;
}

Measured memory_bytes: 2176
s = input()
t = input()
ls = len(s)
lt = len(t)
dp = [[0] * (ls+1) for _ in range(lt+1)]

for i in range(1, lt+1):
    tt = t[i-1]
    for j in range(1, ls+1):
        ts = s[j-1]
        if ts == tt:
            dp[i][j] = dp[i-1][j-1] + 1
        else:
            dp[i][j] = max(dp[i-1][j], dp[i][j-1])

ret = []
while ls > 0 and lt > 0:
    if dp[lt][ls] == dp[lt][ls-1]:
        ls -= 1
    elif dp[lt][ls] == dp[lt-1][ls]:
        lt -= 1
    else:
        ret.append(s[ls-1])
        ls -= 1
        lt -= 1

ret.reverse()
print("".join(ret))


Measured memory_bytes: 112220
from collections import deque

def solve(A, K):
    a = deque() # 繰り返し部分
    seen = [False for _ in range(len(A))] # 一度見たかどうか
    cur = 0
    while True:
        # 一度通った頂点を見つけたときの処理
        if seen[cur]:
            while a[0] != cur:
                # 最初の余計な数手分を除去する
                K -= 1
                a.popleft()

                # K が限界になったらリターン
                if K == 0:
                    return a[0] + 1
            break

        # 最初は愚直にシミュレーションしつつ、履歴をメモしていく
        a.append(cur)
        seen[cur] = True
        cur = A[cur]        
    return a[K % len(a)] + 1

N, K = map(int, input().split())
A = list(map(int, input().split()))
A = [v - 1 for v in A]
print(solve(A, K))

Measured memory_bytes: 33788
#line 1 "/mnt/c/Users/leafc/dev/compro/lib/template.hpp"


#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; i++)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define ALL(v) (v).begin(), (v).end()
#define coutd(n) cout << fixed << setprecision(n)
#define ll long long int
#define vl vector<ll>
#define vi vector<int>
#define MM << " " <<

using namespace std;

template <class T> void say(bool val, T yes = "Yes", T no = "No") { cout << (val ? yes : no) << "\n"; }

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

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


#line 2 "nomura2020_a.cpp"

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

  int h1, m1, h2, m2, k;
  cin >> h1 >> m1 >> h2 >> m2 >> k;
  int s = h1 * 60 + m1;
  int e = h2 * 60 + m2;
  cout << e - s - k << endl;
}


Measured memory_bytes: 3692
n = int(input())
s = input()
cw = 0
lol = 0
for i in s:
    if i == 'W':
        cw += 1
for i in range(n-1,n-cw-1,-1):
    if s[i] == 'W':
        lol += 1
print(abs(lol-cw))

Measured memory_bytes: 9332
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int main() {
    string s;
    vector<int> a(128,0);
    bool b =true;
    cin >>s;
    for(int i=0;i<s.size();i++){
        a[s[i]]=1;
    }
    for(char j='a';j<='z';j++){
        if(a[j]==0){  
            cout << j <<endl;
            b =false;
            break;
        }
    }
    if(b==true) cout <<"None"<<endl;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<n; i++)
#define PI 3.14159265359
#define INF 1000100100
#define all(x) (x).begin(),(x).end()
typedef long long ll;
#define P pair<int, int>
using namespace std;

int main(){
    int n; cin >> n;
    vector<P> task(n);
    rep(i,n) cin >> task[i].second >> task[i].first;
    sort(all(task));
    ll now=0;
    rep(i,n){
        now+=task[i].second;
        if(now>task[i].first){
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
return 0;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = a; i < (b); i++)
#define rrep(i, a, b) for (int i = a; i >= (b); i--)
#define all(x) (x).begin(), (x).end()
using namespace std;
using ll = long long;
using P = pair<int, int>;
template <class T>
inline bool chmin(T& a, T b) {
   if (a > b) {
      a = b;
      return true;
   }
   return false;
}
template <class T>
inline bool chmax(T& a, T b) {
   if (a < b) {
      a = b;
      return true;
   }
   return false;
}
void hr() {
   cerr << "--------------" << endl;
}
const int INF = 1001001001;
const int MOD = 1000000007;
// const int MOD = 998244353;

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

   int n, m;
   cin >> n >> m;
   vector<int> h(n);
   rep(i, 0, n) cin >> h[i];
   vector<bool> ok(n, true);
   rep(i, 0, m) {
      int a, b;
      cin >> a >> b;
      a--, b--;
      if (h[a] <= h[b]) ok[a] = false;
      if (h[b] <= h[a]) ok[b] = false;
   }
   int ans = 0;
   rep(i, 0, n) if (ok[i]) ans++;
   cout << ans << endl;
   return 0;
}

Measured memory_bytes: 3724
def countInn(n, L):
  numInn = 1
  mainHurdle = L[0]
  hurdle = mainHurdle
  for i in range(1, n):
    currentH = L[i]
    if currentH < mainHurdle or currentH < hurdle:
      continue
    numInn += 1
    hurdle = currentH
  print(numInn)
  
n = int(input())
a = list(map(int, input().split()))
countInn(n, a)


Measured memory_bytes: 3060
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <map>
#include <numeric>
#include <string>
#include <cmath>
#include <iomanip>
#include <queue>
#include <list>
#include <stack>
#include <cctype>
#include <cmath>

using namespace std;

/* typedef */

typedef long long ll;

/* constant */

const int INF = 1 << 30;
const int MAX = 1000000;
const int mod = 1000000007;
const double pi = 3.141592653589;
/* global variables */

/* function */

/* main */
int main(){

    string S; cin >> S;
    for (int i = 0; i < S.size(); i++) 
        cout << 'x';
    cout << '\n';
    return 0;
}


Measured memory_bytes: 256
import Foundation

let N = Int(readLine()!)!
let entryNumber = readLine()!.components(separatedBy: " ").map{ Int($0)! }

var evenNumbers:[Int] = []
var j = 0

for i in 0...N - 1 {
    if entryNumber[i] % 2 == 0 {
        evenNumbers.append(entryNumber[i])
        if evenNumbers[j] % 3 != 0 && evenNumbers[j] % 5 != 0 {
            print("DENIED")
            break
        }
        j += 1
    }
    if i == N - 1 {
        print("APPROVED")
    }
}

Measured memory_bytes: 14072
#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;


const int INF = 1e+9;

// 
long long check( int num, vector<int>& a, vector<int>& ps )
{
    int N = a.size();
    long long ret = 0, now = 0;
    unordered_map<int,int> count;

    count[0] = 1;
    for( int i = 0; i < N; ++i ){
        ps[i] = (i? ps[i-1]: 0) + (a[i]<=num? 1: -1);
        if( a[i] <= num ) now += count[ps[i]-1];
        else now -= count[ps[i]];
        ++count[ps[i]];
        ret += now;
    }

    return ret;
}


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


    vector<int> ps(N);

    // 中央値になる値を二分探索
    long long l = 0, r = INF;
    long long want = 1LL*(N+1)*N/4 + 1;
    while(r-l > 1){
        int c = (l+r)/2;
        if( check(c, a, ps) >= want ) r = c;
        else l = c;
    }
    cout << r << endl;
    return 0;
}

Measured memory_bytes: 5192
#include <bits/stdc++.h>
using namespace std;
int main(){
  int H,W;cin>>H>>W;long long int DP[H+1][W+1];
  for(int i=0;i<=H;i++)DP[i][0]=0;
  for(int i=0;i<=W;i++)DP[0][i]=0;
  DP[0][1]=1;char x;
  for(int i=1;i<=H;i++)for(int j=1;j<=W;j++){
    cin>>x;
    if(x=='#')DP[i][j]=0;
    else DP[i][j]=(DP[i-1][j]+DP[i][j-1])%1000000007;
  }
  cout<<DP[H][W]<<endl;
}

Measured memory_bytes: 8064
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <map>
#include <unordered_map>
#include <set>
#include <queue>
using namespace std;
#define ALL(x) (x).begin(),(x).end()
#define SZ(x) int((x).size())
#define OUT(x) cout << (x) << endl
typedef long long ll;
typedef vector<int> V;
typedef vector<vector<int>> VV;
typedef pair<int, int> P;
typedef map<string, int> M;
typedef unordered_map<int, int> HM;
typedef set<int> S;
typedef multiset<int> MS;
typedef queue<int> Q;

int main(){
    int n,T; cin>>n>>T;
    V t(n);
    for(int i=0; i<n; i++)
        cin>>t[i];
    ll minus = 0;
    for(int i=1; i<n; i++){
        if(t[i]-t[i-1] > T){
            minus += t[i]-t[i-1]-T;
        }
    }
    cout << t[n-1]-minus+T << endl;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
 
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define rep(i, n)  for(int i=0;i<(n);++i)
#define REPr(i, n) for(int i=(n)-1;i>=0; --i)
#define FORq(i, m, n) for(int i = (m);i <= (n);++i)
#define FORqr(i, m, n) for(int i = (n);i >=(m);--i)
#define PB push_back
#define MP make_pair
#define DEBUG printf("%s\n","debug")
#define fst first
#define snd second
#define SIN(x, S) (S.count(x) != 0)
#define M0(x) memset(x,0,sizeof(x))
#define FILL(x, y) memset(x,y,sizeof(x))
#define MM(x) memset(x,-1,sizeof(x))
#define ALL(x) (x).begin(),(x).end()
using namespace std;
typedef pair<int, int> PII;
typedef pair<long long, long long> PLL;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<long long> VL;
typedef long long ll;
typedef long long integer;
///////////////////////////////////////////////
/* (๑╹◡╹) */
ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll MOD = 1000000007;
template<class T>
inline bool chmin(T &a, T b) {
	if (a > b) {
		a = b;
		return true;
	}
	return false;
}
 /* (๑╹◡╹)(๑╹◡╹)(๑╹◡╹)*/
template<class T>
inline bool chmax(T &a, T b) {
	if (a < b) {
		a = b;
		return true;
	}
	return false;
}
/* (๑╹◡╹)(๑╹◡╹)(๑╹◡╹)(๑╹◡╹)(๑╹◡╹)(๑╹◡╹) */
///////////////////////////////////////////////
const int MAX = 510000;

long long 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;
    }
}

// 二項係数計算
long long COM(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;
}
 



int main() {
	ll N,K; cin >> N >> K;
	vector<ll> A;
	for (int i = 0; i < N; i++)
	{
		ll a; cin >> a;
		A.PB(a);
	}
	
	ll c = 0;//Aの中での転倒数
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			if(j>i and A[i]>A[j]){c++; c = c % MOD;
			}
		}
	}
	ll d = 0;//Aの外での転倒数
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			if(A[i]>A[j] and i != j){d++; d = d % MOD;
			}
		}
	}
	K = K % MOD;
	ll ans = (K * c) % MOD + (d % MOD) * (((K * (K-1)) / 2) % MOD);
	ans = ans % MOD;
	cout << ans << endl;
	}


Measured memory_bytes: 256
#include <algorithm>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <tuple>
#include <vector>
using namespace std;
typedef long long ll;
ll const INF = 1LL << 60;

int main() {
  ll N, A, B;
  cin >> N >> A >> B;
  ll ans;
  if (B % 2 != A % 2)
    ans = min(A - 1, N - B) + 1 + (B - A - 1) / 2;
  else
    ans = (B - A) / 2;
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3588
#include <bits/stdc++.h>
using namespace std;
#define ll int64_t
const ll N = 3e5 + 5, M = 1e9 + 5;
ll dp[N];
int main()
{
	ios::sync_with_stdio(0), cin.tie(0);
	ll n, W, w, v;
	cin >> n >> W;
	for(ll i = 1; i <= n; i++)
	{
		cin >> w >> v;
		for(ll j = W; j >= w; j--) dp[j] = max(dp[j], v + dp[j - w]);
	}
	cout << dp[W];
}

Measured memory_bytes: 1024
from functools import lru_cache

@lru_cache(102400)
def t(n, u):
    if u <= 0:
        return 1
    ans = 0
    for k1 in range(0, n + 1):
        for k2 in range(k1 + 1, (n - k1) + 1):
            ans += (k2 - k1) * t(n - k1 - k2, u - 1)
    return ans

def tl(n, u):
    return list(map(lambda x: t(x, u), range(n)))

def d(x):
    return [x[i + 1] - x[i] for i in range(len(x) - 1)]

l = tl(80, 5)
sp = [[], []]

for j in range(2):
    sp[j] = [(i, l[i]) for i in range(j, len(l), 2)]
    # u = [l[i] for i in range(j, len(l), 2)]
    # for k in range(30):
    #     print(u)
    #     u = d(u)

mo = 10 ** 9 + 7

def rev(x):
    global mo
    return pow(x, mo - 2, mo)

def solveKth(s, k):
    global mo
    for u, v in s:
        if u == k:
            return v % mo
    def l(j):
        global mo
        ans = 1
        for i in range(len(s)):
            if i != j:
                ans = ans * (k - s[i][0]) * rev(s[j][0] - s[i][0]) % mo
        return ans
    ans = 0
    for j in range(len(s)):
        ans = (ans + s[j][1] * l(j)) % mo
    return ans

t = int(input())
for _ in range(t):
    x = int(input())
    print(solveKth(sp[x % 2], x))

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

typedef long long s64; 
typedef std::pair<int, int> pii; 

template <class T>
inline void read(T &x) {
	static char ch; 
	while (!isdigit(ch = getchar())); 
	x = ch - '0'; 
	while (isdigit(ch = getchar()))
		x = x * 10 + ch - '0'; 
}

inline void invalid() {
	puts("-1"); 
	exit(0); 
}

const int MaxN = 1e5 + 5;  

int n; 
int sze[MaxN]; 
bool vis[MaxN]; 

s64 d[MaxN], c[MaxN];
std::vector<pii> ans; 
std::map<s64, int> pos; 

int fa[MaxN]; 
std::vector<int> adj[MaxN]; 

inline void addEdge(int u, int v) {
	sze[u] += sze[v]; 
	adj[u].push_back(v); 
	ans.push_back(pii(u, v)); 
}

inline void dfs(int u) {
	for (int v : adj[u]) {
		dfs(v); 
		c[u] += c[v] + sze[v]; 
	}
}

bool check() {
	int G = pos[d[n]]; 
	return dfs(G), c[G] == d[n]; 
}

int main() {
#ifdef orzczk
	freopen("tree.in", "r", stdin); 
#endif
	
	read(n); 
	for (int i = 1; i <= n; ++i) {
		read(d[i]); 
		sze[i] = 1; 
		pos[d[i]] = i; 
	}
	std::sort(d + 1, d + n + 1, std::greater<s64>()); 

	for (int i = 1; i < n; ++i) {
		int v = pos[d[i]], u; 
		s64 faD = d[i] - n + 2 * sze[v]; 

		vis[v] = true; 
		if (!pos.count(faD) || vis[u = pos[faD]]) {
			invalid(); 
		}
		
		addEdge(u, v); 
	}

	if (check()) {
		for (int i = 0; i < n - 1; ++i) {
			printf("%d %d\n", ans[i].first, ans[i].second); 
		}
	} else {
		invalid(); 
	}

	return 0; 
}

Measured memory_bytes: 20756
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const ll MOD = 1000000007LL;
int main() {
	cout << "? 1000000000" << endl;
	string ans;
	cin >> ans;
	if (ans == "Y") {
		for (int i = 8; i >= 1; i--) {
			cout << "? 1" + string(i - 1, '0') + "1" << endl;
			cin >> ans;
			if (ans == "N") {
				cout << "! 1" + string(i + 1, '0') << endl;
				return 0;
			}
		}
		cout << "? 9" << endl;
		cin >> ans;
		if (ans == "Y") cout << "! 1" << endl;
		else cout << "! 10" << endl;
	}
	else {
		int l = 1, r = 10;
		while (r - l > 1) {
			ll m = (l + r) / 2;
			cout << "? 1" + string(m - 1, '0') << endl;
			cin >> ans;
			if (ans == "Y") {
				l = m;
			}
			else {
				r = m;
			}
		}
		int d = l;
		vector<int> vec;
		for (int i = 0; i < d; i++) {
			l = 0, r = 10;
			if (i == 0) l = 1;
			while (r - l > 1) {
				int m = (l + r) / 2;
				cout << "? ";
				for (int j = 0; j < i; j++) cout << vec[j];
				cout << m;
				for (int j = 0; j < d - i; j++) cout << 0;
				cout << endl;
				cin >> ans;
				if (ans == "Y") {
					cout << "? ";
					for (int j = 0; j < i; j++) cout << vec[j];
					cout << m - 1;
					for (int j = 0; j < d - i; j++) cout << 9;
					cout << endl;
					cin >> ans;
					if (ans == "Y") {
						r = m;
					}
					else {
						cout << "! ";
						for (int j = 0; j < i; j++) cout << vec[j];
						cout << m;
						for (int j = 0; j < d - i - 1; j++) cout << 0;
						cout << endl;
						return 0;
					}
				}
				else {
					l = m;
				}
			}
			vec.push_back(l);
		}
		cout << "!";
		for (int i = 0; i < vec.size(); i++) cout << " " << vec[i];
		cout << endl;
	}
}

Measured memory_bytes: 596
#![allow(unused_imports)]
#![allow(non_snake_case)]
use std::cmp::*;
use std::collections::*;
use itertools::Itertools;
use num_traits::clamp;
use ordered_float::OrderedFloat;
use proconio::{input, marker::*, fastout};
use superslice::*;

#[fastout]
fn main() {
    input! {
        n: usize,
        a: [i64; n]
    }
    let M = 1_000_000_007i64;

    let mut cum = vec![0; n];
    for i in 1..n {
        cum[i] = cum[i-1] + a[i];
    }

    let mut ans = 0;
    for i in 0..n-1 {
        ans += (a[i] * ((cum[n-1] - cum[i]) % M)) % M;
        ans %= M;
    }
    println!("{}", ans);
}


Measured memory_bytes: 7208
// inputに入力データ全体が入る
function Main(input) {
  chars = input.split("");
  
  if(chars[0]==chars[1] || chars[1]==chars[2] || chars[2]==chars[3]){
   console.log("Bad");
  }else{
   console.log("Good");
  }
}
  
//*この行以降は編集しないでください（標準入出力から一度に読み込み、Mainを呼び出します）
Main(require("fs").readFileSync("/dev/stdin", "utf8"));


Measured memory_bytes: 7372
require 'matrix'
loop do
  s = gets.chomp.chop
  break if s == ''

  #lookahead(?!  )
  s.gsub!(/([A-Z\)])(?![a-z\d])/, '\11')
  s.gsub!(/([A-Z][a-z])(?!\d)/, '\11')
  s.gsub!(/\((.+?)\)(\d*)/){
    as, n = $1, $2
    as.gsub(/([a-zA-Z])(\d+)/){"#{$1}#{$2.to_i * n.to_i}"}
  }
  atoms = s.scan(/[A-Z][a-z]?/).uniq
  l = s.split('->')[0].count('+') + 1
  molecules = s.split(/\->|\+/)
  m = molecules.size - 1
  n = atoms.size

  a = Matrix.build(n, m){|y, x|
    sum = 0
    molecules[x].scan(/#{atoms[y]}(\d+)/).each{ |a|
      x < l ? sum += a[0].to_i : sum -= a[0].to_i
    }
    sum.to_r
  }.to_a

  b = [0] * n
  atoms.each do |atom|
    molecules[-1].scan(/(#{atom})(\d+)/).each{ |a, k|
      b[atoms.index(a)] = k.to_r
    }
  end

  # Gauss-Jordan elimination
  (0...[n,m].min).each do |i|
    pv = (i...n).max{|k| a[k][i].abs}
    a[i], a[pv] = a[pv], a[i]
    b[i], b[pv] = b[pv], b[i]
    (0...n).each do |j|
      next if i == j
      r = a[j][i] / a[i][i]
      (i...m).each do |k|
        a[j][k] -= r * a[i][k]
      end
      b[j] -= r * b[i]
    end
  end

  ans = (Matrix[*a[0,m]].inv * Vector[*b[0,m]]).to_a + [1.to_r]
  lcm = ans.map(&:denominator).reduce(&:lcm)
  puts ans.map{|x| (x * lcm).to_i} * ' '
end

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

int main(){
    int N;
    int Y=0;
    int X=0;
    int goukei=0;
    cin >> N;
    vector<int>vec(N);
    for (int L=0; L<N; L++){
        cin >>vec.at(L);
    }
    for (X=0; X<N; X++){
        for (Y=0; Y<N; Y++){
            goukei+=vec.at(X)*vec.at(Y);
        }
        goukei-=vec.at(X)*vec.at(X);
    }
    cout << goukei/2 << endl;
}



Measured memory_bytes: 256
#include <stdio.h>

int main(void)
{
	int n, i, debt, inter, result;
	scanf("%d", &n);
	
	debt = 100000;
	for (i = 0; i < n; i++){
		
		inter = debt * 0.05;
		
		debt += inter;
		
		if (debt % 1000 != 0){
			debt /= 1000;
			debt++;
			debt *= 1000;
		}
	}
		printf("%d\n", debt);
	return (0);
}

Measured memory_bytes: 592
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define vi vector<int>
#define vii vector<int, int>
#define po pop_back
#define hell 1000000007
using namespace std;
 
void solve(){
	int n;
	cin>>n;
	while(n>0){
		if(n%10==7){
			cout<<"Yes";
			return;
		}
		n/=10;
	}
	cout<<"No";
}
 
int main(){
	int t = 1;
	//cin>>t;
	while(t--){
		solve();
	}
}

Measured memory_bytes: 3620
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#include<map>
#include<set>
#include<utility>//swapでaとbの値を入れ替える
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define ll long long
#define sort(s) sort(s.begin(),s.end())
#define reverse(v)  reverse(v.begin(), v.end());
#define Yes(ans) if(ans)cout<<"Yes"<<endl; else cout<<"No"<<endl;
#define YES(ans) if(ans)cout<<"YES"<<endl; else cout<<"NO"<<endl;
#define hei(a) vector<a>
#define whie(a) vector<vector<int>>

int f(int x,vector<int> s) {
	if (x == 0)return 0;
	if (x == 1)return 1;
	if (s[x] != 0)return s[x];
	s[x] = f(x - 1,s) + f(x - 2,s);
	return s[x];
}


int main() {
	ll x, y;
	ll ans = 0;
	cin >> x >> y;
	for (int i = 0;; i++) {
		if (x > y) {
			ans = i;
			break;
		}
		x *= 2;
	}
	cout << ans << endl;
}


Measured memory_bytes: 256
n, m = [int(i) for i in input().split()]

ab = [[int(i) for i in input().split()] for _ in range(m)]

ab = sorted(ab, key = lambda x:(x[1],x[0]))

now = ab[0][1] - 1
count = 1

for i in range(m):
    if(now < ab[i][0]):
        now = ab[i][1] - 1
        count += 1

print(count)


Measured memory_bytes: 34248
N,Y = list(map(int, input().split()))
for i in reversed(range(N+1)):
    for j in reversed(range(N-i+1)):
        k = N-i-j
        if i*10000 + j*5000 + k*1000 == Y:
            print(i, j, k)
            exit()

print(-1, -1, -1)

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

int main() {
  int m1, d1, m2, d2; cin >> m1 >> d1 >> m2 >> d2;
  if (m1+1 == m2) cout << 1;
  else cout << 0;
  return 0;
}

Measured memory_bytes: 256
#include<stdio.h>

int main()
{
    int A,B,x;
    scanf("%d%d%d",&x,&A,&B);
    if(1<=x && x<=1000000000 && 1<=A && A<=1000000000 && 1<=B && B<=1000000000)
    {
        if(B<=A) printf("delicious");
        else if (B>A+x) printf("dangerous");
        else printf("safe");
    }

return 0;
}

Measured memory_bytes: 1732
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pp pair<int,int>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define ld long double
#define al(a) (a).begin(),(a).end()
#define mk make_pair
#define check cout<<"?"<<endl;

ll MOD=1000000007;
ll mod=998244353;
int inf=1000001000;
ll INF=1e18+5;

int main(){
    ll n,d,ans=0; cin>>n>>d;
    rep(i,n){
        ll x,y; cin>>x>>y;
        if(d*d>=x*x+y*y) ans++;
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 3632
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <limits>
#include <random>
#include <complex>
#include <cmath>
#include <cstdio>
#include <cstdlib>
using namespace std;
typedef long long ll;
#define REP(i,n) for (int i = 0; i < n; i++)
template <class T> using reversed_priority_queue = priority_queue<T, vector<T>, greater<T> >;

int main ()
{
    int N,K;
    cin >> N >> K;
    vector < int > a(N);
    REP(i,N) cin >> a[i];

    int ans = -1e9;
    for (int A = 0; A <= N; A++) {
        for (int B = 0; B <= N; B++) {
            if (A + B > N) continue;
            if (A + B > K) continue;
            vector < int > cnd;
            for (int i = 0; i < A; i++) {
                cnd.push_back(a[i]);
            }
            for (int i = N - 1; i >= N - B; i--) {
                cnd.push_back(a[i]);
            }
            sort(cnd.begin(), cnd.end());
            int anst = 0;
            for (int i = (int)cnd.size() - 1; i >= 0; i--) {
                if (cnd[i] < 0 && i + 1 <= K - A - B) {
                    continue;
                } else {
                    anst += cnd[i];
                }
            }
            ans = max(ans, anst);
        }
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int X, Y, Z;
struct Node {
  int a, b, c;
  Node() = default;
  Node(int x, int y, int z) : a(x), b(y), c(z){};
};

int a[100005][3];
int main() {
  vector<Node> vv;
  cin >> X >> Y >> Z;
  const int n = X + Y + Z;
  ll csum = 0;
  for (int i = 0; i < n; ++i) {
    cin >> a[i][0] >> a[i][1] >> a[i][2];
    vv.push_back(Node(a[i][0], a[i][1], a[i][2]));
    csum += a[i][2];
  }

  sort(vv.begin(), vv.end(), [](const Node &n1, const Node &n2) {
    return (n1.a - n1.b) > (n2.a - n2.b);
  });

  priority_queue<int, vector<int>, greater<int>> pq1;
  auto pq2 = pq1;

  vector<ll> smax1(n + 1);
  ll lsum = 0;
  for (int i = 0; i < X; ++i) {
    pq1.push(vv[i].a - vv[i].c);
    lsum += vv[i].a - vv[i].c;
  }
  smax1[X] = lsum;
  for (int i = X; i < n - Y; ++i) {
    pq1.push(vv[i].a - vv[i].c);
    lsum += vv[i].a - vv[i].c;
    lsum -= pq1.top();
    pq1.pop();
    smax1[i + 1] = lsum;
  }

  vector<ll> smax2(n + 1);
  ll rsum = 0;
  for (int i = n - 1; i >= n - Y; --i) {
    pq2.push(vv[i].b - vv[i].c);
    rsum += vv[i].b - vv[i].c;
  }

  smax2[n - Y] = rsum;
  for (int i = n - Y - 1; i >= X; --i) {
    pq2.push(vv[i].b - vv[i].c);
    rsum += vv[i].b - vv[i].c;
    rsum -= pq2.top();
    pq2.pop();
    smax2[i] = rsum;
  }

  ll ret = 0;
  for (int i = X; i <= n - Y; ++i) {
    ret = max(ret, smax1[i] + smax2[i] + csum);
  }

  cout << ret << endl;
}

Measured memory_bytes: 4980
a = list(map(int,input().split()))
ev = a[0]
od = a[1]
if (ev<=1)and(od<=0):
  n = 0
elif ev<=1:
  n = a[1]*(a[1]-1)/2
elif od<=1:
  n = a[0]*(a[0]-1)/2
else:
  n = a[0]*(a[0]-1)/2+a[1]*(a[1]-1)/2
print(int(n))

Measured memory_bytes: 3064
open System

let inline avg a b = (a + b) / 2

let rec f k (a,b,c) =
    if a=b && b=c then
        if a%2 = 0 then -1 else k
    elif (a%2)+(b%2)+(c%2) = 0 then
        f (k+1) (avg b c, avg c a, avg a b)
    else k
        
let [|a; b; c|] = stdin.ReadLine().Split() |> Array.map int

printfn "%d" <| f 0 (a,b,c)

Measured memory_bytes: 14040
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdlib>
#include <map>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define pie 3.141592653589793238462643383279
#define mod 998244353
#define inf 10000000000000007
#define all(vec) vec.begin(),vec.end()
#define ggr getchar(); getchar();return 0;
#define int long long
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;
}
bool prime(int x) {
	for (int i = 2; i <= sqrt(x); i++) {
		if (x%i == 0)return false;
	}
	return true;
}

int kai(int x) {
	if (x == 1)return 1;
	return kai(x - 1)*x;
}

int mod_pow(int x, int y, int moder) {
	int res = 1;
	while (y > 0) {
		if (y & 1)res = res * x%moder;
		x = x * x%moder;
		y >>= 1;
	}
	return res;
}

int n;
string s[10000];
int ans;
int a, b, c;
bool ta = true;

signed main() {
	cin >> n;
	rep(i, n) {
		cin >> s[i];
		rep(j, s[i].size() - 1) {
			if (s[i][j] == 'A'&&s[i][j + 1] == 'B')ans++;
		}
		if (s[i][0] == 'B')b++;
		else ta = false;
		if (s[i][s[i].size() - 1] == 'A')a++;
		else ta = false;
		if (ta)c++;
		ta = true;
	}
	if (a == b && b == c && a != 0)ans += a - 1;
	else ans += min(a, b);
	cout << ans << endl;
}

Measured memory_bytes: 768
#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
long long INF = 1e18;

long long calc(const vector<long long>&X, long long x, long long m){
  if(not m) return INF;
  long long N = X.size();
  priority_queue<long long> Q;
  long long t = N*x;
  for(int i = N-1; i >= 0; --i){
    if(i < N-m){
      long long k = -Q.top();
      Q.pop();
      t += (2*k+1)*X[i];
      Q.push(-(k+1));
    }else{
      t += 5*X[i]+x;
      Q.push(-2);
    }
  }
  return t;
}

int main(){
  long long N, x;
  cin >> N >> x;
  vector<long long> X(N);
  for(int i = 0; i < N; ++i) cin >> X[i];
  long long ans = INF, l = 1, r = N;
  
  while(r-l > 2){
    long long m1 = (2*l+r)/3, m2 = (l+2*r)/3;
    //cerr << m1 << " " << m2 << endl;
    long long s1 = calc(X,x,m1), s2 = calc(X,x,m2);
    //cerr << s1 << " " << s2 << endl;
    if(s1 < s2){
      r = m2;
    }else{
      l = m1;
    }
  }
  //cerr << l << " " << r << endl;
  ans = min({calc(X,x,l),calc(X,x,l+1),calc(X,x,r)});
  cout << ans << endl;
}


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

int main(){
    int K;
    cin >> K;
    int V = 7%K;
    vector<bool> found(K);
    for(int ans=1; ; ans++){
        if(V == 0){
            cout << ans << endl;
            return 0;
        }
        if(found[V]) break;
        found[V] = 1;
        V = (10*V+7) % K;
    }
    cout << -1 << endl;
    return 0;
}


Measured memory_bytes: 3716
N = int(input())
W = list(map(int, input().split()))

W_sum = sum(W)
S = 0
for i in range(N):
    S += W[i]
    if S > W_sum // 2:
        idx = i
        break
if 0 < idx < N-1:
    ans_1 = abs(sum(W[:i+1]) - sum(W[i+1:]))
    ans_2 = abs(sum(W[:i]) - sum(W[i:]))
    print(min(ans_1, ans_2))
elif idx == 0:
    print(abs(W[0] - sum(W[1:])))
else:
    print(abs(W[-1] - sum(W[:N-1])))

Measured memory_bytes: 38256
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i,n) for(int i=0;i<(n);++i)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define all(x) (x).begin(), (x).end()
#define PI 3.14159265358979323846264338327950L
using namespace std;
typedef long long ll;
typedef long double ld;
int main() {
    int n;
    cin>>n;
    vector<ll> a(n);
    rep(i,n) cin>>a[i];
    sort(all(a));
    ll ans=0,i=0;
    while(i<n){
        ll b=a[i],c=0;
        while(i<n&&b==a[i]) c++,i++;
        ans+=c%2;
    }
    cout<<ans;
}

Measured memory_bytes: 3980
/**
 * @copyright (c) 2020 Daisuke Hashimoto
 */

#include <bits/stdc++.h>
using namespace std;
using Pair = pair<int64_t, int64_t>;
constexpr int64_t kInf = INT64_MAX / 2L;

// std::cout << std::setprecision(20) << 1.1 << endl;

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

  int64_t N;
  cin >> N;
  vector<Pair> A(N);
  for (int64_t i = 0; i < N; ++i) {
    cin >> A[i].first >> A[i].second;
  }
  sort(A.begin(), A.end());
  map<Pair, int64_t> counts;
  int64_t max_count = 0;
  for (int64_t i = 0; i < N; ++i) {
    for (int64_t j = i + 1; j < N; ++j) {
      const Pair p(A[j].first - A[i].first, A[j].second - A[i].second);
      if (counts.find(p) == counts.end()) {
        counts[p] = 1;
      } else {
        ++counts[p];
      }
      max_count = max(max_count, counts[p]);
    }
  }
  int64_t result = N - max_count;
  cout << result << endl;
  return 0;
}


Measured memory_bytes: 3648
#include <bits/stdc++.h>
using namespace std;
const int M = 101;

int n, m, odd, a[M];
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m;
	for(int i = 0; i < m; i++) {
		cin >> a[i];
		if(a[i] % 2) ++odd;
	}
	if(odd > 2) cout << "Impossible", exit(0);
	for(int i = 0; i < m; i++) if(a[i] % 2) swap(a[i], a[0]);
	for(int i = 1; i < m; i++) if(a[i] % 2) swap(a[i], a[m-1]);
	for(int i = 0; i < m; i++) cout << a[i] << ' ';
	vector<int> res;
	if(m == 1) {
		if(a[0] > 1) res.push_back(a[0]-1);
		res.push_back(1);
	}
	else for(int i = 0; i < m; i++) {
		if(!i) {
			if(a[i] > 1) res.push_back(a[i]-1);
		}
		else if(i == m-1) res.push_back(a[i]+1);
		else res.push_back(a[i]);
	}
	cout << endl << res.size() << endl;
	for(int x: res) cout << x << ' ';
}


Measured memory_bytes: 256
while True:
    try:
        x1,y1,x2,y2,xq,yq=map(float,raw_input().split(","))
    except EOFError:
        break
    try:
        m=(y2-y1)/(x2-x1)
        y=(yq*(m*m-1)+2*m*xq+2*(y2-m*x2))/(1+m*m)
        x=m*yq+xq-m*y
    except ZeroDivisionError:
        x=-xq
        y=yq
    print x,y

Measured memory_bytes: 4244
def main():
    a, b = map(int, input().split())
    A = ''
    for i in range(b):
        A = str(a) + A
    B = ''
    for i in range(a):
        B = str(b) + B
    dicA = int(A[0])
    dicB = int(B[0])
    if dicA < dicB:
        print(A)
    else:
        print(B)
main()

Measured memory_bytes: 9036
A, B, K = map(int, input().split())

for i in range(K):
    if i % 2 == 0:
        if A % 2 != 0:
            A -= 1
        A = A // 2
        B += A
    else:
        if B % 2 != 0:
            B -= 1
        B = B // 2
        A += B

print(A, B)

Measured memory_bytes: 38496
// clang-format off
#include <bits/stdc++.h>
#define int long long
#define main signed main()
#define loop(i, a, n) for (int i = (a); i < (n); i++)
#define rep(i, n) loop(i, 0, n)
#define forever for (;;)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define prec(n) fixed << setprecision(n)
template<typename A> using V = std::vector<A>;
template<typename A> using F = std::function<A>;
template<typename A, typename B> using P = std::pair<A, B>;
using pii = P<int, int>;
using vi = V<int>;
using vd = V<double>;
using vs = V<std::string>;
using vpii = V<pii>;
using vvi = V<vi>;
using vvpii = V<vpii>;
constexpr int INF = sizeof(int) == sizeof(long long) ? 1000000000000000000LL : 1000000000;
constexpr int MOD = 1000000007;
constexpr double PI = acos(-1);
template<typename A, typename B> bool cmin(A &a, const B &b) { return a > b ? (a = b, true) : false; }
template<typename A, typename B> bool cmax(A &a, const B &b) { return a < b ? (a = b, true) : false; }
template<typename T> std::istream &operator>>(std::istream &is, std::vector<T> &v) { for (T &x : v) is >> x; return is; }
template<typename A, typename B> std::istream &operator>>(std::istream &is, std::pair<A, B> &p) { is >> p.first; is >> p.second; return is; }
using namespace std;
// clang-format on

main {
  int n;
  while (cin >> n, n) {
    vi p(n), j(n - 1);
    cin >> p >> j;
    int s = accumulate(all(p), 0);
    sort(rall(j));
    int maxi = s * n;
    rep(i, n - 1) {
      s += j[i];
      cmax(maxi, s * (n - i - 1));
    }
    cout << maxi << endl;
  }
}

Measured memory_bytes: 3872
# include <bits/stdc++.h>
/// my holy template
# define F first    
# define S second
# define mp make_pair
# define pii pair<int,int>         
/// eveything goes according to plan
# define long long long  
# define pb push_back
# define sz(a) (int)(a.size())
/// countdown BEGAN. 10 , 9 , 8 ...
# define y1    Y_U_NO_y1
# define left  Y_U_NO_left
# define right Y_U_NO_right     

const int Mod = (int)1e9 + 7;
const int MX = 1073741822;
const long MXLL = 9223372036854775807;
const int Sz = 1110111;

using namespace std;

inline void Read_rap () {
  ios_base :: sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
}
inline void randomizer3000 () {
  unsigned int seed;
  asm("rdtsc" : "=A"(seed));
  srand(seed);
}
     
                              
int main() 
{
  Read_rap ();
  int n;  cin >> n;

  if (n / 10 == 9 || n % 10 == 9)
    cout << "Yes";
  else
    cout << "No";

  return 0;
} 










// Coded by Z...

Measured memory_bytes: 256
#include <iostream>
#define x 200000
using namespace std;
int main(){
	int p[x+1];
	bool q[x+1];
	for(int i=2;i<=x;i++) q[i] = true;
	for(int i=2;i<=x;i++){
		if(not q[i]) continue;
		for(int j=2;j<=x/i;j++) q[i*j] = false;
	}
	int c = 0;
	for(int i=2;i<=x;i++) if(q[i]) p[c++] = i;

	int n;
	while(1){
		cin >> n;
		if(n==0) break;
		int b = 0;
		for(int i=0;i<n;i++) b+=p[i];
		cout << b << endl;
	}
}

Measured memory_bytes: 1428
n = int(input())
l = [None] * n
for i in range(n):
  l[i] = list(map(int, input().split()))
l.sort(key=lambda x:x[1])
t = 0
for a, b in l:
  t += a
  if t > b:
    print('No')
    exit(0)
print('Yes')

Measured memory_bytes: 53716
#include <iostream>
#include <vector>
#define int long long
#define rep(i, n) for(i = 0; i < n; i++)
using namespace std;

namespace matrix {
	typedef vector<int> Array;
	typedef vector<Array> Mat;

	Mat E(int n) {
		Mat m(n, Array(n, 0));
		int i; rep(i, n) m[i][i] = 1;
		return m;
	}

	Mat mulmod(Mat a, Mat b, int mod) {
		int i, j, k;
		int h = a.size(), w = b[0].size(), s = a[0].size();
		Mat c(h, Array(w, 0));
		rep(i, h)rep(j, w) rep(k, s) c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % mod;
		return c;
	}
	
	Mat powmod(Mat m, int n, int mod) {
		if (n == 0) return E(m.size());
		if (n & 1) return mulmod(m, powmod(m, n - 1, mod), mod);
		return powmod(mulmod(m, m, mod), n / 2, mod);
	}
	
	Array mulmod(Mat a, Array b, int mod) {
		int i, j;
		int h = a.size(), s = a[0].size();
		Array c(h, 0);
		rep(i, h) rep(j, s) c[i] = (c[i] + a[i][j] * b[j]) % mod;
		return c;
	}
}

int toX(int k) {
	int st = 0, ed = 2000000001, mid; //oooxxx, [st, ed)
	while (ed - st >= 2) {
		mid = (st + ed) / 2;
		if ((mid * mid) / 4 <= k) st = mid;
		else ed = mid;
	}
	return st;
}

//x' + y' = xを満たすマス(y', x')を調べる. 
//マス(y, x)にはfib(x+1)*fib(y+2)が何番目のイカ数かが, 0-indexedで書かれている.
//y'の偶奇で模様をつけると法則があるので、O(1)で殴れる.
int toY(int k, int x) {	
	int n = (x + 1) / 2;
	int s = k - (x * x) / 4;
	if (s < (n + 1) / 2) return 2 * s;
	s -= (n + 1) / 2;
	s = n / 2 - 1 - s;
	return 2 * s + 1;
}

int fib(int n, int mod) {
	matrix::Array x(2); x[0] = 0; x[1] = 1;
	matrix::Mat m(2, matrix::Array(2));
	m[0][0] = 0; m[0][1] = 1;
	m[1][0] = 1; m[1][1] = 1;
	m = matrix::powmod(m, n, mod);
	x = matrix::mulmod(m, x, mod);
	return x[0];
}

int mod = 1000000007;

signed main() {
	int k, x, y;
	cin >> k;
	k--;
	x = toX(k);
	y = toY(k, x);
	x -= y;
	cout << fib(x + 1, mod) * fib(y + 2, mod) % mod << endl;
	return 0;
}


Measured memory_bytes: 3184
#include<stdio.h>
int main(){
	int N,K,X,Y;
	int sum=0;
	scanf("%d%d%d%d",&N,&K,&X,&Y);
	if(N>=K)
	sum = K*X +(N-K)*Y;
	else
	sum = N*X;
	printf("%d\n",sum);
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0; i<(n); i++)
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
int main(){
    string s,t; cin>>s>>t;
    cout<<t<<s<<endl;
    return 0;
}

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

int main(){
	int hand[5];
	int card[13];
	int m;
	while(scanf("%d,%d,%d,%d,%d", &hand[0], &hand[1], &hand[2], &hand[3], &hand[4]) != EOF){
		m = -99999;
		for(int i = 0; i < 13; i++){
			card[i] = 0;
		}
		for(int i = 0; i < 5; i++){
			card[hand[i]]++;
		}
		sort(hand, hand+5);
		for(int i = 0; i < 13; i++){
			m = max(m, card[i]);
		}
		if(m == 4){
			printf("four card\n");
		}else if(m == 3){
			if((hand[0] == hand[1] && hand[0] == hand[2] && hand[3] == hand[4])
				||(hand[0] == hand[1] && hand[2] == hand[3] && hand[2] == hand[4])){
				printf("full house\n");
			}else {
				printf("three card\n");
			}
		}else if(m == 2){
			if(hand[0] == hand[1] && (hand[2] == hand[3] || hand[3] == hand[4])
					|| hand[1] == hand[2] && hand[3] == hand[4]){
				printf("two pair\n");
			}else if(hand[0] == hand[1] || hand[1] == hand[2] || hand[2] == hand[3] || hand[4]){
				printf("one pair\n");
			}
		}else if(hand[0]+1 == hand[1] && hand[1]+1 == hand[2] && hand[2]+1 == hand[3] && hand[3]+1 == hand[4]
				|| hand[0] == 1 && hand[1] == 10 && hand[2] == 11 && hand[3] == 12 && hand[4] == 13){
			printf("straight\n");
		}else{
			printf("null\n");
		}
	}
	return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll dp[32][3];
const ll mod=1e9+7;
int main(){
	ll n;	cin>>n;
	int N=0;
	while(n>>N)	N++;
	dp[N][0]=1;
	for(int i=N;i>0;i--){
		//j=0,1
		for(int j=0;j<3;j++){
			for(int k=0;k<3;k++){
				//N-side:k<=j*2+(N)<=2+k
				int t=j*2+((n>>(i-1))&1);
				if(t>=k)	(dp[i-1][min(2,t-k)]+=dp[i][j])%=mod;
			}
		}
	}
	ll ans=0;
	for(int i=0;i<3;i++)	(ans+=dp[0][i])%=mod;
	cout<<ans<<endl;
	return 0;
}


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

#define int             long long
#define FOR( i, m, n )  for( int (i) = (m); (i) < (n); (i)++ )
#define REP( i, n )     FOR( i, 0, n )
#define REPR( i, m )    for( int (i) = (m); (i) >= 0; (i)-- )
#define REPONE( i, n )  FOR( i, 1, n + 1 )
#define ALL( a )        (a).begin(), (a).end()
#define MP              make_pair

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

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; }

const int INF = 1e9;
const int MOD = 1e9 + 7;

struct UnionFind{
    vector<int> par, rank;

    UnionFind( int N ) : par( N ), rank( N ){
        REP( i, N ) par[i] = i, rank[i] = 0;
    }

    int root( int x ){
        if( par[x] == x ) return x;
        else return par[x] = root( par[x] );
    }

    bool same( int x, int y ){
        return root( x ) == root( y );
    }

    void unite( int x, int y ){
        x = root( x );
        y = root( y );
        if( x == y ) return;

        if( rank[x] < rank[y] ){
            par[x] = y;
        }else{
            par[y] = x;
            if( rank[x] == rank[y] ) rank[x]++;
        }
    }
};

signed main(){
    int N, M; cin >> N >> M;
    vector<int> p( N );
    REP( i, N ) cin >> p[i];

    UnionFind uf( N );

    REP( i, M ){
        int x, y; cin >> x >> y;
        uf.unite( x - 1, y - 1 );
    }

    int ans = 0;
    REP( i, N ){
        if( uf.same( i, p[i] - 1 ) ) ans++;
    }

    cout << ans << endl;
}


Measured memory_bytes: 2560
def show(A, n):
    for i in range(n):
        print(A[i])


def insertion_sort(A, n, g):
    global cnt
    for i in range(g, n):
        v = A[i]
        j = i - g
        while j >= 0 and A[j] > v:
            A[j+g] = A[j]
            j -= g
            cnt += 1
        A[j+g] = v


def shell_sort(A, n):
    global cnt
    cnt = 0

    G = []
    g = 1
    while g <= n:
        G.append(g)
        g = 3 * g + 1

    print(len(G))
    for g in reversed(G):
        if g != 1:
            print(g, end=' ')
        else:
            print(g)
        insertion_sort(A, n, g)
    print(cnt)
    show(A, n)


def main():
    n = int(input())
    A = [int(input()) for i in range(n)]

    shell_sort(A, n)


if __name__ == "__main__":
    main()



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

using i64 = int64_t;

int main(){
    int n, d;
    string x;
    cin >> n >> x >> d;
    string ans = x;
    int cnt = 0;
    if(d == 0){
        cout << ans << endl;
        return 0;
    }
    for(int i=0;i<n;++i){
        if(x[i] == '0'){
            ans[i] = '1';
            cnt++;
        }
        if(cnt >= d)break;
    }

    if(cnt >= d){
        cout << ans << endl;
        return 0;
    }

    for(int i=n-1;i>=0;--i){
        if(x[i] == '1'){
            ans[i] = '0';
            cnt++;
        }
        if(cnt >= d)break;
    }

    cout << ans << endl;

    return 0;
}



Measured memory_bytes: 3200