問題＃22：ITトレーニング-主要企業の現在の問題と課題

ご質問

1. 故障した機械
   

   ネジを生産する10台の機械があり、それぞれ重量が1グラムです。 ただし、機械の1つは、重量が0.9グラムのねじのみを生産します。 計量は1回のみ許可されており、故障した機械を特定する必要があります。

   
   
   翻訳

   ネジを生産する10台の機械があり、それぞれの重量は1グラムです。 確かに、機械の1つは0.9グラムの重量のネジを生産します。 欠陥のあるネジを生産する機械を見つけるために、1つの計量（ 約ネジ ）のみが許可されます。
   
2. ホームズと暗号
   

   シャーロックホームズは暗号化されたメッセージをデコードしていました。 暗号化の場合、DISTANCEはIDTUBECNとして書き込まれ、DOCUMENTはODDVNTNEとして書き込まれます。
   
   彼がHTTQYADを解読するのを手伝ってもらえますか？
   

   
   
   翻訳

   シャーロックホームズは暗号化されたメッセージを解読します。 暗号では、DISTANCEはIDTUBECNとして指定され、DOCUMENTはODDVNTNEとして指定されます。
   
   HTTQYADを解読するのを手伝ってもらえますか？

タスク

1. 研究センターと希少元素
   

   研究チームは、希少元素を発見した地域に研究センターを設立したいと考えており、そこにある研究の全体的なコストを削減できるように、すべての希少元素に可能な限り近づけることを望んでいますレア要素のすべての場所は道路で接続されていることを考えると、研究センターは道路上でのみ構築できることも与えられています。チームはこのタスクをコーダーに割り当てることにしました。タスク：-希少元素の特定の場所から研究センターの最適な位置を見つけます。
   
   場所はマトリックスセル形式で指定されます。1は道路を表し、0は道路を表しません。 希少要素の数とその位置も指定され（数<= 5）、正方行列の順序は（20）以下でした。
   

   
   
   翻訳

   研究チームは、いくつかの希少元素が発見されている地域に研究センターを設立したいと考えています。 全体的なコストを削減するために、すべての要素のソースにできるだけ近い位置に配置したいと考えています。 要素のソースは道路で接続されています。 また、研究センターは道路の近くにしか建設できません。 チームはタスクを開発者に任せることを決定し、可能性を感じた場合は、要素の場所に基づいて最適なセンターの場所を見つけます。
   
   場所はマトリックスの形式で与えられます。セル内の1は道路の存在を意味し、0-は存在しないことを意味します。
   要素の位置も指定されます（数値<= 5）。 正方行列の次数<= 20。
2. スタックダウンまたはアップ
   

   典型的なプロセスでは、プログラムのスタックセグメントには、関数が呼び出されるたびに保存される情報とともにローカル変数が含まれます。 関数が呼び出されるたびに、戻り先のアドレスと、マシンレジスタの一部など、呼び出し元の環境に関する特定の情報がスタックに保存されます。 次に、新しく呼び出された関数は、自動変数と一時変数のためにスタック上のスペースを割り当てます。
   
   スタックは、コードがコンパイルされる環境に応じて、下向きまたは上向きに成長する場合があります。つまり、コンパイラに依存します。 プログラムを書き留めて、スタックが下向きになるか上向きになるかを判断しますか？

   
   
   翻訳

   通常、プログラムスタックセグメントには、関数が呼び出されるたびに保存される情報を持つローカル変数が含まれます。 関数が呼び出されると、戻りアドレスと環境に関する情報（たとえば、いくつかのレジスター）がスタックに格納されます。 次に、呼び出された関数は、自動変数および一時変数のためにスタック上で実行されます。
   
   スタックは、コードがコンパイルされる環境に応じて、つまりコンパイラに依存して大きくなったり小さくなったりします。 スタックが成長しているか成長しているかを判断するプログラムを実装します。
3. 次の大きな要素
   

   配列を指定して、すべての要素の次の大きい要素（NGE）を出力します。 要素xの次の大きい要素は、配列内のxの右側にある最初の大きい要素です。 より大きな要素が存在しない要素は、次に大きい要素を-1と見なします。
   
   例：
   a）どの配列でも、右端の要素には常に-1の次の大きい要素があります。
   b）降順でソートされた配列の場合、すべての要素の次に大きい要素が-1になります。
   c）入力配列[4、5、2、25]の場合、各要素の次に大きい要素は次のとおりです。
   

   要素nge
       4-> 5
       5-> 25
       2-> 25
       25-> -1
   

   
   d）入力配列[13、7、6、12]の場合、各要素の次に大きい要素は次のとおりです。
   

     要素nge
       13-> -1
       7-> 12
       6-> 12
       12-> -1
   

   
   

   
   
   翻訳

   配列を指定して、各要素に次に大きい要素（NGE）を入力します。 xの次に大きい要素は、配列内のxの右側にある最初の大きい要素です。 そのような要素が存在しない場合、NGEは-1です。
   例：
   a）どの配列でも、右端の要素は常にNGE = -1です。
   b）降順でソートされた配列の場合、すべての要素のNGE = -1があります。
   c）配列要素[4、5、2、25]の場合、NGEは次のようになります。
   

    NGE要素
       4-> 5
       5-> 25
       2-> 25
       25-> -1
   

   
   d）配列要素[13、7、6、12]の場合、NGEは次のようになります。
   

     NGE要素
       13-> -1
       7-> 12
       6-> 12
       12-> -1
   

   
   

解決策

1. 質問1

   jmdorianは正しい答えを出しました -各マシンのボルトの数をその数に等しい重量を量ります。 バランスの取れたディスクを使用するオプションには注意が必要です。
   
   
   
2. 質問2

   回答：木曜日。
   決定原則
   
   
   
3. タスク1

   最適化の可能性があるソリューション：
   

   using namespace std ; bool ar[21][21]; bool visited[21][21]; int ans[21][21]; int xa[]={0,-1,0,1}; int yb[]={1,0,-1,0}; int n; typedef struct Point{ int x,y; }P; typedef struct C { int x,y; int dis; } C; bool issafe(int x,int y) { return (x>=0 && x<n &&="" y="">=0 && y<n && ar[x][y] && !visited[x][y]); } void bfs(int x,int y) { queue<c> q; C in; in.x=x; in.y=y; in.dis=0; q.push(in); visited[x][y]=1; while(!q.empty()) { C c=q.front(); q.pop(); int a=cx; int b=cy; int d=c.dis; ans[a][b]=d; for(int i=0;i<4;i++) { int nx=a+xa[i]; int ny=b+yb[i]; if(issafe(nx,ny)) { visited[nx][ny]=1; in.x=nx; in.y=ny; in.dis=d+1; q.push(in); } } } } int main() { cin>>n; for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { cin>>ar[i][j]; } } int q; cin>>q; P rare[q]; int fans=10000; int mx=-1; for(int i=0;i<q;i++) { int a,b; cin>>a>>b; rare[i].x=a; rare[i].y=b; } for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { memset(ans,10000,sizeof(ans)); int flag=0; memset(visited,0,sizeof(visited)); mx=-1; if(ar[i][j]) { bfs(i,j); for(int k=0;k<q;k++) { if(ans[rare[k].x][rare[k].y]==10000) { flag=1; break; } } if(!flag) { for(int k=0;k<q;k++) { mx=max(mx,ans[rare[k].x][rare[k].y]); } } fans=min(fans,mx); } } } cout<<fans<<endl; } 

   
   
   
   
4. タスク2

   多くが正解。 元のバージョン：
   

    void stupdown(int *main_local_addr) { int fun_local; if (main_local_addr < &fun_local) printf("Stack grows upward\n"); else printf("Stack grows downward\n"); } int main() { // st's local variable int main_local; stupdown(&main_local); return 0; } 

   
   
   
   
5. タスク3

   元のソリューション：
   

    // A Stack based C++ program to find next // greater element for all array elements. #include<bits/stdc++.h> using namespace std; /* prints element and NGE pair for all elements of arr[] of size n */ void printNGE(int arr[], int n) { stack<int> s; /* push the first element to stack */ s.push(arr[0]); // iterate for rest of the elements for (int i=1; i<n; i++) { int next = arr[i]; if (s.empty() == false) { // if stack is not empty, then // pop an element from stack int element = s.top(); s.pop(); /* If the popped element is smaller than next, then a) print the pair b) keep popping while elements are smaller and stack is not empty */ while (element < next) { cout << element << " --> " << next << endl; if (s.empty() == true) break; element = s.top(); s.pop(); } /* If element is greater than next, then push the element back */ if (element > next) s.push(element); } /* push next to stack so that we can find next greater for it */ s.push(next); } /* After iterating over the loop, the remaining elements in stack do not have the next greater element, so print -1 for them */ while (s.empty() == false) { cout << s.top() << " --> " << -1 << endl; s.pop(); } } /* Driver program to test above functions */ int main() { int arr[] = {11, 13, 21, 3}; int n = sizeof(arr)/sizeof(arr[0]); printNGE(arr, n); return 0; }