ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1639. Chocolate 2

How did you find the alhorithm, AC-guys?
Posted by Komarov Dmitry [Pskov SPI] 12 Nov 2009 01:52
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
Posted by Komarov Dmitry [Pskov SPI] 12 Nov 2009 11:17
Thank you very much!)
You saved hours of my life!
Re: How did you find the alhorithm, AC-guys?
Posted by Mindaugas Kazlauskas 26 Jun 2011 07:47
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?
Posted by ONU_Bullsquid 24 Oct 2012 19:38
Is it possible at all?
Re: How did you find the alhorithm, AC-guys?
Posted by Anisimov Dmitry (Novosibirsk STU) 15 Oct 2014 12:30
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?
Posted by zhangweilst 6 Dec 2015 09:51
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?
Posted by kert_sad 8 Dec 2017 00:33
mathem much important in programming. U MUST know that, if u dont wants to write indian code