Olimpiade Sains Provinsi (OSP) 2017 - Komputer, Nomor 47

Question

HUBUNGAN KAKEK-CUCU Pada soal ini, Anda diminta untuk memroses silsilah dinasti kerajaan KITOKI. Setiap lelaki dinasti ini diberi nomor 1, 2, ... , N. Pendiri dinasti kerajaan diberi nomor 1. Anda diberi dafter hubungan ayah-anak, dimana A[Y]=X menyatakan bahwa Y adalah ayah dari X. Dari hubungan ayah-anak, Anda dapat mendeteksi hubungan kakek-cucu karena jlka z adalah ayah dari Y, dan Y adalah ayah dari X, maka Z adalah kakek dari X. Dari sebuah daftar hubungan ayah-anak, Anda diminta untuk mem

Mamat Rahmat · Accepted Answer

Perhatikan bahwa setiap cucu pasti memiliki tepat 1 orang kakek (sedangkan seorang kakek bisa memiliki banyak cucu).

Untuk menghitung hubungan kakek-cucu, kita cukup menghitung banyaknya orang bisa berperan sebagai cucu, yaitu orang yang memiliki kakek. Orang yang memiliki kakek adalah orang yang bukan pendiri dinasti kerajaan (root dari tree) dan bukan anak dari pendiri dinasti kerajaan.

Untuk itu, kita cukup membuat program untuk menghitung orang yang ayahnya bukan pendiri dinasti kerajaan. Hitung banyaknya $i$ sehingga $A[i] \neq 1$

var
    N, i, total : longint;
    a: array[1..100010] of longint;

begin
    readln(N);
    for i := 2 to N do
    begin
        if (A[i] <> 1) then
            inc(total);
    end;
    writeln(total);
end.

Erik Prasetio · Answer

Menurut saya, semua orang pasti memiliki kakek kecuali anak dari pendiri dinasti jadi selain anak pendiri masing-masing punya hubungan dengan kakek. #include stdio.h int main(){ int N,tmp,ans; scanf( %d , N); ans=N-1;//dikurangi pendiri for(int i=2;i =N;i++){ scanf( %d , tmp); if(tmp==1)ans--; } printf( %d
 ,ans); }

Kadek Surya Mahardika · Answer

#include bits/stdc++.h using namespace std; int main(){ ios::sync_with_stdio(0); cin.tie(0); int n,data[100001]; vector int v; int ans; cin n; for(int i=1;i =n-1;i++){ cin data[i]; } multiset int m(data+1, data+n); set int s(data+1, data+n); for(auto x:s){ v.push_back(m.count(x)); } for(int i=1;i v.size();i++){ ans += v[i]; } cout ans 
 ; //for(auto x:v) cout x 
 ; } CMIIW

Yosua Krisnando · Answer

DFS

Olimpiade Sains Provinsi (OSP) 2017 - Komputer, Nomor 47

4 jawaban