Solution UVA: 10090 - Marbles

Problem	Verdict	Lang	Time	Best	Rank	Submit Time
| discuss10090 - Marbles	Accepted	C++11	0.010	0.000	1352	1 mins ago

Suggest: (from codeantenna.com/a/WO2VpJHAQP)

/****************************************************************************

 *

 * let d = gcd (n1, n2)

 *     n1 * x + n2 * y = n  <==>  n1 / d * x + n2 / d * y = n / d  ... (1)

 * let n1 / d * x0 + n2 / d * y0 = 1  ... (2)

 *     x0 and y0 can be get by 'Extended Euclid Algorithm'.

 * multiply (2) by 'n / d' and compare to (1), we get:

 *     x = x0 * n / d

 *     y = y0 * n / d

 * if we have x, y such that:

 *     n1 * x + n2 * y = n

 * then we have:

 *     n1 * (x + i * n2 / d) + n2 * (y - i * n1 / d) = n   (i = 1, 2, ...)  ... (3)

 * because 'n1 * (x + i * n2 / d)' increase n1 * n2 / d while 'n2 * (y - i * n1 / d)' decrease n1 * n2 / d.

 * and here 'x' and 'y' are fixed values.

 *

 * according to the statement of the problem, x >= 0 and y >= 0.

 * so we get:

 *     x + i * n2 / d >= 0 and y - i * n1 / d >= 0

 * solve these two inequations we get the range of 'i', let's note the range [l, u]

 *

 * the problem asks us to minimize 'c1 * x + c2 * y',

 * let z = c1 * (x + i * n2 / d) + c2 * (y - i * n1 / d)  ... (4)

 * so (4) is what we want to minimize.

 * since it's monotonically either increasing or decreasing, what we need to do is examine two cases when i == l and i == u.

 *

 ****************************************************************************/

I was able to solve this problem thanks to the hint provided, although it took some time dealing with the equation 

n1 * (x + i * n2 / d) + n2 * (y - i * n1 / d) = n (i = 1, 2, ...)

<=> n1*x + n2*y + n1*n2/d - n2*n1/d = n

<=> n1*x + n2*y + 0 = n

#include<bits/stdc++.h>

#define int long long

#define X first

#define Y second

using namespace std;

typedef pair<int, int> ii;

int euclid(int a, int b){

    if (b==0) return a;

    return euclid(b, a%b);

}

ii extended_euclid(int a, int b, ii aa, ii bb){

    if (b==0) return aa;

    int div= a/b;

    ii cc(aa.X - div * bb.X, aa.Y - div * bb.Y);

    return extended_euclid(b, a%b, bb, cc);

}

int32_t main(){

    ios::sync_with_stdio(0); cin.tie(0);

    int a, b, c, ca, cb;

   

    while(cin >> c && c){

        cin >> ca >> a >> cb >> b;

        int d= euclid(a, b);

        if (c%d) cout<<"failed\n";

        else{

                ii p= extended_euclid(a, b, ii(1, 0), ii(0, 1));      

                int q= c/d;

                int x= p.X*q;

                int y= p.Y*q;

               

                //x + i * b / d >= 0 and y - i * a / d >= 0

                int l= ceil(-x * d * 1.0/b);

                int r= floor(y * d * 1.0/a);

               

                int x1= x + l * b/d;

                int y1= y - l * a/d;

                int x2= x + r * b/d;

                int y2= y - r * a/d;

                if (x1*ca + y1*cb < x2*ca + y2*cb){

                        if (x1<0 || y1<0) cout<<"failed\n";

                        else cout<<x1<<" "<<y1<<"\n";

                }

                else    

                        if (x2<0 || y2<0) cout<<"failed\n";

                        else cout<<x2<<" "<<y2<<"\n";

       

        }

    }

}

 

ma so sv - ho ten sinh vien.docx - Google Drive

Solution UVA: 10182 - Bee Maja

 

Problem	Verdict	Lang	Time	Best	Rank	Submit Time
| discuss10182 - Bee Maja	Accepted	C++11	0.000	0.000	874	55 secs ago

Suggest:
We need to find the rules of grid, i will speak as image:

                                                   

Image 1

Red: down

Green: down_left

Purple: up_left

Blue: up

Yellow: up_right

Pink: down_right

Image 2

Yellow: cycle 1

Green: cycle 2

#include <bits/stdc++.h>

#define X first

#define Y second

using namespace std;

const int N= 1000111;

typedef pair<int, int> ii;

ii a[N];

ii down(ii p){          return ii(p.X, p.Y+1);}

ii down_left(ii p){     return ii(p.X-1, p.Y+1);}

ii up_left(ii p){       return ii(p.X-1, p.Y);}

ii up(ii p)     {       return ii(p.X, p.Y-1);}

ii up_right(ii p){      return ii(p.X+1, p.Y-1);}

ii down_right(ii p){    return ii(p.X+1, p.Y);}

int main() {

        a[1]= ii(0, 0);

        a[2]= ii(0, 1);

        a[3]= ii(-1, 1);

        a[4]= ii(-1, 0);

        a[5]= ii(0,- 1);

        a[6]= ii(1, -1);

        a[7]= ii(1, 0);

        int state=7, c=1;

        while(state <= 100000){

               

                int i= state;

               

                for(i; i<=state+c; ++i) //7 8

                        a[i]= down(a[i-1]);            

                state= i;

               

                for(i; i<=state+c-1; ++i) //7 8

                        a[i]= down_left(a[i-1]); //9

                state= i; //10

               

                for(i; i<=state+c; ++i) //10 11

                        a[i]= up_left(a[i-1]);

                state= i; //12

               

                for(i; i<=state+c; ++i) //12 13

                        a[i]= up(a[i-1]);

                state= i;       //14

               

                for(i; i<=state+c; ++i) //14 15

                        a[i]= up_right(a[i-1]);

                state= i; //16

               

                for(i; i<=state+c; ++i) //16 17

                        a[i]= down_right(a[i-1]);

                state= i; //18

                c++;

        }

        ios::sync_with_stdio(0); cin.tie(0);

       

        int n;

        while(cin >> n){

                cout<<a[n].X<<" "<<a[n].Y<<"\n";

        }

       

}

Solution UVA: 389 - Basically Speaking

 

Problem	Verdict	Lang	Time	Best	Rank	Submit Time
| discuss389 - Basically Speaking	Accepted	C++11	0.060	0.000	465	4 mins ago

Suggest:

- Convert BaseA to Decimal

- Convert Decimal to BaseB

#include<bits/stdc++.h>

#define int long long

using namespace std;

string s;

int a, b;

int f(char x){

        if (x=='A') return 10;

        if (x=='B') return 11;

        if (x=='C') return 12;

        if (x=='D') return 13;

        if (x=='E') return 14;

        if (x=='F') return 15;

        return x-'0';

       

}

char ff(int n){

        if (n<10) return char('0'+n);

        return char('A'+n-10);

}

int toDec(string s, int a){

        int hat= 0, res= 0;

        for(int i=s.size()-1; i>=0; i--)

                res += f(s[i])*pow(a, hat++);

        return res;

}

string toAns(int n, int b){

        string s="";

        while(1){

                s = ff(n%b) + s;

                n /= b;

                if (n==0) break;

        }

        return s;

}

int32_t main(){

        ios::sync_with_stdio(0); cin.tie(0);

        while(cin >> s >> a >> b){

                int dec= toDec(s, a);

                string ans= toAns(dec, b);

               

                if (ans.size() > 7)

                        cout << setw(7) << "ERROR"<< "\n";

                else

                        cout << setw(7) << ans << "\n";

               

        }

       

}

Solution UVA: 11231 - Black and white painting

 

Problem	Verdict	Lang	Time	Best	Rank	Submit Time
| discuss11231 - Black and white painting	Accepted	C++11	0.000	0.000	2576	53 secs ago

Suggest:

- Number of the white right bottom of chessboard is the result

"Any embedded chessboard can be identified uniquely with its lower right corner. 

If we count the number of valid lower-right-hand-corners, we thus have our solution."

(algorithmist.com)

#include <bits/stdc++.h>

#define int long long

using namespace std;

int32_t main() {

        ios::sync_with_stdio(0); cin.tie(0);

        int n, m, c;

        while(cin >> n >> m >> c && !(n==0 && m==0 && c==0)){

                n-=7, m-=7;

                cout<<(c ? (n*m+1)/2 : n*m/2)<<"\n";

        }

}

Solution UVA: 11401 - Triangle Counting

Problem	Verdict	Lang	Time	Best	Rank	Submit Time
| discuss11401 - Triangle Counting	Accepted	C++11	0.000	0.000	798	28 secs ago

Suggest:

- Let's denote F[n] as the number of triangles formed from n sides. I've observed that the number of triangles formed from n sides will include F[n-1] + add(n).

- Here, add(n) represents the number of triangles that contain side n.

* For example, with n=6, we will have the following triangles:

- Triangles with n=5 (not containing side 6):

    

    According to the test, we have 3 triangles.

- Triangles containing side 6:

    2 5 6    

        => 1

    3 4 6

    3 5 6

        => 2

    4 5 6

        => 1

Therefore, the result of F[6] = 3 + (1+2+1) = 7.

* Note that add(n) will differ between even and odd n values. I will provide further examples to help you visualize the cases:

F[3] = 0

F[4] = 1

F[5] = 1 + (1+1) = 3

F[6] = 3 + (1+2+1) = 7

F[7] = 7 + (1+2+2+1) = 13

F[8] = 13 + (1+2+3+2+1) = 22

F[9] = 22 + (1+2+3+3+2+1) = 34

=> We can readily observe a pattern quite similar to Pascal's Triangle.

 

#include<bits/stdc++.h>

#define int long long

using namespace std;

int F[1000111];

int add(int n){

        int r= n/2-1, l=1;

        int p= r-l+1;

        int s= (l+r)*(1.0*p/2);

        if (n%2) return s*2;

        return s*2-r;

}

int32_t main(){

        F[3]=0, F[4]=1;

        for(int i=5; i<=1000000; i++)

                F[i] = F[i-1] + add(i);

        ios::sync_with_stdio(0); cin.tie(0);

        int n;

        while(cin >> n && n>=3){

                cout<<F[n]<<"\n";

        }

       

}