Hi, everyone.

Why same source code is slower on GCC-5.1 C compiler and very fast on GCC-5.1 C++.

See 38119970 for GCC C runs 468 ms.

And 38119937 for GCC C++ runs 78 ms.

Are there different optimization compiler flags ?

Привет, всем.

Я решаю одну задачу, и как подзадача требуется организовать рекурсия (возможно, ДП).

Подзадача:

Дано натуральные числа: K, a[1], a[2], .., a[N], где 1<=K<=10^9, 1<=a[i]<=35, 1<=N<=35, sum(a[i])<=35. Требуется разделить эти a[1], a[2], .. , a[N] на несколько не пустых и не пересикающих множества, которые у каждого множества сумма их элементов (НЕ количество, а именно сумма). является делителям число K, конечно, если такое разбиение возможен.

И вот как найти эти множества?

Спасибо.

Привет, всем.

Вроде бы не так сложно, но я немогу решить, помогите, пожалуйста решить эту задачу.

Спасибо.

1. step. Go to Problemset.
2. step. Open any of a problem.
3. step. Change current english language to russian from right-up of screen button.
4. step. Press Submit (Отослать) .

CF can't find number of current open problem.

Pure C have scanf and printf, gets , getchar, ... puts, putchar functions.

C++ have std::cin, std::cout iostream objects ...

But, I'd like Pascal's read and write functions, they are easy to write and easy to understand.

So, why we can't emulate read and write in C++ and C++11 ?!

Go...

// write basic types: int, long long, double , and string
int read(int& a) { return scanf("%d",&a);}

int read(long long& a) { return scanf("%lld",&a);}
int read(char&c){ return (c = getchar()), 1; }
int read(double& a) { return scanf("%lf",&a);}
int read(char s[], int n){  return fgets(s, n, stdin) != 0;}
template<size_t n> int read(char (&s)[n]){ return read((char*)s, n);}
int read(string&s){int c ; while((c = getchar()) != '\n' && c != EOF)s+=(char)c; return 1;}

// now generalize for all situations, C++11 variadic template helps us.
template<typename ... T>
int read(T& ... a)
{
    using shadow = int[];
    shadow sh = {read(a) ...};
    return sizeof(sh)/sizeof(sh[0]);
}


//usage: 
int main(){

int a,b,c,d,e;
read(a,b,c,d,e);

printf("max is : %d\n", max({a,b,c,d,e});

return 0;
}

int write(int a){return printf("%d", a);}
int write(ll a){ return printf("%lld", a);}
int write(double f){ return printf("%.8f", f);}
int write(char c){return printf("%c",c);}
int write(const char * s){ return printf("%s",s);}
int write(string const& s){ return write(s.c_str());}


// Generalize for all situations.
template<typename ...T>
int write(T const& ... a)
{
    using shadow = int[];
    shadow sh = {write(a)...};
    return sizeof(sh) / sizeof(sh[0]);
}

// writeln == write  +  line break .
template<typename ... T>
int writeln(T const& ... a){ writeln(a..., '\n');}

There a lot of books for algorithms, data structures. But for competitive programming need good math knowledge, also,

Which math books are best for competitive programming ??

I mean, there algebra, number theory, statistics, probability, arithmetic, computation geometry and etc...

This is (Conrcete-Mathematics) already good for me, now.

UPD: Number theory book. Rosen K.H. Elementary Number Theory

UPD-2: https://artofproblemsolving.com Thanks -emli- for good resource.

UPD-3: Matters Computational Thanks anta, for comment here

Thnx.

I decided to rewrite this post, previously has been deleted.

I know there a many of posts low-level i/o.

scanf/printf solves slowly i/o, partially, but not always.

Most generic usage i/o — is read and write integers, so I'll write about it without a hundred lines of source code.

1. Read integers.

For simplicity, all input file content loaded to a big buffer, and it will be parsed.

char in[1<<23] ; // a big buffer
char const* o ; // pointer to buffer.

And for detecting end of buffer, put '\0' — terminating symbol to end of buffer ( as plain c-string).

Now loading the file:

void load(){  o = in;   in [   fread(in,  1,  sizeof(in ) - 4 ,  stdin ) ] = 0; }

fread - returns number of reading symbols, we just use this for put '\0' terminating symbol to end of buffer.

Reading a unsigned integer:

unsigned readUInt(){
      unsigned u = 0;
      
      while( *o && *o <= 32) ++o ; //  skip spaces
    
      while ( *o >='0' && *o <='9') u = (u << 3) + (u << 1) + (*o++ -'0');
      return u;
}

By default most implementations used u = u * 10 + (*o++ - '0'),
but u * 10 = u * 8 + u * 2 = (u << 3) + (u <<1) I don't know it gives speed, but with shifting the code become happy :)

Reading signed integer.

Some theory of signed integer representation, in most situation see here

-u == ~u + 1

There ~ — bitwise inverting.

And ~u == u ^ 0xFFFFFFFF or ~u == u ^ ~0

Let start writing method

    int readInt()
    {
         unsigned u = 0, s = 0; // s = 0, if integer positive, s = ~0 - if integer negative
         while(*o && *o <= 32)++o; // skip spaces
         
         if (*o == '-')s = ~0, ++o; else if (*o == '+') ++o; // determine sign
         while( *o >='0' && *o <= '9') u = (u << 3) + (u << 1) + (*o ++ - '0');

         return (u^s) + !!s; // ??????? : s = 0 :  (u^s) + !!s = (u^0) + !!0 = u + 0 = u, and
                             //           s = ~0:  (u^s) + !!s = (u ^ ~0) + !! ~0 = (u^0xFFFFFFFF) + 1 = ~u + 1 = -u
         
    }

How to use this complete?

#include <cstdio>

char const * o;
char in[1<<23];

void load(){ o = in ;  in [ fread(in,1,sizeof(in)-4,stdin)] = 0; }
unsigned readUInt(){
     unsigned u = 0;
     while(*o && *o <= 32)++o;
     while(*o >='0' && *o <='9') u = (u << 3) + (u << 1) + (*o++ -'0');
     return u;
}
int readInt(){
    unsigned u = 0, s = 0;
    while(*o && *o <= 32)++o;
    if (*o == '-') s = ~0, ++o; else if(*o == '+') ++o;
    while(*o >='0' && *o <='9') u = (u << 3) + (u << 1) + (*o++ - '0');

    return (u ^ s) + !!s;
}

int main()
{
     load();
     int n = readInt();
     int s = 0;
     for(int i= 0; i < n; ++i)s += readInt();

     printf("summa = %d\n", s);
     
     return 0;
}

Compare low-level i/o: 24139587 with std::cin , std::cout 24133798

Benchmark: read and write 10^6 numbers took 120~150 milliseconds where scanf/printf ~650 milliseconds.

for competetive programming this single method is enough for reading integers:

   typedef long long ll;
   typedef unsigned long long ull;

    ll  readInt(){
          ull u = 0 , s = 0;
          while(*o && *o <= 32)++o;
          if (*o == '-') s = ~s, ++o; else if (*o == '+') ++o;
          while(*o >='0' && *o<='9') u = (u << 3) + (u << 1) + (*o++ -'0');

          return (u ^ s) +!!s; 
    }

2. Writing integers.

There are need a big buffer and pointer, again.

typedef long long ll;
char out[1<<23];
char * w = out; // initialize with &out[0] - beginning of the buffer.

There a single writeInt method, arguments: integer u and serarator c .

// need to implement this method.
void writeInt( ll u, char separator); // u - integer, separator - will printed after the integer, most situations is space, or '\n'.

AND flush method, which we must call at the end of all operations.

// flush - must be called before end of program.
void flush(){  fwrite(out, 1, w - out, stdout); }

For implementing writeInt need temporary buffer :

void writeInt(ll u, char separator)
{
     char tmpbuf[20]; int i;
     if ( u < 0 ){ *w ++ = '-'; u = - u ; }
     i = 20;
     do tmpbuf[--i] = u % 10 + '0'; while(u/=10); // write last digits of u to tmpbuf from end to begin.
     
     // now write tmpbuf to out[] buffer from w pointer.
     do *w++ = tmpbuf[i++]; while(i < 20);

    // and separator
     *w++ = separator;
}

It's all.

------------------------------------------------------------------------------------------------------

UPD: Wrapper classes.

Let simplify all above codes.

typedef long long ll;
typedef unsigned long long ull;

char in[1<<23];
char out[1<<23];

//wrapper to reader
struct scanner
{
    char const* o;
    scanner(): o(in){ load(); }
    void load(){ in[ fread(in , 1, sizeof(in)- 4, stdin)] = 0; }
    ll readInt(){
        ull u = 0, s = 0;
        while(*o && *o <= 32)++o;
        if (*o == '-')s = ~s, ++o; else if (*o == '+')++o;
        while(*o >='0' && *o <='9') u = (u << 3) + (u << 1) + (*o++ - '0');
        return (u^s) + !!s;
    }
};

//wrapper to writer
struct writer
{
    char * w;
    writer(): w(out){}
   ~writer(){ flush();}
   void flush(){ if (w!=out){ fwrite(out,1,w-out,stdout); w = out; } } 
   void writeInt(ll u, char c){
        char t[20]; int i = 20; 
         if (u < 0){ *w++ = '-'; u = -u;}
        do t[--i] = u % 10 + '0'; while(u/=10);
        do *w++ = t[i++]; while(i < 20);
        *w++ = c;
   }
};


//A+B
int main()
{
    scanner sc;
    writer pw;
    pw.writeInt(sc.readInt() + sc.readInt(), '\n');
}

UPD-2 Reverse-Writer

Sometimes, needed restore answer from end to begin, for example shortest path in graph from source to target. Most solution is save answer to array, vector, and reverse it and print. But there exists another solution with reverse-writer.

Reverse-writer -is simple writes numbers to array from end to begin in reverse order.

Let code it

typedef long long ll;
typedef unsigned long long ull;

char out[1<<23];

struct reverse_writer
{
   char * w;
   reverse_writer(): w( out + sizeof(out) ){} // w - indicated end of  out[] array
   ~reverse_writer(){ flush(); }
   void flush(){  
      if (w != out + sizeof(out) ) 
          fwrite(w, 1, out + sizeof(out) - w, stdout), w = out + sizeof(out);
    }
   
   void writeInt(ll u, char c){
       *--w = c; // print separator at first
       (u < 0) ? (u = -u, c ='-') : c = '\0' ; // determine sign
       do *--w = u%10 + '0'; while(u/=10); // put digits 
       if(c)   *--w= c ;// write sign 
   }
};


// USAGE:

vi g[maxn];
int parent[maxn];
int n,m,source, target;
int main()
{
     scanner sc; 
     reverse_writer pw;
     
     n = sc.readInt(), m = sc.readInt(), source = sc.readInt(), target = sc.readInt();

      for(int i= 0; i<m;++i){ 
          int a = sc.readInt(), b = sc.readInt(); 
         g[a].push_back(b); g[b].push_back(a);
      }

      memset(parent, -1, sizeof(parent)); 
     dejkstra(source, target);

     int total = 0;  char c = '\n';
     for(int i = target ; i != -1; i = parent[i], ++total) 
               pw.writeInt( i , c), c = ' ';
     pw.writeInt(total, '\n');
}

GOoD lUck!

Known value of A ( 0 <= A < 2^32), and

D1 = A XOR (B1 XOR ... XOR Bn);  
D2 = A AND (B1 AND B2 AND ... AND Bn);  
D3 = A OR  (B1 OR B2 OR ... OR Bn)

values. (0<= D1,D2,D3 < 2^32) but, B1, B2,..,Bn — are unknown values in [0 .. 2^32-1].

Can I find X = B1 AND B2 AND .. AND Bn ??

Thanks.

Уважаемые люди, помогите решить эту задачу http://codeforces.net/gym/101181/problem/D у меня 68-ом тесте ошибка. 68 ошибкаhttp://codeforces.net/gym/101181/submission/22695394 заранье спасибо!!!

UPD: AC 26-попытки!! очень интересная задачка, спасибо за автору.

Не давно узнал от источника http://neerc.ifmo.ru/subregions/uzbekistan.html проводится четверфинал в Узбекистане 13-ноября 2016 году. Я желаю успехи всем олимпиадисты в Узбекистане! Я всегда болею за вас!!!

O'zbek tilida ham ikki o'giz gap. Yigitlar (va albatta qiz olimpiadistlar ham :) ), olg'a!!! hammaga yana bir marta muvaffaqiyat tilayman.

Привет, всем. Я долго пыталься решить вот этого задачу, но кажеться моя идея неверно. Моя идея:``

1. если d > L (где L = h / cos(alpha/2) — длина конуса), то нет решения.
2. если h <= d <= L — есть решения с одним отрезком (её легко построить).
3. теперь спускаем по вертикально как можно.
4. если мы уже поверхности — все, мы нашел ответь
5. если из текущего точка можно посадить поверхности конус — все, мы нашел ответь
6. посадим самая крайная точка конуса и ищем обратного путь к вершина конуса.

жду ваше мнения. спасибо.