Пожалуйста, прочтите новое правило об ограничении использования AI-инструментов. ×

Блог пользователя MarioYC

Автор MarioYC, 13 лет назад, По-английски
I cant't understand the following example case

4 4 2 + 1 + 2 - 1 - 2 + 2 + 1 - 2 - 1

the answer is :-(

But if the first mage does all its four actions, and after that the second mage does
all its four actions, then there would be no problem. Why isn't this possible?

Edit:

Now I'm getting WA #5, basically what I do is fix the number of moves that both mages
could have done before none of them can perform an action.


#include <iostream>
#include <cstring>

using namespace std;

int main(){
    int T,n,m,k,val1[1000],val2[1000];
    int used[1001];
    char op1[1000],op2[1000];
    
    cin >> T;
    
    while(T--){
        cin >> n >> m >> k;
        
        for(int i = 0;i < n;++i) cin >> op1[i] >> val1[i];
        for(int i = 0;i < m;++i) cin >> op2[i] >> val2[i];
        
        bool found = false;
        
        for(int i = 0;i <= n;++i){
            memset(used,0,sizeof used);
            
            for(int j = 0;j < i;++j){
                if(op1[j] == '+') ++used[ val1[j] ];
                else --used[ val1[j] ];
            }
            
            bool valid = true;
            
            for(int j = 0;j <= m;++j){
                if(j > 0){
                    if(op2[j - 1] == '+') ++used[ val2[j - 1] ];
                    else --used[ val2[j - 1] ];
                    
                    if(used[ val2[j - 1] ] == 2 || used[ val2[j - 1] ] == -2) valid = false;
                }
                
                if(!valid) break;
                
                if(i < n && j < m && op1[i] == '+' && op2[j] == '+'){
                    if(used[ val1[i] ] > 0 && used[ val2[j] ] > 0)
                        found = true;
                }
            }
        }
        
        if(found) cout << ":-(" << endl;
        else cout << ":-)" << endl;
    }
    
    return 0;
}

Edit2: Finally got AC, after adding a counter that keeps the number of indices where
abs(used[i]) == 2. The state is possible to reach only if its value is zero.

  • Проголосовать: нравится
  • +4
  • Проголосовать: не нравится

13 лет назад, # |
Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится
Wrong language.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Кстати, задача - нехилый боян. Дальневосточный четвертьфинал 2008 года.
http://ipc.susu.ac.ru/11909.html
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

This is a dead-lock problem. Zagamius and Sandro are threads, and mages are resources.

At first Sandro performs +1, then Zagamius +2, and deadlock now.

13 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится
Just use f(i, j) to solve it. This problem is not very difficult.