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

using namespace std;

int main() {
    int N, M;
    int p[200000];
    string S[200000];
    cin >> N >> M;
    if (M != 0) {
        for (int i = 1; i <= M; ++i) cin >> p[i] >> S[i];
    }

    // ACが出たかフラグで判定
    int ac_flg[200000] = {0}; // ac出たら1
    int wa_sum[200000] = {0}; // ac出るまでのWA累計数

    const string AC = "AC";
    const string WA = "WA";

    int num_ac, num_wa;
    num_ac = 0;
    num_wa = 0;

    if (M != 0) {

        // とりあえず正解が出るまでWAを累計させる
        for (int i = 1; i <= M; ++i) {
            if (ac_flg[p[i]] == 0) {
                if (S[i] == WA) wa_sum[p[i]] +=1;
                if (S[i] == AC) ac_flg[p[i]] = 1;
            };
        };

        // 最後まで正解できなかった問題の不正解数を捨てる
        for (int i = 1; i <= N; ++i){
            num_ac += ac_flg[i];
            if (ac_flg[i] == 1) {
                num_wa += wa_sum[i];
            }
        }
    }

    cout << num_ac << " " << num_wa << endl;
}

Measured memory_bytes: 8832
#include <algorithm>
#include<stdio.h>
#include <cstdio>
#include <iostream>
#include <iomanip>
#include <string>
#include <algorithm>
#include <vector>
#include <math.h>
#include <stack>
#include <queue>
#include<map>
#include <set>
#include<math.h>
using namespace std;
#define int long long
#define ll long long
#define rep(i,n) for(ll i=0;i<n;++i)
#define Rep(i,n) for(ll i=1;i<=n;++i)
#define loop(i,m,n) for(ll i=m;i<n;++i)
#define ggr getchar(); getchar();return 0;
#define pie 3.141592653589793238462643383279
#define elif else if
#define P pair<ll,ll>
#define prique priority_queue<ll>
#define all(a)  (a).begin(),(a).end()
const int mod = 1000000007;
const int mod2 = 998244353;
int bin(int bina) {
	int ans = 0;
	for (int i = 0; bina > 0; i++)
	{
		ans = ans + (bina % 2) * pow(10, i);
		bina = bina / 2;
	}
	return ans;
}
bool prime(int n) {
	for (ll i = 2; i <= sqrt(n); i++) {
		if (n % i == 0)return false;
	}
	return n != 1;
}
int gcd(int x, int y) {
	if (y == 0)return x;
	return gcd(y, x % y);
}
int lcm(int x, int y) {
	return x * y / gcd(x, y);
}
int kai(int x) {
	if (x == 0)return 1;
	return kai(x - 1) * x % mod;
}
int mod_pow(int x, int y, int m) {
	int res = 1;
	while (y) {
		if (y & 1) {
			res = res * x % m;
		}
		x = x * x % m;
		y >>= 1;
	}
	return res;
}
int comb(int n, int r) {
	int ans = 1;
	for (ll i = n; i > n - r; --i) {
		ans = ans * i;
	}
	for (ll i = 1; i < r + 1; ++i) {
		ans = ans / i;
	}
	return ans;
}
int per(int n, int r) {
	r = n - r;
	int sum = 1;
	int i;
	for (i = n; i >= r + 1; i--)sum *= i;
	return sum;
}
struct UnionFind {
	vector<int> par;

	UnionFind(int n) : par(n, -1) { }

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

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

	bool merge(int x, int y) {
		x = root(x); y = root(y);
		if (x == y) return false;
		if (par[x] > par[y]) swap(x, y);
		par[x] += par[y];
		par[y] = x;
		return true;
	}

	int size(int x) {
		return -par[root(x)];
	}
};
signed main(){
	int n;
	cin >> n;
	if (n == 0) {
		cout << 0 << endl;
		return 0;
	}
	vector<int>ans;
	for (int i = 1; n; i *= -2) {
		if (n % (i * -2)) {
			ans.push_back(1);
			n -= i;
		}
		else {
			ans.push_back(0);
		}
	}
	reverse(all(ans));
	for (int p : ans)cout << p;
	cout << endl;
}


Measured memory_bytes: 256
n = int(input())
a = list(map(int, input().split()))

others = 0
rates = [False for i in range(8)]
for i in a:
    if i <= 399: rates[0] = True
    elif i <= 799: rates[1] = True
    elif i <= 1199: rates[2] = True
    elif i <= 1599: rates[3] = True
    elif i <= 1999: rates[4] = True
    elif i <= 2399: rates[5] = True
    elif i <= 2799: rates[6] = True
    elif i <= 3199: rates[7] = True
    else:
        others += 1
        
min_ans = rates.count(True)
if min_ans == 0: min_ans = 1
max_ans = rates.count(True)
if others > 0:
    max_ans += others

print(min_ans, max_ans)

Measured memory_bytes: 3064
#include <iostream>
#include <cmath>
#include <climits>
#include <string>
#include <numeric>
#include <vector>
#include <queue>
#include <map>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <set>

using namespace std;
using ll = long long;

template<typename T> void print(T t) { cout << t << endl; }
ll MOD = 1000000007;


int main() {
	int N;
	cin >> N;
	vector<ll> A(N + 1), B(N);
	A[0] = 0;
	for (int i = 1; i <= N; i++ ) cin >> A[i];
	B[N - 1] = A[N];
	for (int i = N - 1; i >= 2; i--) {
		B[i - 1] = (B[i] + A[i]) % MOD;
	}
	ll ans = 0;
	for (int i = 1; i <= N - 1; i++) {
		ans = (ans +  (A[i] * B[i])%MOD)%MOD;
	}
	cout << ans << endl;
}

Measured memory_bytes: 6420
#include<iostream>
#include<vector>
#include<string>
#define rep(i, start, end) for (int i = (int)start; i < (int)end; ++i)
#define rrep(i, start, end) for (int i = (int)start - 1; i >= end; --i)
#define iter(i, c) for (auto i = (c).begin(); i != (c).end(); ++i)
#define riter(i, c) for (auto i = (c).rbegin(); i != (c).rend(); ++i)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
using namespace std;
using ll = long long;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    string S;
    cin >> S;
    string week[7] = {"SUN","MON","TUE","WED","THU","FRI","SAT"};
    rep(i, 0, 7) {
        if (S == week[i]) {
            if (S == "SUN") cout << 7 << endl;
            else cout << 7 - i << endl;
            return 0;
        }
    }
    return 0;
}

Measured memory_bytes: 256
import sys

def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり

D = I()
c = [0] + LI()
s = [0] + [[0] + LI() for _ in range(D)]

last = [[0]*27 for _ in range(D+1)]
t = [0]

for i in range(1,D+1):
    r = 0
    manzoku = 0
    for j in range(1,27):
        m = s[i][j]
        for k in range(1,27):
            if k != j:
                m -= c[k]*(i-last[i-1][k])
            else:
                continue
        if j == 1:
            r = 1
            manzoku = m
        else:
            if manzoku < m:
                manzoku = m
                r = j
    t.append(r)
    for j in range(1,27):
        if j == r:
            last[i][j] = i
        else:
            last[i][j] = last[i-1][j]


dq = []
for i in range(1,D+1,5):
    for j in range(1,27):
        dq.append([i,j])

from copy import deepcopy

for d,q in dq:
    t0 = t[d]
    manzoku = s[d][q] - s[d][t0]
    for j in range(d,D+1):
        if j == d:
            last[d][t0] = last[d-1][t0]
            manzoku -= c[t0] * (d - last[d][t0])
            last[d][q] = d
            manzoku += c[q] * (d - last[d-1][q])
        else:
            if last[j][t0] == d:
                last[j][t0] = last[d-1][t0]
                manzoku -= c[t0] * (d - last[d][t0])
            if last[j][q] == last[d-1][q]:
                last[j][q] = d
                manzoku += c[q] * (d - last[d-1][q])
    if manzoku > 0:
        t[d] = q
    else:
        for j in range(d,D+1):
            if j == d:
                last[d][t0] = d
                last[d][q] = last[d-1][q]
            else:
                if last[j][t0] == last[d-1][t0]:
                    last[j][t0] = d
                if last[j][q] == d:
                    last[j][q] = last[d-1][q]

del t[0]

print(*t,sep='\n')

Measured memory_bytes: 70736
import scala.io.StdIn.readLine

object Main {

  def d(i:Int) = if(i<0) 15+i else i

  def getIndex(s:String) = s match {
    case "Rock" => 0 case "Fire" => 1 case "Scissors" => 2 case "Snake" => 3
    case "Human" => 4 case "Tree" => 5 case "Wolf" => 6 case "Sponge" => 7
    case "Paper" => 8 case "Air" => 9 case "Water" => 10 case "Dragon" => 11
    case "Devil" => 12 case "Lightning" => 13 case "Gun" => 14
  }

  val gestures = Array("Rock", "Fire", "Scissors", "Snake", "Human", "Tree", "Wolf", "Sponge", "Paper", "Air", "Water", "Dragon", "Devil", "Lightning", "Gun")

  def scan(list:Array[Int],i:Int,n:Int):String = {
    if(i==n) "Draw"
    else {
      val win = d(list((i+1)%n)-list(i))
      val j = if(i>0) i-1 else n-1
      val lose = d(list(i)-list(j))
      if(win<=7 && lose>7) gestures(list(i))
      else scan(list,i+1,n)
    }
  }

  def main(args:Array[String]) = {
    var n = 0
    while({n=readLine.trim.toInt;n}!=0) {
      val list = {for(i<-1 to n) yield getIndex(readLine.trim)}.toArray.sorted
      println(scan(list,0,list.length))
    }
  }
}

Measured memory_bytes: 55344
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
using ll = long long;
using pii = pair<int,int>;
using vi = vector<int>;
using vs = vector<string>;
using vll = vector<long long>;
using vpii = vector<pair<int,int>>;
using vivi = vector<vector<int>>;
const int dx[4] = {1,0,-1,0};
const int dy[4] = {0,1,0,-1};



int main(void) {
  int a,b;
  cin >> a >> b;
  if(a>9 || a<1 || b>9 || b<1) cout << -1 << endl;
  else cout << a*b << endl;
         
         
  
}


Measured memory_bytes: 256
import math

def main():
    n = input()

    p1 = [0., 0.]
    p2 = [100., 0.]
    a = [p1,p2]
    a = rec(a,n)

    for item in a:
        print item[0], item[1]
    
def rec(a,n):
    if n == 0:
        return a
    else:
        n -= 1
        b = []
        for i in range(len(a)-1):
            p1 = a[i]
            p2 = a[i+1]
            b += koch(p1,p2)
        b.append(a[-1])
        return rec(b,n)

def koch(p1,p2):
    s  = [p1[0]+(p2[0]-p1[0])/3.,    p1[1]+(p2[1]-p1[1])/3.]
    t  = [p1[0]+2.*(p2[0]-p1[0])/3., p1[1]+2.*(p2[1]-p1[1])/3.]
    st = [t[0]-s[0],t[1]-s[1]]
    u  = [s[0]+(st[0]-math.sqrt(3)*st[1])/2., s[1]+(math.sqrt(3)*st[0]+st[1])/2.]
    return [p1,s,u,t]
    
if __name__ == "__main__":
    main()

Measured memory_bytes: 6996
#include<iostream>
#include<algorithm>
#include<functional>
#include<cmath>
#include<string>
#include<vector>
using namespace std;
const int mod = 1000000007;
#define ll long long

int main()
{
	string S; cin >> S;
	for (int i = 0; i < S.size() - 1; i++)
	{
		if (S[i] == 'A' && S[i + 1] == 'C') {
			cout << "Yes" << endl;
			return 0;
		}
	}
	cout << "No" << endl;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main()
{
	unsigned long long int a,b,x,n;
	
	cin>>a>>b>>n;
	
	if(b==1)
		cout<<0;
	else if(n>=b)
	{
		cout<<(b-1)*a/b;
	}
	else
	{
		cout<<n*a/b;
	}
	
	return 0;
}


Measured memory_bytes: 3624
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define INF 100000000
using namespace std;
const int mod = 1000000007;

int main() {

  int N;
  bool ap=true;
  cin>>N;
  vector<int> A(N);
  for(int i=0; i<N; i++){
    cin>>A[i];
    if(A[i]%2==0){
      if(A[i]%3!=0&&A[i]%5!=0){
        cout<<"DENIED"<<endl;break;
      }
    }
    if(i==N-1)cout<<"APPROVED"<<endl;
  }
  //vector<vector<int>> A(N,vector<int>(M));
  //for(int i=0; i<N; i++){for(int j=0; j<M; j++){cin>>A[i][j];}}
  //sort(A.begin(),A.end());
  //for (int i = 0; i < N; i++) { maximum = max(maximum , A[i]);}
  //for (int i = 0; i < N; i++) { minimum = min(minimum , A[i]);}

}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for (int i = (a); i <= (b); ++ i)
#define rrp(i,a,b) for (int i = (a); i >= (b); -- i)
#define gc() getchar()
#define fir first
#define sec second
typedef pair<int,int> pii;
typedef long double db;
typedef long long ll;
template <typename tp>
inline void read(tp& x) {
  x = 0; char tmp; bool key = 0;
  for (tmp = gc(); !isdigit(tmp); tmp = gc())
    key = (tmp == '-');
  for (; isdigit(tmp); tmp = gc())
    x = (x << 3) + (x << 1) + (tmp ^ '0');
  if (key) x = -x;
}
template <typename tp>
inline void ckmn(tp& x,tp y) {
  x = x < y ? x : y;
}
template <typename tp>
inline void ckmx(tp& x,tp y) {
  x = x < y ? y : x;
}

const int N = 200010;
int len[N], n, ans;
map<int,int> mp;
bool check(int x) {
  mp.clear();
  rep (i, 1, n) {
    if (len[i] > len[i-1]) continue;
    int p = len[i];
    while (p >= 1 && mp[p] == x-1) -- p;
    if (p == 0) return false;
    ++ mp[p];
    map<int,int> :: iterator it = mp.find(p);
    ++ it;
    mp.erase(it, mp.end());
  }
  return true;
}
int main() {
  read(n);
  rep (i, 1, n) read(len[i]);
  int key = 1;
  rep (i, 2, n) if (len[i] <= len[i-1]) key = 0;
  if (key)
    return puts("1"), 0;
  int l = 2, r = n, ans = n;
  while (l <= r) {
    int mid = (l + r) >> 1;
    if (check(mid)) r = mid - 1, ans = mid;
    else l = mid + 1;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 1024
#include <stdio.h>

int main(){
   int n,m,a[100000],w[100000],i,p,ac,wa;
   char s[3];
 
   scanf("%d %d",&n,&m);
   for (i=0;i<n;i++) a[i]=w[i]=0;
   for (i=0;i<m;i++) {
      scanf("%d %s",&p,s);
      if (s[0]=='A') a[p-1]=1;
      else if (a[p-1]==0) w[p-1]++;
   }
   for (ac=wa=i=0;i<n;i++) 
      if (a[i]>0) {
         ac+=a[i];
         wa+=w[i];
      }
   printf("%d %d\n",ac,wa);
   return 0;
}


Measured memory_bytes: 896
#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 fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
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 (b<a) { a = b; return 1; } return 0; }
//---------------------------------------------------------------------------------------------------
/*---------------------------------------------------------------------------------------------------
　　　　　　　　　　　 ∧＿∧  
　　　　　 ∧＿∧ 　（´<_｀ ）　 Welcome to My Coding Space!
　　　　 （ ´_ゝ`）　/　 ⌒i     
　　　　／　　　＼　 　  |　|     
　　　 /　　 /￣￣￣￣/　　|  
　 ＿_(__ﾆつ/　    ＿/ .| .|＿＿＿＿  
　 　　　＼/＿＿＿＿/　（u　⊃  
---------------------------------------------------------------------------------------------------*/
 
 
 
 
 
int N, M;
int _E[707][707];
vector<int> E[707];
//---------------------------------------------------------------------------------------------------
int vis[707], col[707];
pair<int, int> dfs(int cu, int co = 0) {
    vis[cu] = 1;
    col[cu] = co;
 
    pair<int, int> res = { 0, 0 };
 
    if (co == 0) res.first++;
    else res.second++;
 
    fore(to, E[cu]) {
        if (vis[to]) {
            if (col[to] == co) return { -1, -1 };
        } else {
            auto p = dfs(to, 1 - co);
            if (p.first < 0) return { -1,-1 };
            res.first += p.first;
            res.second += p.second;
        }
    }
 
    return res;
}
//---------------------------------------------------------------------------------------------------
int dp[707][1007];
void _main() {
    cin >> N >> M;
    rep(i, 0, M) {
        int a, b; cin >> a >> b;
        a--; b--;
        _E[a][b] = _E[b][a] = 1;
    }
    rep(i, 0, N) rep(j, 0, N) if (!_E[i][j] and i != j) E[i].push_back(j);
 
    vector<pair<int, int>> v;
    rep(i, 0, N) if (!vis[i]) {
        auto p = dfs(i);
        if (p.first < 0) {
            printf("-1\n");
            return;
        }
        v.push_back(p);
    }
 
    int n = v.size();
    dp[0][0] = 1;
    rep(i, 0, n) rep(cn, 0, 707) if(dp[i][cn]) {
        dp[i+1][cn + v[i].first] = 1;
        dp[i+1][cn + v[i].second] = 1;
    }
 
    int ans = inf;
    rep(cn, 0, 707) if(dp[n][cn]) {
        int taka = cn;
        int hashi = N - cn;
        chmin(ans, taka * (taka - 1) / 2 + hashi * (hashi - 1) / 2);
    }
    cout << ans << endl;
}

Measured memory_bytes: 5120
#include <stdio.h>

int main(void){
	int a, b, c;
	int tmp;
	scanf("%d %d %d",&a, &b, &c);

	if(a > b){
		tmp = a;
		a = b;
		b = tmp;
	}
	if(b > c){
		tmp = b;
		b = c;
		c = tmp;
	}
	if(a > b){
		tmp = a;
		a = b;
		b = tmp;
	}

	printf("%d %d %d\n", a, b, c);
	return 0;
}

Measured memory_bytes: 596
#include <iostream>
using namespace std;
int main() {
    int k;
    int flag=0;
    cin>>k;
    int a,b;
    cin>>a>>b;
    for(int i=a;i<=b;i++)
    {
        if(i%k==0)
        {
            flag=1;
            break;
        }
    }
    if(flag==1)
        cout<<"OK"<<endl;
    else
        cout<<"NG"<<endl;
}


Measured memory_bytes: 3596
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int N = 1e5+5;
const ll p = 9901;
const ll mod = 1e9+7;
const double eps = 1e-8;
int n,m,k;
ll has[N];
vector<int>edg[N];
map<ll,ll>mp;
map<ll,ll>::iterator it;
void dfs(int u,int fa){
    has[u]=1;
    for(int v:edg[u]){
        dfs(v,u);
        has[u]=(has[u]+has[v]*p)%mod;
    }
    mp[has[u]]++;
}
int main()
{
    int u,v;
    scanf("%d",&n);
    for(int i=1;i<n;i++){
        scanf("%d%d",&u,&v);
        edg[u].push_back(v);
    }
    dfs(1,0);
    ll ans=0;
    for(it =mp.begin();it!=mp.end();it++){
        ans+=(it->second-1)*it->second/2;
    }
    printf("%lld\n",ans);
    return 0;
}

Measured memory_bytes: 23512
import java.math.BigInteger
import java.util.*
import kotlin.math.min

fun main() {

    val coins = arrayOf(2L,3L,5L) //61, 39, 27

    val sc = Scanner(System.`in`)
    val t = sc.nextInt()

    repeat(t) {
        val n = sc.nextLong()
        val costs = LongArray(3)
        costs[0] = sc.nextLong()
        costs[1] = sc.nextLong()
        costs[2] = sc.nextLong()
        val d = sc.nextLong()

        val cache = HashMap<Long,Long>()

        fun bestCost(v:Long, c:Int, p : Long, r:Long): Long {
            if(p == 0L){
                return r * d
            }
            val remainder = r * d
            val cost = costs[c] + remainder
            val diff = v - p
           // val costD = diff * d
            val b1 = BigInteger(cost.toString())
            val b2 = BigInteger(diff.toString()).multiply(BigInteger(d.toString()))
            if(b1 < b2) {
                return b1.toLong()
            } else {
                return b2.toLong()
            }
//            if(costD < 0)
//                return cost
//            return min(costD, cost)
        }

        fun solve(remain:Long): Long {
            if(remain == 0L)
                return 0L
            if(remain == 1L)
                 return d
            if(cache.contains(remain)) {
                return cache[remain]!!
            }
            var best = Long.MAX_VALUE
            for(i in coins.indices) {
                val c = coins[i]
                val p = remain / c
                val r = remain % c
                val up = p + 1L
                val ur = c - r
                best = min(best, bestCost(remain, i, p, r) + solve(p))
                if(ur == c) {
                    continue
                }
                best = min(best, bestCost(remain, i, up, ur) + solve(up))
            }
            cache[remain] = best
            return best
        }
        println(solve(n))

        // 0x1000 - 1
        // 0x0fff
        // 2^n
        // 0x1024 - 1
        // 0x100000
        // 0x0fffff & 0x03424
        //
    }


}

Measured memory_bytes: 75480
#pragma GCC optimize("Ofast")   //Comment optimisations for interactive problems (use endl)
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")
#include<bits/stdc++.h>

using namespace std;

#define  fastio         ios:: sync_with_stdio(0);cin.tie(0);cout.tie(0);cout<<fixed;cout<<setprecision(10);
#define  randomINIT     mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
#define  all(x)         (x).begin(),(x).end()
#define  mset(x,val)    memset(x,val,sizeof(x))
#define  endl           "\n"
#define  pb             push_back
#define  sym(s)         s="#"+s+"#";
#define  mp             make_pair
#define  s              second
#define  f              first
#define  dline          cerr<<"///REACHED///\n";
#define  debv(a)        for(auto it: a)cout<<it<<" ";cout<<endl;
#define  deb1(a)        cout<<a<<endl;
#define  deb2(a,b)      cout<<a<<" "<<b<<endl;
#define  deb3(a,b,c)    cout<<a<<" "<<b<<" "<<c<<endl;
#define  deb4(a,b,c,d)  cout<<a<<" "<<b<<" "<<c<<" "<<d<<endl;
#define  uniq(a)        a.resize(unique(a.begin(), a.end()) - a.begin());

typedef  long long             ll;
typedef  unsigned long long    ull;
typedef  long double           ld;
typedef  pair<ll,ll>           pll;
typedef  vector<ll>            vll;
typedef  vector<pll>           vpll;

const ll   MOD   =  1e+9+7;
const ll   INF   =  0x7f7f7f7f7f7f7f7f;
const int  INFi  =  0x7f7f7f7f;
const ll   N  =  3e+5+7;

vll adj[N];ll vis[N]={};
int dx8[]={0,1,1,1,0,-1,-1,-1}, dy8[]={1,1,0,-1,-1,-1,0,1};
int dx4[]={0,1,0,-1}, dy4[]={1,0,-1,0};

//<<-----Declare Variable Here------->>//
int t=1;
ll n,x,g;
//<<-----Implement Functions Here---->>//


//<<-----Start of Main--------------->>//
void MAIN(){
		cin>>n>>x>>g;
		if(n%x==0)cout<<n/x*g;
		else cout<<(n/x+1)*g<<endl;
}

int main(){
    fastio;randomINIT;

    //cin>>t;
    while(t--){
        MAIN();
    }

    #ifndef ONLINE_JUDGE
    cout<<"\nTime Elapsed: " << 1.0*clock() / CLOCKS_PER_SEC << " sec\n";
    #endif
}

Measured memory_bytes: 10668
s = input()
if len(s) != 26:
    x = sorted(set(map(chr, range(97, 123)))-set(s))
    print(s+x[0])
else:
    num = list(map(lambda x: ord(x)-ord('a'), s))
    for i in reversed(range(25)):
        L, R = i, i+1
        if num[L] < num[R]:
            tmp = 26
            for r in num[R:]:
                if num[L] < r:
                    tmp = min(tmp, r)
            ans = num[:L]+[tmp]
            print(''.join(map(lambda x: chr(x+ord('a')), ans)))
            break
    else:
        print(-1)


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

using namespace std;

typedef long long ll;

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

	int n;
	cin >> n;

	vector<ll> d(n);
	rep(i, n) cin >> d[i];

	ll ans = 0;
	for(int i = 0; i < n; i++){
		for(int j = i + 1; j < n; j++){
			ans += d[i] * d[j];
		}
	}

	cout << ans << endl;
}


Measured memory_bytes: 256
use std::io::*;
use std::str::FromStr;

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

fn main() {
    let s: String = read();
    let mut ans: String = String::new();

    for (i, v) in s.chars().enumerate() {
        if i % 2 == 0 {
            ans += &v.to_string()
        }
    }
    println!("{}", ans);
}


Measured memory_bytes: 4352
#include <stdio.h>
#include <string.h>

int main(void) {

  char s[200001];
  scanf("%s", s);
  int length = strlen(s);
  int s_count = 0;
  int operation = 0;
  for (int i = 0; i < length; i++) {
    if (s[i] == 'S') {
      s_count++;
    } else {
      if (s_count > 0) {
        operation++;
        s_count--;
      }
    }
  }
  int answer = length-operation*2;
  printf("%d\n", answer);

  return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
#define REP(i, n) for(long long i=0; i<n; i++)
#define REPR(i, n) for(long long i=n-1; i>=0; i--)
#define FOR(i, m, n) for(long long i=m; i<=n; i++)
#define FORR(i, m, n) for(long long i=m; i>=n; i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define VSORTR(v) sort(v.rbegin(), v.rend());
#define ALL(v) (v).begin(),(v).end()
#define FIN ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using P = pair<ll, ll>;
const ll mod = 1e9+7;
const ll inf = 1e15;


int main(){FIN
 
    ll n;cin>>n;
    vll p(n), q(n);
    REP(i,n) cin>>p[i];
    REP(i,n) cin>>q[i];
    if (p[0]>q[0]) p.swap(q);
    ll cnt=0;
    do{
        bool same = true;
        REP(i,n) if(p[i]!=q[i]) same=false;
        if(same) break;
        cnt++;

    }while(next_permutation(ALL(p)));
    cout<<cnt<<endl;
    return 0;
}

Measured memory_bytes: 256
/* ex7_1
   reo012 */

#include<stdio.h>

typedef struct point{
    int x_elem;     //x座標
    int y_elem;     //y座標
}point;

//point a,bに対して、bを中心にaを時計回りに90度回転した点cを求める関数
point turn_90(point a, point b){
    int delta_x, delta_y;
    point c;
    delta_x = b.x_elem - a.x_elem;  //aからbになったときのxの変化量
    delta_y = b.y_elem - a.y_elem;  //aからbになったときのyの変化量
    c.x_elem = b.x_elem - delta_y;  //(cのx座標)=(bのx座標)-(yの変化量)
    c.y_elem = b.y_elem + delta_x;  //(cのy座標)=(bのy座標)+(xの変化量)
    return c;
}

int main(void){
    int x1, x2, y1, y2;
    point p1, p2, p3, p4;
    //入力
    scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
    //p1,p2にx,y座標を代入
    p1.x_elem = x1;
    p1.y_elem = y1;
    p2.x_elem = x2;
    p2.y_elem = y2;

    p3 = turn_90(p1, p2);   //turn_90関数でp1,p2からp3を求める
    p4 = turn_90(p2, p3);   //turn_90関数でp2,p3からp4を求める
    //出力
    printf("%d %d %d %d\n", p3.x_elem, p3.y_elem, p4.x_elem, p4.y_elem);
    return 0;
}


Measured memory_bytes: 1732
#include <bits/stdc++.h>//Carefully Crafted by hetp111
using namespace std;
#define int long long
#define double long double
#define all(v) (v).begin(),(v).end()
#define vi vector<int>
#define pii pair<int,int>
#define prec(n) fixed<<setprecision(n)
#define MOD 1000000007
#define eps 1e-8
#define FASTER ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
template<class A, class B> ostream& operator<<(ostream& out, const pair<A, B> &a){
    return out<<"("<<a.first<<","<<a.second<<")";}
template<class A> ostream& operator<<(ostream& out, const vector<A> &a){
	out<<"";for(auto it=a.begin();it!=a.end();it++){if(it!=a.begin())out<<" ";out<<*it;}out<<"";
	return out;}
template<class A, class B> istream& operator>>(istream& in, pair<A,B> &a){in>>a.first>>a.second;return in;}
template<class A> istream& operator>>(istream& in, vector<A> &a){for(A &i:a)in>>i;return in;}
//ifstream cinn("input.txt");ofstream coutt("output.txt");



signed main(){
    FASTER;
    int l,r;cin>>l>>r;

    if(r-l>2019){
        cout<<0;
    }else{
        int ans=INT_MAX;
        for(int i=l;i<=r;i++){
            for(int j=i+1;j<=r;j++){
                ans=min(ans,(i*j)%2019);
            }
        }
        cout<<ans;
    }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define REP(i,m,n) for(int i=(int)(m); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define RREP(i,m,n) for(int i=(int)(m); i>=(int)(n); i--)
#define rrep(i,n) RREP(i,n-1,0)
#define all(v) v.begin(), v.end()
const int inf = 1e9+7;
const ll longinf = 1LL<<60;
const ll mod = 1e9+7;

ll gcd(ll x, ll y) {
  if(x > y)
    return gcd(y, x);
  else if(x == 0)
    return y;
  else
    return gcd(y % x, x);
}
ll lcm(ll x, ll y) {
  ll g = gcd(x, y);
  return g * (x / g) * (y / g);
}
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  ll a, b;
  cin >> a >> b;
  cout << lcm(a, b) << "\n";
  return 0;
}


Measured memory_bytes: 3620
#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <algorithm>
#include <bitset>
#include <tuple>
#include <set>
#include <map>
#define range(i, r) for(int i=0;i<r;i++)
#define ranges(i, l, r) for(int i=l;i<r;i++)
#define vv(a, b, c, d) vector<vector<d> >(a, vector<d>(b, c))
#define vvi std::vector<std::vector<int> >
#define vvl std::vector<std::vector<ll> >
#define MODs 1000000007;
#define MODn 1000000009;
typedef long long int ll;
using namespace std;

int main(int argc, char const *argv[]) {
  ll N, A, B, C, D;
  std::cin >> N >> A >> B >> C >> D;
  string S;
  std::cin >> S;
  S = " " + S;
  if((A-B)*(C-D)>=0){
    for(int i=A+1;i<C;i++){
      if(S[i]=='#'&&S[i-1]=='#'){
        std::cout << "No" << '\n';
        return 0;
      }
    }
    for(int i=B+1;i<D;i++){
      if(S[i]=='#'&&S[i-1]=='#'){
        std::cout << "No" << '\n';
        return 0;
      }
    }
    std::cout << "Yes" << '\n';
  }else{
    for(int i=A+1;i<C;i++){
      if(S[i]=='#'&&S[i-1]=='#'){
        std::cout << "No" << '\n';
        return 0;
      }
    }
    for(int i=B+1;i<D;i++){
      if(S[i]=='#'&&S[i-1]=='#'){
        std::cout << "No" << '\n';
        return 0;
      }
    }
    for(int i=max(A, B);i<=min(C, D);i++){
      if(S[i]=='.'&&S[i+1]=='.'&&S[i-1]=='.'){
        std::cout << "Yes" << '\n';
        return 0;
      }
    }
    std::cout << "No" << '\n';
    return 0;
  }
  return 0;
}


Measured memory_bytes: 888
import java.util.Scanner;

class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		long N = sc.nextLong();

		// 文字列の長さを求める
		long[] max = new long[12];
		int l = 1;
		max[l] = 26;
		while(N > max[l]) {
			l++;
			max[l] = (max[l - 1] + 1) * 26;
		}


		// l桁の範囲で、元の数字をa~zを0~25の26進数として変換する
		N = N - max[l - 1] - 1;
		char[] c = new char[l];
		for (int i = 0; i < l; i++) {
			c[i] = (char)('a' + (N % 26));
			N /= 26;
		}
		for (int i = l - 1; i >= 0; i--) {
			System.out.print(c[i]);
		}
		System.out.println();
	}
}


Measured memory_bytes: 35788
#include<stdio.h>
main(){
  int i,n=0,q=0,c[512],a=0,b=0;
  char s[1024],t[512][32],*p;
  fgets(s,1024,stdin);
  for(;;){
    p=strchr(s+q,' ');
    if(!p)
      p=s+strlen(s)-1;
    strncpy(t[n],s+q,p-s-q);
    for(i=0;i<n;i++)
      if(strcmp(t[i],t[n])==0){
	c[i]++;
	break;
      }
    if(i==n){
      c[i]=1;
      n++;
    }
    q=p-s+1;
    if(p==s+strlen(s)-1)
      break;
  }
  for(i=1;i<n;i++){
    if(c[i]>c[a])
      a=i;
    if(strlen(t[i])>strlen(t[b]))
      b=i;
  }
  printf("%s %s\n",t[a],t[b]);
  return 0;
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
ll gcd(ll a,ll b){return b!=0?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}

int main(){
    ll n,m,s=0;
    cin>>n>>m;
    vector<ll> x(m),d(m-1);
    for(ll i=0;i<m;i++) cin>>x[i];
    sort(all(x));
    for(ll i=0;i<m-1;i++) d[i]=x[i+1]-x[i];
    sort(all(d));
    for(ll i=0;i<m-n;i++) s+=d[i];
    cout<<s<<endl;
    return 0;
}

Measured memory_bytes: 1792
n=int(input())
a=list(map(int,input().split()))
d={}
sei=[]
tyo=[]
for s in a:
  if s not in d:
    d[s]=0
  d[s]+=1
  
for t in a:
  if d[t]>=2:
    tyo.append(t)
  if d[t]>=4:
    sei.append(t)
  d[t]=0
  
if len(sei)==0 and len(tyo)<=1:
  print(0)
  
else:
  tyos=0
  seis=0
  if len(tyo)>1:
    tyo=sorted(tyo)
    tyos+=tyo[-1]*tyo[-2]
  if len(sei)>0:
    sei=sorted(sei)
    seis+=sei[-1]**2
    
  print(max(tyos,seis))

Measured memory_bytes: 21656
import sys
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
read = sys.stdin.buffer.read
sys.setrecursionlimit(10 ** 7)

A, B, C = map(int, readline().split())

if A == B and B == C and A % 2 == 0:
    print(-1)
    exit()

ans = 0
while True:
    if A % 2 == 1 or B % 2 == 1 or C % 2 == 1:
        break
    half_A = A // 2
    half_B = B // 2
    half_C = C // 2

    A = half_B + half_C
    B = half_A + half_C
    C = half_A + half_B
    ans += 1

print(ans)

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

#define printl(s) cout << s << endl;
#define rep(i,n) for(int i=0;i<(n);i++)
using ll = long long;
using vvi = vector<vector<int>>;
using pii = pair<int,int>;

const ll modSeed = pow(10,9) + 7;
const int INF = 1'000'000'000;

template <typename T>
vector<T> getVector(ll num){
    vector<T> values(num);
    for(ll i=0;i<num;i++){
        cin >> values.at(i);
    }
    return values;
}

string S;
int N,ans;

bool check(vector<pii> evi, int i){
  for(int j=0;j<(int)evi.size();j++){
    if( (i&(1<<evi[j].first)) && (evi[j].second==0)) return false;
    if( !(i&(1<<evi[j].first)) && (evi[j].second==1)) return false;  
  }
  return true;
}

int main(){
  ans = 0;
  cin >> N;
  vector<vector<pii>> evi(N);
  for(int i=0;i<N;i++){
    int A;
    cin >> A;
    evi[i].resize(A);
    rep(j,A){
      int x,y;
      cin >>x>>y;
      evi[i][j] = make_pair(x-1,y);
    }
  }
  for(int i=0;i<(1<<N);i++){
    bool flg = true;
    for(int j=0;j<N;j++){
      if(!(i &(1<<j))) continue;
      if(!check(evi[j],i)){
        flg = false;
        break;
      }
    }
    if(flg){
      bitset<15> s(i);
      int num = s.count();
      ans = max(ans,num);
    }
  }

  printl(ans);
}


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

int main() {
	string S; cin >> S;
	map<char, int> mp;
	for(int i=0; i<26; ++i) mp['a'+i]=0;
	bool f=true;
	for(int i=0; i<S.size(); ++i){
	    if(mp[S[i]]){
	        f=false;
	        break;
	    }
	    else ++mp[S[i]];
	}
	if(f) cout << "yes" << endl;
	else cout << "no" << endl;
	return 0;
}


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

struct node{
  int key;
  struct node *prev, *next;
};

typedef struct node Node;

Node *nil;

void init(){
  nil = (Node *)malloc(sizeof(Node));
  nil->prev = nil;
  nil->next = nil;
}

void insert(int key){
  Node *x = (Node *)malloc(sizeof(Node));
  x->key = key;
  x->next = nil->next;
  nil->next->prev = x;
  nil->next = x;
  x->prev = nil;
}

Node* listSearch(int key){
  Node *cur = nil->next;
  while ( cur != nil && cur->key != key ){
    cur = cur->next;
  }
  return cur;
}

void deleteNode(Node *t){
  if (t == nil) return;
  t->prev->next = t->next;
  t->next->prev = t->prev;
  free(t);
}

void deleteFirst(){
  deleteNode(nil->next);
}

void deleteLast(){
  deleteNode(nil->prev);
}

void deleteKey(int key){
  deleteNode(listSearch(key));
}

int main(void){
  int n, i, a, b = 0;
  char s[100];
  scanf("%d",&n);
  init();
  for(i=0;i<n;i++){
    scanf("%s",s);
    if(s[0] == 'd'){
      if(s[6] == 'F') deleteFirst();
      else if(s[6] == 'L') deleteLast();
      else {
        scanf("%d",&a);
        deleteKey(a);
      }
    }
    else {
      scanf("%d",&a);
      insert(a);
      b++;
    }
  }
  printf("%d",nil->next->key);
  Node *c = nil->next->next;
  while(c != nil){
    printf(" %d",c->key);
    c = c->next;
  }
  printf("\n");
  return 0;
}

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

using namespace std;

typedef long long ll;

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

	int n;
	cin >> n;

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

	sort(d.begin(), d.end());

	cout << d[n/2] - d[n/2-1]<< endl;
}


Measured memory_bytes: 640
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <cmath>
#include <algorithm>

using namespace std;

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

    cin >> N;

    if(N == 1){
        cout << "Hello World" << endl;
        return 0;
    }
    if(N == 2){
        cin >> A >> B;
        cout << (A + B) << endl;
    }

    return 0;
}

Measured memory_bytes: 256
import numpy as np

N, M, C = map(int, input().split())
B = list(map(int, input().split())) 
A = np.zeros((N,M))



for i,_ in enumerate(A):
    A[i:] = list(map(int, input().split())) 

cnt = 0
z = 0
for A_line in A:
    for i,a in enumerate(A_line):
        z = z + a*B[i]
    if z+C >0:
        cnt += 1
    z = 0

print(cnt)

Measured memory_bytes: 12396
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <math.h> // sqrt
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <iomanip> // setprecision
using namespace std;
using ll = long long;
using ld = long double;
using vi = vector<int>;
using vb = vector<bool>;
using vll = vector<long long>;
using pii = pair<int, int>;
using psi = pair<string, int>;

ll minusn(ll n) {
    if (n % 2 == 0) {
        return 1;
    }
    return -1;
}

int main() {
    ll A, B, C, K;
    cin >> A >> B >> C >> K;
    if (K == 0) {
        cout << A - B << endl;
        return 0;
    }
    if (K == 1) {
        cout << B - A << endl;
        return 0;
    }
    if (A == B && B == C) {
        cout << 0 << endl;
        return 0;
    }
    ll i, j;
    i = 2 * minusn(K - 2);
    j = minusn(K - 1);
    ll ans = i * (A - B) + j * (B - A);
    cout << ans / 3 << endl;
}

Measured memory_bytes: 3620
#pragma GCC optimize ("O3")
#include <iostream>
#include <iomanip>
#include <istream>
#include <ostream>
#include <sstream>
#include <iterator>
#include <vector>
#include <algorithm>
#include <queue>
#include <deque>
#include <list>
#include <stack>
#include <map>
#include <unordered_map>
#include <set>
#include <bitset>
#include <utility>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <string>
#include <ctime>
#include <cctype>
#include <cstdlib>
#define IINF 10e8
#define INF 1<<30
#define MOD 1000000007
#define mod 998244353
#define REP(i, a, n) for (ll i = a; i < (ll)(n); i++)
#define REPE(i, a, n) for (ll i = a; i <= (ll)(n); i++)
#define Endl endl
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define eb emplace_back
#define mmax(x,y)(x>y?x:y)
#define mmin(x,y)(x<y?x:y)
#define chmax(x,y) x=mmax(x,y)
#define chmin(x,y) x=mmin(x,y)
#define all(x) (x).begin(),(x).end()
#define siz(x) (ll)(x).size()
#define PI acos(-1.0)
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;
typedef pair<int,int>Pin;
typedef pair<ll,ll>Pll;
template<class T> using V=vector<T>;
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;}
int dx[4]={-1,0,1,0};
int dy[4]={0,-1,0,1};
int ddx[8]={-1,0,1,0,1,1,-1,-1};
int ddy[8]={0,-1,0,1,1,-1,1,-1};
ll cmp(pair<ll,ll>a,pair<ll,ll> b){
        if(a.se!=b.se)
        return a.se<b.se;
        else
        return a.fi<b.fi;
}
//----------------------------------------------------------------------
int dp[310][310];
//----------------------------------------------------------------------
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    //-------------------------------  
    //ll begin_time=clock();
    //-------------------------------
    int n;cin>>n;
    while(n){
        V<int>a(n);
        for(int i=0;i<n;i++)cin>>a[i];
        int ans=0;
        memset(dp,0,sizeof(dp));
        for(int len=2;len<=n;len++){
            for(int i=0;i<n;i++){
                int j=i+len-1;
                if(j>=n)continue;
                if(dp[i+1][j-1]==len-2){
                    if(abs(a[i]-a[j])<=1){
                        chmax(dp[i][j],len);
                    }
                }
                for(int k=i;k<j;k++){
                    chmax(dp[i][j],dp[i][k]+dp[k+1][j]);
                }
            }
        }

        cout<<dp[0][n-1]<<endl;
        cin>>n;
    }
    //-------------------------------  
    //ll end_time=clock();cout<<"time="<<end_time-begin_time<<"ms"<<endl;
    //-------------------------------
    return 0;
}
//----------------------------------------------------------------------





























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

#define rep(i,n) for(int i=0;i<(n);++i)
#define reps(i,n) for(int i=1;i<=(n);++i)
#define repr(i,n) for(int i=(n);i>=0;--i)
#define int long long
#define itn int
#define pb push_back
#define m_p make_pair
#define m_t meke_tuple
#define p_p(a,b) pb(m_p(a,b))
#define all(a) a.begin(),a.end()
#define SORT(a) sort(all(a))
#define RSORT(a) sort(all(a));reverse(all(a))
#define UNIQUE(a) a.erase(unique(all(a)),a.end())
#define SZ(a) (ll)(a.size())
#define ENDL cout<<endl
#define debg(a) cout<<#a<<" "<<a<<endl;
#define call(a) for(auto i:a)cout<<i<<" ";cout<<endl
#define show(a) rep(ghf,SZ(a)){rep(kjh,SZ(a[ghf])){cout<<(a[ghf][kjh]<10?" ":"")<<a[ghf][kjh]<<" ";}ENDL;}
#define out(a) cout<<(a)<<endl
#define fi first
#define se second
#define Vec vector
#define P pair
typedef long long ll;
typedef string str;
typedef vector<ll> V;
typedef pair<ll,ll> Pi;
typedef vector<Pi> VP;
const long long INF = 1LL<<60;
const long long MOD = 1e9+7;
int gcd(int a,int b){if(b==0)return a;return gcd(b,a%b);}
int lcm(int a,int b){return a/gcd(a,b)*b;}
int max(int a,int b){if(a>b)return a; return b;}
int min(int a,int b){if(a>b)return b; return a;}
void Yes(){cout<<"Yes"<<endl;}
void No(){cout<<"No"<<endl;}
void YN(bool b){cout<<(b?"Yes":"No")<<endl;}
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}
template<class T>bool chmin(T &a,const T &b){if(a>b){a=b;return true;}return false;}

signed main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  int n;
  str s;
  cin>>n>>s;
  int a=0,b=0;
  V left(n+1,0),right(n+1,0);
  rep(i,n){
    if(s[i]=='(')a++;
    else{
      b++;
      if(a>0){
        a--;
        b--;
      }
    }
  }
  rep(i,b)s='('+s;
  rep(i,a)s=s+')';
  out(s);
  
  
  
  return 0;
}



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

#define dump(...) do{print_vars(cout<<"# "<<#__VA_ARGS__<<'=',__VA_ARGS__);cout<<endl;}while(0)
#define repi(i,a,b) for(int i=int(a);i<int(b);i++)
#define peri(i,a,b) for(int i=int(b);i-->int(a);)
#define rep(i,n) repi(i,0,n)
#define per(i,n) peri(i,0,n)
#define all(c) begin(c),end(c)
#define mp make_pair
#define mt make_tuple

using uint=unsigned;
using ll=long long;
using ull=unsigned long long;
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using vd=vector<double>;
using vvd=vector<vd>;
using vs=vector<string>;

void print_vars(ostream&){}
template<typename Car,typename... Cdr>
void print_vars(ostream& os,const Car& car,const Cdr&... cdr){
	print_vars(os<<car<<(sizeof...(cdr)?",":""),cdr...);
}

template<typename T1,typename T2>
ostream& operator<<(ostream& os,const pair<T1,T2>& p){
	return os<<'('<<p.first<<','<<p.second<<')';
}

template<int I,typename Tuple>
void print_tuple(ostream&,const Tuple&){}
template<int I,typename Car,typename... Cdr,typename Tuple>
void print_tuple(ostream& os,const Tuple& t){
	os<<get<I>(t)<<(sizeof...(Cdr)?",":"");
	print_tuple<I+1,Cdr...>(os,t);
}
template<typename... Args>
ostream& operator<<(ostream& os,const tuple<Args...>& t){
	print_tuple<0,Args...>(os<<'(',t);
	return os<<')';
}

template<typename Ch,typename Tr,typename C>
basic_ostream<Ch,Tr>& operator<<(basic_ostream<Ch,Tr>& os,const C& c){
	os<<'[';
	for(auto i=begin(c);i!=end(c);++i)
		os<<(i==begin(c)?"":" ")<<*i;
	return os<<']';
}

constexpr int INF=1e9;
constexpr int MOD=1e9+7;
constexpr double EPS=1e-9;

struct UnionFind{
	vi data;
	UnionFind(int n):data(n,-1){}
	int Find(int i){
		return data[i]<0?i:(data[i]=Find(data[i]));
	}
	bool Unite(int a,int b){
		a=Find(a),b=Find(b);
		if(a==b) return false;
		if(-data[a]<-data[b]) swap(a,b);
		data[a]+=data[b];
		data[b]=a;
		return true;
	}
	int Size(int i){
		return -data[Find(i)];
	}
};

int main()
{
	#ifndef _GLIBCXX_DEBUG
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	constexpr char endl='\n';
	#endif

	for(ll n,m;cin>>n>>m&&n|m;){
		UnionFind uf(2*n);
		rep(i,m){
			int u,v; cin>>u>>v; u--,v--;
			uf.Unite(u,n+v);
			uf.Unite(n+u,v);
		}
		bool bipartite=uf.Find(0)!=uf.Find(n);
		if(bipartite){
			ll l=0;
			rep(i,n) l+=uf.Find(0)==uf.Find(i);
			ll r=n-l;
			cout<<l*r-m<<endl;
		}
		else
			cout<<n*(n-1)/2-m<<endl;
	}
}


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

int n;
int d[110];

const int vmax=499*100+1;
int dp[110][vmax];
int dp2[110][vmax];

int main(void){
	while(cin >> n,n){
		rep(i,n) cin >> d[i];
		rep(i,n+1)rep(j,vmax) dp[i][j]=-1,dp2[0][0]=0;
		dp[0][0]=0;
		rep(i,n)rep(j,vmax){
			if(dp[i][j]==-1) continue;
			if(dp[i+1][j]<dp[i][j]||(dp[i][j]==dp[i+1][j]&&dp2[i][j]<dp2[i+1][j])){
				dp[i+1][j]=dp[i][j];
				dp2[i+1][j]=dp2[i][j];
			}
			int next=dp[i][j];
			int next2=dp2[i][j]+d[i];
			int change=(5000-d[i])%1000;
			int nj=j+change;
			if(nj>=500) next++,nj-=500;
			if(dp[i+1][nj]<next||(next==dp[i+1][nj]&&next2<dp2[i+1][nj])){
				dp[i+1][nj]=next;
				dp2[i+1][nj]=next2;
			}
		}
		int ans=0,ans2=0;
		rep(j,vmax){
			if(ans<dp[n][j]||(dp[n][j]==ans&&dp2[n][j]<ans2)){
				ans=dp[n][j];
				ans2=dp2[n][j];
			}
		}
		cout << ans << " " << ans2 << endl;
	}
}

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

string Ticket(string S, int N){
  if(S.size() == 1){
    if (stoi(S) == N) {
      return S;
    }
    return "";
  }
  
  int l = S.size();
  string Last = "";
  Last.push_back(S.at(l-1));
  string Sp = S.erase(l-1);
  string a = Ticket(Sp, N - stoi(Last));
  string b = Ticket(Sp, N + stoi(Last));

    if ( a.size() > 0 ){
      return Ticket(Sp, N - stoi(Last)) + "+" + Last;
    }
    else if ( b.size() > 0 ) {
      return Ticket(Sp, N + stoi(Last)) + "-" + Last;
    }

  return "";
}

int main() {
  string St;
  cin >> St;
  
  cout << Ticket(St,7) << "=7" << endl;
  
  return 0;
}


Measured memory_bytes: 3596
function Main(input) {
  input = input.split('\n')
  var N = parseInt(input[0])
  var a = input[1].split(' ').map(x => parseInt(x))

  var answer = 0

  for (var i = 0; i < N; i++) {
    while (Number.isInteger((a[i] = a[i] / 2))) {
      answer++
    }
  }

  console.log(answer)
}

Main(require('fs').readFileSync('/dev/stdin', 'utf8'))


Measured memory_bytes: 10444
#include<iostream>
#include<vector>
#include<algorithm>
#include<cctype>
#include<utility>
#include<string>
#include<cmath>
#include<cstring>

#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)
#define INF 1000000000
using namespace std;
typedef pair<int, int> P;
typedef pair<llong, llong> LP;
typedef pair<int, P> PP;
typedef pair<llong, LP> LPP;



int dp[22][50010];

int main(){

   REP(i,22){
       REP(j,50010){
           dp[i][j] = INF;
       }
   }

    int n,m;
    cin >> n >> m;
    vector<int> c(m,0);
    REP(i,m){
        cin >> c[i];
    }

    //dp[i][j]:i番目までを使って総和がjとなるような枚数の最小

    dp[0][0] = 0;//0番目までで総和が0の枚数
    

    for(int i = 1;i <= c.size();i++){
        //cout << c[i-1] << endl;
        for(int j = 0;j <= n;j++){
            
            if(c[i-1] > j){//c[i]を使えない場合
                dp[i][j] = dp[i-1][j];
            }else{//c[i]を使う場合
                dp[i][j] = min(dp[i-1][j],dp[i][j-c[i-1]]+1);
            }
        }
    }

    cout << dp[c.size()][n] << endl;   

    return 0;
}


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

int main() {
  int tcase;
  
  cin >> tcase;
  while(tcase--) {
    string A, B, C = "";
    cin >> A >> B;
    
    unsigned sz = max(A.size(), B.size());
    while(A.size()<sz) A = '0' + A;
    while(B.size()<sz) B = '0' + B;

    int c = 0;
    for(int i=sz-1; i>=0; i--) {
      // 確定情報
      C += (( (A[i]-'0') + (B[i]-'0') + c ) % 10 + '0');
      // 前座
      c = ( (A[i]-'0') + (B[i]-'0') + c ) / 10;
    }
    if(c>0) C += (c + '0');
    
    reverse(C.begin(), C.end());
    if(C.size() > 80) cout << "overflow" << endl;
    else cout << C << endl;
  }
  return 0;
}

Measured memory_bytes: 1220