Warning
This page is located in archive.

http://www.tutorialspoint.com/compile_cpp11_online.php

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) {
return  areaDifferenceUpperLower(h-x, 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;
 
      // solve quadratic equation:
      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
    int noofshades = 0;
    for(int i = 0; i < 2*N; i++) {
      if( floorPts[i].startShade ) {
        if (noofshades == 0)
          printf("%.2f ", floorPts[i].xcoord + Bx);
        noofshades++;
      }
      else {
        if (noofshades == 1)
          printf("%.2f\n", floorPts[i].xcoord + Bx);
        noofshades--;
      }
    }
    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

roury ppt, roury pdf

LCS: https://cw.fel.cvut.cz/wiki/_media/courses/a4b33alg/alg10_2015c.pdf

/////////////////////////////////////////////////////////////////////////
// 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];
int head, tail;
 
 
while (true) {
 
  // read maze
  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
    S0 = q[head][0]; S1 = q[head][1]; S2 = q[head][2]; head++;
 
    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;
   BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
   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));
   }
}
}


Konec ukázek


Jiné

http://www.fi.muni.cz/usr/jkucera/tic/tic0229.html

//: 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) {
		loadFromStd();
		print(root);
		System.out.printf("sum values %d\n", sumvals(root));
		System.out.printf("no of leaves %d\n", noOfLeaves(root));
		print(root, 0);
	}
 
static void loadFromStd() {
	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 [][] adjMx;
 
static int [][] edgeList;
 
static int dist[];
 
 
public static void main(String[] args) {
	//loadGraphNeighListFromStd();
	loadGraphMxFromStd();
	hr();
	adjMx2neighList();				
	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
		currNode = q[head++];
		// 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
}
 
static void adjMx2neighList(){
	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 (adjMx[i][j] == 1) {  // add edge
 
				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
// --------------------------------------------------------------------------
 
static void loadGraphMxFromStd() {
	Scanner input = new Scanner( System.in );
	N = input.nextInt();
	adjMx = new int [N][N];
	for(int i = 0; i < N; i++)
		for(int j = 0; j < N; j++)
			M += (adjMx[i][j] = input.nextInt());
	M /= 2; // each edge counted twice 
}  
 
static void loadGraphEdgeListFromStd() {
	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();
	}
}
 
static void loadGraphNeighListFromStd() {
	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("%d ", adjMx[i][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
readln(t);
for i := 1 to t do begin
  readln(n, x, y);
  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));
}

courses/a4b36acm/support.txt · Last modified: 2017/02/06 15:48 by berezovs