akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define ALL(A) (A).begin(), (A).end()
#define ll long long
#define rep(i, n) for (int i = 0; i < (n); i++)

const ll mod = 1e9 + 7;
const ll INF = -1 * ((1LL << 63) + 1);
const int inf = -1 * ((1 << 31) + 1);

using namespace std;

int main(void){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    ll a,b,c,k;
    cin >> a >> b >> c >> k;
    ll ans = 0;
    if(k%2==0)ans = a-b;
    else ans = b-a;
    if(abs(ans)>1e18)cout << "unfair" << endl;
    else cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
    using namespace std;
     
    long long A, B, C, D;
     
    long long gcd(long long a, long long b) {
    	if (b == 0) return a;
    	return gcd(b, a % b);
    }
     
    long long solve(long long N) {
    	long long r = N;
    	long long r1 = N / C;
    	long long r2 = N / D;
    	long long r3 = N / (C * D / gcd(C, D));
    	return r - r1 - r2 + r3;
    }
     
    int main() {
    	cin >> A >> B >> C >> D;
    	cout << solve(B) - solve(A - 1) << endl;
    	return 0;
    }

Measured memory_bytes: 256
#include <bits/stdc++.h>
using i64 = long long;

int main() {
    std::string s;
    i64 k;
    std::cin >> s >> k;
    std::vector<std::pair<char, i64>> v;
    for (auto c : s) {
        if (v.empty() || v.back().first != c) v.emplace_back(c, 1);
        else v.back().second++;
    }

    i64 ret = 0;
    if (v.size() == 1) {
        ret += s.size() * k / 2;
    } else if (v.back().first == v.front().first) {
        ret += v.back().second / 2 + v.front().second / 2 + (v.back().second + v.front().second) / 2 * (k - 1);
        for (int i = 1; i + 1 < v.size(); i++) {
            ret += v[i].second / 2 * k;
        }
    } else {
        for (auto &e : v) ret += e.second / 2 * k;
    }

    std::cout << ret << std::endl;

    return 0;
}


Measured memory_bytes: 256
package main

import (
  "bufio"
  "os"
  "strconv"
  "strings"
  "fmt"
  "container/heap"
)

var reader = bufio.NewReaderSize(os.Stdin, 1000000)
var writer = bufio.NewWriter(os.Stdout)
func NextLine() string {
  buffer := make([]byte, 0)
  for true {
    line, isPrefix, err := reader.ReadLine()
    if err != nil { panic(err) }
    buffer = append(buffer, line...)
    if !isPrefix { break }
  }
  return string(buffer)
}
func NextInt() int {
  n, _ := strconv.Atoi(NextLine())
  return n
}
func NextIntVec() []int {
  L := strings.Split(NextLine(), " ")
  N := make([]int, len(L))
  for i := range N {
    N[i], _ = strconv.Atoi(L[i])
  }
  return N
}
func Write(s interface{}) {
  fmt.Fprintln(writer, s)
}
func Output() {
  _ = writer.Flush()
}

type Item struct {
  Comparison  int
  R       int
}
type PriorityQueue []*Item
func (pq PriorityQueue) Len() int { return len(pq) }
func (pq PriorityQueue) Less(i, j int) bool {
  return pq[i].Comparison < pq[j].Comparison
}
func (pq PriorityQueue) Swap(i, j int) {
  pq[i], pq[j] = pq[j], pq[i]
}
func (pq *PriorityQueue) Pop() interface{} {
  old := *pq
  n := len(old)
  item := old[n - 1]
  *pq = old[0:n - 1]
  return item
}
func (pq *PriorityQueue) Push(x interface{}) {
  item := x.(*Item)
  *pq = append(*pq, item)
}

func main() {
  NM := NextIntVec()
  N, M := NM[0], NM[1]
  RC := make([][][]int, N)
  for i := range RC {
    RC[i] = make([][]int, 0)
  }
  for i := 0; i < M; i++ {
    LRC := NextIntVec()
    L, R, C := LRC[0] - 1, LRC[1] - 1, LRC[2]
    RC[L] = append(RC[L], []int{R, C})
  }
  D := make([]int, N)
  for i := range D {
    if 0 < i { D[i] = -1 }
  }
  var PQ PriorityQueue
  for i := 0; i < N - 1; i++ {
    if D[i] < 0 { break }
    for _, rc := range RC[i] {
      heap.Push(&PQ, &Item{D[i] + rc[1], rc[0]})
    }
    for 0 < len(PQ) {
      pq := heap.Pop(&PQ).(*Item)
      if pq.R < i + 1 { continue }
      D[i + 1] = pq.Comparison
      heap.Push(&PQ, pq)
      break
    }
  }
  Write(D[N - 1])
  Output()
}

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

using namespace std;
int main(int argc, char *argv[]) {
	string s;
	cin >> s;
	
	string d[] = {"SUN", "MON", "TUE", "WED", "THU", "FRI", "SUT"};

	int i;
	for (i = 0; i < 7; i++) {
		if (s == d[i]) {
			break;
		}
	}
	int ct = 1;
	for (int j = i + 1; j < 7; j++) {
		if (d[j] == "SUN") {
			break;
		}
		ct += 1;
	}
	
	cout << ct << endl;
}

Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<iostream>
std::string x = "";
int main()
{
	char c;
	while((c = getchar()) != '\n')
		if(c != 'B') x += c;
		else if(!x.empty()) x.erase(x.size() - 1);
	std::cout << x << std::endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std ;
#define ll long long 
#define all(x) x.begin(),x.end()

int const N = 2e5;
int n , cap;
vector<int>w,v;
vector<ll>dp;

ll go(){
	     for(int i = 0; i < n; i++)
	       	for(ll j = cap; j >= w[i]; --j)
			         dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
	     return dp[cap];
}

int main(){
     scanf("%d%d",&n,&cap);
     v.resize(n),w.resize(n),dp.resize(N);
     for(int i=0;i<n;++i)
       scanf("%d%d",&w[i],&v[i]);
     
	      printf("%lld\n",go());

	   return 0 ; 
}

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

typedef long long int ll;
typedef pair<ll, ll> pll;

#define FOR(i, n, m) for (ll(i) = (m); (i) < (n); ++(i))
#define REP(i, n) FOR(i, n, 0)
#define OF64 std::setprecision(10)

const ll MOD = 1000000007;
const ll INF = (ll)1e15;

ll A[1005];
int main()
{
    ll N;
    cin >> N;
    REP(i, N)
    {
        cin >> A[i];
    }

    double sum = 0;
    REP(i, N)
    {
        sum += (double)(1.0 / double(A[i]));
    }

    cout << OF64 << 1.0 / sum << endl;
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>

#define Max 100
#define Min 1
#define AMAX 100

int main(){
  int i,n,A[AMAX],flag=1,tmp,cnt=0;

  scanf("%d",&n);

  if(n >= Min && n <= Max)
    for(i=0; i<n; i++)
      scanf("%d",&A[i]);

  while(flag){
    flag=0;
    for(i=n-1; i>=1; i--){
      if(A[i] < A[i-1]){
	tmp = A[i];
	A[i] = A[i-1];
	A[i-1] = tmp;
	cnt++;
	flag = 1;
      }
    }
  }

  for(i=0; i<n; i++)
    if(i == n-1) printf("%d\n",A[i]);
    else printf("%d ",A[i]);

  printf("%d\n",cnt);

  return 0;
}
	

  



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

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

typedef int _loop_int;
#define REP(i,n) for(_loop_int i=0;i<(_loop_int)(n);++i)
#define FOR(i,a,b) for(_loop_int i=(_loop_int)(a);i<(_loop_int)(b);++i)
#define FORR(i,a,b) for(_loop_int i=(_loop_int)(b)-1;i>=(_loop_int)(a);--i)

#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define DEBUG_VEC(v) cout<<#v<<":";REP(i,v.size())cout<<" "<<v[i];cout<<endl
#define ALL(a) (a).begin(),(a).end()

#define CHMIN(a,b) a=min((a),(b))
#define CHMAX(a,b) a=max((a),(b))

// mod
const ll MOD = 1000000007ll;
#define FIX(a) ((a)%MOD+MOD)%MOD

// floating
typedef double Real;
const Real EPS = 1e-11;
#define EQ0(x) (abs(x)<EPS)
#define EQ(a,b) (abs(a-b)<EPS)
typedef complex<Real> P;

int main(){
  int n,a;
  cin>>n>>a;
  cout<<(n*n-a)<<endl;
  return 0;
}


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

using namespace std;

int Max(const vector<int>& v, const vector<int>& w, int W) {
    vector<int> dp(W + 1, 0);
    for (int i = 0; i < v.size(); i++) {
        for (int j = W; j - w[i] >= 0; j--) {
            dp[j] = max(dp[j], dp[j - 1]);
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
        }
    }
    return dp[W];
}

int main() {
    int N, W;
    cin >> N >> W;
    vector<int> v(N), w(N);
    for (int i = 0; i < N; i++) {
        cin >> v[i] >> w[i];
    }
    cout << Max(v, w, W) << endl;
    return 0;
}

Measured memory_bytes: 1232
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>

using namespace std;

int N;
long long K;
vector<pair<int,int> > v;

int main(){
    cin >> N >> K;
    int a,b;
    for(int i=0;i<N;i++){
        cin >> a >> b;
        v.push_back(make_pair(a,b));
    }
    sort(v.begin(),v.end());
    long long count = 0;
    for(int i=0;i<N;i++){
        count += v[i].second;
        if(K <= count){
            cout << v[i].first << endl;
            break;
        }
    }
    return 0;
}

Measured memory_bytes: 1400
def bubble_sort(num_list):
    list_b = num_list[:]
    for i in range(len(list_b)-1):
        for j in range(len(list_b)-1,i,-1):
            if list_b[j][1] < list_b[j-1][1]:
                list_b[j],list_b[j-1] = list_b[j-1],list_b[j]
    return list_b

def selection_sort(num_list):
    list_s = num_list[:]
    for i in range(len(list_s)):
        minj = i
        for j in range(i,len(list_s)):
            if list_s[minj][1] > list_s[j][1]:
                minj = j
        list_s[i],list_s[minj] = list_s[minj],list_s[i]
    return list_s

def isStable(list_x, list_y):
    leng = int(len(list_x))
    for i in range(leng-1):
        for j in range(i+1, leng):
            for x in range(leng-1):
                for y in range(x+1, leng):
                    if list_x[i][1]==list_x[j][1] and list_x[i]==list_y[y] and list_x[j] == list_y[x]:
                        return "Not stable"
    return "Stable"


qnt = int(input())
num_list = input().split()

bs = bubble_sort(num_list)
ss = selection_sort(num_list)
print(" ".join(bs))
print(isStable(num_list,bs))
print(" ".join(ss))
print(isStable(num_list,ss))

Measured memory_bytes: 7796
v[30];P(n,m,l,i){if(n)for(i=m<n?m:n;i;i--)P(n-i,v[l]=i,l+1);else for(i=l;i--;)printf("%d%c",v[l-i-1],i?32:10);}main(n){for(;scanf("%d",&n)*n;)P(n,n,0);}

Measured memory_bytes: 0
import java.util.Scanner;
public class Main{
    public static void main(String[] args) {
	Scanner scan = new Scanner(System.in);
	int n = Integer.parseInt(scan.nextLine());
	String[] input = scan.nextLine().split(" ");
	Card[] cards = new Card[n];
	Card[] cardsForBubble = new Card[n];
	Card[] cardsForSelect = new Card[n];
	for (int i = 0; i < n; i++) {
	    String suit = input[i].substring(0, 1);
	    int value = Integer.parseInt(input[i].substring(1, 2));
	    cards[i] = new Card(suit, value);
	    cardsForBubble[i] = new Card(suit, value);
	    cardsForSelect[i] = new Card(suit, value);
	}
	Sort sort = new Sort();
	sort.BubbleSort(cardsForBubble, n);
	sort.printCards(cardsForBubble);
	if(sort.isStable(cards, cardsForBubble)) {
	    System.out.println("Stable");
	} else {
	    System.out.println("Not stable");
	}
	sort.SelectionSort(cardsForSelect, n);
	sort.printCards(cardsForSelect);
	if(sort.isStable(cards, cardsForSelect)) {
	    System.out.println("Stable");
	} else {
	    System.out.println("Not stable");
	}
    }
}
class Sort{
    Card[] BubbleSort(Card[] cards, int n) {
	for (int i = 0; i < n; i++) {
	    for (int j = n-1; j > i; j--) {
		if (cards[j].value < cards[j-1].value) {
		    Card tmp = cards[j];
		    cards[j] = cards[j-1];
		    cards[j-1] = tmp;
		}
	    }
	}
	return cards;
    }
    Card[] SelectionSort(Card[] cards, int n) {
	for (int i = 0; i < n; i++) {
	    int minKey = i; 
	    for (int j = i; j < n; j++) {
		if (cards[j].value < cards[minKey].value) {
		    minKey = j;
		}
	    }
	    if (minKey != i) {
		Card tmp = cards[i];
		cards[i] = cards[minKey];
		cards[minKey] = tmp;
	    }
	}
	return cards;
    }
    boolean isStable(Card[] cards, Card[] sortedCards) {
	for (int i = 0; i < sortedCards.length - 1; i++) {
	    if (sortedCards[i].value == sortedCards[i+1].value) {
		int value = sortedCards[i].value;
		String front = sortedCards[i].suit;
		String back = sortedCards[i+1].suit;
		int frontIndex = 0;
		int backIndex = 0;
		for (int j = 0; j < cards.length; j++) {
		    if (cards[j].value == value && cards[j].suit.equals(front)) {
			frontIndex = j;
		    } else if (cards[j].value == value && cards[j].suit.equals(back)) {
			backIndex = j;
		    }
		}
		if (frontIndex > backIndex) {
		    return false;
		}
	    }
	}
	return true;
    }
    void printCards (Card[] cards) {
	for (int i = 0; i < cards.length - 1; i++) {
	    System.out.print(cards[i].suit + cards[i].value + " ");
	}
	System.out.println(cards[cards.length - 1].suit + cards[cards.length - 1].value);
    }
}
class Card{
    String suit;
    int value;
    Card (String suit, int value) {
	this.suit = suit;
	this.value = value;
    }
}

Measured memory_bytes: 26328
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(),(x).end()
#define YES() printf("YES\n")
#define NO() printf("NO\n")
#define isYES(x) printf("%s\n",(x) ? "YES" : "NO")
#define Yes() printf("Yes\n")
#define No() printf("No\n")
#define isYes(x) printf("%s\n",(x) ? "Yes" : "No")
#define isIn(x,y,h,w) (x >= 0 && x < h && y >= 0 && y < w)

#define int long long
//using ll = long long;
using P = pair<int,int>;

ostream &operator<<(ostream &os,const P &p){ return os << "(" << p.first << "," << p.second << ")"; }
template<class T>
ostream &operator<<(ostream &os,const vector<T> &v){
	for(int i = 0;i < v.size();i++) os << (i ? "," : "[") << v[i];
	os << "]";
	return os;
}

template<class T> T &chmin(T &a,const T &b){ return a = min(a,b); }
template<class T> T &chmax(T &a,const T &b){ return a = max(a,b); }

const int INF=1e+18;
const double EPS=1e-9;
const int MOD=998244353;

const int dx[]={1,0,-1,0},dy[]={0,-1,0,1};

signed main(){
	int n,a[100010],sum[100010] = {},ans = 0;
	cin >> n;
	for(int i = 0;i <= n;i++) cin >> a[i];
	for(int i = n;i >= 0;i--) sum[i] = sum[i + 1] + a[i];
	int cnt = 1;
	bool flag = false;
	for(int i = 0;i <= n;i++){
		if(cnt < 0){
			cout << -1 << endl;
			return 0;
		}
		if(cnt >= sum[i]){
			flag = true;
			cnt = sum[i];
		}
		ans += cnt;
		if(flag) cnt -= a[i];
		else cnt = (cnt - a[i]) * 2;
	}
	if(!flag) cout << -1 << endl;
	else cout << ans << endl;
}


Measured memory_bytes: 5184
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<map>
#include<vector>
#include<set>
using namespace std;
const int maxn = 1e5+5;
int n;
long long a[maxn];
int main()
{
    long long turn = 0, t;
    cin>>n;
    for(int i = 0; i < n; i++) scanf("%I64d", &a[i]), turn += a[i];
    t = a[n-1];
    for(int i = n; i >= 1; i--) a[i] -= a[i-1];
    a[0] -= t;
    t = (long long)n*(n+1)/2;
    if(turn % t) return puts("NO"), 0;
    turn /= t;
    int cnt = 0;
    t = (n-1)*turn;
    for(int i = 0; i < n; i++)
    {
        a[i] += t;
        if(a[i] % n)  return puts("NO"), 0;
        a[i] /= n;
        if(a[i] > turn) return puts("NO"), 0;
        cnt += turn - a[i];
    }
    if(cnt != turn) return puts("NO"), 0;
    puts("YES");
    return 0;
}


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

string s;
vector <string> rec;

int main(){
	ios::sync_with_stdio(false);
	int n, k;
	cin >> s;
	n = s.size();
	cin >> k;
	for (int i = 0; i < n; i++){
		for (int j = 1; j <= min(k, n - i); j++)
			rec.push_back(s.substr(i, j));
	}
	sort(rec.begin(), rec.end());
	unique(rec.begin(), rec.end());
	cout << rec[k - 1] << '\n';
	return 0;
}

Measured memory_bytes: 1660
import java.util.Scanner;

public class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int i = sc.nextInt();
		int rc = i * (i - 1) / 2;
		int ten[] = new int[i];
		for(int j = 0; j < i; j++){
			ten[j] = 0;
		}
		for(int j = 0; j < rc; j++){
			int a = sc.nextInt();
			int b = sc.nextInt();
			int c = sc.nextInt();
			int d = sc.nextInt();
			if(c > d){
				ten[a-1] = ten[a-1] + 3;
			}else if(c < d){
				ten[b-1] = ten[b-1] + 3;
			}else if(c == d){
				ten[a-1] = ten[a-1] + 1;
				ten[b-1] = ten[b-1] + 1;
			}
		}
		for(int j = 0; j < i; j++){
			int cnt = 0;
			for(int k = 0; k < i; k++){
				if(ten[j] >= ten[k]){
					cnt = cnt + 1;
				}
			}
			int rank = i - cnt + 1;
			System.out.println(rank);
		}
	}
}

Measured memory_bytes: 42256
package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)

func Scanner() string {
	sc.Scan()
	return sc.Text()
}

type Sort1 [][]int

func (x Sort1) Len() int           { return len(x) }
func (x Sort1) Less(i, j int) bool { return x[i][1] < x[j][1] }
func (x Sort1) Swap(i, j int)      { x[i], x[j] = x[j], x[i] }

type Sort1r [][]int

func (x Sort1r) Len() int           { return len(x) }
func (x Sort1r) Less(i, j int) bool { return x[i][1] > x[j][1] }
func (x Sort1r) Swap(i, j int)      { x[i], x[j] = x[j], x[i] }

type Sort0 [][]int

func (x Sort0) Len() int           { return len(x) }
func (x Sort0) Less(i, j int) bool { return x[i][0] < x[j][0] }
func (x Sort0) Swap(i, j int)      { x[i], x[j] = x[j], x[i] }

type Sort0r [][]int

func (x Sort0r) Len() int           { return len(x) }
func (x Sort0r) Less(i, j int) bool { return x[i][0] > x[j][0] }
func (x Sort0r) Swap(i, j int)      { x[i], x[j] = x[j], x[i] }

func main() {
	buf := make([]byte, 0)
	sc.Buffer(buf, 1000000009)
	sc.Split(bufio.ScanWords)
	n, _ := strconv.Atoi(Scanner())
	ab := make([][]int, n)
	cd := make([][]int, n)
	for i := 0; i < n; i++ {
		a, _ := strconv.Atoi(Scanner())
		b, _ := strconv.Atoi(Scanner())
		ab[i] = []int{a, b}
	}
	for i := 0; i < n; i++ {
		c, _ := strconv.Atoi(Scanner())
		d, _ := strconv.Atoi(Scanner())
		cd[i] = []int{c, d}
	}
	sort.Stable(Sort0r(ab))
	sort.Stable(Sort1(cd))
	ans := 0
	list := make([]bool, n)
	for i := 0; i < n; i++ {
		c, d := cd[i][0], cd[i][1]
		for j := 0; j < n; j++ {
			a, b := ab[j][0], ab[j][1]
			if !list[j] && a < c && b < d {
				list[j] = true
				ans += 1
				break
			}
		}
	}
	fmt.Println(ans)
}


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

using namespace std;

typedef double db;
typedef long long ll;
typedef long double ld;
typedef unsigned int ui;
typedef unsigned long long ull;

typedef pair < db, db > pdd;
typedef pair < db, ld > pdl;
typedef pair < ld, db > pld;
typedef pair < ld, ld > ldp;

typedef pair < ll, ll > pll;
typedef pair < int, ll > pil;
typedef pair < ll, int > pli;
typedef pair < int, int > pii;

#define F first
#define S second

#define en end()
#define bg begin()

#define rev reverse
#define mp make_pair
#define pb push_back

#define y1 y1234567890
#define um unordered_map

#define all(x) x.bg, x.en
#define sz(x) (int)x.size()
#define len(x) (int)strlen(x)

#define sqr(x) ((x + 0ll) * (x))
#define sqrd(x) ((x + 0.0) * (x))

#define forn(i, n) for (int i = 1; i <= n; i++)

const ll inf = (ll)1e18;
const ll mod = (ll)1e9 + 7;

const db eps = (db)1e-9;
const db pi = acos(-1.0);

const int dx[] = {0, 0, 1, 0, -1};
const int dy[] = {0, 1, 0, -1, 0};

const int N = 200500;

ll ans;
stack < int > st;
int n, a[N], l[N], r[N];

int main() {
	//freopen(".in", "r", stdin);
	//freopen(".out", "w", stdout);
	//freopen(".err", "w", stderr);

	//srand(time(NULL));

	cin.tie(NULL);
	cout.tie(NULL);
	ios_base::sync_with_stdio(false);

	//cout << setprecision(10) << fixed;
	
	cin >> n;

	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		while (!st.empty() && a[st.top()] > a[i])
			st.pop();
		l[i] = (st.empty() ? 1 : st.top() + 1);
		st.push(i);
	}

	while (!st.empty())
		st.pop();

	for (int i = n; i >= 1; i--) {
		while (!st.empty() && a[st.top()] > a[i])
			st.pop();
		r[i] = (st.empty() ? n : st.top() - 1);
		st.push(i);
	}

	for (int i = 1; i <= n; i++) {
		ans += (r[i] - i + 1) * 1ll * (i - l[i] + 1) * a[i];
	}

	cout << ans;
	
	//cerr << (clock() + 0.0) / CLOCKS_PER_SEC;

	return 0;
}


Measured memory_bytes: 3456
#![allow(non_snake_case)]
#![allow(dead_code)]
#![allow(unused_macros)]
#![allow(unused_imports)]

use std::cmp::*;
use std::collections::*;

macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

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

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

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

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

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

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

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

#[derive(Clone)]
struct Edge(usize, usize);

struct Solver {
    color: Vec<usize>,
}

const DUMMY: usize = 9;

impl Solver {
    fn new(N: usize) -> Solver {
        Solver { color: vec![DUMMY; N] }
    }
    fn dfs(&mut self, i: usize, p: usize, acc: usize, g: &Vec<Vec<Edge>>) {
        self.color[i] = acc;
        for &Edge(to, w) in &g[i] {
            if to == p {
                continue;
            }
            self.dfs(to, i, acc ^ w, g);
        }
    }
}

fn main() {
    input!{
        N: usize,
        uvw: [(usize1, usize1, usize); N-1],
    }
    let mut graph = vec![Vec::new(); N];
    for (u, v, w) in uvw {
        let w = w % 2;
        graph[u].push(Edge(v, w));
        graph[v].push(Edge(u, w));
    }
    let mut s = Solver::new(N);
    s.dfs(0, N+1, 0, &graph);
    for i in s.color {
        println!("{}", i);
    }
}


Measured memory_bytes: 22772
// 2:00~

#include<queue>
#include<cstdio>
#include<cassert>

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

using namespace std;

const int INF=1<<29;

class edge{
public:
	int v,cost;
	edge(int v,int cost):v(v),cost(cost){}
};

int main(){
	for(int n,m,k;scanf("%d%d%d",&n,&m,&k),n;){
		vector<edge> G[100];
		int d[100][100];
		rep(u,n) rep(v,n) d[u][v]=(u==v?0:INF);
		rep(_,m){
			int u,v,cost; scanf("%d%d%d",&u,&v,&cost);
			d[u][v]=d[v][u]=cost;
			G[u].push_back(edge(v,cost));
			G[v].push_back(edge(u,cost));
		}

		rep(w,n) rep(u,n) rep(v,n) d[u][v]=min(d[u][v],d[u][w]+d[w][v]);

		vector<int> D[100]; // 最短経路 DAG
		rep(u,n) rep(i,G[u].size()) {
			int v=G[u][i].v,cost=G[u][i].cost;
			if(d[0][u]+cost+d[v][n-1]==d[0][n-1]) D[u].push_back(v);
		}

		double dp[100][100]={}; // dp[u][v] := ( u->v 間の最短経路の個数 )
		// rep(u,n){
			// bool vis[100]={}; vis[u]=true;
			// dp[u][u]=1;
			// queue<int> Q; Q.push(u);
			// while(!Q.empty()){
				// int v=Q.front(); Q.pop();
				// rep(i,D[v].size()){
					// int w=D[v][i];
					// if(!vis[w]){
						// vis[w]=true;
						// Q.push(w);
					// }
					// dp[u][w]+=dp[u][v];
				// }
			// }
		// }
		rep(u,n) rep(i,G[u].size()) {
			int v=G[u][i].v,cost=G[u][i].cost;
			if(d[0][u]+cost+d[v][n-1]==d[0][n-1]) dp[u][v]=1;
		}
		rep(w,n) rep(u,n) rep(v,n) dp[u][v]+=dp[u][w]*dp[w][v];

		rep(_,k){
			int c; scanf("%d",&c);
			printf("%.9f\n",dp[0][c]*dp[c][n-1]/dp[0][n-1]);
		}
		puts("");
	}

	return 0;
}

Measured memory_bytes: 1352
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int count =0;
    for (int i=1; i<=N; i++) {
      if (i <= 9) count++;
      if (i >= 100 && i<= 999) count++;
      if (i >= 10000 && i<= 99999) count++;
    }
    System.out.println(count);
  }
}

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

using namespace std;

int main() {
    unsigned int n;
    cin >> n;

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

    int q;
    cin >> q;
    while (q--) {
        int b, e, t;
        cin >> b >> e >> t;
        swap_ranges(a.begin() + b, a.begin() + e, a.begin() + t);
    }

    for (int i = 0; i < a.size(); ++i) {
        cout << (i ? " " : "") << a[i];
    }
    cout << endl;
    return 0;
}


Measured memory_bytes: 3100
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<set>
#include<math.h>
#include<queue>
#include<string.h>
#include<string>
#include<map>
#include<stack>
#include<vector>
#define mod 998244353
using namespace std;
struct str {
	int end, cost;
};
struct str2 {
	int cur;
	double cost, time;
	bool operator < (const str2&A)const {
		return cost > A.cost;
	}
};
priority_queue<str2> pq;
vector<str> vec[5611];
vector<int> back[600];
int n, t, w,k, h, m, s, e, q;
vector<str> arr[6600];
int bd[600];
int ans[600];
int chk[5010];
str temp[100];
int main() {
	scanf("%d", &n);
	int a, b;
	scanf("%d %d", &a, &b);
	for (int i = 0; i < n; i++) {
		scanf("%d", &ans[i]);
	}
	int cnt = 0;
	sort(ans, ans + n);
	int l=0, mid=0, r=0;
	for (int i = 0; i < n; i++) {
		if (ans[i] <= a) {
			l++;
		}
		if (a < ans[i] && ans[i] <= b)mid++;
		if (b < ans[i])r++;
	}
	printf("%d", min(l,min(mid,r)));
	return 0;
}

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

signed main(){
   int A,B,C; cin>>A>>B>>C; bool ans=false;
   for(int i=0;i<1000000;i++){
       if(i*A%B==C){ans=true; break;}
   }
   cout<<(ans ? "YES" : "NO")<<endl;
}

Measured memory_bytes: 256
#include <iostream>
#include<string>
#include<cmath>
#include<algorithm>
#include<cctype>
#include<queue>
#include<deque>
#include<regex>
#include<stack>
#include<stdio.h>
#include<vector>
#include<set>
#include<map>
#include<iomanip>

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

typedef int long long ll;
using namespace std;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
const ll MOD = 1e9 + 7;
static const int MAX = 100;
static const int INF = (1 << 23);

int main() {
    ll n;
    cin>>n;
    vector<ll> a(n);
    rep(i,n){
        cin>>a[i];
        a[i]-=(i+1);
    }
    sort(a.begin(),a.end());
    ll b=0;
    ll ans=0;
    if(n%2==0){
        b=a[n/2];
        rep(i,n){
            ans+=abs(a[i]-b);
        }
        b=a[(n+1)/2];
        ll j=0;
        rep(i,n){
            j+=abs(a[i]-b);
        }
        ans=min(ans,j);
        cout<<ans<<endl;


    }else{
        b=a[n/2];
        rep(i,n){
            ans+=abs(a[i]-b);
        }
        cout<<ans<<endl;
    }





    return 0;
}


Measured memory_bytes: 1792
# Welcome to AtCoder

# 入力の準備
N, M = map(int, input().split())
result_list = []
for i in range(M):
    result_list.append(input().split())

ans_num = 0 # 正答数
penalty_num = 0 # ペナルティ数

correct_memo = {} # 正答されたものを保管するメモ
penalty_memo = [0 for i in range(N+1)] # ペナルティ数のメモ

for r in result_list:
    key = int(r[0])
    if key in correct_memo: # すでにACが出ていればスキップ
        continue

    if r[1]=='WA': # ペナルティ数のメモ
        penalty_memo[key] = penalty_memo[key] + 1
    elif r[1]=='AC':
        correct_memo[key] = 1 # メモをしておく
        ans_num = ans_num + 1
        penalty_num = penalty_num + penalty_memo[key]

print(ans_num, penalty_num)


Measured memory_bytes: 45016
#include <bits/stdc++.h>
using namespace std;
typedef long long lli;
typedef long double lld;
#define mod 1000000007
#define mod2 998244353
#define fori(n) for (int i = 0; i < n; i++)
#define forj(n) for (int j = 0; j < n; j++)
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define fast ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define endl "\n"
#define sortvec(a) sort(a.begin(), a.end())
#define watch(x) cerr << "\n" << (#x) << " is " << (x) << endl
#define cerr if(true)cerr
void print(){cout<<endl;}
template<typename T,typename... Args>
void print(T a, Args... args) {cout<<a<<" ";print(args...);}
lli llipowerp(lli x, lli y, lli p=LLONG_MAX)
{
    lli res = 1;
    x = x % p;
    while (y > 0)
    {
        if (y & 1) res = (res * x) % p;
        y = y >> 1;
        x = (x * x) % p;
    }
    return res;
}
lli binarySearch(vector<int> arr, int l, int r, int x)
{
    if (r >= l)
    {
        lli mid = l + (r - l) / 2;
        if (arr[mid] == x)
            return mid;
        if (arr[mid] > x)
            return binarySearch(arr, l, mid - 1, x);
        return binarySearch(arr, mid + 1, r, x);
    }
    return -1;
}
template <typename T>
inline void printvec(vector<T> inp){
    for(auto it:inp) cout<<it<<" ";
    cout << endl;
}
//---------------------------------------------------------------------------------
int n;
vector<lli> a;
const int N=3010;
lli dp[N][N][2];

lli get(int l,int r,int c){
    if(l>r || l<0 || l>=n ||r<0 || r>=n) return 0;
    if(dp[l][r][c]!=-1) return dp[l][r][c];

    if(l==r){
        if(c==0)
            dp[l][r][c]=a[l];
        else dp[l][r][c]=-1*a[l];
        return dp[l][r][c];
    }

    if(c==0){
        dp[l][r][c]=max(get(l+1,r,1)+a[l],get(l,r-1,1)+a[r]);
        return dp[l][r][c];
    }
    else{
        dp[l][r][c] = min(get(l + 1, r, 0)-a[l], get(l, r - 1, 0)-a[r]);
        return dp[l][r][c];
    }
}

int main(){
    cin>>n;
    int x;
    memset(dp,-1,sizeof(dp));
    fori(n){
        cin>>x;
        a.pb(x);

    }
    // fori(n){
    //     forj(n){
    //         cout<<get(i,j,0)<<","<<get(i,j,1)<<"   ";
    //     }
    //     cout<<endl;
    // }
    cout<<get(0,n-1,0)<<endl;
}

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

int main(){
  int H,W;
  cin >> H >> W;
  string S[60];
  for(int i=0;i<H;i++) cin >>S[i];
  int count[60][60];
  for(int i=0;i<60;i++)
    for(int j=0;j<60;j++)
      count[i][j]=0;
  //隣接する爆弾をカウント
  for(int i=0;i<H;i++){
    for(int j=0;j<W;j++){
      if(S[i].at(j)=='#')
        for(int k=i;k<i+3;k++)
          for(int l=j;l<j+3;l++)
            count[k][l]++;
    }
  }
  //爆弾の個数に書き換え
  for(int i=0;i<H;i++){
    for(int j=0;j<W;j++){
      if(S[i].at(j)=='.')
        S[i].at(j)='0'+count[i+1][j+1];
    }
  }
  //出力
  for(int i=0;i<H;i++)
    cout << S[i] <<endl;
  
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double dd;
const int N = 2e6+5;
const double eps = 1e-8;
const int mod = 1e9+7;

inline ll qpow(long long a, int b) {
  ll ans = 1;
  a = (a % mod + mod) % mod;
  for (; b; b >>= 1) {
    if (b & 1) ans = (a * ans) % mod;
    a = (a * a) % mod;
  }
  return ans;
}

ll r1,r2,c1,c2,fac[N];

ll com(ll m,ll n){
  ll ans = fac[m];
  ans = (ans*qpow(fac[n],mod-2))%mod;
  ans = (ans*qpow(fac[m-n],mod-2))%mod;
  return ans%mod;
}

int main(){
  // freopen("input.txt","r",stdin);
  cin>>r1>>c1>>r2>>c2;
  fac[0] = 1;
  for(int i = 1;i <= 2e6+3;i++) fac[i] = ((fac[i-1]%mod)*(i%mod))%mod;
  ll x= com(r2+c2+2,c2+1);
  ll y = com(r1+c2+1,c2+1);
  ll z = com(r2+c1+1,c1);
  ll w = com(r1+c1,c1);
  ll ans = (x-y+mod)%mod;
  ans = (ans + w%mod)%mod;
  ans = (ans-z+mod)%mod;
  cout << ans << endl;  
  return 0;
}


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

using namespace std;
typedef long long ll;

const ll INF = 1e9;

struct edge {int to; ll cost;};
vector<vector<edge> > edges;

void dfs(int v, ll d, vector<vector<pair<int ,ll> > > &G, vector<ll> &list) {
  list[v] = d;
  for (pair<int, int> p : G[v]) {
    if (list[p.first] == -1LL) {
      dfs(p.first, d + p.second, G, list);
    }
  }
}

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

  vector<vector<pair<int, ll> > > G(n);
  vector<ll> list(n, -1LL);
  for (int i = 0; i < n - 1; i++) {
    int a, b, c;
    cin >> a >> b >> c;
    a--, b--;
    G[a].push_back(make_pair(b, c));
    G[b].push_back(make_pair(a, c));
  }

  int q, k;
  cin >> q >> k;
  k--;

  dfs(k, 0, G, list);

  for (int i = 0; i < q; i++) {
    int x, y;
    cin >> x >> y;
    x--, y--;
    cout << list[x] + list[y] << endl;
  }
  return 0;
}


Measured memory_bytes: 14336
#include <bits/stdc++.h>
using namespace std;
int x[1111],y[1111],h[1111];
int main(){
	int n,p=0;
	scanf("%d",&n);
	for (int i=1;i<=n;i++) {
		scanf("%d%d%d",&x[i],&y[i],&h[i]);
		if (h[i]!=0 && !p) p=i;
	}
	for (int X=0;X<=100;X++)
		for (int Y=0;Y<=100;Y++){
			int H=(abs(x[p]-X)+abs(y[p]-Y))+h[p];
			bool flag=1;
			for (int i=1;i<=n;i++){
				if (h[i]!=max(H-abs(x[i]-X)-abs(y[i]-Y),0)){
					flag=0; break;
				}
			}
			if (flag){
				printf("%d %d %d\n",X,Y,H);
				return 0;
			}
		}
	return 0;
}
			

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


const ll MOD = 1e9 + 7;
template<ll MOD> struct ModInt {
    ll value;
    ModInt() : value(0) {}
    ModInt(const ll& v) : value(v % MOD) {
        if ( value < 0 ) value += MOD;
    }
    ModInt<MOD>& operator=(const ModInt& o) {
        value = o.value;
        return *this;
    }
    inline bool operator==(const ModInt& o) {
        return value == o.value;
    }
    inline bool operator!=(const ModInt& o) {
        return value != o.value;
    }
    ModInt<MOD>& operator+=(const ModInt& o) {
        value += o.value;
        if ( value >= MOD ) value -= MOD;
        return *this;
    }
    ModInt<MOD>& operator-=(const ModInt& o) {
        value += MOD - o.value;
        if (value >= MOD ) value -= MOD;
        return *this;
    }
    ModInt<MOD>& operator*=(const ModInt& o) {
        value *= o.value;
        value %= MOD;
        return *this;
    }
    ModInt<MOD>& operator/=(const ModInt& o) {
        value *= inverse(o.value);
        value %= MOD;
        return *this;
    }
    ModInt<MOD> operator-() {
        return ModInt<MOD>(-value);
    }
    ModInt<MOD> operator+(const ModInt& o) {
        ModInt<MOD> r(*this);
        r += o;
        return r;
    }
    ModInt<MOD> operator-(const ModInt& o) {
        ModInt<MOD> r(*this);
        r -= o;
        return r;
    }
    ModInt<MOD> operator*(const ModInt& o) {
        ModInt<MOD> r(*this);
        r *= o;
        return r;
    }
    ModInt<MOD> operator/(const ModInt& o) {
        ModInt<MOD> r(*this);
        r /= o;
        return r;
    }
    ModInt<MOD> pow(ll n) {
        ModInt<MOD> t(*this), r = 1;
        while ( n > 0 ) {
            if ( n & 1 ) r *= t;
            t *= t;
            n >>= 1;
        }
        return r;
    }
private:
    ll inverse(ll a) {
        ModInt<MOD> t(a);
        return t.pow(MOD - 2).value;
    }
};
template<ll MOD> std::ostream& operator<< (std::ostream& os, const ModInt<MOD>& o) {
    os << o.value;
    return os;
}
template<ll MOD> std::istream& operator>> (std::istream& is, ModInt<MOD>& o) {
    is >> o.value;
    return is;
}

using Int = ModInt<MOD>;

ll solve() {
    string K;
    ll D;
    cin >> K >> D;
    int n = K.size();
    vector<vector<Int>> dp0(n+1, vector<Int>(D)), dp1(n+1, vector<Int>(D));
    dp1[0][0] = 1;
    for ( int i = 1; i <= n; i++ ) {
        int k = K[i-1] - '0';
        for ( int d = 0; d < D; d++ ) {
            for ( int j = 0; j < 10; j++ ) {
                dp0[i][(d+j)%D] += dp0[i-1][d];
            }
            for ( int j = 0; j < k; j++ ) {
                dp0[i][(d+j)%D] += dp1[i-1][d];
            }
            dp1[i][(d+k)%D] += dp1[i-1][d];
        }
    }
    Int ans = dp0[n][0] + dp1[n][0] - Int(1);
    return ans.value;
}

int main() {
    auto ans = solve();
    cout << ans << "\n";
    return 0;
}

Measured memory_bytes: 16640
import java.util.*;
 
public class Main {

    private static final int MOD = 1_000_000_007;
    private static final int MAX = 1000000;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int X = sc.nextInt();
        int Y = sc.nextInt();

        int A = -1, B = -1;
        for (int a = 0; a <= X; a++) {
            int b = X - 2*a;
            if (a+2*b == Y) {
                A = a;
                B = b;
                break;
            }
        }
        if (A == -1) {
            System.out.println(0);
        } else {
            System.out.println(combMod(A+B, A));
        }
    }
    private static long combMod(int n, int k) {
        long[] fac = new long[MAX];
        long[] finv= new long[MAX];
        long[] inv= new long[MAX];
        fac[0] = 1;
        fac[1] = 1;
        finv[0] = 1;
        finv[1] = 1;
        inv[1] = 1;
        for (int i = 2; i < MAX; i++) {
            fac[i] = fac[i-1]*i % MOD;
            inv[i] = MOD-inv[MOD%i]*(MOD/i) % MOD;
            finv[i] = finv[i-1]*inv[i]%MOD;
        }

        if (n < k) {
            return 0;
        }
        if (n < 0 || k < 0) {
            return 0;
        }
        return fac[n]*(finv[k]*finv[n-k]%MOD)%MOD;
    }
}


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

#define int long long
#define fi first
#define se second
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define rep1(i,n) for(int i=1;i<=(int)(n);++i)
#define rep11(i,n) for(int i=1;i<(int)(n);++i)
#define repo(i,o,n) for(int i=o;i<(int)(n);++i)
#define repm(i,n) for(int i=(int)(n)-1;i>=0;--i)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define sperase(v,n) (v).erase(remove(all(v), n), (v).end())
#define vdelete(v) (v).erase(unique(all(v)), (v).end())
#define pb(n) push_back(n)
#define mp make_pair
//#define MOD 1000000007
#define INF LONG_LONG_MAX

#define MOD 998244353

int n,d,cnt[100000],MAX,ans=1;

signed main() {
    cin >> n >> d;
    if (d) {
        cout << 0 << endl;
        return 0;
    }
    rep(i,n-1) {
        cin >> d;
        cnt[d]++;
        MAX = max(MAX,d);
    }
    if (cnt[0]) {
        cout << 0 << endl;
        return 0;
    }
    cnt[0] = 1;
    rep1(i,MAX) {
        int tmp = 1;
        rep(j,cnt[i]) tmp = (tmp*cnt[i-1])%MOD;
        ans = (ans*tmp)%MOD;
    }
    cout << ans << endl;

}


Measured memory_bytes: 1024
/* 
	Author: ankrypt
*/
#include <bits/stdc++.h>

using namespace std;

const int MAX_LIMIT = 105;
long long N;
long long arr[MAX_LIMIT];

int main()
{
	scanf("%lld", &N);
	for(int i = 0; i < N; i++) {
		scanf("%lld", &arr[i]);
	}

	sort(arr, arr + N);

	long long finalAns = arr[N - 1] - arr[0];

	printf("%lld\n", finalAns);
	
	return 0;
}
/*
	Powered by Buggy Plugin
*/


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
using ll = long long;
typedef pair<int, int> P;
ll Mod = 998244353;
ll modinv(ll a, ll m) {
    ll b = m, u = 1, v = 0;
    while (b) {
        ll t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}
ll fact[400003];
ll ifact[400003];
ll Combination(ll a,ll b) {
  ll s = (fact[a] * ifact[b]) % Mod;
  return (s * ifact[a-b]) % Mod;
}
int main() {
  fact[0] = 1;
  ifact[0] = 1;
  for (int i = 1; i <= 400002; i++) {
    fact[i] = fact[i-1] * i;
    fact[i] %= Mod;
    ifact[i] = modinv(fact[i],Mod);
  }
  ll N,A,B,K;
  cin >> N >> A >> B >> K;
  ll ans = 0;
  for (ll i = 0; i <= N; i++) {
    if ((K - (A * i)) % B == 0) {
      ll a = i;
      ll b = (K - (A * i)) / B;
      if (0 <= b && b <= N) {
        ll res = Combination(N,a);
        res %= Mod;
        res *= Combination(N,b);
        res %= Mod;
        ans += res;
        ans %= Mod;
      }
    }
  }
  cout << ans << endl;
  return 0;
}

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

int main(void){
        int a,b;
        int i=scanf("%d",&a);
        int j=scanf("%d",&b);
        if(i<1||j<1){
                printf("error");
                exit(1);
        }
        int b1=a%3;
        int b2=b%3;
        int b3=(a+b)%3;
        if(b1==0||b2==0||b3==0){
                printf("Possible");
        }else{
                printf("Impossible");;
        }
        return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
#define ll long long int
#define M 1000000007
#define mod 998244353
#define mp(x,y) make_pair(x,y)
#define pb(x) push_back(x)
#define pi pair<ll,ll>
using namespace std;
const ll N=100010;

ll n;
ll ar[N];
ll dp[3001][3001][2];
ll func(ll st,ll en,ll t)
{
    if(st>en){return 0;}
    if(dp[st][en][t]==-1){
    ll ans;
    if(t==0)
    {
        ans=max(ar[st]+func(st+1,en,1),ar[en]+func(st,en-1,1));
    }
    else
    {
        ans=min(func(st+1,en,0),func(st,en-1,0));
    }
    dp[st][en][t]=ans;
    }
    return dp[st][en][t];
}

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

    ll sum=0;
    cin>>n;
    for(ll i=0;i<n;++i){cin>>ar[i];sum+=ar[i];}
    memset(dp,-1,sizeof(dp));
    ll ans=func(0,n-1,0);

    ans=2*ans-sum;

    cout<<ans<<endl;

    return (0);
}


Measured memory_bytes: 141696
from sys import exit

N, u, v = map(int, input().split())

if u == v:
    print(0)
    exit()

edges = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    A, B = map(int, input().split())
    edges[A].append(B)
    edges[B].append(A)


def calc_destination(start, edges):
    destination = [-1] * (N + 1)
    destination[start] = 0
    q = [start]
    while len(q) != 0:
        current = q.pop()
        for n in edges[current]:
            if destination[n] != -1:
                continue
            destination[n] = destination[current] + 1
            q.append(n)
    return destination


tak = calc_destination(u, edges)
aok = calc_destination(v, edges)

result = 0
for i in range(1, N + 1):
    aoki = aok[i]
    if tak[i] >= aoki:
        continue
    if aoki > result:
        result = aoki
print(result - 1)


Measured memory_bytes: 29068
#include <stdio.h>
int main(void){
    int i,j,k;
    char str[21];
    scanf("%s",str);
    for(j=0;str[j]!='\0';j++){

    }
    for(i=j-1;i>=0;i--){
        printf("%c",str[i]);
    }
    puts("");
    return 0;
}

Measured memory_bytes: 524
import itertools
num = str(input())

olist = [int(i+1) for i in range(len(num)-1)]
comblist = []
for i, _ in enumerate(olist, 1):     
    for j in itertools.combinations(olist, r=i):
        comblist.append(j)

L = []
for i in range(len(comblist)):
  t = num
  for j in range(len(comblist[i])):
    t = t[0:comblist[i][j]+j] + "," + t[comblist[i][j]+j:]
  L.append(t)

out = 0
for i in range(len(L)):
  t = L[i].split(",")
  for j in range(len(t)):
    out += int(t[j])
print(out+int(num))

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
using ll =long long;
#define all(v) v.begin(),v.end()
 
int main() {
  ll N;
  cin>>N;
  vector<double> vec(N);
  for(ll i=0;i<N;i++) {
cin>>vec[i];
  }
  sort(all(vec));
  double ans=(vec[0]+vec[1])/2;
  for(ll i=2;i<N;i++) {
ans=(ans+vec[i])/2;
  }
  
  
  cout<<fixed<<setprecision(8);
  cout<<ans<<endl;
}

    
    
    
      
      
      
      
      
 
      
      
      
    
    
    
    
    
    
    
    
    


Measured memory_bytes: 3832
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <algorithm>
#include <string>
#include <climits>
#include <cmath>
#include <cstdlib>

using namespace std;

string num = "";

char ask(string str)
{
	char ch;
    cout << "? " << str << endl << flush;
    cin >> ch;
    return ch;
}

void answer(string str)
{
    cout << "! " << str << endl << flush;
    exit(0);
}

bool check(char digit)
{
    if (digit == '9') return true;
    string tmp = num + digit;
    tmp.append(15 - tmp.size(), '9');
    bool res = (ask(tmp) == 'Y');
//    cerr << tmp << ": " << res << endl;
    return res;
}

int getceil(char l, char r)
{
    while (r > l) {
        char m = (l + r) / 2;
        if (check(m)) r = m;
        else l = m+1;
//        cerr << l << ' ' << r << endl;
    }
    return r;
}

int solve()
{
	char ch = ask("1000000000000001");
	if (ch == 'Y') {
        string str = "2";
        while (ask(str) == 'N') str += "2";
        answer("1" + string(str.size() - 1, '0'));
        return 0;
	}

    string str = "1";
    while (ask(str) == 'Y') {
		str += '0';
    }
    int numdigits = str.size() - 1;


    num += getceil('1', '9');
    for (int i = 1; i < numdigits; ++i) {
        num += getceil('0', '9');
    }
    answer(num);
	return 0;
}

int main()
{
    return solve();
}


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

char a[26] = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm',
              'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'};

int main() {
  char c;
  cin >> c;
  bool b = false;
  rep(i, 26) {
    if (a[i] == c) b = true;
  }
  if (b) {
    cout << 'a' << endl;
  } else {
    cout << 'A' << endl;
  }
}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;

int main()
{
    int n;
    cin>>n;
    string s;
    cin>>s;
    int w=0,e=0;
    for(int i=0;i<n;i++){
        if(s[i]=='W'){
            w++;
        }
        else{
            e++;
        }
    }
    int best=INF;
    int ep=0,wp=0;
    for(int i=0;i<n;i++){
        if(s[i]=='E'){
            ep++;
        }
        best=min(best,wp+e-ep);
        if(s[i]=='W'){
            wp++;
        }
    }
    cout<<best;
    return 0;
}


Measured memory_bytes: 900
def input_data_sets
  data_sets = []
  
  while data_count = gets.strip.to_i
    return data_sets if data_count.nil? || data_count.to_i == 0
    data_sets << input_data_set(data_count)
  end
  
  data_sets
end

def input_data_set(data_count)
  data_count.times.map{ gets.strip.split }
end

class Employee
  RENDERABLE_THRESHOLD = 1_000_000
  
  attr_reader :id
  
  def initialize(__id)
    @id = __id
    @sales = 0
  end
  
  def add_sales(unit_value, count)
    @sales += unit_value.to_i * count.to_i
  end
  
  def renderable?
    @sales >= RENDERABLE_THRESHOLD
  end
  
  def to_s
    id.to_s
  end
end

class EmployeesContainer
  def initialize(date_set)
    @employees = []
    date_set.each do |data|
      get_employee(data[0]).add_sales(*data[1, 2])
    end
  end
  
  def get_employee(id)
    @employees.find{ |e| e.id == id } || add_employee(id)
  end
  
  def add_employee(id)
    employee = Employee.new(id)
    @employees << employee
    employee
  end
  
  def add_sales(id, unit_value, count)
    get_employee(id).add_sales(unit_value, count)
  end
  
  def render_to_string
    renderable_employees = @employees.select(&:renderable?)
    if renderable_employees.empty?
      "NA"
    else
      renderable_employees.map(&:to_s).join("\n")
    end
  end
end

data_sets = input_data_sets
=begin
data_sets = [
  #4
  [
    %w(1001 2000 520),
    %w(1002 1800 450),
    %w(1003 1600 625),
    %w(1001 200 1220)
  ],
  #2
  [
    %w(1001 100 3),
    %w(1005 1000 100),
  ],
  #2
  [
    %w(2013 5000 100),
    %w(2013 5000 100),
  ],
  #0
]
=end

data_sets.each do |data_set|
  puts EmployeesContainer.new(data_set).render_to_string
end

Measured memory_bytes: 6132
#include <bits/stdc++.h>
using namespace std;
const int maxn=2e5+5;
struct node
{
    int x, y;
}edg[maxn];
int book[maxn];

int main()
{
    int n, m, i, j, ans=0;
    cin>>n>>m;
    for(i=0; i<m; i++)
    {
        scanf("%d%d", &edg[i].x, &edg[i].y);
        if(edg[i].x>edg[i].y)swap(edg[i].x, edg[i].y);
        if(edg[i].x==1)book[edg[i].y]=1;
    }
    for(i=0; i<m; i++)
    {
        if(edg[i].y==n && book[edg[i].x])ans=1;
    }
    if(ans)printf("POSSIBLE\n");
    else printf("IMPOSSIBLE\n");
}


Measured memory_bytes: 2560
#include <bits/stdc++.h>
const int INF = 1e9;
const int MOD = 1e9+7;
const long long LINF = 1e18;
#define dump(x)  cout << 'x' << ' = ' << (x) << ` `;
#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define rep(i,n) for(ll i=0;i<(n);++i)
#define REPR(i,n) for(ll i=n;i>=0;i--)
#define FOREACH(x,a) for(auto& (x) : (a) )
typedef long long ll;
using namespace std;
typedef pair<ll, ll> P;

template<typename T>
void print(const vector<T> &x) {
    int n = x.size();
    rep(i,n) {
        cout << x[i];
        if (i!=n-1) cout<<" ";
        else cout << endl;
    }
}

template<typename T>
void print(const vector<vector<T>> &x) {
    int n = x.size();
    rep(i,n) {
        rep(j,x[i].size()) {
            cout << x[i][j] << " ";
        }
        cout << endl;
    }
}

template<typename T>
void print(const vector<T> &x, int n) {
    rep(i,n) {
        cout << x[i];
        if (i!=n-1) cout<<" ";
        else cout << endl;
    }
}

template<typename T>
void print(const vector<vector<T>> &x, int n, int m) {
    rep(i,n) {
        rep(j,m) {
            cout << x[i][j] << " ";
        }
        cout << endl;
    }
}

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

void input_init() {
    cin.tie(0); ios::sync_with_stdio(false);
}

typedef long double ld;

int main(int argc, char const *argv[]) {
    ld a,b; cin>>a>>b;
    ld h,m; cin>>h>>m;

    ld PI = acos(-1.0);

    ld A = (60*h+m)/720*(2*PI);
    ld B = m/60*(2*PI);
    ld deg = A-B;
    cout << fixed << setprecision(15);
    cout << sqrt(a*a+b*b - 2.0*a*b*std::cos(deg)) << '\n';

    return 0;
}

Measured memory_bytes: 4124