SRM 611 - Proclub/Knowledge-Repo GitHub Wiki

Div 2 Soal Easy

Problem

Fox Ciel thinks that the number 41312432 is interesting. This is because of the following property: There is exactly 1 digit between the two 1s, there are exactly 2 digits between the two 2s, and so on.

Formally, Ciel thinks that a number X is interesting if the following property is satisfied: For each D between 0 and 9, inclusive, X either does not contain the digit D at all, or it contains exactly two digits D, and there are precisely D other digits between them.

You are given a String x that contains the digits of a positive integer. Return "Interesting" if that integer is interesting, otherwise return "Not interesting".

Constraints

x will correspond to an integer between 1 and 1,000,000,000, inclusive.
x will not start with a '0'.

Examples

0: "2002"
Returns: "Interesting"
There are 0 digits between the two 0s, and 2 digits between the two 2s, so this is an interesting number.

1: "1001"
Returns: "Not interesting"
There should be 1 digit between the two 1s, but there are 2 digits between them. Hence, this number is not interesting.

2: "41312432"
Returns: "Interesting"
This is the number in the statement.

3:
"611"
Returns: "Not interesting"
There is only one digit 6 in this number, so it's not interesting.

4:
"64200246"
Returns: "Interesting"

5:
"631413164"
Returns: "Not interesting"
This number contains the digit 1 three times.

Mistakes

Dean

#include <iostream>
#include <string>
    
using namespace std;
    
class InterestingNumber {
public:
  string isInteresting(string str) {
    int num;
    bool interesting = true;
    for (int i = 0; i < str.length(); i++) {
      if (str[i] == '-')
        continue;
      num = (str[i] - '0') + 1;
      if (i + num >= str.length() || str[i+num] != str[i]) {
        interesting = false;
        break;
      }
     
      str[i+num] = '-';
    }
    
    if (interesting)     
      return string("Interesting");
    else
      return string("Not interesting");
  }
};

Hanya miss pada syarat:

"For each D between 0 and 9, inclusive, X either does not contain the digit D at all, or it contains exactly two digits D"

Nisa(Dyo)

#include <iostream> 
#include <string> 
    
using namespace std; 
class InterestingNumber 
{ 
  public: 
    string isInteresting(string x) 
    { 
      int pjg=x.size(); 
      string s; 
      int jumlah[100000]; 
      bool isi[100000]; 
      for(int i=0;i<pjg;i++)
      { 
            int n=x[i]-'0'; 
            isi[i]=false; 
            jumlah[n]=0; 
        } 
        for(int i=0;i<pjg;i++) 
        { 
          int nilai=x[i]-'0'; 
          int nilai1=nilai+i+1; 
          jumlah[nilai]+=2; 
          if(isi[i]!=true) 
          { 
            if(jumlah[nilai]>2) { 
              s="Not interesting"; 
              return s; 
            } 
            if(x[i]!=x[nilai1]) 
            { 
              s="Not interesting";  
              return s; 
            }else 
            { 
              isi[i]=true; 
              isi[nilai1]=true; 
            } 
          } 
      } 
      s="Interesting"; 
      return s; 
    } 
};

Beruntungnya, kode ini lolos system test. Beberapa hal yang dapat diperbaiki:

Return dapat langsung berupa nilai, tanpa harus dimasukkan ke dalam variabel terlebih dahulu.
Akses x[nilai1] berpotensi error jika nilai1 lebih besar dari pjg panjang string. Sebelum mengaksesnya, pastikan nilai1 merupakan index yang valid.
Lebih cepat melakukan inisiasi nilai 0 atau false pada array dengan menggunakan memset.
Detail pada soal menunjukkan, array sebesar 15 elemen sudah cukup.

#include <iostream> 
#include <string> 
    
using namespace std; 
class InterestingNumber 
{ 
  public: 
    string isInteresting(string x) 
    { 
      int pjg=x.size(); 
      int jumlah[15]; 
      bool isi[15]; 
    
      memset(jumlah, 0, sizeof(jumlah));
      memset(isi, 0, sizeof(isi));
    
      for(int i=0;i<pjg;i++) 
      { 
        int nilai=x[i]-'0'; 
        int nilai1=nilai+i+1; 
        jumlah[nilai]+=2; 
        if(!isi[i]) 
        { 
          if(jumlah[nilai]>2 || nilai1 >= pjg || x[i]!=x[nilai1]) { 
            return "Not interesting"; 
        } else 
        { 
          isi[i]=true; 
          isi[nilai1]=true; 
        } 
      } 
    } 
    return "Interesting"; 
};

Contoh Solusi Berbeda

class InterestingNumber {
  int cnt[10];
  int place[10];
  public:
    string isInteresting(string);
};
     
string InterestingNumber::isInteresting(string x) {
  int len = x.length();
  memset(cnt, 0, sizeof cnt);
  for (int i = 0; i < len; i++)
  {
    int v = x[i] - '0';
    if (cnt[v] == 0) place[v] = i;
    else if (cnt[v] == 1) place[v] = i - place[v] - 1;
    ++cnt[v];
  }
      
  bool ok = true;
  for (int i = 0; i < 10; i++)
  {
    if (cnt[i] != 0 && cnt[i] != 2) ok = false;
    if (cnt[i] == 2 && place[i] != i) ok = false        
  }
      
  return ok ? "Interesting" : "Not interesting";
}