שתי שאלות קשות שהמורה שלי הביא....

[X-BLADE]

צודק, יש טעות בחישוב שלי.

אתה צריך לבדוק גם אם N-i+1 > N-j+1. שים לב שכיוון ש-i<j, אז הביטוי הזה תמיד נכון, כלומר אין צורך באמת לבדוק אותו (אלא רק להעלות את mone ב-1).

כמו שאמרתי - הפתרון הזה הוא הדבר שהכי פשוט לחשוב עליו, לא הדבר הכי יעיל. אפשר פשוט לנסח את הפתרון לשאלה ע"י נוסחה מתמטית פשוטה, ולכן לפתור את התרגיל בהצבת ה-N בנוסחה הזו.

אחי זה עובד בדקתי את זה עם המספרים 2 ו4.

עכשיו שאלה: למה זה לא עובד עם מספרים זוגיים [למרות שאתה עשית את העבודה מצויין כי השאלה מדברת על קלט זוגי] הרי אין הבדל בפתרון אם זה זוגי או לא זוגי [אם הבנתי נכוןת וכנראה שלא] אז אם תוכל להסביר לי למה אודה לך מאוד. אגב זו התוכנית לאחר השינוי:

  public static void main(String[] args) {
Scanner in=new Scanner(System.in);
int n,mone=0,i=0,j=0;
n=in.nextInt();
for (i=1;i<=n;i++)
{
	for (j=i+1;j<=n;j++)
	{
		if (n-i+1>j)
		mone++;
		if (n-j+1<i)
		mone++;
		mone++;
	}
}
 System.out.println(mone);
 }
}

בנוסף שמתי לב שיש לך מוח נדיר, אולי תוכל לנסות לפתור את התרגיל השני???כתוב ברמז שהוא קשור איכשהו לסדרת פיבונצ'י. אם אתה רוצה יש באתר של האולמפיאדה הזאת בשאלונים הקודמים יש הרבה דוגמאות לסוגי משחקים דומיםת ובפתרונות גם כן ראיתי שיש קשר לפיבונצ'י אבל לא כ"כ הבנתי אתה כנראהתבין אז אם תוכל להסביר לי אני ממש אשמח...תודה רבה על העזרה!

אה ושכחתי עוד משהו: מה זה סיבוכיות O(n) ?

[שניצל]

אני מניח שאתה מתכוון מספרים אי-זוגיים.

באמת יש בעיה עם מספרים אי-זוגיים - עבור X ששווה ל-N+1)/2), שני הקווים שיוצאים ממנו הם בעצם אותו קו, והאלגוריתם מתייחס אליו כאילו אלה שני קווים שונים.

אז בעקרון אתה צריך להתייחס במיוחד למקרה הזה.

סיבוכיות זה נושא קצת יותר מתקדם... בגדול זה אומדן לכמה "מסובך" האלגוריתם (כמה הוא יעיל או לא) ביחס לגודל הקלט.

סיבוכיות (O(N אומרת שזמן הריצה של האלגוריתם תלוי באופן לינארי בגודל הקלט (N). תכנית עם לולאה אחת שרצה על כל הקלט בד"כ תהיה בסיבוכיות כזו.

סיבוכיות (O(1 אומרת שזמן הריצה של האלגוריתם קבוע, ואינו תלוי בגודל הקלט.

האלגוריתם שנתתי לך לפתרון התרגיל הוא בסיבוכיות (O(N^2, כי יש לך לולאה בתוך לולאה. כמו שאמרתי, האלגוריתם שנתתי לך בסיסי מאוד ולא יעיל.

לגבי התרגיל השני, לא ממש הצלחתי לחשוב על פתרון בשבילו עדיין.

[X-BLADE]

הנה אחי שיניתי את התוכנית לכך:

  public static void main(String[] args) {
Scanner in=new Scanner(System.in);
int n,mone=0,i=0,j=0;
n=in.nextInt();
for (i=1;i<=n;i++)
{
	for (j=i+1;j<=n;j++)
	{
	if (j%2==0)	
	{
				if (n-i+1>j)
		mone++;
		if (n-j+1<i)
		mone++;

	mone++;
}
if (j%2!=0)
{
					if (n-i+1>j)
		mone++;
		if (n-j+1<i)
		mone++;
}
	}
}
 System.out.println(mone);
 }
}

וזה עובד, תודה רבה!

[dganit30]

בקשר לשאלה 1

הפתרון הוא מגאומטריה חישובית ונקרא SWEEP LINE

אם תרצה ..תקרא קצת על זה

http://en.wikipedia.org/wiki/Sweep_line_algorithm

[X-BLADE]

אחי לא כ"כ הבנתי מה כתוב שם לא רק בגלל שזה היה באנגלית...אם תוכל להסביר לי אודה לך...

ולגבי הפתרון של שניצל, הסברת לי שהוא לא עובד טוב עם אי זוגיים בגלל שיש שם קו מתלכד בעצם, למה התוכנית לא יודעת את זה???זה בגלל שהיא מונה את החיתוך בו כשני קווים?