Differences

This shows you the differences between two versions of the page.

Link to this comparison view

courses:a4b36acm1:support [2018/10/03 03:51] (current)
Line 1: Line 1:
 +
 +<​HTML>​
 +<​style>​
 +.code .kw1, .code .kw2, .code .kw4 { color: #00f; font-weight:​ bold; text-decoration:​ underline;}
 +.code .br0, .code .kw3, .code .me1, .code .me2, .code .nu0 { color: #000; }
 +.code .co1, .code .coMULTI { color: #080; font-style: normal; }
 +.code .co2 { color: #888; font-style: normal; }
 +.code .st0 { color: #a31515; }
 +</​style>​
 +</​HTML>​
 +http://​www.tutorialspoint.com/​compile_cpp11_online.php
 +
 +==== Ukázka převodu zápisu do z/do jiných základů ====
 +
 +<code Cpp>
 +#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;
 +}
 +
 +</​code>​
 +
 +
 +==== Ukázky pro 11. seminář 26.5.2016 ====
 +<code Cpp>
 +// 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;
 +}
 +</​code>​
 +
 +<code Cpp>
 +// 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;
 +}
 +</​code>​
 +----
 +<code Cpp>
 +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;
 +}
 +</​code>​
 +
 +
 +
 +==== Ukázky pro 11. seminář 5.5.2016 ====
 +<code Cpp>
 +#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);
 +}
 +</​code>​
 +
 +
 +
 +==== Ukázky pro 8. seminář 14.4.2016 ====
 +<code Cpp>
 +// 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;
 +}
 +
 +</​code>​
 +
 +
 +==== Ukázky pro 6. seminář 31.3.2016 ====
 +<code Cpp>
 +/////////////////////////////////////////////////////////////////////////​
 +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;
 +}
 +
 +</​code>​
 +
 +==== Ukázky pro 4. seminář 17.3.2016 ====
 +
 +{{:​courses:​a4b36acm:​ukazkaprez.pptx| roury ppt}}, {{:​courses:​a4b36acm:​ukazkaprez.pdf| roury pdf}}
 +
 +LCS:  https://​cw.fel.cvut.cz/​wiki/​_media/​courses/​a4b33alg/​alg10_2015c.pdf
 +
 +
 +
 +<code Cpp>
 +/////////////////////////////////////////////////////////////////////////​
 +// 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
 +  }
 +}
 +
 +</​code>​
 +
 +
 +==== Ukázky pro 3. seminář 10.3.2016 ====
 +
 +=== Example: Union-Find Data Structure ===
 +Can be used to solve [[https://​uva.onlinejudge.org/​index.php?​option=com_onlinejudge&​Itemid=8&​category=116&​page=show_problem&​problem=1549|10608 - Friends]] and [[https://​uva.onlinejudge.org/​index.php?​option=com_onlinejudge&​Itemid=8&​category=105&​page=show_problem&​problem=1537|10596 - Morning Walk]].
 +
 +<code Cpp>
 +#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]);
 +}
 +
 +</​code>​
 +==== Ukázky pro 2. seminář 3.3.2016 ====
 +<code Cpp>
 +//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;
 +}
 +</​code>​
 +
 +----
 +
 +<code Cpp>
 +//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;
 +}
 +
 +</​code>​
 +
 +----
 +<code Cpp>
 +// 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;
 +}
 +</​code>​
 +
 +----
 +{{:​courses:​a4b36acm:​112img1.gif?​200|}}
 +
 +<code Cpp>
 +//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;
 +}
 +
 +</​code>​
 +
 +----
 +
 +{{:​courses:​a4b36acm:​986img1.gif?​500|}}
 +
 +<code Cpp>
 +// 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));​
 +   }
 +}
 +}
 +
 +</​code>​
 +
 +----
 +==== Konec ukázek ====
 +----
 +==== Jiné ====
 +
 +http://​www.fi.muni.cz/​usr/​jkucera/​tic/​tic0229.html
 +
 +<code C pp>
 +//: 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;
 +}
 +*/
 +
 +</​code>​
 +
 +<code Cpp>
 +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
 +*/
 +
 +
 +}
 +</​code>​
 +
 +
 +<code Cpp>
 +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.
 +*/
 +}
 +
 +</​code>​
 +
 +
 +<​code>​
 +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
 +</​code>​
 +
 +<code Cpp>
 +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();​
 + }
 +}
 +</​code>​
 +
 +<​code>​
 +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
 +</​code>​
 +
 +<​code>​
 +abbbaaaaaa
 +abbbaaaaaa
 +abbbaaaaaa
 +aaaaaaaaaa
 +aaaaaaaaaa
 +aaccaaaaaa
 +aaccaaaaaa
 +</​code>​
 +
 +<​code>​
 +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
 +</​code>​
 +
 +
 +
 +<​code>​
 +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, 
 +</​code>​
 +
 +<code Cpp>
 +
 +// 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));
 +}
 +
 +</​code>​
 +
  
courses/a4b36acm1/support.txt · Last modified: 2018/10/03 03:51 (external edit)