fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. int number_operations[101];
  6. int _set[] = {1, 5, 7, 10};
  7.  
  8. void bfs(){
  9.     queue<int> q;
  10.  
  11.     // initialize
  12.     for (int i = 0; i < 101; i++)
  13.         number_operations[i] = 1<<30;
  14.  
  15.     q.push(0);
  16.     number_operations[0] = 0;
  17.  
  18.     // do BFS
  19.     while (!q.empty()){
  20.  
  21.         int v = q.front();
  22.         q.pop();
  23.         for (int i = 0; i < 4; i++){
  24.             int _new = v + _set[i];
  25.  
  26.             if (_new > 100) // set a max number to find
  27.                 continue;
  28.  
  29.             if (number_operations[v] + 1 < number_operations[_new]){
  30.                 number_operations[_new] = number_operations[v] + 1;
  31.                 q.push(_new);
  32.             }
  33.         }
  34.  
  35.     }
  36. }
  37.  
  38. int main(){
  39.  
  40.  
  41.     bfs();
  42.     // 9*10 + 1*7 + 1*1
  43.     printf ("number of operations to reach %d is %d\n", 98, number_operations[98]);
  44.     printf ("number of operations to reach %d is %d", 12, number_operations[12]);
  45. }
  46.  
Success #stdin #stdout 0s 3464KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
number of operations to reach 98 is 11
number of operations to reach 12 is 2
https://ideone.com/Xec19L
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!