Discussion @ 1639. Chocolate 2 @ Timus Online Judge

Vlad correct code [2] // Problem 1639. Chocolate 2 7 Jan 2012 09:24

Nargiza Asqarova Bu....... [4] // Problem 1639. Chocolate 2 1 Dec 2011 17:50

xatosi qayerda bilasizmi?

var m,n:1..50;
   begin
   read(m,n);
   if odd(m*n)then write('[second]:=]')
   else write('[:=[first]');
end.

Zaripova Aziza Re: Bu....... // Problem 1639. Chocolate 2 8 Dec 2011 19:08

var a,n,m:word;
begin
a:=m*n-1;
if a mod 2=0 then
writeln('[second]=:]') else
writeln('[:=[first]');readln;
readln;end.

choriyev bekzod Re: Bu....... // Problem 1639. Chocolate 2 8 Dec 2011 19:15

#include <stdio.h>
void main()
{
int n,m;
scanf("%d %d",&m,&n);
printf("%s",(m*n%2)?"[second]=:]":"[:=[first]" );
}

Sunnat hojiyevsunatullo_1991@mail.ru [1] // Problem 1639. Chocolate 2 8 Dec 2011 19:20

men paskallni yaxshi tushunmiyman C++ da kod quyidagicha yozilgan:

#include<iostream>
using namespace std;
int main()
{
    int n,m,s1=0,s2=0,i=0;
    cin>>n>>m;
    while(i==0)
    {
       if(n%2==0||m%2==0)
       {
           if(n%2==0&&m%2==0)
           {
                if(n>m)n=n/2;
                else m=m/2;
           }
           else if(n%2==0)n=n/2;
           else m=m/2;
           s1+=n*m;
        }
        else
        {
        s1+=1;
        s2+=n*m-1;
        n=0;m=0;i=1;
        }

      //------------------------------------------------
        if(n%2==0||m%2==0)
        {
           if(n%2==0&&m%2==0)
           {
                if(n>m)n=n/2;
                 else m=m/2;
           }
           else if(n%2==0)n=n/2;
           else m=m/2;
           s2+=n*m;
         }
         else
         {
            s2+=1;
            s1+=n*m-1;
             n=0;m=0;i=1;
         }

    }
    if(s1>=s2)cout<<"[:=[first]";
    else cout<<"[second]=:]";
    return 0;
}

Muhammad Re: hojiyevsunatullo_1991@mail.ru // Problem 1639. Chocolate 2 13 Nov 2020 16:42

//javada ,in java

import java.util.Scanner;
public class ONETHOUSANDTWO {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int s1 = 0, s2 = 0, i = 0;
        if ((m * n - 1) % 2 == 0) {
            System.out.println();
        }

        while(i==0)
        {
            if(n%2==0||m%2==0)
            {
                if(n%2==0&&m%2==0)
                {
                    if(n>m)n=n/2;
                    else m=m/2;
                }
                else if(n%2==0)n=n/2;
                else m=m/2;
                s1+=n*m;
            }
            else
            {
                s1+=1;
                s2+=n*m-1;
                n=0;m=0;i=1;
            }

            //------------------------------------------------
            if(n%2==0||m%2==0)
            {
                if(n%2==0&&m%2==0)
                {
                    if(n>m)n=n/2;
                    else m=m/2;
                }
                else if(n%2==0)n=n/2;
                else m=m/2;
                s2+=n*m;
            }
            else
            {
                s2+=1;
                s1+=n*m-1;
                n=0;m=0;i=1;
            }

        }
        if (s1>=s2) System.out.println("[:=[first]");
        else System.out.println("[second]=:]");
    }
}

Sunnat wrote 8 December 2011 19:20

men paskallni yaxshi tushunmiyman C++ da kod quyidagicha yozilgan:

#include<iostream>
using namespace std;
int main()
{
    int n,m,s1=0,s2=0,i=0;
    cin>>n>>m;
    while(i==0)
    {
       if(n%2==0||m%2==0)
       {
           if(n%2==0&&m%2==0)
           {
                if(n>m)n=n/2;
                else m=m/2;
           }
           else if(n%2==0)n=n/2;
           else m=m/2;
           s1+=n*m;
        }
        else
        {
        s1+=1;
        s2+=n*m-1;
        n=0;m=0;i=1;
        }

      //------------------------------------------------
        if(n%2==0||m%2==0)
        {
           if(n%2==0&&m%2==0)
           {
                if(n>m)n=n/2;
                 else m=m/2;
           }
           else if(n%2==0)n=n/2;
           else m=m/2;
           s2+=n*m;
         }
         else
         {
            s2+=1;
            s1+=n*m-1;
             n=0;m=0;i=1;
         }

    }
    if(s1>=s2)cout<<"[:=[first]";
    else cout<<"[second]=:]";
    return 0;
}

Vladislav Ershov Python Solution. // Problem 1639. Chocolate 2 21 Jul 2019 14:02

SpamBot Я и Балл // Problem 1639. Chocolate 2 28 Jan 2019 02:47

Komarov Dmitry [Pskov SPI] How did you find the alhorithm, AC-guys? [8] // Problem 1639. Chocolate 2 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!!

melkiy Re: How did you find the alhorithm, AC-guys? [1] // Problem 1639. Chocolate 2 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).

Komarov Dmitry [Pskov SPI] to melkiy // Problem 1639. Chocolate 2 12 Nov 2009 11:17

Thank you very much!)
You saved hours of my life!

Mindaugas Kazlauskas Re: How did you find the alhorithm, AC-guys? [2] // Problem 1639. Chocolate 2 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

ONU_Bullsquid Re: How did you find the alhorithm, AC-guys? // Problem 1639. Chocolate 2 24 Oct 2012 19:38

Is it possible at all?

zhangweilst Re: How did you find the alhorithm, AC-guys? // Problem 1639. Chocolate 2 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.

Anisimov Dmitry (Novosibirsk STU) Re: How did you find the alhorithm, AC-guys? // Problem 1639. Chocolate 2 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.

ELDVN Re: How did you find the alhorithm, AC-guys? // Problem 1639. Chocolate 2 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;
}

kert_sad Re: How did you find the alhorithm, AC-guys? // Problem 1639. Chocolate 2 8 Dec 2017 00:33

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

Marginean Ciprian Solved in O(1). [1] // Problem 1639. Chocolate 2 31 Oct 2008 20:48

Aleksandr Скорость негодует [3] // Problem 1639. Chocolate 2 16 Jan 2017 02:13

Народ, кто может указать на часть моего кода которая тормозит алгоритм? Чистил как мог, не смог выйти за 0.125 секунд

import java.util.Scanner;
public class Timus {
        public static void main (String[] args)
        {
            Scanner in = new Scanner(System.in);

            byte m = in.nextByte(), n = in.nextByte();

            System.out.println( (m*n-1)%2==0 ? "[second]=:]" : "[:=[first]");

            in.close();

        }
}

Oleg Baskakov Re: Скорость негодует [2] // Problem 1639. Chocolate 2 16 Jan 2017 04:49

Всё нормально, просто джава медленная. Вон у вас задача a+b за 0.109.

Aleksandr Re: Скорость негодует [1] // Problem 1639. Chocolate 2 16 Jan 2017 15:12

Спасибо за пояснение;) а каким же образом люди в топе выходят за 0.05 секунд? Вон первое место в А+B аж за 0.015 работает! Наверняка люди обходят стороной медленные методы и операции. Может вы знаете ресурс где можно почитать об этом? Поиск в гугле ни привёл ни к чем

Oleg Baskakov Re: Скорость негодует // Problem 1639. Chocolate 2 16 Jan 2017 23:11

К сожалению, не могу сказать точно. Тут есть несколько моментов.
Во-первых, более ранняя джава была быстрее, что можно увидеть по тому, что в основном большинство сабмитов, где указано java 1.5 / java 1.6, быстрее, чем те, в которых java 1.8. Конечно, этот сабмит а+б за 0.015 как раз на джаве 1.8, для меня это конечно странно. Может в коде в опциях был выставлен какой-то ключ для использования более ранней версии или типа того...
Во-вторых, "общий" совет, который я могу дать — используйте BufferedReader (и если надо, StreamTokenizer) вместо Scanner'a, потому что последний в джаве обычно медленнее. (см. также код внизу страницы http://acm.timus.ru/help.aspx?topic=java&locale=ru). Хотя, конечно, для программ с маленьким объёмом входных данных разница не должна быть сильно критичной, но там где надо считывать со входа мегабайты — она очень ощутима.

lhyx1990 ac c++ // Problem 1639. Chocolate 2 26 Jan 2014 15:08

shailendrasky what's wrong with this code.....???? // Problem 1639. Chocolate 2 31 Dec 2013 01:56

Cawa222 error in test#9 // Problem 1639. Chocolate 2 25 Jul 2013 00:45

BlackShark ??????? [1] // Problem 1639. Chocolate 2 6 Mar 2009 20:03

tudorfrent am solutia // Problem 1639. Chocolate 2 1 Nov 2012 14:37

isolver example // Problem 1639. Chocolate 2 28 Apr 2012 12:30

Kirill where error????? [2] // Problem 1639. Chocolate 2 23 Dec 2011 16:22

Tom what s wrong here ? WA2 [1] // Problem 1639. Chocolate 2 4 Aug 2011 22:58

milad why is my code wrong?????????? [1] // Problem 1639. Chocolate 2 8 Jul 2011 21:11

jacinto It doesn't need "return 0" In the end of the program ? [1] // Problem 1639. Chocolate 2 1 Jul 2011 06:16

kutenin Very easy :D // Problem 1639. Chocolate 2 2 Jan 2011 12:06

Bagdat Answer // Problem 1639. Chocolate 2 23 Mar 2009 00:20

Vedernikoff Sergey (HSE: EconomicsForever!) No topic // Problem 1639. Chocolate 2 25 Oct 2008 22:29

Discussion of Problem 1639. Chocolate 2