SRM518

	Level 1	Level 2	Level 3
Div 1	Level 1	Level 2	Level 3
Div 2	Level 1	Level 2	Level 3

Tutorials:

---

Division One - Level Three:

Solution

Source Code:

---

Division One - Level Two:

Solution

Source Code:

---

Division One - Level One:

Solution

The same with the Div2 - 500 pts.

Source Code:

---

Sivision Two - Level Three:

Solution

Source Code:

---

Division Two - Level Two:

Solution

pos[i] represents the biggest character's position but smaller than ith element after ith element.

Source Code:

//Wednesday, September 14, 2011 14:52 CDT
import java.util.*;
import java.util.regex.*;
import java.text.*;
import java.math.*;
import java.awt.geom.*;

public class LargestSubsequence
{
    public String getLargest(String s)
    {
        int N = s.length();
        int[] pos = new int[N];
        for (int i = 0; i < N; i++) {
            pos[i] = i;
        }
        int mmax = -1;
        char c = 96;
        for (int i = 0; i < N; i++) {
            if (c < s.charAt(i)) {
                mmax = i;
                c = s.charAt(i);
            }
            char ch = 'a';
            for (int j = N - 1; j > i; j--) {
                if (s.charAt(i) >= s.charAt(j) && ch <= s.charAt(j)) {
                    pos[i] = j;
                    ch = s.charAt(j);
                }
            }
        }
        for (int i = 0; i < N; i++) {
            System.out.print(pos[i]);
            System.out.print(", ");
        }
        System.out.println();
        String ret = "";
        for (; mmax != pos[mmax];) {
            ret += s.charAt(mmax);
            mmax = pos[mmax];
        }
        ret += s.charAt(pos[mmax]);
        return ret;
    }
}
//Powered by [KawigiEdit] 2.0!

---

Division Two - Level One:

Solution

Source Code:

//Wednesday, September 14, 2011 14:52 CDT
import java.util.*;
import java.util.regex.*;
import java.text.*;
import java.math.*;
import java.awt.geom.*;

public class TwiceString
{
    public String getShortest(String s)
    {
        int N = s.length();
        String ret = "";
        for(int i=0; i<N; i++){
            String str = s + s.substring(i, N);
            if(str.startsWith(s) && str.endsWith(s))
                ret = str;
        }
        return ret;
    }
}
//Powered by [KawigiEdit] 2.0!

SRM519

	Level 1	Level 2	Level 3
Div 1	Level 1	Level 2	Level 3
Div 2	Level 1	Level 2	Level 3

Tutorials:

---

Division One - Level Three:

Solution

Source Code:

---

Division One - Level Two:

Solution

Source Code:

---

Division One - Level One:

Solution

The same with Div2 - 900 pts.

Source Code:

---

Sivision Two - Level Three:

Solution

I just followed the tutorials on official website.

Source Code:

//Wednesday, September 28, 2011 18:08 PDT
import java.util.*;
import java.util.regex.*;
import java.text.*;
import java.math.*;
import java.awt.geom.*;

public class BinaryCards
{
    public long largestNumber(long A, long B) {
        for (int i=60; i>=0; --i)   // 60 = ceil( log2(10 ^ 18) )
            if ( ((A^B) & (1L<<i) ) != 0)
                return A | ((1L<<(i+1))-1);
        return A;
    }
     
 
}
//Powered by [KawigiEdit] 2.0!

---

Division Two - Level Two:

Solution

Solve the problem recursively. It's pretty natural.

Source Code:

//Wednesday, September 28, 2011 18:08 PDT
import java.util.*;
import java.util.regex.*;
import java.text.*;
import java.math.*;
import java.awt.geom.*;

public class ThreeTeleports
{
    public int shortestDistance(int xMe, int yMe, int xHome, int yHome, String[] teleports)
    {
        long dist = Math.abs(xMe - xHome) + Math.abs(yMe - yHome);
        for(int i=0; i<teleports.length; i++){
            String[] strs = teleports[i].split(" ");
            int x1 = Integer.parseInt(strs[0]);
            int y1 = Integer.parseInt(strs[1]);
            int x2 = Integer.parseInt(strs[2]);
            int y2 = Integer.parseInt(strs[3]);
            String[] teles = new String[teleports.length - 1];
            for(int j=0, k=0; j<teleports.length; j++){
                if(i!=j){
                    teles[k++] = teleports[j];
                }
            }
         
            dist = Math.min(dist, Math.abs(xMe - x1) + Math.abs(yMe - y1) + 10L + shortestDistance(x2, y2, xHome, yHome, teles));
            dist = Math.min(dist, Math.abs(xMe - x2) + Math.abs(yMe - y2) + 10L + shortestDistance(x1, y1, xHome, yHome, teles));
        }
        return (int)dist;
    }  
}
//Powered by [KawigiEdit] 2.0!

---

Division Two - Level One:

Solution

Use the sum from 1 to 7, subtract every corresponding day from the sum, leave the only missing one to return.

Source Code:

//Wed Sep 28 18:19:03 PDT 2011
import java.util.*;
import java.util.regex.*;
import java.text.*;
import java.math.*;
import java.awt.geom.*;

public class WhichDay
{
    public String getDay(String[] notOnThisDay)
    {
        int sum = (1 + 7) * 7 / 2;
        for(String str : notOnThisDay){
            sum -= getNumber(str);
        }
        return getDays(sum);
    }
 
    public int getNumber(String s){
        if(s.compareTo("Sunday") == 0) return 7;
        if(s.compareTo("Saturday") == 0) return 6;
        if(s.compareTo("Friday") == 0) return 5;
        if(s.compareTo("Thursday") == 0) return 4;
        if(s.compareTo("Wednesday") == 0) return 3;
        if(s.compareTo("Tuesday") == 0) return 2;
        if(s.compareTo("Monday") == 0) return 1;
        return 0;
    }
 
    public String getDays(int n){
        if(n == 1) return "Monday";
        if(n == 2) return "Tuesday";
        if(n == 3) return "Wednesday";
        if(n == 4) return "Thursday";
        if(n == 5) return "Friday";
        if(n == 6) return "Saturday";
        if(n == 7) return "Sunday";
        return "None";
    }  
}
//Powered by [KawigiEdit] 2.0!

SRM411

	Level 1	Level 2	Level 3
Div 1	Level 1	Level 2	Level 3
Div 2	Level 1	Level 2	Level 3

Tutorials:

---

Division One - Level Three:

Solution

Source Code:

---

Division One - Level Two:

Solution

Source Code:

---

Division One - Level One:

Solution

The same with Div2 - 600 pts.

Source Code:

---

Sivision Two - Level Three:

Solution

Source Code:

---

Division Two - Level Two:

Solution

Dynamic Programming, The most amazing part of this solution is use length of the string as the variable here, since how to cut the string into pieces is the most difficult problem from the start. The idea from tomek's solution is very brilliant and inspiring.

Source Code:

//
import java.util.*;
import java.util.regex.*;
import java.text.*;
import java.math.*;
import java.awt.geom.*;

public class SentenceDecomposition
{
    public final static int mmax = 1000000000;
    public Integer dp[];
    public String str;
    public String[] list;

    public int decompose(String sentence, String[] validWords)
    {
        str = sentence;
        list = validWords;
        dp = new Integer[str.length() + 1];
        int ret = solve(str.length());
        return ret==mmax? -1 : ret;
    }

    public int solve(int len){
        if(dp[len] != null) return dp[len];
        dp[len] = mmax;
        if(len == 0){
            return dp[len] = 0;
        }
        for(String s: list){
            int len2 = s.length();
            if(len2 > len) continue;
            int cost = match(s, str.substring(len-len2, len));
            if(cost == -1) continue;
            dp[len] = Math.min(dp[len], cost + solve(len-len2));
        }
        return dp[len];
    }

    public int match(String a, String b){
        String c = sorted(a);
        String d = sorted(b);
        if(c.compareTo(d) != 0) return -1;
        int ret = 0;
        for(int i=0; i<a.length(); i++){
            if(a.charAt(i) != b.charAt(i))
                ret++;
        }
        return ret;
    }

    public String sorted(String a){
        char[] content = a.toCharArray();
        Arrays.sort(content);
        String ret = new String(content);
        return ret;
    }
  
  
}
//Powered by [KawigiEdit] 2.0!

---

Division Two - Level One:

Solution

Source Code:

//2009/08/29 02:07:24
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <math.h>
#include <sstream>
#include <algorithm>

using namespace std;

class MaximumScoredNumber
{
public:
    int getNumber(int lowerBound, int upperBound)
    {
        int mmax = -1;
        int ret = -1;
        for(int i=upperBound; i>=lowerBound; i--)
        {
            if(mmax < score(i) || mmax == -1)
            {
                mmax = score(i);
                ret = i;
            }
        }
        return ret;
    }
    int score(int n)
    {
        int ret = 0;
        for (int i=0; i*i<=n/2; i++)
            if (issquare(n - i*i))
                ret++;
        return ret;
    }
    bool issquare(int n)
    {
        int a = (int) sqrt(n);
        if (a * a == n) return true;
        return false;
    }
};

SRM366

	Level 1	Level 2	Level 3
Div 1	Level 1	Level 2	Level 3
Div 2	Level 1	Level 2	Level 3

Tutorials:

---

Division One - Level Three:

Solution

Source Code:

---

Division One - Level Two:

Solution

Source Code:

---

Division One - Level One:

Solution

The same with Div2 - 500 pts

Source Code:

---

Sivision Two - Level Three:

Solution

Source Code:

---

Division Two - Level Two:

Solution

Dynamic Programming, using mark[i][j] represents maximum level can be reached by using first i elements, with the maximum level j.

Source Code:

//Wed Sep 21 09:02:50 CDT 2011
import java.util.*;
import java.util.regex.*;
import java.text.*;
import java.math.*;
import java.awt.geom.*;

public class ChangingSounds
{
    public int[] list;
    public int mmax;
    public Integer[][] mark;
    public int maxFinal(int[] changeIntervals, int beginLevel, int maxLevel)
    {
        mmax = maxLevel;
        list = changeIntervals;
        mark = new Integer[list.length+2][mmax+1];
        return solve(0, beginLevel);
    }

    public int solve(int index, int level){
        if(level > mmax) return -1;
        if(level < 0) return -1;
        if(index == list.length) return level;
        if(mark[index][level] != null) return mark[index][level];
        int ret = -1;
        ret = Math.max(ret, solve(index+1, level + list[index]));
        ret = Math.max(ret, solve(index+1, level - list[index]));
        return mark[index][level] = ret;
    }
 
 
}
//Powered by [KawigiEdit] 2.0!

---

Division Two - Level One:

Solution

Source Code:

//2009/08/24 13:28:43
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <sstream>
#include <algorithm>

using namespace std;

class SerialNumbers
{
public:
    vector <string> sortSerials(vector <string> serialNumbers)
    {
        vector<string> ret(serialNumbers);
        for (int i=0; i<ret.size(); i++)
            for (int j=0;j<ret.size();j++)
            {
                if (i!=j && cmp(ret[i], ret[j]) < 0)
                {
                    cout << ret[i] << " " << ret[j] << endl;
                    string temp = ret[j];
                    ret[j] = ret[i];
                    ret[i] = temp;
                    cout << ret[i] << " " << ret[j] << endl;
                }
            }
        return ret;
    }
private:
    int cmp(string a, string b)
    {
        int s1 = sum_of_digits(a);
        int s2 = sum_of_digits(b);
        //cout << "Sum: " << s1 << " " << s2 << endl;
        if (a.size() != b.size()) return a.size() - b.size();
        else if (s1 != s2) return s1 - s2;
        else return a.compare(b);
    }
    int sum_of_digits(string a)
    {
        int sum = 0;
        for (int i=0; i<a.size(); i++)
            if (isdigit(a[i]))
                sum += a[i] - '0';
        return sum;
    }
};

SRM363

	Level 1	Level 2	Level 3
Div 1	Level 1	Level 2	Level 3
Div 2	Level 1	Level 2	Level 3

Tutorials:

---

Division One - Level Three:

Solution

Source Code:

---

Division One - Level Two:

Solution

Source Code:

---

Division One - Level One:

Solution

The same with Div2 - 500

Source Code:

---

Sivision Two - Level Three:

Solution

Source Code:

---

Division Two - Level Two:

Solution

Dynamic Programming. The cost[i] is the cost for i business men. The idea is like cutting the cake, any connection between two persons will divide the table into two parts, since any good handshake cannot cross. So, we can take businessman 0, iterate over all other businessmen and each time count recursively how many shakes are there for the rest. 


The fomula is: f(n) = (sum for all 0 < i <= n) f(i – 1) * f(n – i – 1)

Source Code:

//Tue Sep 20 19:22:38 CDT 2011
import java.util.*;
import java.util.regex.*;
import java.text.*;
import java.math.*;
import java.awt.geom.*;

public class HandsShaking
{
    public long cost[];
 
    public long countPerfect(int n)
    {
        cost = new long[n+1];
        for(int i=0; i<=n; i++){
            cost[i] = new Long(-1);
        }
        solve(n);
        return cost[n];
    }

    public void solve(int n){
        if(n==0) cost[n] = 1;
        if(n==2) cost[n] = 1;
        if(cost[n] != -1) return;
        long ret = 0;
        for(int i=1; i<n; i+=2){
            solve(i-1);
            solve(n-i-1);
            ret += cost[i-1] * cost[n-i-1];
        }
        cost[n] = ret;
        return;
    }
 
 
}
//Powered by [KawigiEdit] 2.0!

---

Division Two - Level One:

Solution

Straight - forward.

Source Code:

//Tue Sep 20 20:53:28 CDT 2011
import java.util.*;
import java.util.regex.*;
import java.text.*;
import java.math.*;
import java.awt.geom.*;

public class MirroredClock
{
    public String whatTimeIsIt(String time)
    {
        String[] t = time.split(":");
        int m = (60 - Integer.parseInt(t[1])) % 60;
        int h = (12 - Integer.parseInt(t[0]) - (m>0?1:0)) % 12;   
        String ret = String.format("%02d:%02d", h, m);
        return ret;
    }
}
//Powered by [KawigiEdit] 2.0!

/***************************************************************************/
//2009/08/24 00:35:48
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <sstream>
#include <algorithm>

using namespace std;

class MirroredClock
{
public:
    string whatTimeIsIt(string time)
    {
        int a, b;
        char c;
        sscanf(time.c_str(), "%d%c%d", &a,&c,&b);
        int e = (60 - b) % 60;
     
        int d = (12 - a - (e+b)/60 ) % 12;
        char s[5];
        sprintf(s, "%.2d%c%.2d", d,c,e);
        return s;
    }
};

SRM352

	Level 1	Level 2	Level 3
Div 1	Level 1	Level 2	Level 3
Div 2	Level 1	Level 2	Level 3

Tutorials:

---

Division One - Level Three:

Solution

Source Code:

---

Division One - Level Two:

Solution

Source Code:

---

Division One - Level One:

Solution

It's the same with Div2-500pts.

Source Code:

---

Sivision Two - Level Three:

Solution

Source Code:

---

Division Two - Level Two:

Solution

Two solutions are provided here, the first one (in Java) is implemented with dynamic programming, while the second one (in C++) calls the function recursively, which count the printed number for '0's and '1's.

Source Code:

//Tue Sep 20 15:54:05 CDT 2011
import java.util.*;
import java.util.regex.*;
import java.text.*;
import java.math.*;
import java.awt.geom.*;

public class NumberofFiboCalls
{
    public int cost[][];
    public int[] fiboCallsMade(int n)
    {
        cost = new int[2][n+1];
        for(int i=0; i<=n; i++){
            cost[0][i] = -1;
            cost[1][i] = -1;
        }
        solve(n);
        int[] ret = new int[2];
        ret[0] = cost[0][n];
        ret[1] = cost[1][n];

        return ret;
    }

    public void solve(int x){
        if(x == 0){
            cost[0][0] = 1;
            cost[1][0] = 0;
        }
        if(x == 1){
            cost[0][1] = 0;
            cost[1][1] = 1;
        }
        if(cost[0][x] != -1 && cost[1][x] != -1)
            return;
        solve(x-1);
        solve(x-2);
        cost[0][x] = cost[0][x-1] + cost[0][x-2];
        cost[1][x] = cost[1][x-1] + cost[1][x-2];
        return;
    }


}
//Powered by [KawigiEdit] 2.0!

//Monday, October 26 2009
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <sstream>
#include <algorithm>

using namespace std;

class NumberofFiboCalls
{
public:
    vector <int> fiboCallsMade(int n)
    {
        count1 = 0;
        count2 = 0;
        fabonacci(n);
        vector<int> v;
        v.push_back(count1);
        v.push_back(count2);
        return v;
    }
    int fabonacci(int n)
    {
        if(n == 0)
        {
            count1++;
            return 0;
        }
        if(n == 1)
        {
            count2++;
            return 1;
        }
        return fabonacci(n-1) + fabonacci(n-2);
    }
    int count1;
    int count2;
};

---

Division Two - Level One:

Solution

Source Code:

//2009/08/22 22:34:24
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <sstream>
#include <algorithm>

using namespace std;

class AttendanceShort
{
public:
    vector <string> shortList(vector <string> names, vector <string> attendance)
    {
        vector<string> v;
        for (int i=0; i<names.size(); i++)
        {
            //v.push_back(names[i]);
            int cnt = 0;
            int pst = 0;
            for (int j=0; j<attendance[i].size(); j++)
            {
                if (attendance[i][j] == 'M') continue;
                if (attendance[i][j] == 'P')
                {
                    cnt ++;
                    pst ++;
                }
                else
                    cnt ++;
            }
            double temp = 100.0 * pst / cnt;
            if (temp < 75.0)
                v.push_back(names[i]);
        }
        return v;
    }
};

SRM325

	Level 1	Level 2	Level 3
Div 1	Level 1	Level 2	Level 3
Div 2	Level 1	Level 2	Level 3

Tutorials:

---

Division One - Level Three:

Solution

Source Code:

---

Division One - Level Two:

Solution

Source Code:

---

Division One - Level One:

Solution

Source Code:

---

Sivision Two - Level Three:

Solution

Source Code:

---

Division Two - Level Two:

Solution

Dynamic Programming.
RGB stores the cost value for each color of every element, while dp[i][j] stores the cost by using first i elements, with using jth (which is smaller than 3) color for ith (which is smaller than N) element.

Source Code:

//Fri Sep 16 16:33:59 CDT 2011
import java.util.*;
import java.util.regex.*;
import java.text.*;
import java.math.*;
import java.awt.geom.*;

public class RGBStreet
{
        public int[][] RGB;
       
        public int[][] dp;
       
        public int estimateCost(String[] houses)
        {
                int N = houses.length;
                RGB = new int[N][3];
                dp = new int[N][3];   //R:0; G:1; B:2;
               
                for(int i=0; i<N; i++){
                        String[] temp = houses[i].split(" ");
                        for(int j=0; j<3; j++)
                                RGB[i][j] = Integer.parseInt(temp[j]);
                       
                        dp[i][0] = Integer.MAX_VALUE;
                        dp[i][1] = Integer.MAX_VALUE;
                        dp[i][2] = Integer.MAX_VALUE;
                }
               
                dp[0][0] = RGB[0][0]; dp[0][1] = RGB[0][1]; dp[0][2] = RGB[0][2];
               
                for(int i=1; i<N; i++){
                        for(int j=0; j<3; j++){
                                for(int k=0; k<3; k++){
                                        if(j!=k){                                         
                                                dp[i][j] = Math.min(dp[i][j], dp[i-1][k] + RGB[i][j]);
                                        }
                                }
                        }
                }
                return Math.min(dp[N-1][0], Math.min(dp[N-1][1], dp[N-1][2]));
        }
       
       
}
//Powered by [KawigiEdit] 2.0!

---

Division Two - Level One:

Solution

Straight-Forward.

Source Code:

//Fri Sep 16 16:43:08 CDT 2011
import java.util.*;
import java.util.regex.*;
import java.text.*;
import java.math.*;
import java.awt.geom.*;

public class SalaryCalculator
{
        public double calcHours(int P1, int P2, int salary)
        {
                if(P1 * 200 >= salary) return 1.0 * salary / P1;
                return 200.0 + (1.0 * salary - P1 * 200) / P2;
        }
      
      
}
//Powered by [KawigiEdit] 2.0!

SRM311

	Level 1	Level 2	Level 3
Div 1	Level 1	Level 2	Level 3
Div 2	Level 1	Level 2	Level 3

Tutorials:

---

Division One - Level Three:

Solution

Source Code:

---

Division One - Level Two:

Solution

Source Code:

---

Division One - Level One:

Solution

The same with Div2, Level 3.

Source Code:

---

Sivision Two - Level Three:

Solution

Alg from Editorial, if (i, j) needed to be changed, then change (i+1, j+1) cell. This is very smart, which could change the cell without changing some cell could not be changed later.

Dynamic Programming.

Source Code:

//Mon Sep 12 16:03:37 CDT 2011
import java.util.*;
import java.util.regex.*;
import java.text.*;
import java.math.*;
import java.awt.geom.*;

public class MatrixTransforming
{
    public int[][] mat;
  
    public void push(int r, int c){
        for(int i=r-1; i<=r+1; i++){
            for(int j=c-1; j<=c+1; j++){
                mat[i][j] ^= 1;
            }
        }
    }
    public int minPushes(String[] a, String[] b)
    {
        int N = a.length;
        int M = a[0].length();
        mat = new int[N][M];
        for(int i=0; i<N; i++) for(int j=0; j<M; j++) mat[i][j] = a[i].charAt(j) - '0';
        int ret = 0;
        for(int i=0; i+2<N; i++){
            for(int j=0; j+2<M; j++){
                if(mat[i][j] != b[i].charAt(j)-'0'){
                    push(i+1, j+1);
                    ret++;
                }
            }
        }
        for(int i=0; i<N; i++) for(int j=0; j<M; j++)
            if(mat[i][j] != b[i].charAt(j)-'0')
                return -1;
        return ret;
    }
  
  
}
//Powered by [KawigiEdit] 2.0!

---

Division Two - Level Two:

Solution

dp[i]: The biggest number(String) by using i matches in total.

PS: dp = new String[55]; here every element in dp will be null, instead of empty value.

Dynamic Programming.

Source Code:

//Thu Sep 15 21:42:11 CDT 2011
import java.util.Arrays;

public class MatchNumbersEasy {
    public String[] dp;

    public String maxNumber(int[] matches, int n) {
        int N = matches.length;
        dp = new String[55];
        for (int i = 1; i <= n; i++)
            dp[i] = "";
        for (int i = 0; i < N; i++) {
            dp[matches[i]] = Integer.toString(i);
        }

        for (int i = 2; i <= n; i++) {
            for (int j = 1; j <= i / 2; j++) {
                String tmp = dp[j] + dp[i - j];
                tmp = sortReversely(tmp);
                if (tmp.length() > dp[i].length() && tmp.charAt(0) != '0')
                    dp[i] = tmp;
                else if (tmp.length() == dp[i].length()
                        && tmp.compareTo(dp[i]) > 0)
                    dp[i] = tmp;
            }
        }
        if (dp[n].length() == 0 || dp[n].charAt(0) == '0')
            return "0";
        return dp[n];
    }

    public static String sortReversely(String s) {
        char[] temp = s.toCharArray();
        Arrays.sort(temp);
        String ret = new String(temp);
        ret = new StringBuffer(ret).reverse().toString();
        return ret;
    }

    
}
// Powered by [KawigiEdit] 2.0!

---

Division Two - Level One:

Solution

Very straight forward.

Source Code:

import java.util.*;
import java.util.regex.*;
import java.text.*;
import java.math.*;
import java.awt.geom.*;

public class EscapeFromRectangle
{
    public int shortest(int x, int y, int w, int h)
    {
        int a = Math.min(Math.abs(x-w), x);
        int b = Math.min(Math.abs(y-h), y);
        return Math.min(a, b);
    }
  
  
}
//Powered by [KawigiEdit] 2.0!

Codeforces Beta Round #86 (Div1 & Div2)

Sep  8, 2011.

Accepted: .        WA: .        NotTried: .

Div 2:
114A.
114B.
Div 1:
113A.
113B.
113C.
113D.
113E.

Tutorial

Problem 1: 114A

Solution:

The precision in java is a miracle. I don''t know why it could let a double number comparable with an integer. but it works.

Source Code:

import java.util.Scanner;

/**
 * 
 */

/**
 * @author antonio081014
 * @date Sep 8, 2011
 * @time 10:01:34 AM
 */
public class Main {

    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        for (int i = 0;; i++) {
            double c = Math.pow(a, i);
            if (c > b) {
                System.out.println("NO");
                break;
            } else if (c == b) {
                System.out.println("YES");
                System.out.println(i - 1);
                break;
            }
        }
    }
}