Warning

### Ukázka převodu zápisu do z/do jiných základů

#include <cstdio>
#include <iostream>
#include <math.h>

using namespace std;

int reverse( int a ) {
int b = 0;
while( a > 0 ) {
b = b*10 + a%10;
a /= 10;
}
return b;
}

int frombase( int n, int b ){
int powb = 1;
int res = 0;
int digit;
while( n > 0 ) {
digit = n % 10;  // extract the digit
res = res + digit*powb;
powb *= b;
n /= 10;        // make next digit available
}
return res;
}

int tobase( int n, int b ) {
// note: cannot make do without proper division and remainder
int pow10 = 1;
int res = 0;
int digit;
while( n > 0 ){
digit = n % b; // extract the digit
res = res + digit*pow10;
pow10 *= 10;
n /= b;  // make next digit available
}
return res;
}

int main( int argc, char ** argv ) {

int a, b;
while( true ) {
//cin >> a; if( a < 0 ) break; cout << reverse(a) << endl;
//cin >> a >> b; if( a < 0 ) break; cout << frombase(a, b) << endl;
cin >> a >> b; if( a < 0 ) break; cout << tobase(a, b) << endl;
}
return 0;
}

### Ukázky pro 11. seminář 26.5.2016

// UVA 11648 - Divide The Land
#include <stdio.h>
#include <iostream>
#include <cmath>

using namespace std;

double a, b, c, d, h;

double areaDifferenceUpperLower(double upperh, double lowerh) {
double lenMidLineEF = d + (a-d) * upperh/h;
double upper = ((lenMidLineEF + d) * upperh )/2;
double lower = ((a + lenMidLineEF) * lowerh )/2;
return upper-lower;
}

double f (double x) {
}

// <xL, xR> is a currently processed segment
// in which at least one root of f exists,
// i.e. values of function f in xL and xR must attain opposite signs
double solveBisection(double xL, double xR) {
double epsilon = 0.00000001;
double xMid, fxL = f(xL), fxR = f(xR), fxMid ;
while(xR - xL > epsilon) {
xMid = (xL+xR) / 2;
fxMid = f(xMid);
if (fxL * fxMid <= 0) { xR = xMid; fxR = fxMid; }
else                  { xL = xMid; fxL = fxMid; }
}
return (xL+xR)/2;
}

int main() {
int N;
double hopt;
cin >> N;
for(int i = 0; i < N; i++) {
cin >> a >> d >> b >> c;
// trapezoid height
h = sqrt((-a+b+c+d) * (a+b+c-d) * (a-b+c-d) * (a+b-c-d)) / (2*abs(d-a));
// optimal height
hopt = solveBisection(0, h);
printf("Land #%d: %.6f %.6f\n", i, b*hopt/h, c*hopt/h);
}

return 0;
}

// UVA 313 - Intervals
#include <stdio.h>
#include <algorithm>
#include <iostream>
#include <cmath>

using namespace std;

// Let P be a shade border point on the floor.
// Suppose that Bx = 0 (everything is shifted horizontally), it makes formulas less cluttered.
// The equation of the line BP is then (By)*X + (Px)*Y - By*Px = 0.
// The distance of (Sx, Sy) from the line BP is exactly r.
// Use the distance formula
// dist( point, line) = |a*point_x + b*point_y + c| / sqrt(a^2 + b^2).
// where a*X+b*Y+c is the equation of the line.
// Plug By, Px, Sx, Sy into the quadratic equation
// dist(point, line) = r
// and solve for P.
// Shift x-coord of P by Bx back to its correct position.

struct floorPt { double xcoord; bool startShade; };

bool compare_floorPt (floorPt pt1, floorPt pt2)
{return pt1.xcoord < pt2.xcoord;}

int main() {  // UVA 313
int N;
double Bx, By, Sx, Sy, r;  // input
double P1, P2;  // shade borders on the floor, P1 < P2
double a, b, c, D;  //coeffs of qua eq. D is discriminant
floorPt floorPts[2*500];

while (true) { // one case
cin >> N; if (N == 0) break;
cin >> Bx >> By;
for(int i = 0; i < N; i++) {
cin >> Sx >> Sy >> r;
// move Sx by Bx to the left;
Sx -= Bx;

a = (Sy-By)*(Sy-By)-r*r;
b = 2*By*Sx*(Sy-By);
c = By*By*(Sx*Sx-r*r);
D = b*b-4*a*c;
P1 = (-b-sqrt(D))/(2*a);
P2 = (-b+sqrt(D))/(2*a);

// fill floor points array
floorPts[2*i] = {P1, true};
floorPts[2*i+1] = {P2, false};

}
// sort floor points
std::sort(floorPts, floorPts+2*N, compare_floorPt);

// output shades, move back to position by Bx
for(int i = 0; i < 2*N; i++) {
printf("%.2f ", floorPts[i].xcoord + Bx);
}
else {
printf("%.2f\n", floorPts[i].xcoord + Bx);
}
}
printf("\n");
} // end of case
return 0;
}

int main() {  // UVA 737

int x1, x2, y1, y2, z1, z2; // lower and upper bounds of intersection cuboid
int N, x, y, z, s;          // no of cubes and current cube, s = size

while (true) {
cin >> N;
if (N == 0) break;

x1 = y1 = z1 = INT_MIN;
x2 = y2 = z2 = INT_MAX;

for( int i = 0; i < N; i++) {
cin >> x >> y >> z >> s;
x1 = max(x1, x);   y1 = max(y1, y);   z1 = max(z1, z);
x2 = min(x2, x+s); y2 = min(y2, y+s); z2 = min(z2, z+s);
}

if( (x1 >= x2) || (y1 >= y2) || (z1 >= z2) )
cout << 0 << endl;
else
cout << (x2-x1)*(y2-y1)*(z2-z1) << endl;
}
return 0;
}

### Ukázky pro 11. seminář 5.5.2016

#include <algorithm>
#include <iostream>
#include <cmath>
#include <climits>

using namespace std;

int N;
long long int maxv[400][400];
long long int minv[400][400];
char op [400];
int values[400];

long long int getmax(int i1, int k, int i2) { // k divides past k-th elem
if (op[k] == '+')
return maxv[i1][k]+maxv[k+1][i2];
if (op[k] == '-')
return maxv[i1][k]-minv[k+1][i2];
if (op[k] == '*')
return max(max(maxv[i1][k]*maxv[k+1][i2], minv[i1][k]*maxv[k+1][i2]),
max(maxv[i1][k]*minv[k+1][i2], minv[i1][k]*minv[k+1][i2]));
return max(max(maxv[i1][k]+maxv[k+1][i2], maxv[i1][k]-minv[k+1][i2]),     // + and -
max(max(maxv[i1][k]*maxv[k+1][i2], minv[i1][k]*maxv[k+1][i2]), // *
max(maxv[i1][k]*minv[k+1][i2], minv[i1][k]*minv[k+1][i2])));
}

long long int getmin(int i1, int k, int i2) { // k divides past k-th elem
if (op[k] == '+')
return minv[i1][k]+minv[k+1][i2];
if (op[k] == '-')
return minv[i1][k]-maxv[k+1][i2];
if (op[k] == '*')
return min(min(maxv[i1][k]*maxv[k+1][i2], minv[i1][k]*maxv[k+1][i2]),
min(maxv[i1][k]*minv[k+1][i2], minv[i1][k]*minv[k+1][i2]));
return min(min(minv[i1][k]+minv[k+1][i2], minv[i1][k]-maxv[k+1][i2]),     // + and -
min(min(maxv[i1][k]*maxv[k+1][i2], minv[i1][k]*maxv[k+1][i2]), // *
min(maxv[i1][k]*minv[k+1][i2], minv[i1][k]*minv[k+1][i2])));
}

void setmaxmin(int i1, int i2) {
maxv[i1][i2] = LLONG_MIN;
minv[i1][i2] = LLONG_MAX;
for( int  k = i1; k < i2; k++) {
maxv[i1][i2] = max(maxv[i1][i2], getmax(i1, k, i2));
minv[i1][i2] = min(minv[i1][i2], getmin(i1, k, i2));
}
}

void allmaxmin() {
// fill main diagonal
for(int i = 0; i < N; i++) {
maxv[i][i] = minv[i][i] = maxv[i+N][i+N] = minv[i+N][i+N] = (long long int) values[i];
op[i+N] = op[i];
}

// fill all diagonals above the main diagonal,
// up to and including (N-1)-th diagonal
int i2;
for( int idiag = 1; idiag < N; idiag++ )
for( int i1 = 0; i1 < 2*N-1-idiag; i1++ ){
i2 = i1+idiag;
setmaxmin(i1, i2);
}
}

//......................................................................
//          D E B U G     L I S T I N G
//......................................................................
void listmaxmin(){
for( int i = 0; i < N; i++)
printf("%4d", maxv[i][i+N-1]);
printf("\n");
for( int i = 0; i < N; i++)
printf("%4d", minv[i][i+N-1]);
printf("\n");

printf("--------------------\n");

for( int i = 0; i < 2*N; i++) {
for( int j = 0; j < 2*N; j++)
printf("%4d", maxv[i][j]);
printf("\n");
}
printf("--------------------\n");

for( int i = 0; i < 2*N; i++) {
for( int j = 0; j < 2*N; j++)
printf("%4d", minv[i][j]);
printf("\n");
}
}

//......................................................................
//                M A I N
//......................................................................

int main() {
N = 3;
op[0] = '*'; op[1] = '?'; op[2] = '+';
values[0] = 2; values[1] = 4; values[2] = 7;
allmaxmin();
listmaxmin();
return(0);
}

### Ukázky pro 8. seminář 14.4.2016

// maximum  safe n = 62, binCoeff(62,31) == 465428353255261088
// safe: binCoeff(n, k) < 2^64 for any n, k.
// if n > 62 then for some k  it may hold binCoeff(n, k) < 2^64
// e.g. binCoeff(63,31) = 916312070471295267 > 2^64 = 18446744073709551616
// eg. binCoeff(80,21) = 10100903263463355200 < 2^64,
// but binCoeff(80,22) = 27088786024742634400 > 2^64
unsigned long long int binCoeff( int n, int k ) {
unsigned long long int  coeff = 1;
for( int d = 1; d <= k; d++ ) {
coeff *= n;
coeff /= d;
n--;
}
return coeff;
}

### Ukázky pro 6. seminář 31.3.2016

/////////////////////////////////////////////////////////////////////////
int main() {  // SPOJ M00PAIR

int digi [1000][301] = {0};  // digits

// precompute all
int cy, sum;
digi [2][0] = 1;
for(int i = 3; i < 1000; i++) {
sum = cy = 0;
for(int j = 0; j < 301; j++) {
sum = cy + 2*digi [i-2][j] + digi [i-1][j];
ff[i][j] = sum%10;
cy = sum/10;
}
}

int n, digit;
while (cin >> n) {
if (n == 1) { cout << 0 << endl; continue;}
digit = 301;
while(digi [n][--digit] == 0);
while(digit >= 0)
cout << digi [n][digit--];
cout << endl;
}
return 0;
}

### Ukázky pro 4. seminář 17.3.2016

/////////////////////////////////////////////////////////////////////////
// 10003 - Cutting Sticks

#include <stdio.h>
#include <string.h>

#define MAXN 50
#define MAXC 50000

int main(void)
{
int i, j, k, l, maxL, N, L[MAXN + 2], C[MAXN + 1][MAXN + 2];

scanf("%d", &maxL);

while (maxL != 0)
{
scanf("%d", &N);

L[0] = 0;
for (i = 1; i <= N; i++)
scanf("%d", L + i);
L[N + 1] = maxL;

for (i = 0; i <= N; i++)
{
C[i][i + 1] = 0;
for (j = i + 2; j <= N + 1; j++)
C[i][j] = MAXC;
}

for (l = 2; l <= N + 1; l++)
{
for (i = 0; i <= N + 1 - l; i++)
{
j = i + l;

for (k = i + 1; k < j; k++)
{
if (C[i][j] > (C[i][k] + C[k][j] + L[j] - L[i]))
C[i][j] = (C[i][k] + C[k][j] + L[j] - L[i]);
}
}
}

printf("The minimum cutting is %d.\n", C[0][N + 1]);

scanf("%d", &maxL);
}

return 0;
}

/////////////////////////////////////////////////////////////////////////
// SPOJ MMAXPER
int main() {
// Longer and Shorter sides of the rectangle
int Lprev = 0, Sprev = 0, LprevOpt = 0, SprevOpt = 0;
int Lcurr, Scurr,  LcurrOpt, ScurrOpt, foo;
int n;

cin >> n;
for(int i = 0; i < n; i++) {

cin >> Lcurr >> Scurr;
if (Lcurr < Scurr) { foo = Lcurr; Lcurr = Scurr; Scurr = foo;}
if (i == 0) {
LcurrOpt = Lcurr;
ScurrOpt = Scurr;
}
else {
LcurrOpt = max(LprevOpt + abs(Sprev-Scurr), SprevOpt + abs(Lprev-Scurr)) + Lcurr;
ScurrOpt = max(LprevOpt + abs(Sprev-Lcurr), SprevOpt + abs(Lprev-Lcurr)) + Scurr;
}

Lprev = Lcurr; Sprev = Scurr;
LprevOpt = LcurrOpt; SprevOpt = ScurrOpt;
}
cout << max(LcurrOpt, ScurrOpt) << endl;

return 0;
}

/////////////////////////////////////////////////////////////////////////
int main() {  // SPOJ BYTESH1

int U[3], L[3], S[3]; // DP table window for  Upper, Lower, Straight
int T, n;

cin >> T;

for(int i = 0; i < T; i++) {

cin >> n;
U[0] = U[1] = L[0] = L[1] = 0; S[0] = S[1] = S[2] = 1; // init DP table

for(int k = 0; k < n-1; k++){
U[2] = L[2] = (U[1] + S[0]) % 10000;       // DP table rules
S[2] = (S[0]+S[1] + U[1] + L[1]) % 10000;

L[0] = U[0] = U[1]; L[1] = U[1] = U[2];  // shift DP table window
S[0] = S[1]; S[1] = S[2];
}
cout << S[2] << endl;
}

return 0;
}

/////////////////////////////////////////////////////////////////////////
int main() {  // UVA 10359

int ff [251][100] = {0};

// precompute all
int cy, sum;
ff[0][0] = ff[1][0] = 1; ff[2][0] = 3;
for(int i = 3; i < 251; i++) {
sum = cy = 0;
for(int j = 0; j < 100; j++) {
sum = cy + 2*ff[i-2][j] + ff[i-1][j];
ff[i][j] = sum%10;
cy = sum/10;
}
}

int n, digit;
while (cin >> n) {
digit = 100;
while(ff[n][--digit] == 0);
while(digit >= 0)
cout << ff[n][digit--];
cout << endl;
}

return 0;
}

//1206167596222043702328864427173832373471562340267089208744349833415761767083

/////////////////////////////////////////////////////////////////////////
int main() {  // UVA 900
int n;
long long int f [51];

f[0] = f[1] = 1;
for(int i = 2; i < 51; i++)
f[i] = f[i-1] + f[i-2];

while (true) {
cin >> n;
if (n == 0) break;
cout << f[n] << endl;
}

return 0;
}

/////////////////////////////////////////////////////////////////////////
int main() { // UVA 532

int Nmax = 30;  // has not sentinel borders
char maze [Nmax][Nmax][Nmax];
int dist [Nmax][Nmax][Nmax];
int L, R, C, INF = INT_MAX;
int S0, S1, S2, E0, E1, E2;

int q [Nmax*Nmax*Nmax][3];

while (true) {

cin >> L >> R >> C;
if (L+R+C == 0) break;

string mazeline;
for(int i = 0; i < L; i++)
for(int j = 0; j < R; j++) {
cin >> mazeline;
fill(dist[i][j],dist[i][j] + C, INF);
for(int k = 0; k < C; k++)
if (mazeline[k] == 'S') { S0 = i, S1 = j; S2 = k;}
else if (mazeline[k] == 'E') { E0 = i, E1 = j; E2 = k;}
else if (mazeline[k] == '#')  {dist[i][j][k] = -1;} // forbid walls
}

// run standard BFS
q[0][0] = S0; q[0][1] = S1; q[0][2] = S2;
dist[S0][S1][S2] = 0;
head = 0; tail = 1;
while(true) {  // terminates in End -- success granted

if (S0 > 0 && dist[S0-1][S1][S2] == INF) {
dist[S0-1][S1][S2] = dist[S0][S1][S2]+1;
q[tail][0] = S0-1; q[tail][1] = S1; q[tail++][2] = S2;
}
if (S0 < L-1 && dist[S0+1][S1][S2] == INF) {
dist[S0+1][S1][S2] = dist[S0][S1][S2]+1;
q[tail][0] = S0+1; q[tail][1] = S1; q[tail++][2] = S2;
}
if (S1 > 0 && dist[S0][S1-1][S2] == INF) {
dist[S0][S1-1][S2] = dist[S0][S1][S2]+1;
q[tail][0] = S0; q[tail][1] = S1-1; q[tail++][2] = S2;
}
if (S1 < R-1 && dist[S0][S1+1][S2] == INF) {
dist[S0][S1+1][S2] = dist[S0][S1][S2]+1;
q[tail][0] = S0; q[tail][1] = S1+1; q[tail++][2] = S2;
}
if (S2 > 0 && dist[S0][S1][S2-1] == INF) {
dist[S0][S1][S2-1] = dist[S0][S1][S2]+1;
q[tail][0] = S0; q[tail][1] = S1; q[tail++][2] = S2-1;
}
if (S2 < C-1 && dist[S0][S1][S2+1] == INF) {
dist[S0][S1][S2+1] = dist[S0][S1][S2]+1;
q[tail][0] = S0; q[tail][1] = S1; q[tail++][2] = S2+1;
}

if ( dist[E0][E1][E2] < INF ) {
cout << dist[E0][E1][E2] << endl;
break;
}
} // while true
}
}

### Ukázky pro 3. seminář 10.3.2016

#### Example: Union-Find Data Structure

Can be used to solve 10608 - Friends and 10596 - Morning Walk.

#define MAXN 200

int p[MAXN], r[MAXN];

int find(int i)
{
return (i != p[i]) ? (p[i] = find(p[i])) : p[i];
}

void merge(int i, int j)
{
// PRECONDITION: i == p[i], j == p[j], i != j.
if (r[i] > r[j]) { int k = i; i = j; j = k; }
p[i] = j;
r[j] += (r[i] == r[j]);
}

### Ukázky pro 2. seminář 3.3.2016

//archive 2756  - Crazy tea party
// reverse the order of guests around the table, only neigbours swaps are allowed
// minimize no. of swaps.
int main() {
int T, n ;
cin >> T;
while(T-- > 0) {
cin >> n;
cout << (n*n - 2*n + (n%2))/4 << endl;
}
return 0;
}

//archive 2158 - Factorial
// For given N, find the number of trailing zeros in N!.
int main() {
int N, n, zeros;
cin >> N;

for(int i = 0; i < N; i++) {
cin >> n;
zeros = 0;
while(n > 0)
zeros += (n /= 5);
cout << zeros << endl;
}

return 0;
}

// archive 3078 - Alphacode
// String contains only digits 0-9. In how many ways can it be decomposed to substrings
// from the set {1, 2, 3, 4, ..., 25, 26}?
int main() {
string code;
int count1, count2, foo, currval;
while(true) {
cin >> code;
if (code[0] == '0') break;

count1 = count2 = 1; currval = 0;
for(int i = 0; i < code.size(); i++) {
currval = (currval%10)*10+ ((int)code[i]-48);
if (currval > 26  || currval < 10)
count1 = count2;
else if (currval % 10 == 0)
count2 = count1;
else { foo = count2; count2 += count1; count1 = foo;}
//cout << count1 << " " << count2 << endl;
}
cout << count2 << endl;
}
return 0;
}

//UVA 112- Tree Summing
// Given a binary tree in prefix bracket format, check if there is a path from the root
// to a leaf which sum of node values equals to the given prescribed values.
// (annoyingly long code...)
int main() {

stack <int> st;
int leafstring = (( '('*256+ ')') *256 + '(')*256 + ')'; // leaf == "()()"

bool start = true;
int I, nodeval = 0, sum = 0, last4 = 0;
string line, found = "no";

while( std::getline (std::cin,line)) {
for(int i = 0; i < line.size(); i++) {
if (line[i] == ' ') continue;
// detect number
if ('0' <= line[i] && line[i] <= '9' ){
nodeval = nodeval*10 + (int)line[i] - 48;
}
// register new node or the prescribed sum
else if (line[i] == '(') {
if (start) {I = nodeval; nodeval = 0; start = false; continue;}
if ((char)(last4 & 255) != ')' ) { // last char was digit
st.push(nodeval);
sum += nodeval;
nodeval = 0;
}
}
// leaving node, possibly leaf
else if (line[i] == ')'){
if ((last4 == leafstring) && (I == sum))
found = "yes";
if ((char)(last4 & 255) == ')' ) {  // last char was also ')'
sum -= st.top();
st.pop();
}
if (st.empty()) {
cout << found << endl;
start = true;
found = "no";
}
}

// register last 4 chars in sliding window
last4 = (last4 << 8) + (int)line[i];
} // for char in line
} // while any line exists
return 0;
}

// Number of paths of lenght N which have exactly X peaks in height Y.
// Number of rooted ordered trees with N nodes which have exactly X leaves in depth Y.
public class UVA986 {

// In each point we register for each K no of paths which end in this point and
// have exactly K peaks in the prescribed height.
// up[node][K] = up[node_Prev_Lower][K] + dn[node_Prev_Higher][K]
// dn[node][K] = dn[node_Prev_Higher][K] + X
//     if (K == prescribed Height) X = dn[node_Prev_Lower][K-1]  // new peak here
//     else 					             X = dn[node_Prev_Lower][K] // no new peak here

// DP tables corresponding to paths which last edge goes up resp. down.
static int [][][] up = new int [41][23][22];
static int [][][] dn = new int [41][23][22];

// r peaks at height k
static int num(int n,  int r_peaks,  int k_height ) {

//clear table
for(int i = 0; i < 2*n+1; i++)
for(int j = 0; j < n+3; j++)
for(int m = 0; m < r_peaks+2; m++)
up[i][j][m] = dn[i][j][m] = 0;

k_height++; // move up r because of indexing from 0 in the table
up[0][1][1] = 1;  // first edge of the first path
for(int in = 1; in <= 2*n; in++)
for(int ihe = 1; ihe < n+2; ihe++)
for(int ipe = 1; ipe < r_peaks+2; ipe++) {
up[in][ihe][ipe] = up[in-1][ihe-1][ipe] + dn[in-1][ihe+1][ipe];

dn[in][ihe][ipe] = dn[in-1][ihe+1][ipe];
if (ihe == k_height)
dn[in][ihe][ipe] += up[in-1][ihe-1][ipe-1];
else
dn[in][ihe][ipe] += up[in-1][ihe-1][ipe];
}
// for all;

return  dn[2*n][1][r_peaks+1];
}

public static void main(String[] args) throws IOException {
String line;
int n, r, k;

while ((line = br.readLine()) != null ) {
StringTokenizer st = new StringTokenizer(line);
n  = Integer.valueOf(st.nextToken());
r  = Integer.valueOf(st.nextToken());
k = Integer.valueOf(st.nextToken());

System.out.printf("%d\n", num(n,r,k));
}
}
}

### Jiné

//: C20:PriorityQueue1.cpp
#include <iostream>
#include <queue>
#include <cstdlib>
#include <ctime>
using namespace std;

int main() {
priority_queue<int> pqi;
srand(time(0)); // Seed random number generator
for(int i = 0; i < 100; i++)
pqi.push(rand() % 25);
while(!pqi.empty()) {
cout << pqi.top() << ' ';
pqi.pop();
}

} ///:~

/**
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
class Boxer{
public:
string name;
int strength;
};
struct Comp{
bool operator()(const Boxer& a, const Boxer& b){
return a.strength<b.strength;
}
};
int main(){
+  Boxer boxer[3];
boxer[0].name="uday", boxer[0].strength=23;
boxer[1].name="manoj", boxer[1].strength=33;
boxer[2].name="rajiv", boxer[2].strength=53;

priority_queue< Boxer, vector<Boxer>, Comp> pq;
pq.push(boxer[0]);
pq.push(boxer[1]);
pq.push(boxer[2]);
Boxer b = pq.top();
cout<<b.name;
//result is Rajiv

return 0;
}
*/

package lps;

import java.util.Arrays;
import java.util.Scanner;

public class BinTree {

static int N;
static int root;
static int nil = -1;
static int [] Val;
static int [] L;
static int [] R;

public static void main(String[] args) {
print(root);
System.out.printf("sum values %d\n", sumvals(root));
System.out.printf("no of leaves %d\n", noOfLeaves(root));
print(root, 0);
}

Scanner input = new Scanner( System.in );
N = input.nextInt();
Val = new int [N];
L = new int [N];
R = new int [N];

root = input.nextInt();
int curr;
for(int i = 0; i < N; i++) {
curr = input.nextInt();
Val[curr] = input.nextInt();
L[curr] = input.nextInt();
R[curr] = input.nextInt();
}
}

static int sumvals(int node) {
if (node == nil) return 0;
return Val[node] + sumvals(L[node]) + sumvals(R[node]);
}

static int noOfLeaves(int node) {
if (L[node] == nil  && R[node] == nil) return 1;
return noOfLeaves(L[node]) + noOfLeaves(R[node]);
}

static void print(int node) {
if (node == nil) return;
System.out.printf("%d %d %d %d\n", node, Val[node], L[node], R[node]);
print(L[node]);
print(R[node]);
}

static void print(int node, int depth) {
if (node == nil) return;

print(R[node], depth+4);
for(int i = 0; i < depth; i++) System.out.printf(" ");
System.out.printf("[%d %d]\n", node, Val[node]);

//print(R[node], depth+4);
print(L[node], depth+4);
}

/*
11 3
0 9 -1 -1
1 10 0 2
2 20 -1 -1
3 30 1 6
4 40 -1 -1
5 50 4 8
6 60 5 10
7 70 -1 -1
8 80 7 9
9 90 -1 -1
10 100 -1 -1
*/

}

package lps;
// peg soli
import java.util.Arrays;
import java.util.Scanner;

public class Graph {

static int N, M;     // nodes and edges
static int [][] neighList; // https://en.wiktionary.org/wiki/neighbour
static int [] dg;

static int [][] edgeList;

static int dist[];

public static void main(String[] args) {
hr();
printNeighList();
hr();
BFS_dists(0);
printDists();

}

// --------------------------------------------------------------------------
//                   P R O C E S S
// --------------------------------------------------------------------------

static void BFS_dists(int startNode) {
// allocate data structures
int [] q = new int [N];
boolean [] Fresh = new boolean [N];
if (dist == null) dist = new int [N];

// intialize search
int head =0, tail = 0, currNode, neigh;
q[0] = startNode;
Arrays.fill(Fresh, true); Fresh[startNode] = false;
dist[startNode] = 0;

// perform search
while (head <= tail) { // queue not empty
// check all neighbours of currNode
for(int j = 0; j < dg[currNode]; j++) {
neigh = neighList[currNode][j];
if (Fresh[neigh]) {  // insert to queue and set the distance
q[tail++] = neigh;
dist[neigh] = dist[currNode]+1;
Fresh[neigh] = false;
}
}
} // while
}

neighList = new int [N][1];  // expand neighbour list later
dg = new int [N];            // populated by zeroes by default
for(int i = 0; i < N-1; i++)
for(int j = i+1; j < N; j++)

if (dg[i] >= neighList[i].length) // adjust array size if necessary
neighList[i] = Arrays.copyOf(neighList[i], dg[i]*2);
neighList[i][dg[i]++] = j;

if (dg[j] >= neighList[j].length) // adjust array size if necessary
neighList[j] = Arrays.copyOf(neighList[j], dg[j]*2);
neighList[j][dg[j]++] = i;
}
}

// --------------------------------------------------------------------------
//                      L O A D
// --------------------------------------------------------------------------

Scanner input = new Scanner( System.in );
N = input.nextInt();
for(int i = 0; i < N; i++)
for(int j = 0; j < N; j++)
M /= 2; // each edge counted twice
}

Scanner input = new Scanner( System.in );
N = input.nextInt();
M = input.nextInt();
edgeList = new int [M][2];
for(int i = 0; i < M; i++) {
edgeList[i][0] = input.nextInt();
edgeList[i][1] = input.nextInt();
}
}

Scanner input = new Scanner( System.in );
N = input.nextInt();
M = input.nextInt();
input.nextLine(); // technicality! skip EOL

neighList = new int [N][]; // expand neighbour list later
dg = new int [N];
int node, neigh; String inLine; String [] tokens;
for(int i = 0; i < N; i++) {
inLine = input.nextLine();
tokens = inLine.split("\\s+"); // enother technicality, suboptimal!
node = Integer.valueOf(tokens[0]);
dg[node] = tokens.length-1;
neighList[node] = new int [dg[node]];
for(int j = 0; j < dg[node]; j++)
neighList[node][j] = Integer.valueOf(tokens[j+1]);
}
}

// --------------------------------------------------------------------------
//                   P R I N T
// --------------------------------------------------------------------------

static void printNeighList () {
System.out.printf("%d %d\n", N, M);
for(int n = 0; n < N; n++) {
System.out.printf("%d  ", n);
for(int j = 0; j < dg[n]; j++)
System.out.printf("%d ", neighList[n][j]);
System.out.printf("\n");
}
}

static void printMx () {
for(int i = 0; i < N; i++) {
for(int j = 0; j < N; j++)
System.out.printf("\n");
}
}

static void printEdges () {
System.out.printf("%d %d\n", N, M);
for(int n = 0; n < N; n++) {
System.out.printf("%d %d\n", edgeList[n][0], edgeList[n][1]);
}
}

static void printDists () {
for(int i = 0; i < N; i++)
System.out.printf("%d %d\n", i, dist[i]);
}

static void hr() {
System.out.printf("--------------------------------------------\n");
}

/*
program divisibility;
var i, x, n, y, a, t : integer;
begin
for i := 1 to t do begin
a := x;
while a < n do begin
if a mod y <> 0 then write(a, ' ');
a := a + x;
end;
end; {for}
writeln;

end.
*/
}

1  0.00  0.00
2  1.00  1.00
3  1.58  2.58
4  2.00  4.58
5  2.32  6.91
6  2.58  9.49
7  2.81  12.30
8  3.00  15.30
9  3.17  18.47
10  3.32  21.79

static boolean onborder2(double x, double y) {
for(int i = 0; i < pows2.length; i++)
if (x <= pows2[i] && y > pows2[i]) return true;
return false;
}

static int [] pows2 = {1,2,4,8,16,32,64,128,256,512,1024,2048,4096, 8192,16384,32768, 65536, 131072, 262144, 524288,  1048576, 2097152, 4194304};

static void bitsinfact() {
double fbits = 0.0;
double last_fbits = fbits;
double log2n;
int n = 1;
while (fbits <= 4*1024*1024.0) { // 2^22
log2n = (Math.log(n)/Math.log(2));
fbits += log2n;
if (onborder2(last_fbits, fbits))
System.out.printf("%d %.3f  %.3f\n", n-1,  last_fbits, fbits);
last_fbits = fbits;
n += 1;
}
}

public static void main(String[] args) {
bitsinfact();
}
}

2 1.000  2.585
3 2.585  4.585  // corresponds to 1960
5 6.907  9.492    // corresponds to 1970
8 15.299  18.469    // corresponds to 1980
12 28.835  32.536     // corresponds to 1990
20 61.077  65.470       // ...
34 127.795  132.924
57 254.485  260.343
98 511.492  518.121
170 1019.369  1026.787
300 2041.278  2049.511
536 4091.998  4101.067
966 8191.380  8201.297
1754 16378.090  16388.868
3210 32767.327  32778.976
5910 65527.312  65539.841
10944 131064.158  131077.576
20366 262142.934  262157.248
38064 524281.326  524296.542
71421 1048567.205  1048583.330
134480 2097136.293  2097153.330  // corresponds to 2150
254016 4194288.154  4194306.108

abbbaaaaaa
abbbaaaaaa
abbbaaaaaa
aaaaaaaaaa
aaaaaaaaaa
aaccaaaaaa
aaccaaaaaa

a1 b1 b1 b1 a1 a1 a1 a1 a1 a1
a1 b1 b2 b2 a1 a2 a2 a2 a2 a2
a1 b1 b2 b3 a1 a2 a3 a3 a3 a3
a1 a1 a1 a1 a1 a2 a3 a4 a4 a4
a1 a2 a2 a2 a2 a2 a3 a4 a5 a5
a1 a2 c1 c1 a1 a2 a3 a4 a5 a6
a1 a2 c1 c2 a1 a2 a3 a4 a5 a6

0, 1, 5, 2, 8, 3, 9, 2, 8, 7, 7, 8, 4, 7, 3, 8, 4, 1, 5, 4,
4, 5, 9, 6, 2, 7, 3, 6, 2, 1, 1, 2, 8, 1, 7, 2, 8, 5, 9, 8,
8, 9, 3, 0, 6, 1, 7, 0, 6, 5, 5, 6, 2, 5, 1, 6, 2, 9, 3, 2,
2, 3, 7, 4, 0, 5, 1, 4, 0, 9, 9, 0, 6, 9, 5, 0, 6, 3, 7, 6,
6, 7, 1, 8, 4, 9, 5, 8, 4, 3, 3, 4, 0, 3, 9, 4, 0, 7, 1, 0,

0, 1, 5, 2, 8, 3, 9, 2, 8, 7, 7, 8, 4, 7, 3, 8, 4, 1, 5, 4,
4, 5, 9, 6, 2, 7, 3, 6, 2, 1, 1, 2, 8, 1, 7, 2, 8, 5, 9, 8,
8, 9, 3, 0, 6, 1, 7, 0, 6, 5, 5, 6, 2, 5, 1, 6, 2, 9, 3, 2,
2, 3, 7, 4, 0, 5, 1, 4, 0, 9, 9, 0, 6, 9, 5, 0, 6, 3, 7, 6,
6, 7, 1, 8, 4, 9, 5, 8, 4, 3, 3, 4, 0, 3, 9, 4, 0, 7, 1, 0, 

// Checks if two segments intersect
static boolean xx (int iA, int iB, int iC, int iD) {
int ABx = x[iB]-x[iA];
int ABy = y[iB]-y[iA];
int CDx = x[iD]-x[iC];
int CDy = y[iD]-y[iC];
int det = ABy*CDx - ABx*CDy; // determinant decides linear (in)dependence
if (det == 0) { // parallel vectors (linearly dependent)
if ((x[iC]-x[iA])*ABy - (y[iC]-y[iA])*ABx != 0) // area triangle ABC
return false;  // parallel distinct lines
// A B C D colinear, check their bounding boxes
return    Math.min(x[iA], x[iB]) <= Math.max(x[iC], x[iD])
&& Math.min(x[iC], x[iD]) <= Math.max(x[iA], x[iB])
&& Math.min(y[iA], y[iB]) <= Math.max(y[iC], y[iD])
&& Math.min(y[iC], y[iD]) <= Math.max(y[iA], y[iB])	;
}

// non parallel vectors, is point of intersection inside both segments?
int num1 = (x[iA]-x[iC])*CDy + CDx*(y[iC]-y[iA]);
int num2 = (y[iC]-y[iA])*ABx - ABy*(x[iC]-x[iA]);
if (det < 0)
return ((0 >= num1) && (num1 >= det) && (0 >= num2) && (num2 >= det));
else
return ((0 <= num1) && (num1 <= det) && (0 <= num2) && (num2 <= det));
}