Pages

Tuesday, November 30, 2010

UVA Problem#10346

Question:
http://uva.onlinejudge.org/external/103/10346.html 

Solution:

Find the pattern and derive the following formula (total_cigar and butt initally set to 0) and simply simulate the process...

while (n > 0) {
  total_cigar += n; /* accumulate all new cigars so far */
  butt += n; /* after Peter smokes these n cigar, we have n butts */
  n = butt / k; /* so these n butts become new cigars */
  butt %= k; /* butts left are reserved for future cigars */
}

Source: http://www.comp.nus.edu.sg/~stevenha/programming/acmoj.html

int main(){
....
....
sum = n, x = n;
        while(x >= k)
            sum += (x / k), x = (x / k) + (x % k);
....
.....
}

No comments:

Post a Comment