How did you find the alhorithm, AC-guys?

I hate such tasks so much! It's not programming, it's pure math!! So how did you proved the algorithm? I broke my brain truying to solve it!!

Re: How did you find the alhorithm, AC-guys?

Posted by

melkiy 12 Nov 2009 03:00

You must understand that there are needed as mush cuts as there are little squares in the bar (minus 1).

Imagine that the bar has the shape 1xnm. How many cuts? (n-1), yeah?

Since at the very end all pieces are the little squares, the shape of intermediate cuts doesn't matter, the total cuts count to (n-1).

to melkiy

Thank you very much!)

You saved hours of my life!

Re: How did you find the alhorithm, AC-guys?

My observation: one cut buys us plus one piece of chocolate, because we can cut only one piece at a time. So, after the first cut we have two pieces, after the second one, we have three pieces, and so on until we have n*m pieces. Now it's easy to see that we only need to check the parity of n*m

Re: How did you find the alhorithm, AC-guys?

Is it possible at all?

Re: How did you find the alhorithm, AC-guys?

There is a winning strategy for the second player is to mirror moves of the first, but if N or M is even, the first player can split it in two halves - the only move cannot be mirrored and wins.

Re: How did you find the alhorithm, AC-guys?

Posted by

ELDVN 29 Oct 2015 23:16

my solution:

#include <iostream>

#include <string>

#include <vector>

#include <set>

#include <queue>

#include <map>

#include <stack>

#include <algorithm>

#include <bitset>

#include <cstring>

#include <cmath>

#include <cstdlib>

#include <cstdio>

#include <iomanip>

#define F first

#define S second

#define ll long long

#define len length()

#define sqr(x) x*x

#define pb push_back

#define mp make_pair

#define sz(x) ((int) (x).size())

#define all(x) x.begin(), x.end()

#define allr(x) x.rbegin(), x.rend()

#define bp(x) __builtin_popcount(x)

#define INF numeric_limits<long long int>::max()

#define frp freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);

#define forit(it, s) for(__typeof(s.begin()) it = s.begin(); it != s.end(); it++)

const int maxn = (int)1e6;

const int mod = (int)1e9 + 7;

using namespace std;

int n,m;

main(){

scanf("%d%d",&n,&m);

if(n*m%2==0)

puts("[:=[first]");

else

puts("[second]=:]");

return 0;

}

Re: How did you find the alhorithm, AC-guys?

That's the thought. It is conjectured that however youcut it during the process, the total steps are always the same, but I didn't prove it. Now Iget it. Thank you.

Re: How did you find the alhorithm, AC-guys?

mathem much important in programming. U MUST know that, if u dont wants to write indian code