akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <utility>
#include <algorithm>
#include <cstdio>
#include <iomanip>
#include <queue>
#include <deque>
#include <stack>
#include <fstream>
#include <cmath>
#include <random>
#include <complex>
#include <functional>
#include <bitset>
#include <sstream>
#include <cassert>
#include <time.h>

#define ll int64_t
#define Rep(i, n) for (ll i = 0; i < n; i++)
using namespace std;
typedef vector<ll> vec;
typedef vector<vec> mat;

const ll inf = 1LL << 60;

template<class T> inline void chmin(T& a, T b) {
    if (a > b) {
        a = b;
    }
}
template<class T> inline void chmax(T& a, T b) {
    if (a < b) {
        a = b;
    }
}
void printvec (vec &v) {
    Rep (i, (ll)v.size()) {
        cout << v[i] << " \n"[i+1 == (ll)v.size()];
    }
}

const int MOD = 1e9+7;
class mint {
    ll x;
public:
    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 {
        mint res(*this);
        return res += a;
    }

    mint operator-(const mint &a) const {
        mint res(*this);
        return res -= a;
    }

    mint operator *(const mint &a) const {
        mint res(*this);
        return res *= a;
    }

    mint pow(ll t) const {
        if (!t) return 1;
        mint a = pow(t >> 1);
        a *= a;
        if (t & 1) a *= *this;
        return a;
    }

    // for prime mod
    mint inv() const {
        return pow(MOD - 2);
    }

    mint &operator /=(const mint &a) {
        return (*this) *= a.inv();
    }

    mint operator /(const mint &a) const {
        mint res(*this);
        return res /= a;
    }

    friend ostream &operator<<(ostream& os, const mint &m) {
        os << m.x;
        return os;
    }
};


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

    ll N, K;
    cin >> N >> K;
    vec a(N);
    Rep (i, N) {
        cin >> a[i];
    }

    vector<vector<mint>> dp(N+1, vector<mint>(K+1, mint(0)));
    dp[0][0] = mint(1);

    Rep (i, N) {
        vector<mint> sub(K+1, mint(0));
        Rep (j, K+1) {
            sub[j] += dp[i][j];
            if (j+a[i]+1 <= K) sub[j+a[i]+1] -= dp[i][j];
        }
        mint tmp(0);
        Rep (j, K+1) {
            tmp += sub[j];
            dp[i+1][j] = tmp;
        }
    }

    // Rep (i, N+1) {
    //     Rep (j, K+1) {
    //         cout << dp[i][j] << " \n"[j==K];
    //     }
    // }
    
    cout << dp[N][K] << endl;
}

Measured memory_bytes: 82960
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define pb push_back
#define all(v) v.begin(), v.end()
#define bigger (char)toupper
#define smaller (char)tolower
using namespace std;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef long long ll;
typedef unsigned long long ull;

int main() {
    int N;
    scanf("%d",&N);
    vi A(N);
    rep(i,N) cin>>A.at(i);
    sort(A.begin(),A.end());
    bool ok=true;
    rep(i,N-1) {
        if(A.at(i)==A.at(i+1)) ok=false;
    }
    if(ok) cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
}

Measured memory_bytes: 1024
import sys
input = sys.stdin.readline

h, w, d = [int(x) for x in input().split()]
a = [[int(x) for x in input().split()] for _ in range(h)]
q = int(input())
lr = [[int(x) for x in input().split()] for _ in range(q)]

dic = {}

for i in range(h):
    for j in range(w):
        dic[a[i][j]] = (i, j)

dis = {}

for i in range(1, d + 1):
    dis[i] = 0
    while i + d <= h * w:
        dis[i + d] = dis[i] + abs(dic[i + d][0] - dic[i][0]) + abs(dic[i + d][1] - dic[i][1])
        i += d

for i in range(q):
    l, r = lr[i]
    print(dis[r] - dis[l])




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

int main()
{
    string s;
    cin >> s;
    if ((s[0] == 'A' && s[1] == 'C') || (s[1] == 'A' && s[2] == 'C') || (s[2] == 'A' && s[3] == 'C') || (s[3] == 'A' && s[4] == 'C'))
    {
        cout << "Yes" << endl;
    }
    else
    {
        cout << "No" << endl;
    }

    return 0;
}

Measured memory_bytes: 256
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
inf = float('inf')
ninf = -float('inf')
 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？

x,y,z=mii()

a=x-z
b=a//(y+z)
print(b)



Measured memory_bytes: 65516
#include <cstdio>
#include <cctype>
#include <algorithm>
#include <vector>
#include <cmath>
#include <cassert>
using namespace std;
using ll = long long;

namespace io {
#define File(s) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)
  const int SIZE = (1 << 21) + 1;
  char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1;
  inline char getc () {return (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++);}
  inline void flush () {fwrite (obuf, 1, oS - obuf, stdout); oS = obuf;}
  inline void putc (char x) {*oS ++ = x; if (oS == oT) flush ();}
  template<class T>
  inline void read(T &x) {
    char ch; int f = 1;
    x = 0;
    while(isspace(ch = getc()));
    if(ch == '-') ch = getc(), f = -1;
    do x = x * 10 + ch - '0'; while(isdigit(ch = getc()));
    x *= f;
  }
  template<class T, class ...Args>
  inline void read(T &x, Args&... args) {read(x); read(args...);}
  template<class T>
  inline void write(T x) {
    static char stk[128];
    int top = 0;
    if(x == 0) {putc('0'); return;}
    if(x < 0) putc('-'), x = -x;
    while(x) stk[top++] = x % 10, x /= 10;
    while(top) putc(stk[--top] + '0');
  }
  template<class T, class ...Args>
  inline void write(T x, Args... args) {write(x); putc(' '); write(args...);}
  inline void space() {putc(' ');}
  inline void endl() {putc('\n');}
  struct _flush {~_flush() {flush();}} __flush;
};
using io::read; using io::write; using io::flush; using io::space; using io::endl; using io::getc; using io::putc;

ll fac[128];
int cnt = 0;

#ifdef LOCAL
using L = long long;
#else
using L = __int128_t;
#endif

L exgcd(L a, L b, L &x, L &y){
  if(b == 0){
    x = 1; y = 0;
    return a;
  }
  L result = exgcd(b, a % b, x, y);
  L tp = x;
  x = y;
  y = tp - a / b * y;
  return result;
}

int main() {
  ll n, nn;
  read(n); nn = n * 2;
  for (int i = 2, li = sqrt(nn); i <= li; ++i) {
    if (nn % i == 0) {
      fac[cnt] = 1;
      do fac[cnt] *= i, nn /= i; while (nn % i == 0);
      ++cnt;
    }
  }
  if (nn) fac[cnt++] = nn;
  L res = numeric_limits<ll>::max();
  for (int i = 0; i < (1 << cnt); ++i) {
    ll p = 1;
    for (int j = 0; j < cnt; ++j)
      if ((i >> j) & 1)
        p *= fac[j];
    ll q = n * 2 / p;
    L x, y;
    exgcd(p, q, x, y);
    x = -x;
    if (x >= 0) {
      ll c = x / q;
      x %= q; y -= p * c;
    }
    else {
      ll c = x / q;
      x %= q;
      if (x < 0) x += q, --c;
      y -= p * c;
    }
    if (x > 0 && y > 0) {
      res = min(L(res), x * p);
    }
  }
  write(res), endl();
  return 0;
}

Measured memory_bytes: 3076
# F - Three Variables Game

n, a, b, c = map(int, input().split())
s = [input() for i in range(n)]

def decode(c):
    return ord(c) - ord('A')

state = [a, b, c]
choice = []
for i in range(n):
    # 'AC' -> (0, 2)
    j, k = map(decode, s[i])

    # 失敗
    if state[j] == state[k] == 0:
        print('No')
        exit()

    # state[j] <= state[k] にする
    if state[j] > state[k]:
        j, k = k, j

    # 1手先読み
    if state[j] == state[k] == 1 and i < n - 1:
        xj, xk = map(decode, s[i + 1])
        if state[xj] + state[xk] == 1 and k in {xj, xk}:
            j, k = k, j

    # jを選択
    state[j] += 1
    state[k] -= 1
    choice.append('ABC'[j])

print('Yes')
for c in choice:
    print(c)


Measured memory_bytes: 17016
#include<bits/stdc++.h>
#define int long long
#define sd(a) scanf("%lld",&a)
#define sf(a) scanf("%lf",&a)
#define pi acos(-1.0)
using namespace std;
const int maxn=105;
struct Vector{
    double x,y;
    bool operator <(const Vector a)const{
        return atan2(y,x)<atan2(a.y,a.x);
    }
}vec[maxn];
double dis(int x,int y){
    return sqrt(x*x+y*y);
}
main(){
    int n;
    sd(n);
    for(int i=1;i<=n;++i){
        sf(vec[i].x);
        sf(vec[i].y);
    }
    sort(vec+1,vec+n+1);
    double mx=0.0;
    double ans=0;
    for(int i=1;i<=n;++i){
        double x=0,y=0;
        int pos=i+1;
        while(1){
            if(pos>n)
            pos=pos%n;
            x+=vec[pos].x;
            y+=vec[pos].y;
            ans=max(ans,dis(x,y));
            if(pos==i)break;
            pos++;
        }
    }
    cout<<fixed<<setprecision(15)<<ans<<endl;
}


Measured memory_bytes: 256
import core.bitop, std.algorithm, std.ascii, std.bigint, std.conv, std.math,
    std.functional, std.numeric, std.range, std.stdio, std.string, std.random,
    std.typecons, std.container, std.format;

// dfmt off
T lread(T = long)(){return readln.chomp.to!T();}
T[] lreads(T = long)(long n){return generate(()=>readln.chomp.to!T()).take(n).array();}
T[] aryread(T = long)(){return readln.split.to!(T[])();}
void scan(TList...)(ref TList Args){auto line = readln.split();
foreach (i, T; TList){T val = line[i].to!(T);Args[i] = val;}}
alias sread = () => readln.chomp();enum MOD = 10 ^^ 9 + 7;
alias PQueue(T, alias less = "a<b") = BinaryHeap!(Array!T, less);
// dfmt on

void main()
{
    auto S = sread();
    if (S.length & 1)
    {
        writeln("No");
        return;
    }
    foreach (i; 0 .. S.length)
    {
        if (S[i] != "hi"[i & 1])
        {
            writeln("No");
            return;
        }
    }
    writeln("Yes");
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long  ll;
#define FOR(i,a,n) for(ll i=(ll)a;i<(ll)n;i++)
#define RFOR(i,a,n) for(ll i=(ll)n-1;i >= (ll)a;i--)
#define rep(i,n) FOR(i,0,n)
#define rrep(i,n) RFOR(i,0,n)
#define ALL(v) v.begin(), v.end()
#define bra(first,second) '(' << first << ',' << second << ')'
constexpr ll MOD = 1000000007;
//constexpr ll MOD = 998244353;
ll INF = 4001001001001001001;
long double EPS = 1e-9;
long double PI = 3.141592653589793238;
template<typename T>
void remove(std::vector<T>& vector, unsigned int index){
    vector.erase(vector.begin() + index);
}

using Graph = vector<vector<tuple<ll,ll,ll>>>;

// MOD確認


int main(){
    ll K,A,B;
    cin >> K >> A >> B;
    FOR(i,A,B+1){
        if(i % K == 0){
            cout << "OK" << endl;
            return 0;
        }
    }
    cout << "NG" << endl;
}


Measured memory_bytes: 3636
using System;
using System.Collections;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Numerics;
using System.Text;
using System.Threading.Tasks;

namespace AtCorder
{
	public class Program
	{
		static void Main(string[] args)
		{
			var cin = new Scanner2();
			int n = cin.Int();
			int k = cin.Int();
			long[] a = cin.ArrayLong(n);

			int m = n * (n + 1) / 2;
			var b = new List<long>(m);
			for (int i = 0; i < n; i++) {
				long sum = 0;
				for (int j = i; j < n; j++) {
					sum += a[j];
					b.Add(sum);
				}
			}

			long ans = 0;
			for (int i = 50; i >= 0; i--) {
				long bit = 1L << i;
				long temp = ans + bit;
				int cnt = 0;
				for (int j = 0; j < m; j++) {
					if ((b[j] & temp) == temp) {
						++cnt;
						if (cnt >= k) {
							break;
						}
					}
				}

				if (cnt >= k) {
					ans = temp;
				}
			}

			Console.WriteLine(ans);
		}
	}

	public class Scanner2
	{
		private readonly char[] delimiter_ = new char[] { ' ' };
		private readonly string filePath_;
		private string[] buf_;
		private int index_;
		Func<string> reader_;

		public Scanner2(string file = "")
		{
			if (string.IsNullOrWhiteSpace(file)) {
				reader_ = Console.ReadLine;
			} else {
				filePath_ = file;
				var fs = new StreamReader(file);
				reader_ = fs.ReadLine;
			}
			buf_ = new string[0];
			index_ = 0;
		}

		public string Next()
		{
			if (index_ < buf_.Length) {
				return buf_[index_++];
			}

			string st = reader_();
			while (st == "") {
				st = reader_();
			}

			buf_ = st.Split(delimiter_, StringSplitOptions.RemoveEmptyEntries);
			if (buf_.Length == 0) {
				return Next();
			}

			index_ = 0;
			return buf_[index_++];
		}

		public int Int() => int.Parse(Next());
		public long Long() => long.Parse(Next());
		public double Double() => double.Parse(Next());

		public int[] ArrayInt(int N, int add = 0)
		{
			int[] Array = new int[N];
			for (int i = 0; i < N; i++) {
				Array[i] = Int() + add;
			}
			return Array;
		}

		public long[] ArrayLong(int N, long add = 0)
		{
			long[] Array = new long[N];
			for (int i = 0; i < N; i++) {
				Array[i] = Long() + add;
			}
			return Array;
		}

		public double[] ArrayDouble(int N, double add = 0)
		{
			double[] Array = new double[N];
			for (int i = 0; i < N; i++) {
				Array[i] = Double() + add;
			}
			return Array;
		}

		public void Save(string text)
		{
			if (string.IsNullOrWhiteSpace(filePath_)) {
				return;
			}

			File.WriteAllText(filePath_ + "_output.txt", text);
		}
	}
}

Measured memory_bytes: 14944
using System;

namespace ABC054B
{
    static class Program
    {
        static void Main()
        {
            var n = int.Parse(Console.ReadLine());
            long power = 1;
            int mod = 1000000007;
            
            for (int i = 1; i < n + 1; i++)
                power = (power * i) % mod;

            Console.WriteLine(power);
        }
    }
}

Measured memory_bytes: 13140
N,K = map(int, input().split())
A = list(map(int, input().split()))
for i in range(N):
    A[i] = A[i] -1
G = 0
lis = [0]*N
lis[0] = 1
roop = []
cnt = 0
while True:
    G = A[G]
    cnt +=1
    lis[G] += 1
    if lis[G] == 2:
        roop.append(G)
    elif lis[G] == 3:
        break

roop_cn = len(roop)
diff = cnt - roop_cn*2
if K < roop_cn + diff:
    G = 0
    for i in range(K):
        G = A[G]
    print(G + 1)
    exit()

K_n = K - diff
amari = K_n % roop_cn
print(roop[amari]+1)

Measured memory_bytes: 32396
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> VI;
typedef vector<vector<int>> VVI;
typedef vector<ll> VLL;
typedef vector<vector<ll>> VVLL;
typedef pair<ll, ll> Pair;
template <class T> T input() {T t; cin>>t; return t;}
#define FOR(i,a,b) for (ll i = a; i < b; i++)
#define REP(i,b) FOR(i,0,b)
#define RFOR(i,a,b) for (ll i = a-1; i >= b; i--)
#define RREP(i,a) RFOR(i,a,0)
#define REPALL(i,x) for (ll i = 0; i < x.size(); i++)
#define RREPALL(i,x) for (ll i = x.size()-1; i >= 0; i--)
#define REPITR(itr,x) for (auto itr = (x).begin(); itr != (x).end(); itr++)
#define ALL(x) (x).begin(), (x).end()
#define SORT(x) sort(ALL(x))
#define MIN_ELEMENT(x) min_element(ALL(x))
#define MAX_ELEMENT(x) max_element(ALL(x))
#define COUNT(x,num) count(ALL(x), num)
#define MEMSET(x,val) memset(x, val, sizeof(x))
#define CHMAX(a,b) a = max(a,b)
#define CHMIN(a,b) a = min(a,b)
#define FIND(x,key) x.find(key) != x.end()
#define IN_RANGE_V2(v,k,x,y) (0<=x+dx[k]&&x+dx[k]<v[y].size()&&0<=y+dy[k]&&y+dy[k]<v.size())
#define debug(x) cerr<<__LINE__<<": "<<(#x)<<" = "<<(x)<<endl;
void YES(bool flag) {cout<<(flag ? "YES" : "NO")<<endl;}
void Yes(bool flag) {cout<<(flag ? "Yes" : "No")<<endl;}
void yes(bool flag) {cout<<(flag ? "yes" : "no")<<endl;}
#define PRINT_ARRAY_H(a) REPALL(__i,a) {cout<<a[__i]<<(__i != a.size()-1 ? " " : "");} newline;
#define PRINT_ARRAY_V(a) REPALL(__i,a) {cout<<a[__i]<<endl;}
#define e1 first
#define e2 second
#define newline putchar('\n')
#define cspace ' '
#define sspace " "
const int INF = 1e7;
const ll MOD = 1e9 + 7;
const double pi = 3.141592653589793;
const VI dx = {1, 0, -1, 0};
const VI dy = {0, 1, 0, -1};
//const VI dx = {1, 1, 0, -1, -1, -1, 0, 1};
//const VI dy = {0, 1, 1, 1, 0, -1, -1, -1};

void solve()
{
    ll a, b, c, d, n, m, l, r, k, x, y, z, ans = 0ll;
    string s, t;
    cin>>s;
    REPALL(i,s) {
        if (i != s.size() - 1 && s[i] == 'B' && s[i+1] == 'C') {
            i++;
            t += 'D';
        } else {
            t += s[i];
        }
    }
    //cout<<t<<endl;
    int cnt_a = 0;
    REPALL(i,t) {
        if (t[i] == 'A') cnt_a++;
        else if (t[i] == 'D') ans += cnt_a;
        else cnt_a = 0;
    }

    cout<<ans<<endl;
}

int main()
{
    cout<<fixed<<setprecision(20);
    int __t = 1;
    //cin>>__t;
    REP(i,__t) {
        solve();
    }
    return 0;
}

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

using namespace std;

int main() {

    int K, A, B; cin >> K >> A >> B;
    int res = false;

    for(int i = 0; i<=1000; i++) {
        if(A <= i*K && i*K <= B) {
            res = true;
        }
    }

    if(res) {
        cout << "OK" << endl;
    }else{
        cout << "NG" << endl;
    }



    return 0;
}

Measured memory_bytes: 3640
#include <stdio.h>

int main(){
    int r,g,b,k;

    scanf("%d %d %d", &r, &g, &b);
    scanf("%d", &k);

    while(k > -1){
        if(g > r){
            break;
        }else{
            k--;
            g *= 2;
        }
    }

    while(k > -1){
        if(b > g){
            break;
        }else{
            k--;
            b *= 2;
        }
    }

    if(k >= 0){
        printf("Yes\n");
    }else{
        printf("No\n");
    }
}

Measured memory_bytes: 1664
n = gets.chomp.to_i
reds = []
blues = []

n.times do
  reds << gets.chomp.split(" ").map(&:to_i)
end
n.times do 
  blues << gets.chomp.split(" ").map(&:to_i)
end

blues.sort_by!{|x| x[0]}
flags = Array.new(n, 0)
cands = []


blues.each do |blue|
  red = [-1, -1]
  flag = -1
  n.times do |i|
    if flags[i] == 0 && reds[i][0] < blue[0] && reds[i][1] < blue[1] then
      if reds[i][1] > red[1] then
        red = reds[i]
        flag = i
      end
    end
  end
  if flag >= 0 then
    flags[flag] = 1
  end
end

puts flags.inject(:+)

Measured memory_bytes: 1788
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
typedef long long ll;
#define M 1000000007

int main(void){
	//cin.tie(1);ios::sync_with_stdio(false);
	string s;cin>>s;
	ll a=0,b=0,c=0;
	for(int i=0;i<s.size();i++)if(s[i]=='B')a++;
	for(int i=0;i<s.size();i++)if(s[i]=='B')b+=i;
	for(int i=s.size()-a;i<s.size();i++)c+=i;
	cout<<c-b<<endl;
	return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, k, c = 0;
int a[1000];
int main()
{
    cin >> n >> k;
    for(int i = 1,d; i <= k; i++){
        cin >> d;
        for(int j = 0,t; j < d; j++){
            cin >> t;
            a[t]++;
        }
    }
    for(int i = 1; i <= n; i++){
        if(a[i] == 0)c++;
    }cout << c << endl;
    return 0;
}


Measured memory_bytes: 3636
// #define _GLIBCXX_DEBUG // for STL debug (optional)
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>
using namespace std;

#define debug(...) fprintf(stderr, __VA_ARGS__)
#define int long long int
 
template<typename T> void chmax(T &a, T b) {a = max(a, b);}
template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chadd(T &a, T b) {a = a + b;}
 
typedef pair<int, int> pii;
typedef long long ll;
 
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
const ll INF = 1001001001001001LL;
const ll MOD = 1000000007LL;


signed main() {    
    int N, M;
    while(cin >> N >> M, N || M) {
        int sum = 0;
        vector<int> S(M), point(N), occupy(N);
        vector< vector<int> > per(M);
        for(int i=0; i<M; i++) {
            int K; cin >> S[i] >> K;
            sum += S[i];
            for(int j=0; j<K; j++) {
                int p; cin >> p; p--;
                per[i].push_back(p);

                point[p] += S[i];
                if(K == 1) occupy[p] += S[i];
            }
        }

        set< pair<int, int> > info;
        for(int i=0; i<N; i++) {
            info.emplace(point[i], i);
        }

        int ub = sum + 10, lb = 0;
        // fprintf(stderr, "sum = %lld\n", sum);
        while(ub - lb > 1) {
            int mid = (ub + lb) / 2;

            bool ok = true;
            for(int i=0; i<N; i++) {
                auto tup = make_pair(point[i], i);
                info.erase(tup);

                // 2 人以上なので OK
                int max_point = (--info.end()) -> first;

                int user_point = occupy[i] + mid;
                ok &= (user_point > max_point);

                info.insert(tup);
            }
            if(ok) ub = mid;
            else lb = mid;
        }
        cout << ub << endl;
    }
    return 0;
}



Measured memory_bytes: 4728
import collections

n = int(input())
v = list(map(int, input().split()))


v_odd = v[1::2]
v_even = v[::2]

vc_odd = collections.Counter(v_odd)
vc_even = collections.Counter(v_even)

odd_common = vc_odd.most_common()
even_common = vc_even.most_common()
if odd_common[0][0] != even_common[0][0]:
    print(n - odd_common[0][1] - even_common[0][1])
else:
    if len(odd_common) == 1 and len(even_common) == 1:
        print(len(v_even))
    elif len(odd_common) == 1:
        print(n - odd_common[0][1] - even_common[1][1])
    elif len(even_common) == 1:
        print(n - odd_common[1][1] - even_common[0][1])
    else:
        cnt1 = n - odd_common[1][1] - even_common[0][1]
        cnt2 = n - odd_common[0][1] - even_common[1][1]
        print(min(cnt1, cnt2))



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

int main() {
	int n;
	ll k;
	cin >> n >> k;
	vector<int> p(n);
	vector<ll> c(n);
	rep(i,n) {
		cin >> p[i];
		p[i]--;
	}
	rep(i,n) cin >> c[i];

	ll ans = -1000000000;

	// 各マスから開始した時の1ループの長さ、1ループ時のスコアを計算
	vector<int> len(n);
	vector<ll> total_p(n);
	rep(i,n) {
		len[i] = 0, total_p[i] = 0;
		int masu = i;
		do {
			masu = p[masu];
			total_p[i] += c[masu];
			len[i]++;
		} while(masu!=i);
		//cout << i << " " << "len:" << len[i] << ",total" << total_p[i] << endl;
	}

	rep(i,n) {
		// マスiから開始したときのスコアの最大値を計算
		ll point = 0;
		ll nokori_k = k;
		if (k>=2*len[i]) {
			ll num_lp = k/len[i] - 2;
			if (total_p[i]>=0) point += total_p[i] * num_lp;
			nokori_k = k - num_lp * len[i];
		}
		ll zan_point = 0;
		ll max_point = -1000000000;
		int masu = i;
		rep(j,nokori_k) {
			masu = p[masu];
			zan_point += c[masu];
			max_point = max(zan_point, max_point);
		}
		point += max_point;

		// ansを更新
		ans = max(ans, point);
	}

	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 3684
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
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; }
 
/* attention
    long longのシフト演算には気をつけよう
    タイポした時のデバッグが死ぬほどきつくなるので変数名は最低3字くらい使った方がいいかも
    sizeは(int)とキャストしよう
    ごちゃごちゃ場合分けを考える前に全探索は考えましたか？
*/

int main(){
    int N, D; cin >> N >> D;
    vector<vector<ll>> x(15, vector<ll>(15, 0));
    for(int i=0; i<N; ++i) for(int j=0; j<D; ++j) cin >> x[i][j];

    int ans = 0;
    for(int i=0; i<N; ++i){
        for(int j=i+1; j<N; ++j){
            ll d2 = 0;
            for(int k=0; k<D; ++k) d2 += (x[i][k]-x[j][k])*(x[i][k]-x[j][k]);
            bool flg = false;
            for(int k=1; k<=2000; ++k) if(d2 == k*k) flg = true;
            if(flg) ++ans;
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
main() {
 int N;
 cin >> N;
 vector<string> vec(N);
  
 for (int i=0; i<N; i++){
  cin >> vec.at(i);
 }
  
 sort(vec.begin(), vec.end());
 int count =N;
  
 for (int i=0; i<N-1; i++){
 
   if (vec.at(i)==vec.at(i+1))
     count--;
 }
cout << count << endl;
}



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

using namespace std;

long long power(int x, int y){
  long long n = 1;
  for(int i = 0; i < y; i++)
    n *= x;
  return n;
}

int log(int x, int y){
  int cnt = 0;
  while(y > 1){
    y /= x;
    cnt++;
  }
  return cnt;
}

int main() {
  int n;
  cin >> n;
  vector<int> h(n);
  for(int i = 0; i < n; i++)
    cin >> h.at(i);
  int ans = 0;
  int cnt = 0;
  for(int i = 0; i < n-1; i++){
    if(h.at(i) >= h.at(i+1)){
    cnt++;
    }
    else{
      ans = max(ans,cnt);
      cnt = 0;
    }
  }
  ans = max(ans,cnt);
  cout << ans << endl;
}


Measured memory_bytes: 640
const MAX_H: usize = 10010;
const MAX_N: usize = 1010;

fn memo(
    x: usize,
    v: usize,
    h: usize,
    n: usize,
    ab: &Vec<(usize, usize)>,
    dp: &mut Vec<Vec<Option<usize>>>,
) -> usize {
    if v >= h {
        return 0;
    }
    if let Some(value) = dp[x][v] {
        return value;
    }
    let (attack, magic) = ab[x];
    let mut result = memo(x, v + attack, h, n, ab, dp) + magic;
    if x + 1 < n {
        result = std::cmp::min(result, memo(x + 1, v, h, n, ab, dp));
    }
    dp[x][v] = Some(result);
    result
}
fn solve() {
    let s = std::io::stdin();
    let mut sc = Scanner { stdin: s.lock() };
    let h: usize = sc.read();
    let n: usize = sc.read();
    let ab: Vec<(usize, usize)> = (0..n)
        .map(|_| {
            let a: usize = sc.read();
            let b: usize = sc.read();
            (a, b)
        })
        .collect();
    let mut dp: Vec<Vec<Option<usize>>> = vec![vec![None; MAX_H]; MAX_N];
    let result = memo(0, 0, h, n, &ab, &mut dp);
    println!("{}", result);
}

fn main() {
    std::thread::Builder::new()
        .stack_size(64 * 1024 * 1024) // 64MB
        .spawn(|| solve())
        .unwrap()
        .join()
        .unwrap();
}

//snippet from kenkoooo
pub struct Scanner<R> {
    stdin: R,
}

impl<R: std::io::Read> Scanner<R> {
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .stdin
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r')
            .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn read_line(&mut self) -> String {
        use std::io::Read;
        let buf = self
            .stdin
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b'\n' || b == b'\r')
            .take_while(|&b| b != b'\n' && b != b'\r')
            .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: 180604
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> P;
typedef pair<int,int> Pi;
#define rep(i,n) for(ll i=0;i<n;i++)
#define FOR(i,a,b) for(ll i=a;i<b;i++)
#define fi first
#define se second
#define endl "\n"

template<typename T> inline bool chmax(T &a, T b){if(a<b){a=b;return true;}return false;}
template<typename T> inline bool chmin(T &a, T b){if(a>b){a=b;return true;}return false;}
template<typename T> ostream& operator<<(ostream& s,const complex<T>& d) {return s<<"("<<d.real()<<", "<<d.imag()<< ")";}
template<typename T1, typename T2> ostream& operator<<(ostream& s,const pair<T1,T2>& d) {return s<<"("<<d.first<<", "<<d.second<<")";}
template<typename T> ostream& operator<<(ostream& s, const vector<T>& d){int len=d.size();rep(i,len){s<<d[i];if(i<len-1) s<<" ";}return s;}
template<typename T> ostream& operator<<(ostream& s,const vector<vector<T>>& d){int len=d.size();rep(i,len){s<<d[i]<<endl;}return s;}
template<typename T> ostream& operator<<(ostream& s,const set<T>& v){s<<"{ ";for(auto itr=v.begin();itr!=v.end();++itr) {if (itr!=v.begin()) {s<< ", ";}s<<(*itr);}s<<" }";return s;}
template<typename T1, typename T2> ostream& operator<<(ostream& s,const map<T1,T2>& m){s<<"{"<<endl;for(auto itr=m.begin();itr!=m.end();++itr){s<<" "<<(*itr).first<<" : "<<(*itr).second<<endl;}s<<"}"<<endl;return s;}

const ll mod=1e9+7;
const ll inf=1e17;
const int INF=1e9;
const double PI=acos(-1);
const double EPS=1e-10;

int main(){
	cin.tie(0);ios::sync_with_stdio(false);
	string s;
	cin>>s;
	s='0'+s;
	reverse(begin(s),end(s));
	int n=s.size();
	vector<vector<ll>> dp(n+1,vector<ll>(2,inf));
	dp[0][0]=0;
	rep(i,n)rep(j,2){
		if(dp[i][j]==inf) continue;
		int now=s[i]-'0';
		rep(a,10){
			int ni=i+1,nj=0,na=a,nb;
			if(j){
				if(a==0){
					nj=1;
					na=9;
				}else{
					na--;
				}
			}
			if(na-now<0){
				nj=1;
				na+=10;
			}
			nb=na-now;
			chmin(dp[ni][nj],dp[i][j]+a+nb);
		}
	}
	cout<<min(dp[n][0],dp[n][1])<<endl;
}

Measured memory_bytes: 55880
#include<bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define rep2(i, m, n) for(int i = (int)(m); i < (int)(n); i++)
#define rep_inv(i, n, m) for(int i = (int)(n); i > (int)(m); i--)
using namespace std;
using ll = long long;
using vl = vector<ll>;
using vc = vector<char>;
using vvl = vector<vl>;
using vvc = vector<vc>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;

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

  vl ex(26, 0);

  rep(i, S.size()){
    if(ex[(S[i] - 'a')] == 1){
      cout << "no" << endl;
      return 0;
    } else{
      ex[(S[i] - 'a')] = 1;
    }
  }

  cout << "yes" << 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 X = Integer.parseInt(sc.next());
		int A = Integer.parseInt(sc.next());
		
		if(X>=A) {
			System.out.println(10);
		}else {
			System.out.println(0);
		}
		
		sc.close();
	}
}


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

const int mod = 1e9 + 7;
const long long INF = 1LL<<60;
using ll = long long;
using P = pair<int,int>;

struct UnionFind {
    vector<int> par; // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2

    UnionFind(int N) : par(N) { //最初は全てが根であるとして初期化
        for(int i = 0; i < N; i++) par[i] = i;
    }

    int root(int x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }

    void unite(int x, int y) { // xとyの木を併合
        int rx = root(x); //xの根をrx
        int ry = root(y); //yの根をry
        if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
        par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける
    }

    bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }
};


int main(){
    int n, m;
    cin >> n >> m;
    
    vector<int> a(m), b(m);
    
    rep(i, m){
        cin >> a[i] >> b[i];
        a[i]--, b[i]--;
    }
    
    int number_of_bridges = 0;
    
    //iは, どの辺を切断するかを表す
    //すべての辺を一度ずつ切断することを試す
    rep(i, m){
        
        UnionFind tree(n);
        
        //jは元通り残される辺を表す
        rep(j, m){
            if (j != i)tree.unite(a[j], b[j]);
        }
        
        if (tree.same(a[i], b[i]))continue;
        else number_of_bridges++;
        
    }
    
    cout << number_of_bridges << endl;
    return 0;
}



Measured memory_bytes: 256
#include <algorithm>
#include <cmath>
#include <climits>
#include <cstring>
#include <deque>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <map> //pair is also included in this library
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>

#define REP(i, s, n) for(int i = (int)(s); i < (int)(n); i++)
#define fst first
#define snd second
#define MP make_pair //incase c++11 or later is not available

using namespace std;

typedef long long int ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;

//prefer define statement
//for reason that const int ver. of INF will raise a silly warning (unused variable)
#define INF (INT_MAX/3)
#define LIM_INF (INT_MAX)
//const int INF = INT_MAX/3;

/*------------------------------------------------------------------------------*/

int cost[1100][1100];

int main(){
  int H, W, N;
  cin >> H >> W >> N;
  vector<string> s;

  s.push_back(string(W+2, 'X'));
  REP(i, 0, H){
    string tmp;
    cin >> tmp;
    s.push_back('X' + tmp + 'X');
  }
  s.push_back(string(W+2, 'X'));

  vector<PII> v(N+1);
  REP(i, 0, H+2){
    REP(j, 0, W+2){
      char c = s[i][j];
      if(c >= '1' && c <= '9'){
        v[c-'0'] = {i, j};
      } else if(c == 'S'){
        v[0] = {i, j};
      }
    }
    //cout << s[i] << endl;
  }

  int dest = 0, res = 0;
  REP(i, 0, N){
    queue<PII> q;
    q.push(v[dest]);
    memset(cost, -1, sizeof(cost));
    cost[v[dest].fst][v[dest].snd] = 0;
    while(!q.empty()){
      PII a = q.front(); q.pop();
      const int dx[4] = {-1, 0, 1, 0};
      const int dy[4] = {0, -1, 0, 1};
      if(s[a.fst][a.snd] == i + '1'){
        res += cost[a.fst][a.snd];
        dest++;
        break;
      }
      REP(i, 0, 4){
        int ny = a.fst + dy[i];
        int nx = a.snd + dx[i];
        if(s[ny][nx] != 'X' && !(cost[ny][nx] + 1)){//cost[ny][nx] + 1 == 0 if not searched
          cost[ny][nx] = cost[a.fst][a.snd] + 1;
          q.push({ny, nx});
        }
      }
    }
  }
  cout << res << endl;

  return 0;
}

Measured memory_bytes: 9716
#include <bits/stdc++.h>
#define rep(i, to) for (int i = 0; i < (to); i++)
#define rrep(i, to) for (int i = (to) - 1; i >= 0; i--)
#define repf(i, from, to) for (int i = (from); i < (to); i++)
#define all(v) v.begin(), v.end()
#define unless(cond) if (!(cond))
using namespace std;
using ll = long long;
template <typename T>
using V = vector<T>;
template <typename T, typename U>
using P = pair<T, U>;

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

  int ans = 0;
  repf(i, 1, n + 1) {
    int sum = 0;
    int left = i;

    while(left > 0) {
      sum += left % 10;

      left /= 10;
    }

    if(sum >= a && sum <= b) {
      ans += i;
    }
  }

  cout << ans << endl;
}

Measured memory_bytes: 3604
#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007 
#define ll long long 
#define N 100005
#define all(v) v.begin(),v.end()
#define pii pair<int,int>
#define piii pair<int, pii>
#define print(x) cout << #x << "=" << x << "\t";
#define endl "\n"
#define newline cout << endl;

int m;
int n;
vector<int> v[N];
int dp[N];
int ans;

int dfs(int id) {
    if (dp[id] != -1)
        return dp[id];
    dp[id] = 0;
    for(auto u : v[id])
        dp[id] = max(dp[id], 1 + dfs(u));
    return dp[id];
}

int main() {
    ios::sync_with_stdio(false); cin.tie(NULL); 
    cin >> n >> m;
    for(int i=0;i<m;i++) {
        int x, y;
        cin >> x >> y;
        v[x].push_back(y);
    }
    memset(dp, -1, sizeof(dp));
    for(int i=1;i<=n;i++)
        if (dp[i] == -1)
            dfs(i);
    for(int i=1;i<=n;i++)
        ans = max(ans, dp[i]);
    cout << ans;
    return 0;
}


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

using namespace std;

int a,b,c;

template<typename Drake>
void read(Drake &x){
	x=0;char ch=getchar();bool f=1;
	while(!isdigit(ch)){
		if(ch=='-')f^=1;
		ch=getchar();
	}
	while(isdigit(ch)){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	x*=(2*f-1);
}

template<typename Drake>
void write(Drake x){
	if(x<0){x=-x;putchar('-');}
	if(x>9)write(x/10);
	putchar(x%10+'0');
}

template<typename Drake>
void writeln(Drake x){
	write(x);
	puts("");
}

void init(){
	read(a);read(b);read(c);
}

int main(){
	init();
	int cnt=0,opt1=0,opt2=0,Max;
	opt1=(a&1)+(b&1)+(c&1);
	opt2=3-opt1;
	if(opt1*opt2==2){
		if(opt1>opt2){
			if(a&1)a++;
			if(b&1)b++;
			if(c&1)c++;
		}
		else if(opt1<opt2){
			if(!(a&1))a++;
			if(!(b&1))b++;
			if(!(c&1))c++;
		}
		cnt++;
	}
	Max=max(a,max(b,c));
	cnt+=(Max-a)/2+(Max-b)/2+(Max-c)/2;
	cout<<cnt<<endl;
	return 0;
}

Measured memory_bytes: 256
import std.stdio, std.algorithm, std.conv, std.array, std.string, std.math, std.typecons, std.numeric, std.container, std.range;

void main()
{
    auto S = readln.chomp;
    writeln((S[0] == S[$-1] && S.length%2 == 0) || (S[0] != S[$-1] && S.length%2 == 1) ? "First" : "Second");
}

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

using namespace std;

#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define pb emplace_back
#define ll long long
#define ld long double

const int INF = 2e9 + 1;
const ll INFLL = 1e18 + 1;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int a, b;
    cin >> a >> b;
    for (int i = 1; i <= 10000; i++) {
        if ((i * 8) / 100 == a && (i * 10) / 100 == b) {
            cout << i;
            return 0;
        }
    }
    cout << -1;
    return 0;
}


Measured memory_bytes: 3588
#include <bits/stdc++.h>
using namespace std;
#include <math.h>
#include <iomanip>
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

vector<pair<int64_t,int64_t>>prime_factorize(int64_t x){
  vector<pair<int64_t,int64_t>>p;
  for(int64_t i=2;i*i<=x;i++){
    int cnt=0;
    if(x%i==0){
    while(x%i==0){cnt++;x/=i;}
    p.push_back(make_pair(i,cnt));
    }
  }
  if(x!=1){p.push_back(make_pair(x,1));}
  return p; 
}

int main() {
  int M,D;
  cin>>M>>D;
  int cnt=0;
  for(int i=1;i<=M;i++){
    for(int j=10;j<=D;j++){
      int d1=j%10;
      int d10=j/10;
      if(d1>=2&&d10>=2&&d1*d10==i){cnt++;}
    }
  }
  cout<<cnt<<endl;
  return 0;
}

Measured memory_bytes: 3596
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();
		int c = sc.nextInt();

		if(b/a < c) {
			System.out.println(b/a);
		} else {
			System.out.println(c);
		}

	}
}


Measured memory_bytes: 21844
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <numeric>

using namespace std;
#define repp(i,a,b) for(int i = (int)(a) ; i < (int)(b) ; ++i)
#define reppe(i,a,b) for(int i = (int)(a) ; i <= (int)(b) ; ++i)
#define repm(i,a,b) for(int i = (int)(a) ; i > (int)(b) ; --i)
#define repme(i,a,b) for(int i = (int)(a) ; i >= (int)(b) ; --i)

typedef long long ll;

long long GCD(long long a, long long b){if(b==0)return a;return GCD(b,a%b);}

int main() {
    int K, N; cin >> K >> N;
    vector<int> A(N); repp(i,0,N) cin >> A[i];

    sort(A.begin(), A.end());
    int C = 0;
    repp(i,0,N) {
        if (i == N-1) C = max((K-A[i]) + A[0], C);
        else C = max(A[i+1] - A[i], C);
    }
    cout << K - C << endl;
}


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

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

int g(int x,int k){
    if(x%k==0)return x/k;
    int d=x/k+1;


    int lb=0,ub=x/d;
    while(ub-lb>1){
        int mid=(ub+lb)/2;
        if((x-mid*d)/k==x/k)lb=mid;
        else ub=mid;
    }
    x-=d*lb;
    if(x%k==0)return x/k;
    x-=d;
    return g(x,k);
}

signed main(){
    int N;cin>>N;
    int G=0;
    rep(i,N){
        int a,k;cin>>a>>k;
        G^=g(a,k);
    }
    if(G)cout<<"Takahashi"<<endl;
    else cout<<"Aoki"<<endl;
    return 0;
}


Measured memory_bytes: 384
#include<iostream>
 
using namespace std;
 
int D[100][2];
 
int main()
{
	int n;
	cin>>n;

    for(int  i =0; i < n; i++)
    {
    	cin>>D[i][0];
        cin>>D[i][1];
    }
  
    for (int i = 0; i < n-2; i++)
    {
    	if (D[i][0] == D[i][1])
        {
        	if (D[i+1][0] == D[i+1][1])
            {
            	if (D[i+2][0] == D[i+2][1])
                {
                	cout<<"Yes";
                    return 0;
                }
            }
        }
    }
    cout<<"No";
}

Measured memory_bytes: 3588
#include <bits/stdc++.h>
#define ll long long
#define lsb(x) (x & (-x))


using namespace std;



int main() {
    //fstream cin("A.in");
    //ofstream cout("A.out");
    int a, b;
    ios::sync_with_stdio(false);
    cin >> a >> b;
    cout << 2 * b - a;
    //cin.close();
    //cout.close();
    return 0;
}


Measured memory_bytes: 256
#include <iostream>

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

    long double ans = 0;

    for (int i = 0; i < n; i++) {
        long double amount;
        std::string jpy_or_btc;

        std::cin >> amount >> jpy_or_btc;

        if (jpy_or_btc == "JPY") {
            ans += amount;
        } else {
            ans += amount * 380000.0;
        }
    }

    std::cout << ans << std::endl;
}


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


typedef long long int llint;

int main() {

	llint n = 0;
	std::cin >> n;

	std::vector<llint> v;
	v.resize(n, 0);

	for (llint i = 0; i < n; i++) {
		std::cin >> v[i];
	}

	llint min = 10000000000;
	llint profit = 0;
	llint max_profit = -10000000000;
	for (int i = 0; i < n; i++) {
		profit = v[i] - min;
		if (v[i] < min)	min = v[i];
		if (profit > max_profit)max_profit = profit;
	}
	std::cout << max_profit << "\n";

	return 0;
}

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

int main(){
  int N, M;
  cin >> N >> M;
  string ans(N,'0');
  for(int i = 0; i < M; ++i){
    int s, c;
    cin >> s >> c;
    --s;
    if(ans[s] != '0' and ans[s] != '0'+c){
      puts("-1");
      return 0;
    }
    if(N > 1 and s == 0 and c == 0){
      puts("-1");
      return 0;
    }
    ans[s] = '0'+c;
  }
  if(N > 1 and ans[0] == '0') ans[0] = '1';
  cout << ans << endl;
}


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

void printlist(int lst[], size_t len){
	for(int i = 0; i < len - 1; i ++){
		cout << lst[i] << " ";
	}
	cout << lst[len - 1] << endl;
}

int bubbSort(int lst[], size_t len){
	bool flag = false;
	int j = len;
	int count = 0;

	do{
		for(int i = 1; i < j; i ++){
			if(lst[i - 1] > lst[i]){
				swap(lst[i - 1], lst[i]);
				flag = true;
				count += 1;
			}
		}

		j --;
	}while(flag && j >= 1);
	return count;
}

int main(int argc, char const *argv[])
{
	int N;
	cin >> N;
	int st[N];
	for (auto& i : st){
		cin >> i;
	}
	int count = bubbSort(st, sizeof(st) / sizeof(int));
	printlist(st, sizeof(st) / sizeof(int));
	cout << count << endl;
	return 0;
}


Measured memory_bytes: 3100
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <math.h>
const long long mod = 1000000007;
//const long long mod = 998244353;
int main() {
	int N;
	scanf("%d", &N);
	auto A = new int[N];
	int maxA = 0;
	for (int i = 0; i < N; i++) {
		scanf("%d", A + i);
		if (maxA < A[i])maxA = A[i];
	}
	maxA++;
	auto pmax = new int[maxA] {};
	for (int i = 0; i < N; i++) {
		int a = A[i];
		for (int j = 2; j*j <= a; j++) {
			int k = 0;
			while (!(a%j)) {
				a /= j;
				k++;
			}
			if (pmax[j] < k) {
				pmax[j] = k;
			}
		}
		if (pmax[a] < 1) {
			pmax[a] = 1;
		}
	}
	std::vector<std::pair<int, int>> p;
	for (int i = 2; i < maxA; i++) {
		if (pmax[i]) {
			p.push_back(std::pair<int, int>{i, pmax[i]});
		}
	}
	long long res = 0;
	for (int i = 0; i < N; i++) {
		int a = A[i];
		long long b = 1;
		for (int l = 0; l < p.size(); l++) {
			int j = p[l].first;
			int k = 0;
			while (!(a%j)) {
				a /= j;
				k++;
			}
			for (int m = 0; m < pmax[j] - k; m++) {
				b *= j;
				b %= mod;
			}
		}
		//printf("%lld ", b);
		res += b;
		res %= mod;
	}
	printf("%lld", res);
  
	return 0;
}

Measured memory_bytes: 4352
/**
 * @Author:      G_bg
 * @DateTime:    2019-07-20 20:50:07
 * @Description: 
 */
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const double PI = 3.1415926535898;
const double E = 2.718281828459;
const int INF = 0x7fffffff;
const int mod = 1e9+7;
const int maxn=1e5+10;
int a[maxn];
multiset<int> s;
int main(int argc, char const *argv[]) {
	ios::sync_with_stdio(0);cin.tie(0);
	int n;cin >> n;
	for(int i = 0;i < n;i++) cin >> a[i];
	for(int i = 0;i < n;i++){
		s.insert(a[i]);
		if(*s.begin() < a[i]){
			auto x = s.find(a[i]);
			s.erase(--x);
		}
	}
	cout << s.size() << endl;
	//system("pause");
	return 0;
}

Measured memory_bytes: 5376
#include <stdio.h>

int main(){
  int n, m;  scanf("%d%d", &n, &m);
  int table[100005] = {0};
  for(int i=0; i<m; i++){
    int l, r;  scanf("%d%d", &l, &r);
    table[l]++;
    table[r+1]--;
  }
  int height = 0;
  int ans = 0;
  for(int i=1; i<=n; i++){
    height += table[i];
    if(height >= m)
      ans++;
  }
  printf("%d\n", ans);
  return 0;
}


Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
int d, a;
string s;
double x = 0, y = 0, p = 0, pi = 3.141592653589793238462643383279502884197169;
void f() {
	int p = 0, sig = 1;
	for (char ch : s) {
		if (ch == ',') {
			d = p*sig; p = 0; sig = 1;
		}
		else if (ch == '-')sig = -1;
		else p = p * 10 + ch - '0';
	}
	a = p * sig;
}
signed main() {
	while (cin >> s) {
		f();
		if (d == 0 && a == 0)break;
		x += d * sin(p * pi / 180);
		y += d * cos(p * pi / 180);
		p += a;
	}
	cout << (int)x << endl << (int)y << endl;
}


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

typedef struct {
    int zaiko;             //zaiko
    int price;          //価格
} cell;

// --------------- 比較用の関数 cmp -------------------
int cmp( const void *p, const void *q ) {
    return ((cell*)p)->price - ((cell*)q)->price;
}

int main(){
  long int max=0;
  
  int N,M,i;
  scanf("%d %d",&N,&M);
  cell A[N];
  for(i=0;i<N;i++){
    scanf("%d %d",&A[i].price,&A[i].zaiko);
  }
   int n = sizeof A / sizeof( cell );
    qsort( A, n, sizeof(cell), cmp );
  i=0;
  while(M!=0){
    if(A[i].zaiko <= M){
      M-=A[i].zaiko;
      max += (long)A[i].price * (long)A[i].zaiko;
      i++;
    }
    else{
      max += (long)M * (long)A[i].price;
      M=0;
    }
  }
  
  printf("%ld\n",max);
  return 0;
}




Measured memory_bytes: 1788
#include <iostream>
using namespace std;
typedef long long ll;
ll x, k, d;

void solve() {
  // 負は考えない
  if (x < 0) x *= -1;
  
  // 常に一方向に動いてプラスなら答え
  if (x / d >= k) {
    cout << (x - (k * d));
    return;
  }
  
  // ０に近づけるだけ近く
  ll cnt = x / d;
  // 残り回数
  ll kk = k - cnt;
  ll near = x % d;
  if (kk % 2 == 0) {
     cout << near;
  } else {
     cout << (near - d) * -1;
  }
}

int main() {
  cin >> x >> k >> d;
  solve();
}

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

int main()
{
  string s;
  int ans=0;
  cin >> s;
  for(auto a:s){
    int buf=a&0x0F;
    if(buf==1)
      buf=9;
    else if(buf==9)
      buf=1;
    ans*=10;
    ans+=buf;
  }
  cout << ans << endl;
}

Measured memory_bytes: 256