ACM - Псков

Информация о пользователе

Привет, Гость! Войдите или зарегистрируйтесь.


Вы здесь » ACM - Псков » Timus » Задача 1440


Задача 1440

Сообщений 1 страница 8 из 8

1

Условие:
http://acm.timus.ru/problem.aspx?space=1&num=1440

Задача в принципе не моя, на аккуратное кодирование.
Я старалсо, но не заходит, грит WA5

Посмотрите код, может увидите ошибку.

Код:
#include <iostream>
#include <string>
#include <map>
using namespace std;

string day;
string month;
int date;
int mn, mx;
int num[10];
string days[7] = {"Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday", "Sunday"};
string months[4] = {"September", "October", "November", "December"};

map <int, string> ISd;
map <string, int> SId;
map <int, string> ISm;
map <string, int> SIm;
int monthl[4] = {30, 31, 30, 24};


void readdata(){
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
	cin >> day;
	cin >> month;
	cin >> date >> mn >> mx;
}

void mapcreate(){
	for(int i=0;i<7;i++){
    ISd[i]=days[i];
    SId[days[i]]=i;
	}
	for(int i=0;i<4;i++){
    ISm[i]=months[i];
    SIm[months[i]]=i;
	}	
}

int curmonth;
int curday;
int limmonth;
int limday;

void precalc(){
	curmonth = 0;
	curday = SIm[day];
	curday++;
	if(curday==7)curday=0;
	limmonth = SIm[month];
	limday = date;
	limday--;
	date=1;
	while(curmonth < limmonth || date < limday ){
    num[curday]++;
    curday++;
    date++;
    if(curday == 7)curday=0;
    if(date == monthl[curmonth]){
    	curmonth++;
    	date=0;
    }    
	}
}

bool found = false;
string ans;
char ch;
string s = "";

void recsolve(int shag, int sum){
	if(shag == 8 || found){
    return;
	}else if(sum >=mn && sum <=mx){
    found = true;
    ans = s;
	}else {
    if(num[shag]){
    	s.push_back(shag+48);
    	recsolve(shag+1, sum+num[shag]);
    	s.erase(s.size()-1, 1);
    }
    recsolve(shag+1, sum);
	}	
}



int main(){
	readdata();
	mapcreate();
	precalc();
	recsolve(0, 0);
	if(!found) cout << "Impossible\n";
	else {
    cout << ans.size() << endl;
    for(int i=0;i<ans.size();i++){
    	if(num[ans[i]-48]){
        cout << days[ans[i]-48] << endl;
    	}
    }
	}
	return 0;
}

2

Только не обращайте внимание на изврат с четырьмя map - ами.  Он работает.  :crazy:

mapcreate();   -     проставление соответствия месяц/номер месяца и день/номер дня
precalc();  -   календарь, рассчитывает сколько раз встретился каждый день недели, проверял, считает
recsolve(0, 0);  -  рекурсивный перебор 7 чисел на достижимость суммы из диапазона

3

А почему рекурсия срезается на восьмом дне недели, а запускается на нулевом?

4

Изначально срезалась на 7-м, но после ВА поднял, чтобы срезания небыло вообще.

Если ответ найден до восьмого шага, то рекурсия срежется по второму условию.
А на восьмом шаге ответ не может быть найден, т.к. используемость восьмого шага = 0
num[7] == num[8] == 0

5

Зачем в прекальке строка limday--; ? Ты же со строгим условием в цикле работаешь. День матча и так не будет посчитан

6

У меня нумерация дней в месяце, как и нумерация месяцев, начинается с 0.
Поэтому считанную дату надо продекриментить, для приведения к моей нумерации.
Аналогично стартовая дата не 2, а 1   -    следующая строка -   date=1;

7

Вторая строка должна выглядеть как curday = SId[day];

В твоем варианте всегда стартовый день имеет номер 0.

Ломающий тест:
Sunday
September 3
1 1
Дает 1 Tuesday

ЗЫ: Никогда больше не используй пробелы для табуляции. Читабельность отступов нулевая

Отредактировано Kelt (2009-01-08 22:45:44)

8

Пасиба. Исправил одну буковку - сдалась.

ЗЫ: отступы расставлены корректно.

Отредактировано Ktulhu (2009-01-08 23:09:40)


Вы здесь » ACM - Псков » Timus » Задача 1440